1
$\begingroup$

Assume I have a linear code over $\mathbb{F}_2$ with dimensions $[3,6]$ and generator matrix $G$ not in standard form

$$\begin{bmatrix} 0&1&0&1&1&0 \\ 1&0&0&1&0&1 \\ 0&0&1&0&1&1 \end{bmatrix}$$

Suppose I receive the vector $$y = (1,0,1,0,0,1)$$ and I want to correct it using the syndrome decoding algorithm.

  • I can put $G$ in standard form by exchanging the first two columns, call it $G'$, get the parity check matrix for the equivalent code, call it $H'$, and then find the original parity check matrix $H$ and apply the Syndrome decoding algorithm to the vector $y$, and that is fine.

  • What about if I want to use the SDA algorithm with the parity check matrix $H'$ (the one that corresponds to generator matrix $G'$)? What should I change?


EDIT:

In this specific example

$$G' = \begin{bmatrix} 1&0&0&1&1&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&1 \end{bmatrix}$$

and

$$H' = \begin{bmatrix} 1&1&0&1&0&0 \\ 1&0&1&0&1&0 \\ 0&1&1&0&0&1 \end{bmatrix}$$

If I want to use $H'$, I consider $yP=(0,1,1,0,0,1)$. Then $H'\cdot yP=(1,1,1)$.

Therefore, I have to compute the cosets of $(1,1,1)$. It is the set $$\{x \in F_2^6: H' \cdot x = (1,1,1) \}$$

and this is represented by

$$ \begin{cases} x_1+x_2+x_4 = 1 \\ x_1+x_3+x_5=1 \\ x_2+x_3+x_6 = 1 \end{cases} $$

The solutions are given by a $$\text{particular one } + C' $$ $$ (1,0,1,0,1,0) + C'$$

and doing the computations I choose as coset leader $e_3 + e_4$, obtaining the correction $$c = yP+e_3+e_4 = (0,1,0,1,0,1)$$

Now, to obtain the right corrected word, I just multiply by $P^{-1} = P$ (it's orthogonal), and hence I obtain $$cP = (1,0,0,1,01)$$ which is a codeword in $C$ (I just checked it by multiplying: $H\cdot cP = 0$)

$\endgroup$
5
  • $\begingroup$ Regarding your example: are you sure your code can correct two errors? Obviously the yP you picked has more than one error, and I can easily pick out three error messages of weight 2 that yield that syndrome, so decoding wouldn’t be unique... $\endgroup$
    – rschwieb
    Commented Jun 19, 2020 at 10:46
  • $\begingroup$ Yes, it can correct $2$ errors, as the minimum distance is $2$. My question was just about if it was right the "procedure". it should be okay,right? @rschwieb $\endgroup$ Commented Jun 19, 2020 at 12:51
  • $\begingroup$ What do you mean "It can correct 2 errors as the minimum distance is 2"? As far as I can tell, it has minimum distance $3$, meaning it can correct a single error. To correct $2$ errors, you'd need a distance of $5$ or more. $\endgroup$
    – rschwieb
    Commented Jun 19, 2020 at 13:57
  • $\begingroup$ You know that for binary codes, you can only guarantee correction of $\lfloor \frac d 2\rfloor$ where $d$ is the distance, right? $\endgroup$
    – rschwieb
    Commented Jun 19, 2020 at 14:03
  • $\begingroup$ my bad, yes you're right (I was doing another exercise and got confused) ! btw, just considering the "algorithm", is it the right way to apply it ? I think so, as $H \cdot cP = 0$ so it's a codeword. @rschwieb $\endgroup$ Commented Jun 19, 2020 at 14:54

1 Answer 1

2
$\begingroup$

If you used the matrix $P$ to get $GP=G'$, then you would apply the algorithm to the codeword $yP$.

At that point you'd be decoding $yP$ with $H'$ from the code $G'$. It sounds like you understand how to apply it so... not sure what is left to say.

$\endgroup$
6
  • $\begingroup$ So, just to be sure: I apply SDA with $H'$ to the vector $yP=(0,1,1,0,0,1)$ and in the algorithm I will always use the elements of the equivalent code $G'$ (to compute cosets and so on...). Then, I will find the corrected vector $c= y-e$. I don't know now if it's in $C$ or in $C'$... do I have to do $cP$ ? Or is it already in $C$? @rschwieb $\endgroup$ Commented Jun 18, 2020 at 19:30
  • $\begingroup$ Your error vector will be in terms of words in the equivalent code. You'd get $c=yP-e$, which would translate to $cP^{-1} = y - eP^{-1}$. That is, the error in the original code was $eP^{-1}$ and your new corrected word is $cP^{-1}$. $\endgroup$
    – rschwieb
    Commented Jun 18, 2020 at 19:36
  • $\begingroup$ Try it out: introduc an error on the first position, then on the second position, then on the third position. Things should work out the way you think they should. $\endgroup$
    – rschwieb
    Commented Jun 18, 2020 at 19:38
  • $\begingroup$ Okay, I'm going to try with an example. Just one last question: so, in practice, I do SDA with $yP,H',G'$ and I find the correction $c$, and then I find the right correction by doing $cP^{-1}$ @rschwieb $\endgroup$ Commented Jun 18, 2020 at 21:28
  • $\begingroup$ @bobinthebox yes, that is what I want you to try out a few times to see things work. I think you’ll see what’s going on after that. $\endgroup$
    – rschwieb
    Commented Jun 19, 2020 at 0:08

You must log in to answer this question.

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