A multiplier is an arithmetic combinational logic circuit which multiplies a M-bit binary number with an N-bit binary number and outputs the (M+N)-bit binary product. The method shown here is probably the simplest of all multiplier designs.

In school you were probably taught to multiply multi-digit numbers by breaking the problem down into simpler single-digit multiplications. For example, if we were to multiply 123 by 32, then we would no doubt write down something like this:

` ````
123
x 32
----
(x2) 246
(x3) 369
----
(+) 3936
```

Here we have turned the multi-digit multiplication into two single-digit multiplications and an addition of the intermediate products. A digital circuit can be built to perform the same steps in parallel (i.e., a combinational, not a sequential step-by-step, circuit). The key to binary multiplication is the realisation that the multiplication of two bits is performed by a simple AND gate. To multiply a M-bit number by a single bit, in order to generate an intermediate product, we would need M AND gates. An adder, such as a ripple carry adder can be used to perform the summation of the intermediate products. When we multiply a M-bit number by an N-bit number we would need N-1 such adders. As for the final result, it will need at most M+N bits for storage.

As an example, consider the multiplication of two 3-bit numbers, A and B, giving the product P. We'll write P5 for bit 5 of P, and A0B1 for bit 0 of A multiplied by bit 1 of B. Bit 0 will be the least significant bit. The plan of action would be:

` ````
A2 A1 A0
x B2 B1 B0
---------------
A2B0 A1B0 A0B0 (P0 = A0B0)
+ A2B1 A1B1 A0B1
----------------------
S3 S2 S1 S0 (P1 = S0, S3 is the carry out of the above addition)
+ A2B2 A1B2 A0B2
------------------
P5 P4 P3 P2 (P5 is the carry out of the above addition)
```

From this we can see how we should configure our two ripple carry adders and nine AND gates.

The following Verilog code implements a 4-bit multiplier. The code for the ripple carry adder and the full adder is also shown for completeness.

` ````
module multiplier(P, A, B);
output [7:0] P; // The 8-bit product.
input [3:0] A; // The 4-bit multiplicand.
input [3:0] B; // The 4-bit multiplier.
wire [3:0] Augend0; // Input to first intermediate addition.
wire [3:0] Addend0; // Input to first intermediate addition.
wire [3:0] Sum0; // First intermediate sum.
wire Carry0; // Carry output of first intermediate addition.
wire [3:0] Addend1; // Input to second intermediate addition.
wire [3:0] Augend1; // Input to second intermediate addition.
wire [3:0] Sum1; // Second intermediate sum.
wire Carry1; // Carry output of second intermediate addition.
wire [3:0] Augend2; // Input to last addition.
wire [3:0] Addend2; // Input to last addition.
//
// Augend0 = (A * B[0]) rshift 1
//
and(P[0], A[0], B[0]); // Bit 0 goes straight to P.
and(Augend0[0], A[1], B[0]);
and(Augend0[1], A[2], B[0]);
and(Augend0[2], A[3], B[0]);
assign Augend0[3] = 0;
//
// Addend0 = A * B[1]
//
and(Addend0[0], A[0], B[1]);
and(Addend0[1], A[1], B[1]);
and(Addend0[2], A[2], B[1]);
and(Addend0[3], A[3], B[1]);
ripple_carry_adder rc0(Sum0, Carry0, Augend0, Addend0); // {Carry0, Sum0} = Augend0 + Addend0
assign P[1] = Sum0[0];
//
// Augend1 = (Augend0 + Addend0) rshift 1
//
assign Augend1[0] = Sum0[1];
assign Augend1[1] = Sum0[2];
assign Augend1[2] = Sum0[3];
assign Augend1[3] = Carry0;
//
// Addend1 = A * B[2]
//
and(Addend1[0], A[0], B[2]);
and(Addend1[1], A[1], B[2]);
and(Addend1[2], A[2], B[2]);
and(Addend1[3], A[3], B[2]);
ripple_carry_adder rc1(Sum1, Carry1, Augend1, Addend1); // {Carry1, Sum1} = Augend1 + Addend1
assign P[2] = Sum1[0];
//
// Augend2 = (Augend1 + Addend1) rshift 1
//
assign Augend2[0] = Sum1[1];
assign Augend2[1] = Sum1[2];
assign Augend2[2] = Sum1[3];
assign Augend2[3] = Carry1;
//
// Addend2 = A * B[3]
//
and(Addend2[0], A[0], B[3]);
and(Addend2[1], A[1], B[3]);
and(Addend2[2], A[2], B[3]);
and(Addend2[3], A[3], B[3]);
ripple_carry_adder rc2(P[6:3], P[7], Augend2, Addend2); // {P[7], P[6], P[5], P[5], P[3]} = Augend2 + Addend2
endmodule // multiplier
module ripple_carry_adder(S, C, A, B);
output [3:0] S; // The 4-bit sum.
output C; // The 1-bit carry.
input [3:0] A; // The 4-bit augend.
input [3:0] B; // The 4-bit addend.
wire C0; // The carry out bit of fa0, the carry in bit of fa1.
wire C1; // The carry out bit of fa1, the carry in bit of fa2.
wire C2; // The carry out bit of fa2, the carry in bit of fa3.
full_adder fa0(S[0], C0, A[0], B[0], 0); // Least significant bit.
full_adder fa1(S[1], C1, A[1], B[1], C0);
full_adder fa2(S[2], C2, A[2], B[2], C1);
full_adder fa3(S[3], C, A[3], B[3], C2); // Most significant bit.
endmodule // ripple_carry_adder
module full_adder(S, Cout, A, B, Cin);
output S;
output Cout;
input A;
input B;
input Cin;
wire w1;
wire w2;
wire w3;
wire w4;
xor(w1, A, B);
xor(S, Cin, w1);
and(w2, A, B);
and(w3, A, Cin);
and(w4, B, Cin);
or(Cout, w2, w3, w4);
endmodule // full_adder
```

When given test inputs, the 4-bit multiplier generated the following waveform (values in decimal):

Mano, M. Morris, and Kime, Charles R. *Logic and Computer Design Fundamentals. 2nd Edition.* Prentice Hall, 2000.

Copyright © 2014 Barry Watson. All rights reserved.