Galois Field Multiplier for Reed Solomon Code

[leongch]

Hi guys,

I am implementing ReedSolomon Code(256,191) with 8bits per symbol

I found some of the online code for Galois Field Multiplier 256 as followed. Who can tell me how to come out with this kind of XOR ?

module gf256mult(a, b, z);
input [7:0] a;
input [7:0] b;
output [7:0] z;
assign z[0] = b[0]&a[0]^b[1]&a[7]^b[2]&a[6]^b[3]&a[5]^b[4]&a[4]^b[5]&a[3]^b[5]&a[7]^b[6]&a[2]^b[6]&a[6]^b[6]&a[7]^b[7]&a[1]^b[7]&a[5]^b[7]&a[6]^b[7]&a[7];
assign z[1] = b[0]&a[1]^b[1]&a[0]^b[2]&a[7]^b[3]&a[6]^b[4]&a[5]^b[5]&a[4]^b[6]&a[3]^b[6]&a[7]^b[7]&a[2]^b[7]&a[6]^b[7]&a[7];
assign z[2] = b[0]&a[2]^b[1]&a[1]^b[1]&a[7]^b[2]&a[0]^b[2]&a[6]^b[3]&a[5]^b[3]&a[7]^b[4]&a[4]^b[4]&a[6]^b[5]&a[3]^b[5]&a[5]^b[5]&a[7]^b[6]&a[2]^b[6]&a[4]^b[6]&a[6]^b[6]&a[7]^b[7]&a[1]^b[7]&a[3]^b[7]&a[5]^b[7]&a[6];
assign z[3] = b[0]&a[3]^b[1]&a[2]^b[1]&a[7]^b[2]&a[1]^b[2]&a[6]^b[2]&a[7]^b[3]&a[0]^b[3]&a[5]^b[3]&a[6]^b[4]&a[4]^b[4]&a[5]^b[4]&a[7]^b[5]&a[3]^b[5]&a[4]^b[5]&a[6]^b[5]&a[7]^b[6]&a[2]^b[6]&a[3]^b[6]&a[5]^b[6]&a[6]^b[7]&a[1]^b[7]&a[2]^b[7]&a[4]^b[7]&a[5];
assign z[4] = b[0]&a[4]^b[1]&a[3]^b[1]&a[7]^b[2]&a[2]^b[2]&a[6]^b[2]&a[7]^b[3]&a[1]^b[3]&a[5]^b[3]&a[6]^b[3]&a[7]^b[4]&a[0]^b[4]&a[4]^b[4]&a[5]^b[4]&a[6]^b[5]&a[3]^b[5]&a[4]^b[5]&a[5]^b[6]&a[2]^b[6]&a[3]^b[6]&a[4]^b[7]&a[1]^b[7]&a[2]^b[7]&a[3]^b[7]&a[7];
assign z[5] = b[0]&a[5]^b[1]&a[4]^b[2]&a[3]^b[2]&a[7]^b[3]&a[2]^b[3]&a[6]^b[3]&a[7]^b[4]&a[1]^b[4]&a[5]^b[4]&a[6]^b[4]&a[7]^b[5]&a[0]^b[5]&a[4]^b[5]&a[5]^b[5]&a[6]^b[6]&a[3]^b[6]&a[4]^b[6]&a[5]^b[7]&a[2]^b[7]&a[3]^b[7]&a[4];
assign z[6] = b[0]&a[6]^b[1]&a[5]^b[2]&a[4]^b[3]&a[3]^b[3]&a[7]^b[4]&a[2]^b[4]&a[6]^b[4]&a[7]^b[5]&a[1]^b[5]&a[5]^b[5]&a[6]^b[5]&a[7]^b[6]&a[0]^b[6]&a[4]^b[6]&a[5]^b[6]&a[6]^b[7]&a[3]^b[7]&a[4]^b[7]&a[5];
assign z[7] = b[0]&a[7]^b[1]&a[6]^b[2]&a[5]^b[3]&a[4]^b[4]&a[3]^b[4]&a[7]^b[5]&a[2]^b[5]&a[6]^b[5]&a[7]^b[6]&a[1]^b[6]&a[5]^b[6]&a[6]^b[6]&a[7]^b[7]&a[0]^b[7]&a[4]^b[7]&a[5]^b[7]&a[6];
endmodule

Thanks

 

[bulx]

If you are asking why this XOR achieves GF multiplication:

it follows from the fact that multiplication by the GF primitive element is a simple operation, and you can easily add up several such products to achieve multiplication by any GF element.

-b

 

[leongch]

Hi Thanks for reply, I am asking, how to achieve it.

Like the function
assign z[0] = b[0]&a[0]^b[1]&a[7]^b[2]&a[6]^b[3]&a[5]^b[4]&a[4]^b[5]&a[3]^b[5]&a[7]^b[6]&a[2]^b[6]&a[6]^b[6]&a[7]^b[7]&a[1]^b[7]&a[5]^b[7]&a[6]^b[7]&a[7];
Why is this function?? How to get into this function?

 

[bulx]

hope you are already familiar with GF basics..

one primitve poly for GF(2^8) is
α^8 + α^4 + α^3 + α^2 + 1 = 0

any a GF (256) ele can be written as a power of the primitive element α. take element α^i. It can be written as
α^i = a7 * α^7 + a6 * α^6 + a5 * α^5 + a4 * α^4 + a3 * α^3 + a2 * α^2 + a1 * α^1 + a0

lets multiply above element with the primitve element α
α * α^i = a7 * α^8 + a6 * α^7 + a5 * α^6 + a4 * α^5 + a3 * α^4 + a2 * α^3 + a1 * α^2 + a0 * α^1

using the primitive poly, we can replace α^8
α^ (i+1) = a7 * (α^4 + α^3 + α^2 + 1) + a6 * α^7 + a5 * α^6 + a4 * α^5 + a3 * α^4 + a2 * α^3 + a1 * α^2 + a0 * α^1

which can be written as
α^ (i+1) = a6 * α^7 + a5 * α^6 + a4 * α^5 + (a3 xor a7) * α^4 + (a7 xor a2) * α^3 + (a7 xor a1) * α^2 + (a7 xor a0)
(hope I got that right)

now you can see that 'multiply by α' can be achieved by shift and xor operations. We can just repeat this to multiply α^i by α^2, α^3, α^4, α^5, α^6 and α^7.

Now think about multiplying by any other GF ele. Any GF ele can be written as
α^j = b7 * α^7 + b6 * α^6 + b5 * α^5 + b4 * α^4 + b3 * α^3 + b2 * α^2 + b1 * α^1 + b0

you can see that to get product of α^i and α^j, what we need to multiply α^i by α^1, α^2, α^3, α^4, α^5, α^6 and α^7 and add up. However, not all need to be added up, only those products whose b's are not zero need to be. This is exactly what your expresion does.
-b

 

[pnchldhvl]

Hello,

Do you have truth table for GF Multiplier? I am designing RS encoder & decoder. I need multiplier for same.Can you pls give me truth table for same?
my email id is pnchldhvl@gmail.com

 

[baskin robe]

i want to know the rs encoding steps with each step architecture block so that it would be easy for me to understand and implement in vhdl................plzz help