Objectives

To practice the combinational design process through the design of a 4-bit multiplier.

Introduction

This lab will be unlike previous labs in two very significant ways. First, we're going to design circuits that are too complex to fit on our breadboard with the parts in the lab kit, so this lab will be done entirely with the simulator. Second, though this lab writeup will provide some insights into a possible design of a multiplier, no circuit diagrams will be provided - you'll do the design yourself (woohoo. OK, now this time with enthusiasm, this is what you're here for: Woohoo!).

The circuit you will be designing is a 4-bit multiplier, i.e. a circuit with two 4-bit numbers as inputs, and the 8-bit product of these two numbers as the output.

A truth table for this circuit would have 8 inputs, 8 outputs, and 256 lines. You would need eight 8 variable K-maps to directly produce boolean equations. So there's no way around it, we're going to have to think some about this one. The following section describes the multiplication process in detail, in terms of steps we've already figured out how to do. After that, it's up to you.

Background

The first thing you need to know about multiplication is that the AND operation will multiply two bits together. It works just like decimal multiplication, 1*1=1, and 0*0=0*1=1*0=0. AND even has the same symbol as decimal multiplication. So, if you need to multiply a number by a single bit, you can just use a bunch of AND gates. Consider the example below:

Things get a little more complicated when your multiplier has more than one bit. AND is a binary operation. We can only AND something with one bit at a time. So, how do we multiply multi-bit numbers together? Well, one way to devise the circuit is to do things the same way we do in our head: multiply the number by a single bit of the second number, then add that result to the one you get by multiplying by a second bit, and so on, as in the example below:

				1	0	1	1
X				1	1	0	1
				1	0	1	1
			0	0	0	0
		1	0	1	1
+	1	0	1	1
1	0	0	0	1	1	1	1

Note that we get an eight bit number from multiplying two four bit numbers.

In the general case, we can rewrite the problem symbolically below, where P_ij is the product (AND) of bit i of the multiplicand (top number) with bit j of the multiplier, and S_i is the sum of the column of numbers above it.

				A3	A2	A1	A0
X				B3	B2	B1	B0
				P30	P20	P10	P00
			P31	P21	P11	P01
		P32	P22	P12	P02
+	P33	P23	P13	P03
C6	S6	S5	S4	S3	S2	S1	S0

That's pretty close to something we can build. We can multiply by single numbers, and we can add numbers together. The only complication is the adders we know how to build can only add two numbers at a time. In this case we need to add whole columns of numbers, so we might want to create some partial sums to make use of the adders we have. A possible way to do this is shown below:

				A3	A2	A1	A0
X				B3	B2	B1	B0
				P30	P20	P10	P00
+			P31	P21	P11	P01
		S14	S13	S12	S11	S10	P00
+		P32	P22	P12	P02
	S24	S23	S22	S21	S20	S11	P00
+	P33	P23	P13	P03
S34	S33	S32	S31	S30	S20	S10	P00

where S_ij represents the jth output of the ith adder. Note that at each stage you need a 4-bit adder (which would have five outputs), and keep in mind that you have already built four bit adder macros in an earlier lab.

Procedure

Design it, simulate it, turn it in.

Bring an electronic copy of your design to lab with you, and be prepared to demonstrate the operation of your functional multiplier (Add appropriate switches and lights so you can input two 4-bit numbers and see your 8-bit output). Make sure your work is your own! Turn in a printout of your final schematic, plus printouts of any macros you used in your designs as well. Also turn in a brief report describing your circuit design. In your report, consider if and how well this circuit design would scale up to multiplying bigger numbers. Also, answer the following questions in your report:

• What would be the strengths and weaknesses of a large multiplier built in this fashion?
• What would the propagation delay be for the circuit in your simulation, assuming a 1 ns delay for each gate?

A note for those who are interested