2
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

It would be too cumbersome to do it by brute force.

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – defacto
    Mar 17, 2021 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .