Error-Correcting Codes

Prev: Cyclic Redundancy Check

Next: Hilbert’s Curve

Sections

• 15-1 Introduction
• 15-2 The Hamming Code
• 15-3 Software for SEC-DED on 32 Information Bits
• 15-4 Error Correction Considered More Generally

Problems

1. Show a Hamming code for $m=3$, making a table similar to Table 15-1.

2. In a certain application of an SEC code, there is no need to correct the check bits. Hence the $k$ check bits need only check the information bits, but not themselves. For $m$ information bits, $k$ must be large enough so that the receiver can distinguish $m+1$ cases: which of the $m$ bits is in error, or no error occurred. Thus, the number of check bits required is given by $2^k\ge m+1$. This is a weaker restriction on $k$ than is the Hamming rule, so it should be possible to construct, for some values of $m$, an SEC code that has fewer check bits than those required by the Hamming rule. Alternatively, one could have just one value to signify that an error occurred somewhere in the check bits, without specifying where. This would lead to the rule $2^k\ge m+2$.

   What is wrong with this reasoning?

3. Given $m$, how would you find the least $k$ that satisfies inequality (1)?

4. Show that the Hamming distance function for any binary block code satisfies the triangle inequality: if $x$ and $y$ are code vectors and $d(x,y)$ denotes the Hamming distance between them, then

   $$d(x,z)\le d(x,y)+d(y,z).$$

5. Prove: $A(2^n,2d)\ge A(n,d)$.

6. Prove the singleton bound:

   $$A(n,d)\le 2^{n-d+1}.$$

7. Show that the notion of a perfect code as equality in the right-hand portion of inequality (6) is a generalization of the Hamming rule.

8. What is the value of $A(n,d)$ if $n=d$? Show that for odd $n$, these codes are perfect.

9. Show that if $n$ is a multiple of 3 and $d=2n/3$, then $A(n,d)=4$.

Show that if $d>2n/3$, then $A(n,d)=2$.

A two-dimensional parity check scheme for 64 information bits arranges the information bits $u_0\dots u_{63}$ into an $8\times 8$ array, and appends a parity bit to each row and column as shown in the book. Continue the exercise from that arrangement.