Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 37 ยท Error-correcting Codes

Linear Block Codes and Syndrome Decoding

Understand linear block codes: generator and parity-check matrices, minimum distance, weight enumerators, syndrome tables and the extended Hamming SECDED code in Python.

The Hamming code of the previous lesson is one example of a large family: linear block codes. Almost every code you meet in practice, from CRC to BCH, Reed-Solomon and LDPC, is linear. Linearity makes everything easier: encoding is a matrix product, the set of codewords is a vector space, and the minimum distance is simply the smallest weight of a non-zero codeword.

In this lesson you learn the vocabulary of an (n, k) code, compute minimum distance by brute force, build a general syndrome decoder, and extend Hamming(7,4) into the code used in ECC computer memory.

Definitions

A binary (n, k) linear code is a k-dimensional subspace of the vector space of all n-bit words over GF(2). Equivalently, it is the set of all u G where u runs over the 2^k messages and G is a k ร— n generator matrix whose rows are a basis. Key facts:

  • The sum (XOR) of two codewords is a codeword; the all-zero word is always a codeword.
  • The Hamming weight w(c) is the number of ones in c. The distance between two codewords is the weight of their XOR, which is again a codeword. So d_min = smallest weight of a non-zero codeword.
  • A parity-check matrix H of size (n-k) ร— n satisfies G H^T = 0; a word r is a codeword exactly when its syndrome s = H r^T is zero.
  • The code detects d_min - 1 errors and corrects t = floor((d_min - 1) / 2) errors.

The code's rate is k/n. The goal is large d_min with a high rate; there are bounds on how far you can go: the Singleton bound d_min <= n - k + 1, and the Hamming (sphere-packing) bound 2^k * sum_{i<=t} C(n,i) <= 2^n.

Python Enumerate a code and find its distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The weight distribution (1 word of weight 0, 7 of weight 3, 7 of weight 4, 1 of weight 7) is the code's fingerprint. Its smallest non-zero weight, 3, is d_min.

A general syndrome decoder

For any linear code, errors of the same pattern always give the same syndrome. So you can build a syndrome table: for each possible syndrome, store the coset leader, the lowest-weight error pattern that produces it. Decoding is then three steps: compute the syndrome, look up the most likely error, XOR it away. This is maximum likelihood decoding on a BSC with p < 0.5, because fewer flips are more probable.

Python Build a syndrome table for any code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Hamming(7,4) the 8 syndromes correspond to "no error" plus 7 single-bit errors, so the table is complete with leaders of weight at most 1, which is exactly what perfect means. For the (5,2) code some syndromes only have weight-2 leaders, and those patterns are sometimes corrected wrongly.

The extended Hamming code and SECDED

Add one overall parity bit to Hamming(7,4) and you get the (8,4) extended Hamming code with d_min = 4. It can correct one error and detect two (SECDED: single-error correct, double-error detect). Decoding rule:

Overall parity Hamming syndrome Meaning
even zero no error
odd non-zero single error, correct it
odd zero the overall parity bit itself flipped
even non-zero two errors detected, do not correct

Server memory uses the same idea with (72,64) codes: 64 data bits, 8 check bits.

Python SECDED with the (8,4) extended Hamming code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The minimum weight of the extended code is 4, so no pair of errors can look like a different codeword; the decoder refuses to guess instead.

Where linear codes go next

Linear block codes get stronger as n grows. BCH and Reed-Solomon codes (next lesson) choose H using algebra so that d_min is large and decoding is fast. LDPC codes use a sparse H and iterative decoding, and come within a fraction of a decibel of the Shannon limit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a linear code, how do you find the minimum distance?

    The XOR of two codewords is a codeword, so the distance between any two equals the weight of some non-zero codeword.
  2. 2. What is a coset leader?

    All error patterns with the same syndrome form a coset; the lightest is the most probable and is used for decoding.
  3. 3. What does SECDED stand for in the extended Hamming code?

    With d_min = 4 the extended Hamming code corrects one error and detects two.
  4. 4. How many errors can a linear code with d_min = 5 correct?

    t = floor((5 - 1) / 2) = 2.

Summary

  • A linear (n, k) code is a k-dimensional subspace; encoding is u G.
  • A word is a codeword when its syndrome H r^T is zero.
  • d_min equals the smallest non-zero codeword weight; t = floor((d_min - 1) / 2) errors are correctable.
  • A syndrome table of coset leaders gives maximum-likelihood decoding on a BSC.
  • Adding an overall parity bit to Hamming(7,4) gives the SECDED code used in memory.

Next: Reed-Solomon and Convolutional Codes