EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

The Hamming Code Revisited - A Matrix Approach

The Hamming Code has been introduced as an error control method allowing correction of single bit errors. The examples described a (7,4) code in which 7-bit codewords carried 4 data bits and 3 error control bits.

The approach will now be generalized and studied in matrix form, where it can be extended to more powerful codes.

The Hamming Code in Matrix Form
 Consider the 7-bit Hamming code built on a message having four data bits (D) which are to be transmitted as a 7-bit codeword by adding three error control bits. This would be called a (7,4) code. The three bits to be added are three EVEN Parity bits (P), where the parity of each is computed on different subsets of the message bits. Let the message be the four element vector M = [ D7 D6 D5 D3 ] By inspection, define a (4 × 7) generator matrix G in which the contents of each column correspond to the data bit enclosed by the seven regions of the Venn diagram.
```             7  6  5  4  3  2  1
[  1  0  0  1  0  1  1  ] ⇐ D7
G = [  0  1  0  1  0  1  0  ] ⇐ D6
[  0  0  1  1  0  0  1  ] ⇐ D5
[  0  0  0  0  1  1  1  ] ⇐ D3
```

The product C = M × G, accomplishes the codeword generation, given only the four input bits M.

```      C = M × G = [ D7 D6 D5 D7+D6+D5 D3 D7+D6+D3 D7+D5+D3 ] = [ D7 D6 D5 P4 D3 P2 P1 ]
```

A received codeword can be checked by confirming the EVEN parity of the bits found within each circle of the Venn diagran. Define a (3 × 7) matrix H called the check matrix in which each row reflects the composition of the three parity check bits.

```            D7 D6 D5 P4 D3 P2 P1
[  1  1  1  1  0  0  0  ] ⇐ P4
H = [  1  1  0  0  1  1  0  ] ⇐ P2
[  1  0  1  0  1  0  1  ] ⇐ P1
```

Observe that the product P = HGT returns a zero matrix (3 × 4), where GT is the transpose of H.

And the matrix product S = HCT equals a zero matrix (3 × 1) for any valid codeword C, as shown below.

```          ---------- H ------------     --CT--
[  1  1  1  1  0  0  0  ]     [ D7 ]      [ D7 + D6 + D5 + P4 ]     [ 0 ]
S =   [  1  1  0  0  1  1  0  ]  x  [ D6 ]   =  [ D7 + D6 + D3 + P2 ]  =  [ 0 ]
[  1  0  1  0  1  0  1  ]     [ D5 ]      [ D7 + D5 + D3 + P1 ]     [ 0 ]
[ P4 ]
[ D3 ]
[ P2 ]
[ P1 ]
```
The zero result indicates no errors, since the modulus 2 addition effects a parity check on the bits defined in each row. The result (S) is called the syndrome. For example, given the valid codeword C = [ 1 0 1 0 0 1 0 ],
```          ---------- H -----------     --CT--
[  1  1  1  1  0  0  0 ]     [ 1  ]      [ 1 + 0 + 1 + 0 + 0 + 0 + 0 ]     [ 0 ]
S =   [  1  1  0  0  1  1  0 ]  x  [ 0  ]   =  [ 1 + 0 + 0 + 0 + 0 + 1 + 0 ]  =  [ 0 ]
[  1  0  1  0  1  0  1 ]     [ 1  ]      [ 1 + 0 + 1 + 0 + 0 + 0 + 0 ]     [ 0 ]
[ 0  ]
[ 0  ]
[ 1  ]
[ 0  ]
```

The Arrival of Errors

The presence of error(s) can be modeled by an error vector such as E = [ 0 1 0 0 0 0 0 ] where the sum B = E + C describes the bit error(s) added to the codeword. For the E shown, the resulting word B would have a single bit error compared to the original codeword C. In polyomial form, the expression E(x)=xN compactly describes a single bit error.

For example, given the codeword C = [ 1 0 1 0 0 1 0 ], then B = C + E = [ 1 1 1 0 0 1 0 ] where a single bit is made incorrect. Of course, when checking this word for errors it it is not known where the bad bit is located, or even if there are any bad bits.

To check for errors, simply compute the product HBT, but first observe the details of this operation:

```   S = HBT = H(E + C)T = H(ET + CT) =  HET + HCT = HET
```
Since the term HCT = 0 by definition.

In conclusion, the syndrome (S) depends only on the error for whatever valid codeword is transmitted.

It is sufficient to examine the error vector E to study the error control aspects of this coding approach.

The Detection of Errors

Single Bit Errors

Let E = [ 0 1 0 0 0 0 0 ], then:

```          ---------- H -----------     --ET--
[  1  1  1  1  0  0  0 ]     [ 0  ]      [ 1 ]
S =   [  1  1  0  0  1  1  0 ]  x  [ 1  ]   =  [ 1 ]
[  1  0  1  0  1  0  1 ]     [ 0  ]      [ 0 ]
[ 0  ]
[ 0  ]
[ 0  ]
[ 0  ]
```

The non-zero syndrome indicates that an error has occurred. The single bit error syndrome matches the column location of the bad bit. Correction is trivial. Note that no two columns in H have the same value and any single bit error can be corrected in this way.

Two-Bit Errors

Let E = [ 0 1 0 1 0 0 0 ], then:

```          ---------- H -----------     --ET--
[  1  1  1  1  0  0  0 ]     [ 0  ]      [ 1 + 1 ]     [ 0 ]
S =   [  1  1  0  0  1  1  0 ]  x  [ 1  ]   =  [ 1 + 0 ]  =  [ 1 ]
[  1  0  1  0  1  0  1 ]     [ 0  ]      [ 0 + 0 ]     [ 0 ]
[ 1  ]
[ 0  ]
[ 0  ]
[ 0  ]
```

The non-zero syndrome indicates that some error has occurred. The error is not correctable as other pairs of errors (or a single bit error) could lead to this same result. Observe that the resulting syndrome is the sum of the syndromes for each single bit error. Any two-bit error is guaranteed to be detected since no two columns in H would add to give zero (the columns would have to be identical).

Multi-Bit Errors

A non-zero syndrome indicates that an error has occurred. A multi-bit error is not correctable as other combinations of errors could lead to this same result. In every case, the resulting syndrome is the sum of the syndromes for each single bit error. Unfortunately, some of these sums will equal zero and the errors will go undetected.

A Systematic Code

Before moving to a more general method of error control using matrices, consider the Hamming code with the bits rearranged such that the parity bits appear separately from the data bits. To this end, the columns of the check matrix may be rearranged as shown below. None of the above error control arguments is affected by this change; however, matrix operations will now replace the Venn diagrams completely.

Specifically, in the new check matrix H, the leftmost columns form a (3 × 3) identity matrix.

```             4  2  1  6  3  7  5
[  1  0  0  1  0  1  1 ]
H = [  0  1  0  1  1  1  0 ]
[  0  0  1  0  1  1  1 ]
```

Similarly, in the new generating matrix G the rightmost columns form a (4 × 4) identity matrix; consequently, the input data bits emerge unchanged and grouped together (after the parity bits).

```          [  1  1  0  1  0  0  0 ]
G = [  0  1  1  0  1  0  0 ]
[  1  1  1  0  0  1  0 ]
[  1  0  1  0  0  0  1 ]
```

Reading across the first three bits in each row reveals the four 3-bit terms (6,3,7,5) from the rightmost columns of the generating matrix; converting between G and H is easily accomplished.

Example: Let the four message bits be M = [ 0 1 0 1 ], then the codeword C = iG as:

```                           [  1  1  0  1  0  0  0 ]
C = MG = [0 1 0 1] x [  0  1  1  0  1  0  0 ]  = [1 1 0 0 1 0 1]
[  1  1  1  0  0  1  0 ]
[  1  0  1  0  0  0  1 ]
```

A generator matrix of this form ensures the arrangement of codeword bits separated from parity bits defining a systematic block code.

To confirm that this is a valid codeword, use the check matrix as HCT to obtain a zero result.

 With the MATLAB Communications Toolbox the generating matrix (G) and the check matrix (H) for an (n,k) Hamming Code can be found using [H,G] = hammgen(M), where M is the number of parity bits, then n = 2M-1, and k = n - M. >> [H,G] = hammgen(3) returns the two matrices shown above.

Conclusions

The Hamming code concepts can be described in matrix form, where a generating matrix (G) creates valid codewords from information bits, and a check matrix (H) computes syndromes for error checking.

When a valid codeword is multiplied by the check matrix, the result (syndrome) is zero. Any non-zero syndrome indicates a bit error. It has been shown that this syndrome depends entirely on an error vector E(x). Each column in the check matrix is different, meaning that all single bit errors of the form E(x)=xN in a codeword produce a unique syndrome and no two-bit errors can produce a zero syndrome. This implies that all single bit errors can be corrected or that all two-bit errors can be detected.

The matrix approach supercedes the description of the (7,4) Hamming code as overlapping parity circles and leads instead to the development of more powerful error control codes.

The systematic generation of codewords with predictable properties is explored with the online Error Control Code from Galois Fields

 Sun May 19 02:49:21 ADT 2013 Last Updated: 30 JAN 2011 Richard Tervo [ tervo@unb.ca ] Back to the course homepage...