CSE 370
Autumn 1996

Homework #8
Solutions


Data path of CSE370 processor

Pretty much everyone implemented a correct solution for this exercise. There was some confusion about whether a separate tristate buffer was needed, or if the A register's tristate buffer could be used. I accepted both solutions as correct. Below is an ABEL-only implementation of the high-level datapath module. The ALU is exactly the one used from HW 6; see the homework 6 solution for the ALU's details.

MODULE datapath

  interface (In7..In0, LoadA, LoadB, EnaA, ALUop3..ALUop1, clk ->
             Out7..Out0, Zero, Neg, Ovf);

TITLE 'Data path of CSE370 Processor'

"Inputs
	In7..In0, LoadA, LoadB, EnaA	pin;
	ALUop3..ALUop1			pin;
	clk				pin;

"Outputs
	Out7..Out0, Zero, Neg, Ovf	pin istype 'com';

"Submodule interfaces
  alu8bit interface (a7..a0, b7..b0, s2..s0 ->
                     c7..c0, cout, overflow, negative, Zero);
  REG8 interface (d7..d0, ld, en, clk -> q7..q0);

"Submodule instantiations
  alu functional_block alu8bit;
  regA functional_block REG8;
  regB functional_block REG8;

"Aliases
  DataIn  = [In7..In0];
  DataOut = [Out7..Out0];
  DataOp  = [ALUop3..ALUop1];
  regAIn  = regA.[d7..d0];
  regAOut = regA.[q7..q0];
  regBIn  = regB.[d7..d0];
  regBOut = regB.[q7..q0];
  ALUInA  = alu.[a7..a0];
  ALUInB  = alu.[b7..b0];
  ALUOut  = alu.[c7..c0];
  ALUCtrl = alu.[s2..s0];

EQUATIONS

  regA.clk = clk;
  regAIn = ALUOut;
  regA.ld = LoadA;
  regA.en = EnaA;

  regB.clk = clk;
  regBIn = DataIn;
  regB.ld = LoadB;
  regB.en = 1;

  ALUInA = regAOut;
  ALUInB = regBOut;
  ALUCtrl = DataOp;

  DataOut = regAOut;
  Zero = alu.Zero;
  Neg = alu.negative;
  Ovf = alu.overflow;

END
MODULE reg8

  interface (d7..d0, ld, en, clk -> q7..q0);

TITLE '8-bit Register module'

"Inputs
  d7..d0, ld, en, clk		pin;

"Outputs
  q7..q0			pin istype 'reg, buffer';

"Aliases
  D =   [d7..d0];
  Q =  [q7..q0];

EQUATIONS

  Q.oe = en;
  Q.clk = clk;

  WHEN (ld) THEN
    Q := D;
  ELSE
    Q := Q.fb;
  
END

This waveform shows the datapath being put through its paces. In the first clock cycle, we load regB with 7 from the input wires. On the next clock cycle, we move B's 7 into A, and load a new value into B (1). Note that we can do both of these things in the same cycle; that's the neat thing about using registers and synchronizing everything. On the third clock cycle, we add A and B and store the result (8) into A. Finally, we clear A. The gray hash marks on the Out0 line show that the output is being tristated (versus the red hash marks, which represent unknown).

[Datapath waveform]


Katz 8.5

You have a Mealy machine with three flip-flops, two inputs, and six asynchronous outputs. What are the minimum and maximum values for the following in a complete FSM:

Number of states
With 3 flip-flops, there are 3 state bits, for 23 = 8 states. Technically, 8 is both the minimum and maximum; you always have 8 states. It is simply the case that there will sometimes be invalid or dead states the you will never enter. I accepted a minimum value of 1 as correct.

Number of transitions arrows leaving a state
In a complete state diagram, there is a separate transition arrow for each input combination. So there are 22 = 4 transitions. This value is both the minimum and maximum.

Number of transition arrows entering a state
At the very least, there might not be any arrows ending in a state: the minimum is 0. On the other extreme, all the arrows in the entire diagram might end in the same state. So there is a maximum of (max number of states) * (max number of transitions per state) = 32 arrows that can end in one state.

Number of different binary patterns that can occur on the outputs
As the minimum the output might be the same for all state and input combinations: 1 pattern. On the other hand, there might be a different pattern for each input/state combination. The max value is also bounded by the number of possible output patterns that can be generated with the given number of output bits. So the maximum different patterns is the min{(number of inputs)*(number of states), 2output bits} = min{32, 64} = 32.


Katz 8.6

You now have a Moore machine with five flip-flops, three inputs, and nine outputs. What are the minimum and maximum values for the following in a complete FSM:

Number of states
With 5 flip-flops, there are 5 state bits, for 25 = 32 states. Just as with the Mealy machine case, 32 is both the maximum and minimum number of states. An answer of 1 for the minimum state count was also accepted as correct.

Number of transitions arrows leaving a state
Same math as with the Mealy machine. Maximum and minimum are both 2number of inputs = 23 = 8.

Number of transition arrows entering a state
Again, same as Mealy. Minimum: 0. Maximum: (max states) * (max transitions per state) = 32 * 8 = 256.

Number of different binary patterns that can occur on the outputs
Not the same as Mealy. The difference is that the output of a Moore machine depends only on the state, not on the inputs.

The minimum number of different patterns is still 1, because the output might be constant for all states. If the output were different for all states, there would be (number of states) different patterns. This is tempered by the number of output bits, though. The maximum is thus the minimum of these values: min{(number of states), 2output bits} = min{32, 512} = 32.


Katz 8.11

The exersize here was to emphasize the difference between Moore machines, asynchronous Mealy machines, and synchronous Mealy machines. Below is a schematic for the Vending Machine control. In this particular example, the Moore and Mealy machines have identical state diagrams and transitions. The only difference is in how the outputs are computed.

In the schematic below, the state machine is implemented. The only output, Open, is computed by three different circuits, for the Moore, Mealy, and synchronous Mealy machines. I have used positive edge triggered flip-flops because that is what ABEL easily supplies me with. You can imagine that the waveforms would be identical if I inverted the clock and use negative edge triggered flip-flops.

[Schematic of Vending Machine
Control]

We can verify that in fact the signals are what they imply that they are: the moore_open signal is dependent upon only the state; the asynch_mealy_open signal is computed with combinational logic only; the sync_mealy_open is the asynch_mealy_open which has been registered by a D flip-flop. The waveforms that are produced are:

[Waveform of Vending Machine Control]

At 22ns, the inputs change. Two nanoseconds later (for the propogation delay of the combinational logic), the asynchronous Mealy Open signal changes. The next rising clock edge is at t = 25ns, which is when the synchronous Mealy Open signal rises. The state changes at this time as well, and a gate propogation delay later, the Moore machine Open signal changes. A similar thing happens at t=42ns when reset is asserted.


Katz 8.21

Inputs: Timer signal T (T==1 when timer expires); Coin Deposited C; Double wash requested DW; Lid Open L (L==1 when lid is open).

Note #1: I like to see all the transitions in state diagrams. That includes the little self-loops on the wash, rinse, and spin states that account for the timer not having expired (T == 0).

Note #2: You cannot simply have a transition from the rinse state to the wash state on T==1 & DW==1. DW, the input for double wash, is 1 during the entire control cycle if a double wash is selected (imagine that DW is read from a knob on the washing machine -- the washing machine can't change the knob itself, so the FSM can't drive the DW signal low). Instead, you need two extra states (wash2, rinse2) to run through if DW==1.

[FSM diagram for Katz problem 8.21]


Katz 8.27

Although this problem may have been a little daunting at first, because there were about a dozen states, the machine has very regular behavior. Pretty much everyone implemented the following idea:

Make states for 0, 5, 10, ..., 35 cents to represent the amount of change the customer has depositied. Make states 40, 45, 50, 55 to represent the customer overpaying. The transitions from one state to another are pretty obvious: nickels advance to the state with 5 more cents added, dimes add 10 cents, etc.

When in the overpay states, the nickel release (NR) or dime release (DR) signals are pulsed until exactly 35 cents remains. Or, if insufficient funds are detected, a refund is generated.

As it turns out, not all 12 states are necessary: you can get rid of the 55 cent state. If you are in state 30, and the customer drops in a quarter, you can determine right then if (a) a dime should be released (if 1 dime and either another dime or two nickels change are available); (b) a nickel should be released (if no dimes but 4 nickels are available); or (c) insufficient change is in the repository, and a refund is necessary. In any case, you never need to enter a return-twenty-cents state. This is a key advantage of Mealy machines: they usually require fewer states, because there can be several transitions between two states, where outputs are driven differently for given inputs.

Attached at the end of this solution set is a state diagram for the newspaper vending machine. The online version has been color coded so that each state's transitions are in a different color. The ABEL code follows now.

MODULE katz8_27

  interface(nkl, dm, qtr, n1, n2, n3, n4, d1, d2, start, clk ->
            unlatch, nr, dr, ref, rel);

TITLE 'Newspaper vending machine (Katz 8.27)'

"Inputs
  nkl, dm, qtr		pin;	"Customer has dropped in a nickel, dime, or quarter
  n1, n2, n3, n4	pin;	"How many nickels are there available?
  d1, d2		pin;	"Same question, about dimes
  start, clk		pin;

"Outputs
  unlatch pin istype 'reg, buffer'; "Unlock the paper storage area
  nr, dr  pin istype 'reg, buffer'; "Release a nickel or dime of change
  ref	  pin istype 'reg, buffer'; "Provide full refund of deposited coins
  rel	  pin istype 'reg, buffer'; "Drop the customer's coins into the repository

"Local registers
  q0..q3		node istype 'reg, buffer';		"State variables

"Aliases
  SREG = [q3..q0];

  zero =	0;	"How much as the customer dropped into the machine?
  five = 	1;
  ten =		2;
  fifteen =	3;
  twenty =	4;
  twentyfive =	5;
  thirty =	6;
  thirtyfive =	7;
  overBy15 =	8;	"How much do we owe the customer?
  overBy10 =	9;
  overBy5 =	10;

EQUATIONS
  SREG.clk = clk;
  SREG.clr = start;

  [unlatch,nr,dr,ref,rel].clk = clk;
  [unlatch,nr,dr,ref,rel].clr = start;


STATE_DIAGRAM SREG

  state zero:		if nkl then five
			else if dm then ten
			else if qtr then twentyfive
			else zero;

  state five:		if nkl then ten
			else if dm then fifteen
			else if qtr then thirty
			else five;

  state ten:		if nkl then fifteen
			else if dm then twenty
			else if qtr then thirtyfive with {unlatch := 1; rel := 1;}
			else ten;

  state fifteen:	if nkl then twenty
			else if dm then twentyfive
			else if (qtr & n1) then thirtyfive with
                                     {unlatch := 1; rel := 1; nr := 1;}
			else if (qtr & !n1) then zero with {ref := 1;}
			else fifteen;

  state twenty:		if nkl then twentyfive
			else if dm then thirty
			else if (qtr & d1) then thirtyfive with
                                     {unlatch := 1; rel := 1; dr := 1;}
			else if (qtr & n2) then overBy5 with
                                     {unlatch := 1; rel := 1; nr := 1;}
			else if qtr then zero with {ref := 1;}
			else twenty;

  state twentyfive:	if nkl then thirty
			else if dm then thirtyfive with {unlatch := 1; rel := 1;}
			else if (qtr & d1 & n1) then overBy5 with
                                     {unlatch := 1; rel := 1; dr := 1;}
			else if (qtr & n3) then overBy10 with
                                     {unlatch := 1; rel := 1; nr := 1;}
			else if qtr then zero with {ref := 1;}
			else twentyfive;

  state thirty:		if nkl then thirtyfive with {unlatch := 1; rel := 1;}
			else if (dm & n1) then thirtyfive with
                                     {unlatch := 1; rel := 1; nr := 1;}
			else if dm then zero with {ref := 1;}
			else if (qtr & d2) then overBy10 with
                                     {unlatch := 1; rel := 1; dr := 1;}
			else if (qtr & d1 & n2) then overBy10 with
                                     {unlatch := 1; rel := 1; dr := 1;}
			else if (qtr & n4) then overBy15 with
                                     {unlatch := 1; rel := 1; nr := 1;}
			else if qtr then zero with {ref := 1;}
			else thirty;

  state thirtyfive:	goto zero with {unlatch := 0; rel := 0; nr := 0; dr := 0;}

  state overBy5:	goto thirtyfive with {nr := 1; dr := 0;}

  state overBy10:	if d1 then thirtyfive with {nr := 0; dr := 1;}
			else overBy5 with {nr := 1; dr := 0;}

  state overBy15:	if d1 then overBy5 with {nr := 0; dr := 1;}
			else overBy10 with {nr := 1; dr := 0;}


END
The state coding used in this ABEL solution is pretty self-explanatory. The states representing customer input up to 35 cents are (input amount) / 5 cents. There are exactly eight such states, so they can be mapped into 4 state bits with the high-order bit clear. The remaining ChangeRequired states have the high bit set.

To demonstrate the vending machine, we pretend to drop in two quarters twice: once with enough change, and once with not enough dimes. Note that the Dime Release signal changes at the same clock edge that the second quarter is asserted. On the first clock edge (t=15ns), the new state was entered (state twentyfive). By the time t=25ns rolled around, Qtr was still high, and the machine had already decided what the new outputs should be (remember, a Synchronous Mealy machine's outputs are dependent upon state and inputs, and pass through a register). When the clock edge at t=25ns hits, the new outputs take effect, and DR=1.

[Newspaper Vending Machine waveform]