# Constructing syndrome decoding table

I'm having trouble understanding how to make a syndrome decoding table. Part of the problem is I was told that a maximum likelihood decoding table was the same as a syndrome decoding table but they look different from the examples I've seen. I'll get straight to an example:

Say I have a generator matrix:

$G = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix}$

The parity matrix for that is:

$H = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$

And the 8 code words I get from that are: 00000, 001011, 010101, 011110, 100111, 101100, 110010, 111001.

Not sure where to go from here. I know the syndromes are: $\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\\end{bmatrix}$

But how are the coset leaders found? I've also seen tables where it has an "error" column and a "pattern/position" column.

EDIT: I think I understand it, if someone could check and confirm I'm doing this correctly that would be great. So I check to see if each syndrome is equal to a column in the parity check matrix, and if it does, I put a 1 in that column in the coset leader, and make a linear combination of the columns if the syndrome doesn't equal a single column.

$\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\\end{bmatrix}$ $\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\\end{bmatrix}$

If this is correct, what is the "error" and "pattern" I see other syndrome tables list??

Create a bordered table with a leftmost (border) column containing all the $2^{n-k}$ syndromes, an adjacent column with all the corresponding $2^{n-k}$ coset leaders, and a top (border) row consisting of all the $2^k$ codewords that you have found. Now you have an empty space of $2^{n-k}$ rows and $2^k$ columns that has been labeled with coset leaders on the left and codewords on top. Fill in the entries in this empty array by putting in each position the sum of its row label and its column label.

Congratulations! You have just created the standard array for the code. All possible $2^n$ binary vectors appear exactly once in this $2^{n-k}\times 2^k$ array. Conceptually, when you receive a vector $\mathbf r$, just find it in the array. The most likely transmitted codeword is the one labeling that position on the top, and the most likely error pattern is the coset leader labeling that position on the left. In practice nobody constructs the entire standard array. Instead, what you have done (a two-column table with syndrome and coset leader) suffices, with the method being to

1. Compute the syndrome $\mathbf{Hr}^T$.
2. Find the corresponding coset leader $\mathbf e$.
3. Take the most likely transmitted codeword to be $\mathbf r \oplus \mathbf e$.
• I see. The example I was looking at said to do it without first constructing the array. So what I did is okay then? Thanks for the instructions by the way! Oct 31, 2015 at 4:03
• Yes, what you did is OK. Oct 31, 2015 at 14:04