# Syndrome Decoding - Coset Leader

Currently, I am studying linear coding and came across the syndrome decoding. I have some difficulties trying to solve this problem:

Let $$C$$ be the linear $$[10,5]$$-code over $$\mathbb{F}_3$$ with generator matrix $$G= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 2 & 0 & 1 & 2 & 1\\ 0 & 0 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2\\ 0 & 0 & 0 & 1 & 0 & 2 & 1 & 2 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 2 & 2 & 1 & 1 & 0 \end{bmatrix}$$ By syndrome decoding, decode $$u= \begin{pmatrix} 1 & 0 & 2 & 2 & 0 & 1 & 2 & 1 & 0 & 0\\ \end{pmatrix}.$$

My approach: I know the parity-check matrix to be, in this case, $$H=[-G^T\,I]$$. That is, $$H=\begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 2 & 0 & 1 & 2 & 0 & 0 & 1 & 0 & 0\\ 2 & 1 & 2 & 0 & 2 & 0 & 0 & 0 & 1 & 0\\ 2 & 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}.$$

The syndrome of $$u$$ is $$\text{syn}(u)=Hu^T= \begin{pmatrix} 2 & 2 & 1 & 0 & 2 \end{pmatrix}^T.$$

Now, I am not sure on how to proceed here. How do I find a coset leader, $$\alpha$$, corresponding to $$\text{syn}(u)$$ so that I may decode $$u$$ as $$u-\alpha$$? Many thanks in advance!

We have $$3^5=243$$ codewords, hence the standard array would have $$243$$ columns and $$3^{10}/3^5=243$$ rows (that is, $$243$$ cosets, each having $$243$$ elements).
By inspection, we can see that your computed syndrome $$s$$ equals the sum of columns $$4$$ and $$6$$ (one-based indexing). Hence the tuple
$$e_1 = (0 0 0 1 0 1 0 0 )$$
verifies $$H e_1^t= s$$ and is one of the elements of the coset. You could find all the other elements by suming to it the $$242$$ non-zero codewords. The coset leader (asuming a channel with small probability of tribit change) would be the element with smallest weight. I'd bet that $$e_1$$ is the one.
• Thanks for the answer! Meanwhile, I figured it out. It is not difficult to see solutions with weight $1$ don't exist. So, $e_1$, a solution of $Hx^T=\text{syn}(u)$, is indeed a coset leader. Mar 17, 2021 at 15:50