Hamming codes explained — parity bits, syndrome, and error correction



In one sentence: A Hamming code adds parity bits at power-of-two positions so the binary syndrome points directly at the flipped bit — correcting any single error in the block.

Keywords: Hamming code, error-correction code, digital communication, data storage, reliable transmission, computer memory systems, satellite communication systems, single-bit error, two-bit errors.

What is a Hamming Code

Hamming codes are a class of error-correcting codes that are commonly employed in digital communication and data storage systems to detect and correct errors that may occur during transmission or storage. They were created by Richard Hamming in the 1950s and bear his name.

The central concept of Hamming codes is to introduce additional (redundant) bits to a message in order to enable the identification and correction of errors. By appending parity bits to the original message, Hamming codes can identify and correct single-bit errors.

A binary Hamming code has minimum distance 3. Used as a bounded-distance decoder it corrects any single-bit error. Used purely as a detector, a nonzero syndrome flags any pattern of one or two errors. It cannot do both at once. The code is perfect: the radius-1 spheres around the codewords fill the space, so a double error always lands in some other codeword’s sphere and is miscorrected if the decoder insists on producing a codeword. Memory systems that must correct one error and still detect a double error add an overall parity bit. That extended Hamming code has distance 4 and is the SECDED code used in ECC RAM.

Technical details of Hamming code

Linear binary Hamming code falls under the category of linear block codes that can correct single bit errors. For every integer p ≥ 3 (the number of parity bits), there is a (2^p-1, 2^p-p-1) Hamming code. Here, 2^p-1 is the number of symbols in the encoded codeword and 2^p-p-1 is the number of information symbols the encoder can accept at a time. All such Hamming codes have a minimum Hamming distance d_min=3 and thus they can correct any single bit error and detect any two bit errors in the received vector. The characteristics of a generic (n,k) Hamming code is given below.

\[\begin{aligned} \text{Codeword length:} \quad && n &= 2^p-1 \\ \text{Number of information symbols:} \quad && k &= 2^p-p-1 \\ \text{Number of parity symbols:} \quad && n-k &= p \\ \text{Minimum distance:} \quad && d_{min} &= 3 \\ \text{Error correcting capability:} \quad && t &=1 \end{aligned}\]

With the simplest configuration: p=3, we get the most basic (7, 4) binary Hamming code. The (7,4) binary Hamming block encoder accepts blocks of 4-bit of information, adds 3 parity bits to each such block and produces 7-bits wide Hamming coded blocks.

Systematic & Non-systematic encoding

Block codes like Hamming codes are also classified into two categories that differ in terms of structure of the encoder output:

● Systematic encoding
● Non-systematic encoding

In systematic encoding, just by seeing the output of an encoder, we can separate the data and the redundant
bits (also called parity bits). In the non-systematic encoding, the redundant bits and data bits are interspersed.

Constructing (7,4) Hamming code

Hamming codes can be implemented in systematic or non-systematic form. A systematic linear block code can be converted to non-systematic form by elementary matrix transformations. A non-systematic Hamming code is described next.

Let a codeword belonging to (7, 4) Hamming code be represented by [D₇,D₆,D₅,P₄,D₃,P₂,P₁], where D represents information bits and P represents parity bits at respective bit positions. The subscripts indicate the left to right position taken by the data and the parity bits. We note that the parity bits are located at position that are powers of two (bit positions 1,2,4).

Now, represent the bit positions in binary.

Seeing from left to right, the first parity bit (P₁) covers the bits at positions whose binary representation has 1 at the least significant bit. We find that P₁ covers the following bit positions

\[\begin{aligned} \text{bit position in decimal} &: \text{in binary} \\ 1 &: 00 \textbf{1} \\ 3 &: 01 \textbf{1}\\ 5 &: 10 \textbf{1} \\ 7 &: 11 \textbf{1} \end{aligned} \]

Similarly, the second parity bit (P₂) covers the bits at positions whose binary representation has 1 at the second least significant bit. Hence, P₂ covers the following bit positions.

\[\begin{aligned} \text{bit position in decimal} &: \text{in binary} \\ 2 &: 0 \textbf{1} 0 \\ 3 &: 0 \textbf{1} 1 \\ 6 &: 1 \textbf{1} 0 \\ 7 &: 1 \textbf{1} 1 \end{aligned} \]

Finally, the third parity bit (P₄) covers the bits at positions whose binary representation has 1 at the most significant bit. Hence, P₄ covers the following bit positions

\[\begin{aligned} \text{bit position in decimal} &: \text{in binary} \\ 4 &: \textbf{1} 00 \\ 5 &: \textbf{1} 01 \\ 6 &: \textbf{1} 10 \\ 7 &: \textbf{1} 11 \end{aligned} \]

If we follow even parity scheme for parity bits, the number of 1’s covered by the parity bits must add up to an even number. Which implies that the XOR of bits covered by the parity (including the parity bits) must result in 0. Therefore, the following equations hold.

\[\begin{aligned} P_1 &= D_3 \oplus D_5 \oplus D_7 \\ P_2 &= D_3 \oplus D_6 \oplus D_7 \\ P_4 &= D_5 \oplus D_6 \oplus D_7 \end{aligned}\]

For clarity, let’s represent the subscripts in binary.

\[\begin{aligned} P_{00 \textbf{1}} &= D_{01 \textbf{1}} \oplus D_{10 \textbf{1}} \oplus D_{11 \textbf{1}} \\ P_{0 \textbf{1} 0} &= D_{0 \textbf{1} 1} \oplus D_{1 \textbf{1} 0} \oplus D_{1 \textbf{1} 1} \\ P_{\textbf{1} 00} &= D_{\textbf{1} 01} \oplus D_{\textbf{1} 10} \oplus D_{\textbf{1} 11} \end{aligned}\]

Following table illustrates the concept of constructing the Hamming code as described by R.W Hamming in his groundbreaking paper [1].

We note that the parity bits and data columns are interspersed. This is an example of non-systematic Hamming code structure. We can continue our work on the table above as it is. Or, we can also re-arrange the entries of that table using elemental transformations, such that a systematic Hamming code is rendered.

After the re-arrangement of columns, we see that the parity columns are nicely clubbed together at the end. We can also drop the subscripts given to the parity/data locations and re-index them according to our convenience. This gives the following structure to the (7,4) Hamming code.

We will use the above systematic structure in the following discussion.

Encoding process

Given the structure in Figure 3, the parity bits are calculated from the following linearly independent equations using modulo-2 additions.

\[\begin{aligned} P_1 &= D_1 \oplus D_2 \oplus D_3 \\ P_2 &= D_2 \oplus D_3 \oplus D_4 \\ P_3 &= D_1 \oplus D_3 \oplus D_4 \end{aligned} \]

At the transmitter side, a Hamming encoder implements a generator matrix -$latex \mathbf{G}$. It is easier to construct the generator matrix from the linear equations listed in equation above. The linear equations show that the information bit D₁ influences the calculation of parities at P₁ and P₃ . Similarly, the information bit D₂ influences P₁ and P₂, D₃ influences P₁, P₂ & P₃ and D₄ influences P₂ & P₃.

With the columns ordered$latex D_1, D_2, D_3, D_4, P_1, P_2, P_3$, the generator matrix is

\[\mathbf{G}=\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix}\]

Represented as matrix operations, the encoder accepts 4 bit message block$latex \mathbf{m}$, multiplies it with the generator matrix$latex \mathbf{G}$ and generates 7 bit codewords$latex \mathbf{c}$. Note that all the operations (addition, multiplication etc.,) are in modulo-2 domain.

\[\mathbf{c}= \mathbf{m} \mathbf{G} \]

Given a generator matrix, the Matlab code snippet for generating a codebook containing all possible codewords ($latex \mathbf{c} \in \mathbf{C}$) is given below. The resulting codebook$latex \mathbf{C}$ can be used as a Look-Up-Table (LUT) when implementing the encoder. This implementation will avoid repeated multiplication of the input blocks and the generator matrix. The list of all possible codewords for the generator matrix ($latex \mathbf{G}$) given above are listed in table 2.

Program: Generating all possible codewords from Generator matrix

bitget is used below so the listing stays inside base MATLAB. The Communications Toolbox function de2bi produces the same message matrix.

% Systematic (7,4) Hamming code: codebook and one single-error correction
G = [1 0 0 0 1 0 1;
     0 1 0 0 1 1 0;
     0 0 1 0 1 1 1;
     0 0 0 1 0 1 1];
H = [1 1 1 0 1 0 0;
     0 1 1 1 0 1 0;
     1 0 1 1 0 0 1];

k = 4;
m = zeros(2^k, k);
for i = 0:2^k-1
    m(i+1, :) = bitget(i, k:-1:1);   % left-msb
end
codebook = mod(m * G, 2);

c = codebook(6, :);
r = c;
r(3) = 1 - r(3);                      % flip the third bit
s = mod(r * H.', 2);
errLoc = find(all(bsxfun(@eq, H, s.'), 1));
corrected = r;
corrected(errLoc) = 1 - corrected(errLoc);
disp(corrected)
disp(all(corrected == c))

The same encoder and syndrome decoder in Python. A syndrome of all zeros means a codeword. Any other syndrome of a single-error pattern equals one column of$latex \mathbf{H}$, and that column index is the flipped bit. A syndrome that matches no column is not a single-bit error. On this perfect code that case does not arise: every nonzero syndrome is some column, which is why a double error is quietly miscorrected.

import numpy as np

G = np.array([
    [1, 0, 0, 0, 1, 0, 1],
    [0, 1, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 1, 1, 1],
    [0, 0, 0, 1, 0, 1, 1],
], dtype=int)
H = np.array([
    [1, 1, 1, 0, 1, 0, 0],
    [0, 1, 1, 1, 0, 1, 0],
    [1, 0, 1, 1, 0, 0, 1],
], dtype=int)

def encode(message):
    return (np.asarray(message, dtype=int) @ G) % 2

def syndrome(received):
    return (np.asarray(received, dtype=int) @ H.T) % 2

def decode(received):
    received = np.array(received, dtype=int, copy=True)
    s = syndrome(received)
    if not np.any(s):
        return received, None
    for index in range(H.shape[1]):
        if np.array_equal(H[:, index], s):
            received[index] ^= 1
            return received, index
    return received, -1

message = np.array([1, 0, 1, 1])
codeword = encode(message)
received = codeword.copy()
received[2] ^= 1
corrected, location = decode(received)
print("codeword ", codeword.tolist())
print("received ", received.tolist(), " flipped bit", location)
print("corrected", corrected.tolist(), " matches", np.array_equal(corrected, codeword))

Decoding process – Syndrome decoding

The three check equations for the given generator matrix ($latex \mathbf{G}$) for the sample (7,4) Hamming code, can be expressed collectively as a parity check matrix -$latex \mathbf{H}$. Parity check matrix finds its usefulness in the receiver side for error-detection and error-correction.

The matching parity-check matrix, with the same column order, is

\[\mathbf{H}=\begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}\]

According to parity-check theorem, for every generator matrix G, there exists a parity-check matrix H, that spans the null-space of G. Therefore, if c is a valid codeword, then it will be orthogonal to each row of H.

\[\mathbf{c} \mathbf{H}^T = 0 \]

Therefore, if$latex \mathbf{H}$ is the parity-check matrix for a codebook$latex \mathbf{C}$, then a vector$latex \mathbf{c}$ in the received code space is a valid codeword if and only if it satisfies$latex \mathbf{c} \mathbf{H}^T=0$.

Consider a vector of received word$latex \mathbf{r}=\mathbf{c}+\mathbf{e}$, where$latex \mathbf{c}$ is a valid codeword transmitted and$latex \mathbf{e}$ is the error introduced by the channel. The matrix product$latex \mathbf{r}\mathbf{H}^T$ is defined as the syndrome for the received vector$latex \mathbf{r}$, which can be thought of as a linear transformation whose null space is$latex \mathbf{C}$ [2].

\[\begin{aligned} \mathbf{s} &= \mathbf{r}\mathbf{H}^T \\ &=\left(\mathbf{c}+\mathbf{e}\right)\mathbf{H}^T \\ &=\mathbf{c}\mathbf{H}^T +\mathbf{e}\mathbf{H}^T \\ &=\mathbf{0} +\mathbf{e}\mathbf{H}^T \\ &=\mathbf{e}\mathbf{H}^T \end{aligned}\]

Thus, the syndrome is independent of the transmitted codeword$latex \mathbf{c}$ and is solely a function of the error pattern$latex \mathbf{e}$. It can be determined that if two error vectors$latex \mathbf{e}$ and$latex \mathbf{e}’$ have the same syndrome, then the error vectors must differ by a nonzero codeword.

\[\begin{aligned} \mathbf{s} &= \mathbf{e}\mathbf{H}^T = \mathbf{e}’\mathbf{H}^T \\ & \Rightarrow \left(\mathbf{e} – \mathbf{e}’\right)\mathbf{H}^T = 0 \\ & \Rightarrow \left(\mathbf{e} – \mathbf{e}’\right) = \mathbf{c} \in \mathbf{C} \end{aligned}\]

It follows from the equation above, that decoding can be performed by computing the syndrome of the received word, finding the corresponding error pattern and subtracting (equivalent to addition in$latex GF(2)$ domain) the error pattern from the received word. This obviates the need to store all the vectors as in a standard array decoding and greatly reduces the memory requirements for implementing the decoder.

Following is the syndrome table for the (7,4) Hamming code example, illustrated here.

Some properties of generator and parity-check matrices

The generator matrix$latex \mathbf{G}$ and the parity-check matrix$latex \mathbf{H}$ satisfy the following property

\[\mathbf{G} \mathbf{H}^T = 0\]

Note that the generator matrix is in standard form where the elements are partitioned as

\[\mathbf{G} = \begin{bmatrix} I_k \mid P \end{bmatrix} \]

where I_k is a k × k identity matrix and P is of dimension k ⨉ (n-k). When G is a standard form matrix, the corresponding parity-check matrix H can be easily determined as

\[\mathbf{H} =[−P^T∣I_{n−k}]\]

Over GF(2) every element is its own additive inverse, because$latex 1+1=0$. The minus sign in$latex -P^{T}$ therefore drops out, and the parity-check matrix of a binary code in systematic form is

\[\mathbf{H} = [P^T \; | \; I_{n-k}]\]

References

[1] R.W Hamming, “Error detecting and error correcting codes”, Bell System Technical Journal. 29 (2): 147–160, 1950.↗
[2] Stephen B. Wicker, “Error Control Systems for digital communication storage”, Prentice Hall, ISBN 0132008092, 1995.

FAQ

What errors can the classic (7,4) Hamming code correct? It corrects any single-bit error in a 7-bit codeword (4 data bits + 3 parity bits). A double error produces a nonzero syndrome that points at the wrong bit, so naive correction can make things worse — extended Hamming or CRC layers are used when double-error detection matters.

What is the syndrome and how does decoding use it? The syndrome is the parity-check outcome packed as a binary integer. A zero syndrome means “no error detected”; a nonzero value is the index of the bit to flip in the textbook Hamming decoder — that is the elegant property that makes Hamming famous in classrooms.

Does Hamming decoding use hard bits or soft reliabilities? The classic algorithm flips hard 0/1 bits. Soft-decision and ML decoding can squeeze more coding gain from the same parity structure by using channel LLRs — see the hard-vs-soft and maximum-likelihood decoding articles linked below.

Similar articles

• Hard and soft decision decoding
• Maximum-likelihood decoding
• Channel capacity