Hamming Code

Hamming Code

The basic example of a linear code is the Hamming code. It has many remarkable properties. Its only drawback is that its distance equals three, meaning it corrects only one error. Nevertheless, it is based on a beautiful combinatorial construction. Understanding its properties is key to understanding more complex codes. To illustrate the properties, we use a toy example with \(n=7\), then discuss why these properties hold in general.

The parity-check matrix of the Hamming code \(C_{7} \subseteq \{0,1\}^{7}\) consists of all possible nonzero vectors of length 3: \[H_{7}= \begin{pmatrix}0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1\\\end{pmatrix}\] In other words, the set \(C_{7}\) consists of words \(u \in \{0,1\}^{7}\) that satisfy the system of linear equations: \[u_{4} \oplus u_{5} \oplus u_{6} \oplus u_{7} = 0, \quad u_{2} \oplus u_{3} \oplus u_{6} \oplus u_{7}=0, \quad u_{1} \oplus u_{3} \oplus u_{5} \oplus u_{7} = 0 \ .\]

It is easy to see that these three equations (the rows of \(H_{7}\)) are linearly independent: indeed, \(u_{4}\) appears only in the first equation, \(u_{2}\) only in the second, \(u_{1}\) only in the third (so no combination of these rows can sum to zero). It follows that \(|C|=2^{7-3}=2^{4}=16\): informally, each equation reduces the degrees of freedom by one. The code distance equals three: there are no zero columns in the parity-check matrix, any two columns are different (and therefore cannot sum to zero), and one can easily find three linearly dependent columns (any two columns sum to another column in the matrix).

Now we list the remarkable properties of the Hamming code, introducing a few new definitions along the way.

• Perfectness.  A code is called perfect if it meets the Hamming bound. Clearly, the code \(C_{7}\) has this property: balls of radius one centered at codewords of \(C_{7}\) optimally pack the space \(\{0,1\}^{7}\).


• Systematic form.  A code is called systematic if encoding is done by appending some information to the original message. The bits of the original message are called information bits, and the appended bits are check bits. More formally, an \((n,k,\cdot)\)-code \(C\) is systematic if there exists an encoding \(\phi \colon \{0,1\}^{k} \to C\) and coordinates \(1 \le i_{1} \le \dotsb \le i_{k} \le n\), such that for any message \(m \in \{0,1\}^{k}\), the projection of its codeword on these coordinates equals \(m\): \(\phi(m)|_{i_1, \dotsc, i_k}=m\).
  Clearly, the code \(C_{7}\) is systematic. Encoding can be done as follows. Denote the message by \((u_{3}, u_{5}, u_{6}, u_{7})\) (this numbering will be convenient for decoding). For any such message we can uniquely find the bits \(u_{1}, u_{2}, u_{4}\): \[u_{4} = u_{5} \oplus u_{6} \oplus u_{7}, \quad u_{2} = u_{3} \oplus u_{6} \oplus u_{7}, \quad u_{1} = u_{3} \oplus u_{5} \oplus u_{7} \ .\] Thus, the encoding is: \[\phi(u_{3}, u_{5}, u_{6}, u_{7}) = (u_{3} \oplus u_{5} \oplus u_{7}, u_{3} \oplus u_{6} \oplus u_{7}, u_{3}, u_{5} \oplus u_{6} \oplus u_{7}, u_{5}, u_{6}, u_{7}) \ .\]
  In fact, any linear code is systematic. One can express one variable from each parity-check equation, substitute it into the others, and so on.


• Simple encoding.  This is essentially described in the previous point: the encoding is as simple and efficient as possible.


• Simple decoding.  Decoding is not only simple and efficient but also elegant. Given a word \(v \in \{0,1\}^{7}\) differing from a codeword in at most one bit, compute the syndrome \(s=H_{7}v\): if \(s=\mathbf{0}\), there is no error; otherwise, \(s\) is the binary representation of the erroneous bit!
  Example: suppose we receive \(v \in \{0,1\}^{7}\) with \(s=(0,1,1)^{T}\). Then \(s\) is the binary representation of three. Take \(e=(0,0,1,0,0,0,0)\), where the 1 is at position three. Clearly, \(H_{7}e=s\). Therefore, \[H_{7}(v \oplus e)=H_{7}v \oplus H_{7}e=s \oplus s = \mathbf{0}\ ,\] meaning \(v \oplus e\) is the original codeword.

from itertools import product


def syndrome(u):
    return ((u[3] + u[4] + u[5] + u[6]) % 2,
            (u[1] + u[2] + u[5] + u[6]) % 2,
            (u[0] + u[2] + u[4] + u[6]) % 2)


def is_code_word(u):
    return syndrome(u) == (0, 0, 0)


def min_non_zero_weight(code):
    return min(sum(u) for u in code if sum(u) > 0)


def encode(m):
    return ((m[0] + m[1] + m[3]) % 2,
            (m[0] + m[2] + m[3]) % 2,
            m[0],
            (m[1] + m[2] + m[3]) % 2,
            m[1],
            m[2],
            m[3])


def decode(v):
    s = syndrome(v)
    if s == (0, 0, 0):
        return v

    i = s[2] + 2 * s[1] + 4 * s[0]
    u = list(v)
    u[i - 1] = (u[i - 1] + 1) % 2
    return u


hamming_code = [u for u in product(range(2), repeat=7) if is_code_word(u)]
print('Length of Hamming code:', len(hamming_code))
print('Minimum non-zero weight:', min_non_zero_weight(hamming_code))
print('Encode (1, 0, 1, 0):', encode((1, 0, 1, 0)))

for word in ((1, 0, 1, 1, 0, 1, 0), (1, 0, 1, 0, 0, 1, 0), (1, 1, 1, 1, 0, 1, 0)):
    print(f'Decode {word}: {decode(word)}')

Length of Hamming code: 16
Minimum non-zero weight: 3
Encode (1, 0, 1, 0): (1, 0, 1, 1, 0, 1, 0)
Decode (1, 0, 1, 1, 0, 1, 0): (1, 0, 1, 1, 0, 1, 0)
Decode (1, 0, 1, 0, 0, 1, 0): [1, 0, 1, 1, 0, 1, 0]
Decode (1, 1, 1, 1, 0, 1, 0): [1, 0, 1, 1, 0, 1, 0]

Now, for the general case. For \(n=2^{t}-1\), the Hamming code is constructed the same way and has all the same properties. In this case, \(H_{n}\) contains all distinct nonzero columns of height \(t=\log_{2}(n+1)\). Then \(|C_{n}|=2^{n-t}=\frac{2^n}{n+1}\). Hence, \(|C_{n}|\) balls of radius one (each containing \(n+1\) points of \(\{0,1\}^{n}\)) fill \(\{0,1\}^{n}\) completely, so the code is perfect. As any linear code, \(C_{n}\) is systematic: the check bits are conveniently chosen as those at positions with binary representation having exactly one 1. Thus, encoding a message of length \(n-t\) appends \(t\) checksums. In decoding, the syndrome is still the binary representation of the erroneous bit.

For \(2^{t-1}\le n < 2^{t}-1\), the Hamming code is no longer perfect (here, \(H_{n}\) has \(n\) columns of height \(t\), corresponding to numbers from 1 to \(n\)), but no other code can be perfect for distance three: for that, \(2^{n}\) must be divisible by \(n+1\). This means some points of \(\{0,1\}^{n}\) will be at distance greater than one from any codeword. In such words the error cannot be corrected, but it is not required. All other properties remain: the code is still systematic, simply encoded, and simply decoded (for \(e \in \{0,1\}^{n}\), \(||e||=1\), we must have \(H_{n}e=s\); if \(H_{n}\) has no column equal to \(s\), the received message cannot be decoded).