h1

Puzzle #14 – Multipliers

April 14, 2009

Here 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.

About these ads

5 comments

  1. 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…


  2. 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…


  3. 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…


  4. 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


  5. 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.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 99 other followers

%d bloggers like this: