Error Detection and Correction Codes

When we talk about digital systems, be it a digital computer or a digital communication set-up, the issue of error detection and correction is of great practical significance. Errors creep into the bit stream owing to noise or other impairments during the course of its transmission from the transmitter to the receiver. Any such error, if not detected and subsequently corrected, can be disastrous, as digital systems are sensitive to errors and tend to malfunction if the bit error rate is more than a certain threshold level. Error detection and correction, as we will see below, involves the addition of extra bits, called check bits, to the information-carrying bit stream to give the resulting bit sequence a unique characteristic that helps in detection and localization of errors. These additional bits are also called redundant bits as they do not carry any information. While the addition of redundant bits helps in achieving the goal of making transmission of information from one place to another error free or reliable, it also makes it inefficient. In this section, we will examine some common error detection and correction codes.

Parity Code

A parity bit is an extra bit added to a string of data bits in order to detect any error that might have crept into it while it was being stored or processed and moved from one place to another in a digital system.

We have an even parity, where the added bit is such that the total number of ls in the data bit string becomes even, and an odd parity, where the added bit makes the total number of ls in the data bit string odd. This added bit could be a ‘0’ or a ‘1’. As an example, if we have to add an even parity bit to 01000001 (the eight-bit ASCII code for ‘A’), it will be a ‘0’ and the number will become 001000001. If we have to add an odd parity bit to the same number, it will be a ‘l’ and the number will become 101000001. The odd parity bit is a complement of the even parity bit. The most common convention is to use even parity, that is, the total number of 1s in the bit stream, including the parity bit, is even. The parity check can be made at different points to look for any possible single-bit error, as it would disturb the parity. This simple parity code suffers from two limitations. Firstly, it cannot detect the error if the number of bits having undergone a change is even. Although the number of bits in error being equal to or greater than 4 is a very rare occurrence, the addition of a single parity cannot be used to detect two-bit errors, which is a distinct possibility in data storage media such as magnetic tapes. Secondly, the single-bit parity code cannot be used to localize or identify the error bit even if one bit is in error. There are several codes that provide self-single-bit error detection and correction mechanisms, and these are discussed below.

Repetition Code

The repetition code makes use of repetitive transmission of each data bit in the bit stream. In the case of threefold repetition, ‘1’ and ‘0’ would be transmitted as ‘111’ and ‘000’ respectively. If, in the received data bit stream, bits are examined in groups of three bits, the occurrence of an error can be detected. In the case of single-bit errors, ‘1’ would be received as 011 or 101 or 110 instead of 111, and a ‘0’ would be received as 100 or 010 or 001 instead of 000. In both cases, the code becomes self-correcting if the bit in the majority is taken as the correct bit. There are various forms in which the data are sent using the repetition code. Usually, the data bit stream is broken into blocks of bits, and then each block of data is sent some predetermined number of times. For example, if we want to send eight-bit data given by 11011001, it may be broken into two blocks of four bits each. In the case of threefold repetition, the transmitted data bit stream would be 110111011101100110011001. However, such a repetition code where the bit or block of bits is repeated 3 times is not capable of correcting two-bit errors, although it can detect the occurrence of error. For this, we have to increase the number of times each bit in the bit stream needs to be repeated. For example, by repeating each data bit 5 times, we can detect and correct all two-bit errors. The repetition code is highly inefficient and the information throughput drops rapidly as we increase the number of times each data bit needs to be repeated to build error detection and correction capability.

Cyclic Redundancy Check Code

Cyclic redundancy check (CRC) codes provide a reasonably high level of protection at low redundancy level. The cycle code for a given data word is generated as follows. The data word is first appended by a number of 0s equal to the number of check bits to be added. This new data bit sequence is then divided by a special binary word whose length equals n + 1, n being the number of check bits to be added. The remainder obtained as a result of modulo-2 division is then added to the dividend bit sequence to get the cyclic code. The code word so generated is completely divisible by the divisor used in the generation of the code. Thus, when the received code word is again divided by the same divisor, an error-free reception should lead to an all ‘0’ remainder. A nonzero remainder is indicative of the presence of errors.

The probability of error detection depends upon the number of check bits, n, used to construct the cyclic code. It is 100 % for single-bit and two-bit errors. It is also 100 % when an odd number of bits are in error and the error bursts have a length less than n + 1. The probability of detection reduces to 1 – (1/2)n−1 for an error burst length equal to n + 1, and to 1 – (1/2)n for an error burst length greater than n + 1.

Hamming Code

We have seen, in the case of the error detection and correction codes described above, how an increase in the number of redundant bits added to message bits can enhance the capability of the code to detect and correct errors. If we have a sufficient number of redundant bits, and if these bits can be arranged such that different error bits produce different error results, then it should be possible not only to detect the error bit but also to identify its location. In fact, the addition of redundant bits alters the ‘distance’ code parameter, which has come to be known as the Hamming distance. The Hamming distance is nothing but the number of bit disagreements between two code words. For example, the addition of single-bit parity results in a code with a Hamming distance of at least 2. The smallest Hamming distance in the case of a threefold repetition code would be 3. Hamming noticed that an increase in distance enhanced the code’s ability to detect and correct errors. Hamming’s code was therefore an attempt at increasing the Hamming distance and at the same time having as high an information throughput rate as possible.

The algorithm for writing the generalized Hamming code is as follows:

1. The generalized form of code is P1P2D1P3D2D3D4P4D5D6D7D8D9D10D11P5  , where P and D respectively represent parity and data bits.
2. We can see from the generalized form of the code that all bit positions that are powers of 2 (positions 1, 2, 4, 8, 16,  ) are used as parity bits.
3. All other bit positions (positions 3, 5, 6, 7, 9, 10, 11,  ) are used to encode data.
4. Each parity bit is allotted a group of bits from the data bits in the code word, and the value of the parity bit (0 or 1) is used to give it certain parity.
5. Groups are formed by first checking N− 1 bits and then alternately skipping and checking N bits following the parity bit. Here, N is the position of the parity bit; 1 for P1, 2 for P2, 4 for P3, 8 for P4 and so on. For example, for the generalized form of code given above, various groups of bits formed with different parity bits would be P1D1D2D4D5, P2D1D3D4D6D7, P3D2D3D4D8D9  , P4D5D6D7D8D9D10D11  and so on. To illustrate the formation of groups further, let us examine the group corresponding to parity bit P3. Now, the position of P3 is at number 4. In order to form the group, we check the first three bits (N− 1 = 3) and then follow it up by alternately skipping and checking four bits (N = 4).

The Hamming code is capable of correcting single-bit errors on messages of any length. Although the Hamming code can detect two-bit errors, it cannot give the error locations. The number of parity bits required to be transmitted along with the message, however, depends upon the message length, as shown above. The number of parity bits n required to encode m message bits is the smallest integer that satisfies the condition (2n – n > m.

The most commonly used Hamming code is the one that has a code word length of seven bits with four message bits and three parity bits. It is also referred to as the Hamming (7, 4) code. The code word sequence for this code is written as P1P2D1P3D2D3D4, with P1, P2 and P3 being the parity bits and D1, D2, D3 and D4 being the data bits. We will illustrate step by step the process of writing the Hamming code for a certain group of message bits and then the process of detection and identification of error bits with the help of an example. We will write the Hamming code for the four-bit message 0110 representing numeral ‘6’. The process of writing the code is illustrated in Table 2.9, with even parity. Thus, the Hamming code for 0110 is 1100110. Let us assume that the data bit D1 gets corrupted in the transmission channel. The received code in that case is 1110110. In order to detect the error, the parity is checked for the three parity relations mentioned above. During the parity check operation at the receiving end, three additional bits X, Y and Z are generated by checking the parity status of P1D1D2D4, P2D1D3D4 and P3D2D3D4 respectively. These bits are a ‘0’ if the parity status is okay, and a ‘1’ if it is disturbed. In that case, ZYX gives the position of the bit that needs correction. The process can be best explained with the help of an example. Examination of the first parity relation gives X =1 as the even parity is disturbed. The second parity relation yields Y = 1 as the even parity is disturbed here too. Examination of the third relation gives Z = 0 as the even parity is maintained. Thus, the bit that is in error is positioned at 011 which is the binary equivalent of ‘3’. This implies that the third bit from the MSB needs to be corrected. After correcting the third bit, the received message becomes 1100110 which is the correct code.