Hamming code

Hamming code: An error-detecting and binary error correcting code, used in data transmission, that can (a) detect all single- and double-bit errors and (b) correct all single-bit errors. Note: A Hamming code satisfies the relation 2^m ≥ n + 1, where n is the total number of bits in the block, k is the number of information bits in the block, and m is the number of check bits in the block, where m = n-k.

See also parity code for some more information.

(Adapted from the Telecomm Glossary 2k at http://www.its.bldrdoc.gov/projects/t1glossary2000/_hamming_code.html)

The set of Hamming codes are called 'Forward Error Correction' and give the ability for the receiving station to correct a transmission error. While this takes more bits to send the information, it means fewer retransmits and thus can actually speed up a noisy connection.

The number of parity bits in the hamming code is given by the Hamming rule. This is a function of the number of bits of information transmitted in a block and is represented by the following inequality:
d + p + 1>= 2^p
'd' is the number of data bits and 'p' is the number of parity bits. Hamming codes are identified by the ordered set (c,d) where 'c' = 'd' + 'p'. The Hamming code (7,4) is the classic example used which describes a word of 4 data bits long and 3 error check bits. This satisfies the above inequality:
4 + 3 + 1 >= 2³

The hamming code word is created by multiplying the data bits by a generator matrix using modulo-2 arithmetic. The result of this is called a code word vector which consists of the original data bits and the parity bits.

The generator matrix used in constructing the hamming code consists of I (the identity matrix) and a parity generation matrix A. For a data size of 4 the following matrix is created:

         I        A
      1 0 0 0 | 1 1 1
      0 1 0 0 | 0 1 1
G =   0 0 1 0 | 1 0 1
      0 0 0 1 | 1 1 0

Multiplying a 4 bit vector (d1, d2, d3, d4) by G results in a 7 bit vector of the form (d1, d2, d3, d4, p1, p2, p3). The A portion is what generates the parity bits. If the selection of the columns of A are unique, it is true that (p1, p2, p3) is the parity calculations of three distinct subsets of the original data.

To validate the code word, it is necessary to multiply the data word by 'H' which is the [inverse A | I] check to form the parity check vector.

          H           r |1|    s
                        |0|
| 1 0 1 1 | 1 0 0 |     |0|   |0|
| 1 1 0 1 | 0 1 0 |  *  |1| = |0|
| 1 1 1 0 | 0 0 1 |     |0|   |0|
                        |0|
H*r=s                   |1|

If all the elements of s are 0, then the entire set has been received correctly. If there are any '1's in s, then there is an error which can be determined by looking at the parity pits that have failed.

If r = [1011001] s will be [101] This matches the third colum of 'H' which corresponds to the bit that has the error.

The (7,4) Hamming code, while good for demonstrations is not the best choice for practical communications - it has allot of overhead and has a non-standard length. The number of parity bits goes up with the log of the number of data bits. Hence, there is less overhead for longer words than shorter words.

The hamming code can detect and fix single bit errors, and detect double bit errors. For the (7,4) hamming code, the following table (error correcting bits are in bold):

decimal binary Hamming(7,4)
   0     0000   0000000
   1     0001   0001110
   2     0010   0010101
   3     0011   0011011
   4     0100   0100011
   5     0101   0100011
   6     0110   0110110
   7     0111   0111000
   8     1000   1000111
   9     1001   1001001
  10     1010   1010010
  11     1011   1011100
  12     1100   1100100
  13     1101   1101010
  14     1110   1110001
  15     1111   1111111

The hamming distance from one valid error correcting set to another for the same data is three. This means that it would take three errors to go from one valid message to another. Example:

Sent message:
    0101010
First error:
    0100010 (not valid - correctable)
Second error:
    0100000 (not valid - not correctable)
Third error:
    0000000 (valid)

It is left an excercise to the reader to demonstrate this is the case for all 127 possible cases that the minimum hamming distance between any two valid messages is three.

This node brought to you by Node Your Homework....and the letter V.

The following code is written for execution via MatLab, and is now intended to be supplemental to the descriptions of Hamming codes already found in this node. It is generally a proof/simulation of the Hamming (7,4) code. The (7,4) incarnation of hamming error correction/detection codes is composed of four data bits and three error check bits. This code calculates BER (bit error rate), and compares to BSC (Binary symmetric channel) efficiency. BSC is simply a single channel capacity and it's corresponding error probability and efficiency. If the probability of error on a channel is 50%, the channel has a capacity of 0 (useless). This is due to the fact that 0 and 1 are equally likely in binary number systems. Capacity is full at error probability of 0% or 100% (inverted).

So the following code is meant as a proof and simulation of Hamming (7,4) code. Its usefulness comes from the resulting two graphs. There is a standard plot of Hamming vs. BSC, and then a log*log plot that shows a better representation of the data comparison (decibels). To run this code, save it into a file, name it "name".m, and move it to the home directoy of any version of MatLab. Then simply type "name" in the MatLab console, and it should all make sense. You can adjust coding variables and table size directly in the program as it is adequately commented. I hope this helps anyone who may be taking classes in digital communications. I think Hamming (7,4) is pretty popular in digital communications courses.

Sources: Ziemer and Peterson: Introduction to Digital Communication, Second Edition. Prentice Hall, 2001.

---

% Jordan Rice
% ELEC 476 (Random Signals and Noise)
% Hamming (7,4) Code Simulation 


%Defining Variables for Hamming (7,4) simulation

k = 4;		                % Number of message bits per block
n = 7;		                % Number of codeword bits per block
p_vector = 0.1:0.01:1;          % Vector of p values; probability of bit error for BSC
N = length(p_vector);           % Length of p_vector
RUNS = 5000;                    % Number of runs


% Codeword Table

xtable =    [0 0 0 0 0 0 0; ...
             1 1 0 1 0 0 0; ...
             0 1 1 0 1 0 0; ...
             1 0 1 1 1 0 0; ...
             1 1 1 0 0 1 0; ...
             0 0 1 1 0 1 0; ...
             1 0 0 0 1 1 0; ...
             0 1 0 1 1 1 0; ...
             1 0 1 0 0 0 1; ...
             0 1 1 1 0 0 1; ...
             1 1 0 0 1 0 1; ...
             0 0 0 1 1 0 1; ...
             0 1 0 0 0 1 1; ...
             1 0 0 1 0 1 1; ...
             0 0 1 0 1 1 1; ...
             1 1 1 1 1 1 1;];

     
for (p_i=1:N)
    
    error = 0;                    % Count the number of errors
    p=p_vector(p_i);
    
    for (r=1:RUNS)           %Generate a block of 4 message bits

        
    z = unifrnd(0, 1, 1, 4);    %Random 4 bit string of 0's and 1's
    w = round(z);               %Round the value of z

        
%Locate the row index, binary to dec. conversion:

    m = w(1) + w(2)*2 + w(3)*4 + w(4)*8;
    x = xtable(m + 1, :);
    z = unifrnd(0, 1, 1, 7);    % Random 7 bit string of 0's and 1's
    zi = find(z <= p);          % Error locations

% Error Vector

    e = zeros(1,7);             % Creates a 7 bit string of 0's
    e(zi) = ones(size(zi));     % Creates a string of 1's the size of z
    y = xor(x,e);               % Exclusive OR your x value and e value 
    
% Approximate the code word

        for(q=1:16)    
        dH(q) = sum(xor(y, xtable(q,:)));   % Compare codeword to received vector
            
            if(dH(q)<=1)      
            wh = xtable(q, 4:7); % wh matches with distance of 1 or less
            end
        end

% Count the number of Errors
        dHw = sum(xor(w,wh));
        error = error + dHw;
    end
    BER(p_i) = error/(RUNS*4);    % Calculate the Bit Error Rate
    P(p_i)=p;                   % Store the value of p 
end



Ps=logspace(-4,0,200);
Pb_high = 1 - ((1-Ps).^7 + 7.*(1-Ps).^6.*Ps);    
Pb_low = (1 - ((1-Ps).^7 + 7.*(1-Ps).^6.*Ps))/k;    



figure(1)
plot(P, BER, 'bx', Ps, Pb_high, 'k-', Ps, Pb_low, 'k-')
legend('Simulated','Analytical')
xlabel('Probability of Error for BSC (p)')
ylabel('BER')
title('Figure 1 - Bit Error Rate for Hamming code over BSC')


figure(2)
loglog(P, BER, 'bx', Ps, Pb_high, 'k-', Ps, Pb_low, 'k-')
legend('Simulated','Analytical')
xlabel('Probability of Error for  BSC (p)')
ylabel('BER')
title('Figure 2 - Bit Error Rate for Hamming code over BSC')