Continue to Site

# Galois Field multiplier

Status
Not open for further replies.

#### max420

##### Newbie level 5
Is it possible to implement a 5 bit Galois Field multiplier?I found the equations for 8bit in the net which is given below:

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

can anyone say me the equations for 5 bit?thank you.

It clearly depends on the choice of connection polynomial.

For reference, a Galois Field is formed by creating a "primitive" element. The actual value of which is essentially unimportant -- it acts like the imaginary number does. It is the root of an equation that has neither 1, nor 0 as a root (an irreducible polynomial). In this case, a rule can be written similar to the rule for i^2 = -1. For your case, one possible case would be a^5 = a^4 + a^2 + 1. again, it is very important not to become overly concerned with the "value" of "a". (I might have the connection polynomial incorrect above, I haven't check it rigorously)

now, all GF32 elements can be written as b4*a^4 + b4*a^4 + ... b0*a^0. again, the value of "a" is unimportant, what is important is the rule that a^5 = a^4 + a^2 + 1.

From here, it is a task of multiplication and reduction. a second GF32 element might have an equation c4*a^4 + ... + c0*a^0.

the product of the two elements is c4*b4*a^8 + (c3*b4 + c4*b3)*a^7 + ... a0*b0, where the terms for each power of "a" is the terms of c/b which add up to that power. (4,4; 4,3 3,4; 3,3 4,2 2,4; ...)

Now reduction is done. if a^5 = a^4 + a^2 + 1, then a^6 = a*a^5. likewise a^7 = a^2 * a^5, etc... using this reduction rule will allow the 8th order polynomial to be reduced back to the 4th order one desired.

other methods exist. the above is the easiest to explain.

Hi,
can you please tell me the internet source of galois field equations?

Thanks

as mentioned above, there is not a single galois field equation. not a single one per size of galois field. wikipedia has some. you can extract them from the taps given **broken link removed** for fibbonacci LFSRs as well.

Status
Not open for further replies.