# Multiplier (Simple)

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.

## Example

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.

## Verilog

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] 	Sum0;    // First intermediate sum.
wire 	Carry0;  // Carry output of first 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.

//
// 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]
//

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]
//

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]
//

endmodule // multiplier

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.

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);