CS-341 Assignment 9

Serial Multiplier Design

Complete the design for the serial multiplier started in class on November 6. The following paragraphs describe the design which is based on the multiplier shown in the text on pages 69-71.

There are two parts to the multiplier, the datapath and the controller. The datapath consists of the registers m, q, c, and a plus the parallel adder. The controller is a finite state machine that generates the signals to cause the datapath to perform the proper sequence of operations.

The multiplier There is one external input signal, called start, and an external output signal called wait. In class I named wait with a bar over it to indicate that it is "active low." That is, when it is zero it indicates that the rest of the datapath should wait for the multiplication to complete. In this web page I'm leaving the bar out (because no way to draw one in html.)

As in the normal ALU design, there are also 4-bit external data inputs named A and B that, for multiplication, supply the multiplicand and multiplier respectively. The a and q registers serve as external data outputs for the product.

Internally, there are four control signals: initialize, add, shift, and the value of q0. The first three are used to control the datapath of the multiplier, and the last one helps determine the state transitions of the controller.

Control Signal Datapath/Controller Operation
initialize Load register m from the A inputs, load register q from the B inputs, and clear registers c (the single flip-flop that captures the carry out of the adder) and a.
add Register a gets the sum of itself and register m.
shift Shift registers c, a, and q (treated as a single 9-bit unit) to the right one place. This can be either an arithmetic or logical shift (or even a circular shift) because the value of c will be overwritten by the result of adding in the following state.
q0 Used to control whether to add or shift in the next state.

Datapath Design

Here is a shortcut that can make design of the datapath easier. There are three variables that control the datapath, initialize, add, and shift, suggesting that there are eight combinations of inputs to consider. But the three control signals are mutually exclusive: no more than one will ever be true at a time. (You have to understand the operation of the multiplier, as described in the text, to see this.) So the design of the datapath can be simplified by generating two intermediate control signals, which I'll call x1 and x0, as follows:

init  add  shift x1  x0
0  0  0 0  0
0  0  1 0  1
0  1  0 1  0
1  0  0 1  1

You can use these two signals to control all the multiplexors for all the flip-flops in all the registers. You just have to connect the correct source of data for each input of each multiplexor.

Controller Design

The purpose of the controller is to generate the values for the control inputs to the datapath, initialize, add, and shift, plus the external output, wait.

I suggest you start implementing the control section with a 4-bit state register named s. Connect the outputs of s to a decoder with outputs named state0, state1, ... state15. (The outputs numbered 9-15 won't be connected to anything because you need only 9 states.) The remainder of the control section design is to show how to produce the D inputs for each of the bits of s (the "next state"), as well as the internal inputs, initialize, shift, and add. (You don't have to do anything about q0 because it is just the Q output of the rightmost flip-flop of register q.)

With all the forgoing material in mind, the behavior of the controller can be described as follows:

State Description
0 The controller remains in this state, with wait equal to 1 ("deasserted") for as long as start is 0. When start becomes 1, wait immediately goes to 0, initialize goes to 1, and on the next clock pulse, the controller goes into either state 1 or state 2, depending on the value of q0.
1 During this state, the add signal should be 1. The next clock pulse puts the controller into state 2.
2 During this state, the shift signal should be 1. The next clock pulse puts the controller into either state 3 or state 4, depending on the value of q0.
3 During this state, the add signal should be 1. The next clock pulse puts the controller into state 4.
4 During this state, the shift signal should be 1. The next clock pulse puts the controller into either state 5 or state 6, depending on the value of q0.
5 During this state, the add signal should be 1. The next clock pulse puts the controller into state 6.
6 During this state, the shift signal should be 1. The next clock pulse puts the controller into either state 7 or state 8, depending on the value of q0.
7 During this state, the add signal should be 1. The next clock pulse puts the controller into state 8.
8 During this state, the shift signal should be 1. The next clock pulse puts the controller into state 0.

Create a state table based on the above description, use it to derive the logic equations for wait, initialize, shift, add, and the D inputs for each bit of state register s. Then complete your design by implementing these functions in your diagram for the entire multiplier.

Note that add and shift follow the Moore state machine model in that their values depend only on the state of the controller. But initialize and wait follow the Mealy model in that their values depend both on the state of the controller and the values of external inputs. What would have been the effect of implementing the controller as a pure Moore machine? (Answer: One more state would have been needed, an overhead of anywhere from 12.5 to 20% added to the time required to complete a multiply operation.)

You do not have to draw a state diagram because the controller described mixes Mealy and Moore behavior, making a state diagram difficult to draw in a consistent fashion for all states and arcs. (Challenge: can you do it anyway?)

Due Date

This homework is to be done on paper, and must be brought to class on Friday, November 9.


See the [ Course Administration Page ] for information on the homework policy for this course.