字序比對設計法Sequence Recognizer

Example:  Sequence Recognizer

How to Design States

ãCircuit has input, X, and output, Z

ãRecognizes sequence 1101 on X

lSpecifically, if X has been 110 and next bit is 1, make Z high

ãStates remember past history

lClearly must remember we’ve seen 110 when next 1 comes along

ã

lTell me one necessary state for this example…?

1)Beginning State

ãStart state:  let’s call it A

lif 1 appears on input, move to next state B  output remains at 0 

ã

New state, C

ãTo reach C, must have seen 11

ã

If 110 has been received, go to D

ãNext 1 will generate a 1 on output Z

ã

What happens to arrow on right?

ãMust go to some state.

ãWhere?

ã

Here we have to interpret the problem statement

ãWe’ve just seen 01

lIs this beginning of new 1101?

lOr do we need to start over w/ another 1?

ãTextbook:  decides that it’s beginning (01…)

ã



Well, must have every possibility out of every state

ãIn this case, just two: X = 0 or 1

ãYou fill in other cases