GCSE Link: None
Sometimes, data can be corrupted while stored or while being transferred. We need systems to find and correct the corrupted data.
Majority voting is the simplest form of error checking and correction.
If you send three copies of each bit, you will have either a majority of 0s or 1s. Just
choose the majority for each bit. For example, if we receive 1100,
1010 and 1001, we know the original sequence was
1000.
With majority voting, we can find and correct errors in the data. However, we need three times the space to store the whole thing (e.g. a 20-bit sequence would need 60 bits in total with majority voting.)
Parity bits can find errors but not correct them.
Usually, one parity bit will be added to the end of a seven-bit sequence to make the total number of
1s even. For example, the sequence 1000101 will have the parity bit
1 appended to it (because there were 3 ones before, and now there are 4).
If we receive a sequence with an odd number of 1s, we know something has gone wrong. However, if we receive a sequence with and even number of 1s, we don't actually know that it's correct. In that case, the data may have an even number of errors. Usually, however, there aren't two or more errors in one byte of data.
(Note: odd parity bits are very uncommon, but in that case the parity bit should make the total number of 1s odd).
Although errors cannot be corrected with parity bits, they take up a lot less space than majority voting.
Check digits are basically parity bits for decimal numbers.
For example, the last digit of a ISBN barcode number or credit card number is a check digit: it verifies that the number has been entered correctly.
Checksums are similar to check digits, but larger than one digit.
Just like with check digits, an algorithm is applied to the data to find a check number, the checksum. This can then be verified when entered.
If a system using majority voting received the sequences 00101101,
01010011 and 11000100, find
the original sequence.
Write the sequences out, lining them up like this:
0 0 1 0 1 1 0 1
0 1 0 1 0 0 1 1
1 1 0 0 0 1 0 0
Then, find the majority for each bit:
0 1 0 0 0 1 0 1