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. |
| 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.
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?)