Error detection and correction

Problem : Error detection and correction

A.   To protect stored or transmitted information one can add check bits to the data to facilitate error detection and correction. One scheme for detecting single-bit errors is to add a parity bit:

b₀ b₁ b₂ b_N-1 p

When using even parity, p is chosen so that the number of "1" bits in the protected field (including the p bit itself) is even; when using odd parity, p is chosen so that the number of "1" bits is odd. In the remainder of this problem assume that even parity is used.

To check parity-protected information to see if an error has occurred, simply compute the parity of information (including the parity bit) and see if the result is correct. For example, if even parity was used to compute the parity bit, you would check if the number of "1" bits was even.

If an error changes one of the bits in the parity-protected information (including the parity bit itself), the parity will be wrong, i.e., the number of "1" bits will be odd instead of even. Which of the following parity-protected bit strings has a detectable error?

(1) 11101101111011011
(2) 11011110101011011
(3) 10111110111011110
(4) 00000000000000000

Strings 1 and 3 have detectable errors. Note that parity allows one to detect single-bit errors (actually any odd number of errors) but doesn't defend against an even number of bit errors.

B.    Detecting errors is useful, but it would also be nice to correct them! To build an error correcting code (ECC) we'll use additional check bits to help pinpoint where the error occurred. There are many such codes; a particularly simple one for detecting and correcting single-bit errors arranges the data into rows and columns and then adds (even) parity bits for each row and column. The following arrangement protects nine data bits:

C.  b0,0     b0,1    b0,2    prow0

D.  b1,0     b1,1    b1,2    prow1

E.  b2,0     b2,1    b2,2    prow2

F.  pcol0    pcol1   pcol2

A single-bit error in one of the data bits (b_I,J) will generate two parity errors, one in row I and one in column J. A single-bit error in one of the parity bits will generate just a single parity error for the corresponding row or column. So after computing the parity of each row and column, if both a row and a column parity error are detected, inverting the listed value for the appropriate data bit will produce the corrected data. If only a single parity error is detected, the data is correct (the error was one of the parity bits).

Give the correct data for each of the following data blocks protected with the row/column ECC shown above.

(1)  1011    (2) 1100    (3) 000    (4) 0111

     0110        0000        111        1001

     0011        0101        10         0110

     011         100                    100

(1)  0011    (2) 1100    (3) 000    (4) 0110

     0110        0000        101        1001

     0011        0101        10         0110

     011         100                    100

(1) and (3) had single bit errors, (2) had no detectable errors, and (4) had an error in a parity bit. The red digits represent corrected values.

C.    The row/column ECC can also detect many double-bit errors (i.e., two of the data or check bits have been changed). Characterize the sort of double-bit errors the code does not detect.

If parity bits detect an error for exactly one column and exactly one row, this will be interpreted as a single bit error in the corresponding data position. This can happen with two parity bit errors, one in each of the row and column check bits. The fact that two errors occurred is not detected; worse, the corresponding data position is changed from the correct value to the incorrect value.

D.   In the days of punch cards, decimal digits were represented with a special encoding called 2-out-of-5 code. As the name implies two out of five positions were filled with 1's as shown in the table below:

Code	Decimal
11000	1
10100	2
01100	3
10010	4
01010	5
00110	6
10001	7
01001	8
00101	9
00011	0

E.    What is the smallest Hamming distance between any two encodings in 2-out-of-5 code?

The Hamming distance between any two encodings is the number of bit positions in which the encodings differs. With this code, the smallest Hamming distance is 2.

F.    Characterize the types of errors (eg, 1- and 2-bit errors) that can be reliably detected in a 2-out-of-5 code?

Codes with a Hamming distance of 2 can detect 1-bit errors. The 2-out-of-5 code also detects 3-bit errors, but not 2-bit errors. Normally when we say a code detects n-bit errors we imply that it detects m-bit errors for m < n. Following this convention, we would say that the 2-out-of-5 code detects 1-bit errors.

G.   We know that even parity is another scheme for detecting errors. If we change from a 2-out-of-5 code to a 5-bit code that includes an even parity bit, how many additional data encodings become available?

There are 16 possible values for the 4 data bits in the 5-bit parity encoding, six more than the 10 possible values in the 2-out-of-5 code.