The Hamming Code with MATLAB

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 Hamming code may be implemented using matrix methods which are readily accomplished using MATLAB. This page explores the MATLAB Communication Toolbox commands that further facilitate the use of the Hamming code.

The Hamming Code in MATLAB

The generating matrix (G) and the check matrix (H) for an (n,k) Hamming Code are defined given only the number of parity bits (M). Let M be the number of parity bits, then n = 2M-1, and k = n - M. For example, M=3 produces a (7,4) code. 

>> M=3;                % M = the number of parity bits
>> [H,G] = hammgen(M)  % return two matrices for an (n,k) Hamming code

H =
     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

G =
     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1
Given either H or G as above, the other matrix (G or H) can be found with one command: 
>> H = gen2par(G)  % given G, find H

H =
     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1
Using the 4-bit message M = [0 1 0 1] and GF(2) arithmetic, the 7-bit codeword is created using generating matrix (G): 
>> M = gf([0 1 0 1]); % Define a 4-bit message M
>> C = M * G          % Create a 7-bit codeword from the message

C = GF(2) array. 
 
Array elements = 
 
           1           1           0           0           1           0           1
Any codeword C can be checked for errors using the check matrix H to give a 3-bit syndrome. In this case, the above codeword C has no errors. 
>> H * C'  % check for errors (find the syndrome) for the codeword C
 
ans = GF(2) array. 
 
Array elements = 
 
           0           
           0
           0
The minimum Hamming distance between any two codewords from the generating polynomial (G) is found as: 
>> d = gfweight(G)   % expect d=3 for single-bit error correction

d =
     3

Correcting an error involves identifying a row in the syndrome table from the error remainer. Consider the single bit error E(x) and find the corresponding remainer (R) as if E(x) alone was the codeword: 


>> E = [ 0 0 0 1 0 0 0 ];   % E(x) = error pattern
>> R = H * E'               % R(x) = syndrome for the error

R = GF(2) array

Array elements =

          1
          1
          0

The non-zero syndrome (R) signals an error. The corresponding column in the check matrix (H) reveals the specific error leading to the bad codeword (R) and the bad bit can be corrected. While this entire error checking and correction process could be automated, other toolbox functions exist to accomplish the entire task as shown below.

The Hamming Code is a Cyclic Code

Because the Hamming code matrices as found on this page define a cyclic code the same results as above can be found by specifying a 7-bit length and the default primitive polynomial with the cyclic code generator as: 

>> P = gfprimdf(3);        % get the current default primitive polynomial 
>> [H,G] = cyclgen(7,P);   % generate a (7,4) cyclic code = Hamming code
>> disp(G)
     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1
If necessary, the (4x4) identity matrix found on the righthand side of G can be moved to lefthand side of G by rotating each row 4 bits to the left as: 
>> wshift(2,G,[0 -4])

ans =

     1     0     0     0     1     1     0
     0     1     0     0     0     1     1
     0     0     1     0     1     1     1
     0     0     0     1     1     0     1
Rotating the columns in this way does not affect the properties of the code.
Coding and Decoding with the Hamming Code

The Hamming code is expected to correct single bit errors. The encode( ) and decode( ) commands automatically incorporate error correction when used with the Hamming code.

While the encode( ) and decode( ) commands are very versatile, their default parameters define cyclic Hamming codes with binary inputs.

For example, the message [1 0 1 1] from the above examples is coded directly into a (7,4) Hamming code as: 

 
>> M = [1 0 1 1];      % M(x) = four message bits 
>> C = encode(M,7,4)   % C(x) = A (7,4) Hamming codeword

C =

     1     0     0     1     0     1     1
The resulting 7-bit codeword is decoded to reveal the original message as: 

>> decode(C,7,4)       % Decode the (7,4) Hamming codeword

ans=

     1     0     1     1
The decode operation appears trivial when there are no errors as the message can be seen in the last four bits of this systematic codeword; however, the same message bits are returned even if a single bit error is added: 

>> E = [ 0 0 0 1 0 0 0];   % E(x) = a single bit error
>> CC = bitxor(C,E)        % Add the single bit error to the codeword
CC =

     1     0     0     0     0     1     1

>> decode(CC,7,4)           % Decode the errored codeword

ans=

     1     0     1     1
The correct original message bits have been returned despite the presence of a bit error.

Conclusions

The Hamming code can be implemented readily in MATLAB, either by first principles using generator and check matrices (G,H), or by using toolbox commands to code and later decode a message despite the presence of errors.

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