Error correction

Transmitting data involves the sending of bits (ones and zeros) as signaled by some alternation in physical charac-teristics (such as voltage or frequency). There are a number of ways in which errors can be introduced into the data stream. For example, electrical “noise” in the line might be interpreted as spurious bits, or a bit might be “flipped” from one to zero or vice versa. Generally speaking, the faster the rates at which bits are being sent, the more sensitive the transmission is to effects that can cause errors.

While a few wrong characters might be tolerated in some text messages or graphics files, binary files represent-ing executable programs must generally be received per-fectly, since random changes can make programs fail or produce incorrect results. Data communications engineers have devised a number of methods for checking the accu-racy of data transmissions.

The simplest scheme is called parity. A single bit is added to each eight-bit byte of data. In even parity, the extra (parity) bit is set to one when the number of ones in the byte is odd. In odd parity, a one is added if the data byte has an even number of ones. This means that the receiver of the data can expect it to be even or odd respectively. When the byte arrives at its destination, the receiving program checks the parity bit and then counts the number of ones in the rest of the byte. If, for example, the parity is even but the data as received has an odd number of ones, then at least one of the bits must have been changed in error. Parity is a fast, easy way to check for errors, but it has some unreliability. For example, if there were two errors in transmission such that a one became a zero and a different zero became a one, the parity would be unchanged and the error would not be detected.

The checksum method offers greater reliability. The binary value of each block of data is added and the sum is sent along with the block. At the destination, the bits in the block are again added to see if they still match the sum. A variation, the cyclical redundancy check or CRC, breaks the data into blocks and divides them by a fixed number. The remainder for the division for each block is appended to the block and the calculation is repeated and checked at the destination. Today most modem control software imple-ments parity or CRC checking.

A more sophisticated method called the Hamming Code offers not only high reliability but also the ability to auto-matically correct errors. In this scheme the data and check bits are encrypted together to create a code word. If the word received is not a valid code word, the receiver can use a series of parity checks to find the original error. Increasing the ratio of redundant check bits to message bits improves the reliability of the code, but at the expense of having to do more processing to encrypt that data and requiring more time to transmit it.