An error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is the sender encodes the message with redundant information in the form of an ECC. The redundancy allows the receiver to detect and correct a limited number of errors without retransmission.
The advantage is that a system using ECC does not require a reverse channel to request retransmission of data when an error occurs. The downside is that there is a fixed overhead that is added to the message, thereby requiring a higher forward channel bandwidth. ECC is therefore applied in situations where retransmissions are costly or impossible, such as one-way communication links and when transmitting to multiple receivers in multicast.
Multidimensional parity-check code[]
A multidimensional parity-check code (MDPC) is a simple type of error correcting code that operates by arranging the message into a multidimensional grid, and calculating a parity digit for each row and column. In general, an n-dimensional parity scheme can correct n/2 errors.
The two-dimensional parity-check code, usually called the optimal rectangular code, is the most popular form of multidimensional parity-check code.
Assume that the goal is to transmit the four-digit message "1234", using a two-dimensional parity scheme. First the digits of the message are arranged in a rectangular pattern:
- 12
- 34
Parity digits are then calculated by summing each column and row separately:
- 123
- 347
- 46
The eight-digit sequence "12334746" is the message that is actually transmitted. If any single error occurs during transmission then this error can not only be detected but can also be corrected as well. Let us suppose that the received message contained an error in the first digit. The receiver rearranges the message into the grid:
- 923
- 347
- 46
The receiver can see that the first row and also the first column add up incorrectly. Using this knowledge and the assumption that only one error occurred, the receiver can correct the error. In order to handle two errors, a 4-dimensional scheme would be required, at the cost of more parity digits.
Decoder[]
An n-dimensional parity scheme is only guaranteed to correct up to n/2 errors, as the minimum distance is (n + 1). As with all block codes, a soft-decision decoder may be able to correct more than this.
Hamming code[]
A Hamming code works on the same principle but with a different system. To transmit 8 bits you would need 4 additional parity bits. Parity bit P1 covers data bits 1, 3, 5, and 7. Parity bit P2 covers data bits 1, 2, 5, and 6. Parity bit P3 covers data bits 1, 2, 3, and 4.
| Data bits | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| P1 | X | X | X | X | ||||
| P2 | X | X | X | X | ||||
| P3 | X | X | X | X | ||||
| P4 | X | X | X | X | X | X | X | X |
If after transmission parity bits P1, P2, P3 and P4 are wrong then the decoder will assume that data bit 1 is wrong.
If after transmission only parity bit P4 is wrong then the decoder will assume that data bit 8 is wrong.
References[]
|
This page uses content that though originally imported from the Wikipedia article Error correction code might have been very heavily modified, perhaps even to the point of disagreeing completely with the original wikipedia article. The list of authors can be seen in the page history. The text of Wikipedia is available under the Creative Commons Licence. |
|
|
This page uses content that though originally imported from the Wikipedia article Multidimensional parity-check code might have been very heavily modified, perhaps even to the point of disagreeing completely with the original wikipedia article. The list of authors can be seen in the page history. The text of Wikipedia is available under the Creative Commons Licence. |