Bit stuffing
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 bit
s.
Bit stuffing is used for various purposes, such as for bringing bit streams that do not necessarily have the same or rationally related bit rate
s up to a common rate, or to fill buffers or frame
s. 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 for run length limited
coding: 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
, HDLC, and Universal Serial Bus
.
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.
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" containing six adjacent 1 bits is commonly used as a "Flag byte" or FSS.
To ensure that this pattern never appears in normal data, a 0 bit is stuffed after every five 1 bits in the data. This typically adds 1 stuffed bit to every 32 random payload bits, on average. Note that this stuffed bit is added even if the following data bit is 0, which could not be mistaken for a sync sequence, so that the receiver can unambiguously distinguish stuffed bits from normal bits.
A similar scheme is used in the Universal Serial Bus
, but for a different reason: to ensure sufficient clock edges. Low- and full-speed USB data is sent NRZI encoded: a 0 bit causes a signal transition, while a 1 bit causes no change. The receiver must count the time between transitions to determine the number of 1 bits, and if that time is too long, the receiver can lose count. USB stuffs a 0 bit (causing a transition) after every 6 consecutive 1 bits; this guarantees at least one transition every 7 bit times. (A (0,6) RLL code.)
The main disadvantage of this form of bit-stuffing is that the code rate
is unpredictable; it depends on the data being transmitted.
Source: from Federal Standard 1037C
in support of MIL-STD-188
Data transmission
Data transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
and telecommunication
Telecommunication
Telecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
, bit stuffing (also known—uncommonly—as positive justification) is the insertion of noninformation bits into data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
. Stuffed bits should not be confused with overhead bit
Overhead bit
In data transmission and telecommunication, overhead bits are nondata bits necessary for transmission .Such bits are not counted as part of the goodput....
s.
Bit stuffing is used for various purposes, such as for bringing bit streams that do not necessarily have the same or rationally related bit rate
Bit rate
In telecommunications and computing, bit rate is the number of bits that are conveyed or processed per unit of time....
s up to a common rate, or to fill buffers or frame
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
s. The location of the stuffing bits is communicated to the receiving end of the data link
Data link
In telecommunication a data link is the means of connecting one location to another for the purpose of transmitting and receiving information. It can also refer to a set of electronics assemblies, consisting of a transmitter and a receiver and the interconnecting data telecommunication circuit...
, 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
Multiplexing
The multiplexed signal is transmitted over a communication channel, which may be a physical transmission medium. The multiplexing divides the capacity of the low-level communication channel into several higher-level logical channels, one for each message signal or data stream to be transferred...
or to rate-match two single channels to each other.
Applications include Plesiochronous Digital Hierarchy
Plesiochronous Digital Hierarchy
The Plesiochronous Digital Hierarchy is a technology used in telecommunications networks to transport large quantities of data over digital transport equipment such as fibre optic and microwave radio systems...
and Synchronous Digital Hierarchy.
Another use of bit stuffing is for run length limited
Run Length Limited
Run length limited or RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. This is used in both telecommunication and storage systems which move a medium past a fixed head. Specifically, RLL bounds the length of stretches ...
coding: 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
Controller Area Network
Controller–area network is a vehicle bus standard designed to allow microcontrollers and devices to communicate with each other within a vehicle without a host computer....
, HDLC, and Universal Serial Bus
Universal Serial Bus
USB is an industry standard developed in the mid-1990s that defines the cables, connectors and protocols used in a bus for connection, communication and power supply between computers and electronic devices....
.
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
Error detection and correction
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...
techniques are used to check the frame for corruption after its delivery and, if necessary, the frame will be resent.
Zero-bit insertion
Zero-bit insertion is a particular type of bit stuffing (in the latter sense) used in some data transmission protocols. It was popularized by IBM's SDLC (later renamed HDLC), to ensure that the Frame Sync Sequence (FSS) never appears in a data frame. An FSS is the method of frame synchronization used by HDLC 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" containing six adjacent 1 bits is commonly used as a "Flag byte" or FSS.
To ensure that this pattern never appears in normal data, a 0 bit is stuffed after every five 1 bits in the data. This typically adds 1 stuffed bit to every 32 random payload bits, on average. Note that this stuffed bit is added even if the following data bit is 0, which could not be mistaken for a sync sequence, so that the receiver can unambiguously distinguish stuffed bits from normal bits.
A similar scheme is used in the Universal Serial Bus
Universal Serial Bus
USB is an industry standard developed in the mid-1990s that defines the cables, connectors and protocols used in a bus for connection, communication and power supply between computers and electronic devices....
, but for a different reason: to ensure sufficient clock edges. Low- and full-speed USB data is sent NRZI encoded: a 0 bit causes a signal transition, while a 1 bit causes no change. The receiver must count the time between transitions to determine the number of 1 bits, and if that time is too long, the receiver can lose count. USB stuffs a 0 bit (causing a transition) after every 6 consecutive 1 bits; this guarantees at least one transition every 7 bit times. (A (0,6) RLL code.)
The main disadvantage of this form of bit-stuffing is that the code rate
Code rate
In telecommunication and information theory, the code rate of a forward error correction code is the proportion of the data-stream that is useful...
is unpredictable; it depends on the data being transmitted.
External links
Source: from Federal Standard 1037C
Federal Standard 1037C
Federal Standard 1037C, titled Telecommunications: Glossary of Telecommunication Terms is a United States Federal Standard, issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, as amended....
in support of MIL-STD-188
MIL-STD-188
MIL-STD-188 is a series of U.S. military standards relating to telecommunications.-Purpose:Faced with “past technical deficiencies in telecommunications systems and equipment and software…that were traced to basic inadequacies in the application of telecommunication standards and to the lack of a...