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

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 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 = 2^M-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

>> 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

>> 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 

>> H * C'  % check for errors (find the syndrome) for the codeword C
 
ans = GF(2) array. 
 
Array elements = 
 
           0           
           0
           0

>> 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.

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

>> 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

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

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

ans=

     1     0     1     1

>> 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

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