1
$\begingroup$

I am trying to implement qr-codes (2d "barcodes"). The part with generating error correction codes is difficult to me, and I've found a tutorial on the www that helps me understanding the math behind it.

http://www.thonky.com/qr-code-tutorial/part-2-error-correction/

I can follow the steps until the writer introduces the term "$α^{78}x^{11}$" in the second section called "Multiply generator polynomial by first coefficient of the above polynomial" (the first sentence there is "First coefficient of the above polynomial: $α^{178}$").

Where does the $x^{11}$ come from?

This is obviously basic math, I feel a bit ashamed to ask this... (first question here on math.sx)

$\endgroup$
1
  • $\begingroup$ Don't feel bad that you are having trouble figuring out what is being done. As joriki says, that tutorial seems unnecessarily complicated, perhaps intended for an audience that has either never heard of "long division" of polynomials or has forgotten it if it was ever taught in their (American) school. $\endgroup$ Nov 26, 2012 at 13:02

1 Answer 1

2
$\begingroup$

The key is in the section headed "Generator polynomial", where it says:

To make this step easier, we multiply the generator polynomial by $x^{12}$ so that its first term is $x^{25}$. This way, the first term matches the message polynomial's first term, which also has $x^{25}$.

The polynomial you're trying to understand is the same generator polynomial, only this time multiplied by $x^{11}$ to match the new first term. The explanation seems unnecessarily complicated; I'd find it easier to understand if the generator polynomial were left unmodified and the multiplication by a power of $\alpha$ and a power of $x$ to match the first term were performed in one step.

$\endgroup$
2
  • $\begingroup$ I really feel a great relief :) I have been pondering about this for quite some time now and all of the sudden (reading your answer), this seems totally clear to me. Always had that feeling once I understood a math problem... Many Thanks! $\endgroup$
    – topskip
    Nov 26, 2012 at 12:28
  • $\begingroup$ @topskip: You're welcome! $\endgroup$
    – joriki
    Nov 26, 2012 at 12:31

You must log in to answer this question.

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