Bit stuffing

From Computer History Wiki
Jump to: navigation, search

Bit stuffing is a simplistic predecessor to run-length limited coding, used in both mass storage and data communication sub-systems. Its purpose is to obscure reserved patterns (such as a sync character) which occur in the user's data, and prevent them from interfering with the proper operation of the sub-system. Instances of that pattern in the user's data are concealed by inserting an extra bit in the patter, which thus hides the reserved pattern; the inserted bit is later removed before the data is used.

For instance, in SDLC serial line protocol, the start and end of a packet are marked by a specific bit pattern, '01111110', the 'flag'. To prevent instances of that pattern in the user's data from interfering with the correct operation of the protocol, '11111' is replaced, during transmission, by '111110'; the inserted '0' is removed on reception.