# CS201 Lab: Integer Multiplier

## Objectives

```
Review Integer Multiplication
Examine the Hardware Implementation Procedure
Review the 4-bit Adder device and use it in multiplier circuits
Review the 4-bit shifft register device and use it in multiplier circuits
Build a 4-bit multiplier circuit and test it

```

## A Note:

```
The ALU is an important part of any computer.
Building an integer multiplier will give us insight of
how machines could multiply numbers and
it will introduce us to some of the issues of control unit operation.

```

## Review of Integer Multiplier

• Pencil and Paper Approach
• ```
Here is an example that requires a 2n-bit adder.

1 0 1 1	  Multiplicand (11)
x 1 1 0 1   Multiplier (13)
----------------
1 0 1 1
0 0 0 0
1 0 1 1	  Partial Products
+ 1 0 1 1
----------------
1 0 0 0 1 1 1 1   Product (143)

```
• Hardware Approach
• ```
Algorithm  of (M x Q):

1.	Initilization:
A (n-bit) = 0;
C (1-bit) = 0;
Counter   = n;

2.	Repeat the following steps until Counter = 0:
a) If Q0 (LSB of Q) = 1, then C A = A + M, and
Shift C, A, and Q one bit to the right simultaneously.
b) If Q0 (LSB of Q) = 0, then
shift C, A, and Q one bit to the right simultaneously.
c) Counter = Counter - 1.

3.	Halt.  The product is in A and Q.

```
• Implementation
• ```
Basic Components:

a) Register M (n-bit): Stores multiplicand.
b) Register Q (n-bit): Stores multiplier.
c) Register A (n-bit): Initialized to zero to store
the partial product.
d) n-bit Adder: Performs addition when Q0 (LSB of Q) is one.
e) Register C (1-bit):	Holds the end carry of the adder.
C, A, Q can be shifted to right simultaneously.
f) Control Logic:  includes number of iterations and
addition and shift operation.

``` ## Using 4-bit Adder

```
Build the following circuit.
Obtain the "Adder-4" from the Simulation Logic library. It demonstrates the following:

1.	How to use the Hex display and Keyboard.

2.	How to use the 4 bit adder put hex keyboards on the inputs,
a binary probe on the CO (carry out) line,
a binary switch on the CI (carry in) line,
and a hex display on the output.

```

## Using 4-bit Shift Register

```
Build the following circuit.
Obtain the "Shift Reg-4" from the Simulation Logic library. It demonstrates the following:

1.	How to use the 4 bit shift register.

2.	How to use the Load and Shift modes.

3.	How to use individual probes on each output to make
it easier to see what's happening in shift mode.

4.	Shifting direction is SI -> Q0 -> Q1 -> Q2 -> Q3.

With LD set to 1:

The register is in shift mode.
The SI (shift input) line is used to set the value to be shifted
into the register. Clocking is positive edge triggered.

With LD set to 0:

The register is in parallel load mode.
Inputs D0 to D3 become outputs Q0 to Q3 on the next rising clock pulse.

```

## Algorithm of using the mutiplier circuit

```
For the multiplier circuit: You do not build a control unit.
You will be the brains of the circuit.
The algorithm to use the circuit will be something like:

Load up the Q register with the multiplier:
LD of Q<- 0
toggle the Q clock

Clear the A register:
LD of A<- 1
toggle the clock until clear

Repeat 4 times:
---------------
IF (LSB of Q = 1)
{
ADD M register to A register:
toggle the C clock
LD of A<- 0
toggle the A clock

Shift C__A__Q:
LD of Q <- 1
toggle the Q clock
LD of A <- 1
toggle the A clock
}
ELSE (LSB of Q = 0)
{
Shift C__A__Q :
LD of Q <- 1
toggle the Q clock
LD of A <- 1
toggle the A clock
}

```

## Assignments Copyright: Department of Computer Science, University of Regina.