# Syndrome decoding algorithm and standard form

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

• 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... Commented Jun 19, 2020 at 10:46
• 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 Commented Jun 19, 2020 at 12:51
• 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. Commented Jun 19, 2020 at 13:57
• You know that for binary codes, you can only guarantee correction of $\lfloor \frac d 2\rfloor$ where $d$ is the distance, right? Commented Jun 19, 2020 at 14:03
• 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 Commented Jun 19, 2020 at 14:54

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.
• 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 Commented Jun 18, 2020 at 19:30
• 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}$. Commented Jun 18, 2020 at 19:36
• 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 Commented Jun 18, 2020 at 21:28