# Why is my Karatsuba multiplier not giving right answers for large numbers?

I tried to implement 16-Bit Karasutba Multiplier in Verilog HDL. It gives me right answers for small numbers, but it's incorrect for large numbers.

Can someone point out what's wrong?

Here's the design:

module karatsuba_2x2(
input [1:0] a,
input [1:0] b,
output [3:0] out
);

wire temp;

assign out[0]= a[0] & b[0];

assign out[1] = (a[1] & b[0]) ^ (a[0] & b[1]);
assign temp =  (a[1] & b[0]) & (a[0] & b[1]);

assign out[2] = temp ^(a[1] & b[1]);
assign out[3] = temp &(a[1] & b[1]);

endmodule

module karatsuba_4x4(
input [3:0] a,
input [3:0] b,
output [7:0] out
);

wire [3:0] ac, bc, ad, bd;
wire [7:0] t1, t2;
wire [6:0] psum;

karatsuba_2x2 k1(.a(a[3:2]), .b(b[3:2]), .out(ac));
karatsuba_2x2 k2(.a(a[1:0]), .b(b[3:2]), .out(bc));
karatsuba_2x2 k4(.a(a[1:0]), .b(b[1:0]), .out(bd));

assign t2 = bd;
assign t1 = {ac, 4'b0000};
assign out = t1 + t2 + psum;

endmodule

module karatsuba_8x8(
input [7:0] a,
input [7:0] b,
output [15:0] out
);

wire [7:0] ac, bc, ad, bd;
wire [15:0] t1, t2;
wire [12:0] psum;

karatsuba_4x4 k1(.a(a[7:4]), .b(b[7:4]), .out(ac));
karatsuba_4x4 k2(.a(a[3:0]), .b(b[7:4]), .out(bc));
karatsuba_4x4 k4(.a(a[3:0]), .b(b[3:0]), .out(bd));

assign t2 = bd;
assign t1 = {ac, 8'b0000};
assign out = t1 + t2 + psum;
endmodule

// Top Module
module karatsuba_16x16(
input [15:0] a,
input [15:0] b,
output [31:0] out
);

wire [15:0] ac, bc, ad, bd;
wire [31:0] t1, t2;
wire [24:0] psum;

karatsuba_8x8 k1(.a(a[15:8]), .b(b[15:8]), .out(ac));
karatsuba_8x8 k2(.a(a[7:0]),. b(b[15:8]),. out(bc));
karatsuba_8x8 k4(.a(a[7:0]),. b(b[7:0]),. out(bd));

assign t2 = bd;
assign t1 = {ac, 16'b0000000000000000};
assign out = t1 + t2 + psum;

endmodule


Here's the testbench:

module tb;
reg [15:0] a,b;
wire [31:0] out;

karatsuba_16x16 DUT(a,b,out);

initial begin
{a,b} = 0;

$monitor("a = %d | b = %d | out = %d", a,b,out); #2 a = 'd3; b = 'd3; #2 a = 'd65535; b = 'd3; #2 a = 'd65535; b = 'd33333; #2 a = 'd65535; b = 'd50000; #2$finish;
end

endmodule


Here's the output:

It calculates (65535 x 33333) correctly but (65535 x 50000) incorrectly.

• @toolic 2x2, 4x4 and 8x8 modules are working fine. I checked them for all possible combinations. The problem lies in the 16x16 module. It's giving a correct answer till (65535 x 33342). From (65535 x 33343) onwards it's giving an incorrect answer less than the correct answer. Eg: (65535 x 3343) gives 2,184,853,889 instead of 2,185,133,505. Commented Jul 14, 2023 at 12:25
• see my answer.... Commented Jul 14, 2023 at 12:30
• I think your 2×2 nice. But none of this "is Karatsuba". For starters, the whole point is each level using 3 smaller multipliers instead of 4. (And the tag multiplier doesn't apply, as it isn't even about "analogue" voltage multipliers.) Commented Jul 15, 2023 at 4:20
• @greybeard Yea, i realised that too. So, i tried implementing the actual Karatsuba multiplier. But there too, i am facing issues. If you can, then pls look into this Commented Jul 15, 2023 at 5:07

That's a lot of code to go through, so you can break the problem down to debug it: thoroughly check the 2x2 module to make sure it works. Then check the 4x4 module, etc. This should narrow your problem down.

I checked 2x2, and it is fine.

There is a problem with 4x4. With the following small testbench, I get an error when a and b hit their maximum values (15):

module tb;
reg [15:0] a,b;
wire [7:0] out4;

karatsuba_4x4 DUT4(a[3:0], b[3:0], out4);

initial begin
for (int i=0;i<16;i++) begin
for (int j=0;j<16;j++) begin
#1;
a=i; b=j;
#1;
$display(a,,b," = ",out4); if (out4 !== (a*b))$display("ERROR");
end
end
#2 \$finish;
end
endmodule


Here is a snippet of the output:

   15    12 = 180
15    13 = 195
15    14 = 210
15    15 = 161
ERROR


This is fixed by changing:

assign psum = {bc+ad, 2'b00};


to:

assign psum = (bc+ad) << 2;


Use the shift-left operator (<<) for psum in the 8x8 and 16x16 modules as well.

assign psum = (bc+ad) << 4;
assign psum = (bc+ad) << 8;


With these changes, I get the output you expect:

a =     0 | b =     0 | out =          0
a =     3 | b =     3 | out =          9
a = 65535 | b =     3 | out =     196605
a = 65535 | b = 33333 | out = 2184478155
a = 65535 | b = 50000 | out = 3276750000


There are subtleties associated with using the concatenation operator ({}) regarding signal bit widths. Refer to IEEE Std 1800-2017, Table 11-21— Bit lengths resulting from self-determined expressions. The problem with your code is that items in a concatenation are self-determined. The item bc+ad is self-determined, meaning the length of the expression for the + operator is determined by the 2 terms, both of which are 4-bit. So, the sum is truncated to 4-bit, instead of the desired 5-bit.