06-Seq

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

VI - Sequential Logic
© Copyright 2004, Gaetano Borriello and 
Randy H. Katz 1
Chapter 6.
sequential logic design
This is the beginning of the second part of this course, sequential logic.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 2
Sequential logic
� Sequential circuits
� simple circuits with feedback
� latches
� edge-triggered flip-flops
� Timing methodologies
� cascading flip-flops for proper operation
� clock skew
� Asynchronous inputs
� metastability and synchronization
� Basic registers
� shift registers
� simple counters
� Hardware description languages and sequential logic
Again, sequential logic circuits are quite different from combinational logic. In general, 
sequential systems are more difficult to design. We will discuss some basic issues in the 
sequential logic systems in this chapter.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 3
C1 C2 C3
comparator
value
equal
multiplexer
reset
open/closed
new equal
mux
control
clock
comb. logic
state
Sequential logic circuits (SLCs)
� Circuits with feedback
� outputs = f(inputs, past inputs, past outputs)
� basis for building "memory" into logic circuits
� door combination lock is an example of a sequential circuit
� state is memory
� state is an "output" and an "input" to combinational logic
� combination storage elements are also memory
In most sequential logic circuits (SLCs), there are storage parts or memory elements. 
Recall that in the door lock system, three numbers should be stored and compared. What 
is the key element here? 
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 4
X1
X2
•
•
•
Xn
switching
network
Z1
Z2
•
•
•
Zn
Circuits with feedback
� How to control feedback?
� what stops values from cycling around endlessly
One popular feature of SLCs is to have a feedback loop from the outputs. In this slide, 
this diagram shows one output goes back to the input. Then how can we control the 
feedback mechanism by which Zn becomes Xn? That is, with this feedback, timing is 
even more important. We will discuss this issue from now on.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 5
� Two inverters form a static memory cell
� will hold value as long as it has power applied
� How to get a new value into the memory cell?
� selectively break feedback path
� load new value into cell
"remember"
"load"
"data"
"stored value"
"0"
"1"
"stored value"
Simplest circuits with feedback
Let’s consider a simple memory element first. What if we place two inverters before a 
stored value and suppose the stored value is 1. Note that there is a feedback from the 
stored value to the first inverter. Another more sophisticated option is to have a selection 
function between a stored value and a new value. If “load” is enabled, the new “data”
will be put into the stored value.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 6
R
S
Q
Q'
R
S
Q
R'
S'
Q
Q
Q'
S'
R'
Memory with cross-coupled gates
Let’s consider this feedback in the cases of cross-connectivity between other gate types. 
With Nor or Nand gates, we can have more control inputs. R and S denote reset and set 
inputs, respectively. Q is the output value of interest and its inverse is denoted by Q’. For 
a NOR gate, think of a case when a single input can determine the output of the gate. 
Suppose R is 1, which makes Q 0. Basically, we assume R and S are opposite for update.
Q'
� Cross-coupled NOR gates
� similar to inverter pair, with capability to force output to 0 
(reset=1) or 1 (set=1)
� Cross-coupled NAND gates
� similar to inverter pair, with capability to force output to 0 (R’=0) 
or 1 (S’=0)
Q'
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 7
Reset Hold Set SetReset Race
R
S
Q
\Q
100
Timing behavior
R
S
Q
Q'
If R=1 and S=0, Q is 0 and Q’ is 1 (recall the meaning of reset R). If R=0 and S=1, Q is 1. 
What if R=S=0, then Q and Q’ will remain with the previous values.
The problem happens when R=S=1. Are Q and Q’ just 0s? The more significant problem 
arises when R=S=1 and then R=S=0, which will yield an oscillation as follows. Q and Q’
will be 1 together. But then Q and Q’ should be changed to 0 again. Then this cycle 
continues.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 8
S R Q
0 0 hold
0 1 0
1 0 1
1 1 unstable
State behavior or R-S latch
� Truth table of R-S latch behavior
Q Q'
0 1
Q Q'
1 0
Q Q'
0 0
Q Q'
1 1
R
S
Q
Q'
This slide shows a state diagram. It describes how Q and Q’ will change as varying 
values of S and R stimulate the system. That is, S and R are inputs and Q and Q’ are 
outputs. A latch is a memory element that stores one bit. And this is called an R-S latch. 
If S is high, 1 will be stored into Q; if R is high, 0 will be stored. Depending on the 
values of Q and Q’, we can think of 4 states.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 9
Theoretical R-S latch behavior
� State diagram
� states: possible values
� transitions: changes
based on inputs
Q Q'
0 1
Q Q'
1 0
Q Q'
0 0
Q Q'
1 1
SR=00
SR=11SR=00
SR=10
SR=01
SR=00
SR=10
SR=00
SR=01
SR=11 SR=11
SR=10SR=01 
SR=01 SR=10
SR=11
possible oscillation
between states 00 and 11
R
S
Q
Q'
Suppose the R-S latch holds initially 01 (QQ’). As long as SR is 01 or 00, the system will 
remain in the same state. If SR=10, Q will be 1. When SR is 11, the state will be 00 
(QQ’). Then the problem happens when SR becomes 00 from that state.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 10
Observed R-S latch behavior
� Very difficult to observe R-S latch in the 1-1 state
� one of R or S usually changes first
� Ambiguously returns to state 0-1 or 1-0
� a so-called "race condition"
� or non-deterministic transition
SR=00SR=00 
Q Q'
0 1
Q Q'
1 0
Q Q'
0 0
SR=10
SR=01
SR=00
SR=10
SR=00
SR=01
SR=11 SR=11
SR=01 SR=10
SR=11
R
S
Q
Q'
In real systems, when SR changes from 11 to 00, normally both S and R may not change 
at the exactly same time. Hence, SR will be either 01 or 10 before changing from 11 into 
00. So we cannot guess which will be changed first. In summary, we should not allow 
SR to be 11.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 11
Q(t+∆)
R
S
Q(t)
S R Q(t) Q(t+∆)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 X
1 1 1 X
hold
reset
set
not allowed characteristic equation
Q(t+∆) = S + R’ Q(t)
R-S latch analysis
� Break feedback path
R
S
Q
Q'
0 0
1 0
X 1
X 1Q(t)
R
S
To analyze the timing, let’s assume the feedback loop is cut off. That is, consider Q(t) 
and Q(t+ ∆) separately. Here ∆ is the delay incurred by the latch. When you look at the 
truth table, you can notice something different. What is it? 
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 12
R’
S’
Q
Q'
Activity: R-S latch using NAND gates
characteristic equation
Q(t+∆) = S + R’ Q(t)
R’
S’
Q(t)
0 0
1 0
X 1
X 1Q(t)
R
S
S R S’ R’ Q(t) Q(t+∆)
0 0 1 1 0 0
0 0 1 1 1 1
0 1 1 0 0 0
0 1 1 0 1 0
1 0 0 1 0 1
1 0 0 1 1 1
1 1 0 0 0 X
1 1 0 0 1 X
hold
reset
set
not allowed
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 13
enable'
S'
Q'
Q
R' R
S
Gated R-S
latch
� Control when R and S 
inputs matter
� otherwise, the slightest 
glitch on R or S while 
enable is low could cause 
change in value stored
Set Reset
S'
R'
enable'
Q
Q'
100
The next version is a gated R-S latch. In the gated (level-sensitive) R-S latch, the R-S 
values are handled cautiously. When enable is low, then R and S are always zeroes (there 
is no glitch or fluctuation in R and S). So R’ and S’ are meaningful only when enable is 
high. This waveform shows when enable is high and S is set (or S’ is low), Q will 
become true.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 14
period
duty cycle (in this case, 50%)
Clocks
� Used to keep time
� wait long enough for inputs (R' and S') to settle
� then allow to have effect on value stored
� Clocks are regular periodic signals
� period (time between ticks)
� duty-cycle (time clock is high between ticks - expressed as % of 
period)
A clock is an important element in sequential circuits. The enable signal in the previous 
slide serves as kind of a clock. Once enable is asserted, it should be high until the input 
stimulates the output fully. Normally, a clock is periodically alternating between high 
and low. The beginning of each period is called a clock tick. And the duty cycle is 
defined as the ratio of High voltage interval to the period.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 15
Clocks (cont’d)
� Controlling an R-S latch with a clock
� can't let R and S change while clock’ is 0 (allowing R and S to pass)
� only have half of clock period for signal changes to propagate
� signals must be stable for the other half of clock period
clock’
S’
Q’
Q
R’ R
S
clock’
R’ and S’
changing stable changing stablestable
Let’s control the gated (or level-sensitive) R-S latch with a clock. While clock’ is 0, R’
and S’ should sustain their values which will update Q and Q’ during that interval. While 
clock’ is high, R’ and S’ can be changed to a new value (for next operation); in the 
meantime, Q and Q’ will not change since R and S are 00.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 16
clock
R
S Q
Q’ R
S Q
Q’R
S
Cascading latches
� Connect output of one latch to input of another
� How to stop changes from racing through chain?
� need to be able to control flow of data from one latch to the next
� move one latch per clock period
� have to worry about logic between latches (arrows) that is too fast
What if we connect multiple latches in a series? In this case, the output of the first latch 
becomes the input for the second latch. For a single ON interval of the clock signal, we 
can assure that Q and Q’ if the first latch will be stabilized after update. But the concern 
is if signal propagation is too fast, even the second R-S latch may be affected like a 
domino effect in the same ON interval. How can we make it sure that only the first latch 
is updated?
R
S
Q
Q'
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 17
Master-slave structure
� Break flow by alternating clocks
� use positive clock to latch inputs into one R-S latch
� use negative clock to change outputs with another R-S latch
� View pair as one basic unit
� master-slave flip-flop
� twice as much logic
� output changes a few gate delays after the falling edge of clock
but does not affect any cascaded flip-flops
master stage slave stage
P
P’
CLK
R
S Q
Q’ R
S Q
Q’R
S
The solution is to use different polarities of clock signals for a pair of R-S latches. So it 
requires twice logic gates. Notice that there is an inverter between two clock signals. So 
when the clock is high, the master latch will be updated and when the clock is low, the 
slave latch will be changed.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 18
Set
1s 
catch
S
R
CLK
P
P’
Q
Q’
Reset
Master
Outputs
Slave
Outputs
The 1s catching problem
� In first R-S stage of master-slave FF
� 0-1-0 glitch on R or S while clock is high is "caught" by master stage
� leads to constraints on logic to be hazard-free
master stage slave stage
P
P’
CLK
R
S Q
Q’ R
S Q
Q’R
S
What would be the problem of the inverted clock signals for the pair of R-S latches? 
While the clock is high, suppose there is a glitch is in the very first S (0-1-0), P and P’
will change, which in turn will affect the slave latch when the clock becomes low. This is 
called the 1s catching problem.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 19
10 gates
D flip-flop
� Make S and R complements of each other
� eliminates 1s catching problem
� can't just hold previous value
(must have new value ready every clock period)
� value of D just before clock goes low is what is stored in flip-flop
� negative edge-triggered 
D Q
Q’
master stage slave stage
P
P’
CLK
R
S Q
Q’ R
S Q
Q’
To eliminate the 1s catching problem, we have to make S and R have opposite values; so 
we use the complementary values from the same input, which is called D flip-flop. D is 
an abbreviation for data. So R and S can be either 01 and 10 only. Now we cannot use 00 
to maintain the same value in the latch. How many gates here? Each R-S latch has two 
NOR gates.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 20
Q
D
Clk=1
R
S
0
D’
0
D’ D
Q’
negative edge-triggered D 
flip-flop (D-FF)
4-5 gate delays
must respect setup and hold time 
constraints to successfully
capture input
characteristic equation
Q(t+1) = D
holds D’ when
clock goes low
holds D when
clock goes low
(Negative) Edge-triggered D flip-flops (FFs)
� More efficient solution: only 6 gates
� sensitive to inputs only near edge of clock signal (not while high)
The other realization to solve the 1s catching problem is to use a clock edge to trigger the 
change of the flip-flop’s value. While the clock is high, the second top NOR and the 
second bottom NOR gates will be 0, which keeps the old values of Q and Q’
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 21
Q
D
Clk=0
R
S
D
D’
D’
D’ D
when clock goes high-to-low
data is latched
when clock is low
data is held
Negative Edge-triggered D flip-flops (cont’d)
� Step-by-step analysis
Q
new D
Clk=0
R
S
D
D’
D’
D’ D
new D ≠ old D
If clock goes from 1 to 0, initially S and R are 0. Then, depending on D’s value, S or R 
will be changed, which in turn will set or reset Q. The numbers in blue shows the case 
when D is 1. After that, D’s change makes no effect. E.g. new D is 0 now, D (second 
bottom NOR) was 1, D’(bottom) is 0. So D (top) is still 1; R and S are not changed.
1
0
0 -> 1
1
0
0
1
0 -> 0
1
0
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 22
positive edge-triggered FF
negative edge-triggered FF
D
CLK
Qpos
Qpos’
Qneg
Qneg’
100
Edge-triggered D flip-flops (cont’d)
� Positive edge-triggered
� inputs sampled on rising edge; outputs change after rising edge
� Negative edge-triggered flip-flops
� inputs sampled on falling edge; outputs change after falling edge
There are two kinds of flip-flops which are triggered by the two edges of the signals: 
rising edge and falling edge. The previous slide shows a negative edge-triggered FF. If 
we add an inverter to the clock, that FF is turned into a positive edge-triggered FF. 
Typically, latches are level triggered and simpler. FFs are normally edge triggered and 
more complicated.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 23
Timing methodologies
� Rules for interconnecting components and clocks
� guarantee proper operation of system when strictly followed
� Approach depends on building blocks used for memory 
elements
� we'll focus on systems with edge-triggered flip-flops
� found in programmable logic devices
� many custom integrated circuits focus on level-sensitive latches
� Basic rules for correct timing:
� (1) correct inputs, with respect to time, are provided to the flip-
flops
� (2) no flip-flop changes state more than once per clocking event
As the same input can produce different outputs over time in sequential logic, timing is 
extremely important. Especially, memory elements like flip-flops should be handled with 
precise timing. So a clock determines when the circuit can change the current state to a 
new state. For each memory element, only one state transition is allowed in a single 
clock period.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 24
there is a timing "window" around 
the clocking event during which the 
input must remain stable and 
unchanged in order to be recognized clock
data
changingstable
input
clock
Tsu Th
clock
data
D Q D Q
Timing methodologies (cont’d)
� Definition of terms
� clock: periodic event, causes state of memory element to change
can be rising edge or falling edge or high level or low level
� setup time: minimum time before the clocking event by which the
input must be stable (Tsu)
� hold time: minimum time after the clocking event until which the
input must remain stable (Th)
Let’s go over terminologies first. We already know what is a clock. For each edge of a 
clock signal, there are some timing constraints. Suppose the positive edge of a clock 
signal triggers a circuit. Then the data input should be stable for an interval which is 
Tsu+Th, which are dependent on transistor circuit delay.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 25
behavior is the same unless input changes
while the clock is high
D Q
CLK
positive
edge-triggered
flip-flop
D Q
C
CLK
transparent
(level-sensitive)
latch
D
CLK
Qedge
Qlatch
Comparison of latches and flip-flops (FFs)
Again, in FFs, the data value only at the rising edge (or falling edge) is critical (see blue 
dots). Meanwhile, most latches are sensitive to D value changes as long as the clock is 
high. Typically, the clock input of a FF is depicted by a triangle.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 26
Type When inputs are sampled When output is valid
unclocked always propagation delay from input change
latch
level-sensitive clock high propagation delay from input change
latch (Tsu/Th around falling or clock edge (whichever is later)
edge of clock)
master-slave clock high propagation delay from falling edge
flip-flop (Tsu/Th around falling of clock
(P.17) edge of clock)
negative clock hi-to-lo transition propagation delay from falling edge
edge-triggered (Tsu/Th around falling of clock
flip-flop edge of clock)
Comparison of latches and flip-flops (cont’d)
In unclocked latches, a stored value will always be affected by data at any time. In level-
sensitive latches, the D value affects the latch as long as the clock stays high. And the D 
value at the falling edge will be maintained while the clock is low. So around the falling 
edge, we should keep data stable for Tsu+Th. In a positive edge-triggered FF, the Tsu/Th
for the rising clock edge should be guaranteed.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 27
all measurements are made from the clocking event (the rising edge of the clock)
Typical timing specifications
� Positive edge-triggered D flip-flop
� setup and hold times
� minimum clock width (Tw)
� propagation delays (low to high, high to low, max and typical)
D 
Clk
Q 
T su
1.8
ns 
T h 
0.5
ns 
T w 
3.3 
ns 
T pd
3.6 ns 
1.1 ns 
T su
1.8
ns 
T h 
0.5 
ns 
T pd
3.6 ns 
1.1 ns 
T w 
3.3 
ns 
This slide illustrates the timing where the rising edge of the clock signal is the reference. 
Tpd is the propagation delay between the rising edge of the clock (event trigger) and the 
change in the output. Tw should be long enough to ensure that D will change Q
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 28
IN
Q0
Q1
CLK
100
Cascading edge-triggered flip-flops
� Shift register
� new value goes into first stage
� while previous value of first stage goes into second stage
� consider setup/hold/propagation delays (prop must be > hold)
CLK
IN
Q0 Q1
D Q D Q OUT
This slide shows the waveform of a two bit shift register made up of two cascaded 
positive edge triggered D FFs. A shift register refers to a circuit that moves a stored bit 
among storage elements. At the first positive edge, IN is 0, which will store 0 at Q0. at 
the next clock tick, Q0 will be propagated to Q1 and Q0 will be updated to the IN’s value 
at that moment. But we have to be careful about timing relationships among signals.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 29
timing constraints
guarantee proper
operation of
cascaded components
assumes infinitely fast 
distribution of the clock
Cascading edge-triggered flip-flops (cont’d)
� Why this works
� propagation delays (Tp or Tpd) exceed hold times (Th)
� clock width constraint exceeds setup time
� this guarantees following stage will latch current value before it 
changes to new value
Tsu
1.8ns
Tp
1.1-3.6ns
Th
0.5ns
In
Q0
Q1
CLK
Tsu
1.8ns
Tp
1.1-3.6ns
Th
0.5ns
The first condition for the proper operation is Tp > Th. Otherwise, the changed Q0 may 
also affect the second stage FF (i.e. changing Q1 as well). Also, the interval between the 
successive clock rising edges, Tperiod > Tp+Tsu. Otherwise Q0 is not ready to change 
Q1.
periodT 
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 30
original state: IN = 0, Q0 = 1, Q1 = 1
due to skew, next state becomes: Q0 = 0, Q1 = 0, and not Q0 = 0, Q1 = 1
CLK1 is a delayed
version of CLK0
In
Q0
Q1
CLK0
CLK1
100
Clock skew
� The problem
� correct behavior assumes next state of all storage elements
determined by all storage elements at the same time
� this is difficult in high-performance systems because time for clock
to arrive at flip-flop is comparable to delays through logic
� effect of skew on cascaded flip-flops:
The last headache in timing is about the distribution of the clock signal. So far, we 
assumed that clocks are arriving at the FFs simultaneously. But those clock signals travel 
along the wires just like the other data signals. So Tp > Tskew +Th (in case that Tskew >
0) and Tperiod + Tskew > Tp + Tsu (in case that Tskew < 0)
Tskew
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 31
Summary of latches and flip-flops
� Development of D-FF
� level-sensitive used in custom integrated circuits
� can be made with 4 switches
� edge-triggered used in programmable logic devices
� good choice for data storage register
� Preset and clear inputs are highly desirable on flip-flops
� used at start-up or to reset system to a known state
D-FFs can be either level-sensitive or edge-triggered. For maintenance purposes, preset 
and clear inputs are desirable for FFs, which will be discussed later. Preset inputs 
initialize the values in FFs. Clear inputs will reset the values of FFs to 0s.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 32
Metastability and asynchronous inputs
� Clocked synchronous circuits
� inputs, state, and outputs sampled or changed in relation to a
common reference signal (called the clock)
� e.g., master/slave, edge-triggered
� Asynchronous circuits
� inputs, state, and outputs sampled or changed independently of a
common reference signal (glitches/hazards a major concern)
� e.g., R-S latch
� Asynchronous inputs to synchronous circuits
� inputs can change at any time, will not meet setup/hold times
� dangerous, synchronous inputs are greatly preferred
� cannot be avoided (e.g., reset signal, memory wait, user input)
If we use only synchronous circuits in the system, then we just need to consider clocks 
for stable system operations. However, some components are asynchronous in the sense 
that the values of these components are changing individually without any common 
reference signal (e.g. clock signal). One typical case happens when an asynch circuit 
meets a synch circuit.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 33
small, but non-zero probability 
that the FF output will get stuck 
in an in-between state
oscilloscope traces demonstrating
synchronizer failure and eventual
decay to steady state
logic 0 logic 1
logic 0
logic 1
Synchronization failure
� Occurs when FF input changes close to clock edge
� the FF may enter a metastable state – neither a logic 0 nor 1 –
� it may stay in this state an indefinite amount of time
� this is not likely in practice but has some probability
Sometimes, Tsu or Th is not long enough for stable transitions. The output of a FF may 
enter a meta-stable state. Three cases take place depending on the energy for the duration 
(Tsu + Th) to make transitions. Suppose Q was 0 and now D is 1 to store bit 1 into Q.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 34
D DQ Q
asynchronous
input
synchronized
input
synchronous system
Clk
Dealing with synchronization failure
� Probability of failure can never be reduced to 0, but it can be reduced
(1) slow down the system clock 
this gives the synchronizer more time to decay into a steady state; 
synchronizer failure becomes a big problem for very high speed systems
(2) use fastest possible logic technology in the synchronizer
this makes for a very sharp "peak" upon which to balance
(3) cascade two synchronizers 
this effectively synchronizes twice (both would have to fail)
There are three ways to reduce the probability of synch. failure. The first option gives the 
logic circuit more time to go to either 0 or 1. The second approach is similar; it gives less 
room to stay at meta-stable state. In the third choice, by cascading two FFs, the 
probability of the synch failure is even more reduced at the cost of slow-down.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 35
D Q
D Q
Q0
Clock
Clock
Q1
Async
Input
D Q
D Q
Q0
Clock
Clock
Q1
Async
Input
D Q
Clocked 
Synchronous 
System
Synchronizer
Handling asynchronous inputs
� Never allow asynchronous inputs to fan-out to more than one flip-flop
� synchronize as soon as possible and then treat as synchronous signal
When an asynch input makes rendezvous with a synch part, only one FF will be placed at 
the junction. On the left, depending on the wire length, an asynch input can arrive at 
different times at two D FFs, which may cause unexpected results. To solve this issue, 
place a single D FF as shown on the right; so the input will change Q only.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 36
In is asynchronous and 
fans out to D0 and D1
one FF catches the 
signal, one does not
inconsistent state may 
be reached!
In
Q0
Q1
CLK
Handling asynchronous inputs (cont’d)
� What can go wrong?
� input changes too close to clock edge (violating setup time 
constraint)
This slide shows waveforms of the dangerous circuit in the previous slide. As the asynch
input arrives late at the lower D FF, the energy may not be high enough to make a 
transition at Q1. In designing a system, we intended to make changes at both FFs from 
the input from the asynch circuit, but we fail to do so.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 37
R S R S R S
D Q D Q D Q D Q
OUT1 OUT2 OUT3 OUT4
CLK
IN1 IN2 IN3 IN4
R S
"0"
Registers
� Collections of flip-flops with similar controls and logic
� stored values somehow related (for example, form binary value)
� share clock, reset, and set lines
� similar logic at each stage
� Examples
� shift registers
� counters
From now on, we will look at a collection of FFs. The first memory element to look at is 
a register. A register is normally defined as a group of FFs with coordinated controls or 
shared controls. Examples of controls are clock, reset, set and so on. In this case, we can 
read/write 4 bits in parallel. 
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 38
D Q D Q D Q D QIN
OUT1 OUT2 OUT3 OUT4
CLK
Shift register
� Holds samples of input
� store last 4 input values in sequence
� 4-bit shift register:
One of the relatively simple registers is a shift register. Here one bit is shifted (or moved 
to left) to the next FF at each clock tick (its positive edge). At each positive edge, the 
stored value will come out and move to the next element.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 39
clear sets the register contents
and output to 0
s1 and s0 determine the shift function
s0 s1 function
0 0 hold state
0 1 shift right
1 0 shift left
1 1 load new input
left_in
left_out
right_out
clear
right_in
output
input
s0
s1
clock
Universal shift register
� Holds 4 values
� serial or parallel inputs
� serial or parallel outputs
� permits shift left or right
� shift in new values from left or right
The shift register in the previous slide goes only from left to right. Here we want to 
design a generic or multi-purpose shift register with the above functionalities. In addition, 
we also want to hold the current value without I/O. Overall, we need some control 
variables.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 40
Nth cell
D
Q
CLK
Q[N-1]
(left)
Q[N+1]
(right)
Input[N]
to N-1th 
cell
to N+1th 
cell
clear s0 s1 new value
1 – – 0
0 0 0 output
0 0 1 output value of FF to left (shift right)
0 1 0 output value of FF to right (shift left)
0 1 1 input
Design of universal shift register
� Consider one of the four flip-flops
� new value at next clock cycle:
s0 and s1
control mux
0 1 2 3
CLEAR
Each memory module (that stores 1 bit) should be able to perform 5 functions. Note that 
there are multiple incoming lines and one of them should be selected. This should ring 
the bell. It will be convenient to use a MUX. Blue wires are about control while black 
wires are data paths. Here, clear, S1 and S0 are depicted by a single wire for simplicity. 
CLK
clear, s0, s1
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 41
parallel inputs
parallel outputs
serial transmission
Shift register application
� Parallel-to-serial conversion for serial transmission
One of the popular application of the shift register is serial transmission, where 
information is transmitted over the medium bit-by-bit.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 42
D Q D Q D Q D QIN
OUT1 OUT2 OUT3 OUT4
CLK
OUT
Pattern recognizer
� Combinational function of input samples
� in this case, recognizing the pattern 1001 on the single input 
signal
Another useful application
of shift registers is bit string identification. In this case, bits 
are shifted from left to right. At any moment, if 4 bits are 1001, then OUT will be true.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 43
D Q D Q D Q D QIN
OUT1 OUT2 OUT3 OUT4
CLK
Counters
� Sequences through a fixed set of patterns
� in this case, 1000, 0100, 0010, 0001
� if one of the patterns is its initial state (by loading or set/reset)
If there are multiple patterns that are used for state representation, this register is 
typically referred to as a counter. Look at the shift register in the slide. Suppose there is a 
initialization (or preset) logic that stores 1000 in the register, which is not shown here. 
Then, as the clock ticks, the bits are rotating this ring. That’s why it is called a ring 
counter. 
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 44
Activity
� How does this counter work? (initial value: 1000)
D Q D Q D Q D QIN
OUT1 OUT2 OUT3 OUT4
CLK
� Counts through the sequence: 1000, 1100, 1110, 1111, 0111, 0011, 0001, 0000
� Known as Mobius (or Johnson) counter
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 45
D Q D Q D Q D Q
OUT1 OUT2 OUT3 OUT4
CLK
"1"
Binary counter
� Logic between registers (not just multiplexer)
� XOR decides when bit should be toggled
� always for low-order bit,
only when first bit is true for second bit,
and so on
Here is a binary counter; the rule of thumb is that if all lower bits are true, than the upper 
bit should be toggled. OUT4 is the MSB while OUT1 is the LSB.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 46
EN
D
C
B
A
LOAD
CLK
CLR
RCO
QD
QC
QB
QA
(1) Low order 4-bits = 1111
(2) RCO goes high
(3) High order 4-bits 
are incremented
Four-bit binary synchronous up-counter
� Standard component with many applications
� positive edge-triggered FFs w/ synchronous load and clear inputs
� parallel load data from D, C, B, A
� enable inputs: must be asserted to enable counting
� ripple-carry out (RCO) is used for cascading counters
� high when counter is in its highest state 1111
� implemented using an AND gate
If we use the binary counter in the previous slide as a basic component, we can build 
many complicated circuits, e.g. a wider binary counter.
Preset
logic
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 47
� Starting offset counters – use of synchronous load
� e.g., 0110, 0111, 1000, 1001,
1010, 1011, 1100, 1101, 1111, 0110, . . .
� Ending offset counter – comparator for ending value
� e.g., 0000, 0001, 0010, ..., 1100, 1101, 0000
� Combinations of the above (start and stop value)
EN
D
C
B
A
LOAD
CLK
CLR
RCO
QD
QC
QB
QA
"1"
"0"
"0"
"0"
"0"
"0"
EN
D
C
B
A
LOAD
CLK
CLR
RCO
QD
QC
QB
QA
"1"
"0"
"1"
"1"
"0"
Offset counters
Other examples are here; using the load input, we can control the initial value. Or by 
using some product term from the stored values, we can configure the ending value of 
the counter.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 48
HDLs and Sequential Logic
� Flip-flops
� representation of clocks - timing of state changes
� asynchronous vs. synchronous
� Shift registers
� Simple counters
As a tidbit, we will see some Verilog programs (HDLs) for sequential logic circuits. 
Because of the characteristics of sequential logic systems, there are peculiar features.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 49
module dff (clk, d, q);
input clk, d;
output q;
reg q;
always @(posedge clk)
q = d;
endmodule
Flip-flop in Verilog
� Use always block's sensitivity list to wait for clock edge
This is an HDL program for a positive-edge triggered D FF. Again, reg is the keyword to 
declare a variable whose value needs to be tracked or stored. On the other hand, wire 
indicates a value that is passing between gates. Here posedge means the positive edge or 
the rising edge of the clock signal.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 50
module dff (clk, s, r, d, q);
input clk, s, r, d;
output q;
reg q;
always @(posedge clk)
if (r) q = 1'b0;
else if (s) q = 1'b1;
else q = d;
endmodule
module dff (clk, s, r, d, q);
input clk, s, r, d;
output q;
reg q;
always @(posedge r)
q = 1'b0;
always @(posedge s)
q = 1'b1;
always @(posedge clk)
q = d;
endmodule
More Flip-flops
� Synchronous/asynchronous reset/set
� single thread that waits for the clock
� three parallel threads – only one of which waits for the clock
Synchronous Asynchronous
Here synchronous and asynchronous flip-flops are described. 1’b0 means that this signal 
is 1 bit wide and 0 will be stored. In synch case, the FF is triggered only by the positive 
edge of the clock. Meanwhile, the asynch FF has three triggering variables.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 51
Verilog, constant syntax 
� Number in bits, apostrophe, radix (base number), and number
� Radix: b, o, d, h
Let me talk about how Verilog expresses the constant number here. By default, we use 
decimal numbers. If we want to use binary or hexadecimal number, we have to specify 
the radix. The number before the apostrophe is the number of bits for the constant.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 52
module dff (clk, d, q);
input clk, d;
output q;
reg q;
always @(clk)
q = d;
endmodule
Incorrect Flip-flop in Verilog
� Use always block's sensitivity list to wait for clock to change
Not correct! Q will
change whenever the
clock changes, not
just on an edge.
If we don’t specify the “posedge” at the clock signal, then the D’s value will be 
transferred to Q not only at the positive edge but also at the negative edge of the clock, 
which is not intended by the Verilog programmer.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 53
always @(posedge CLK)
begin
temp = B;
B = A;
A = temp;
end
always @(posedge CLK)
begin
A <= B;
B <= A;
end
Blocking and Non-Blocking Assignments
� Blocking assignments (X=A)
� completes the assignment before continuing on to next statement
� Non-blocking assignments (X<=A)
� completes in zero time and doesn’t change the value of the target 
until a blocking point (delay/wait) is encountered
� Example: swap
There are two kinds of assignments. In Verilog, the assignment statements within an 
always block are executed sequentially, which is on the left. If we use <= assignment, the 
value change is taking place at the end of the always block.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 54
Register-transfer-level (RTL) Assignment
� Non-blocking assignment is also known as an RTL assignment
� if used in an always block triggered by a clock edge
� all flip-flops change together
// B,C,D all get the value of A
always @(posedge clk)
begin
B = A;
C = B;
D = C;
end
// implements a shift register too
always @(posedge clk)
begin
B <= A;
C <= B;
D <= C;
end
An useful usage of the non-blocking assignment is shift registers, where all the bits (or 
values) are transferred in parallel. On the left, the behavior for the shift register has some 
problem.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 55
Mobius Counter in Verilog
initial
begin
A = 1’b0;
B = 1’b0;
C = 1’b0;
D = 1’b0;
end
always @(posedge clk)
begin
A <= ~D;
B <= A;
C <= B;
D <= C;
end
Here is an HDL specification of a Mobius counter
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 56
Binary Counter in Verilog
module binary_counter (clk, c8, c4, c2, c1);
input clk;
output c8, c4, c2, c1;
reg [3:0] count;
initial begin
count = 0;
end
always @(posedge clk) begin
count = count + 4’b0001;
end
assign c8 = count[3];
assign c4 = count[2];
assign c2 = count[1];
assign c1 = count[0];
endmodule
module binary_counter (clk, c8, c4, c2, c1, rco);
input clk;
output c8, c4, c2, c1, rco;
reg [3:0] count;
reg rco;
initial begin . . . end
always @(posedge clk) begin . . . end
assign c8 = count[3];
assign c4 = count[2];
assign c2 = count[1];
assign c1 = count[0];
assign rco = (count == 4’b1111);
endmodule
On the left, there is a Verilog description for a binary counter without rco; on the right, 
rco is also described.
VI - Sequential Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 57
Sequential logic summary
� Fundamental building block of circuits with state
� latch and flip-flop
� R-S latch, R-S master/slave, D master/slave, edge-triggered D flip-flop
� Timing methodologies
� use of clocks
� cascaded FFs work because propagation delays exceed hold times
� beware of clock skew
� Asynchronous inputs and their dangers
� synchronizer failure: what it is and how to minimize its impact
� Basic registers
� shift registers
� counters
� Hardware description languages and sequential logic