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)

  • 0
    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.2012-11-26

1 Answers 1

2

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.

  • 0
    @topskip: You're welcome!2012-11-26