The idea: remember how much of the pattern you have seen

A sequence detector reads one bit per clock cycle and outputs 1 when the last bits are a given pattern, here 1011. It cannot store the whole stream. It only needs to know how much of 1011 the latest bits already match. That is its state:

  • S0: nothing useful seen yet;
  • S1: the last bit was 1;
  • S2: the last bits were 10;
  • S3: the last bits were 101;
  • and, in a Moore machine only, S4: the last bits were 1011, a match.
The stream 1 0 1 1 0 1 1 0 in eight cycles. Under each bit the Mealy state before it: S0, S1, S2, S3, S1, S2, S3, S1. The Mealy output z is 1 under cycle 3 and cycle 6. The two matches 1011 overlap: the 1 in cycle 3 is the end of the first and the start of the second.
On 10110110 the detector finds two matches that share a 1; the state under each bit says how much of 1011 is already there.

On the canvas, press Design Step six times to build the detector, then Clock Edge to feed the stream one bit per cycle. The general parts of a state machine (state register, next-state logic, output logic, encodings) are explained on Finite State Machines; this page is one complete worked design.

Stage 1: the forward path

Start in S0 and follow the pattern. Each correct bit moves one state forward: S0 –1→ S1 –0→ S2 –1→ S3 –1→ match. In a Mealy machine the last arrow carries the output, written x / z = 1/1. In a Moore machine the output belongs to a state, so the match needs a state of its own, S4, with Z = 1 inside it (Demo: build the Mealy 1011 detector, Demo: build the Moore 1011 detector).

Stage 2: where a wrong bit goes

Every state needs an arrow for both input values. A wrong bit does not always send the detector back to S0. Write down what was seen plus the new bit, and keep its longest end that is still a start of 1011:

statewrong bitseenlongest end that starts 1011go to
S000noneS0
S11111S1
S20100noneS0
S30101010S2

The S3 row is the one people get wrong. After 101 a 0 gives 1010, and its end 10 is the start of a new 1011. Going back to S0 would miss the match in 1010110 (Demo: a wrong bit keeps 10: z = 1 in cycle 5). The S2 row really does start over: in 10010110 the 100 leaves nothing, and the match comes in cycle 6 (Demo: 100 starts over). This rule is the same failure function that the Knuth-Morris-Pratt string search builds.

Overlapping or not

After a match, the last 1 of 1011 could also be the first 1 of the next one. An overlapping detector counts it: Mealy S3 –1/1→ S1, and Moore S4 goes to S1 on 1 and to S2 on 0 (10110 ends with 10). A non-overlapping detector throws the match away and starts over: Mealy S3 –1/1→ S0, Moore S4 behaves like S0. On 10110110 the overlapping detector finds 2 matches, the non-overlapping one finds 1 (Demo: Mealy vs Moore on 10110110 and Demo: overlapping vs non-overlapping). Which one is right depends on the job: counting every occurrence, or finding separate packets.

Mealy or Moore

Two state diagrams of the overlapping 1011 detector. Top, Mealy: four states S0 to S3 in a row with forward arrows 1/0, 0/0, 1/0, a self loop 0/0 on S0 and 1/0 on S1, S2 back to S0 on 0/0, S3 back to S2 on 0/0, and S3 to S1 on 1/1 in red. Bottom, Moore: five states S0/0 to S4/1 with the same forward path, loops on S0 and S1, S2 to S0 on 0, S3 to S2 on 0, S4 to S2 on 0 and S4 to S1 on 1.
The Mealy detector puts the 1 on an arrow and needs 4 states; the Moore detector needs a fifth state to hold Z = 1.
MealyMoore
output depends onstate and input xstate only
states for 101145
D flip-flops23
output equationz = Q1·Q0·xZ = Q2
output is 1in the cycle of the last 1in the next cycle

From diagram to circuit

  1. State table. One row per state, the next state (and Mealy output) for x = 0 and x = 1. It says exactly what the arrows say.
  2. State assignment. N states need ⌈log₂ N⌉ flip-flops: 4 states fit in 2 (S0..S3 = 00, 01, 10, 11), 5 need 3 (S0..S4 = 000 … 100). The Moore codes 101, 110 and 111 never occur, so they are don't cares.
  3. Equations. With D flip-flops, D is just the next value of its bit, so each D input is 1 in the table cells where that bit of the next state is 1. Group them on a Karnaugh map.
  4. Circuit. The equations become the next-state logic in front of the D inputs; the Q outputs feed back; one clock loads all flip-flops at once.
machineD inputsoutput
Mealy, overlappingD1 = Q0·x' + Q1·Q0'·x, D0 = xz = Q1·Q0·x
Mealy, non-overlappingD1 = Q0·x' + Q1·Q0'·x, D0 = Q1'·x + Q0'·xz = Q1·Q0·x
Moore, overlappingD2 = Q1·Q0·x, D1 = Q0·x' + Q2·x' + Q1·Q0'·x, D0 = Q1'·x + Q0'·xZ = Q2
Moore, non-overlappingD2 = Q1·Q0·x, D1 = Q0·x' + Q1·Q0'·x, D0 = Q1'·x + Q0'·xZ = Q2

Take D0 of the overlapping Mealy detector. Every arrow on a 1 goes to S1 or S3, the odd codes, and every arrow on a 0 goes to S0 or S2. So the next Q0 is just x: D0 = x. For JK or T flip-flops you would go through excitation tables instead, as on Flip-Flop and Counter Design.

Output timing: the same stream into both

The timing diagram on the canvas feeds the same bits into a Mealy and a Moore detector. In each cycle the Mealy z is computed from the state and the bit that is arriving, so it goes to 1 in the cycle of the last 1 of 1011. The Moore Z is read from the flip-flops, so it goes to 1 only after the clock edge has loaded S4, one cycle later, and then stays 1 for that whole cycle.

A timing diagram over cycles 0 to 7 with the clock, the input x = 1 0 1 1 0 1 1 0, the Mealy output z high in cycles 3 and 6, and the Moore output Z high in cycles 4 and 7.
Same stream, same matches: Mealy z = 1 in cycles 3 and 6, Moore Z = 1 in cycles 4 and 7.

On 10110110 the overlapping detectors give Mealy z = 1 in cycles 3 and 6 and Moore Z = 1 in cycles 4 and 7. The Mealy answer is earlier, but it is a combinational path from the input to the output: a glitch on x is a glitch on z. The Moore answer is clean for a whole cycle. In the Demo: Moore circuit on 110110, Q2 Q1 Q0 = 100 during cycle 5, so Z = Q2 = 1. Building the flip-flops themselves from gates is on Sequential Logic.

What the page leaves out

  • Other patterns and lengths. The method is the same for any pattern: one state per prefix, the longest-end rule for wrong bits.
  • Unused Moore codes. The page never enters 101, 110 or 111. A real design checks where the equations send them after power-up, or uses a reset.
  • Gate drawings and minimisation. The logic is drawn as two boxes with the equations; the K-map grouping is on its own page.
  • Other encodings such as one-hot or Gray, and other flip-flop types.
  • Delays. No gate or clock-to-Q delay, so no glitches appear and the input is one clean bit per cycle; a real asynchronous input needs a synchronizer.

On the mind map

Open the Computer Architecture mind mapComputerArchitectureAbstraction and numbers: layers and bit patternsAbstraction and numbersCombinational logic: output depends only on inputsCombinational logicSequential logic: state held by a clockSequential logicMIPS software: how C becomes machine wordsMIPS softwareThe processor: datapath plus controlThe processorPipelines and parallelism: more instructions at oncePipelines and parallelismMemory and I/O: small fast near, big slow farMemory and I/OLatches and flip-flopsLatches and flip-flopslatch is level, flip-flop is edgeFlip-flops and counter designFlip-flops and counter designexcitation = characteristic backwardsLatch from transistorsLatch from transistorstransmission gates plus inverter loopTiming analysisTiming analysissetup limits clock, hold limits short pathsFinite state machinesFinite state machinesMoore: output from state; Mealy: +inputs1011 Sequence DetectorA wrong bit keeps the longest prefixShift registers and countersShift registers and countersChained flip-flops shift or count each clockOpen the Computer Architecture mind mapComputer Architecturestate held by a clockSequential logicLatches and flip-flopsLatches and flip-flopslatch is level, flip-flop is edgeFlip-flops and counter designFlip-flops and counter designexcitation = characteristic backwardsLatch from transistorsLatch from transistorstransmission gates plus inverter loopTiming analysisTiming analysissetup limits clock, hold limits short pathsFinite state machinesFinite state machinesMoore: output from state; Mealy: +inputs1011 Sequence DetectorA wrong bit keeps the longest prefixShift registers and countersShift registers and countersChained flip-flops shift or count each clock
This page on the Computer Architecture mind map · 46 pages in 7 branches · open it to see the whole map and test yourself in recall mode.