Binary Codes: Hamming Codes for Channel Coding

The idea behind Hamming codes is to intersperse, or append, extra binary digits to a binary code so that errors in transmission of the code over a channel may be detected and corrected. For example, suppose we transmit the code 01101001, and it is received as 01001001. In this transmission, the third most significant bit is received erroneously. Let's define the following “modulo-2 addition” of binary numbers:

0⊕0=0

0⊕1=1

1⊕0=1

1⊕1=0.

(1)

Multiplication in modulo-2 arithmetic is simply 0·0=0·1=1·0=0 and 1 ·1=1. Then we can say that the error sequence 00100000 is “added” to the transmission 01101001 to produce the erroneous reception:

	01101001	transmitted
⊕	00100000	error
	01001001	received.

(2)

Hamming error correcting codes will permit us to receive the erroneous transmission and to detect and correct the error. This is obviously of great value in transmitting and storing information. (Imagine how upset you would be to have the binary code for your checking account confused with that of Mrs. Joan Kroc.)

Choosing the Number of Check Bits. Let's suppose we have N bits of information that we wish to transmit and that we wish to intersperse “check bits” that will enable us to detect and correct any single bit error in the transmission. If we use N information bits and n check bits, then we will transmit a code word containing N+n bits. The n check bits can code 2ⁿ events, and we want these events to indicate whether or not any errors occurred and, if so, where they occurred. Therefore we require

where (N+n) is the number of single error events that can occur and +1 is the number of no-error events. For example, when N=4, we require n=3 so that 2³≥(4+3)+1.

How many check bits do you require to code seven bits of information for single error correction?

Code Construction. Let's suppose we have constructed an (N,n) Hamming code consisting of N information bits and n check bits (or parity bits). We denote the information bits byx₁,x₂,...,x_N and the check bits by c₁,c₂,...,c_n. These bits may be interspersed. When N=4 and n=3, then a typical array of bits within a code word would be one of the following:

[ c1 c2 x1 c3 x2 x3 x4 ]

or

[ x1 x2 x3 x4 c1 c2 c3 ]

.(3)

The first ordering is “natural” (as we will see), and the second is “systematic” (a term that is used to describe any code whose head is information and whose tail is check). If a single error occurs in an (N,n) code, then the received code word will be the modulo-2 sum of the code word and the error word that contains a 1 in its i^{normaltnormalh} position:

[

c1

c2

xnormall

c3

x2

x3

x4

]⊕[

0

0

0

normall

0

0

0

].(4)

We would like to operate on this received code word in such a way that the location of the error bit can be determined. If there were no code word, then an obvious solution would be to premultiply the error word by the parity check matrix

A^T=

[ 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ]

[ (1) (2) (3) (4) (5) (6) (7) ]

.(5)

The i^{normaltnormalh} column of A^T is just the binary code for i. When A^T premultiplies an error word, the error bit picks out the column that codes the error position:

Figure 1

If the error word contains no error bits, then the product is 0, indicating no errors.

This seems like a good idea, but what about the effect of the code word? In Exercise 1, you are asked to show that the effect of the parity check matrix A^T applied to the modulo-2 sum of a code word x and an error word e is

normalA^T(normalx⊕normale)=normalA^Tnormalx⊕normalA^Tnormale.(6)

In this equation all sums and products obey the rules of modulo-2 arithmetic.

EXERCISE 1

Let normaly=normalx⊕normale denote the modulo-2 sum of a code word x and an error word normale;normalA^T is a parity check matrix. Show that

normalA^Tnormaly=normalA^Tnormalx⊕normalA^Tnormale.(7)

We have designed the parity check matrix A^T so that the syndromenormalA^Tnormale produces a binary code for the error location. (The location of the error is normaltnormalh^'normalesyndrome for the error word.) The product normalA^Tnormalx will interfere with this syndrome unless A^Tx=0. Therefore we will require that the code word x satisfy the constraint

normalA^Tnormalx=0.(8)

This constraint actually defines the Hamming code. Let's illustrate this point by applying the constraint to a code word in its “natural format” normalx^T=(c₁c₂x₁c₃x₂x₃x₄).

Natural Codes. When the information bits and the check bits are coded in their natural order (c₁c₂x₁c₃x₂x₃x₄), then we may determine the check bits by writing normalA^Tnormalx as follows:

[

1	0	1	0	1	0	1
0	1	1	0	0	1	1
0	0	0	1	1	1	1

][

c1

c2

x1

c3

x2

x3

x4

]=[

0

0

0

](9)

We use the rules of modulo-2 arithmetic to write these constraints as

c1⊕x1⊕x2⊕x4=0

c2⊕x1⊕x3⊕x4=0

c3⊕x2⊕x3⊕x4=0.

(10)

Therefore the check bits c₁,c₂, and c₃ are simply the following modulo-2 sums

c1=x1⊕x2⊕x4

c2=x1⊕x3⊕x4

c3=x2⊕x3⊕x4.

(11)

This finding may be organized into the matrix equation

[

c1

c2

xnormall

c3

x2

x3

x4

]=[

1101

1011

1000

0111

0100

0010

0001

][

x1

x2

x3

x4

].(12)

This equation shows how the code word x is built from the information bits (x₁,x₂,x₃,x₄). We call the matrix that defines the construction a coder matrix and write it as H:

x=HΘ

normalxT=(c1c2x1c3x2x3x4)ΘT=(x1x2x3x4)

(13)

H=[

1101

1011

1000

0111

0100

0010

0001

](14)

This summarizes the construction of a Hamming code x.

EXERCISE 2

Check to see that the product of the parity check matrix A^T and the coder matrix H is normalA^TnormalH=0. Interpret this result.

EXERCISE 3

Fill in the following table to show what the Hamming (4,3) code is:

x1	x2	x3	x4	c1	c2	x1	c3	x2	x3	x4
0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	1	1	0	1	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

(15)

EXERCISE 4

Design a Hamming (11,n) code for coding eleven information bits against single errors. Show your equations for c₁,c₂,...,c_n and write out the coder matrix H for x=normalHΘ.

Decoding. To decode a Hamming code, we form the syndrome normalA^Tnormaly for the received (and possibly erroneous) code word normaly=normalx⊕normale. BecausenormalA^Tnormalx=0, the syndrome is

normals=normalA^Tnormale.(16)

Convert this binary number into its corresponding integer location and change the bit of y in that location. If the location is zero, do nothing. Now strip off the information bits. This is the decoding algorithm.

EXERCISE 5

Use the table of Hamming (4,3) codes from Exercise 3 to construct a table of received codes that contain either no bit errors or exactly one bit error. Apply the decoding algorithm to construct (x₁,x₂,x₃,x₄) and show that all received code words with one or fewer errors are correctly decoded.

Digital Hardware. The tables you have constructed in Exercise 3 and 5 for coding and decoding Hamming (4,3) codes may be stored in digital logic chips. Their functionality is illustrated inFigure 1. The coder chip accepts (x₁x₂x₃x₄) as its address and generates a coded word. The decoder chip accepts (c₁c₂x₁c₃x₂x₃x₄) as its address and generates a decoded word. In your courses on digital logic you will study circuits for implementing coders and decoders.

Figure 2: Digital Logic for Hamming Code

EXERCISE 6

Discuss the possibility of detecting a received (4,3) code word that is neither a valid code word nor a code word with a single error. How would you use such a detector?

EXERCISE 7

What fraction of received seven-bit words can be correctly decoded as Hamming (4,3) codes?

Systematic Codes. Systematic Hamming codes are codes whose information bits lead and whose check bits trail. The format for a (4,3) code is then (x₁x₂x₃x₄c₁c₂c₃). The construction of a (4,3) code word from the information bits may be written as

[

x1

x2

x3

x4

c1

c2

c3

]=[

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
c11	c12	c13	c14
c21	c22	c23	c24
c31	c32	c33	c34

][

x1

x2

x3

x4

](17)

The coder matrix takes the form

H=[

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
c11	c12	c13	c14
c21	c22	c23	c24
c31	c32	c33	c34

]=[

I

_____

C

].(18)

The problem is to find the matrix C that defines the construction of check bits. The constraint normalA^Tnormalx=0 produces the constraint normalA^TnormalH=0 so thatnormalA^TnormalHΘ=0. The constraints normalA^TnormalH=0 may be written out as

{

1	0	1	0	1	0	1
0	1	1	0	0	1	1
0	0	0	1	1	1	1

}=[

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
c11	c12	c13	c14
c21	c22	c23	c24
c31	c32	c33	c34

]=[

0	0	0	0
0	0	0	0
0	0	0	0

].(19)

These constraints produce all the equations we need (twelve equations in twelve unknowns) to determine the c_ij.

EXERCISE 8

Solve Equation 19 for the c_ij. Show that the coder matrix for a systematic Hamming (4,3) code is

H=[

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
0	1	1	1
1	0	1	1
1	1	0	1

].(20)

EXERCISE 9

Show that the coder matrix of Exercise 7 is a permutation of the coder matrix in Equation 14. (That is, the rows are reordered.)

EXERCISE 10

(MATLAB) Write a MATLAB program that builds Hamming (4,3) codes from information bits (x₁x₂x₃x₄) and decodes Hamming (4,3) codes (c₁c₂x₁c₃x₂x₃x₄) to obtain information bits(x₁x₂x₃x₄). Synthesize all seven-bit binary codes and show that your decoder correctly decodes correct codes and one-bit error codes.