Hamming code with solved problems

Hamming Code is one of the most widely used error detection and correction codes in digital communication and computer networks. It detects and corrects single-bit errors during binary data transmission by adding redundant bits, also called parity bits, to the original data. It was originally invented by Richard W. Hamming in the year 1950. The Hamming code algorithm improves communication reliability while requiring only a small amount of additional data.

The redundant bits are the extra bits that are placed at certain locations of the data bits to detect the error. At the receiver end, the code is decoded to detect errors and the original message is received.

So before transmitting, the sender has to encode the message with the redundant bits. It involves three steps, as described below.

Encoding the message with hamming code

Selecting the number of redundant bits

The first step in hamming code encoding is determining the number of redundant bits required for reliable error detection and correction. The hamming code algorithm uses these redundant bits to detect and correct single-bit errors during binary data transmission.

The number of redundant bits depends on the number of information (data) bits in the message. The minimum number of redundant bits required is calculated using the hamming code formula.

Let n be the number of information or data bits, then the number of redundant bits P is determined from the following hamming code formula,

In this way, the number of redundant bits is determined for the number of information bits to be transmitted before performing hamming code encoding.

Choosing the location of redundant bits

Once the required number of parity bits has been calculated, the next step in the hamming code algorithm is placing the redundant bits in the correct positions.

For the above example, the number of data bits n=4, and the number of redundant bits P=3. So the message consists of 7 bits in total that are to be coded. Let the rightmost bit be designated as bit 1, the next successive bit as bit 2 and so on.

The seven bits are bit 7, bit 6, bit 5, bit 4, bit 3, bit 2, bit 1.

In this, the redundant bits are placed at the positions that are numbered corresponding to the power of 2, i.e., 1, 2, 4, 8,… Thus the locations of data bit and redundant bit are D4, D3, D2, P3, D1, P2, P1.

Placing the parity bits in these fixed locations allows the Hamming code decoder to quickly identify the position of an erroneous bit during error detection and correction.

Assigning the values to redundant bits

Now the next step in hamming code encoding is to assign bit value to the redundant bits in the formed hamming code group. The assigned bits are called a parity bit.

Each parity bit will check certain other bits in the total code group, whether it contains an even or odd number of 1s. Depending on the communication system, either even parity or odd parity is used.

The bit location table is drawn as shown below.

Parity bit P1 covers all data bits in positions whose binary representation has 1 in the least significant position(001, 011, 101, 111, etc.). Thus P1 checks the bit in locations 1, 3, 5, 7, 9, 11, etc..

Parity bit P2 covers all data bits in positions whose binary representation has 1 in the second least significant position(010, 011, 110, 111, etc.). Thus P2 checks the bit in locations 2, 3, 6, 7, etc.

Parity bit P3 covers all data bits in positions whose binary representation has 1 in the third least significant position(100, 101, 110, 111, etc.). Thus P3 checks the bit in locations 4, 5, 6, 7, etc.

Each parity bit checks the corresponding bit locations and assign the bit value as 1 or 0, so as to make the number of 1s as even for even parity and odd for odd parity.

This parity checking process is the foundation of the hamming code algorithm and enables efficient single-bit error correction.

How to detect and correct the error in the hamming code?

After receiving the encoded message, each parity bit along with its corresponding group of bits are checked for proper parity. While checking, the correct result of individual parity is marked as 0 and the wrong result is marked as 1.

After checking all the parity bits, a binary word called syndrome is formed taking the result bits for P1 as LSB. So formed binary word gives the bit location, where there is an error.

If the formed binary word is 0000, then there is no error in the message. This process allows hamming code decoding to accurately detect and correct any single-bit error without retransmitting the message.