Large (256x256) Multiplier in verilog

[malikkhaled]

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

---

 

[pbernardi]

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.

 

[malikkhaled]

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

 

[pbernardi]

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?

 

[ads-ee]

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