Elegance of Hamming Codes
In 202108162031_how-do-hamming-codes-work, we went over how hamming codes can be used to detect and correct single error messages or detect (but not correct) the presences of two or more errors in a message. However, while the implementation may have seemed complicated, it is actually very elegant and simple.
If the parity checks passing/failing is denoted as zero or one, it literally spells out the position of the error in binary. For example if the parity check failed (a.k.a is odd) for all but the last one, then the position is 0111b, or bit#7. The following description explains why this happens.
Assume the same 16-bit message as the last article, except with each index represented in binary instead:
[ 0000 **0001** **0010** 0011]
[ **0100** 0101 0110 0111]
[ **1000** 1001 1010 1011]
[ 1100 1101 1110 1111]
When checking if the even columns pass parity, what we are really checking is this question:
“If there is an error, is the last bit of its position index a 1?”. This is because the positions in these two columns all have the last bit equal to one. Similarly the other parity checks follow through for the other bits of the error position. This is the reason for the parity bits being places where they are. At those position indices, the only a single bit is “on”.
A note on XOR
The XOR operation in binary is essentially “add mod 2”. This is also equivalent to a parity check as XOR returns one for an odd number of ones and zero for an even number of ones.
Hamming code using XOR
Each column/row being checked can be XORed with each other to get the parity check. So the way to do all four parity checks at once, is to take the positions of all the ones in the message and XOR them together to get the position of the error. Each bit in a position index is denoting what parity group it is part of.
For example, if bit#3 and bit#15, part of the last column are ones, then we XOR 0011 and 1111 resulting in 1100. This means if these were the only ones in the message, parity group “1” and “2”, or even columns and the last two columns have parity of zero, the rows checks have odd parity.
Python Implementation
If bits is a numpy array of zeros and ones.
from functools import reduce
import numpy as np
import operator
bits = np.random.randint(0, 2, 16)
parity = reduce(operator.xor, [i for i, bit in enumerate(bits) if bit])
# Set parity bits
if (parity & 0b1000):
bits[parity & 0b1000] = not bits[parity & 0b1000]
if (parity & 0b0100):
bits[parity & 0b0100] = not bits[parity & 0b0100]
if (parity & 0b0010):
bits[parity & 0b0010] = not bits[parity & 0b0010]
if (parity & 0b0001):
bits[parity & 0b0001] = not bits[parity & 0b0001]
# Parity will now be zero
assert(reduce(operator.xor, [i for i, bit in enumerate(bits) if bit])==0)
# Add error
bits[10] = not bits[10]
assert(reduce(operator.xor, [i for i, bit in enumerate(bits) if bit])==10)
Practical Usage
Hamming codes offer single error correction with only log(N) bits for an N-bit message block. Message blocks may be overlapping to make this more robust against burst errors. Block size selected by balancing efficiency vs risk of errors.
References