Electronic – 3-bit multipliers – how do they work

digital-logicmultiplier

I need to understand how 3-bit multipliers work and then I must design one. I've read through Wikipedia's binary multiplier but I just can't wrap my head around it. I don't understand where to start. Could you please explain to me what happens when two 3-bit numbers are run through a 3-bit multiplier? Maybe then I can reconstruct each step in a circuit on paper. Alternatively, could you outline the relevant sub-concepts I need to grasp?

In general, I'm thankful for any help in understanding 3-bit multipliers.

EDIT: Thank you to everyone who contributed to this Question. You all helped me understand the relevant concepts, and so I wish I could accept all answers as solutions.

Best Answer

If you're a EE/CPE student and you're just starting to learn logic, maybe you haven't learned this yet but you will.

Arithmetic and logic functions are essentially realized in circuit form by starting with a truth table and filling in the values that implement the function you want. For 2x2 bit multiplication, this is the truth table:

From the program Logic Friday

Go through each row, and you'll see how it implements it. It is in the form A0,A1 * B0,B1 = F0,F1,F2,F3

Sorry, it's backwards as typically the LSB is A0 or B0, I numbered it wrong. Anyways, take for instance the last row. It says 11 * 11 = 1001. In decimal, that's just 3 * 3 = 9

After the truth table is complete, you could fill this into a karnaugh map, and derive the equations for each output of the circuit. In this case, I let this handy program do it for me.

The output came to this.

Logic Friday

At this point, you can see that I have an equation for F0 through F3 based on the inputs. Now I just need to throw in the logic gates to match those equations. And voila, you have a circuit that performs binary multiplication.

This is the simplistic side of it. Real processors and the ALUs inside of them don't exactly do it this way. For instance on a 64-bit computer, the amount of combinational logic necessary to perform 64x64 bit multiplication would be insane. Instead, as the wikipedia article you read states, they multiply one of the 64-bit operands by each individual bit of the 2nd operand, each time shifting the result. Finally, they add all of the partial sums together. That is the absolute most simplistic method of performing the multiplication sequentially. Some processors though have even faster multiply implementations that make use of wallace trees

Also, if you'd like a little more insight on the sequential type multiplier, here you go. This may be a little more difficult so don't worry about understanding how each of the components works underneath, because you will learn it soon. I leared shift registers, ALUs, and all that by the end of my first digital logic course.

This image comes from http://faculty.kfupm.edu.sa/COE/mimam/files/COE200experiment13.pdf

This is a simplified 4x4 bit version, and it goes sort of like this:

1) The 4-bit multiplier is loaded and stored in the P shift register, specifically Pl. Also, the 4-bit multiplicand is stored in the B-register. Ph is all 0's

2) On each clock cycle, the P register is shifted to the right, and the rightmost bit, P0, is sign-extended (not shown, to make it 4 bits), and ANDed with the multiplicand in the B-register. If you go back to the binary multiplier page on wikipedia, under multiplication basics, the 2nd grey area, you can see this happening with each staggered row, it is an AND operation that essentially does the multiplication since each time it is either multiplicand x 0, or multiplicand x 1.

Since the ALU is performing the add operation, the result of the 1 bit multiplication is added to the previous partial sum, in this case 0 since this is the first step, and stored in Ph.

3) On the next cycle, the P register is again shifted, and so you can see how the Ph output gets shifted and added again to the result of the 1-bit multiplication.

4) At the end, you have an 8-bit result stored in the p register.

Related Solutions

Connecting multipliers to increase operation bit width

Yes there is functional block that can be used to create any N*N multiplier, it's called an array multiplier cell and it looks like this:

enter image description here

A non-optimised NN multiplier will use NN array multiplier cells.A circuit that uses these cells to make a 4*4 multiplier can be seen below

enter image description here

where m and p are the numbers being multiplied together and p is the result.

For a detailed explanation of how this circuit works you can search for "array multiplier" on google, there should be lots of information on it, but the basic idea is that at every stage of multiplication we will either be adding zero or m (the multiplicand).What decides if we add m or zero at stage n is the value of n th bit of q, so we use the nth bit of q and an AND gate to multiplex between m and zero at every stage.

Electronic – Bit compression in Verilog

You can get this to work if you replace the non-blocking assignments with blocking assignments. It is still not readily synthesizable, but it would be OK as a testbench. Example below.

Non-blocking assignments which use <= don't take effect immediately, but rather are delayed until a later point in time, which can be thought of as the end of the current time step. Since all the for loops are inside the same time step, if they use non-blocking assignments, they schedule a series of events to occur at the end of the current time step. So thefor j and for k loops always see the initial values of the array. As this algorithm is expressed, it is necessary for these two loops to be working with the data after the swap has occurred.

module compressMe();

  reg [15:0] p0;
  reg [15:0] p1;
  reg [15:0] p2;
  reg [15:0] p3;
  reg [15:0] p4;
  reg [15:0] p5;
  reg [15:0] p6;
  reg [15:0] p7;

  reg [15:0] pp [7:0];

  integer i,j,k;

  reg swapTemp;

  initial
    begin
      p0 <= 16'b0000000000000000;
      p1 <= 16'b1111111111111111;
      p2 <= 16'b0000000000000000;
      p3 <= 16'b1111111111111111;
      p4 <= 16'b0000000000000000;
      p5 <= 16'b1111111111111111;
      p6 <= 16'b0000000000000000;
      p7 <= 16'b1111111111111111;
  end

  always @ (p0 or p1 or p2 or p3 or p4 or p5 or p6 or p7)
    begin
    pp[0] = p0;
    pp[1] = p1;
    pp[2] = p2;
    pp[3] = p3;
    pp[4] = p4;
    pp[5] = p5;
    pp[6] = p6;
    pp[7] = p7;

    for (i=0; i<=15; i=i+1)
      begin
          for (j=7; j>=1; j=j-1)
          begin
            for (k=j-1; k>=1; k=k-1)c
                beginc
                if (    ( !pp[j][i] )     &&    (  pp[k][i]  )    )   
                  begin
                  swapTemp = pp[j][i];
                  pp[j][i] = pp[k][i];
                  pp[k][i] = swapTemp;
                  end
                end
            end
        end
  end


  initial
    begin
    #100 for (i=0; i<=7; i=i+1)
        $display("pp[%d] = %16b ", i, pp[i]);
    end


endmodule

This will produce:

 ncsim> run
 pp[          0] = 0000000000000000 
 pp[          1] = 0000000000000000 
 pp[          2] = 0000000000000000 
 pp[          3] = 0000000000000000 
 pp[          4] = 1111111111111111 
 pp[          5] = 1111111111111111 
 pp[          6] = 1111111111111111 
 pp[          7] = 1111111111111111

Best Answer

Related Solutions

Connecting multipliers to increase operation bit width

Electronic – Bit compression in Verilog

Related Topic