__Problem :__

**Hamming single-error-correcting-code**

The Hamming
single-error-correcting code requires approximately log2(N) check bits to
correct single-bit errors. Start by renumbering the data bits with indices that
aren't powers of two:

Indices for 16 data bits = 3, 5, 6, 7, 9, 10,
11, 12, 13, 14, 15, 17, 18, 19, 20, 21

The idea is to compute
the check bits choosing subsets of the data in such a way that a single-bit
error will produce a set of parity errors that uniquely indicate the index of
the faulty bit:

p0 = even parity for data bits 3, 5, 7, 9, 11,
13, 15, 17, 19, 21

p1 = even parity for data bits 3, 6, 7, 10, 11, 14, 15, 18, 19

p2 = even parity for data bits 5, 6, 7, 12, 13, 14, 15, 20, 21

p3 = even parity for data bits 9, 10, 11, 12, 13, 14, 15

p4 = even parity for data bits 17, 18, 19, 20, 21

p1 = even parity for data bits 3, 6, 7, 10, 11, 14, 15, 18, 19

p2 = even parity for data bits 5, 6, 7, 12, 13, 14, 15, 20, 21

p3 = even parity for data bits 9, 10, 11, 12, 13, 14, 15

p4 = even parity for data bits 17, 18, 19, 20, 21

Note that each data bit
appears in at least two of the parity calculations, so a single-bit error in a
data bit will produce at least two parity errors. When checking a protected
data field, if the number of parity errors is zero or one, the data bits are okay
(exactly one parity error indicates that one of the parity bits was corrupted).
If two or more parity errors are detected then the errors identify exactly
which bit was corrupted.

A.
What is the relationship between the index of a particular data
bit and the check subsets in which it appears? Hint: consider the binary
representation of the index.

Digit

*i*in the binary expansion of a data bit index indicates whether the index should be included in the calculation of p*i*. For example, the first data bit (which has index 3 = 00011) would be used in the parity calculation for parity bits p0 and p1. Likewise, the sixth data bit (which has index 10 = 01010) would be used in the parity calculation for parity bits p1 and p3. Since no data bit is assigned an index which is a power of two, we guarantee that each data bit is used in the calculation of at least two different parity bits.
B.
If the parity calculations involving p0, p2 and p3 fail, assuming
a single-bit error what is the index of the faulty data bit?

We need to find the data index that appears in
the calculation p0, p2 and p3 but

*not*in the calculations for p1 and p4. Indicies 13 and 15 appear in p0, p2 and p3, but index 15 appears in the calculation for p1. So the index of the data bit that failed is 13.
We
can construct the index of the failing data bit directly from the parity
calculations using e

*i*= 1 if the p*i*failed and e*i*= 0 if it didn't. So if p0, p2 and p3 failed, and the others didn't, the index is e4e3e2e1e0 = 01101 = 13_{10}.
C.
The Hamming SECC doesn't detect all double-bit errors.
Characterize the types of double-bit errors that will not be detected. Suggest
a simple addition to the Hamming SECC that allows detection of all double-bit
errors.

If errors occur in two separate parity bits, this
will be misinterpreted as a single data bit error. Also when certain pairs of
data bits have errors, the double-bit error masquerades as a single-bit error
in another, unrelated bit (e.g., suppose bits with indicies 19 and 21 both have
errors).

We
can detect these situations by adding an additional parity bit, p5, which is
the parity of all other parity and data bits. If a single data bit failed, this
bit would indicate and error. But if exactly two bits have failed, p5 would
indicate no error, but p0, p1, ..., p4 would indicate the presence of some
error (although the indication might point at the wrong data bit). So, if by
looking at p0, p1, ..., p4 it seems as though an error occurred, we should
check p5 to make sure that only one error occurred. If p5 does not indicate an
error, then a double-bit error occurred.

## No comments:

## Post a Comment