Digital Design: Sequential Circuits VHDL
Uploaded by
hiepphan6003Digital Design: Sequential Circuits VHDL
Uploaded by
hiepphan6003©
[Link]
Imec 2001
Course contents
Digital
• Digital design
design
• Combinatorial circuits: without status
Combina-
torial
Sequential circuits: with status
circuits
• FSMD design: hardwired processors
Sequential
circuits • Language based HW design: VHDL
FSMD
design
VHDL
3/1
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential
circuits
FSMD
design
VHDL
3/2
©
[Link]
Imec 2001
Sequential Circuits
Digital
The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential
circuits
FSMD
design
VHDL
3/3
©
[Link]
Imec 2001
The flip-flop as building block
Digital
• Definitions:
design
Combinatorial circuit: the output is function of the
Combina-
current value of the inputs
torial
circuits
Sequential circuit: the output is function of the
current value of the inputs and of the current state
Sequential (i.e. also function of the sequence of past inputs)
circuits
FSMD
design
VHDL
3/4
©
[Link]
Imec 2001
The flip-flop as building block
Digital
• Definitions
design
Asynchronous sequential circuits: outputs and state
Combina-
change as soon as an input changes
torial
circuits
Synchronous sequential circuits: outputs and state
change only when a special input, the clock, gets a
Sequential certain value
circuits
Clock period: duration between two consecutive
FSMD 10 transitions of the clock
design
Clock frequency: 1 / (clock period)
VHDL Duty cycle: (duration that the clock equals 1) /
(clock period)
Rising edge: 01 transition of the clock
Falling edge: 10 transition of the clock
3/5
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Flip-flop types
FSMD • Design of synchronous sequential circuits
design
• Design of asynchronous sequential circuits
VHDL
• Basic RTL building blocks
3/6
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Flip-flop types
FSMD • Design of synchronous sequential circuits
design
• Design of asynchronous sequential circuits
VHDL
• Basic RTL building blocks
3/7
©
[Link]
Imec 2001
SR Latch
Digital S R Q(next)
design
Set 0 0 Q
Q’
Combina-
0 1 0
torial 1 0 1
circuits
1 1 NA
Sequential Reset Q
circuits
FSMD
design
S
VHDL
Q’
Undefined
3/8
©
[Link]
Imec 2001
SR Latch
Digital
• Note that a Boolean signal now already
design
consists of 5 values:
Combina- 0: the logical signal “0”
torial
circuits 1: the logical signal “1”
x: don’t care
Sequential
circuits Z: high impedant
U: undefined
FSMD
design
• The oscillation is called critical race
VHDL • The oscillation only happens when the delay
of both gates is exactly equal
• When the delays are not equal, the fastest
gates determines the end result:
implementation and run-time dependent
undefined
3/9
©
[Link]
Imec 2001
SR Latch
Digital S R Q(next)
design
Set 1 1 Q
Q
Combina-
1 0 0
torial 0 1 1
circuits
0 0 NA
Sequential Reset Q’
circuits Set and Reset active low
FSMD
design
S
VHDL
Q’
3/10
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Flip-flop types
FSMD • Design of synchronous sequential circuits
design
• Design of asynchronous sequential circuits
VHDL
• Basic RTL building blocks
3/11
©
[Link]
Imec 2001
Gated SR Latch
Digital
design Set C=1: follow inputs
Combina-
Q’ C=0: latch outputs
torial
circuits Clock
Sequential
circuits Q
Reset
FSMD
design C S R Q(next)
0 0 0 Q
VHDL
0 0 1 Q
0 1 0 Q
0 1 1 Q
1 0 0 Q
1 0 1 0
1 1 0 1
1 1 1 NA
3/12
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Flip-flop types
FSMD • Design of synchronous sequential circuits
design
• Design of asynchronous sequential circuits
VHDL
• Basic RTL building blocks
3/13
©
[Link]
Imec 2001
Gated D Latch
D C=1: follow input
Digital C=0: latch output
design Q’
C D Q(next)
Combina-
Clock 0 0 Q
torial 0 1 Q
circuits
Q 1 0 0
Sequential 1 1 1
circuits
DQ delay when C high: L-to-H delay: 2.4+1.4+1.4=5.2
FSMD
design H-to-L delay: 1+2.4+1.4=4.8
CQ delay when D high: L-to-H delay: 2.4+1.4+1.4=5.2
VHDL when D low: H-to-L delay: 2.4+1.4=3.8
3/14
©
[Link]
Imec 2001
Gated D Latch
D C=1: follow input
S
Digital C=0: latch output
design Q’
C D Q(next)
Combina-
Clock 0 0 Q
torial 0 1 Q
circuits
R Q 1 0 0
Sequential 1 1 1
circuits
D must not change “immediately before” H-to-L of the
clock (during the setup time); reason: clock changes
FSMD
design between the switching of D and of D’ hence Set and
Reset switch from H to L at the same time undefined
VHDL (setup time = H-to-L of invertor)
D
C
S
D’
R
3/15
©
[Link]
Imec 2001
Gated D Latch
D C=1: follow input
S
Digital C=0: latch output
design Q’
C D Q(next)
Combina-
Clock 0 0 Q
torial 0 1 Q
circuits
R Q 1 0 0
Sequential 1 1 1
circuits
When D switches at least setup time before the clock
FSMD transition, S and R will not switch from H to L at the
design
same time OK (S is longer high than R, hence Q will
come high following the D input)
VHDL
D
C
S
D’
R
3/16
©
[Link]
Imec 2001
Gated D Latch
D C=1: follow input
S
Digital C=0: latch output
design Q’
C D Q(next)
Combina-
Clock 0 0 Q
torial 0 1 Q
circuits
R Q 1 0 0
Sequential 1 1 1
circuits
FSMD Analogously, D may not switch “immediately after” H-to-L
design
of the clock (during the hold time)
VHDL
Symbol
Given values:
D Q 5.2=C to QLH
5.2/3.8 3.8=C to QHL
C Q’
3/17
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Level-sensitive latch
FSMD Master-slave flip-flop
design
Edge-triggered flip-flop
VHDL
Flip-flop types
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/18
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Level-sensitive latch
FSMD Master-slave flip-flop
design
Edge-triggered flip-flop
VHDL
Flip-flop types
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/19
©
[Link]
Imec 2001
Level sensitive latch
Digital
• All previous gated latches are level sensitive
design
Transparent when clock is high
Combina- Remembering the last value when clock is low
torial
circuits • Level sensitive latches give problems for shift
Sequential
registers for example
circuits The input signal may ripple through multiple stages
FSMD
during one clock-high phase
design making it very hard to meet setup/hold time
VHDL
requirements
See next slide
3/20
©
[Link]
Imec 2001
Level sensitive latch
X Y
Digital
design
D Q1 D Q2 D Q3
4/3 4/3 4/3
Combina- C C C
torial
circuits Clk
Sequential
circuits
Clk
FSMD
design
X
VHDL Q1
Q2
Q3
Two solutions:
• Master-slave
• Edge-triggered
3/21
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Level-sensitive latch
FSMD Master-slave flip-flop
design
Edge-triggered flip-flop
VHDL
Flip-flop types
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/22
©
[Link]
Imec 2001
Master-slave flip-flop
X Master Slave Q1 Master Slave Y
Digital D Qm1 D Qs1 D Qm2 D Qs2
design
4/3 4/3 4/3 4/3
Combina-
C C C C
torial Clk
circuits
Sequential
circuits
Clk
FSMD
design
X
VHDL Qm1
Q1
Qm2
The master clocks at the falling clock edge
The slave clocks at the rising edge
3/23
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
SR Latch
Combina- Gated SR Latch
torial
circuits Gated D Latch
Flip-flop sensitivity
Sequential
circuits Level-sensitive latch
FSMD Master-slave flip-flop
design
Edge-triggered flip-flop
VHDL
Flip-flop types
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/24
©
[Link]
Imec 2001
Edge-triggered flip-flop
A Set Latch Output
Digital Latch
design Set
Q
Combina-
torial Clk
circuits
Reset Q’
Sequential
circuits
B
D Reset Latch
FSMD
design
VHDL Clk
D
B
A
R
S
3/25
Q
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital SR Latch
design
Gated SR Latch
Combina-
torial
Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL
D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/26
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital SR Latch
design
Gated SR Latch
Combina-
torial
Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL
D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/27
©
[Link]
Imec 2001
SR flip-flop
Digital Symbol Characteristic table
design
(for design of SR flip-flop)
Combina-
S Q S R Q(next)
torial
circuits Clk 0 0 Q
R Q’ 0 1 0
Sequential 1 0 1
circuits
Triangle next to clock 1 1 NA
FSMD means positive
design edge-triggered
Negative edge-triggered
VHDL
Excitation table
Positive level triggered (for design with SR flip-flop)
Q Q(next) S R
Negative level triggered
0 0 0 x
0 1 1 0
1 0 0 1
1 1 x 0
3/28
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital
design SR Latch
Gated SR Latch
Combina-
torial Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/29
©
[Link]
Imec 2001
JK flip-flop
Digital Symbol Characteristic table
design
(for design of JK flip-flop)
Combina-
J Q J K Q(next)
torial
circuits Clk 0 0 Q
K Q’ 0 1 0
Sequential 1 0 1
circuits
1 1 Q’
FSMD
design
VHDL
Excitation table
(for design with JK flip-flop)
Q Q(next) J K
Circuits that use 0 0 0 x
JK flip-flops are cheaper 0 1 1 x
than those using SR flip-flops: 1 0 x 1
more don’t cares 1 1 x 0
3/30
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital
design SR Latch
Gated SR Latch
Combina-
torial Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/31
©
[Link]
Imec 2001
D flip-flop
Digital Symbol Characteristic table
design
(for design of D flip-flop)
Combina-
D Q
torial D Q(next)
circuits Clk
0 0
Q’
1 1
Sequential
circuits
FSMD
design
VHDL
Excitation table
(for design with D flip-flop)
Q Q(next) D
Designing with D flip-flop 0 0 0
is easy 0 1 1
1 0 0
1 1 1
3/32
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital
design SR Latch
Gated SR Latch
Combina-
torial Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/33
©
[Link]
Imec 2001
T flip-flop
Digital Symbol Characteristic table
design
(for design of T flip-flop)
Combina-
T Q
torial T Q(next)
circuits Clk
0 Q
Q’
1 Q’
Sequential
circuits
FSMD
design
VHDL
Excitation table
(for design with T flip-flop)
T D Q Q Q(next) T
0 0 0
Clk
0 1 1
Q’
1 0 1
1 1 0
3/34
©
[Link]
Imec 2001 Sequential Circuits
• The flip-flop as building block
Digital
design SR Latch
Gated SR Latch
Combina-
torial Gated D Latch
circuits
Flip-flop sensitivity
Sequential Flip-flop types
circuits
SR flip-flop
FSMD
design JK flip-flop
VHDL D flip-flop
T flip-flop
Asynchronous set and reset
• Design of synchronous sequential circuits
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/35
©
[Link]
Imec 2001
Asynchronous set and reset
Preset
Digital
design A
Combina-
torial Set
circuits Q
Clk
Sequential
circuits Reset
Q’
FSMD
design B
D
VHDL
Clear
PRS
D Q
Asynchronous set and reset are
useful to put the flip-flop Clk Q’
initially in a known state
CLR
(see lab sessions)
3/36
©
[Link]
Imec 2001
Asynchronous set and reset
Digital
• Why are the asynchronous preset and clear
design
connected to both layers of SR-flip-flops?
Combina- The first layer passes input modifications to the
torial
circuits
second layer only at the rising clock edge
The second layer reacts immediately, without
Sequential
circuits
waiting for the rising clock edge => needed for
asynchronous reaction
FSMD If they were only connected to the second layer, the
design
first layer would not know in what state the second
VHDL layer was put and could give a conflicting command
to the second layer at the next rising clock edge,
e.g. reset since D=0 and at the same time an
asynchronous preset
3/37
©
[Link]
Imec 2001
Asynchronous set and reset
Digital
• Why are the asynchronous preset and clear
design
active low?
Combina- Because ‘wired-or’ of ‘open drain’ circuits is used to
torial
circuits
avoid short circuits when there are multiple sources
driving them:
Sequential
circuits R
FSMD
Open
design No No drain
preset preset
VHDL
Implements an AND
function (hence ‘wired-
or’ ...) with unlimited
number of inputs:
preset preset The bus is only ‘1’
when all inputs to the
bus are equal to ‘1’
3/38
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential
circuits
FSMD
design
VHDL
3/39
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/40
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/41
©
[Link]
Imec 2001
Finite State Machine
Digital
• Design a modulo 4 “Counter”, that counts when
design the input “CE” (Count Enable) equals 1 and stops
Combina-
counting when the input “CE” equals 0.
torial
circuits
• Step 1: translate to a Finite State Machine (FSM):
Sequential
circuits
CE=0 CE=0
FSMD
design CE=1
Count=0 Count=1
VHDL
CE=1 CE=1
CE=0 Count=3 Count=2 CE=0
CE=1
3/42
©
[Link] Finite State Machine
Transition to the next state happens at each rising clock edge
Imec 2001
(a synchronous FSM is clocked!).
At each rising clock edge, exactly one transition condition
should be true: for each input combination, a transition should
Digital
design be specified in each of the states.
CE=0 CE=0
Combina-
torial CE=1
circuits Count=0 Count=1
Sequential
circuits
CE=1 CE=1
FSMD
design
CE=0 Count=3 Count=2 CE=0
VHDL
CE=1
1. We are in state “Count=0”
2. CE input equals 0: we are waiting at the tip of the edge
3. CE=1: wait at tip of other edge, but do not count yet!
4. Rising clock edge: go to “Count=1”, still with CE=1
5. CE input becomes 0: wait at tip of other edge
3/43 6. Rising clock edge: go to “Count=1”, with CE=0
©
[Link]
Imec 2001
Finite State Machine
Digital
• Step 2: Minimise the number of states.
design
It is already the minimum number.
Combina- • Step 3: Encode the states:
torial
circuits
Sequential
circuits
CE=0 CE=0
FSMD
CE=1
design Q1Q0=00 Q1Q0=01
VHDL
CE=1 CE=1
CE=0 Q1Q0=11 Q1Q0=10 CE=0
CE=1
3/44
©
[Link]
Imec 2001
Finite State Machine
Digital
• Step 4: Select the flip-flop type. We select the
design
D type for its simplicity.
Combina- • Step 5: Realise the circuit. See next slides:
torial
circuits
Sequential
circuits
FSMD
design
VHDL
3/45
©
[Link]
Imec 2001
Finite State Machine
Digital
• Translate the FSM in a next-state table:
design
CE=0 CE=0
Combina-
torial CE=1
circuits
Q1Q0=00 Q1Q0=01
Sequential
circuits CE=1 CE=1
FSMD
design CE=0 Q1Q0=11 Q1Q0=10 CE=0
CE=1
VHDL
Present state Next state
Q1Q0 Q 1nQ 0n
CE=0 CE=1
00 00 01
01 01 10
10 10 11
3/46
11 11 00
©
[Link]
Imec 2001
Finite State Machine
Digital
• Determine the excitation functions:
design
Present state Next state
Combina- Q1Q0 Q 1nQ 0n
torial
circuits CE=0 CE=1
00 00 01
Sequential
circuits
01 01 10
10 10 11
FSMD
design
11 11 00
Excitation table
VHDL
for D flip-flop Q0 Q0
Q Q(next) D Q1n=D1 Q0n=D0
Q1 Q1
0 0 0
0 1 1 0 0 1 1 0 1 1 0
1 0 0 0 1 0 1 1 0 0 1
CE CE
1 1 1
D to be applied
3/47 is identical to Qn
©
[Link]
Imec 2001
Finite State Machine
Digital
• Implement:
design
Q0 Q0
Combina-
torial
Q1n=D1 Q1 Q0n=D0 Q1
circuits
0 0 1 1 0 1 1 0
Sequential
circuits CE 0 1 0 1 CE 1 0 0 1
FSMD CE Q1 Q0
design
Q1
VHDL Q1n
D1
Q’
Q0
Q0n
D0
Q’
3/48
©
[Link]
Imec 2001
Finite State Machine
Digital
• Step 6: Timing analysis
design CE Q1 Q0
Combina-
Q1
torial Q1n
circuits D1
Q’
Sequential
circuits
Q0
Q0n
FSMD D0
design
Q’
VHDL
Clk
CE
Q1
Q0
3/49
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/50
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Design a modulo 4 “Counter”, that counts
design
when the “CE” input equals 1 and stops
Combina- counting when “CE” equals 0. The output “Y”
torial
circuits equals 1 when the count value equals 3.
Sequential
• Step 1: translate to FSM:
circuits
CE=0 CE=0
FSMD
design
Count=0 CE=1 Count=1
VHDL Y=0 Y=0
CE=1 CE=1
CE=0 Count=3 Count=2 CE=0
Y=1 Y=0
CE=1
3/51
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Be extremely careful about timing issues!! Assume
design
that the Y output is used as a load-enable for a register
Combina- and as the add/subtract line for an adder/subtractor:
torial
circuits when arriving in state 3, Y becomes 1, immediately
causing the adder/subtractor to switch to “subtract”
Sequential
circuits mode, but NOT causing the register to load a new
FSMD
value!!! The loading will only occur at the next state
design transition (i.e. the next clock edge)
VHDL
LE Clocked
Register Clk
CE
Counter
Add/Subtract Combinatorial
3/52 A/S’
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• State-based:
design
the output is indicated for each state
Combina- the output is only function of the current state, not
torial
circuits
of the inputs applied
Hence, the output value is indicated in the circle
Sequential
circuits
representing the state
FSMD
design
VHDL
3/53
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Step 2: Minimise the number of states. This is
design
already the minimum number.
Combina- • Step 3: Encode the states:
torial
circuits
Sequential
circuits
CE=0 CE=0
FSMD
design Q1Q0=00 CE=1 Q1Q0=01
Y=0 Y=0
VHDL
CE=1 CE=1
CE=0 Q1Q0=11 Q1Q0=10 CE=0
Y=1 Y=0
CE=1
3/54
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Step 4: Select the flip-flop type. We select the
design
D type for its simplicity.
Combina- • Step 5: Realise the circuit. See next slides:
torial
circuits
Sequential
circuits
FSMD
design
VHDL
3/55
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Translate the FSM in a next-state table:
design
CE=0 CE=0
Combina-
torial Q1Q0=00 CE=1 Q1Q0=01
circuits Y=0 Y=0
Sequential
circuits CE=1 CE=1
FSMD Q1Q0=10
CE=0 Q1Q0=11 CE=0
design
Y=1 Y=0
CE=1
VHDL
Present state Next state Outputs Y is
Q1Q0 Q 1nQ 0n Y only
CE=0 CE=1 dependent
00 00 01 0 on the
current
01 01 10 0
state,
10 10 11 0 not on
3/56 11 11 00 1 the inputs
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Determine the excitation functions:
design
Present state Next state Outputs
Combina-
Q1Q0 Q 1nQ 0n Y
torial CE=0 CE=1
circuits
00 00 01 0
Sequential 01 01 10 0
circuits
10 10 11 0
FSMD 11 11 00 1
design
Q0 Q0
Excitation table
VHDL
for D flip-flop Q1n=D1 Q1 Q0n=D0 Q1
Q Q(next) D
0 0 1 1 0 1 1 0
0 0 0
0 1 1 CE 0 1 0 1 CE 1 0 0 1
1 0 0
1 1 1 Q0
Y
D to be applied 0 0
3/57 is identical to Qn Q1 0 1
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Implement:
design
Q0 Q0
Combina-
torial
Q1n=D1 Q1 Q0n=D0 Q1 Q0
circuits Y
0 0 1 1 0 1 1 0 0 0
Sequential
circuits CE 0 1 0 1 CE 1 0 0 1 Q1 0 1
FSMD CE Q1 Q0
design
Q1 Y
VHDL Q1n
D1
Q’
Q0
Q0n
D0
Q’
3/58
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Step 6: Timing analysis
design CE Q1 Q0
Combina-
Q1 Y
torial Q1n
circuits D1
Q’
Sequential
circuits
Q0
Q0n
FSMD D0
design
Q’
VHDL
Clk
CE
Q1
Danger for
Q0 Glitch!
3/59 Y
©
[Link]
Imec 2001
State-based or Moore-type FSM
Digital
• Is a glitch harmful?
design
When the output with the glitch is connected to the
Combina-
clock of some clocked circuit:
torial
circuits This clocked circuit will unintentionally
clock: harmful
Sequential
circuits Hard to debug: glitch may disappear
FSMD when probe is connected due to
design
increased capacitance and hence also
VHDL increased delay
When the output with the glitch is connected to a
combinatorial circuit that eventually is the input of
a register:
Not harmful, since the register looks at
its input only at the clock edge
Dissipates unnecessary power
3/60
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/61
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Design a modulo 4 “Counter”, that counts when
design the “CE” input equals 1 and stops counting when
Combina-
“CE” equals 0. The “Y” output value equals 1
torial
circuits
when the count=3 while the input “CE” equals 1.
• Step 1: translate to FSM:
Sequential
circuits
CE=0/Y=0 CE=0/Y=0
FSMD
design
CE=1/Y=0
Count=0 Count=1
VHDL
CE=1/Y=1 CE=1/Y=0
CE=0/Y=0 Count=3 Count=2 CE=0/Y=0
CE=1/Y=0
3/62
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Transition to the next state happens
Digital at each rising clock edge
design
CE=0/Y=0 CE=0/Y=0
Combina-
torial CE=1/Y=0
circuits Count=0 Count=1
Sequential
circuits
CE=1/Y=1 CE=1/Y=0
FSMD
design
CE=0/Y=0 Count=3 Count=2 CE=0/Y=0
VHDL
CE=1/Y=0
1. We are in state “Count=2”
2. CE input equals 1: wait at tip of edge with Y=0
3. Rising clock edge: go to “Count=3”, still with CE=1: Y=1
4. C input becomes 0: wait at tip of other edge with Y=0;
combinatorial circuit driven by Y reacts, clocked don’t
3/63 5. Rising clock edge: Y=0 is clocked into output register
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Be extremely careful about timing issues!! Assume
design
that the Y output is used as a load-enable for a register
Combina- and as the add/subtract line for an adder/subtractor:
torial
circuits when arriving in state 3 with CE=1, Y becomes 1
adder/subtractor switches to “subtract”, but register
Sequential
circuits doesn’t load new value!!! When CE=0, Y becomes 0
FSMD
adder/subtractor switches to “add”, and LE=0. When
design the next clock edge comes while CE=0, register will
VHDL
not load.
LE Clocked
Register Clk
CE
Counter
Add/Subtract Combinatorial
3/64 A/S’
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Input-based:
design
the output is specified for each state and each
Combina-
combination of inputs in that state
torial
circuits
the output is function of the current state, and of
the applied inputs
Sequential Hence the output is specified next to each
circuits
transition
FSMD
design
VHDL
3/65
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Step 2: Minimise the number of states. This is
design
already the minimum number.
Combina- • Step 3: Encode the states:
torial
circuits
Sequential
circuits
CE=0/Y=0 CE=0/Y=0
FSMD
CE=1/Y=0
design Q1Q0=00 Q1Q0=01
VHDL
CE=1/Y=1 CE=1/Y=0
CE=0/Y=0 Q1Q0=11 Q1Q0=10 CE=0/Y=0
CE=1/Y=0
3/66
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Step 4: Select the flip-flop type. We select the
design
D type for its simplicity.
Combina- • Step 5: Realise the circuit. See next slides:
torial
circuits
Sequential
circuits
FSMD
design
VHDL
3/67
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Translate FSM to next-state table:
design
CE=0/Y=0 CE=0/Y=0
Combina-
torial CE=1/Y=0
circuits
Q1Q0=00 Q1Q0=01
Sequential
circuits CE=1/Y=1 CE=1/Y=0
FSMD
design CE=0/Y=0 Q1Q0=11 Q1Q0=10 CE=0/Y=0
CE=1/Y=0
VHDL
Present state Next state/Outputs Y does
Q1Q0 Q 1nQ 0n/Y not only
CE=0 CE=1 depend
00 00/0 01/0 on the
current
01 01/0 10/0 state,
10 10/0 11/0 but also on
3/68 11 11/0 00/1 the inputs
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Determine the excitation functions:
design Present state Next state/Outputs
Combina-
Q1Q0 Q 1nQ 0n/Y
torial CE=0 CE=1
circuits
00 00/0 01/0
Sequential 01 01/0 10/0
circuits
10 10/0 11/0
FSMD 11 11/0 00/1
design Q0 Q0
Excitation table Q1n=D1 Q1 Q0n=D0 Q1
VHDL
for D flip-flop
Q Q(next) D 0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 1 0 0 1
CE CE
0 1 1 Q0
1 0 0 Y Q1
1 1 1
0 0 0 0
D to be applied
3/69 is identical to Qn CE 0 0 1 0
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Implement:
design
Q0 Q0 Q0
Combina-
torial
Q1n=D1 Q1 Q0n=D0 Q1 Y Q1
circuits
0 0 1 1 0 1 1 0 0 0 0 0
Sequential
circuits CE 0 1 0 1 CE 1 0 0 1 CE 0 0 1 0
FSMD CE Q1 Q0
design
Q1 Y
VHDL Q1n
D1
Q’
Q0
Q0n
D0
Q’
3/70
©
[Link]
Imec 2001
Input-based or Mealy-type FSM
Digital
• Step 6: Timing analysis
design CE Q1 Q0
Combina- Q1 Y
torial Q1n
circuits D1
Q’
Sequential
circuits
Q0
Q0n
FSMD D0
design
Q’
VHDL
Clk
CE
Q1
Danger for
Q0 Glitch!
3/71 Y
©
State-based model
[Link]
Imec 2001
Next Current
Inputs I Clock
State S* State S
Digital
design
D Q
Combina-
torial Clk
circuits
Outputs
O
Sequential S*=F(S,I)
circuits
D Q O=H(S)
Next Clk
FSMD Output
design State
Combi-
Combi-
nato-
VHDL nato-
rial
rial
Logic
Logic
D Q
Clk
3/72
©
Input-based model
[Link]
Imec 2001
Clock Next State S* Current
Inputs I State S
Digital
design
D Q
Combina-
torial Clk
circuits
Outputs
O
Sequential S*=F(S,I)
circuits
D Q O=H(S,I)
Next Clk
FSMD Output
design State
Combi-
Combi-
nato-
VHDL nato-
rial
rial
Logic
Logic
D Q
Clk
3/73
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/74
©
[Link]
Imec 2001
Step 1: construction of the FSM
• The first step in the design of synchronous sequential circuits
Digital is the construction of the FSM starting from the description in
design
natural language (ambiguous and incomplete)
Combina-
• Example: Modulo-3 up/down counter
torial Count enable (C):
circuits
C=1: count
Sequential C=0: do not count
circuits
Direction (D):
FSMD D=1: count down
design
D=0: count up
VHDL Output (Y): Y=1 when (count equals 2 and we count up) or
when (count equals 0 and we count down)
What is the meaning of “We count up”?
Do we have to “count” (C=1) and “up” (D=0)
or is it sufficient that the direction is “up”
(C=X and D=0)?
Ambiguous; I choose for the first
3/75
©
[Link]
Imec 2001
Step 1: construction of the FSM
Digital
• First step: is this a State-based or an Input-
design
based design?
Combina- It is Input-based, since the output depends on the
torial
circuits
state and the input
• Second step: construct the FSM starting from
Sequential
circuits the first state, for each combination of inputs
FSMD
from each state
design See next slide
VHDL
Note: when an output needs to remain high during
several consecutive states, it should be assigned a
‘high’ value in each of these states!! Each output
should be assigned a value in each state!
3/76
©
[Link]
Imec 2001
Step 1: construction of the FSM
CD=10
Y=1
Digital
design
CD=0X CD=0X CD=0X
Y=0 Y=0 Y=0
Combina-
torial CD=10 CD=10
circuits
u0 Y=0 u1 Y=0 u2
Sequential CD=10
circuits CD=10 Y=0 CD=11
Y=1 Y=0
FSMD
design CD=11
CD=10
Y=0 Y=1
VHDL CD=11
Y=0
d0 d1 d2
CD=11 CD=11
Y=0 Y=0
CD=0X CD=0X CD=0X
Y=0 Y=0 Y=0
CD=11
Y=1
3/77
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/78
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Goal: less states means less flip-flops
design
• Principal: equivalent behavior of two FSMs
Combina-
torial
• Two FSMs are equivalent when they produce
circuits
the same output sequence for the same input
Sequential sequence
circuits
FSMD
design
VHDL
3/79
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Two states in an FSM may be replaced by 1
design
state when both states produce the same
Combina- outputs for the same inputs and when both
torial
circuits jump to equivalent next states for the same
inputs
Sequential
circuits
• Formally: states sj and sk are equivalent
FSMD (sjsk) if and only if
design
iI: h(sj,i)=h(sk,i): both states produce the same
VHDL
output for each combination of inputs
and
iI: f(sj,i)f(sk,i): the next states are equivalent for
each input combination
3/80
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• In practice: build the next state table out of
design
the state diagram first
Combina- PRESENT NEXT STATE / OUTPUT
torial STATE CD=0X CD=10 CD=11
circuits
u0 u 0/0 u 1/0 d 2/1
Sequential u1 u 1/0 u 2/0 d 0/0
circuits
u2 u 2/0 u 0/1 d 1/0
FSMD
d0 d 0/0 u 1/0 d 2/1
design d1 d 1/0 u 2/0 d 0/0
d2 d 2/0 u 0/1 d 1/0
VHDL
3/81
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Construct the implication table: 1 square per
design
combination of 2 states
Combina- PRESENT NEXT STATE / OUTPUT
torial STATE CD=0X CD=10 CD=11
circuits
u0 u 0/0 u 1/0 d 2/1
Sequential u1 u 1/0 u 2/0 d 0/0
circuits
u2 u 2/0 u 0/1 d 1/0
FSMD
d0 d 0/0 u 1/0 d 2/1
design d1 d 1/0 u 2/0 d 0/0
u1 d2 d 2/0 u 0/1 d 1/0
VHDL
u2
d0
d1
d2
u0 u1 u2 d0 d1
3/82
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Delete all combinations that have different
design
outputs for the same inputs
Combina- PRESENT NEXT STATE / OUTPUT
torial STATE CD=0X CD=10 CD=11
circuits
u0 u 0/0 u 1/0 d 2/1
Sequential u1 u 1/0 u 2/0 d 0/0
circuits
u2 u 2/0 u 0/1 d 1/0
FSMD
d0 d 0/0 u 1/0 d 2/1
design d1 d 1/0 u 2/0 d 0/0
u1 d2 d 2/0 u 0/1 d 1/0
VHDL
u2
d0
d1
d2
u0 u1 u2 d0 d1
3/83
©
[Link]
Imec 2001
Step 2: minimise the number of states
• Indicate for the remaining which next states have to be
Digital
design equivalent to make the current states equivalent
Combina-
torial
circuits PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11
Sequential u0 u 0/0 u 1/0 d 2/1
circuits
u1 u 1/0 u 2/0 d 0/0
FSMD u2 u 2/0 u 0/1 d 1/0
design
d0 d 0/0 u 1/0 d 2/1
u1 d1 d 1/0 u 2/0 d 0/0
VHDL
u2 d2 d 2/0 u 0/1 d 1/0
d0 OK Minimum number
of states: 3 ie.
d1 OK
{u0,d0}=s0
d2 OK {u1,d1}=s1
{u2,d2}=s2
u0 u1 u2 d0 d1
3/84
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Construct the new next state table
design
PRESENT NEXT STATE / OUTPUT
Minimum number
STATE CD=0X CD=10 CD=11
Combina- of states: 3 ie.
torial u0 u 0/0 u 1/0 d 2/1
circuits {u0,d0}=s0
{u1,d1}=s1 u1 u 1/0 u 2/0 d 0/0
Sequential
{u2,d2}=s2 u2 u 2/0 u 0/1 d 1/0
circuits
d0 d 0/0 u 1/0 d 2/1
FSMD
d1 d 1/0 u 2/0 d 0/0
design d2 d 2/0 u 0/1 d 1/0
VHDL
PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11
s0 s 0/0 s 1/0 s 2/1
s1 s 1/0 s 2/0 s 0/0
s2 s 2/0 s 0/1 s 1/0
3/85
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• FYI: draw new state diagram
design
PRESENT NEXT STATE / OUTPUT
Combina-
STATE CD=0X CD=10 CD=11
torial s0 s 0/0 s 1/0 s 2/1
circuits
s1 s 1/0 s 2/0 s 0/0
Sequential s2 s 2/0 s 0/1 s 1/0
circuits
CD=10
Y=1
FSMD
design
CD=0X CD=0X CD=0X
Y=0 Y=0 Y=0
VHDL CD=10 CD=10
Y=0 Y=0
s0 s1 s2
CD=11 CD=11
Y=0 Y=0
CD=11 This could have been constructed from the begin
3/86 Y=1 -ning, but better 1 state too much than too little
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• This example did not show how you should
design
manipulate the implication table
Combina- • Hence an imaginary example showing all
torial
circuits problems:
Sequential
circuits
PRESENT NEXT STATE / OUTPUT
FSMD STATE AB=00 AB=01 AB=10
design
s0 s 4/1 s 2/0 s 1/1
VHDL
s1 s 2/0 s 5/1 s 4/1
s2 s 1/1 s 0/0 s 3/1
s3 s 2/0 s 5/1 s 4/1
s4 s 0/0 s 5/1 s 1/1
s5 s 2/0 s 4/1 s 2/1
3/87
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Construct the implication table: 1 square per
design
combination of 2 states
Combina-
torial
PRESENT NEXT STATE / OUTPUT
circuits STATE AB=00 AB=01 AB=10
Sequential
s0 s 4/1 s 2/0 s 1/1
circuits s1 s 2/0 s 5/1 s 4/1
s2 s 1/1 s 0/0 s 3/1
FSMD
design s3 s 2/0 s 5/1 s 4/1
s1 s4 s 0/0 s 5/1 s 1/1
VHDL
s5 s 2/0 s 4/1 s 2/1
s2
s3
s4
s5
s0 s1 s2 s3 s4
3/88
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Delete all combinations with different outputs
design
for same inputs
Combina-
torial
PRESENT NEXT STATE / OUTPUT
circuits STATE AB=00 AB=01 AB=10
Sequential
s0 s 4/1 s 2/0 s 1/1
circuits s1 s 2/0 s 5/1 s 4/1
s2 s 1/1 s 0/0 s 3/1
FSMD
design s3 s 2/0 s 5/1 s 4/1
s1 s4 s 0/0 s 5/1 s 1/1
VHDL
s5 s 2/0 s 4/1 s 2/1
s2
s3
s4
s5
s0 s1 s2 s3 s4
3/89
©
[Link]
Imec 2001
Step 2: minimise the number of states
• Indicate for the remaining which next states have to be
Digital
design equivalent to make the current states equivalent
Combina-
torial PRESENT NEXT STATE / OUTPUT
circuits
STATE AB=00 AB=01 AB=10
Sequential s0 s 4/1 s 2/0 s 1/1
circuits
s1 s 2/0 s 5/1 s 4/1
FSMD s2 s 1/1 s 0/0 s 3/1
design
s3 s 2/0 s 5/1 s 4/1
VHDL s1 s4 s 0/0 s 5/1 s 1/1
1-4 s5 s 2/0 s 4/1 s 2/1
s2 1-3
s3 OK
0-2
s4 0-2
1-4
4-5 4-5 0-2, 4-5
s5 2-4 2-4 1-2
3/90 s0 s1 s2 s3 s4
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Delete those states that are equivalent when non-
design equivalent next states would have been equivalent
Combina-
torial PRESENT NEXT STATE / OUTPUT
circuits
STATE AB=00 AB=01 AB=10
Sequential s0 s 4/1 s 2/0 s 1/1
circuits
s1 s 2/0 s 5/1 s 4/1
FSMD s2 s 1/1 s 0/0 s 3/1
design
s3 s 2/0 s 5/1 s 4/1
VHDL s1 s4 s 0/0 s 5/1 s 1/1
1-4:
1-4 ? s5 s 2/0 s 4/1 s 2/1
s2 1-3:OK
1-3
s3 OK
0-2:
0-2 ?
s4 0-2:
0-2 ?
1-4:
1-4 ?
4-5 4-5 0-2, 4-5
s5 2-4 2-4 1-2
3/91 s0 s1 s2 s3 s4
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Delete again as long as states are deleted
design
during an iteration
Combina-
torial PRESENT NEXT STATE / OUTPUT
circuits
STATE AB=00 AB=01 AB=10
Sequential s0 s 4/1 s 2/0 s 1/1
circuits
s1 s 2/0 s 5/1 s 4/1
FSMD s2 s 1/1 s 0/0 s 3/1
design
s3 s 2/0 s 5/1 s 4/1
VHDL s1 s4 s 0/0 s 5/1 s 1/1
1-4: ? s5 s 2/0 s 4/1 s 2/1
s2 1-3:OK
Minimum number
s3 OK
of states: 3 ie.
0-2: ?
s4 0-2: ?
1-4: ?
{s0,s2}=u0
4-5 4-5 0-2, 4-5 {s1,s3,s4}=u1
s5 2-4 2-4 1-2 {s5}=u2
3/92 s0 s1 s2 s3 s4
©
[Link]
Imec 2001
Step 2: minimise the number of states
Digital
• Construct the new next state table
design
Minimum number PRESENT NEXT STATE / OUTPUT
Combina- of states: 3 ie. STATE AB=00 AB=01 AB=10
torial
circuits
{s0,s2}=u0 s0 s 4/1 s 2/0 s 1/1
{s1,s3,s4}=u1 s1 s 2/0 s 5/1 s 4/1
Sequential {s5}=u2 s2 s 1/1 s 0/0 s 3/1
circuits
s3 s 2/0 s 5/1 s 4/1
FSMD s4 s 0/0 s 5/1 s 1/1
design
s5 s 2/0 s 4/1 s 2/1
VHDL
PRESENT NEXT STATE / OUTPUT
STATE A B =00 A B =01 A B =10
u0 u 1/1 u 0/0 u 1/1
u1 u 0/0 u 2/1 u 1/1
u2 u 0/0 u 1/1 u 0/1
3/93
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/94
©
[Link]
Imec 2001
Step 3: State encoding
Digital • n states require at least log2n flip-flops.
design
• There are n! possible encodings (n choices for
Combina-
torial
the first state, n-1 for the second, etc.)
circuits
Sequential
circuits
No. s0 s1 s2 s3 No. s0 s1 s2 s3
1 00 01 10 11 13 10 00 01 11
FSMD
design 2 00 01 11 10 14 10 00 11 01
3 00 10 01 11 15 10 01 00 11
VHDL 4 00 10 11 01 16 10 01 11 00
5 00 11 01 10 17 10 11 00 01
6 00 11 10 01 18 10 11 01 00
7 01 00 10 11 19 11 00 01 10
8 01 00 11 10 20 11 00 10 01
9 01 10 00 11 21 11 01 00 10
10 01 10 11 00 22 11 01 10 00
11 01 11 00 10 23 11 10 00 01
12 01 11 10 00 24 11 10 01 00
3/95
©
[Link]
Imec 2001
Step 3: State encoding
Digital
• Does the chosen encoding matters?
design
Yes. Each choice leads to a different combinatorial
Combina-
circuit with different cost and delay.
torial
circuits • Often chosen encodings:
Straightforward
Sequential
circuits Minimum-bit-change
One-hot
FSMD
design
VHDL
3/96
©
[Link]
Imec 2001
Step 3: State encoding:
Straightforward
Digital
• Straightforward encoding uses the binary
design
representation of the state number as code
Combina- (s0000, s5101, …)
torial
circuits • Straightforward encoding is mostly used
Sequential when the state number has a physical
circuits
meaning
FSMD E.g. a counter whose count value is sent to a
design
display
VHDL • Straightforward encoding is dangerous for
glitches and leads to non-minimal area and
power consumption: multiple bits have to
change at each state transition (multiple bit-
changes seldomly happen concurrently; each bit-
change requires some logic to implement it; each bit-
change consumes power)
3/97
©
[Link]
Imec 2001
Step 3: State encoding:
Straightforward
Digital
design
PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11
Combina- s0 s 0/0 s 1/0 s 2/1
torial
circuits
s1 s 1/0 s 2/0 s 0/0
s2 s 2/0 s 0/1 s 1/0
Sequential
circuits
FSMD
design PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11
VHDL
00 00/0 01/0 10/1
01 01/0 10/0 00/0
10 10/0 00/1 01/0
3/98
©
[Link]
Imec 2001
Step 3: State encoding:
Minimum-bit-change
Digital
• For minimum-bit-change encoding we assign
design
the codes such that the total number of bit-
Combina- changes for all state transitions is minimal
torial
circuits • Minimum-bit-change encoding is mostly used
Sequential
when area and power need to be minimized
circuits
(CMOS)
FSMD
design
VHDL 1 1
00 01 00 01
Gray code
counter
2 2 1 1
1 1
11 10 10 11
3/99 Straightforward Minimum-bit-change
©
[Link]
Imec 2001
Step 3: State encoding:
Minimum-bit-change
PRESENT NEXT STATE / OUTPUT
Digital STATE
design
CD=0X CD=10 CD=11
s0 s 0/0 s 1/0 s 2/1
Combina- s1 s 1/0 s 2/0 s 0/0
torial
circuits
s2 s 2/0 s 0/1 s 1/0
Sequential
circuits 0 1
All transitions are equally likely
FSMD Preferrably only 1 bit difference
design
between each pair of transitions
This can only be realised between two
VHDL
2 of the three pairs
PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11 Possible
00 00/0 10/0 11/1 encoding:
10 10/0 11/0 00/0 s0=00
s1=10
11 11/0 00/1 10/0
3/100 s2=11
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
Digital
• Each state has 1 flip-flop, hence no encoding;
design
Q of 1 FF =1, Q of others=0
Combina- • Flip-flop cost = O(n) i.o. O(logn), hence only
torial
circuits useful for small number of states: controller
Sequential • Very easy to realise: short design time (time-
circuits
to-market, e.g. exam…)
FSMD
design
• Very small combinatorial circuits to drive the
inputs of the flip-flops: cheap combinatorial
VHDL
part, more expensive flip-flop part
An FPGA possesses per half CLB a small
combinatorial circuit and 1 flip-flop: one-hot
encoding is ideal for FPGA implementations (except
counters: too many states)
3/101
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
PRESENT NEXT STATE / OUTPUT
Digital STATE
design
CD=0X CD=10 CD=11
s0 s 0/0 s 1/0 s 2/1
Combina- s1 s 1/0 s 2/0 s 0/0
torial
circuits
s2 s 2/0 s 0/1 s 1/0
Sequential
circuits One-hot encoding
s0=001
FSMD
design
s1=010
s2=100
VHDL
PRESENT NEXT STATE / OUTPUT
STATE CD=0X CD=10 CD=11
001 001/0 010/0 100/1
010 010/0 100/0 001/0
100 100/0 001/1 010/0
3/102
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
CD=0X CD=0X CD=0X
Digital CD=10
design Y=0 Y=0 Y=0
Y=1 CD=10 CD=10
Y=0 Y=0
Combina-
torial s0 s1 s2
circuits
CD=11 CD=11 CD=11
Y=1 Y=0 Y=0
Sequential
circuits
FSMD
design
Q0 Q1 C Q2 C
P
VHDL D D D Y
C
3/103
D
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
Digital
• Implementation rule for One-hot with D flip-
design
flop:
Combina- Each arriving transition at a state needs an AND
torial
circuits
gate
Sequential
circuits
FSMD
design
VHDL
3/104
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
CD=0X CD=0X CD=0X
Digital CD=10
design Y=0 Y=0 Y=0
Y=1 CD=10 CD=10
Y=0 Y=0
Combina-
torial s0 s1 s2
circuits
CD=11 CD=11 CD=11
Y=1 Y=0 Y=0
Sequential
circuits
FSMD
design
P Q0 Q1 C Q2 C
VHDL S R S R S R Y
C
3/105 D
©
[Link]
Imec 2001
Step 3: State encoding:
One-hot
Digital
• Implementation rule for One-hot with SR flip-
design
flop:
Combina- Each arriving transition starting at another state
torial
circuits
requires an AND gate at the S input
Each departing transition to another state requires
Sequential
circuits
an AND gate at the R input
FSMD
design
VHDL
3/106
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/107
©
[Link]
Imec 2001
Step 4: Choice of the flip-flop type
Digital
• JK flip-flop
design
Most expensive flip-flop
Combina- Most difficult design
torial
circuits Largest number of don’t cares: probably cheapest
(and fastest) combinatorial control logic
Sequential
circuits Used when a different signal sets resp. resets the
flip-flop
FSMD
design • SR flip-flop
Cheap flip-flop
VHDL
Difficult design
Many don’t cares: probably cheap (and fast) control
logic
Used when a different signal sets resp. resets the
flip-flop
3/108
©
[Link]
Imec 2001
Step 4: Choice of the flip-flop type
Digital
• D flip-flop
design
Cheap flip-flop
Combina- Most easy design
torial
circuits No don’t cares: probably most expensive (and
slowest) combinatorial control logic
Sequential
circuits Used when the same signal sets resp. resets the
flip-flop, i.e. when the value of a signal has to be
FSMD
design
remembered temporarily
• T flip-flop
VHDL
Cheap flip-flop
Easy design
No don’t cares: probably most espensive (and
slowest) combinatorial control logic
Used for counters and frequency dividers: fast
toggling
3/109
©
[Link]
Imec 2001
Step 4: Choice of the flip-flop type
Digital
• No fixed selection rule exists
design
When we want the cheapest circuit, all variants
Combina-
have to be tried out
torial
circuits
When the fastest design time is needed, D flip-flops
are the best choice
Sequential FPGAs only possess D flip-flops
circuits
FSMD
design
VHDL
3/110
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/111
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: D flip-flop
Digital
• Determine the excitation functions
design Q0
PRESENT NEXT STATE / OUTPUT Y Q1
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1 0 0 x 0
Sequential 01 01/0 10/0 00/0 0 0 x 0
circuits D
10 10/0 00/1 01/0 1 0 x 0
C
FSMD 0 0 x 1
design
Excitation table Q0 Q0
VHDL
for D flip-flop Q1n=D1 Q1 Q0n=D0 Q1
Q Q(next) D
0 0 0 0 0 x 1 0 1 x 0
0 1 1 0 0 x 1 0 1 x 0
1 0 0 D D
1 0 x 0 0 0 x 1
1 1 1 C C
0 1 x 0 1 0 x 0
D to be applied
3/112 is identical to Qn
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: D flip-flop
Q0 Q0 Q0
Digital
design
Q1n=D1 Q1 Q0n=D0 Q1 Y Q1
Combina- 0 0 x 1 0 1 x 0 0 0 x 0
torial
circuits 0 0 x 1 0 1 x 0 0 0 x 0
D D D
1 0 x 0 0 0 x 1 1 0 x 0
Sequential C C C
circuits 0 1 x 0 1 0 x 0 0 0 x 1
FSMD
design
Q1 Clr Q0 Clr
Cost: 35
VHDL D D Y
1.5 CLB
C
D
3/113
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: T flip-flop
Digital
• Determine the excitation functions
design Q0
PRESENT NEXT STATE / OUTPUT Y Q1
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1 0 0 x 0
Sequential 01 01/0 10/0 00/0 0 0 x 0
circuits D
10 10/0 00/1 01/0 1 0 x 0
C
FSMD 0 0 x 1
design
Excitation table Q0 Q0
VHDL
for T flip-flop T1 Q1 T0 Q1
Q Q(next) T
0 0 0 0 0 x 0 0 0 x 0
0 1 1 0 0 x 0 0 0 x 0
1 0 1 D D
1 1 0
1 0 x 1 0 1 x 1
C C
0 1 x 1 1 1 x 0
3/114
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: T flip-flop
Q0 Q0 Q0
Digital
design
T1 Q1 T0 Q1 Y Q1
Combina- 0 0 x 0 0 0 x 0 0 0 x 0
torial
circuits 0 0 x 0 0 0 x 0 0 0 x 0
D D D
1 0 x 1 0 1 x 1 1 0 x 0
Sequential C C C
circuits 0 1 x 1 1 1 x 0 0 0 x 1
FSMD
design
Q1 Clr Q0 Clr
Cost: 32
VHDL T T Y
C
D
3/115
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: SR flip-flop
Digital
• Determine the excitation functions
design
PRESENT NEXT STATE / OUTPUT
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1
Sequential 01 01/0 10/0 00/0
circuits 10 10/0 00/1 01/0
FSMD
design
Excitation table Q0 Q0
VHDL
for SR flip-flop S1 Q1 R1 Q1
Q Q(next) S R
0 0 0 x 0 0 x x x x x 0
0 1 1 0 0 0 x x x x x 0
1 0 0 1 D D
1 0 x 0 0 x x 1
1 1 x 0 C C
0 1 x 0 x 0 x 1
3/116
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: SR flip-flop
Digital
• Determine the excitation functions
design Q0
PRESENT NEXT STATE / OUTPUT Y Q1
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1 0 0 x 0
Sequential 01 01/0 10/0 00/0 0 0 x 0
circuits D
10 10/0 00/1 01/0 1 0 x 0
C
FSMD 0 0 x 1
design
Excitation table Q0 Q0
VHDL
for SR flip-flop S0 Q1 R0 Q1
Q Q(next) S R
0 0 0 x 0 x x 0 x 0 x x
0 1 1 0 0 x x 0 x 0 x x
1 0 0 1 D D
0 0 x 1 x 1 x 0
1 1 x 0 C C
1 0 x 0 0 1 x x
3/117
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: SR flip-flop
Q0 Q0
Digital S1 Q1 R1 Q1
design
0 0 x x x x x 0
Combina-
torial 0 0 x x x x x 0
circuits
D D
1 0 x 0 0 x x 1
Sequential C C
circuits 0 1 x 0 x 0 x 1
FSMD
design
Q1 C Q0 C
VHDL S R S R
C
3/118 D
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: SR flip-flop
Q0 Q0
Digital S0 Q1 R0 Q1
design
0 x x 0 x 0 x x
Combina-
torial 0 x x 0 x 0 x x
circuits
D D
0 0 x 1 x 1 x 0
Sequential C C
circuits 1 0 x 0 0 1 x x
FSMD
design
Q1 C Q0 C
VHDL S R S R
C
3/119 D
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: SR flip-flop
Q0 Q0 Q0
Digital S0 Q1 R0 Q1 Y Q1
design
0 x x 0 x 0 x x 0 0 x 0
Combina-
torial 0 x x 0 x 0 x x 0 0 x 0
circuits
D D D
0 0 x 1 x 1 x 0 1 0 x 0
Sequential C C C
circuits 1 0 x 0 0 1 x x 0 0 x 1
FSMD
design
Q1 C Q0 C
Y Cost: 32
VHDL S R S R
C
3/120 D
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: JK flip-flop
Digital
• Determine the excitation functions
design
PRESENT NEXT STATE / OUTPUT
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1
Sequential 01 01/0 10/0 00/0
circuits 10 10/0 00/1 01/0
FSMD
design
Excitation table Q0 Q0
VHDL
for JK flip-flop J1 Q1 K1 Q1
Q Q(next) J K
0 0 0 x 0 0 x x x x x 0
0 1 1 x 0 0 x x x x x 0
1 0 x 1 D D
1 0 x x x x x 1
1 1 x 0 C C
0 1 x x x x x 1
3/121
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: JK flip-flop
Digital
• Determine the excitation functions
design Q0
PRESENT NEXT STATE / OUTPUT Y Q1
Combina-
torial STATE CD=0X CD=10 CD=11
circuits
00 00/0 01/0 10/1 0 0 x 0
Sequential 01 01/0 10/0 00/0 0 0 x 0
circuits D
10 10/0 00/1 01/0 1 0 x 0
C
FSMD 0 0 x 1
design
Excitation table Q0 Q0
VHDL
for JK flip-flop J0 Q1 K0 Q1
Q Q(next) J K
0 0 0 x 0 x x 0 x 0 x x
0 1 1 x 0 x x 0 x 0 x x
1 0 x 1 D D
0 x x 1 x 1 x x
1 1 x 0 C C
1 x x 0 x 1 x x
3/122
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: JK flip-flop
Q0 Q0
Digital J1 Q1 K1 Q1
design
0 0 x x x x x 0
Combina-
torial 0 0 x x x x x 0
circuits
D D
1 0 x x x x x 1
Sequential C C
circuits 0 1 x x x x x 1
FSMD
design
Q1 C Q0 C
VHDL J K J K
C
3/123 D
©
[Link]
Imec 2001
Step 5: Realization of the
combinatorial logic: JK flip-flop
Q0 Q0 Q0
Digital J0 Q1 K0 Q1 Y Q1
design
0 x x 0 x 0 x x 0 0 x 0
Combina-
torial 0 x x 0 x 0 x x 0 0 x 0
circuits
D D D
0 x x 1 x 1 x x 1 0 x 0
Sequential C C C
circuits 1 x x 0 x 1 x x 0 0 x 1
FSMD
design
Q1 C Q0 C
Y Cost: 26
VHDL J K J K
C
3/124 D
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina- Finite State Machine (FSM)
torial
circuits State-based or Moore-type FSM
Sequential
Input-based or Mealy-type FSM
circuits Step 1: State diagram
FSMD Step 2: State minimization
design
Step 3: State encoding
VHDL Step 4: Choice of the flip-flop type
Step 5: Realization of the combinatorial logic
Step 6: Timing analysis
• Design of asynchronous sequential circuits
• Basic RTL building blocks
3/125
©
[Link]
Imec 2001
Step 6: Timing analysis
Digital
• Determine maximum clock frequency
design
Max. clock frequency = 1/(delay of critical path)
Combina- Critical path is the path with the longest
torial
circuits
combinatorial delay between two clock edges
Example:
Sequential
circuits
FSMD
design
Q1 Clr Q0 Clr
VHDL D D Y
C
D
3/126
©
[Link]
Imec 2001
Step 6: Timing analysis
• Delay of critical path (assume zero
connection delay):
Digital
design clockQ0 + invertor + 4-input AND + 3-input OR +
setup Dclock
Combina-
torial = 5.2 + 1.0 + (2.2+1.0) + (1.8+1.0) + 1.0 = 13.2
circuits
ns (assuming that our relative times can be
Sequential considered to be nanoseconds)
circuits
fmax = 76 MHz (same assumption)
FSMD
design
Q1 Clr Q0 Clr
VHDL D D Y
C
D
3/127
©
[Link]
Imec 2001
Step 6: Timing analysis
Digital
• After designing the combinatorial circuits for
design
next state and output, all traditional design
Combina- steps follow:
torial
circuits Technology mapping
Placement and routing
Sequential
circuits Timing simulation
FSMD • Timing simulation is even more important for
design
sequential circuits than for combinatorial
VHDL circuits
Determine the maximum clock frequency to check
whether setup and hold times are satisfied
Avoid, if necessary because of connected circuits,
glitches when a state transition involves multiple
bit-flips
3/128
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential
circuits
FSMD
design
VHDL
3/129
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
Definitions and Fundamental Mode Restriction
Sequential Design
circuits
• Basic RTL building blocks
FSMD
design
VHDL
3/130
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
Definitions and Fundamental Mode Restriction
Sequential Design
circuits
• Basic RTL building blocks
FSMD
design
VHDL
3/131
©
[Link]
Imec 2001
Asynchronous Sequential Circuits
Digital
• Definitions:
design
Sequential circuit: the output is function of the
Combina-
current value of the inputs and of the current state
torial (i.e. also function of the sequence of past inputs)
circuits
Asynchronous sequential circuits: outputs and state
Sequential change as soon as an input changes
circuits
• Fundamental mode restriction:
FSMD
design
only one input may change at a time; the next input
change may only occur when all effects to the
VHDL previous input change died out
• Goal: design of small asynchronous circuits,
e.g. interfaces between two synchronous
islands with not-correlated clocks or clocks
with unpredictable clock skew
3/132
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
Definitions and Fundamental Mode Restriction
Sequential Design
circuits
• Basic RTL building blocks
FSMD
design
VHDL
3/133
©
[Link]
Imec 2001
Example circuit: requirements
• Design a circuit with two inputs (I and E) and
Digital
design one output Q.
If E is high, a rising edge on I causes Q to go high.
Combina-
torial Q stays high until E goes low.
circuits
While E is low, Q is low.
Sequential
circuits
FSMD
design
VHDL
3/134
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/135
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/136
©
[Link]
Imec 2001
State table
Digital
• List all states: each possible combination of
design
inputs and outputs is a state
Combina-
torial Q I E State
circuits
0 0 0 a
0 0 1 b
Sequential
circuits 0 1 0 c
0 1 1 d
FSMD
1 0 0 impossible
design
1 0 1 e
VHDL 1 1 0 impossible
1 1 1 f
3/137
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/138
©
[Link]
Imec 2001
State transition diagram
01 11 11
Digital Q I E State
design
0 0 0 a
Combina-
e/0 f/0 0 0 1 b
torial
01 0 1 0 c
circuits
0 1 1 d
IE 00 11 1 0 0 impossible
Sequential
01
circuits
00 1 0 1 e
01
1 1 0 impossible
FSMD
design a/0 b/0 1 1 1 f
00
VHDL 10
We opted for a
10 00 01
Moore or state
11
10 based design; we
11
could as well have
c/0 d/0 chosen a Mealy
10 approach, with
output per
transition
3/139
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/140
©
[Link]
Imec 2001
Primitive flow table
Digital
IE Q I E State
design
S 00 01 11 10 Q 0 0 0 a
Combina- a a b x c 0 0 0 1 b
torial
b a b f x 0 0 1 0 c
circuits
c a x d c 0 0 1 1 d
Sequential d x b d c 0 1 0 0 impossible
circuits
e a e f x 1 1 0 1 e
f x e f c 1 1 1 0 impossible
FSMD
design 1 1 1 f
VHDL
3/141
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/142
©
[Link]
Imec 2001
Minimized flow table
Digital
• Rule: merge compatible states: states with
design
same next states and outputs or don’t cares
Combina- • ‘Compatibility’ is not associative!
torial
circuits (a compatible b) AND (a compatible c) does
Sequential
NOT induce (b compatible c)
circuits
• Note that minimizing the number of states of
FSMD synchronous circuits requires equivalence
design
instead of compatibility.
VHDL States with same outputs and equivalent next
states
‘Equivalence’ is associative!
3/143
©
[Link]
Imec 2001
Minimized flow table
IE
Digital S 00 01 11 10 Q Are a and b compatible?
design
a a b x c 0
YES, hence merge them
Combina- b a b f x 0
torial
circuits
c a x d c 0
d x b d c 0
Sequential e a e f x 1
circuits
f x e f c 1
FSMD
design
IE
VHDL S 00 01 11 10 Q
f c 0
c x d c 0
d x d c 0
e e f x 1
f x e f c 1
3/144
©
[Link]
Imec 2001
Minimized flow table
IE
Digital Are c and d compatible?
design S 00 01 11 10 Q
f c 0 YES, hence merge them
Combina-
c x d c 0
torial
circuits d x d c 0
e e f x 1
Sequential
circuits f x e f c 1
FSMD
design
IE
VHDL
S 00 01 11 10 Q
f 0
0
e e f x 1
f x e f 1
3/145
©
[Link]
Imec 2001
Minimized flow table
IE
Digital Are e and f compatible?
design S 00 01 11 10 Q
ff
0
0 YES, hence merge them
Combina-
0
torial 0
circuits e
e ff x 1
e e x 1
ff x e ff
1
x e 1
Sequential
circuits
FSMD IE
design
S 00 01 11 10 Q This minimized flow table
0 is called the
VHDL
0 Transition Table
1
3/146
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/147
©
[Link]
Imec 2001
State assignment
IE Assume we make following
Digital
S 00 01 11 10 Q straightforward
design
state assignment:
0
Combina- : 00
0
torial : 01
circuits 1
: 11
Sequential
circuits IE
S 00 01 11 10 Q
FSMD 00 00 00 11 01 0
design
01 00 00 01 01 0
VHDL
11 00 11 11 01 1
3/148
©
[Link]
Imec 2001
State assignment
Digital
design
IE
Combina- S 00 01 11 10 Q
torial
circuits
00 00 00 11 01 0
01 00 00 01 01 0
Sequential 11 00 11 11 01 1
circuits
FSMD
design
VHDL
S0 S0
S0n S1 S1n S1
0 0 0 x 0 0 0 x
0 0 1 x 0 0 1 x S0
E E
I 1 1 1 x I 1 0 1 x 0 0
1 1 1 x 0 0 0 x S1 x 1
3/149
©
[Link]
Imec 2001
State assignment
Digital
design I E S1 S0
Combina-
torial
circuits
Sequential
circuits
Q
FSMD
design
VHDL
S0 S0
S0n S1 S1n S1
0 0 0 x 0 0 0 x
0 0 1 x 0 0 1 x S0
E E
I 1 1 1 x I 1 0 1 x 0 0
1 1 1 x 0 0 0 x S1 x 1
3/150
©
State assignment
[Link]
Imec 2001
I E S1 S0 IE
Digital S 00 01 11 10 Q
design
00 00 00 11 01 0
Combina- 01 00 00 01 01 0
torial
circuits
11 00 11 11 01 1
Sequential
circuits Q
FSMD
design Let’s animate behav from state S=00 with inputs IE=01->11
Step 1: Stable state S=00 with inputs IE=01
VHDL
Step 2: Inputs change to IE=11
Step 3: after 2-input gate delay, OR-gate switches,
making S0=1
No Step 4: we are stuck in stable state S=01 because
both state bits did not change at the same time
The fact that 2 or more state variables have to change,
when 1 input-bit changes is called a RACE CONDITION
When this leads to the wrong final state,
3/151 it’s called a CRITICAL RACE
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/152
©
[Link]
Imec 2001
Elimination of critical races
Digital
• Solution: make the state assignment such
design
that never 2 or more state variables need to
Combina- change following a single input change
torial
circuits
IE 00 01
Sequential
S 00 01 11 10 Q
circuits
0
FSMD 0
design
1
VHDL 11
No encoding can be found satisfying the above rule!
3/153
©
[Link]
Imec 2001
Elimination of critical races
Digital
• Do the state assignment as good as you can.
design
Use additional states to solve the problems
Combina- that remain
torial
circuits
IE
S 00 01 11 10 Q Don’t care because both
Sequential
circuits 00 00 00 10
11 01 0 new transitions require
01 00 00 01 01 0 an output change: it
FSMD is not important whether
11 10
00 11 11 01 1
design this already happens in
10 00 x 11 x x
the intermediate state
VHDL
Highlight remaining problems
Route these transitions via an additional state, which
differs in only one state variable
3/154
©
[Link]
Imec 2001
Elimination of critical races
Digital IE
design S 00 01 11 10 Q
00 00 00 10 01 0
Combina-
torial 01 00 00 01 01 0
circuits 11 10 11 11 01 1
10 00 x 11 x x
Sequential
circuits
FSMD
design
VHDL
S0 S0
S0n S1 S1n S1
0 0 0 0 0 0 1 0
0 0 1 x 0 0 1 x S0
E E
I 0 1 1 1 I 1 0 1 1 0 0
1 1 1 x 0 0 0 x S1 x 1
3/155
©
[Link]
Imec 2001
Elimination of critical races
I E S1 S0
Digital
design
Combina-
torial
circuits
Sequential
circuits
FSMD
design
Q
VHDL
S0 S0
S0n S1 S1n S1
0 0 0 0 0 0 1 0
0 0 1 x 0 0 1 x S0
E E
I 0 1 1 1 I 1 0 1 1 0 0
3/156 1 1 1 x 0 0 0 x S1 x 1
©
[Link]
Imec 2001
Elimination of critical races
Digital IE
design S 00 01 11 10 Q
00 00 00 10 01 0
Combina-
torial 01 00 00 01 01 0
circuits 11 10 11 11 01 1
10 00 00
x 11 01
x x
Sequential
circuits Race, but not critical
FSMD What happens at power-up?
design
The circuit could as well start in state S=10 with an
VHDL input of IE=01
It then depends on the actual values of the don’t cares
what is going to happen; it could even remain stable
in that state...
It would hence be wise to remove the don’t cares and
replace them with an evolution to a stable state with
the same inputs
3/157
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/158
©
[Link]
Imec 2001
Hazard free combinatorial design
Digital
• The combinatorial circuits of an asynchronous
design
design should be designed in a hazard free
Combina- way
torial
circuits Static hazard: a status variable that is supposed not
to change, briefly changes; this could lead to a
Sequential
circuits
wrong final state
Dynamic hazard: a status variable that is supposed
FSMD
design
to change just once, changes three times; this
could lead to a wrong final state
VHDL
• Synchronous designs do not need to be
hazard free, since state variables are only
taken into account on a clock edge
• Our design was hazard free, and hence
should not be changed
3/159
©
[Link]
Imec 2001 Design flow
State table
Digital
design
State transition diagram
Combina-
torial
circuits
Primitive flow table
Sequential
circuits
Minimized flow table
FSMD
design
State assignment
VHDL
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
3/160
©
[Link]
Imec 2001
Avoidance of input skew
Digital
• Assume that input I is skewed on the bottom
design
AND gate with respect to the other inputs
Combina-
IE
torial S 00 01 11 10 Q
circuits
I E S1 S0 00 00 00 10 01 0
Sequential 01 00 00 01 01 0
circuits 11 10 11 11 01 1
10 00 11 11 01 1
FSMD
design
Start in state S=01 with IE=11
VHDL
I becomes 0: S should go to 00
Now the delayed version of I
goes to zero
State however does not change
Q anymore and ends in the
incorrect S=11
Delay State variables may change only after all input
3/161 changes are applied to all gates!
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
Basic RTL building blocks
Sequential
circuits
FSMD
design
VHDL
3/162
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/163
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/164
©
[Link]
Imec 2001
Registers
Digital
• Register
design
I3 I2 I1 I0
Combina-
torial
circuits
D Q D Q D Q D Q
Sequential
circuits
FSMD
design
Clk
VHDL
Q3 Q2 Q1 Q0
I3 I2 I1 I0
Register Symbol
3/165 Q3 Q2 Q1 Q0
©
[Link]
Imec 2001
Registers
Digital
• Asynchronously presettable and clearable
design Register
Combina- I3 I2 I1 I0
torial
circuits
Preset
Sequential D Q D Q D Q D Q
circuits
FSMD
design Clear
Clk
VHDL Q3 Q2 Q1 Q0
I3 I2 I1 I0
Preset
Register Symbol
Clear
3/166 Q3 Q2 Q1 Q0
©
[Link]
Imec 2001
Registers
Digital
• Loadable register (without gated clock)
design
I3 I2 I1 I0
Combina-
torial
circuits 1 0 1 0 1 0 1 0
S S S S
Sequential
circuits
Load
FSMD D Q D Q D Q D Q
design
VHDL
Clk
Q3 Q2 Q1 Q0
• Loads only when “Load=1”
• High power dissipation: multiple gates switch whenever the
clock changes
• No clock skew problems since each flip-flop is clocked by the
3/167
master clock
©
[Link]
Imec 2001
Registers
Digital
• Loadable register (without gated clock)
design
Combina-
torial
circuits I3 I2 I1 I0
Sequential Load
circuits
Register Symbol
FSMD
design
Q3 Q2 Q1 Q0
VHDL
3/168
©
[Link]
Imec 2001
Registers
Digital
• Loadable register (with gated clock)
design
I3 I2 I1 I0
Combina-
torial
circuits D Q D Q D Q D Q
Sequential
circuits CE
FSMD
design Clk
Q3 Q2 Q1 Q0
VHDL
• Clocks only when “CE=1”
• Low power dissipation: gates only switch when a new
value is loaded
• Gated clocks (derived clocks) are sensitive to clock
3/169
skew
©
[Link]
Imec 2001
Registers
Digital
• Loadable register (with gated clock)
design
Combina-
torial
circuits I3 I2 I1 I0
Sequential CE
circuits
Register Symbol
FSMD
design
Q3 Q2 Q1 Q0
VHDL
3/170
©
[Link]
Imec 2001
Registers
• Clock skew problem for
Digital
design gated clocks:
Not all clocks of all registers
Combina-
change concurrently I3 I2 I1 I0
torial
circuits Expected behavior:
Sequential
New I3..0 applied Register 1
circuits
At next clock edge:
FSMD Clk*11, Clk*21 A3..0
design
Q*3..0A3..0, A*3..0I3..0 CE
Real behavior: Register 2
VHDL
New I3..0 applied
At next clock edge: Q3 Q2 Q1 Q0
Clk*11
A*3..0I3..0, Clk*21
Q*3..0A*3..0
Risk for setup violation
3/171
©
[Link]
Imec 2001
Registers
I A Q
Digital
design
D0 Q0 D1 Q1
Combina-
torial
Clk
circuits
CE
Sequential Possible setup or hold
circuits
violation for 2nd flip-flop
FSMD
design Clk
VHDL I
CE
Gated
Clk
Q
3/172
©
[Link]
Imec 2001
Registers
Digital
• What causes clock skew?
design
Gated clocks
Combina- Different relative routing delay
torial
circuits On PCB and within chip: different wire
Sequential
length
circuits
In FPGA: different number of routing
FSMD switches
design
• Delay depends on many things:
VHDL
temperature, power supply voltage, fan-out, IC
batch
under no circumstance clock skew may cause
problems!!! worst case analysis (e.g. min-delay
for data path and max-delay for clock path and vice
versa)
3/173
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/174
©
[Link]
Imec 2001
Shift registers
Digital
• Serial-in/parallel-out shift register (SIPO)
design
IL
Combina-
torial
circuits 1 0 1 0 1 0 1 0
S S S S
Sequential
circuits
SE
FSMD D Q D Q D Q D Q
design
VHDL
Clk
Q3 Q2 Q1 Q0
Example of utilization:
Receive register (Rx) serial port
Delay line for FIR and IIR filters
3/175
©
[Link]
Imec 2001
Shift registers
Digital
• Serial-in/parallel-out shift register (SIPO)
design
Combina-
torial
circuits
Sequential IL
circuits
Shift Register Symbol
SE
FSMD
design
Q3 Q2 Q1 Q0
VHDL
3/176
©
[Link]
Imec 2001
Shift registers
Digital
• Parallel-in/serial-out shift register (PISO)
design
IL I3 I2 I1 I0
Combina-
torial
circuits 1 0 1 0 1 0 1 0
S S S S
Sequential
circuits
Sh/Ld
FSMD D Q D Q D Q D Q
design
Clk
VHDL
CE
Q0
Example of utilization: Transmit register (Tx) serial port
3/177
©
[Link]
Imec 2001
Shift registers
Digital
• Parallel-in/serial-out shift register (PISO)
design
Combina-
torial
circuits I3 I2 I1 I0
Sequential IL
circuits
Shift Symbol
FSMD CE Register
design Sh/Ld’
VHDL
Q0
3/178
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/179
©
[Link]
Imec 2001
Synchronous counters
Digital
• Synchronous up-counter
design
Combina-
E
torial
circuits
Sequential HA HA HA
circuits
FSMD D Q D Q D Q
design
VHDL Clear
Clk Output Q2 Q1 Q0
carry
Synchronous because all flip-flops are clocked by the
same signal
3/180
©
[Link]
Imec 2001 Glitch! Synchronous counters
Digital
E
design
Combina-
torial HA HA HA
circuits
Sequential D Q D Q D Q
circuits
FSMD Clear
design
Clk Output
VHDL Q2 Q1 Q0
carry
Clk
Clear
E
Q0
Q1
Q2
3/181
©
[Link]
Imec 2001
Synchronous counters
Digital
• Synchronous up/down-counter
design
D
Combina-
E
torial Co Ci
circuits HAS HAS HAS
Sequential
circuits
FSMD D Q D Q D Q
design
VHDL Clear
Clk Output Q2 Q1 Q0
carry
Half adder/subtractor
3/182
©
[Link]
Imec 2001
Synchronous counters
Digital
• Design of the Half adder/subtractor
design
Behavior:
Combina- D When ci=0 then Di=Qi (no counting)
torial co
circuits HAS ci When ci=1 this section should toggle
Qi C0 has to be 1 when the next section
Sequential
circuits has to toggle. When should this happen?
Di
FSMD
design
Up-count Down-count
VHDL
00 00
01 11
10 10
11 01
00 00
01 11
… …
Next section toggles Next section toggles
at 10 of this section at 01 of this section
3/183
©
[Link]
Imec 2001
Synchronous counters
Digital
• Design of the Half adder/subtractor
design ci Dir Qii Dii cci+1
i+1 Behavior:
0 0 0 0 0
0 When ci=0 then Di=Qi (no counting)
Combina-
torial 0 0 1 1 0
0 When ci=1 this section should toggle
circuits 0 1 0 0 0
0 C0 has to be 1 when the next section
0 1 1 1 0
0 has to toggle. When should this happen?
Sequential
circuits 1 0 0 1 0
0
1 0 1 0 1
1
FSMD 1 1 0 1 1
1
design
1 1 1 0 0
0 Up-count Down-count
00 00
VHDL
01 11
10 10
11 01
00 00
01 11
… …
Next section Next section
toggles at 10 toggles at 01
3/184 of this section of this section
©
[Link]
Imec 2001
Synchronous counters
Digital
• Design of the Half adder/subtractor
design
ci Dir Qi Di c i+1 Qi Qi
Combina- 0 0 0 0 0 Di Dir ci+1 Dir
torial
circuits 0 0 1 1 0
0 1 0 0 0 0 1 1 0 0 0 0 0
Sequential 0 1 1 1 0 ci 1 0 0 1 ci 0 1 0 1
circuits
1 0 0 1 0
FSMD
1 0 1 0 1
design 1 1 0 1 1
ci
1 1 1 0 0
VHDL Dir
Qi
Di ci+1
3/185
©
[Link]
Imec 2001
Synchronous counters
Digital
• Parallel loadable up/down-counter
design I2 I1 I0
D
Combina-
torial
circuits E
HAS HAS Co HAS
Sequential Ci
circuits
1 0 1 0 1 0
FSMD
design
Load
VHDL
D Q D Q D Q
Clear
Clk Output Q2 Q1 Q0
carry
3/186
©
[Link]
Imec 2001
Synchronous counters
Digital
• BCD up-counter
design
Combina-
torial
circuits 0 0 0 0
Sequential I3 I2 I1 I0
circuits
Up-counter
FSMD E
design Load Q3 Q2 Q1 Q0
VHDL
Compares with constant:
When count equals ‘1001’ (i.e. 9),
‘0000’ is loaded at next clock edge
3/187
©
[Link]
Imec 2001
Synchronous counters
Digital
• BCD up/down-counter
design
1 0 0 1 0 0 0 0
Combina-
torial 1 0
circuits
Mux
Sequential
circuits
FSMD
design
D I3 I2 I1 I0
Up/down-
VHDL
E counter
Load Q3 Q2 Q1 Q0
3/188
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/189
©
[Link]
Imec 2001
Asynchronous counters
Digital
E
design T Q T Q T Q T Q
Combina- Q’ Q’ Q’ Q’
torial
circuits
Clear
Sequential
circuits
FSMD Clk Q3 Q2 Q1 Q0
design
VHDL
Clk
Q0
Q1
Q2
Q3
3/190
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/191
©
[Link]
Imec 2001
Register files
Digital
design
Dout
WE D Q
Combina-
torial Din
circuits
Clk
Sequential RE
circuits
Register File Cell (RFC)
FSMD This implementation dissipates much power due to the
design
active memorization of data, but does not suffer from
VHDL
clock skew problems.
Combining ‘WE’ with ‘Clk’ into a gated clock, we can
reduce the power dissipation
Note that in both cases, Dout
Din D Q
‘writing’ is clocked, but
‘reading’ is not clocked!
WE
Needed for critical-path Clk
3/192
computation... RE
©
[Link]
Imec 2001
Register files
I3 I2 I1 I0
Digital
design
2-to-4
Combina-
0 read
torial dec
circuits RFC RFC RFC RFC
WA1 RA1
0
Sequential
WA0 1 RA0
circuits
RFC RFC RFC RFC
FSMD
design 1
WE 2 RE
VHDL
RFC RFC RFC RFC
2
3
2-to-4 RFC RFC RFC RFC
write 3
dec
O3 O2 O1 O0
3/193
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/194
©
[Link]
Imec 2001
LIFO queue - stack
Digital
design
Top empty
45
23
12
10 1. Reset
Combina-
torial 2. Push 45
circuits Top-1 empty
45
12
3. Push 12
Top-2 empty
45 4. Push 23
Sequential
circuits 5. Pop -> 23
Top-3 empty
6. Push 10
FSMD
design Top-4 empty
Top-5 empty
VHDL
Top-6 empty
Top-7 empty
3/195
©
[Link]
Imec 2001
LIFO queue - stack
Enable Push/pop’ Operations
Digital
0 0 No c hange
design
0 1 No c hange
Combina- 1 0 P op
torial
1 1 P ush
circuits
Sequential Using left/right’ shift register and counter for indication
circuits
empty/full
FSMD Count Empty Full
design Reset IL IR
L/R’ 0000 1 0
Enable O7 O0 0001 0 0
VHDL
0010 0 0
0011 0 0
0100 0 0
0101 0 0
0110 0 0
0111 0 0
1000 0 1
3/196
©
[Link]
Imec 2001
LIFO queue - stack
In0
0
Digital
design
Reset IL IR
L/R’
Enable O7 O0
Combina-
torial
circuits
Out0
In7
0
Sequential
circuits Reset IL IR
L/R’
Enable O7 O0
FSMD
design
Out7
VHDL Reset
Up/down’
Enable Q3..0
Reset’ Empty
Push/pop’
Enable Full
3/197
©
[Link]
Imec 2001
LIFO queue - stack
Digital
Alternative implementation: for large stacks
design
Does not 0=empty 0=full At
Combina-
shift! ‘Push’
torial Write Ptr both
circuits
0 empty
45 2
3
0
1 ptrs
Sequential
count up
circuits 1 empty
23
Read Ptr
2 empty
12
17 At ‘Pop’
FSMD
design 1
2
3
0 both
3 empty
52
ptrs
VHDL
count
1. Reset down
2. Push 45
3. Push 23
4. Push 12
5. Pop -> 12
6. Push 17
3/198 7. Push 52
©
[Link]
Imec 2001
LIFO queue - stack
Note: 10
SET Full/
Digital empty
design
R Up/down
U/D’ counter 1
Combina-
torial E Write ptr 2-to-1
circuits
MUX
S Up/down
Sequential U/D’ counter 0
circuits
E Read ptr S
FSMD Reset’
design
Push/
VHDL Pop’
Enable A 8
1Kx8 Data
CS RAM D in/out
R/W’
Watch timing of the enable: when RAM is not clocked
be careful not to read/write twice since the counters
3/199 count further
©
[Link]
Imec 2001
Sequential Circuits
Digital
• The flip-flop as building block
design
• Design of synchronous sequential circuits
Combina-
torial
• Design of asynchronous sequential circuits
circuits
• Basic RTL building blocks
Sequential Registers
circuits
Shift registers
FSMD
design
Counters
Synchronous counters
VHDL
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
3/200
©
[Link]
Imec 2001
FIFO queue
Digital
design
1. Reset
Top empty
45
23
12
57
Combina- 2. Write 45
torial
circuits Top-1 empty
45
23
12 3. Write 23
4. Write 12
Top-2 empty
45
23
Sequential 5. Read -> 45
circuits
Top-3 empty 6. Write 57
FSMD
design Top-4 empty
Top-5 empty
VHDL
Top-6 empty
Top-7 empty
3/201
©
[Link]
Imec 2001
FIFO queue
In0
Digital
Reset IL
design
Enable O7 O0
Combina- 7
torial
circuits In7 Uit0
0 S2..0
Sequential Reset IL
circuits Read
pointer Enable O7 O0
FSMD 7
design
Uit7
0 S2..0
VHDL
Set
Up/down’
Enable Q3..0
Reset’
Read/ Empty
write’
Enable Full
3/202
©
[Link]
Imec 2001
FIFO queue
Digital
Alternative implementation: for large FIFO’s
design
Does not Wrap-around Only write
Combina- shift! pointer incr.
torial Write Ptr at write
circuits
0 empty
45
16 2
3
0
1
Sequential
circuits 1 empty
23
Read Ptr
2 empty
12
FSMD
design 0
1 Only read
3 empty
57 pointer incr.
VHDL at read
1. Reset
2. Write 45
Read and write
3. Write 23
pointer equal: empty
4. Write 12 or full
5. Read -> 45
6. Write 57
3/203 7. Write 16
©
[Link]
Imec 2001
FIFO queue
Digital
• Previous implementation indicates empty/full
design
but does not distinguish between both
Combina- • Solution:
torial
circuits assume queue depth equals 2n
read and write pointer are hence n-bit up-counters
Sequential
circuits select however an (n+1)-bit up-counter:
FSMD
n-LSB of read and write equal: empty/full
design
MSB equal: empty
VHDL
MSB different: full
apply only the n-LSB as address for RAM-
queue
• For the stack, we also did not differentiate
between empty and full; how can it be solved
there?
3/204
©
[Link]
Imec 2001
FIFO queue
MSB Full
Digital
design
10-LSB =? Empty
Combina-
torial
circuits R 11-bit Up
E counter 0
Sequential Write ptr 2-to-1
circuits
MUX
R 11-bit Up
FSMD
design E counter 1
Read ptr S
VHDL
Reset’
Read/ 10
Write’
Enable A 8
1Kx8 Data
CS RAM D in/out
R/W’
3/205
You might also like
- Digital Design: Combinatorial & Sequential CircuitsNo ratings yetDigital Design: Combinatorial & Sequential Circuits206 pages
- Digital Design Gta Esg: - Sequential CircuitNo ratings yetDigital Design Gta Esg: - Sequential Circuit34 pages
- Class Notes - Digital Design - ch03 - Frank VahidNo ratings yetClass Notes - Digital Design - ch03 - Frank Vahid68 pages
- Digital Design: Sequential Logic Design - ControllersNo ratings yetDigital Design: Sequential Logic Design - Controllers58 pages
- S2 Chapter 2 - Sequential Logic V2 Part 1No ratings yetS2 Chapter 2 - Sequential Logic V2 Part 132 pages
- Registers and Counters in Digital DesignNo ratings yetRegisters and Counters in Digital Design47 pages
- Sequential Logic Design: Latches & Flip-FlopsNo ratings yetSequential Logic Design: Latches & Flip-Flops15 pages
- VLSI Sequential Circuit Design OverviewNo ratings yetVLSI Sequential Circuit Design Overview54 pages
- Sequential Circuit Design in Digital LogicNo ratings yetSequential Circuit Design in Digital Logic26 pages
- Latches and Flip-Flops in Digital LogicNo ratings yetLatches and Flip-Flops in Digital Logic39 pages
- Digital Logic Design: Sequential CircuitsNo ratings yetDigital Logic Design: Sequential Circuits64 pages
- BEE 271 Lecture 11 - Sequential Circuits - 2017-05-08No ratings yetBEE 271 Lecture 11 - Sequential Circuits - 2017-05-08102 pages
- CMOS Sequential Circuit Design OverviewNo ratings yetCMOS Sequential Circuit Design Overview38 pages
- VHDL Timer Design for FPGA ImplementationNo ratings yetVHDL Timer Design for FPGA Implementation15 pages
- Digital System Memory Elements OverviewNo ratings yetDigital System Memory Elements Overview91 pages
- Digital Logic Design: Sequential CircuitsNo ratings yetDigital Logic Design: Sequential Circuits37 pages
- Pronoun Reference - Exercise 5: Correction Should Sound Natural and Be LogicalNo ratings yetPronoun Reference - Exercise 5: Correction Should Sound Natural and Be Logical4 pages
- Cobas e 601/602 Assay Calibration SignalsNo ratings yetCobas e 601/602 Assay Calibration Signals5 pages
- JEE Main Nurture Online Test Series Target 2028 Phase 1No ratings yetJEE Main Nurture Online Test Series Target 2028 Phase 16 pages
- Auto Pilot Security System For Railway Gates Using LabviewNo ratings yetAuto Pilot Security System For Railway Gates Using Labview4 pages
- Vedic Mantra and Thirukkural Competition 2024No ratings yetVedic Mantra and Thirukkural Competition 202422 pages
- 101 1033.1 Detroit Diesel Parts CatalogNo ratings yet101 1033.1 Detroit Diesel Parts Catalog1,103 pages
- Biometric Functions in Actuarial MathematicsNo ratings yetBiometric Functions in Actuarial Mathematics10 pages
- Anatomy and Functions of the PericardiumNo ratings yetAnatomy and Functions of the Pericardium10 pages
- M.G. Engineering: Conveyor & Coal SolutionsNo ratings yetM.G. Engineering: Conveyor & Coal Solutions6 pages
- Presentation Tools for Effective SkillsNo ratings yetPresentation Tools for Effective Skills39 pages