While digital computers can process data very quickly, it is generally recognized that the utility of the result is no better than the reliability of the data. That is, if the data that is processed by the computer is corrupted before or during processing, the resulting processed data will generally reflect the corruption. Accordingly, several arrangements have been developed to facilitate the detection and correction of errors which may develop in the data.
One relatively simple arrangement is to use one extra "parity" bit added to the binary representation of each data word. The value of the parity bit is a function of the condition of the other bits of the data word, and may reflect, for example, the number of bits in the binary representation whose value is "one." That is, if an even number of bits in the binary representation have the value "one," the parity bit may also have the value "one," but if an odd number of bits have the value "one," the parity bit will have the value "zero." If, when the computer is to later use the augmented data word (that is, the original data word with the parity bit appended), it determines that the number of bits having the value "one" differs from the number indicated by the parity bit, it can conclude that an error has occurred in the augmented data word. It will be appreciated that, since the value of the parity bit is to reflect whether the number of "ones" in the original data word is even or odd, a change of any one bit in the augmented data word, including the parity bit, from a "one" to a "zero," or from a "zero" to a "one," will trigger an error indication. It will be further appreciated that use of such a parity bit will not protect against a two-bit error, since the even-ness or odd-ness of the number of "ones" will be the same.
In addition, the use of a parity bit will not help identify the location of an error if one is detected. Accordingly, while use of a parity bit will help in error detection, it will not help in error correction. To assist in error correction, error correction coding techniques have been developed to provide additional error correction bits which can indicate the presence of, and facilitate the location of, errors in a data word. Generally, for each data word to be protected, a multiple-bit error correction code is generated and added to the data word to form the augmented data word. The particular number of errors which may be detected and corrected will depend on particular encoding techniques which are used. Generally, for a data word of a given size, the more errors which may be detected and corrected in the data word, the more bits are required in the associated code word. When the computer is to later use the data word, it and the associated error correction code are processed to determine if any errors developed prior to processing. If so, a "syndrome" is generated which identifies the particular erroneous bit of the data word.
Both parity and error correction code techniques are often used in the same computer. For example, error correction coding may be used in data storage, since greater confidence in data integrity may be required, the additional bit storage is relatively inexpensive, and the likelihood of an error is relatively high. On the other hand, parity may be used in buses used to transmit data between the storage subsystem and processor, since the additional lines used to carry the data may be expensive, buses are relatively reliable and, if an error is detected in transmission, the transmission can be repeated without loss of the data.
USPTO Backgrounds
USPTO Backgrounds