Hamming Code: Error Detection & Correction

The Limits of Simple Parity

The simplest form of error detection is adding a single parity bit to a data word. For example, in an even parity scheme, the parity bit is set to 0 or 1 to make the total number of 1s in the entire word (data + parity) even.

• Data: 1011001 (four 1s - already even) -> Parity bit is 0. Transmitted word: 1011001**0**.
• Data: 1100011 (five 1s - odd) -> Parity bit is 1. Transmitted word: 1100011**1**.

If the receiver gets a word with an odd number of 1s, it knows a single-bit error occurred. However, it doesn't know which bit flipped, so it can't correct the error. Furthermore, if two bits flip, the parity remains even, and the error goes completely undetected. We need a more robust system.

Hamming Distance and Error Correction

The power of an error-correcting code lies in the "distance" between valid code words. This is formalized as the Hamming distance, which is simply the number of bit positions in which two binary words of the same length differ.

• 1011 and 10**0**1 have a Hamming distance of 1.
• 0**1**1**0** and 0**0**1**1** have a Hamming distance of 2.

To correct errors, we need to choose our valid code words to be far apart. If a single-bit error occurs, the corrupted word will still be "closer" to the original correct word than to any other valid word.

As you've read, a code with a minimum Hamming distance of 3 between any two valid code words can detect and correct any single-bit error. This is the foundation of the standard Hamming code.

Constructing a Hamming Code (Encoding)

Richard Hamming's insight was to use multiple, overlapping parity bits. Each parity bit checks a different subset of the data bits. When an error occurs, the pattern of "failed" parity checks (called the syndrome) uniquely identifies the position of the faulty bit.

How Many Parity Bits are Needed?

Let's say we have $m$ data bits and we add $k$ parity bits. The total length of the code word is $n=m+k$. These $k$ parity bits must be able to identify which of the $n$ positions is in error, plus one more state for "no error". So, the $k$ bits must be able to represent at least $n+1$ different states. This gives us the fundamental relationship for Hamming codes:

Since $n=m+k$, we can rewrite this as:

This formula tells you the minimum number of parity bits ($k$) required for a given number of data bits ($m$). For example, if you have 4 data bits ($m=4$), you'll find that you need $k=3$ parity bits, because $2^3\ge 4+3+1⟹8\ge 8$. This results in the common (7,4) Hamming code (7 total bits, 4 data bits).

The following video explains this relationship clearly.

The Encoding Process

The standard procedure for creating a Hamming code is as follows:

1. Position the Parity Bits: Number the bit positions starting from 1. The parity bits ($P_1,P_2,P_4,\dots$) are placed in positions that are powers of two (1, 2, 4, 8, etc.). The data bits ($D_3,D_5,D_6,\dots$) fill the remaining slots.

2. Determine Parity Groups: Each parity bit is responsible for checking a unique set of positions (including its own). The rule is:

   • $P_1$ checks all bit positions whose binary representation has a 1 in the least significant bit (positions 1, 3, 5, 7, 9, 11, ...).
   • $P_2$ checks all bit positions whose binary representation has a 1 in the second bit position (positions 2, 3, 6, 7, 10, 11, ...).
   • $P_4$ checks all bit positions whose binary representation has a 1 in the third bit position (positions 4, 5, 6, 7, 12, ...).
   • And so on.

3. Calculate Parity Bit Values: For each parity group, calculate the value of the parity bit to satisfy the chosen parity scheme (typically even parity). This is done by taking the XOR of all the data bits in that group.

The next video segment will walk you through this entire encoding process for a (7,4) code.

Detecting and Correcting an Error (Decoding)

Now for the most powerful part. When a receiver gets a Hamming-coded word, it performs the following steps:

1. Recalculate Parity: The receiver re-calculates the parity for each group, this time including the received parity bit in the check. For each group, it computes a check bit ($C_1,C_2,C_4,\dots$). If the parity is correct (e.g., it's even for an even parity system), the check bit is 0. If the parity is incorrect, the check bit is 1.

2. Form the Syndrome: The check bits, ordered from highest to lowest ($C_4,C_2,C_1$), form a binary number called the syndrome.

3. Locate the Error: The decimal value of the syndrome is the exact position of the bit that is in error!

   • If the syndrome is 000, there is no error.
   • If the syndrome is 101 (decimal 5), then bit 5 is wrong.

4. Correct the Error: To correct the error, simply flip the bit at the identified position.

The following video provides a perfect, concise demonstration of this decoding and correction process.

The image below provides a great static summary of this process. It shows a received 11-bit code, the four parity checks being performed, the resulting syndrome 0111, and how this value (decimal 7) correctly points to the bit in position 7 as the error.

A Complete Worked Example: (12,8) Hamming Code

Let's apply these principles to a slightly larger example. We want to transmit the 8-bit data word 10011101.

1. Determine Parameters:

• Data bits $m=8$.
• Using $2^k\ge m+k+1$, we need to find $k$.
  • If $k=3$, $2^3\ge 8+3+1⟹8\ge 12$ (False).
  • If $k=4$, $2^4\ge 8+4+1⟹16\ge 13$ (True).
• So we need $k=4$ parity bits. The total code word will have $n=m+k=8+4=12$ bits. This is a (12,8) Hamming code. The parity bits will be $P_1,P_2,P_4,P_8$.

2. Encoding:

• First, lay out the 12 positions, placing the data bits (MSB to LSB) in the non-power-of-two slots.

  • Positions: 12 11 10 9 8 7 6 5 4 3 2 1
  • Type: D D D D P8 D D D P4 D P2 P1
  • Data: 1 0 0 1 1 1 0 1

• Now, calculate the parity bits for even parity (XOR of the data bits in each group):

  • P1 (checks 3, 5, 7, 9, 11): $D_3\oplus D_5\oplus D_7\oplus D_9\oplus D_{11}=1\oplus 0\oplus 1\oplus 1\oplus 0=1$. So, $P_1=1$.
  • P2 (checks 3, 6, 7, 10, 11): $D_3\oplus D_6\oplus D_7\oplus D_{10}\oplus D_{11}=1\oplus 1\oplus 1\oplus 0\oplus 0=1$. So, $P_2=1$.
  • P4 (checks 5, 6, 7, 12): $D_5\oplus D_6\oplus D_7\oplus D_{12}=0\oplus 1\oplus 1\oplus 1=1$. So, $P_4=1$.
  • P8 (checks 9, 10, 11, 12): $D_9\oplus D_{10}\oplus D_{11}\oplus D_{12}=1\oplus 0\oplus 0\oplus 1=0$. So, $P_8=0$.

• The final transmitted code word is:

  • Pos: 12 11 10 9 8 7 6 5 4 3 2 1
  • Bit: 1 0 0 1 0 1 1 0 1 1 1 1

3. Decoding with an Error:

• Suppose during transmission, bit 6 flips. The received word is:
  • Pos: 12 11 10 9 8 7 6 5 4 3 2 1
  • Bit: 1 0 0 1 0 1 0 0 1 1 1 1
• The receiver calculates the check bits (syndrome):
  • C1 (checks 1, 3, 5, 7, 9, 11): $1\oplus 1\oplus 0\oplus 1\oplus 1\oplus 0=0$. (Parity is even, OK). $C_1=0$.
  • C2 (checks 2, 3, 6, 7, 10, 11): $1\oplus 1\oplus 0\oplus 1\oplus 0\oplus 0=1$. (Parity is odd, FAIL). $C_2=1$.
  • C4 (checks 4, 5, 6, 7, 12): $1\oplus 0\oplus 0\oplus 1\oplus 1=1$. (Parity is odd, FAIL). $C_4=1$.
  • C8 (checks 8, 9, 10, 11, 12): $0\oplus 1\oplus 0\oplus 0\oplus 1=0$. (Parity is even, OK). $C_8=0$.
• The syndrome word is $C_8{C}_4{C}_2{C}_1=0110$.
• The decimal value of 0110 is 6. The error is in bit position 6.
• The receiver flips bit 6 from 0 back to 1, perfectly restoring the original code word.

Practice Problem

Now it's your turn. A (7,4) Hamming code is generated using even parity. The 4-bit data word to be sent is 1101.

1. Generate the 7-bit Hamming code that should be transmitted.
2. Suppose that after transmission, the receiver gets the word 0111101. Calculate the syndrome to find the error, and state the corrected 7-bit code word.

Conclusion

This lesson concludes our first module on number systems and codes. You've now seen how binary data can be structured for arithmetic (2's complement), for interfacing (BCD), for preventing transitional errors (Gray code), and now for ensuring data integrity (Hamming code).

Here are the key takeaways from our study of Hamming codes:

• Simple parity can detect single-bit errors but cannot correct them.
• Hamming codes increase the Hamming distance between valid code words, allowing for both detection and correction. A minimum distance of 3 allows for single-bit error correction.
• The encoding process involves adding $k$ parity bits at power-of-two positions, where $2^k\ge m+k+1$.
• The decoding process involves calculating a syndrome whose binary value directly points to the position of the single erroneous bit.

With this foundation, we are ready to move from representing data to manipulating it. In our next module, we will dive into Boolean Algebra, the mathematical language that governs the behavior of all logic gates and forms the bedrock of digital circuit design.