Welcome!

August 2022 Hamming codes

Below is an example of the $(7,4)$ Hamming code. The bits $s₁s₂s₃s₄$ are the source bits, and the bits $t₅t₆t₇$ are the parity bits. The parity bits are set such that the parity of the bits within each circle is even (zero since each bit can be either $1$ or $0$). The transmitted codeword can be represented by the matrix $𝐭=\begin{bmatrix} s₁&s₂&s₃&s₄ &t₅&t₆&t₇\end{bmatrix}^⊺$.

We have

$$\begin{align*} s_1 \oplus s_3 \oplus s_4 \oplus t_7 = 0,& \\ s_1 \oplus s_2 \oplus s_3 \oplus t_5 = 0,&\text{ and }\\ s_2 \oplus s_3 \oplus s_4 \oplus t_6 = 0,& \\ \end{align*}$$

where $\oplus$ is addition modulo $2$. Then $s_1 \oplus s_3 \oplus s_4 = t_7$ and so on. In matrix form this is expressed as

$$𝐭=𝐆^T𝐬 =\begin{bmatrix} 𝐈_4 \\ 𝐏 \end{bmatrix}𝐬, \quad\text{ with } 𝐏=\begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix}.$$

Decoding is then the reverse process. The syndrome is given by $$𝐇𝐭=\begin{bmatrix}𝐏 & 𝐈_3 \end{bmatrix}𝐭.$$

Assuming each of $t_5t_6t_7$ has not been flipped, the syndrome identifies which bit of $s_1s_2s_3s_4$ should be flipped to make the parity even again. For example, if the syndrome is $\begin{bmatrix}1 & 1 & 0\end{bmatrix}^T$, then the syndromes involving $s_1s_2s_3t_5$ and $s_2s_3s_4t_5$ have odd parity. Flipping either $s_2$ or $s_3$ would make these syndroms even parity, but flipping $s_3$ would affect the other syndrome, so $s_2$ is flipped.

Some code that implements a $(7,4)$ Hamming encoder/decoder is given below.

P = [1 1 1 0; 0 1 1 1; 1 0 1 1]
I₄ = [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1]
I₃ = [1 0 0; 0 1 0; 0 0 1]

encode(s::Vector{T}) where {T} = vcat(I₄, P)*s .% 2

decode(t::Vector{T}) where {T} = begin
    syndrome = hcat(P, I₃)*t .% 2
    if syndrome == [1;0;1]
        t = (t + [1; 0; 0; 0; 0;0;0]) .% 2
    elseif syndrome == [1;1;0]
        t = (t + [0; 1; 0; 0; 0;0;0]) .% 2
    elseif syndrome == [1;1;1]
        t = (t + [0; 0; 1; 0; 0;0;0]) .% 2
    elseif syndrome == [0;1;1]
        t = (t + [0; 0; 0; 1; 0;0;0]) .% 2
    end
    return t[1:4]
end

@test encode([0;1;0;0]) == [0;1;0;0;1;1;0]
@test decode([0;1;0;0;1;1;0]) == [0;1;0;0]
@test decode([0;1;1;0;1;1;0]) == [0;1;0;0]

Encoding a picture of an owl, adding some noise with probability $0.1$, and decoding the picture again gives the following result.