![[Datapath waveform]](datapathwav.gif)
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).
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.
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]](katz8_11sch.gif)
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]](katz8_11wav.gif)
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.
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]](katz8_21fsm.gif)
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]](katz8_27wav.gif)