How does channel coding work using hamming codes?

In telecommunication and information theory, channel coding, also known as forward error correction (FEC), is a system of error control for data transmission, whereby the sender systematically adds redundant data to its messages, also known as an error-correcting code (ECC). The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first FEC code, the Hamming (7,4) code, in 1950.1

As a showing example in a communication between two nodes, e.g. two computers, it can happen that the data get corrupted which means that one bit flips from 0 to 1 or from 1 to 0 due to electromagnetic fields or other physical disturbances. Channel encodings like the hamming code help us to avoid data loss or retransmissions due to transmission errors which occured on the way from the sender to the receiver and give the receptor the possibility to correct faulty bits directly as they arrive.

Beside the hamming algorithm there are other encodings of which some will be discussed in other articles coming at a later time. In this article you will learn how to calculate the redundancy bits using the hamming algorithm and how one-bit errors are detected and corrected. The howto is divided into three sections, the first describes how the hamming code is generated, the second briefly describes the transmission and the third is about detecting and correcting bit errors.

1. Generating the hamming code

Initial packets

First of all we need to create two packets, one for the data bits and one for the hamming code which will be calculated in the next steps. If we wanted to send the ASCII code 57 (which represents the character ’9′) to a receiver we would initialize a 8-bit long data packet with ones and zeros as follows.

Then we have to create an empty hamming code packet with the length of the data packet plus the amount of the required parity bits which is \max(\{x: 2^x \le data\_length + x\})+1. In other words the amount of parity bits depends on the length of the data packet.

data packet length ≤ amount of parity bits
1 2
4 3
11 4
26 5
57 6

In our example the data packet has 8 bits, thus we need 4 parity bits. The hamming code will thus have a length of 12 bits.

Merge the data packet into the empty hamming code packet

To know what data bit is copied to what bit position in the hamming code we must know where the parity bits have to be placed to. For hamming codes their positions are always a power of 2, which means that the first parity bit is bit 2^0=1, the second is bit 2^1=2, the third is bit 2^2=4 and so on. These fields, colored red in the following picture, are reserved for the parity purpose and mustn’t be used for data bits.

Then the data bits are copied to the other non-reserved positions in the same order as they appear in the original data packet.

Calculating the parity bits

The general hamming code algorithm can be described as follows:

What bit positions of the hamming code are to be considered for the calculation of the corresponding parity bit depends on its position. So for each parity bit, we consider the bit set which is obtained as follows:

  • The first parity bit position is 1. Starting from this position we consider 1 bit, skip 1, consider 1 again etc. The set consists of the bits 1, 3, 5, 7, 9, …
  • The second parity bit position is 2. Starting from this position we consider 2 bits, skip 2, consider 2 again etc. The set consists of the bits 2-3, 6-7, 10-11, …
  • The third parity bit position is 4. Starting from this position we consider 4 bits, skip 4, consider 4 again etc. The set consists of the bits 4–7, 12–15, 20–23, …
  • The fourth parity bit position is 8. Starting from this position we consider 8 bits, skip 8, consider 8 again etc. The set consists of the bits 8–15, 24–31, 40–47, …

A parity bit is calculated by counting all the bits of a set which are equal to one. For the hamming code a parity bit is 1 if the amount of the counted ones is odd 0 else.

As we include the red fields which are the parity bit positions, we assume that their values are 0.

First parity bit

We consider the bit position set {1, 3, 5, 7, 9, …} and count the ones at these positions. As a result we count an even amount of ones so the parity bit p1 is 0.

Second parity bit

We consider the bit position set {2-3, 6-7, 10-11, …} and count the ones at these positions. As a result we count an even amount of ones so p2 is 0.

Third parity bit

We consider the bit position set {4–7, 12–15, 20–23, …} and count the ones at these positions. As a result we count an odd amount of ones so p3 is 1.

Fourth parity bit

We consider the bit position set {8–15, 24–31, 40–47, …} and count the ones at these positions. As a result we count an even amount of ones so p4 is 0.

The final hamming code


2. Transmission

In a communication between two nodes, e.g. two computers, it can happen that the data get corrupted which means that one bit flips from 0 to 1 or from 1 to 0 due to electromagnetic fields or other physical disturbances. The following picture shows how the fifth bit of the hamming code and thus the second data bit flipped its value.

If there was no redundancy added to the data bits the receiver would have got a corrupted data packet which looks like this:

In decimal the content of the packet changed from 57 to 121 and this now represents the ASCII code for the character ‘y’. Because reduntancy was added this bit error can be detected and corrected as the next section describes.

3. Detecting and correcting

To find out if the transmission was error-free the parity bits must be recalculated by the receiver. By doing this the receiver resets all the parity bits to 0 and does the same calculation as the sender did as described in the first section. The result is the regenerated hamming code:

Compared to the received hamming code we see that the parity bits p1 and p4 have changed and thus an error was detected.

Now we calculate the sum of the positions of the changed parity bits which is 5 in this example. This is the position of the bad bit of the received hamming code which can be corrected now. After extracting the data bits of the corrected hamming code the original data packet is obtained:

Further notices:

  • It doesn’t matter if a parity bit or a data bit flips. If one of the recalculated parity bits differs from the received hamming code packet the data bits are ok.
  • If more than one of the recalculated parity bits differ, the data bits are not ok.
  • Each data bit is considered by at least two parity bits.

6 Comments

  1. slopjong

    I’ve noticed many visits yesterday, it seems that this post is somehow useful for others. If there is something unclear or you have other questions, just ask.

    I’ve already improved the howto but I haven’t adapted this post yet.

  2. sajib

    hello,
    Nice tutorials, appreciate it.
    What if there are two bits in the data flips? Is it possible to correct both of the bits that were changed?

  3. slopjong

    This tutorial is about the Hamming (7,4) and according Wikipedia the answer is no.

    The Hamming (7,4) and similar Hamming codes cannot distinguish between single-bit errors and two-bit errors. That is, two-bit errors appear the same as one-bit errors. If error correction is performed on a two-bit error the result will be incorrect.

    However it is possible to correct a two bits error if an additional parity bit is used. I have to do some research on how the algorithm explained above has to be adapted.

    As soon as I’ve got some spare time I’m trying to find it out what I’ll be blogging then.

  4. ashok

    How many redundant bits are to be sent for correcting a 32 bit unit using hamming code.

  5. slopjong

    You need 6. Here is how you come to that number:
    First build the set of numbers (x) which fulfill the given condition.
    $latex {x: 2^x \le data\_length + x\}$
    This means you start with x=0, check the condition, then set it to 1, check the condition again and so forth. You stop by the first number where the condition is not fulfilled and exclude that one of course.

    With the max function you take the biggest number to which you add 1.

    $latex max({x_1, x_2, …}) + 1$

  6. alx

    i have a question if i have to send 8 bit is there any way that i can find at least 2 errors?, it doesn’t matter if i can’t correct both.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>