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 singlebit errors is to add a parity bit:
b_{0} b_{1} b_{2} b_{N1} 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 parityprotected 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 parityprotected 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
parityprotected bit strings has a detectable error?
(1) 11101101111011011
(2) 11011110101011011
(3) 10111110111011110
(4) 00000000000000000
(2) 11011110101011011
(3) 10111110111011110
(4) 00000000000000000
Strings 1 and 3 have detectable errors. Note that
parity allows one to detect singlebit 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 singlebit 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
singlebit 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 singlebit 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 doublebit errors (i.e.,
two of the data or check bits have been changed). Characterize the sort of
doublebit 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 2outof5 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 2outof5 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 2bit errors) that
can be reliably detected in a 2outof5 code?
Codes with a Hamming distance of 2 can detect
1bit errors. The 2outof5 code also detects 3bit errors, but not 2bit
errors. Normally when we say a code detects nbit errors we imply that it
detects mbit errors for m < n. Following this convention, we would say that
the 2outof5 code detects 1bit errors.
G. We know that even parity is another scheme for detecting errors. If we
change from a 2outof5 code to a 5bit 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 5bit parity encoding, six more than the 10 possible values in the
2outof5 code.