## 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…

by Alex R April 15, 2009 at 12:04 amI’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…

by tar April 15, 2009 at 1:02 pmThe 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…

by Alex R April 15, 2009 at 6:24 pmmodule 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);

by shishira mohan pareppady July 20, 2009 at 9:18 amend

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.

by Mike August 4, 2011 at 5:19 amWhat if the 2X2 bit multiplier results in a four bit output?

by Ganesh September 29, 2013 at 10:19 pmThat case is not mentioned above, If it would have been mentioned it would have been best.