0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ $v \cdot H^t$ is not the "one which has been encoded", it is the syndrome of the error pattern from which one needs to determine what the error pattern was. Many different error patterns will ;produce the same syndrome and the decoder's job is to determine which is the most likely one (hint: fewer errors are more likely than many errors. $\endgroup$ Mar 17, 2019 at 19:53

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you for your answer! I found here some examples, too: homepages.math.uic.edu/~leon/mcs425-s08/handouts/… $\endgroup$
    – JohnD
    Mar 15, 2019 at 12:12
  • $\begingroup$ What I don't get: How are the coset leader(s) determined? $\endgroup$
    – JohnD
    Mar 15, 2019 at 12:12
  • $\begingroup$ I think it requires enumeration. $\endgroup$
    – Wuestenfux
    Mar 15, 2019 at 12:15

You must log in to answer this question.

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