← ProblemsCircuits / Sequential Logic / Finite State Machines
HDLC frame synchronization
5%fsmserial-protocolsHDLC-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 — assertdisc(discard) for one cycle. - Exactly six 1s followed by a 0 (
...01111110): a frame flag — assertflagfor one cycle. - Seven or more consecutive 1s: an error — assert
errcontinuously, starting the cycle after the 7th consecutive 1 and remaining high until the cycle afterinreturns 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).