Hamming Codes

A ECC that is able to detect 2-bit errors and fix 1-bit errors. Uses parity bits and parity circles to determine where errors occur.

Notation

$Hamming(A,B)$

• Encodes $B$-input bits into $A$-output bits
• Adds extra parity $A-B$ parity bits Theoretically, for $k$ parity bits, you can have $2^k-k-1$ data bits

Process (Hamming (7,4))

Sending Process

1. Create your message, then encode with a hamming encoding algorithm (Maybe Hamming (7,4))
2. For Hamming (7,4), we have the encoding matrix:

1 & 0 & 0 & 0\ 0 & 1 & 0 & 0\ 0 & 0 & 1 & 0\ 0 & 0 & 0 & 1\ 0 & 1 & 1 & 1\ 1 & 0 & 1 & 1\ 1 & 1 & 0 & 1\ \end{array}\right]$$ 3. Then, with our message, lets say $v=(1,0,1,0)$, encoded is $Gv$ 4. In our case, $Gv=(1,0,1,0,1,0,1)$

Recieving Process

1. Given the message, calculate the sum of each circle for the recieved message by left multiplying vector
2. $H=[L_1^T,L_2^T,L_3^T,L_4^T,L_5^T,L_6^T,L_7^T]=[c_1,c_2,c_3{]}^T$ where:
   • $c_i$ is the parity of each $i-th$ circle
   • $L_i$ is the location of each bit in the circles
3. Bob calculates $H(v)$ to get $(c_1,c_2,c_3)$
4. If $(c_1,c_2,c_3)$ contains non-zero entries, then there is an error
   1. If one error occured, then the error $e_i$ is precisely at location $L_i=(c_1,c_2,c_3)$
      1. If $1\le i\le 4$ (one of the message bits was ruined) then $(x_1,x_2,x_3,x_4{)}^T+e_i$ would be the corrected message
      2. If $i>4$ (one of the parity bits was ruined), then we can just ignore it
   2. Alternatively, finding through the diagram, the wrong bit, first find the two circles that are invalid, then the wrong bit is at the intersection between the two circles

Concepts

• Hamming Distance
• n-Error Detecting Code
• Hamming (7,4)
• Matrix Representation of Hamming Function
• String Parity