What is Hamming code for?

Hamming code is a linear error-correcting code. Name comes from the inventor last name Richard Hamming. The code is used in communication. It can detect and correct one bit error, moreover two bit errors can be detected but unhappily not corrected. So in single frame there can occur zero or one bit error to ensure reliable transmission. Number of odd bits between sender and receiver message is known as Hamming Distance. To perform Hamming code original message must be concatenated with redundant Hamming code bits.

How Hamming coding algorithm works

Sender site:

  1. Get message and convert it to binary string
  2. Create H matrix
  3. Compute redundant Hamming bits
  4. Concatenate message and Hamming bits
  5. Send frame

Receiver site:

  1. Receive frame
  2. Divide frame to message and code bits
  3. Generate H matrix
  4. Compute Hamming bits from message
  5. Perform XOR operation between received and computed Hamming bits
  6. If XOR result is all zero binary
    • Message have no errors
  7. Else
    1. Generate H matrix with identity
    2. Perform on matrix columns XOR operation with previous XOR result
    3. If some result is all zero bit
      1. The column number is faulty bit position
      2. Change frame bit on founded position to opposite
      3. Compute Hamming bits for frame message part
      4. If corrected frame Hamming bits equals computed Hamming bits
        • Message is corrected
      5. Else
        • There is more then one bit error cannot correct
    4. Else
      • There is more then one bit error cannot correct

Hamming algorithm sections

In this section is shown how specific parts of algorithm works.

Get message and convert it to binary string

Get message and convert it to binary representation. In our program we have to prepare binary single-handedly.

Binary message;
#if !DEBUG
    Console.WriteLine("Enter message in binary representation:");
    string rawMessage = Console.ReadLine();
    message = new Binary(rawMessage.Select(c => c == '1' ? true : false));
#else
    message = new Binary(new[] {true,false,true,false,true,false});
#endif

Create H matrix

To create Hamming redundant bits firstly we have to create H matrix. This matrix is also used in receiver context. What is important the matrix in both sites sender and receiver must be the same. To create matrix firstly we have find matrix dimension size.

int columnsAmount = message.Count();
int rowsAmount = (int) Math.Ceiling(Math.Log(columnsAmount, 2) + 1);

Then we have to incrementally generate binary values of every integer. The values that have more then 2 bits set to ’1′ are inserted to matrix as column.

BinaryMatrix H = new BinaryMatrix(rowsAmount, columnsAmount);

int n = 0;
for (int i = 1; i <= Math.Pow(2, rowsAmount); i++)
{
    Binary binary = new Binary(i, H.RowAmount);
    if (binary.CountOnes() >= 2)
    {
        for (int y = 0; y < rowsAmount; y++)
        {
            H.Set(y, n, binary[y]);
        }
        n++;
    }
    if (n >= H.ColumnAmount)
        break;
}
return H;

Compute redundant Hamming bits

To generate verification bits every H matrix row have to be performed logical AND with message. Then if the single result have even number of ’1′ bits the single verification bit is ’1′ else ’0′. Concatenation of every single result is a Hamming redundant bit.

Binary verification = new Binary(new bool[H.RowAmount]);
for (int i = 0; i < H.RowAmount; i++)
{
    Binary row = H.GetRow(i);
    Binary addiction = row & message;
    bool verificationBit = addiction.CountOnes()%2 == 1 ? true : false;
    verification[i] = verificationBit;
}
return verification;

Concatenate message and Hamming bits

To create a whole frame the message and redundant bits must be concatenated.

Binary frame = Binary.Concatenate(message, verification);

 

public static Binary Concatenate ( Binary a, Binary b)
{
    Binary result = new Binary(new bool[a.Length+b.Length]);
    int n = 0;
    foreach (bool bit in a)
    {
        result[n] = bit;
        n++;
    }
    foreach (bool bit in b)
    {
        result[n] = bit;
        n++;
    }
    return result;
}

Send frame

In final state the frame is send to receiver.

Receive frame

The frame is received.

Divide frame to message and code bits

Firstly the frame have to be divided to message and Hamming code (verification) bits.

Binary receivedMessage = new Binary(receivedFrame.Take(columnsAmount));
Binary receivedVerification = new Binary(receivedFrame.Skip(columnsAmount));

Generate H matrix

The H matrix is generated in the same way as in sender context.

H = GenerateHMatrix(rowsAmount, columnsAmount);

Compute Hamming bits from message

For received message there must be computed verification bits as in previous section they are generated in the same way as in receiver context.

Binary receivedMessageVerification = GenerateVerificationBits(H, receivedMessage);

Perform XOR operation between received and computed Hamming bits

In this step there is required to check if the generated verification bits are equal to received frame verification bits. The fastest operation that can handle that is XOR. So there is why this operation is used.

Binary s = receivedVerification ^ receivedMessageVerification;

If XOR result is all zero binary

If the XOR result have all zeros that tells us there is no error in frame.

if(s.CountOnes()>0)
{
    [...]
}
else
{
    Console.WriteLine("The received frame is correct");
}

Else

Else there is one or more errors in received frame.

Generate H matrix with identity

To check error in message part of frame we need just H matrix, but the error can also be in the verification bits. Ability to find error bit in whole frame gives us a concatenated H with Identity matrix. Beneath there is a code that creates that matrix:

static BinaryMatrix GenerateHWithIdentity(BinaryMatrix H)
{
    BinaryMatrix HWithIdentity = new BinaryMatrix(H.RowAmount, H.ColumnAmount + H.RowAmount);
    for (int y = 0; y < H.RowAmount; y++)
    {
        for (int x = 0; x < H.ColumnAmount; x++)
        {
            HWithIdentity.Set(y, x, H.Get(y, x));
        }
    }

    for (int y = 0; y < H.RowAmount; y++)
    {
        int n = 0;
        for (int x = H.ColumnAmount; x < H.ColumnAmount + H.RowAmount; x++)
        {
            HWithIdentity.Set(y, x, y == n);

            n++;
        }
    }
    return HWithIdentity;
}

Finding faulty bit

  • Perform on matrix columns XOR operation with previous XOR result
  • If some result is all zero bit
  • The column number is faulty bit position
private static int FindFaultyBit(BinaryMatrix H, Binary s)
{
    for (int i = 0; i < H.ColumnAmount; i++)
    {
        Binary column = H.GetColumn(i);
        Binary check = s ^ column;
        if(check.Any(b=>b))
            continue;
        return i;
    }

    throw new WarningException("Faulty bit not found!");
}

Change frame bit on founded position to opposite

Binary correctedFrame = new Binary(receivedFrame.ToArray());
correctedFrame[faultyBitPosition] = !correctedFrame[faultyBitPosition];

Download Solution: Hamming C# Code