Bit stuffing, occasionally referred to as positive justification, is the process of adding in extra, non-data information into a string of computer data, typically to ensure that the data is read properly when the computer receives it. Computer data is made of bits of information in the form of 1's and 0's. To signal the beginning and the end of a data chunk, a code is used. When actual information being transmitted might be confused for this code and ignored, extra bits, such as 0's, are inserted — stuffed — into the code so the computer knows what data to process.
Also known as bit padding, bit stuffing helps prevent errors when a computer receives information. The bits do not represent any actual information and once all the data is transmitted, the computer deletes or ignores the unnecessary bits. If, for example, the signal for the beginning of a line of code was five 1's in a row and the actual data being sent started with five 1's, the computer would think this was the start signal and delete it. To prevent this, a zero bit would be inserted in between the fourth and fifth 1's so it would read as "111101" instead of "11111." The computer would then delete the zero and read the data as five ones instead of deleting it.
Another use for bit stuffing is to fill out a string of data that requires a certain number of bits to transmit properly. A string of information might need to be at least 10 bits long but have only nine present. In this situation, an extra bit would be added to bring the total to 10. The extra bit will be discarded when the data is interpreted.
Aside from helping the computer interpret chunks of data properly, bit stuffing is also used to help computer synchronization. A computer sends and receives information in a steady rhythm based on its internal clock. If too many of the same bits — a line of all 0's for example — are sent at once, the computer clock may get out of sync and execute the commands in the wrong order. Inserting a 1 into the line of 0's forces the computer clock to re-sync itself and prevents this problem.
Similar to helping a computer stay in sync, bit stuffing also helps the computer read data correctly when the information is sent in bits instead of as a continuous stream. To trick the computer into seeing the transmission as continuous, random bits are generated and sent to the computer while it waits for the next actual chunk of information to be transmitted. This keeps the transmission pattern at a consistent pace.
The computer knows to remove non-data bits from data streams once they are received. Computer programmers need to know which bits to stuff so the computer will remove them instead of reading them as actual data. If the computer tried to interpret these stuffed bits instead of discarding them, it would cause computer errors in the program.
