Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Galois Field multiplier

Status
Not open for further replies.

max420

Newbie level 5
Joined
Nov 30, 2010
Messages
8
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,358
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.
 

permute

Advanced Member level 3
Joined
Jul 16, 2010
Messages
923
Helped
295
Reputation
590
Reaction score
268
Trophy points
1,343
Activity points
8,543
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.
 

tariq786

Advanced Member level 2
Joined
Feb 24, 2004
Messages
562
Helped
67
Reputation
134
Reaction score
52
Trophy points
1,308
Location
USA
Activity points
3,043
Hi,
can you please tell me the internet source of galois field equations?

Thanks
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top