35. Detecting 1101, with overlap

coreStream 1101101: how many overlapping matches?

Two, at bit positions 4 and 7.

coreMoore states needed?

Five, including the detected state.

basicIn a pattern detector for 1101, what does each state actually stand for?

Each state records how much of the pattern has been matched so far: nothing, 1, 11, 110 or the full 1101. The machine can't look back at old bits, so the state is its only memory of the past. More precisely, the state is the longest ending of the bits seen so far that is also a beginning of 1101. That one definition decides every transition.

basicA Moore detector for 1101 has five states. How many flops does it need with binary encoding and with one-hot encoding, and how many binary codes go unused?

Binary needs 3 flops, since 2^2 = 4 is too few and 2^3 = 8 is enough. One-hot needs one flop per state, so 5. With 3 binary bits there are 8 codes and only 5 are used, which leaves 3 unused codes that the default branch should send back to S0.

coreThe machine is in S11 (it has just seen 11) and another 1 arrives. Which state should it go to, and why do many people get this wrong?

It should stay in S11. After 111, the last two bits are still 11, and that is the longest ending that also begins the pattern. A common mistake is to go back to S1, which throws away one of the two 1s. The stream 11101 exposes it: the correct machine fires at the end, and the broken one doesn't.

coreThis detector passes a test on the stream 1101101 but fails in the field. Find the bug and a short stream that shows it.

always @(posedge clk)
  if (rst) state <= S0;
  else case (state)
    S0:    state <= din ? S1    : S0;
    S1:    state <= din ? S11   : S0;
    S11:   state <= din ? S1    : S110;
    S110:  state <= din ? S1101 : S0;
    S1101: state <= din ? S11   : S0;
    default: state <= S0;
  endcase
assign detect = (state == S1101);

The S11 line sends a further 1 back to S1, but after 111 the last two bits are still 11, so it should stay in S11. A stream such as 11101 shows it: the correct machine detects once at the end, and this one never does, because it falls to S1 and then the 0 sends it to S0. The stream 1101101 never sends a third 1 into S11, so it can't reveal the bug. Simulated, this version finds 2 matches on 1101101 like the correct one, but 0 on 11101.

coreHow would you build the same 1101 detector as a Mealy machine, and how does its output timing differ from the Moore version?

assign detect = (state == S110) & din;

The Mealy version needs only four states, S0, S1, S11 and S110, because the final 1 is seen on the arrow out of S110 rather than in a state of its own. The output is detect = (state == S110) & din. It fires in the same cycle as the last bit, one clock earlier than the Moore version. The cost is that the output now depends combinationally on the input, so it can glitch and carries input timing into the next block unless it is registered.

coreAn overlapping 1101 detector sees the stream 1101101101, first bit first. How many times does it fire, and at which bit positions do the matches end?

Three times, with matches ending at bits 4, 7 and 10. After each match, the final 1 is reused as the first 1 of the next attempt, because from S1101 a 1 goes to S11. So each later match needs only three new bits, 101. Simulated, the overlapping detector gives 3 on this stream.

advancedHow would you convince yourself that your 1101 detector is correct on every possible input, not just the streams you thought of?

Write a second, independent model and compare them every cycle on long random streams. A simple reference is a 4-bit shift register compared against 1101, which is a completely different design. Then add directed streams that hit each arrow, such as 11101 for the S11 self-loop and 1101101 for the overlap arrow. Random testing finds what you didn't imagine, while the directed cases make sure each transition is exercised.

advancedFor an overlapping detector of 1011 (not 1101), where should the full-match state go on a 1 and on a 0?

Use the same question: what is the longest ending that is also a beginning of 1011? After 1011 then 1, the bits end in ...10111. Its endings 11, 111 and 0111 are not beginnings, but 1 is, so go to S1. After 1011 then 0, the bits end in ...10110, and the ending 10 is a beginning, so go to S10. That is why 1011011 contains two overlapping matches, which a simulation of this machine confirms.