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

Question

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.

Answer 1

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:

• The trick you just saw with the Hamming code is one of them. (Though a LUT with $2^3$ entries can easily fit in a CPU cache or a small region of silicon, so the LUT size isn't much of a practical concern for the Hamming code.)
• There are several algorithms to decode Reed-Solomon codes without calculating a lookup table: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Error_correction_algorithms
• Similar for BCH codes: https://en.wikipedia.org/wiki/BCH_code#Decoding

Answer 2

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?).