Puzzle #14 – Multipliers
April 14, 2009Here is an interview question that was circulating some of the message boards lately.
Can you create a 4×4 multiplier with only 2×2 multipliers at hand?
post your answers as a comment to this post.
Advertisements
This question could be interpreted in two ways: (1) is it possible? or (2) how is it done?
The answer to question (1) is *yes*, because a 2×2 multiplier calculating A*B = C can calculate NAND (set a1 = b1 = 1, then c2 = a0 NAND b0), and any logic function can be generated with enough NAND gates. Question (2) would take a little more time…
I’ll do it by taking one example. Otherwise explanation may create some confusion.
take a= 1010 in binary
take b= 0101 in binary
now we want to perform a*b
so 10_10 (a)
* 01_01 (b)
================
step 1:
first we will multiply 10(lsb side of a) with 01(lsb side of b) as we have only 2X2 Multiplier.
so resut will be 10 – we will place this in LSB position of answer , say C so after this step C will be XX_XX_10
step2:
Now we will multiply 10 (LSB side of a) with 01(MSB side of b), which will result in 10
step3:
Now we will multiply 10(MSB side of a) with 01(LSB side of b), which will result in 10
Now we will add the result of step2 and step3 and its result will be kept as further bits of C
so now C will become XX_00_10 with carry 1’b1 on XX
step4:
Now we will multiply 10(MSB side of a) with 01(LSB side of b), which will result in 10
Step5: Put the result of step4 + carry generated by step 3 at MSB position in Answer C
so now C will become 11_00_10
BY this method other examples can also be calculated…
The more complete solution: as tar suggests, we treat the 4-bit inputs as two “digit” radix-4 quantities, call them ab and cd, where a, b, c, and d are each two-bit quantities. We compute the 4 partial products a*c, a*d, b*c, and b*d with 2×2 multipliers. Each of these is 4 bits. The final product is the sum: b*d + (a*d + b*c)<<2 + (a*c)<<4, where I have used “c” notation to indicate the bit shifts. This sum will have 8 bits, the lowest two of which are the lowest two bits of b*d, the next two include the sum of the lower 2 bits of a*d and b*c and the upper bits of b*d, the next two include the sum of the upper bits of a*d and b*c, the lower bits of a*c, and the carry from the previous sum, and finally, the uppermost two bits are the sum of the upper two bit of a*c and the carry from the sum just mentioned.
Of course, doing all these sums requires some adders as well, but conveniently, we note that a 2×2 multiplier can be converted to a half-adder by setting the upper bit of each input to ‘1’ — we then find that bit 1 (the “2’s place”) of the output is the sum (XOR) of the lower bits of the inputs, and that either bit 3 or bit 0 is the carry (AND). We can combine these as needed to do all of the additions, though I haven’t counted how many are needed — it may be quite a few, given that several intermediate results must be summed and several half-adders are needed even to make one full-adder.
By the way, I assume we are doing unsigned multiplies here; I don’t really want to think about doing this with signed multiplies…
module top;
reg [3:0]a;
reg [3:0]b;
reg [4:0]temp3;
reg [4:0]temp4;
reg [4:0]temp5;
reg [4:0]temp6;
reg [7:0]c;
initial
begin
a = 4’b1111;
b = 4’b1111;
temp3 = 0;
temp4 = 0;
temp5 = 0;
temp6 = 0;
temp3 = a[1:0]*b[1:0]; //two bit multiplication
c[1:0] = temp3[1:0];
temp4 = a[3:2]*b[1:0]; //two bit multiplication
temp5 = a[1:0]*b[3:2];
c[3:2] = temp4+temp5+temp3[4:2];
temp6 = temp4+temp5+temp3[4:2];
//two bit multiplication
c[7:4] = (a[3:2]*a[3:2])+temp6[4:2];
$display(“The inputs are a=%b, b = %b, a*b = %b”, a,b,c);
end
endmodule
The only issue I see with these answers is that they have used adders inadvertently whereas teh question said we only have multipliers at hand.
What if the 2X2 bit multiplier results in a four bit output?
That case is not mentioned above, If it would have been mentioned it would have been best.