← ProblemsCircuits / Sequential Logic / Finite State Machines

HDLC frame synchronization

5%fsmserial-protocols

HDLC-style framing sends data as a bitstream in which runs of consecutive 1s carry special meaning. Build a Moore FSM that watches the serial input in (one bit per cycle) and counts consecutive 1s:

  • Exactly five 1s followed by a 0 (...0111110): the 0 is a stuffed bit — assert disc (discard) for one cycle.
  • Exactly six 1s followed by a 0 (...01111110): a frame flag — assert flag for one cycle.
  • Seven or more consecutive 1s: an error — assert err continuously, starting the cycle after the 7th consecutive 1 and remaining high until the cycle after in returns to 0. The 0 that ends an error run produces no disc or flag.
  • A 0 after zero to four 1s: nothing is asserted.

Because the machine is Moore (outputs are functions of registered state), each disc/flag pulse appears in the cycle after the closing 0 arrives.

The 0 that closes a disc or flag pattern also serves as the leading 0 of the next run: a 1 in the very next cycle starts a new count of consecutive 1s. After the synchronous, active-high reset, the machine behaves as if a 0 had just been seen (all outputs 0, ready to count 1s).