Parity bit error correction model
Each block is transmitted some predetermined number of times. For example, to send the bit pattern "", the four-bit block can be repeated three times, thus producing " ". However, if this twelve-bit pattern was received as " " — where the first block is unlike the other two — it can be determined that an error has occurred. A repetition code is very inefficient, and can be susceptible to problems if the error occurs in exactly the same place for each group e.
The advantage of repetition codes is that they are extremely simple, and are in fact used in some transmissions of numbers stations. A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits i.
It is a very simple scheme that can be used to detect single or any other odd number i. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous. Extensions and variations on the parity bit mechanism are horizontal redundancy checks , vertical redundancy checks , and "double," "dual," or "diagonal" parity used in RAID-DP.
A checksum of a message is a modular arithmetic sum of message code words of a fixed word length e. The sum may be negated by means of a ones'-complement operation prior to transmission to detect errors resulting in all-zero messages. Checksum schemes include parity bits , check digits , and longitudinal redundancy checks. Some checksum schemes, such as the Damm algorithm , the Luhn algorithm , and the Verhoeff algorithm , are specifically designed to detect errors commonly introduced by humans in writing down or remembering identification numbers.
A cyclic redundancy check CRC is a non-secure hash function designed to detect accidental changes to digital data in computer networks; as a result, it is not suitable for detecting maliciously introduced errors.
It is characterized by specification of what is called a generator polynomial , which is used as the divisor in a polynomial long division over a finite field , taking the input data as the dividend , such that the remainder becomes the result. A cyclic code has favorable properties that make it well suited for detecting burst errors. CRCs are particularly easy to implement in hardware, and are therefore commonly used in digital networks and storage devices such as hard disk drives.
The output of a cryptographic hash function , also known as a message digest , can provide strong assurances about data integrity , whether changes of the data are accidental e. Any modification to the data will likely be detected through a mismatching hash value. Furthermore, given some hash value, it is infeasible to find some input data other than the one given that will yield the same hash value.
If an attacker can change not only the message but also the hash value, then a keyed hash or message authentication code MAC can be used for additional security. Without knowing the key, it is not possible for the attacker easily or conveniently calculate the correct keyed hash value for a modified message. Any error-correcting code can be used for error detection. Using minimum-distance-based error-correcting codes for error detection can be suitable if a strict limit on the minimum number of errors to be detected is desired.
The parity bit is an example of a single-error-detecting code. An acknowledgment is a message sent by the receiver to indicate that it has correctly received a data frame. Usually, when the transmitter does not receive the acknowledgment before the timeout occurs i. ARQ is appropriate if the communication channel has varying or unknown capacity , such as is the case on the Internet.
However, ARQ requires the availability of a back channel , results in possibly increased latency due to retransmissions, and requires the maintenance of buffers and timers for retransmissions, which in the case of network congestion can put a strain on the server and overall network capacity. An error-correcting code ECC or forward error correction FEC code is a process of adding redundant data, or parity data , to a message, such that it can be recovered by a receiver even when a number of errors up to the capability of the code being used were introduced, either during the process of transmission, or on storage.
Since the receiver does not have to ask the sender for retransmission of the data, a backchannel is not required in forward error correction, and it is therefore suitable for simplex communication such as broadcasting. Error-correcting codes are frequently used in lower-layer communication, as well as for reliable storage in media such as CDs , DVDs , hard disks , and RAM.
Error-correcting codes are usually distinguished between convolutional codes and block codes:. Shannon's theorem is an important theorem in forward error correction, and describes the maximum information rate at which reliable communication is possible over a channel that has a certain error probability or signal-to-noise ratio SNR.
This strict upper limit is expressed in terms of the channel capacity. More specifically, the theorem says that there exist codes such that with increasing encoding length the probability of error on a discrete memoryless channel can be made arbitrarily small, provided that the code rate is smaller than the channel capacity. The actual maximum code rate allowed depends on the error-correcting code used, and may be lower.
This is because Shannon's proof was only of existential nature, and did not show how to construct codes which are both optimal and have efficient encoding and decoding algorithms. There are two basic approaches: The latter approach is particularly attractive on an erasure channel when using a rateless erasure code. By the time an ARQ system discovers an error and re-transmits it, the re-sent data will arrive too late to be any good.
Applications where the transmitter immediately forgets the information as soon as it is sent such as most television cameras cannot use ARQ ; they must use FEC because when an error occurs, the original data is no longer available. Applications that require extremely low error rates such as digital money transfers must use ARQ.
Reliability and inspection engineering also make use of the theory of error-correcting codes. Development of error-correction codes was tightly coupled with the history of deep-space missions due to the extreme dilution of signal power over interplanetary distances, and the limited power availability aboard space probes. Whereas early missions sent their data uncoded, starting from digital error correction was implemented in the form of sub-optimally decoded convolutional codes and Reed—Muller codes.
The Voyager 1 and Voyager 2 missions, which started in , were designed to deliver color imaging amongst scientific information of Jupiter and Saturn. The Voyager 2 craft additionally supported an implementation of a Reed—Solomon code: Concatenated codes are increasingly falling out of favor with space missions, and are replaced by more powerful codes such as Turbo codes or LDPC codes.
The different kinds of deep space and orbital missions that are conducted suggest that trying to find a "one size fits all" error correction system will be an ongoing problem for some time to come. For missions close to Earth the nature of the noise in the communication channel is different from that which a spacecraft on an interplanetary mission experiences. Additionally, as a spacecraft increases its distance from Earth, the problem of correcting for noise gets larger.
The demand for satellite transponder bandwidth continues to grow, fueled by the desire to deliver television including new channels and High Definition TV and IP data. Transponder availability and bandwidth constraints have limited this growth, because transponder capacity is determined by the selected modulation scheme and Forward error correction FEC rate.
The need in the art is addressed by the present invention which provides fin improved multi-bit error correction system. The inventive error correcting system performs a fast error correcting operation on individual bits within multi-bit modules.
In a specific implementation, the invention uses a Hamming code and divides an n times m bit data word into n modules, with each module having m bits. Next, the ith bits of each module are combined to form a set of parity bits. Syndrome bits are generated from the parity bits and used to locate errors in the bits and provide an indication of same.
Finally, errors in the bits are corrected in a conventional manner to provide corrected data bits. The invention therefore provides high speed error detection and correction for multiple bit modules in digital data communication, processing, storage and retrieval systems. Illustrative embodiments and exemplary applications will now be described with reference to the accompanying drawings to disclose the advantageous teachings of the present invention. Note that the Reed-Solomon decoder handles all of the data in a digital word at one time.
This is illustrated with reference to FIGS. Next these two group comparisons are combined and the resulting combination is combined with syndrome group two again for error correction location indication. The Reed-Solomon parity equations are shown below:. The Reed-Solomon error location equations for bits 31 - 28 are shown below: Reed-Solomon parity generation requires several data bits to be combined together.
These wide equations cause the parity generation logic to have relatively large delays. The error location equations similarly have many terms. To implement each of these functions in current technologies, where typical gate width is limited to 2 to 5 inputs, creates paths of propagation delay that are very large. Hence, package correction is accomplished at the cost of memory speed.
For example, the levels of logic required for the typical conventional Reed-Solomon decoder is shown below in Table I:. The 11 level logic of the Reed-Solomon decoder typically amounts to a total delay in complementary metal-oxide semiconductor CMOS technology of 27 nanoseconds. As mentioned above, for many current applications, there is a need for a faster error detecting and correcting system. As described more fully below, the multiple Hamming code decoder of the present invention can perform error correction on the same data as the Reed-Solomon decoder with 6 logic levels and a typical delay of 15 nanoseconds in CMOS technology.
The illustrative error correcting system 1 includes a multiple Hamming code decoder 10 consisting of M individual identical Hamming error correcting code decoders 11 , 13 , As with the conventional Reed-Solomon decoder, the error correcting codes bits are stored together in modules separate from the locations where data is stored. As discussed more fully below, by using several identical simple fast Hamming code decoders to operate on single bits of data, a higher throughput of data may be achieved.
There is one decoder for each bit in a module. The ith bit of each module is presented to the ith decoder where i varies from 1 to m, Thus, the 1st bit of each module is input to the first decoder 11 , the 2nd bit of each module is input to the second decoder 13 , the third bit of each module is input to the third decoder 15 and so on.
With nine modules in tie illustrative embodiment, 9 bits of data are presented for error correction. The parity generator 16 of each decoder combines the 9 bits together to form parity bits using exclusive OR gates in accordance with the multiple Hamming code parity equations shown below: Each syndrome generator 18 then generates 5 syndromes in the example using error correcting code ECC checkbits stored and retrieved wish the data from memory in accordance with the same bit slice scheme.
The syndromes are combined logically to locate errors by an error location and correction indication circuit The error location and correction indication circuit 20 is implemented with exclusive OR gates and logic gates in accordance with the equations below. The multiple Hamming code error location equation for bits 31 - 28 are shown below: The erroneous bits are corrected by a conventional error correcting circuit 22 to provide the corrected data bits.
Those skilled in the art will appreciate that the multiple Hamming code decoder system of the present invention limits the parity equation depth to 6 terms and limits the error location terms to 5.
As illustrated in Table I above, the parity generation terms can be implemented in current technologies with a maximum of two levels of gate delay while the error location terms can be implemented in one to two levels of gate delay, depending on whether input gates with sufficiently wide fan-in are available.
In any event, the result is a correction scheme that is very fast compared with the Reed-Solomon approach while offering the same correction capabilities. Thus, the present invention has been described herein with reference to a particular embodiment for a particular application. Those having ordinary skill in the art and access to the present teachings will recognize additional modifications, applications and embodiments within the scope thereof.
For example, the invention is not limited to use with Hamming codes. Other codes may be used for the purpose as well. In addition, the present teachings may be used in a system in which memory words are divided into groups greater than a single bit and Reed-Solomon codes, for example, as used for the error correction.