# Determine order in which the 3 inputs go high

Specs

Three input signals: A, B, C that are all low upon reset

Only one signal goes high at a time. Once a signal is high, it remains high until reset

Output the order in which the three signals arrived. You can encode this output however you prefer

Sort of a phase comparator, but with 3 inputs

My attempt

Create a moore FSM with 10 states: idle, a,b,c,ab,ac, ba, bc, ca, cb. The terminating 6 states each correspond to one of the 6 possible outputs.

I feel this is overkill for something as simple. Does any one have a more elegant approach to tackle this problem? A smaller fsm maybe? Your suggestion could be completely orthogonal to mine as long as it is simpler.

• Your explanation is inconsistent. You initially talk about signals going high, but then ask about the order they "arrive" in. You haven't said anything about propagation or other delays, so this makes no sense. Also, what is the minimum guaranteed time between one signal going high and the next one going high? Commented Feb 10, 2018 at 18:56
• @OlinLathrop I assume "arrive" = "goes high" and that signal separation is sufficient for whatever logic family is being used Commented Feb 10, 2018 at 18:57
• @OlinLathrop The first two paragraphs are completely unambiguous. Commented Feb 10, 2018 at 19:01
• Yes, there is no issue about signal separation. Only one of them goes high at any instant, and then there's long enough time until the next one goes high. Commented Feb 10, 2018 at 19:04
• Because you're tracking a time relationship between the signals, the solution will have to be based around registers (flip-flops) to record the previous positions. A combinatorial logic circuit is capable of tracking time relationships. Besides an FSM, a circuit that captures the 3-bit input in a 3-stage 3-bit shift register could be used, with combinatorial logic or a LUT encoding the 6-bit result code (2-bits for each of 3 what-happened-next codes). But that may be more gates than the FSM, dunno Commented Feb 10, 2018 at 19:07

Dave suggests using six D-latches (four gates each), but you only really need six gates total, or seven if you want to detect when all input are high.

A NAND SR-latch will remember its state when both inputs are high. When both inputs are low, both outputs are high. This lets us detect that the output isn't stable.

If you don't need to detect if the order of inputs is known already, it also suffices to take just one output from each pair. If you want to know when all inputs are high, add an extra three-input gate in parallel to the latches.

• Very good! You just need one more layer of gates to decode the six possible sequences. In addition, this implicitly tells you when the sequence is complete. Commented Feb 10, 2018 at 19:47
• The question states "You can encode this output however you prefer". If you want a vector of six indicators, you can add six more gates, but it isn't a part of the requirements. Commented Feb 10, 2018 at 19:50

An asynchronous FSM is one logical way to approach this, but I think it would be easier (in terms of design effort) to simply employ six latches.

The latches are arranged in three pairs, in which each input signal latches the states of the other two signals at the time that it goes high. From these six variables, its a simple combinatorial problem to decode the six possible outcomes. Start by decoding the latch outputs in each pair to determine whether the enable sginal went high first (both latches low), second (one latch or the other is low) or third (both latches high).

simulate this circuit – Schematic created using CircuitLab

• By six latches, do you mean six gates in three latches? I'm not exactly sure how you intend to wire the six latches. Commented Feb 10, 2018 at 19:14
• @JohnDvorak: A latch is a memory device in which the input is copied to the output when the "enable" input is active, but holds its previous value when the enable is inactive. It is equivalent to approximately four gates. Commented Feb 10, 2018 at 19:17
• Is it a convention that "latch" defaults to D latches? Usually one uses SR because it's fewer gates. Commented Feb 10, 2018 at 19:24
• simulator.io/board/obvlhqBe2A/1 Commented Feb 10, 2018 at 19:35
• @Trevor_G: Very good. I was doing the same thing in CircuitLab. I realized that I didn't really need to deocde the "this signal second" state explicitly at all. Commented Feb 10, 2018 at 19:41

only three bits of state are needed, two to encode the first high, and another bit to encode which of the other two was the second high.

in other words the states a,b,c can each be merged with one of the terminal states.

state.  INPUT  result state

0      010     1
0      100     2
0      011     3
1      110     4
2      101     5
any     000     0


all other inputs, keep current state.

• That's true; once two signals have gone high, you have your answer. Commented Feb 10, 2018 at 19:05
• @Jasen I didn't follow you on the "another bit to encode which of the other two was the second high" part. Are you suggesting a Mealy FSM solution? Commented Feb 10, 2018 at 19:28
• yes mealy FSM, there are only two choices for the second input given that one of inppts is already high. so a single flip-flop is all that's required to store this. Commented Feb 10, 2018 at 19:59
• Actually a Moore machine is sufficient unless unless you need to suppress the output until there is full (or unambiguous input) Commented Feb 10, 2018 at 20:14

I'd do it this way...

Simulator