Tell me more ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.
up vote 1 down vote favorite

I need to design a 4-input sequence detector and I'm really having trouble with this.

The numbers are entered as a 4 digit input (0010 is 2, 0110 is 6, etc).

The sequence must detect, for instance, a 5 digit key (i.e 3-4-1-7-5)

I'm really troubled with the design methodology for this problem, because if we do it the traditional way, it's going to take forever, we need 3 state variables and 11 different inputs possibilities to deal with (the 1010 key is "clear")

If we type 3-4-4, the sequence must clear, for example.

If we type 3-4-1-7-5 (the correct sequence), then the output should be a logical 1.

Otherwise, the output is zero.

Any help greatly appreciated.

EDIT: the sequential circuit is synchronous (has an external clock source)

share|improve this question
What have you tried? Is this in Verilog or VHDL? – Greg Aug 1 at 23:59
This is just to draw the schematic of the sequential circuit. I've tried using flip-flops, but I couldn't get the sequence to clear properly, and the way I was trying is just guessing and checking, which is bad. – triplebig Aug 2 at 0:07
Why don't you try drawing a state diagram, like a flowchart? I think you'll see that the problem isn't as hard as you think. – Joe Hass Aug 2 at 0:09
I have, as I've stated in my question. It's quite a simple state diagram. But there are ELEVEN different input possibilities (remember there are four inputs, and not one). Each of these will lead to a different state, which is associated to three state variables. This method will be too troublesome, and I'm looking for a simpler way, given the simplicity of the state diagram. I'd appreciate it if you could assist with the state diagram --> circuit transition – triplebig Aug 2 at 0:15
Why not use a counter and a LUT for the current valid input, and clear if not valid? – Ignacio Vazquez-Abrams Aug 2 at 0:30
show 6 more comments

2 Answers

up vote 2 down vote accepted

Here's a hint: The states in your state machine are not associated with the binary codes representing the key inputs, they're associated with the number of correct numbers entered so far. You start out in an initial, or "reset" state, in which no valid keys have been entered so far, and then proceed to states representing 1 valid key entered, 2 valid keys entered, etc. until you get to the final state with 5 valid keys entered. In the last state, the output is 1; in all others it's 0.

In each state, if the next valid key is entered, you proceed to the next state; otherwise, you go back to the initial state.

share|improve this answer
but they have to be associated with which key is pressed, and in what state. Otherwise I can just press the right keys in the wrong order and it is going to work. Sorry, but I don't understand your meaning. – triplebig Aug 2 at 0:48
@triplebig: Only one key will advance to the next state. Any other will clear. – Ignacio Vazquez-Abrams Aug 2 at 0:52
Say you make it really simple so that you have ST0 -> ST5. In ST0 if you see the correct bit pattern on the 4-bit keyed input you then transition to ST1. The logic for that transition equation is a simple 7 input AND gate (three inputs represent the ST bits and 4 inputs represent the KEY bits. Some inputs may need inverters to feed the AND for those signals that are zero at the transition time. Then just repeat this four more times for S1 + 2nd KEY input and so forth. – Michael Karas Aug 2 at 0:58
1  
This advice should work fine for any sequence. Why should repetitions matter? Let S0 be the 'reset' state. Let the magic sequence be 2-2-2-2. A '2' entry takes S0 to S1. A second '2' takes state S1 to state S2. Etc. However many digits you want. It's the transitions that match up to key entries, not the states. When you get all the digits, that state sets the output to unlock the lock or whatever. Now the real problem, of course, will be key bounce. – JustJeff Aug 2 at 1:37
@trav1s: You seem to be hung up on this point. The OP has stated that if an incorrect sequence is entered, you must start over. Your fancy sliding-window sequence matcher is completely unnecessary. – Dave Tweed Aug 2 at 3:12
show 3 more comments
up vote 2 down vote

Presenting the SuperShifting©, Flexi-Coded MultiDetector™:

One way we can solve the problem is with a shift register which stores the last 5 input codes. We also have a register which stores the passcode. Then we use digital comparators (logic AND of bitwise XOR) to see if each input code matches the corresponding passcode. If they all match, the output is 1. Otherwise, the output is 0. Here's a full schematic:

enter image description here

Featuring:

  • Changeable passcode
  • Number of digits is easily scalable
  • Bits per digit is easily scalable
  • Avoids the need for a clear key
  • Vulnerable to rainbow table attacks

Because of the vulnerability to rainbow table attacks feature, if you forget your passcode, you can gain it back with increased speed by compressing your key guesses in a rainbow table attack! いいね.

share|improve this answer
It's also vulnerable to a "rainbow string" attack. – Ignacio Vazquez-Abrams Aug 2 at 2:43
Of course, the advantage with this is that one doesn't have to regenerate the state transition table and propagate it into the device, just to change the pass code. And at the cost of one more bit line through the registers, or a small auxiliary counter (not much more than this, however you slice it, left as exercise to the reader) you can make it stop accepting input after the 5th character and thwart the dreaded rainbow string. So +1 – JustJeff Aug 2 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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