Another Galois Field Multiply

After completing my Reed-Solomon decoder’s HDL, I decided to see how well it performed.  The results weren’t as good as I expected.  The limiting path was in the field math.  A bit of simple pipelining allowed 250MHz operation on my Virtex-6 -1 platform.  I had seen another snippet of code for a Galois Field multiply, but didn’t want to use it because I didn’t understand how it was derived.  A second look quickly revealed its secrets.

Before continuing, It might be helpful to read previous articles I’ve written about Galois Fields in order to avoid any confusion with the below math.

The thing I noticed in the second look was that the structure for each coefficient was simply a sum of products in GF2.  This was what prompted me to write out the code to generate my own fpga-efficient multiply.  Below is the basic principle, shown for elements a and b in GF8 generated by would be:

The first step is to perform the polynomial multiply directly:

The next step is to find the remainder  modulo .  This can be done using long division.  The first step is to cancel out the first term, .  This would mean subtracting from the above.  In a Galois Field that is a power of two, addition and subtraction are the same.  This gives:

This process continues.  The next term to subtract is .  This gives:

This gives expressions for the results:

Keep in mind that, though not shown here, it is possible that the same term will appear multiple times in a result.  For a Galois Field of a power of two, addition and subtraction are the same because each element is its own additive inverse.  This means .  In the above expressions, multiplication of the a and b terms is done using AND, while addition is done using XOR.

The resulting logic is:

c[2] = a[2]&b[2] ^ a[2]&b[1] ^ a[2]&b[0] ^ a[1]&b[2] 

     ^ a[1]&b[1] ^ a[0]&b[2];

c[1] = a[2]&b[2] ^ a[1]&b[0] ^ a[0]&b[1];

c[0] = a[2]&b[2] ^ a[2]&b[1] ^ a[1]&b[2] ^ a[0]&b[0];

This method can be put into a script, to allow for easy generation of a synthesizable Galois Field multiply function.  If my testing with Reed-Solomon decoders is any indication, the improvements can be significant.

I have made a python script that uses the above to generate a package for valid 256 element Galois Fields.  The resulting files are:

• Python: Code Generator for gf256_pkg.vhd
• VHDL: GF256 Package