Library

FST · Rational transduction

HDLC bit stuffing

A frame is marked by 01111110, so the data inside must never contain six 1s in a row. After every five consecutive 1s the sender inserts a 0, and the receiver removes it. The transducer counts the run of 1s and, at five, writes 10 instead of 1.

r0r1r2r3r40/01/10/01/10/01/10/01/10/0, 1/10
The machine as drawn — 5 states, 10 transitions.

The author’s examples, run

0 → reject · 01 → reject · 100 → reject · 0001 → reject · 01000 → reject · 0001111101000011001 → reject · 11111001000011001