Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

I begin by answering the question in the last paragraph with a single word No! This is something very specific to Hamming code.

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.

share|improve this answer
    
Thanks! I have refined my question: math.stackexchange.com/q/379384/21813 –  Ryan May 2 '13 at 15:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.