Error-Correcting Codes
In certain applications such as transmissions from spacecraft visiting distant planets, it is not sufficient to merely have codes that detect transmission errors when they arise; correction is required. Another example of a need for error-correcting codes is in live streaming video, where the frames are transmitted in sequence and displayed immediately. If a particular frame is distorted during transmission, then it must either be fixed by the receiver right then or else must be discarded completely (which however would result in image flicker or jitter for the viewer). Asking the source to resend a frame is not an option.
Therefore, in such cases as the above, given restrictions of distance, limited bandwidth or time, and other problems, it is extremely difficult to ask for a re-transmission of the data even if an error is detected. Therefore, a better protocol is needed where any errors that arise are fixed and the original data is restored, provided the magnitude of the error is within some specified limit.
Almost all electronic data exchange is in binary format at the basic level, and errors in transmission are of the form where some of the 0s are changed to 1s, or vice versa. These are called "bit errors," and error-correction is often of the form of detecting and fixing such bit errors when they arise. Such correction may be done in software or by special-purpose hardware. For time-critical applications such as streaming video, special-purpose hardware is generally used because software tends to be far too slow.
Bit errors are more frequent than we may think—if we are used to considering electronic devices as flawless machines. Some types of technology are more prone to bit errors than other--for instance, optical disks (CD-ROMs and others) have a higher bit error rate than magnetic disks (hard drives and so on). Fiber optic cables have a lower bit error rate than RS-232 coaxial cables. Still, even the best possible storage or communication technology will have some non-zero error rate, no matter how small. Without error correction, no storage or data transfer technology now in use could be applied.
Bit errors may be measured either in terms of number of errors per unit of time, or else in terms of number of errors per billion bits transferred. As there is a serious effort underway to increase the number of bits held in a storage device, and also the number of bits transferred per unit time over communication media, we may expect that the number of raw errors will rise, given constant error rates. Even with incremental improvements in technology that cause bit error rates by these measures to drop, it is seen that the number of bit errors increases continually.
Error correction is used, as indicated above, to make possible the development and use of high capacity storage devices and communication media. Reliable hard drives that can store 20 GB or more of data are possible in large part owing to error correction that makes them sufficiently reliable. DRAM memory modules as well as other artifacts and devices can be made cheaper and more reliable using error correction that allows for cheaper components to be used. Error correction is useful in the creation of fault tolerance, such as in aircraft controls, because the information flow may be able to tolerate errors caused by the failures of specific components.
Error correction is typically achieved by dividing strings of bits to form blocks, which are then coded to form a longer block that is robust to the loss or change of a certain number of bits. Each block is encoded and decoded independently of the others, hence a limit is set on the maximum loss that can occur even if too many bits are flipped for the error correction to work properly. The two kinds of error correcting codes in common use here are convolutional or tree codes, or block codes. Convolutional codes use smaller blocks of data, and the coding of one block of data is done in a fashion that depends upon the state of the encoder as well as the data that is to be encoded. Block codes generally use longer blocks, and each block is coded in a similar fashion.
Claude Shannon's development of information theory in the late 1940s was the basis for the development of error-correcting codes. Shannon's mathematical work showed that the best way to get maximum storage out of a device, or the higher possible transfer rate on a communication channel, is by the use of error correction. Shortly thereafter, Richard Hamming developed the first error correcting code that was able to tolerate the loss or distortion of one bit. Codes similar to his are thus called Hamming codes. In 1968, Elwyn Berlekamp and James Massey discovered an algorithm (since known as the Berlekamp-Massey algorithm for solving the key decoding equation) needed to build decoders for multiple error correcting codes. The Berlekamp-Massey algorithm is a variation of an old method for finding the greatest common divisor, which was discovered around 300 BC by the ancient mathematician Euclid. Numerous variations of the Berlekamp-Massey/Euclid-GCD algorithm exist and are used to solve the key decoding equation.
This is the complete article, containing 854 words
(approx. 3 pages at 300 words per page).
