• D&H Chapter 16 ‣ 16.1 – 16.3
(ignore Verilog code)
Recap of Sequential Logic Thus Far
Copyright By PowCoder代写 加微信 powcoder
• Feedback essential for sequential behavior ‣ SR latch
• Two types of sequential:
‣ Asynchronous: state is updated at arbitrary time
‣ Synchronous: state is updated only at a clock tick
– D Flip-flop
• Synchronous sequential = State Register + Next State Logic + Output Logic
• Two types of synchronous sequential ‣ Mealy: Output = f(state, input)
‣ Moore: Output = f(state)
• Representation ‣ State table
‣ State diagram
This Module:
An approach for dealing with lots of states
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath ‣ The vending machine example
‣ The combinational lock example
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath ‣ The vending machine example
‣ The combinational lock example
Consider: A Simple 5-bit Counter Sequential Logic
Suppose you want to build an FSM with the following state diagram
~rst ~rst ~rst ~rst ~rst rst rst rst rst
We could do it using the state table approach…
State[4:0]
Next_State[4:0]
2n states and 2n rows in the State Table ☹
Now, imagine we want to create a 32-bit counter! (very common in hardware)
How many states in the state graph?
A better way: using ‘Datapaths’
“x = a ? b : c”
is equivalent to
“x = b if a!=0; x=c otherwise”
Can be compactly described by an expression:
next_state = rst ? 0 : state + 1 ;
• This “counter” is an example of a sequential “datapath”
‣ a sequential circuit where the next state function is generated by an expression rather than a table
‣ similar to programming!
State[4:0]
Next_State[4:0]
Make State Table Symbolic
State[4:0]
Next_State[4:0]
next_state = rst ? 0 : state + 1 ;
State[4:0]
Next_State[4:0]
” What building blocks do we need to implement this?
Datapath view of the simple counter
rst: control
next_state = rst ? 0 : state + 1 ;
state: data
General Form of Sequential “Datapath” Circuits
Described as functions instead of tables
Example #2: An Up/Down/Load (UDL) Counter
A Deluxe Counter that can:
up, down, and load guaranteed to be one-hot. rst overrides.
Next State Function
if rst next_state = 0
if (!rst & up) next_state = state+1
if (!rst & down) next_state = state-1 if (!rst & load) next_state = in otherwise next_state = state
count up (increment) count down (decrement) be loaded with a value
Output Function
count = state
Compare with the table version
Next State
Symbolic Tables
Next State
Next State
Symbolic Tables
Next State
Next State
” What circuit elements do
we use to select one of these next states?
Schematic of UDL Counter
Recall: An adder can perform subtraction as well
Also controls inc or dec
Using a Mux4: rst, inc/ dec, load, no change
What does it do?
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath ‣ The vending machine example
‣ The combinational lock example
Example #3: A Timer Module
rst – resets timer
load – loads value into timer
done – asserted when count = 0
timer decrements unless load or done is true
• Used to generate a notification at a future time when something needs to be done
‣ Many applications – incredibly important!
• Typical use pattern
‣ assert load to set count to a value
– value corresponds to the time duration till when notification is needed ‣ assert count
‣ wait for done to become 1
rst – resets timer
load – loads value into timer
done – asserted when count = 0
timer decrements unless load or done is true
Next State Function
if (rst | (!load & done) next_state = 0 if (!rst & load) next_state = in otherwise next_state = state – 1
Output Function
done = !(state[n-1] | state[n-2] | … | state[0])
Schematic of Timer
Example #4: A Simple Shift Register
rst – resets out to 0
otherwise on each clock out is shifted left with input sin filling in the LSB
Next State Function Output Function
if (rst) next_state = 0
otherwise next_state = {state[n-2:0], sin}
out = state
Schematic of the Simple Shift Register
Example #5:
A Sophisticated Bi-directional Shift Register
rst – resets out to 0
left – out is shifted left with input sin filling in the LSB right – out is shifted right with input sin filling in the MSB load – out is set equal to input in
otherwise out is unchanged Next State Function
if (rst) next_state = 0
if (!rst & left) next_state = {state[n-2:0], sin}
if (!rst & !left & right) next_state = {sin, state[n-1:1]} if (!rst & !left & !right & load) next_state = in otherwise next_state = state
Output Function
out = state
Schematic of the Sophisticated Shift Register
Remember, these are just wires
Summary of examples
• All these examples are basically factoring a complex sequential logic problem so that part of it can be implemented more easily / efficiently
• Two very common approach are
‣ Master-Slave Partitioning
– FSMs are split into a hierarchy of interacting FSMs
‣ Controller+Datapath Partitioning
– next states are computed using datapaths, and different datapaths
are selected via a control logic
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath
‣ The vending machine example
‣ The combinational lock example
Datapath – Control Partitioning
• Real systems often viewed as having two coupled sequential logic parts
Control FSM + Datapath
• Datapath computes its next state
‣ “data state” like program variables ‣ via multiplexers and functional
– e.g. counters, shifters, adders etc.
• Control FSM computes its next state (“control state”) via a state table or state diagram
Datapath – Control Partitioning
• Control FSM sends commands to Datapath, which sends back status
• Inputs and outputs of the system also divided into control and data
• The separation of control and data is often the key to a ‘clean’ design
Datapath – Control Partitioning
Ic = control inputs ∪ status Oc = control outputs ∪
command next_statec = f(statec, Ic) Oc = f(statec, Ic)
ID = data inputs ∪ command OD = data outputs ∪ status
next_stateD = f(stateD, ID) Oc = f(stateD, ID)
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath
‣ The vending machine example ‣ The combinational lock example
Example: Vending Machine Controller
• Specification
‣ Receives coins (nickel, dime, quarter) and
accumulates sum
‣ When “dispense” button is pressed serves a drink
if enough coins have been deposited
‣ Then returns change – one nickel at a time
• Assume that the motor for dispensing and returning change returns a “done” signal when the action is completed
• Partition task
– keep track of amount owed user
– keep track of sequence – deposit, serve, change
No selection of drinks/ snacks; A user needs to
press a button to dispense;
State Diagram for Control
• Receives coins (nickel, dime, quarter) and accumulates sum
• When “dispense” button is pressed serves a drink if enough coins have been
• Then returns change – one nickel at a time.
Continuously Waits for dispensing accepts coins to be done
Checks how much $ is left
Waits for a nickel to be dispensed
Checks how much $ is left
~done & zero
~done & ~zero
NOTE: For clarity self-transitions omitted
(FSM stays in a state if conditions for none of the edges out of a state are true) Assume the mechanical components will send a signal when the actual dispensing is done
~done & ~zero
~done & zero
Datapath for the Vending Machine
Datapath for the Vending Machine
The control logic
Datapath for the Vending Machine
Select nickel, dime or quarter and price.
” why select price?
Datapath for the Vending Machine
• When depositing, add an incoming coin’s • amount to the deposited amount
Before returning: subtract price from the
• deposited amount to get the change amount
When returning, subtract an outgoing coin’s amount from the change amount
Select add or sub.
” when do we select add and when sub?
Datapath for the Vending Machine
• Select amount when waiting for mechanical • components to perform operations
Select sum when performing own logic • (depositing or returning)
Select 0 to reset
” When to select which: ‘sum’ from adder, 0, or ‘amount’?
Datapath for the Vending Machine
Compares if the deposited amount is enough for the price
A register that stores the currently deposited amount
Detects zero when returning change
Vending Machine in Operation
Deposit Dime
Attempt Dispense
Two Quarters
Deposit Nickel
Serve Drink
Return First Nickel
Return Second Nickel
• Controller + datapath: what and why
• Examples of controller + datapath designs
• How to partition controller and datapath ‣ The vending machine example
‣ The combinational lock example
Example: Combination Lock
• Accepts inputs from a decimal keypad
‣ 4-bit key with accompanying valid to indicate key press
• User enters a sequence of digits and then presses enter
‣ sequence stored in internal memory, its length available as variable
• If sequence was correct, unlock output is asserted
• To relock, the user presses enter again
• If sequence was incorrect, a busy output is asserted and a timer is activated to wait a predefined period before the user can try again
‣ for security, the busy light should turn on only upon pressing enter
• valid & enter are preprocessed so as to be asserted for 1 clock cycle per press
‣ can be done by other simple FSMs
Now partition into datapath and control FSM…
State Diagram for Control
• Start in “enter” state
• Gets kmatch and lmatch from datapath,
and enter from keypad
• Stays in “enter” state as long as correct
digits are pressed
• Unlocks if in “enter” state and enter is pressed and length matches
• If invalid key pressed then moves to “wait1”
• Stays there till enter is pressed and then moves to “wait2”
• If enter is pressed but only part of the sequence entered then moves to “wait2”
• In “wait2” starts a timer and waits for it to be done
• Then move back to “enter” state
kmatch: the entered keys match a subsequence of the codes lmatch: the length of the entered keys matches that of the codes
enter & ~lmatch
valid &
~kmatch
” Can we wait for the user to enter the entire unlock code and then compare?
• kmatch allows for early elimination of invalid key entry
‣ ! kmatch ” invalid
• Alternative design: wait until the user hits “enter” and then compare strings
‣ what is the trade-off
• Logic of string comparison will be more complex
‣ one will need to compare equivalence of two strings of different lengths which are not even known at design time
enter & ~lmatch
valid &
~kmatch
” What status variables come from the datapath?
Datapath for the Combination Lock
Compares length and value of code entered
index: # of keys pressed by the user (which char in the code should the current key be compared to)
The code is stored in ROM
Status variables
Times the wait period when incorrect code entered
Sets or resets a timer value
• Datapath state machines
‣ Next state function specified by an expression, not a table ‣ e.g.
next = rst ? 0 : (inc ? next + 1 : next) ;
‣ Common “idioms” – Counters
– Shift registers
• Datapath and control partitioning
‣ Divide state space into control (deposit, serve, change) and data ‣ FSM determines control state
‣ Datapath computes amount
‣ Status and control signals
Advice Regarding Design
• Hardest part of this course—design (especially partitioning)
• Signs of a bad design: a control logic seems too complicated,
or performs datapath-like operation
‣ … that means a not-so-clean partition
• Rather than finding universal rules of design, try studying existing examples to learn ‘design patterns’
‣ All good designs share things in common
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com