I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I have looked at a bunch of existing implementations, and they all try to implement a bunch of polynomial math that goes straight over my head, particularly with regards to the Galois fields. The most straightforward way I can see, both in mathematical complexity and in memory requirements is a circuit concept that is laid out in the spec itself:
With their description, I am fairly confident I could implement this with the exception of the parts labeled GF(256) addition and GF(256) Multiplication.
They offer this help:
The polynomial arithmetic for QR Code shall be calculated using bit-wise modulo 2 arithmetic and byte-wise
modulo 100011101 arithmetic. This is a Galois field of 2^8
with 100011101 representing the field's prime modulus
polynomial x^8+x^4+x^3+x^2+1.
which is all pretty much greek to me.
So my question is this: What is the easiest way to perform addition and multiplication in this kind of Galois field arithmetic? Assume both input numbers are 8 bits wide, and my output needs to be 8 bits wide also. Several implementations precalculate, or hardcode in two lookup tables to help with this, but I am not sure how those are calculated, or how I would use them in this situation. I would rather not take the 512 byte memory hit for the two tables, but it really depends on what the alternative is. I really just need help understanding how to do a single multiplication and addition operation in this circuit.
Best Answer
For your purposes, the elements of $GF(256)$ are polynomials in $x$ of degree $\le 7$ with coefficients in $GF(2)$. $GF(2)$ is just $\{0,1\}$ with binary addition and multiplication, but there are no carries: 1+1=0 in $GF(2)$.
So for example, $x^4 + x^3 + 1$, $x^7 + x^2 + x$, $x^5 + x^3 + 1$, are all elements of $GF(256)$. There are 256 elements in all (hence the name $GF(256)$).
Addition of 2 polynomials in $GF(256)$ is straightforward. For example: $(x^4 + x^3 + 1) + (x^3 + x^2 + 1) = x^4 + x^2$. This is just normal addition of polynomials, but the coefficients of the calculations take place in $GF(2)$. So when I added the 2 $x^3$ terms together, the coefficient became 1+1=0 (so the $x^3$ term disappeared altogether). As bit sequences this would be: 11001 + 1101 = 10100. This is straightforward to implement in most programming languages: It's just an XOR of the bit sequences.
To multiply 2 polynomials in $GF(256)$, first you multiply the polynomials just like ordinary polynomials but again, remembering that the calculations take place in $GF(2)$. Then divide the result by $x^8+x^4+x^3+x^2+1$ and take the remainder. Unlike addition, this is less straightforward to implement from scratch. (You can't use the usual multiplication operator in your programming language to do the multiplication, because ordinary multiplication has carries, but $GF(2)$ does not.)
See the example here which is a slightly different polynomial (they use $x^8+x^4+x^3+x+1$ instead of $x^8+x^4+x^3+x^2+1$), but it's the same process. There is also a description of a multiplication algorithm there (you'll have to change it slightly for your polynomial).