Error checking and correction
A parity bit is a method of detecting errors in data during transmission. When sending data, it is sent as a series of 0s and 1s.
In the figure above, a Unicode character is transmitted as the binary code 0111000110101011. It is quite possible that this code could get corrupted as it passed around either inside the computer or across a network.
Parity can only detect odd numbers of errors and cannot repair the damaged bits. |
In the top example the parity bit is set to 0 to maintain an even number of ones. One method for detecting errors is to count the number of ones in each byte before the data is sent to see whether there is an even or odd number. At the receiving end, the code can be checked to see whether the number is still odd or even.
We have to remember to count 1s not 0s and the parity bit is normally put as the MSB. |
Majority voting[edit | edit source]
Majority voting is another method of identifying errors in transmitted data. In this case each bit is sent three times. So the binary code 1001 would be sent as:
111000000111.
When data is checked, patterns of three bits are usually seen. In this case, it is 111 for the first bit, then 000 and so on. Where there is a discrepancy, majority voting indicates which bit occurs the most frequently. For example, if the same code 10001 was received as:
101010000111.
Assume that the first bit should be 1 as two out of three of the three bits are 1 and assume that the second bit is 0 as two of the three bits are 0. The last two bits are 0 and 1 as there appears to be no errors in this part of the code.
Majority vote can repair errors but if two errors are made on the same bit then it will not be detected. And of course three times as much data must be transmitted. |
Check digits[edit | edit source]
Like a parity bit, a check digit is a value that is added to the end of a number to try and ensure that the number is not corrupted in any way. The check digit is created by taking the digits that make up the number itself and processing them in some way to create a single digit. The simplest but most error-prone method is to add the digits of the number together, and keep on adding the digits until only a single digit remains.
So the digits of 123456 add up to 21 and 2 and 1 in turn add up to 3, so the number with its check digit becomes 1234563. When the data is being processed the check digit is recalculated and compared with the digit that has been transmitted. Where the check digit is the same then it is assumed that the data is corrected. Where there is a discrepancy, an error message is generated.
Check digits identify one or more errors have occurred but need more processing than parity and don't repair like majority vote. |