Syndrome Decoding
Decode by the syndrome: cosets, coset leaders, and the parity-check matrix.
The idea
Syndrome decoding is the standard decoding procedure for linear codes: instead of comparing a received word against every codeword, compute one short vector — the syndrome — and look up the error it names.
A decoder must recover, from the received word $r$, the codeword most likely sent. On a channel that corrupts symbols independently and rarely, that is the codeword closest to $r$, and comparing $r$ against all $2^{k}$ codewords of a dimension-$k$ code finds it — at a cost that grows exponentially in $k$.
For a linear code with parity-check matrix $H$, the syndrome of $r$ is $s = r\,H^{\top}$, a vector of length $n - k$. Write $r = c + e$, where $c$ is the codeword sent and $e$ is the error pattern the channel added — the vector with a nonzero entry in each corrupted position. Every codeword satisfies $c\,H^{\top} = 0$, so $s = (c + e)\,H^{\top} = c\,H^{\top} + e\,H^{\top} = e\,H^{\top}.$ The syndrome depends only on the error pattern, not on which codeword was sent.
Grouping words by their syndrome therefore partitions the whole space into cosets, one per syndrome value, and the error patterns that could have produced $r$ are exactly the members of the coset its syndrome names. The most likely of them is the member of smallest weight, called the coset leader. The decoder is then:
Algorithm.
Algorithm: Syndrome Decoding Input: a received word r, the parity-check matrix H of an (n, k) linear code Output: the decoded codeword 1. in advance, tabulate the coset leader of each of the 2^(n-k) syndrome values // leader = the minimum-weight error pattern with that syndrome 2. s = r Hᵀ 3. if s = 0, return r // r is already a codeword 4. e = the coset leader tabulated for s 5. return r - e // binary field: flip the bits of r where e is nonzero
Step 1 is done once per code; after that, decoding a word costs one matrix product and one lookup.
Ways to work on it
- Walkthrough. Correct transmission errors by reading a received word's syndrome.
- Practice. Read a Hamming syndrome and name the bit to correct.
- Hardest. Decode a received word corrupted in more than one bit.
Not sure where to start? Take the ten-question placement test.