Bit stuffing

From Wikipedia, the free encyclopedia

In data transmission and telecommunication, bit stuffing (also known -- uncommonly -- as positive justification) is the insertion of noninformation bits into data. Stuffed bits should not be confused with overhead bits.

Bit stuffing is used for various purposes, such as for bringing bit streams that do not necessarily have the same or rationally related bit rates up to a common rate, or to fill buffers or frames. The location of the stuffing bits is communicated to the receiving end of the data link, where these extra bits are removed to return the bit streams to their original bit rates or form. Bit stuffing may be used to synchronize several channels before multiplexing or to rate-match two single channels to each other.

Applications include Plesiochronous Digital Hierarchy and Synchronous Digital Hierarchy.

Another use of bit stuffing is to limit the number of consecutive bits of the same value in the data to be transmitted. A bit of the opposite value is inserted after the maximum allowed number of consecutive bits. Since this is a general rule the receiver doesn't need extra information about the location of the stuffing bits in order to do the destuffing.

This is done to create additional signal transitions to ensure reliable transmission or to escape special reserved code words such as frame sync sequences when the data happens to contain them.

Applications include Controller Area Network.

Bit stuffing does not ensure that the payload is intact (i.e. not corrupted by transmission errors); it is merely a way of attempting to ensure that the transmission starts and ends at the correct places. Error detection and correction techniques are used to check the frame for corruption after its delivery and, if necessary, the frame will be resent.

[edit] Zero-bit insertion

Zero-bit insertion is a particular type of bit stuffing (in the latter sense) used in some data transmission protocols, such as HDLC, to ensure that the Frame Sync Sequence (FSS) doesn't incidentally appear in a data frame. An FSS is used to indicate the beginning and/or end of a frame.

The name relates to the insertion of only 0 bits. No 1 bits are inserted to limit sequences of 0 bits.

The bit sequence "01111110" is commonly used as an FSS. Therefore it is necessary to prevent a sequence of six consecutive 1s from occurring in the frame data as they may be confused for the FSS. Zero-bit insertion is used to prevent such a sequence from occurring - if a series of five 1s is found by the sender a 0 is inserted after the fifth 1, thereby limiting the maximum possible run of 1s to five. At the receiver, if a series of five 1s is received, the subsequent 0 is removed to recover the original data. Five ones is used as it results in the least number of insertions and so reduces redundancy.

When the receiver finds "0111111" two possible outcomes may occur. To determine which, the next bit is checked - if it is a 0 (i.e. "01111110") a valid FSS is assumed to have been received, but if it is a 1 (i.e. "01111111") then some corruption must have occurred during transmission as that data sequence cannot have been transmitted (a 0 would have been inserted after the fifth 1). Should corruption during transmission result in the FSS being received as part of the data, that will not be corrected and the frame will be truncated.