1. Home
2. Academy
3. State Machines from Zero
4. Volume 06

6.1 Overlapping vs non-overlapping

A sequence detector watches a stream of bits, one per clock cycle, and says "found it" whenever the latest bits match a pattern. Overlapping detection lets the end of one match be the start of the next.

The job

Data often arrives one bit at a time, one bit per clock cycle, on a single wire. Such a series of bits is a bit stream. Serial links, radio receivers and disk drives all produce them. Very often a circuit must spot a special pattern in the stream - a start marker, a password, a sync word. The circuit that does this is a sequence detector.

Throughout this volume, the input is x (one bit per cycle) and the output is z (1 when the pattern has just been seen).

Two ways to count a match

Take the pattern 101 and this stream, one bit per cycle:

The bits in cycles 0, 1 and 2 are 1 0 1 - a match. Now look at cycles 2, 3 and 4: also 1 0 1. The 1 in cycle 2 is both the end of the first match and the start of the second. Should it count twice?

• In overlapping detection, yes. Matches end in cycles 2, 4 and 7.
• In non-overlapping detection, no. After a match, the machine starts again from nothing. Matches end in cycles 2 and 7 only.

These are Mealy outputs: z rises in the same cycle as the last bit of the match, as in Volume 02.

6.2 Detecting 101 and 1011 (Mealy and Moore)

Name each state after the longest start of the pattern that the stream ends with. Then every arrow can be worked out by one simple rule.

The method

Detectors are easy to get wrong by guessing. This method never guesses.

A prefix of a pattern is its first few bits. The prefixes of 101 are 1, 10 and 101. Now:

1. Make one state per prefix. Include the empty prefix - "nothing matched yet". For 101: S0 (nothing), S1 (seen "1"), S10 (seen "10").
2. For each state and each input bit, add the bit to the end of that state's prefix.
3. If the result is the whole pattern, the output is 1.
4. Find the next state: the longest prefix of the pattern that the result ends with. For overlapping detection, this rule applies even after a full match.

The last step is the heart of it. It asks: "of what I have seen, how much could still be the start of a new match?"

The 101 detector, Mealy, overlapping

Work through every state and input:

Look at the row S1 with input 1. The bits are "11". That is not a prefix, but it ends with "1", which is. So the machine stays in S1: the new 1 could start a match. And the last row: after 101, the final 1 could start the next match - so the machine goes to S1, not S0. That single arrow is what makes the detector overlapping.

For non-overlapping detection, only one arrow changes: after a match, go back to S0 instead of S1. So the arrow S10 --1/1--> goes to S0.

The 101 detector, Moore

A Moore machine needs a state for "the whole pattern has just been seen", in which z = 1. Add S101. Its arrows follow the same rule. From 101, a 0 gives "1010", which ends with the prefix "10", so the machine goes to S10. A 1 gives "1011", which ends with the prefix "1", so it goes to S1.

Figure 6.4 runs both 101 detectors on the stream from sub-module 6.1, plus one more bit. As always, the Moore output comes one cycle after the Mealy output.

The 1011 detector

The same method, with one more prefix. The states are S0, S1, S10 and S101, and a Moore machine adds S1011:

Here is the Moore 1011 detector in Verilog. Each row of the table becomes one line of the case statement:

module seq1011_moore (
  input  wire clk, rst, x,
  output wire z
);
  localparam [2:0] S0 = 3'd0, S1 = 3'd1, S10 = 3'd2, S101 = 3'd3, S1011 = 3'd4;
  reg [2:0] state, next_state;

  always @(posedge clk)
    if (rst) state <= S0;
    else     state <= next_state;

  always @(*) begin
    case (state)
      S0:      next_state = x ? S1    : S0;
      S1:      next_state = x ? S1    : S10;
      S10:     next_state = x ? S101  : S0;
      S101:    next_state = x ? S1011 : S10;
      S1011:   next_state = x ? S1    : S10;
      default: next_state = S0;          // unused codes 5, 6, 7: start again
    endcase
  end

  assign z = (state == S1011);           // Moore output
endmodule

6.3 Longer and multiple patterns

The same method handles long patterns and several patterns at once. For long fixed patterns, a shift register and a comparator can do the job with no state diagram at all.

A longer pattern: 1101

Longer patterns need no new ideas - only more rows. For 1101, the prefixes give the states S0, S1, S11 and S110:

Notice the row S1 with x = 0. For the pattern 101, "10" was a prefix. For 1101 it is not - the second bit of 1101 is a 1. The method takes care of this for you: the rows depend on the pattern, so you must work each one out, never copy them from another detector.

Several patterns at once

Suppose the machine must say z = 1 when it sees either 101 or 110. Make one state for every prefix of either pattern: S0, S1, S10 (from 101) and S11 (from 110). Then use the same rule - the longest ending that is a prefix of any pattern:

Four states detect both patterns, overlapping each other freely. If the two patterns need separate outputs - z1 for 101 and z2 for 110 - the states stay the same; only the output logic splits.

The engineer's shortcut: a shift register

For a fixed pattern of n bits, there is a second way. Keep the last n bits in a shift register - a row of flip-flops that moves each bit along one place per cycle - and compare them with the pattern:

reg [3:0] last4;                                   // the last four bits
always @(posedge clk)
  if (rst) last4 <= 4'b0000;
  else     last4 <= {last4[2:0], x};               // shift the new bit in
assign z = (last4 == 4'b1011);                     // Moore timing

It is short, obviously right, and handles overlapping by itself. The cost is flip-flops: n of them, against about log₂(n + 1) for the state machine. For a 32-bit sync word, that is 32 flip-flops against 6.

6.4 Divisibility checkers on a bit stream

A state machine can tell whether the binary number arriving on a bit stream is divisible by k, using only k states - one for each possible remainder.

The question

The bits arrive most significant first, and together they form a binary number. After every bit, the machine must say whether the number so far is divisible by 3. The number can grow without limit, so the machine cannot store it. Can a small machine still answer?

The trick: keep only the remainder

Reading a new bit b multiplies the number so far by 2 and adds b. Write the number as N. Then:

• the new number is 2N + b
• so the new remainder is (2 × old remainder + b) mod 3

The remainder is all the machine needs to remember - and a remainder after dividing by 3 is only ever 0, 1 or 2. So three states are enough: R0, R1 and R2.

Try it on the stream 1, 1, 0 - the number 110 in binary, which is 6:

1. Start in R0. The number so far is 0, and 0 is divisible by 3.
2. Read 1: the number is 1, remainder 1. Go to R1.
3. Read 1: the number is 11 in binary, 3, remainder 0. Go to R0 - divisible.
4. Read 0: the number is 110 in binary, 6, remainder 0. Stay in R0 - divisible, as expected.

The same idea works for any k: k states, and the arrow from state r on bit b goes to state (2r + b) mod k. It is one of the most popular state machine questions in written exams.

6.5 Testing a detector thoroughly

Test a detector by feeding it thousands of bits and comparing its output, every cycle, with a simple reference model that is obviously correct.

Why hand-picked tests are not enough

A detector has many paths. The bugs hide in the rare ones: a near-miss such as 1010, a pattern straight after a match, a long run of 1s. You could write a test for each one by hand - a directed test - but you will always miss some.

A better plan uses two ideas together:

• A reference model: a second version of the detector that is so simple it is obviously right. For a fixed pattern, the shift register from sub-module 6.3 is perfect.
• Random stimulus: thousands of random bits, which will hit the rare paths again and again.

Every cycle, the testbench compares the design's output with the model's. Any difference is a bug.

module seq1011_tb;
  reg  clk = 0, rst = 1, x = 0;
  wire z;
  reg  [3:0] hist;                          // reference model: the last four bits
  integer i, errors = 0, matches = 0;

  seq1011_moore dut (.clk(clk), .rst(rst), .x(x), .z(z));

  always #5 clk = ~clk;

  always @(posedge clk)                     // the obviously-correct model
    if (rst) hist <= 4'b0000;
    else     hist <= {hist[2:0], x};

  initial begin
    repeat (2) @(negedge clk); rst = 0;
    for (i = 0; i < 5000; i = i + 1) begin
      @(negedge clk);                       // mid-cycle: check, then drive
      if (z !== (hist == 4'b1011)) begin
        errors = errors + 1;
        $display("MISMATCH in cycle %0d: z = %b", i, z);
      end
      if (z) matches = matches + 1;
      x = $random;                          // a random bit for the next cycle
    end
    $display("%0d matches seen", matches);
    if (errors == 0) $display("PASS"); else $display("FAIL: %0d mismatches", errors);
    $finish;
  end
endmodule

Four details make this testbench trustworthy:

1. Same timing. The model samples x on the same rising edge as the design, so both have seen exactly the same bits when they are compared.
2. Compare with !==. The !== comparison also catches an unknown x value on z, which a plain != would not.
3. Count the matches. A test that never saw a match proves nothing. Random bits contain 1011 about once every 16 cycles, so 5000 cycles give roughly 300 matches.
4. Report one verdict. PASS or FAIL, so nobody has to read a log.

Directed tests still matter

Random bits find most bugs, but a few hand-written streams make a good first test, and they are easy to read when something fails:

What you learned

• Overlapping detection reuses the end of one match as the start of the next; the specification must say which rule applies.
• Name each state after the longest prefix of the pattern that the stream ends with, and every arrow follows from one rule.
• A Mealy detector for an n-bit pattern needs n states; a Moore detector needs n + 1.
• Several patterns share one machine: one state per prefix of any of them.
• A shift register and comparator detect a fixed pattern with no state diagram, at the cost of n flip-flops.
• A divisible-by-k checker needs only k states: it remembers the remainder, using (2r + b) mod k.
• Test detectors against a simple reference model with thousands of random bits, and count the matches you saw.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Bit stream
• Sequence detector
• Overlapping detection
• Prefix
• Shift register
• Modulo (mod)
• Directed test
• Reference model
• Random stimulus

Practice

Interview corner

Next, Volume 07 shows that counters, timers and debouncers - circuits you may not think of as state machines - are state machines too.