Large (256x256) Multiplier in verilog

Status
Not open for further replies.
M

malikkhaled

Junior Member level 1
Joined
Jan 14, 2010
Messages
19
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Location
sweden
Activity points
1,447
I am designing (256x256)-bit Multiplier using DSP blocks available on Xilinx FPGAs. I split operands into several chunks of 64-bits, using Karatsuba technique 256-bit multiplier can be constructed using 3, 128-bit multipliers each of which are further realized by 3, 64-bit multipliers. i have constructed 64-bit multiplier and used it to design 128-bit multiplier as

AXB = 2^128 a1b1+ 2^64(a1b1+a0b0-dxdy)+a0b0; where dx= a1-a0 and dy=b1-b0;

dx and dy can be negative so it requires 2's complement representation. I am confused how to handle this situation here i am also posting my code any help in this regard would be appreciated.

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//// 128-bit multiplier using 3, 64-bit multipliers ///
////  128-bit multiplier ///
`define k1 128
`define k2 64
`define k 255
module mul_128bit(input [`k1-1:0]a,
                        input [`k1-1:0]b,
                        input clk,
                        output [`k-1:0]ab
    );
 
wire [`k1-1:0] a0b0,a1b1,dxdy;
wire [`k2-1:0] dx,dy;
reg [`k1-1:0] r1,r2;
reg [191:0] r3;
reg [`k-1:0]r4;
 
assign dx1= a[`k1-1:`k2]-a[`k2-1:0];// a1-a0
assign dy1= b[`k1-1:`k2]-b[`k2-1:0];// b1-b0
assign ab= r4;//output
//// 64-bit multiplier instantiation
mul_64bit m1(a[63:0],b[63:0],clk,a0b0);
mul_64bit m2(a[127:64],b[127:64],clk,a1b1);
mul_64bit m3(dx,dy,clk,dxdy);
 
 
always@(posedge clk)
begin
r1<= a1b1+a0b0;
r2<= r1-dxdy;                       
r3<={r2,`k2'b0}+a0b0;
r4<={a1b1,`k1'b0}+r3;
end
endmodule
 
Last edited by a moderator:

What FPGA are you using?

To implement this, I think you have to instance manually each DSP, so knowing deep details of your DSP (that can changes depending of FPGA family) is a must.
 

I am using Xilinx virtex-6 family.

Yes you are right i manually instantiated DSPs blocks in my 64-bit multiplier and it works well, the confusion arises in 128-bit multiplication using karatsuba technique. Dx and Dy can be negative so do i need a signed multiplier to multiply (DxDy)? In my project i need 256-bit unsigned multiplier.

thanks
 

I don't know karatsuba technique in details, so I cannot answer it, sorry.

But, once it is only two way (signed vs unsigned), can't you simulate it by yourself both implementations?
 

Have you considered the example on wikipedia https://en.wikipedia.org/wiki/Karatsuba_algorithm they have a representation of the z1 computation that uses the complements and additions instead of subtractions. This will require a modulus calculation though.

Regards
 

Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…