Syndrome decoding

Question

I have a conceptional question to the concept of "syndrome decoding" (i.e. the procedure to decode a received vector).

Let's say I'm given a generator matrix G and a received vector v = (1, 1, 1, 0, 1, 0). How can I decode the received vector?

Here is what I would do, but I'm not sure:

1. Bring G to standard form (I | A)
2. Parity check matrix is: $H = (-A^t | I)$
3. Compute $v \cdot H^t$, the received code is the one which has been encoded.

Is this correct?

Thanks for any correction!

Answer 1

Well, its incomplete. Take the received word $v$ and compute the syndrome $s = Hv^t$.

Here you need to do some preliminary work. Write $v=c+e$ for codeword $c$ and error vector $e$. Then $Hv^t = Hc^t+ He^t = He^t$. Thus the syndrome $s$ tells you the error vector $e$. Then $c=v-e$ gives the decoded codeword. To do so, you need to make a list of pairs $(s, e)$ where $s$ is a syndrome and $e$ is a vector (coset leader) with $s=He^t$ of minimal Hamming weight. Note that there are cases where $e$ is not uniquely determined by $s$.