A system that uses error-detecting code generates, transmits, and stores data in the form of code words. So, the correct data must be a valid code word. It is expected that the presence of an error in a data bit stream would make it a non code word, and thereby it would be easy to detect an error. However, it may not be the case always. Even after there is an error, if the resultant bit stream is still a valid code word, then the error will not be detected.
| A code detects all single-bit errors if the minimum distance (hamming distance) between all possible pairs of code words is at least 2. |
Let’s understand the above statement clearly.
Consider a 3-bit data stream. There are 8 possible combinations of data starting from 000 to 111. We will look at two different sets of codes as mentioned below:
Code 1 – {001, 010, 100, 101, 111}
The above code has five code words. The code word 101 is immediate adjacent to 001, 100, and 111. So, the distance of Code 1 is only 1, and not 2. Therefore, Code 1 is not capable of detecting all single-bit errors. For example, if the code word 001 has an error at the MSB, then the code word will become 101 which is again a valid code word. In this case, the error will not be detected.
If we make 101 a non-code word, then the new code will be Code 2 – {001, 010, 100, 111}. Now, the distance of Code 2 is 2. Therefore, Code 2 is capable of detecting all possible single-bit errors.
In this case, Code 2 is more robust in terms of error detection than Code 1. However, we have fewer code words for carrying the actual information in the case of Code 2 than Code 1. Therefore, we generally perform an encoding, where we add additional bits (check bits) so that we can have enough non-code words. For example, the addition of a parity bit for error detection.
Coding
A data word with ‘d‘ bits is encoded into a code word with ‘c‘ bits, where c>d
- Not all 2c combinations are valid code words. It also includes the non code words.
- To extract original data, c bits must be decoded
- If the c bits do not constitute a valid code word, an error is detected
- For certain encoding schemes – some types of errors can also be corrected
- This encoding introduces information redundancy; that is, we use more bits than absolutely needed
Key Parameters of Code
- Number of erroneous bits that can be detected
- Number of erroneous bits that can be corrected
Overhead of Code
- Additional bits required
- Time required to encode and decode
Previous Table of Content Next