Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

share|cite|improve this question
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. – Dilip Sarwate Nov 26 '12 at 13:02
up vote 1 down vote accepted

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.

share|cite|improve this answer
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! – topskip Nov 26 '12 at 12:28
@topskip: You're welcome! – joriki Nov 26 '12 at 12:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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