mathqr-codereed-solomongalois-field# Addition and multiplication in a Galois Field

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.

Solution

In practice only one table is needed. That would be for the GP(256) multiply. Note that all arithmetic is carry-less, meaning that there is no carry-propagation.

Addition and subtraction without carry is equivalent to an xor.

So in GF(256), `a + b`

and `a - b`

are both equivalent to `a xor b`

.

GF(256) multiplication is also carry-less, and can be done using carry-less multiplication in a similar way with carry-less addition/subtraction. This can be done efficiently with hardware support via say Intel's CLMUL instruction set.

However, the hard part, is reducing the modulo `100011101`

. In normal integer division, you do it using a series of compare/subtract steps. In GF(256), you do it in a nearly identical manner using a series of compare/xor steps.

In fact, it's bad enough where it's still faster to just precompute all 256 x 256 multiplies and put them into a 65536-entry look-up table.

page 3 of the following pdf has a pretty good reference on GF256 arithmetic:

- Algorithm to locate local maxima
- unsigned long long int pow
- Simple statistics - Java packages for calculating mean, standard deviation, etc
- Arbitrary-precision arithmetic Explanation
- How do I calculate r-squared using Python and Numpy?
- Print all ways to sum n integers so that they total a given sum.
- Prove that (p → q) → ((r ∨ p) → (r ∨ q)) is a tautology without using truth table
- How to implement this Desmos roll function in Unity
- How to compute the centroid of a mesh with triangular faces?
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Efficiently getting all divisors of a given number
- In JavaScript, why does zero divided by zero return NaN, but any other divided by zero return Infinity?
- Float number division with 3 decimal places
- Python fit line to high dimensional points and sample between them
- How can I compute a dual norm?
- How to pick between 2 numbers
- Fastest implementation of sine, cosine and square root in C++ (doesn't need to be much accurate)
- double and accuracy
- Is there a standard sign function (signum, sgn) in C/C++?
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Is there such thing as math.substring in java?
- Count number of ways to pair integers 1-14 under constraint
- How to round up on a log10
- Bezier curve arc lengths
- Calculate cash flows given a target IRR
- Integration in Python Midpoint Calculation
- Generate P random N-dimensional points from list of ALL possible pairwise distances
- Grouping a list of integers with nearest values
- Branchless calculation for multiplying by the complement of a fraction with a flag
- Finding least number of moves