09-SeqTech

Prévia do material em texto

IX - Sequential Logic 
Technology
© Copyright 2004, Gaetano Borriello and 
Randy H. Katz 1
Chapter 9.
sequential logic 
technologies
In chapter 4, we looked at diverse implementation technologies for combinational logic 
circuits: random logic, regular logic, programmable logic. The similar variants can be 
also applied to the implementation of sequential logic systems.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 2
Combination logic technologies Revisited
� Standard gates (random logic)
� gate packages
� cell libraries
� Regular logic
� multiplexers
� decoders 
� Two-level programmable logic
� PALs
� PLAs
� ROMs
Recall that there are three categories of approaches to implement combinational logic 
circuits. The random logic is also called fixed logic.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 3
Sequential logic implementation
� Implementation
� random logic gates and FFs
� programmable logic devices (PAL with FFs)
� Design procedure
� state diagrams
� state transition table
� state assignment and encoding
� next state functions
There are two categories in implementing sequential logic circuits. We already covered 
the first approach. In chapters 7 and 8, we implemented the combination logic for the 
next state and output by random logic gates mostly. Before going on to the 
programmable logic devices such as PAL, we look at some special cases of sequential 
logic circuit implementations.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 4
Median filter FSM
� Remove single 0s between two 1s (output = NS3)
000
0
1
0
100
010 110
111 011001
1
1
1
1
1
1
0
0
0
0
0
Reset
I PS1 PS2 PS3 NS1 NS2 NS3
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 0 1 0
0 1 0 1 X X X
0 1 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 1 1 1
1 0 1 1 1 1 1
1 1 0 0 1 1 0
1 1 0 1 X X X
1 1 1 0 1 1 1
1 1 1 1 1 1 1
The first example is to try to implement the overall system by using a shift register 
instead of three independent FFs. Whenever the three recent bits are 101, the output 
becomes 111.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 5
Median filter FSM (cont’d)
� Realized using the standard procedure and individual 
FFs and gates
I PS1 PS2 PS3 NS1 NS2 NS3
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 0 1 0
0 1 0 1 X X X
0 1 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 1 1 1
1 0 1 1 1 1 1
1 1 0 0 1 1 0
1 1 0 1 X X X
1 1 1 0 1 1 1
1 1 1 1 1 1 1
NS1 = Reset’ (I)
NS2 = Reset’ ( PS1 + PS2 I )
NS3 = Reset’ PS2
O = PS3
If we implement the combinational logic with K-maps, the next states will be represented 
by the above expressions. If reset is true, all the stored values will be reset to 0s.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 6
Median filter FSM (cont’d)
� But it looks like a shift register if you look at it right
000
0
1
0
100
010 110
111 011001
1
1
11
1
1
0
0
0
0
0
Reset000
0
1
0
100
010 110
111 011001
1
1
1
1
1
1
0
0
0
0
0
Reset
101
1
0
The state diagram of the median filter is so similar to that of a 3-bit shift register.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 7
Median filter FSM (cont’d)
� An alternate implementation with S/R FFs
� The set input (S) does the median filter function by making the 
next state 111 whenever the input is 1 and PS2 is 1 (1 input to 
state x1x)
R = Reset
S = PS2 I
NS1 = I
NS2 = PS1
NS3 = PS2
O = PS3Out
CLK
D Q
R S
D Q
R S
D Q
R S
In
Reset
Consider the function of the median filter, if the input string is 101, the output (or the 
next state) will be 111. In other words, if the current input is 1 and PS2 is 1, then NS1, 
NS2, NS3 will be set to 1s. This example can be compared to a regular logic 
implementation of combinational logic systems, shift registers and counters are similar to 
MUXes and DEMUXes.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 8
homework
� Example 9.2
� Figure 9.4 and 9.5
� No need to hand in solutions
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 9
Programmable logic building block for sequential logic
� ROM, PLA/PAL
Block Diagram for
Synchronous Mealy Machine
Block Diagram for
Synchronous Mealy Machine
ROM-based RealizationROM-based Realization
•Inputs & Current State
form the address
•ROM data bits form the
Outputs & Next State
Combinational 
Logic Registers
OutputsOutput Function
Next State 
Function
Inputs
ROM Registers
OutputsInputs
A0
An-1
An
An+m-1 Dk+m-1
D0
Dk-1
Dk
State
State
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 10
D Q
Q
Implementation using PALs
� Programmable logic building block for sequential logic
� macro-cell: FF + logic
� D-FF
� two-level logic capability like PAL (e.g., 8 product terms)
This slide illustrates an implementation with a PAL. An input comes from the bottom left 
to the AND array. The current state goes back from the bottom right to the AND array. 
Be aware that there can be multiple blocks.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 11
D0 = reset'(Q0'N + Q0N' + Q1N + Q1D)
D1 = reset'(Q1 + D + Q0N)
OPEN = Q1Q0
Vending machine example (Moore PLD mapping)
DQ
DQ
DQ
Q0
Q1
Open
Com
Seq
Seq
CLK
N
D
Reset
This is a PAL implementation of the vending machine based on the Moore model. Seq
(sequential) and Com (combinational) are the selector inputs of the MUXes, depicted by 
trapezoids. X marks indicate enabled cross-points. The trapezoid is a MUX.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 12
OPEN = reset'(Q1Q0N' + Q1N + Q1D + Q0'ND + Q0N'D)
Vending machine (synch. Mealy PLD mapping)
OPEN
DQ
DQ
DQ
Q0
Q1
Open
Seq
Seq
Seq
CLK
N
D
Reset
This synch. Mealy machine is derived from Moore machine model. So here, OPEN is 
reset’D1D0, actually.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 13
22V10 PAL
� Combinational logic
elements (SoP)
� Sequential logic
elements (D-FFs)
� Up to 10 outputs
� Up to 10 FFs
� Up to 22 inputs
� Fig. 9.28
This is a specific type of a PAL, 
which has 10 blocks (or 10 
combinational logic elements). 
There is a tri-state gate on the 
rightmost column. OE is “output 
enable.” If OE is unasserted, the 
gate is disconnected.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 14
Tri-state buffer
� 4 types
� Depending on s, either X1 or X2 will be connected to output f
Depending on whether OE and output are inverted, there are 4 types of tri-state buffers. 
Z means high-impedance state, which means the output is disconnected from the input.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 15
Tri-state buffer
� Tri-state buffers are used when multiple circuits all 
connect to a common bus. Only one circuit at a time is 
allowed to drive the bus
If there is a shared bus, and multiple inputs have different voltage values, there is a 
conflict about the data value in the bus. That is why a tri-state buffer is widely used in 
FPGAs. For details, look at section 4.4
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 16
22V10 PAL Macro Cell
� Sequential logic element + output/input selection
•Asynchronous Reset (AR) sets all 
registers to zero any time.
•Synchronous Preset (SP) sets all 
registers to a logic one on the rising 
edge of the next clock pulse. 
•AR and SP are common to all the 
registers.
This is the inside of a macro cell. The main function of this macrocell is to select the 
current outputof the combinational logic or the stored value, which will be relayed to the 
output. Also, it can decide that either the stored value or the final output goes back to the 
combinational logic part.
OE
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 17
Example: traffic light controller
� A busy highway is intersected by a little used farmroad
� Detectors C sense the presence of cars waiting on the farmroad
� with no car on farmroad, light remain green in highway direction
� if vehicle on farmroad, highway lights go from Green to Yellow to Red, allowing the 
farmroad lights to become green
� these stay green only as long as a farmroad car is detected but never longer than a 
set interval
� when these conditions are met, farm lights transition from Green to Yellow to Red, 
allowing highway to return to green
� even if farmroad vehicles are waiting, highway gets at least a set interval as green
� Assume you have an interval timer that generates:
� a short time pulse (TS) and
� a long time pulse (TL),
� in response to a set (ST) signal.
� TS is to be used for timing yellow lights and TL for green lights
Now we will look at a traffic light controller, which controls traffic signals for two 
crossing roads. Probably, we should give a green light to highway traffic as much as 
possible.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 18
highway
farm road
car sensors
Example: traffic light controller (cont’)
� Highway/farm road intersection
There are two sensors on the farmroad. When one of them detects a car waiting, it will 
send a signal to the traffic controller. The signal is denoted by C
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 19
Example: traffic light controller (cont’)
� Tabulation of inputs and outputs
inputs description outputs description
reset place FSM in initial state HG, HY, HR assert green/yellow/red highway lights
C detect vehicle on the farm road FG, FY, FR assert green/yellow/red highway lights
TS short time interval expired ST start timing a short or long interval
TL long time interval expired
� Tabulation of unique states – some light configurations imply others
state description
HG highway green (farm road red)
HY highway yellow (farm road red)
FG farm road green (highway red)
FY farm road yellow (highway red)
There ar many variables. H is Highway and F means Farmroad. G,Y and R are initials of 
Green, Yellow, and Red. TS for a yellow signal and TL is for a green signal. ST triggers 
either TS or TL depending on situations.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 20
Example: traffic light controller (cont’)
� State diagram Reset
TS'
TS / ST
(TL•C)'
TL•C / ST
TS'
TS / ST
(TL+C')'
TL+C' / ST
HG
FG
FYHY
Suppose the system starts with HG state. If the long interval expires and C is asserted, 
then it will move to HY state. With this transition, it will enable ST (for short interval). 
After the short interval, TS will be set to true, which makes the system go to FG state. In 
FG state, either of two events will trigger the transition to the next state, FY. Two events 
are long time expiration and no car on the farmroad. Each transition will set the timer, 
either long interval or short interval.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 21
Inputs Present State Next State Outputs
C TL TS ST H F
0 – – HG HG 0 Green Red
– 0 – HG HG 0 Green Red
1 1 – HG HY 1 Green Red
– – 0 HY HY 0 Yellow Red
– – 1 HY FG 1 Yellow Red
1 0 – FG FG 0 Red Green
0 – – FG FY 1 Red Green
– 1 – FG FY 1 Red Green
– – 0 FY FY 0 Red Yellow
– – 1 FY HG 1 Red Yellow
SA1: HG = 00 HY = 01 FG = 11 FY = 10
SA2: HG = 00 HY = 10 FG = 01 FY = 11
SA3: HG = 0001 HY = 0010 FG = 0100 FY = 1000 (one-hot)
output encoding – similar problem 
to state assignment
(Green = 00, Yellow = 01, Red = 10)
Example: traffic light controller (cont’)
� Generate state table with symbolic states
� Consider state assignments
We will consider three kinds of state assignments (SA1, SA2, SA3).
PS1 PS0 NS1 NS0
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 22
Logic for different state assignments
� SA1
NS1 = C•TL'•PS1•PS0 + TS•PS1'•PS0 + TS•PS1•PS0' + C'•PS1•PS0 + TL•PS1•PS0
NS0 = C•TL•PS1'•PS0' + C•TL'•PS1•PS0 + PS1'•PS0
ST = C•TL•PS1'•PS0' + TS•PS1'•PS0 + TS•PS1•PS0' + C'•PS1•PS0 + TL•PS1•PS0
H1 = PS1 H0 = PS1'•PS0
F1 = PS1' F0 = PS1•PS0‘
� SA2
NS1 = C•TL•PS1' + TS'•PS1 + C'•PS1'•PS0
NS0 = TS•PS1•PS0' + PS1'•PS0 + TS'•PS1•PS0
ST = C•TL•PS1' + C'•PS1'•PS0 + TS•PS1
H1 = PS0 H0 = PS1•PS0'
F1 = PS0' F0 = PS1•PS0
� SA3
NS3 = C'•PS2 + TL•PS2 + TS'•PS3 NS2 = TS•PS1 + C•TL'•PS2
NS1 = C•TL•PS0 + TS'•PS1 NS0 = C'•PS0 + TL'•PS0 + TS•PS3
ST = C•TL•PS0 + TS•PS1 + C'•PS2 + TL•PS2 + TS•PS3
H1 = PS3 + PS2 H0 = PS1
F1 = PS1 + PS0 F0 = PS3
These are the boolean expressions for each state assignment. Note that in SA3, the 
product terms for the next state is originally the number of incoming transitions.
IX - Sequential Logic 
Technology © Copyright 2004, Gaetano Borriello and Randy H. Katz 23
Sequential logic implementation summary
� Models for representing sequential circuits
� finite state machines and their state diagrams
� Mealy, Moore, and synchronous Mealy machines
� Finite state machine design procedure
� deriving state diagram
� deriving state transition table
� assigning codes to states
� determining next state and output functions
� implementing combinational logic
� Implementation technologies
� random logic + FFs
� PAL with FFs (programmable logic devices – PLDs)