# How to construct a syndrome dictionary?

Consider the $[4,2]$ ternary Hamming code with check matrix $\left( \begin{array}{ccc} 1 & 1 & 2 &0\\ 0 & 1 & 1 & 1\end{array} \right).$

Clearly, the code has $2$-tuple syndromes $\{\vec s_1=\vec0,...,\vec s_9 \}$ and $4$-tuple minimum-weight error vectors $\{\vec e_{m1}=\vec0,...,\vec e_{m9} \}$. To construct the syndrome table, we first need to list the nine minimum-weight error vectors, then compute the syndrome for each (using the formula $\vec s=H\vec e_m$). So far so good. But how do I determine the minimum-weight error vectors?

In this case, my textbook says to list $\vec0$ and all the eight 4-tuples whose weight is $1$, since nonzero 4-tupple error vectors have minimum weight 1.

Sounds reasonable, except that I would like to be properly convinced of the italized statement above; is it true in general that listing all the $p^{n-k}$ coset leaders of length $n$ always means listing $\vec0$ with all the $p^{n-k}-1$ $n$-tuples of weight $1$? If so, why?

-
Think about it for a minute. The number of $n$-tuples of weight 1 is only $n(p-1)$. – Jyrki Lahtonen May 2 '13 at 12:14

On with something more useful. Let's count how many error patterns of weight at most one there are! There is a single error pattern of weight zero, namely $(0,0,0,0)$. There are two ternary error patterns of weight one such that the offending component is the first, namely $(1,0,0,0)$ and $(2,0,0,0)$. Similarly you can find two error patterns of weight two such that the offending component is in any other positions. So we have a total of $1+4\cdot2=9$ error patterns of weight $\le1$. The minimum distance of the code is three, so these all belong to different cosets of the code. As the code is of codimension two, it has exactly $3^2=9$ cosets and we are done.
A couple of remarks. If a code can correct up to $t$ errors then similarly all the error patterns of weight $\le t$ belong to distinct cosets. A similar counting argument shows that there are exactly $$\sum_{\ell=0}^t{n\choose \ell}(p-1)^\ell$$ such error patterns. It is very rare, indeed, that this number should happen to be equal to $p^{n-k}$ (usually it is much less). This is equal to $p^{n-k}$ only when $C$ is a so called perfect $p$-ary code. Perfect is an apt name, because for this to happen, the balls of radius $t$ centered at codewords must exactly fill the entire Haming space without any overlap. The possible parameters of perfect codes were classified in the 1960s by Tietäväinen.