3
$\begingroup$

When talking about FEC (forward error correction) block codes, some literature uses matrix terminology and some talks about polynomials. I know that the same block code could be expressed with either a generator matrix, or a generator polynomial, but I don't know what the relationship between them is.

Unfortunately I don't know enough about Galois fields, in this case GF(2) to figure this out.

  • If you know the generator matrix of a block code, how do you get its generator polynomial?
  • If you know the generator polynomial, how do you get the generator matrix?

And finally,

  • Why are these equivalent?
$\endgroup$
2
$\begingroup$

You're dealing with two types of block codes : "linear" codes which can be completely defined by a generator matrix, and "cyclic" codes which can be completely defined by a generator polynomial. Cyclic codes are a subset of linear codes; so if you know the generator ploy of a cyclic code you can derive a generator matrix from it very easily (the process is straight forward and is described in many textbooks so I'll skip that, someone else might have a direct reference or online resource). Going the other way is not always possible since there are codes that are linear but not cyclic so no such polynomial exists for these. For some codes in use : Reed-Solomon codes are cyclic (and therefor linear), almost all other codes (LDPC codes in Wifi,...) are linear but not cyclic.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is basically it. I do want to add that: 1) if we shorten a cyclic code from the end, we can still use a generator polynomial (simply restrict the inputs to lower degree polynomials) even though the shortened code is no longer cyclic. 2) The FEC codes for transmission of bulk data have so large block lengths that it would be impractical to store a generator matrix. It is nice to be able to compress the information needed for encoding. Many LDPC codes also have extra structure that can be exploited not unlike the generator polynomial. This has other (off-topic) practical advantages as well. $\endgroup$ – Jyrki Lahtonen Sep 4 '16 at 6:50
  • 1
    $\begingroup$ the LDPC in Wifi and some other standards have parity check matrices that are "quasi-cyclic" and that definitely helps simplify their decoding (and encoding, but to large extent the decoder is more critical). $\endgroup$ – unknown Sep 4 '16 at 17:31
  • $\begingroup$ Yup. Some other LDPC codes (DVB-S2/T2/NGH) have something similar, and a bidiagonal ladder block at the end. Those also enable a simpler circuitry to run the message passing decoding algorithm (the routing of messages may become too complex with a random Tanner graph). That is, indeed, their main point - conceding that (it also was the part I declared "off-topic"). But, you really don't want to store many something like a 64800 x 16200 (or thereabouts) generator matrices either :-) $\endgroup$ – Jyrki Lahtonen Sep 4 '16 at 18:17
  • $\begingroup$ Assuming that I have a code that is linear and cyclic (for example, Golay code), and I have the generator matrix, how do I get the generator polynomial and vice versa? I haven't been able to find good material so I'd welcome even a link to a textbook that explains it well. $\endgroup$ – Venemo Sep 5 '16 at 18:08
  • $\begingroup$ math.stackexchange.com/questions/1047535/… $\endgroup$ – unknown Sep 6 '16 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.