[Back to Lecture Notes page]
Error Detection and Correction
- How to detect errors and how to correct detected errors.
- Error correcting codes
– include enough redundant information in the bits so that even if some are some errors, the receiver can still infer what the correct bits are suppose to be.
- Error detecting codes
– include just enough extra information in the bits so that the receiver will be able to tell there are errors, but not be able to infer what the correct bits are suppose to be.
- Most errors are burst errors – most errors in transmission happen to large chunks of bits rather than isolated bits. This is due to the physical processes generating the errors, eg. electrical interference.
- Good because less whole blocks are affected
- Bad because harder to correct – see error correcting codes later
Error Correcting Codes
- We add some check bits to the original message bits.
- Check bits + Message bits = codeword – instead of sending just the message bits, we send the whole codeword to the receiver.
- Error correcting codes are built on the idea of Hamming Distance – Hamming distance between two bit sequences (must be of equal length) is just the number of bits which are different.
Eg.
Hamming distance between 0011 and 0010 is 1 – only the last bit is different.
Hamming distance between 1011 and 0010 is 2 – first and last bits are different.
Hamming distance between 1011 and 0100 is 4 – all four bits are different.
- A code is just a collection of legal codewords we can transmit.
- The Hamming distance of a code is the minimum distance between all codewords.
Eg 1.
We have a code consisting of 000000, 000111, 111000, and 111111 – using this code we can ONLY transmit these four bit sequences.
The Hamming distance between 000000 and 000111 is 3.
The Hamming distance between 000000 and 111000 is 3.
The Hamming distance between 000000 and 111111 is 6.
The Hamming distance between 000111 and 111000 is 6.
The Hamming distance between 000111 and 111111 is 3.
The Hamming distance between 111000 and 111111 is 3.
So the Hamming distance of this code (the minimum distance from above) is 3.
- When a codeword has errors, we look for the nearest legal codeword in the code - The idea of error correction is to have codes with Hamming distance large enough so that if a few bits gets garbled, we will still be able to find what the legal codeword is suppose to be, by looking for the codeword with the least hamming distance from the codeword with error.
Eg
If we use the code from eg 1 above:
If a sender sends 000111 but the first bit was changed on transmission, the receiver will receive 100111. The receiver knows it is an error because 100111 is not a valid codeword in this code. To figure out what the real codeword should be, he just looks for the "nearest" legal codeword, which is 000111, which is correct.
Note that this will not work if there are 2 errors, eg 000111 becomes 110111. If a receiver receives 110111, he will infer that the correct codeword is 111111, which is wrong. For a code with Hamming distance n, it can only handle n/2 number of bit errors.
Designing Error Correcting Codes
- So how do we actually design the check bits so that the final codewords are far enough apart?
- A parity bit is a single check bit added to a message so that the final number of 1’s is even (or odd).
- Even parity – final number of 1’s is even
- Odd parity – final number of 1’s is odd.
Eg (we will put the parity bit at the beginning of the codeword).
In even parity, the parity bit for 1100 is 0 – so the codeword is 01100 (even number of 1’s).
In even parity, the parity bit for 1110 is 1 – so the codeword is 11110 (even number of 1’s).
In odd parity, the parity bit for 1100 is 1 – so the codeword is 11100 (odd number of 1’s).
In odd parity, the parity bit for 1110 is 0 – so the codeword is 01110 (odd number of 1’s).
Hamming Code
- Hamming discovered that we can use the minimum number of parity bits to do error correction by:
- For a codeword, use the bits 1, 2, 4, 8, 16, etc (the ones which are powers of two) as parity bits.
- Use the other bits 3, 5, 6, 7, 9, 10, etc, for the message bits.
- This is called the Hamming code
(Read the textbook p185 on how to do this).
- Hamming code used for single bit errors – can also be used for burst errors of more than one bit.
See Fig 3-6 p186
The idea is to take a series of k codewords and transmit all the first bits first, then all their second bits, the all their third bits, and so on. If we get a burst error (up to k bits), then all we lose is a single bit in each of the codewords. As we described above, we can still recover the original codeword from a single bit error.
Error Detecting Codes
- We need many parity bits to correct errors, but only a few bits to only detect errors.
- Sometimes better to just detect errors, and tell the sender to retransmit if there are errors.
- Use one parity bit per block - to detect single bit errors, we only need one parity bit in each block, regardless of how big the block is.
Cyclic Redundancy Code (CRC code)
- Also called polynomial code
- Based on the idea of representing bit strings as polynomials, and using polynomials arithmetic to compute the checksums – a checksum is a series of bits used as check bits. It is calculated by the sender based on the message and transmitted to the receiver. If the checksum calculated by the receiver is not the same as the checksum received, the receiver knows there are errors in the received message.
- Some international standard CRC codes:
- CRC-16 and CRC-CCITT uses 16-bit checksums and can catch
- all 1-bit and 2-bit errors,
- all errors with odd number of bits
- all 16-bit or less burst errors
- 99.997% of 17-bit burst errors
- 99.998% 18-bit or more burst errors
- CRC checksums usually calculated in hardward.
[Back to Lecture Notes page]