# How to find all the coset leaders? (follow-up to a previous question)

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 $4$-tuple minimum-weight error vectors $\{\vec e_{m1}=\vec0,…,\vec e_{m9} \}$ corresponding to all the syndromes $\{\vec s_1=\vec0,…,\vec s_9 \}$. 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 don’t understand why the italized statement is so nor why each coset has at least one such vector.

More importantly, in general, given a linear code, is there an algorithm to determine the minimum-weight error vectors corresponding to the syndromes, without having to first list out all the possible cosets?

(I understand that multiple such vectors may correspond to a syndrome, and also realise that different coset leaders may have different weights.)

#### Solutions Collecting From Web of "How to find all the coset leaders? (follow-up to a previous question)"

I am not aware of a general efficient algorithm for doing this. Again a few remarks listing some obvious things and then trying to explain why this is difficult in general.

First the easy parts. If the minimum distance of the code is $d$, then any vector of weight $\le(d-1)/2$ is the leader of its coset. This follows immediately from the triangle inequality (applied to the Hamming metric). If the weight of a vector $x$ is $w>(d-1)/2$, then $x$ may or may not be a coset leader. If $w>d/2$, then we can always find some vectors of weight $w$ that are not coset leaders. If $w=d/2$, then $x$ is a coset leader, but there may be other vectors of weight $w$ in the same coset, and it is not at all clear which of those should be included in the syndrome dictionary!

Then the difficult part. In general we do not know the maximum weight of a coset leader! This maximum has another name. It is better known as the covering radius of the code. The covering radius is known only for relatively few of the well studied linear codes, such as the Hamming code. If the covering radius of a code $C$ is $\rho$, this means that any vector is within Hamming distance $\le\rho$ from a codeword of $C$. For example the covering radii of BCH-codes are known in a few specific cases, and in the asymptotic case (keep the designed distance but let the length grow). These were studied in highly non-trivial research papers, so I won’t get into details here.

However, we can easily settle the truth of the italicized statement in your question! While doing that we actually prove that the covering radius of this code is $1$, but you don’t need to necessarily worry about that.

You correctly observed that the syndrome of this code has nine possible values.
Furthermore, we know that the minimum distance of this code is $d=3$. In my answer to an earlier version of this question I explained, why there are nine vectors of weight $\le1$ in
the Hamming space $\mathbb{F}_3^4$. Because their weights are all $\le(d-1)/2$, they belong to distinct coset of the code (see the “easy part”). Therefore they cover all the nine cosets between them. A miracle occurred!

There is another way of seeing this. The syndrome of the zero vector is obviously zero. But the syndrome of the vector with three zeros and a single one is the corresponding column of the check matrix. Similarly the syndrome of the vector with three zeros and a single two is the corresponding column multiplied by $2=-1$. Now, you should check that if you list all the four columns of your check matrix together with the versions multiplied by $2$ (or $-1$), your list contains all the eight non-zero vectors with two ternary components.