1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Olin Lathrop Feb 10 '18 at 18:56
  • 1
    \$\begingroup\$ @OlinLathrop I assume "arrive" = "goes high" and that signal separation is sufficient for whatever logic family is being used \$\endgroup\$ – John Dvorak Feb 10 '18 at 18:57
  • 1
    \$\begingroup\$ @OlinLathrop The first two paragraphs are completely unambiguous. \$\endgroup\$ – Dave Tweed Feb 10 '18 at 19:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – frank_010 Feb 10 '18 at 19:04
  • \$\begingroup\$ 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 \$\endgroup\$ – TonyM Feb 10 '18 at 19:07
2
\$\begingroup\$

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.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Dave Tweed Feb 10 '18 at 19:47
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Feb 10 '18 at 19:50
2
\$\begingroup\$

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).

schematic

simulate this circuit – Schematic created using CircuitLab

\$\endgroup\$
  • \$\begingroup\$ By six latches, do you mean six gates in three latches? I'm not exactly sure how you intend to wire the six latches. \$\endgroup\$ – John Dvorak Feb 10 '18 at 19:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Dave Tweed Feb 10 '18 at 19:17
  • \$\begingroup\$ Is it a convention that "latch" defaults to D latches? Usually one uses SR because it's fewer gates. \$\endgroup\$ – John Dvorak Feb 10 '18 at 19:24
  • \$\begingroup\$ simulator.io/board/obvlhqBe2A/1 \$\endgroup\$ – Trevor_G Feb 10 '18 at 19:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Dave Tweed Feb 10 '18 at 19:41
2
\$\begingroup\$

Your answer is slightly more complex than needed

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.

\$\endgroup\$
  • \$\begingroup\$ That's true; once two signals have gone high, you have your answer. \$\endgroup\$ – Dave Tweed Feb 10 '18 at 19:05
  • \$\begingroup\$ @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? \$\endgroup\$ – frank_010 Feb 10 '18 at 19:28
  • \$\begingroup\$ 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. \$\endgroup\$ – Jasen Feb 10 '18 at 19:59
  • \$\begingroup\$ Actually a Moore machine is sufficient unless unless you need to suppress the output until there is full (or unambiguous input) \$\endgroup\$ – Jasen Feb 10 '18 at 20:14
1
\$\begingroup\$

I'd do it this way...

enter image description here

Simulator

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.