Now comes the hard part.
Most of the Math in QR codes in performed in the Galois Field of order 28 = 256. In this set, denoted as GF(256):
inclu...
For further actions, you may consider blocking this person and/or reporting abuse
Very nice article! A question though: IIUC, GF(2^8) marks a set of polynomials with coefficients taken from GF(2), i.e. the coefficients can only be 0 or 1. Yet the article keeps referring to 255 as being the top value for a coefficient. How come?
Where did you get that the coefficients can only be 0 or 1? Some irreducible polynomials used for the algorithm have only 0 or 1 as coefficients, but not in the general case.
I was reading up on finite fields (in preparation for QR code generation, obviously :)) and in these lecture notes - engineering.purdue.edu/kak/compsec/ (Finite Fields PART 1-4) - the field GF(2^8) is described as comprising elements that are polynomials (up to a certain degree) with coefficients in the set {0,1} (because the coeffs themselves are from GF(2)).
The irreducible polynomials will always have 0,1 as coeffs, IIUC, (see e.g. codyplanteen.com/assets/rs/gf256_p...) but the generator polynomial(s) given in the QR standard have coefficients that are powers of the primitive element (2, i.e. the polynomial x). Which is confusing to me. Maybe it boils down to the same thing in the end, if one were to rewrite the generator polynomials without the primitive element.
I guess I'm having a bit of trouble merging the view of the fields and their arithmetics as given in the lecture notes with that of, it seems, the implementations I've found so far, with regards to some aspects.
I'm impressed the lengths you're covering to fully understand the algorithm behind - I have a degree in Mathematics and yet I stopped at some point 😅 Props to you!
And now I notice how miserably worded this phrase is:
What I mean that some polynomials have only 0 and 1 coeffs, and happen to be irreducible.
Thank you! And props to you too! I must say it's very nice to have trailblazers such as you that not only do the implementation but also write about it!
Ah, I think I am beginning to understand the source of my confusion. I interpreted the (QR) standard's wording on the RS encoding as:
"Treat the message codewords as coefficients of a polynom that is an element of GF(2^8)"
But it should be, I guess, (although quite obtusely worded, IMHO):
"Use the message codewords (as coefficients) to form a polynomial with coefficients that are elements of GF(2^8)".
That would explain much. Such a relief. I thought I was going to have to go mad.
Yes! I agree, that's kind of obscure.
But then again, the whole algorithm is kind of obscure haha
The first element of your LOG table is 0x00. I think it should be 0xFF.
Found these pre-calculated Log and Exp tables here
github.com/anunpanya/ESP8266_QRcod...
and I think they are correct.
I'm at a point in my implementation where I get the same result for the polynomial division as in this tutorial (for the very same example), and I must take a moment to give your credit for the clean code you have produced. My own code is generally blargh, in comparison, with complicated constructs of indices and unnecessary array constructs (very nice use of slice in the polyRest function!). And ofc, overall impressive how you seem to be so confident with the arithmetics involved. Very valuable to follow your example. I imagine it would have taken me three days to figure out which k the standard refers to when it says "if you do this by long division, you must multiply the data codewords by x^k". I'll see if I arrive at the same symbol in the end... :)