Reed-Solomon algorithm for a QR code generator

Question

In my data structures class, I wanted to create a QR code generator for my final project. However I am having some trouble understanding the "Formatted Error Correction" part of it. I want to use a error correction of 11 (L) and a masking pattern of 100 (every other row). Since I am an undergrad, I want to try and keep it pretty simple with dealing with a version 1 QR code and use byte encoding.

Then I don't understand how to come up with error correction boxes after the data is output.

Answer 1

Looking at some specifications, error correction level L (low, can correct 7%) is identified as the two bit pattern 01, not 11. Link to QR code format strings, which include mask and error correction level.

http://www.thonky.com/qr-code-tutorial/format-version-information

Since you've chosen a specific error correction level and mask pattern, which are the same as used in the thonky.com web page, the format string will be a fixed 15 bit pattern of bits: "the final format string for a code with error correction level L and mask pattern 4 is 110011000101111" , so you won't have to bother calculating it.

For QR codes, the 8 bit field GF(2^8) is based on a 9 bit polynomial

    x^8 + x^4 + x^3 + x^2 + 1 = hex 11d
    the primitive   α = x + 0 = hex   2

Note that both addition and subtraction for a binary field are the same as xor.

QR code version 1 is a matrix of 21 by 21 bits = 441 bits represented as black or white squares, with 208 bits == 26 bytes used for data and ecc.

QR code with error correction level L has 152 bits == 19 bytes of data and 56 bits == 7 bytes of ecc, 4 used for correction, 3 used for detection. The 4 bytes used for correction can correct 2 out of 26 bytes, about 7% of the 26 data bytes. In addition to the 3 bytes used for detection, an uncorrectable error is also detected if during decoding, either of the calculated locations is outside the range of the 26 bytes of data.

The generator polynomial g(x) is an 8 term polynomial that results in a 7 term remainder. The 7 roots of g(x) = 0 are consecutive powers of α, in this case α^0, α^1, ... α^6 == hex 01, 02, 04, 08, 10, 20, 40.

g(x) = (x-1)(x-α)(x-α^2)(x-α^3)(x-α^4)(x-α^5)(x-α^6)

Since addition == subtraction == xor, the minuses can be replaced with pluses:

g(x) = (x+1)(x+α)(x+α^2)(x+α^3)(x+α^4)(x+α^5)(x+α^6)
g(x) = (x+01)(x+02)(x+04)(x+08)(x+10)(x+20)(x+40)
g(x) = 01 x^7 + 7f x^6 + 7a x^5 + 9a x^4 + a4 x^3 + 0b x^2 + 44 x + 75

Consider the 19 bytes of data as a polynomial m(x) (m stands for message). The 19 bytes of data are padded with 7 bytes of zero by multiplying by x^7. Then the 26 byte polynomial is divided by the generator polynomial and the remainder is "subtracted" (xor'ed or since the padding produces zeroes, the remainder just replaces the padded bytes) to the low 7 bytes of the padded data. Calling the remainder r(x), and the coded result c(x):

r(x) = (m(x) x^7) % g(x)
c(x) = (m(x) x^7) - r(x)

Again note that subtraction is xor, the same as addition.

Wiki has a decent article about Reed Solomon:

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

and NASA has a tutorial:

http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf