# When decoding a block code, how do you know which error a syndrome corresponds to?

I'm working with forward error correcting block codes such as Hamming(7,4) and Golay(23,12). I'm quite new to this field, so there are some things that I don't yet understand. I chose these codes because they are simple enough for me to understand their theory.

I know that I can encode a codeword by either using the generator matrix approach or by using polinomial division.

When decoding, I can use the parity check matrix to get a syndrome vector from the received code word. However, how could my algorithm know which syndrome corresponds to which error? In other words, if I know the syndrome, how do I decide which bits to flip in the received code word to do error correction?

I could, of course, build a lookup table for this (which would be easy), but I'd like to correctly understand the theory first.

Wikipedia says in its Hamming(7,4) article that I should interpret the syndrome as an integer and use it to tell which bit to flip, but this doesn't even work with the example generator matrix. This guy seems to simply flip every possible combination of bits until the errors are fixed. There must be a better way.

Recall that for a parity check matrix $H$ and codeword $c$, $Hc^T = 0$ (by definition). When you send a codeword $c$ over the channel and receive $r$ on the other end, it effectively gets a noise vector $n$ added to it: $r = c + n$. Thus the syndrome is $s = Hr^T = H (c + n)^T = Hc^T + Hn^T = Hn^T$.

The most likely noise vector is the one with the lowest Hamming weight (assuming the probability of a bit flip is $<\frac{1}{2}$). So to decode a received vector $r$, you calculate its syndrome, find the lowest weight vector $n$ with the same syndrome, then decode to $\hat{c} = r - n$.

The trick with the $[7,4]$ Hamming code works if you use the parity check matrix

$$H = \begin{pmatrix} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{pmatrix}.$$

It works because multiplying $H$ by the vector with a $1$ in the $k^\text{th}$ position yields the $k^\text{th}$ column of the matrix, which is $k$ in binary.

As you noted, explicitly calculating the lookup table for every syndrome is impractical for large codes. Different decoding algorithms use different tricks to avoid calculating the whole lookup table:

• Thanks for your answer! I'm surprised there isn't a good generic algorithm for syndrome-based decoding. Can you suggest a similar good trick for decoding the Golay code? It looks like it would require a ~11k lookup table, which is quite impractical. But calculating every permutation of every possible error also feels wasteful. Doesn't the syndrome at least give a hint? Aug 7, 2015 at 8:54
• I don't know how to decode the binary Golay code, but searching "decoding binary golay code" yielded this document. I think it's better to think of syndome decoding as a starting point for more efficient, specialized decoding algorithms. Aug 7, 2015 at 17:36
• By the way, you'd only need a lookup table of size $\sum_{i=0}^3 \binom{23}{i} = 2048$ for syndrome decoding, since the (perfect) binary Golay code can only correct up to 3 errors. Aug 7, 2015 at 17:41

Flipping all possible bits until the errors are fixed is very similar to minimum distance decoding, and that's what you probably have to do if there are more errors than can be corrected by the code. Syndrome decoding also works with a lookup-table, but with fewer entries. I'm not sure, but it seems that "interpreting the syndrome as an integer" might only work for the Hamming code (why do you think it did not work in the Wikipedia example?).

• If I use the generator matrix from the Wikipedia example, to encode 1100 I get 0111100. Then, let's say there is an error in the 6th bit, so I receive 0111110. Multiplying the parity check matrix from the Wikipedia example with this vector, I get 011 which is decimal 3. Aug 7, 2015 at 8:45
• Hmm, ok, I see. But if you reverse the bit order to 110, then it's 6. Could this be the problem? Aug 7, 2015 at 9:47
• Maybe that's what I should do... I'm honestly not sure if there would be other vectors which wouldn't work that way. Aug 7, 2015 at 10:20
• Can you maybe give me a tip about decoding the Golay-code? Aug 7, 2015 at 10:48
• Sorry, I don't know anything about Golay-codes -- really sorry! Aug 7, 2015 at 11:07