Back to the on-screen lesson · Print

Syndrome decoding

s = Hr^T = He^T; cosets and coset leaders; single-error correction by matching a column.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to compute the syndrome of a received word, explain why it depends only on the error pattern, describe the cosets of a linear code and their leaders, and perform syndrome decoding by hand, including locating and correcting a single error by matching the syndrome to a column of the parity-check matrix. You will construct the Hamming code for any number of parity bits, state its length, dimension, rate and minimum distance, decode it in one step with the binary column ordering, and prove that it is perfect by counting syndromes against error patterns.

2. Syndrome decoding

Send a codeword $c$; the channel adds an error pattern $e$, a word with $1$s where bits were flipped; receive $r = c + e$. The syndrome $s = Hr^T = Hc^T + He^T = He^T$ depends on $e$ alone. All $2^n$ words split into $2^{n-k}$ cosets $c + \text{code}$, and words in the same coset share a syndrome; the coset leader is the lowest-weight word in the coset, the most likely error with that syndrome on a BSC with $\varepsilon < \tfrac{1}{2}$. Syndrome decoding: compute $s$, look up its coset leader $\hat{e}$ in a table of $2^{n-k}$ entries, output $r + \hat{e}$. This is nearest-codeword decoding with a table exponential in $n - k$ rather than in $k$. For single errors the table is $H$ itself: an error in position $i$ has syndrome equal to column $i$ of $H$, so if $H$ has distinct nonzero columns every single error is located by matching the syndrome to a column. Two errors give the sum of two columns, which for $d = 3$ is nonzero (detected) but may coincide with a third column (miscorrected).

3. The syndrome sees only the error

Send a codeword $c$; the channel adds an error pattern $e$ with a $1$ wherever a bit flipped; you receive $r = c + e$. Now compute the syndrome $$s = Hr^T = Hc^T + He^T = He^T,$$ because $Hc^T = 0$ for every codeword. The syndrome does not depend on which codeword was sent — only on the error. That is the whole idea: a decoder that knows $s$ knows everything the parity checks can tell it about the damage, and nothing about the message.

All $2^n$ words split into $2^{n-k}$ cosets $c + \text{code}$, one per syndrome, and every word in a coset has the same syndrome. The coset leader is the lowest-weight word in the coset — the most likely error with that syndrome, as long as the channel flips each bit with probability under $\tfrac{1}{2}$. So syndrome decoding is three steps: compute $s$, look up its coset leader $\hat{e}$, output $r + \hat{e}$. It is nearest-codeword decoding with a table of $2^{n-k}$ entries instead of a search over $2^k$ codewords — exponential in the redundancy rather than in the message.

For a Hamming code the table is not even needed. Order the columns of $H$ as the binary numbers $1$ to $n$; then the syndrome of a single error at position $i$ is the $i$-th column, which is $i$ in binary. Read the syndrome as a number and you have the position.

4. Solving the practice problems

1. Which position is in error, from a syndrome: read the three bits as a binary number, most significant first — $011$ is $3$, $101$ is $5$, $111$ is $7$.
2. Syndrome and corrected codeword for a received word: XOR the columns of $H$ at the $1$s of the word to get $s$, read $s$ as a position, flip that bit. The table above holds every case the practice draws.
3. How many syndromes for an $[n, k]$ code: $2^{n-k} = 2^r$, and that is also the largest number of error patterns syndrome decoding can correct, counting the zero pattern.
4. Why it works and what is stored: the syndrome depends only on the error, and the decoder stores one coset leader per syndrome.

Common mistakes

• Reading the syndrome bits in the wrong order: with columns ordered as binary $1$ to $n$, the first syndrome bit is the most significant.
• Answering $2^k$ for the number of syndromes: it is $2^{n-k}$, one per coset.
• Flipping the bit and forgetting to check: recompute the syndrome of the corrected word; it must be zero.

5. Correcting one error

1. Hamming $[7, 4]$, received $1000110$: $1$s at positions $1, 5, 6$, syndrome $001 \oplus 101 \oplus 110 = 010 = 2$.

   XOR the binary positions.

2. Flip bit $2$: $1100110$; check $001 \oplus 010 \oplus 101 \oplus 110 = 000$. Decoded.

6. Cosets and leaders

1. The $[5, 2]$ code with $H = [A^T \mid I_3]$ has $2^3 = 8$ cosets. Five of them have a weight-$1$ leader (the single errors), one is the code itself.

2. The remaining two cosets need weight-$2$ leaders: the decoder corrects two particular double errors as well, but not all of them.

   Not a perfect code.

7. Correcting $1111110$

1. The $1$s are at positions $1$ to $6$, so $s$ is the XOR of the columns $001, 010, 011, 100, 101, 110$.

2. Column by column: $001 \oplus 010 = 011$; $\oplus 011 = 000$; $\oplus 100 = 100$; $\oplus 101 = 001$; $\oplus 110 = 111$.

   Pairs that repeat cancel, so the order does not matter.

3. $s = 111 = 7$: flip position $7$, giving $1111111$, whose syndrome is $000$.

8. Counting what a table can hold

1. A $[15, 11]$ code has $r = 4$ redundant bits, so $2^4 = 16$ syndromes.

2. Sixteen coset leaders: the zero pattern and fifteen single errors, one per position.

   $1 + 15 = 16$ exactly, which is what makes the Hamming code perfect.

3. There is no room left for a double error: every syndrome is already spoken for.

9. Your turn: Hamming $[7, 4]$, received $1111110$

1. $1$s at positions $1$ to $6$: $001 \oplus 010 \oplus 011 \oplus 100 \oplus 101 \oplus 110 = 111$.

2. Your turn: work this step out. Its working is at the end of the packet.

   Syndrome $7$: flip bit $7$, giving $1111111$.

10. Guided practice

A Hamming $[7, 4]$ code has $H$ whose column $i$ is the binary representation of $i$ (columns $001, 010, 011, \ldots, 111$). A received word has syndrome $110$. Which position (1-based) is in error?

Computed value: _answer

11. Guided practice

With the same Hamming $[7, 4]$ code (column $i$ of $H$ = binary $i$), the word $1111110$ is received. Give its syndrome and the corrected codeword.

syndrome _s, codeword _c

12. Practice

An $[\,14, 6\,]$ linear code: how many distinct syndromes are there, and hence how many error patterns can syndrome decoding correct at most (counting the zero pattern)?

Computed value: _answer

13. Practice

A Hamming $[7, 4]$ code has $H$ whose column $i$ is the binary representation of $i$ (columns $001, 010, 011, \ldots, 111$). A received word has syndrome $001$. Which position (1-based) is in error?

Computed value: _answer

14. Somewhere new

Why does syndrome decoding work, and what does the decoder store?

• $Hr^T = He^T$ depends only on the error; a table of $2^{n-k}$ coset leaders gives nearest-codeword decoding
• The syndrome equals the transmitted codeword
• The decoder stores all $2^k$ codewords and compares each with the received word

15. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

16. Test question

With the same Hamming $[7, 4]$ code (column $i$ of $H$ = binary $i$), the word $1111110$ is received. Give its syndrome and the corrected codeword.

syndrome _s, codeword _c

17. What you can do now

You can decode any single error with a syndrome and build the perfect Hamming codes. Next: the bounds that say how good any code can possibly be.

Working for the steps left to you

9. Your turn: Hamming $[7, 4]$, received $1111110$, step 2