Bài giảng Digital Electronics - Bài 3 - Pham Ngoc Nam
FIFO queue Previous implementation indicates empty/full but does not distinguish between both Solution: assume queue depth equals 2n read and write pointer are hence n-bit up-counters select however an (n+1)-bit up-counter: n-LSB of read and write equal: empty/full MSB equal: empty 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?
Bạn đang xem trước 20 trang tài liệu Bài giảng Digital Electronics - Bài 3 - Pham Ngoc Nam, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
’
Y
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
Danger for Glitch!
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
CE
Q 1
Q 0
Q 1n
Q 0n
D 1
Q 1
Q’
D 0
Q 0
Q’
Y
71
State-based model
D
Clk
Q
S*=F(S,I)
Next
State
Combi-
nato-
rial
Logic
O=H(S)
Output
Combi-
nato-
rial
Logic
D
Clk
Q
D
Clk
Q
Clock
Next State S*
Current
State S
Outputs O
Inputs I
72
Input-based model
D
Clk
Q
S*=F(S,I)
Next
State
Combi-
nato-
rial
Logic
O=H(S, I )
Output
Combi-
nato-
rial
Logic
D
Clk
Q
D
Clk
Q
Clock
Next State S*
Current
State S
Outputs O
Inputs I
73
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
74
Step 1: construction of the FSM
The first step in the design of synchronous sequential circuits is the construction of the FSM starting from the description in natural language (ambiguous and incomplete)
Example: Modulo-3 up/down counter
Count enable (C):
C=1: count
C=0: do not count
Direction (D):
D=1: count down
D=0: count up
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
75
Step 1: construction of the FSM
First step: is this a State-based or an Input-based design?
It is Input-based, since the output depends on the state and the input
Second step: construct the FSM starting from the first state, for each combination of inputs from each state
See next slide
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!
76
Step 1: construction of the FSM
u 0
CD=0X
Y=0
CD=0X
Y=0
CD=0X
Y=0
u 2
CD=10
Y=0
CD=0X
Y=0
CD=10
Y= 1
CD=0X
Y=0
CD=0X
Y=0
CD=11
Y=0
CD=11
Y= 1
d 2
CD=11
Y= 1
CD=10
Y= 1
CD=11
Y=0
d 0
CD=11
Y=0
u 1
CD=10
Y=0
CD=10
Y=0
d 1
CD=11
Y=0
CD=10
Y=0
77
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
78
Step 2: minimise the number of states
Goal: less states means less flip-flops
Principal: equivalent behavior of two FSMs
Two FSMs are equivalent when they produce the same output sequence for the same input sequence
79
Step 2: minimise the number of states
Two states in an FSM may be replaced by 1 state when both states produce the same outputs for the same inputs and when both jump to equivalent next states for the same inputs
Formally: states s j and s k are equivalent (s j s k ) if and only if
i I: h(s j ,i)=h(s k ,i): both states produce the same output for each combination of inputs
and
i I: f(s j ,i) f(s k ,i): the next states are equivalent for each input combination
80
Step 2: minimise the number of states
In practice: build the next state table out of the state diagram first
81
Step 2: minimise the number of states
Construct the implication table: 1 square per combination of 2 states
u 1
u 2
d 0
d 1
d 2
u 0
u 1
u 2
d 0
d 1
82
Step 2: minimise the number of states
Delete all combinations that have different outputs for the same inputs
u 1
u 2
d 0
d 1
d 2
u 0
u 1
u 2
d 0
d 1
83
Step 2: minimise the number of states
Indicate for the remaining which next states have to be equivalent to make the current states equivalent
u 1
u 2
d 0
d 1
d 2
u 0
u 1
u 2
d 0
d 1
OK
OK
OK
OK
OK
OK
Minimum number
of states: 3 ie.
{u 0 ,d 0 }=s 0
{u 1 ,d 1 }=s 1
{u 2 ,d 2 }=s 2
84
Step 2: minimise the number of states
Construct the new next state table
Minimum number
of states: 3 ie.
{u 0 ,d 0 }=s 0
{u 1 ,d 1 }=s 1
{u 2 ,d 2 }=s 2
85
Step 2: minimise the number of states
FYI: draw new state diagram
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=10
Y=1
CD=11
Y=1
This could have been constructed from the begin
-ning, but better 1 state too much than too little
86
Step 2: minimise the number of states
This example did not show how you should manipulate the implication table
Hence an imaginary example showing all problems:
87
Step 2: minimise the number of states
Construct the implication table: 1 square per combination of 2 states
s 1
s 2
s 3
s 4
s 5
s 0
s 1
s 2
s 3
s 4
88
Step 2: minimise the number of states
Delete all combinations with different outputs for same inputs
s 1
s 2
s 3
s 4
s 5
s 0
s 1
s 2
s 3
s 4
89
Step 2: minimise the number of states
Indicate for the remaining which next states have to be equivalent to make the current states equivalent
s 1
s 2
s 3
s 4
s 5
s 0
s 1
s 2
s 3
s 4
1-4
1-3
1-4
1-3
OK
1-4
1-3
0-2
OK
1-4
1-3
4-5
2-4
0-2
OK
1-4
1-3
4-5
2-4
0-2
0-2
1-4
OK
1-4
1-3
4-5
2-4
4-5
2-4
0-2
0-2
1-4
OK
1-4
1-3
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2
0-2
1-4
OK
90
1-4
1-3
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2
0-2
1-4
OK
Step 2: minimise the number of states
Delete those states that are equivalent when non-equivalent next states would have been equivalent
s 1
s 2
s 3
s 4
s 5
s 0
s 1
s 2
s 3
s 4
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2
0-2
1-4
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2
1-4
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2
1-4
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
91
Step 2: minimise the number of states
Delete again as long as states are deleted during an iteration
s 1
s 2
s 3
s 4
s 5
s 0
s 1
s 2
s 3
s 4
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
1-4: ?
1-3:OK
4-5
2-4
4-5
2-4
0-2, 4-5
1-2
0-2: ?
0-2: ?
1-4: ?
OK
Minimum number
of states: 3 ie.
{s 0 ,s 2 }=u 0
{s 1 ,s 3 ,s 4 }=u 1
{s 5 }=u 2
92
Step 2: minimise the number of states
Construct the new next state table
Minimum number
of states: 3 ie.
{s 0 ,s 2 }=u 0
{s 1 ,s 3 ,s 4 }=u 1
{s 5 }=u 2
93
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
94
Step 3: State encoding
n states require at least log 2 n flip-flops.
There are n! possible encodings ( n choices for the first state, n -1 for the second, etc.)
95
Step 3: State encoding
Does the chosen encoding matters?
Yes. Each choice leads to a different combinatorial circuit with different cost and delay.
Often chosen encodings:
Straightforward
Minimum-bit-change
One-hot
96
Step 3: State encoding: Straightforward
Straightforward encoding uses the binary representation of the state number as code (s 0 000, s 5 101, )
Straightforward encoding is mostly used when the state number has a physical meaning
E.g. a counter whose count value is sent to a display
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)
97
Step 3: State encoding: Straightforward
98
Step 3: State encoding: Minimum-bit-change
For minimum-bit-change encoding we assign the codes such that the total number of bit-changes for all state transitions is minimal
Minimum-bit-change encoding is mostly used when area and power need to be minimized (CMOS)
00
01
10
11
1
1
2
2
00
01
11
10
1
1
1
1
Straightforward
Minimum-bit-change
Gray code
counter
99
Step 3: State encoding: Minimum-bit-change
0
1
2
All transitions are equally likely
Preferrably only 1 bit difference between each pair of transitions
This can only be realised between two of the three pairs
Possible
encoding:
s 0 =00
s 1 =10
s 2 =11
100
Step 3: State encoding: One-hot
Each state has 1 flip-flop, hence no encoding; Q of 1 FF =1, Q of others=0
Flip-flop cost = O(n) i.o. O(log n ), hence only useful for small number of states: controller
Very easy to realise: short design time (time-to-market, e.g. exam)
Very small combinatorial circuits to drive the inputs of the flip-flops: cheap combinatorial 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)
101
Step 3: State encoding: One-hot
One-hot encoding
s 0 =001
s 1 =010
s 2 =100
102
Step 3: State encoding: One-hot
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
C
D
Y
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
Q 0
D
Q 1
D
Q 2
D
P
C
C
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
103
Step 3: State encoding: One-hot
Implementation rule for One-hot with D flip-flop:
Each arriving transition at a state needs an AND gate
104
Step 3: State encoding: One-hot
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
Q 0
S
R
Q 1
S
R
Q 2
S
R
C
D
Y
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
P
C
C
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
CD=10
Y=1
s 0
CD=0X
Y=0
s 1
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
s 2
CD=10
Y=0
CD=11
Y=0
CD=0X
Y=0
CD=11
Y=1
105
Step 3: State encoding: One-hot
Implementation rule for One-hot with SR flip-flop:
Each arriving transition starting at another state requires an AND gate at the S input
Each departing transition to another state requires an AND gate at the R input
106
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
107
Step 4: Choice of the flip-flop type
JK flip-flop
Most expensive flip-flop
Most difficult design
Largest number of don’t cares: probably cheapest (and fastest) combinatorial control logic
Used when a different signal sets resp. resets the flip-flop
SR flip-flop
Cheap flip-flop
Difficult design
Many don’t cares: probably cheap (and fast) control logic
Used when a different signal sets resp. resets the flip-flop
108
Step 4: Choice of the flip-flop type
D flip-flop
Cheap flip-flop
Most easy design
No don’t cares: probably most expensive (and slowest) combinatorial control logic
Used when the same signal sets resp. resets the flip-flop, i.e. when the value of a signal has to be remembered temporarily
T flip-flop
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
109
Step 4: Choice of the flip-flop type
No fixed selection rule exists
When we want the cheapest circuit, all variants have to be tried out
When the fastest design time is needed, D flip-flops are the best choice
FPGAs only possess D flip-flops
110
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
111
Step 5: Realization of the combinatorial logic: D flip-flop
Determine the excitation functions
Excitation table
for D flip-flop
D to be applied
is identical to Q n
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
0
0
x
1
0
0
x
1
Q 1n =D 1
Q 0
Q 1
1
0
x
0
0
1
x
0
C
D
0
1
x
0
0
1
x
0
Q 0n =D 0
Q 0
Q 1
0
0
x
1
1
0
x
0
C
D
112
Step 5: Realization of the combinatorial logic: D flip-flop
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
0
0
x
1
0
0
x
1
Q 1n =D 1
Q 0
Q 1
1
0
x
0
0
1
x
0
C
D
0
1
x
0
0
1
x
0
Q 0n =D 0
Q 0
Q 1
0
0
x
1
1
0
x
0
C
D
Q 1
D
Q 0
D
C
D
Y
Cost: 35
1.5 CLB
Clr
Clr
113
Step 5: Realization of the combinatorial logic: T flip-flop
Determine the excitation functions
Excitation table
for T flip-flop
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
0
0
x
0
0
0
x
0
T 1
Q 0
Q 1
1
0
x
1
0
1
x
1
C
D
0
0
x
0
0
0
x
0
T 0
Q 0
Q 1
0
1
x
1
1
1
x
0
C
D
114
0
0
x
0
0
0
x
0
T 0
Q 0
Q 1
0
1
x
1
1
1
x
0
C
D
0
0
x
0
0
0
x
0
T 1
Q 0
Q 1
1
0
x
1
0
1
x
1
C
D
Step 5: Realization of the combinatorial logic: T flip-flop
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
Q 1
T
Q 0
T
C
D
Y
Cost: 32
Clr
Clr
115
Step 5: Realization of the combinatorial logic: SR flip-flop
Determine the excitation functions
Excitation table
for SR flip-flop
S 1
Q 0
Q 1
C
D
R 1
Q 0
Q 1
C
D
0
0
x
x
0
0
0
0
x
x
x
x
0
0
x
0
0
x
x
x
0
x
x
0
0
0
x
0
0
x
0
x
x
0
x
x
0
x
0
0
x
0
0
x
0
1
x
x
0
x
x
0
x
0
0
0
x
0
0
x
0
1
0
x
x
0
x
x
0
x
0
1
0
0
x
0
0
x
1
0
0
0
1
0
x
x
0
x
x
0
0
x
1
x
0
1
0
0
x
x
0
0
x
x
1
0
x
0
0
1
x
0
x
x
x
0
x
x
x
0
0
x
x
1
x
0
x
1
116
Step 5: Realization of the combinatorial logic: SR flip-flop
Determine the excitation functions
Excitation table
for SR flip-flop
S 0
Q 0
Q 1
C
D
R 0
Q 0
Q 1
C
D
0
x
0
0
x
0
x
0
x
x
0
x
0
x
0
0
x
0
1
0
0
x
0
x
x
0
x
0
1
x
0
x
0
0
x
0
0
0
1
1
0
0
x
0
x
x
0
x
x
1
0
0
1
x
0
x
x
0
0
x
x
0
0
0
x
1
1
0
x
0
x
0
x
x
x
0
x
x
x
1
x
0
0
1
x
x
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
117
Step 5: Realization of the combinatorial logic: SR flip-flop
S 1
Q 0
Q 1
C
D
R 1
Q 0
Q 1
C
D
0
0
x
x
0
0
x
x
1
0
x
0
0
1
x
0
x
x
x
0
x
x
x
0
0
x
x
1
x
0
x
1
Q 1
S
R
Q 0
S
R
C
D
C
C
118
Step 5: Realization of the combinatorial logic: SR flip-flop
S 0
Q 0
Q 1
C
D
R 0
Q 0
Q 1
C
D
Q 1
S
R
Q 0
S
R
C
D
C
C
0
x
x
0
0
x
x
0
0
0
x
1
1
0
x
0
x
0
x
x
x
0
x
x
x
1
x
0
0
1
x
x
119
Step 5: Realization of the combinatorial logic: SR flip-flop
S 0
Q 0
Q 1
C
D
R 0
Q 0
Q 1
C
D
Q 1
S
R
Q 0
S
R
C
D
C
C
0
x
x
0
0
x
x
0
0
0
x
1
1
0
x
0
x
0
x
x
x
0
x
x
x
1
x
0
0
1
x
x
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
Y
Cost: 32
120
Step 5: Realization of the combinatorial logic: JK flip-flop
Determine the excitation functions
Excitation table
for JK flip-flop
J 1
Q 0
Q 1
C
D
K 1
Q 0
Q 1
C
D
0
0
x
x
0
0
0
0
x
x
x
x
0
0
x
0
0
x
x
x
0
x
x
0
0
0
x
0
0
x
0
1
x
x
x
0
x
x
0
x
x
1
0
0
x
0
0
x
1
0
x
0
1
x
x
x
0
x
x
0
x
x
1
x
x
1
0
0
x
x
0
0
x
x
1
0
x
x
0
1
x
x
x
x
x
0
x
x
x
0
x
x
x
1
x
x
x
1
121
Step 5: Realization of the combinatorial logic: JK flip-flop
Determine the excitation functions
Excitation table
for JK flip-flop
J 0
Q 0
Q 1
C
D
K 0
Q 0
Q 1
C
D
0
x
0
0
x
0
x
0
x
x
0
x
0
x
0
0
x
0
1
x
0
x
0
x
x
0
x
x
1
x
0
x
0
0
x
0
0
x
1
1
x
0
x
0
x
x
0
x
x
1
x
x
1
x
0
x
x
0
0
x
x
0
0
x
x
1
1
x
x
0
x
0
x
x
x
0
x
x
x
1
x
x
x
1
x
x
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
122
Step 5: Realization of the combinatorial logic: JK flip-flop
J 1
Q 0
Q 1
C
D
K 1
Q 0
Q 1
C
D
Q 1
J
K
Q 0
J
K
C
D
C
C
0
0
x
x
0
0
x
x
1
0
x
x
0
1
x
x
x
x
x
0
x
x
x
0
x
x
x
1
x
x
x
1
123
Step 5: Realization of the combinatorial logic: JK flip-flop
J 0
Q 0
Q 1
C
D
K 0
Q 0
Q 1
C
D
Q 1
J
K
Q 0
J
K
C
D
C
C
0
x
x
0
0
x
x
0
0
x
x
1
1
x
x
0
x
0
x
x
x
0
x
x
x
1
x
x
x
1
x
x
0
0
x
0
0
0
x
0
Y
Q 0
Q 1
1
0
x
0
0
0
x
1
C
D
Y
Cost: 26
124
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Finite State Machine (FSM)
State-based or Moore-type FSM
Input-based or Mealy-type FSM
Step 1: State diagram
Step 2: State minimization
Step 3: State encoding
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
125
Step 6: Timing analysis
Determine maximum clock frequency
Max. clock frequency = 1/(delay of critical path)
Critical path is the path with the longest combinatorial delay between two clock edges
Example:
Q 1
D
Q 0
D
C
D
Y
Clr
Clr
Q 1
D
Q 0
D
C
D
Y
Clr
Clr
126
Step 6: Timing analysis
Delay of critical path (assume zero connection delay):
clock Q 0 + invertor + 4-input AND + 3-input OR + setup Dclock
= 5.2 + 1.0 + (2.2+1.0) + (1.8+1.0) + 1.0 = 13.2 ns (assuming that our relative times can be considered to be nanoseconds)
f max = 76 MHz (same assumption)
Q 1
D
Q 0
D
C
D
Y
Clr
Clr
127
Step 6: Timing analysis
After designing the combinatorial circuits for next state and output, all traditional design steps follow:
Technology mapping
Placement and routing
Timing simulation
Timing simulation is even more important for sequential circuits than for combinatorial 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
128
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
129
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Definitions and Fundamental Mode Restriction
Design
Basic RTL building blocks
130
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Definitions and Fundamental Mode Restriction
Design
Basic RTL building blocks
131
Asynchronous Sequential Circuits
Definitions:
Sequential circuit: the output is function of the current value of the inputs and of the current state (i.e. also function of the sequence of past inputs)
Asynchronous sequential circuits: outputs and state change as soon as an input changes
Fundamental mode restriction:
only one input may change at a time; the next input change may only occur when all effects to the 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
132
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Definitions and Fundamental Mode Restriction
Design
Basic RTL building blocks
133
Example circuit: requirements
Design a circuit with two inputs (I and E) and one output Q.
If E is high, a rising edge on I causes Q to go high.
Q stays high until E goes low.
While E is low, Q is low.
134
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
135
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
136
State table
List all states: each possible combination of inputs and outputs is a state
137
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
138
State transition diagram
a/0
00
e/0
01
IE
f/0
11
b/0
01
d/0
11
c/0
10
11
01
01
00
11
10
10
10
00
01
11
00
We opted for a
Moore or state
based design; we
could as well have
chosen a Mealy
approach, with
output per
transition
139
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
140
Primitive flow table
141
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
142
Minimized flow table
Rule: merge compatible states: states with same next states and outputs or don’t cares
‘Compatibility’ is not associative! (a compatible b) AND (a compatible c) does NOT induce (b compatible c)
Note that minimizing the number of states of synchronous circuits requires equivalence instead of compatibility .
States with same outputs and equivalent next states
‘Equivalence’ is associative!
143
Minimized flow table
Are a and b compatible?
YES, hence merge them
144
Minimized flow table
Are c and d compatible?
YES, hence merge them
145
Minimized flow table
Are e and f compatible?
YES, hence merge them
This minimized flow table
is called the
Transition Table
146
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
147
State assignment
Assume we make following
straightforward
state assignment:
a : 00
b : 01
g : 11
148
State assignment
0
0
0
x
0
0
1
x
E
S 0n
S 0
S 1
1
1
1
x
1
1
1
x
I
0
0
0
x
0
0
1
x
E
S 1n
S 0
S 1
1
0
1
x
0
0
0
x
I
0
0
x
1
S 0
S 1
149
State assignment
0
0
0
x
0
0
1
x
E
S 0n
S 0
S 1
1
1
1
x
1
1
1
x
I
0
0
0
x
0
0
1
x
E
S 1n
S 0
S 1
1
0
1
x
0
0
0
x
I
0
0
x
1
S 0
S 1
I E S 1 S 0
Q
150
State assignment
I E S 1 S 0
Q
Let’s animate behav from state S=00 with inputs IE=01->11
Step 1: Stable state S=00 with inputs IE=01
Step 2: Inputs change to IE=11
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
Step 3: after 2-input gate delay, OR-gate switches,
making S 0 =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,
it’s called a CRITICAL RACE
151
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
152
Elimination of critical races
Solution: make the state assignment such that never 2 or more state variables need to change following a single input change
a
b
g
No encoding can be found satisfying the above rule!
00
01
11
153
Elimination of critical races
Do the state assignment as good as you can. Use additional states to solve the problems that remain
Highlight remaining problems
Route these transitions via an additional state, which
differs in only one state variable
Don’t care because both
new transitions require
an output change: it
is not important whether
this already happens in
the intermediate state
154
Elimination of critical races
0
0
0
0
0
0
1
x
E
S 0n
S 0
S 1
0
1
1
1
1
1
1
x
I
0
0
1
0
0
0
1
x
E
S 1n
S 0
S 1
1
0
1
1
0
0
0
x
I
0
0
x
1
S 0
S 1
155
Elimination of critical races
0
0
0
0
0
0
1
x
E
S 0n
S 0
S 1
0
1
1
1
1
1
1
x
I
0
0
1
0
0
0
1
x
E
S 1n
S 0
S 1
1
0
1
1
0
0
0
x
I
0
0
x
1
S 0
S 1
I E S 1 S 0
Q
156
Elimination of critical races
What happens at power-up?
The circuit could as well start in state S=10 with an
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
Race, but not critical
157
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
158
Hazard free combinatorial design
The combinatorial circuits of an asynchronous design should be designed in a hazard free way
Static hazard: a status variable that is supposed not to change, briefly changes; this could lead to a wrong final state
Dynamic hazard: a status variable that is supposed to change just once, changes three times; this could lead to a wrong final state
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
159
Design flow
State table
State transition diagram
Primitive flow table
Minimized flow table
State assignment
Elimination of critical races
Hazard free combinatorial design
Avoidance of input skew
160
Avoidance of input skew
Assume that input I is skewed on the bottom AND gate with respect to the other inputs
I E S 1 S 0
Q
Delay
Start in state S=01 with IE=11
I becomes 0: S should go to 00
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
Now the delayed version of I
goes to zero
State however does not change
anymore and ends in the
incorrect S=11
State variables may change only after all input
changes are applied to all gates!
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
I E S 1 S 0
Q
161
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
162
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
163
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
164
Registers
Register
D
Q
D
Q
D
Q
D
Q
Clk
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Register
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Symbol
165
Registers
Asynchronously presettable and clearable Register
D
Q
D
Q
D
Q
D
Q
Clk
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Preset
Clear
Register
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Symbol
Preset
Clear
166
D
Q
D
Q
D
Q
D
Q
Clk
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
1
0
S
Load
1
0
S
1
0
S
1
0
S
Registers
Loadable register (without gated clock)
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 master clock
167
Register
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Symbol
Load
Registers
Loadable register (without gated clock)
168
D
Q
D
Q
D
Q
D
Q
Clk
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Registers
Loadable register ( with gated clock)
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 skew
CE
169
Registers
Loadable register ( with gated clock)
Register
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
Symbol
CE
170
Registers
Clock skew problem for gated clocks:
Not all clocks of all registers change concurrently
Expected behavior:
New I 3..0 applied
At next clock edge: Clk* 1 1, Clk* 2 1 Q* 3..0 A 3..0 , A* 3..0 I 3..0
Real behavior:
New I 3..0 applied
At next clock edge: Clk* 1 1 A* 3..0 I 3..0 , Clk* 2 1 Q* 3..0 A* 3..0
Risk for setup violation
Register 1
I 3
I 2
I 1
I 0
Register 2
Q 3
Q 2
Q 1
Q 0
CE
A 3..0
171
Registers
D 0
Q 0
D 1
Q 1
I
A
Q
Clk
CE
Clk
I
A
CE
Gated
Clk
Q
D 0
Q 0
D 1
Q 1
I
A
Q
Clk
CE
D 0
Q 0
D 1
Q 1
I
A
Q
Clk
CE
D 0
Q 0
D 1
Q 1
I
A
Q
Clk
CE
Possible setup or hold violation for 2nd flip-flop
D 0
Q 0
D 1
Q 1
I
A
Q
Clk
CE
172
Registers
What causes clock skew?
Gated clocks
Different relative routing delay
On PCB and within chip: different wire length
In FPGA: different number of routing switches
Delay depends on many things:
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)
173
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
174
Shift registers
Serial-in/parallel-out shift register (SIPO)
D
Q
D
Q
D
Q
D
Q
Clk
I L
Q 3
Q 2
Q 1
Q 0
1
0
S
SE
1
0
S
1
0
S
1
0
S
Example of utilization:
Receive register (Rx) serial port
Delay line for FIR and IIR filters
175
Shift registers
Serial-in/parallel-out shift register (SIPO)
Shift Register
Q 3
Q 2
Q 1
Q 0
Symbol
SE
I L
176
Shift registers
Parallel-in/serial-out shift register (PISO)
D
Q
D
Q
D
Q
D
Q
Clk
I L
Q 0
1
0
S
Sh/Ld
1
0
S
1
0
S
1
0
S
Example of utilization: Transmit register (Tx) serial port
I 3
I 2
I 1
I 0
CE
177
Shift registers
Parallel-in/serial-out shift register (PISO)
Shift
Register
I 3
I 2
I 1
I 0
Q 0
Symbol
I L
CE
Sh/Ld’
178
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
179
Synchronous counters
Synchronous up-counter
D
Q
D
Q
Clk
Q 1
Q 0
Clear
D
Q
Q 2
Output
carry
HA
HA
HA
E
Synchronous because all flip-flops are clocked by the
same signal
180
Synchronous counters
Clk
Q 1
Q 0
Q 2
Output
carry
D
Q
D
Q
D
Q
HA
HA
HA
E
Clear
Clk
Clear
E
Q 0
Q 1
Q 2
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
Glitch!
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
D
Q
D
Q
D
Q
HA
HA
HA
181
Synchronous counters
Synchronous up/down-counter
D
Q
D
Q
Clk
Q 1
Q 0
Clear
D
Q
Q 2
Output
carry
E
HAS
HAS
HAS
D
C i
C o
Half adder/subtractor
182
Synchronous counters
Design of the Half adder/subtractor
HAS
D
c i
Q i
D i
c o
Behavior:
When c i =0 then D i =Q i (no counting)
When c i =1 this section should toggle
C 0 has to be 1 when the next section
has to toggle. When should this happen?
Up-count
00
0 1
1 0
11
0 0
01
Next section toggles
at 1 0 of this section
Down-count
0 0
1 1
10
0 1
00
11
Next section toggles
at 0 1 of this section
183
Synchronous counters
Design of the Half adder/subtractor
Up-count
00
0 1
1 0
11
0 0
01
Next section
toggles at 1 0
of this section
Down-count
0 0
1 1
10
0 1
00
11
Next section
toggles at 0 1
of this section
Behavior:
When c i =0 then D i =Q i (no counting)
When c i =1 this section should toggle
C 0 has to be 1 when the next section
has to toggle. When should this happen?
Up-count
00
0 1
1 0
11
0 0
01
Next section
toggles at 1 0
of this section
Down-count
0 0
1 1
10
0 1
00
11
Next section
toggles at 0 1
of this section
Behavior:
When c i =0 then D i =Q i (no counting)
When c i =1 this section should toggle
C 0 has to be 1 when the next section
has to toggle. When should this happen?
Up-count
00
0 1
1 0
11
0 0
01
Next section
toggles at 1 0
of this section
Down-count
0 0
1 1
10
0 1
00
11
Next section
toggles at 0 1
of this section
Behavior:
When c i =0 then D i =Q i (no counting)
When c i =1 this section should toggle
C 0 has to be 1 when the next section
has to toggle. When should this happen?
Up-count
00
0 1
1 0
11
0 0
01
Next section
toggles at 1 0
of this section
Down-count
0 0
1 1
10
0 1
00
11
Next section
toggles at 0 1
of this section
Behavior:
When c i =0 then D i =Q i (no counting)
When c i =1 this section should toggle
C 0 has to be 1 when the next section
has to toggle. When should this happen?
184
Synchronous counters
Design of the Half adder/subtractor
0
1
1
0
1
0
0
1
c i
Dir
Q i
D i
0
0
0
0
0
1
0
1
c i
Dir
Q i
c i+1
c i
Dir
Q i
D i
c i+1
185
Synchronous counters
Parallel loadable up/down-counter
Clk
Q 1
Clear
D
Q
Q 2
Output
carry
E
HAS
HAS
HAS
D
C i
C o
0
1
D
Q
0
1
Q 0
D
Q
0
1
I 2
I 1
I 0
Load
186
Synchronous counters
BCD up-counter
Up-counter
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
E
Load
0 0 0 0
Compares with constant:
When count equals ‘1001’ (i.e. 9), ‘0000’ is loaded at next clock edge
187
Synchronous counters
BCD up/down-counter
Up/down-
counter
I 3
I 2
I 1
I 0
Q 3
Q 2
Q 1
Q 0
E
Load
Mux
0 0 0 0
1 0 0 1
1
0
D
188
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
189
Asynchronous counters
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
Clk
Q 0
Q 1
Q 2
Q 3
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
T
Q
T
Q
T
Q
T
Q
Clk
Q 3
Q 2
Q 1
Q 0
Clear
E
Q’
Q’
Q’
Q’
190
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
191
Register files
D
Q
WE
D in
Clk
RE
D out
Register File Cell (RFC)
This implementation dissipates much power due to the
active memorization of data, but does not suffer from
clock skew problems.
Combining ‘WE’ with ‘Clk’ into a gated clock, we can
reduce the power dissipation
D
Q
D out
WE
D in
Clk
RE
Note that in both cases,
‘writing’ is clocked, but
‘reading’ is not clocked!
Needed for critical-path
computation...
192
Register files
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
RFC
0
1
2
3
0
1
2
3
I 0
I 1
I 2
I 3
O 0
O 1
O 2
O 3
2-to-4
write
dec
2-to-4
read
dec
WA 1
WA 0
WE
RA 1
RA 0
RE
193
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
194
LIFO queue - stack
Top
Top-1
Top-2
Top-3
Top-4
Top-5
Top-6
Top-7
empty
empty
empty
empty
empty
empty
empty
empty
1. Reset
45
empty
empty
empty
empty
empty
empty
empty
2. Push 45
12
45
empty
empty
empty
empty
empty
empty
3. Push 12
4. Push 23
23
12
45
empty
empty
empty
empty
empty
5. Pop -> 23
12
45
empty
empty
empty
empty
empty
empty
6. Push 10
10
12
45
empty
empty
empty
empty
empty
195
LIFO queue - stack
Using left/right’ shift register
Reset
L/R’
Enable
I L
I R
O 0
O 7
and counter for indication
empty/full
196
LIFO queue - stack
Reset
L/R’
Enable
I L
I R
O 0
O 7
Reset
L/R’
Enable
I L
I R
O 0
O 7
Reset
Up/down’
Enable
Q 3..0
0
0
Enable
Reset’
Push/pop’
In 0
In 7
Out 0
Out 7
Empty
Full
197
LIFO queue - stack
Alternative implementation: for large stacks
0
1
2
3
Write Ptr
Read Ptr
empty
empty
23
45
2
1
3. Push 23
Does not shift!
empty
12
23
45
3
2
4. Push 12
2. Push 45
empty
empty
empty
45
1
0
At ‘Push’ both ptrs count up
5. Pop -> 12
empty
empty
23
45
2
1
At ‘Pop’ both ptrs count down
6. Push 17
empty
17
23
45
3
2
1. Reset
empty
empty
empty
empty
0
3
0=empty
7. Push 52
52
17
23
45
0
3
0=full
198
LIFO queue - stack
R
U/D’
E
Up/down
counter
Write ptr
S
U/D’
E
Up/down
counter
Read ptr
2-to-1
MUX
1Kx8
RAM
A
CS
R/W’
D
10
1
0
S
8
Watch timing of the enable: when RAM is not clocked
be careful not to read/write twice since the counters
count further
Reset’
Push/
Pop’
Enable
Full/
empty
Data
in/out
Note:
SET
199
Sequential Circuits
The flip-flop as building block
Design of synchronous sequential circuits
Design of asynchronous sequential circuits
Basic RTL building blocks
Registers
Shift registers
Counters
Synchronous counters
Asynchronous counters
Register files
LIFO queue (push down stack)
FIFO queue
200
FIFO queue
Top
Top-1
Top-2
Top-3
Top-4
Top-5
Top-6
Top-7
empty
empty
empty
empty
empty
empty
empty
empty
1. Reset
45
empty
empty
empty
empty
empty
empty
empty
2. Write 45
23
45
empty
empty
empty
empty
empty
empty
3. Write 23
12
23
45
empty
empty
empty
empty
empty
4. Write 12
12
23
empty
empty
empty
empty
empty
empty
5. Read -> 45
57
12
23
empty
empty
empty
empty
empty
6. Write 57
201
FIFO queue
Reset
Enable
I L
O 0
O 7
Reset
Enable
I L
O 0
O 7
Set
Up/down’
Enable
Q 3..0
Enable
Reset’
Read/
write’
In 0
In 7
Uit 0
Uit 7
Empty
Full
7
0
7
0
S 2..0
S 2..0
Read
pointer
202
FIFO queue
Alternative implementation: for large FIFO’s
0
1
2
3
Write Ptr
Read Ptr
empty
empty
empty
empty
0
0
1. Reset
2. Write 45
empty
empty
empty
45
1
0
Only write pointer incr. at write
empty
empty
23
45
2
0
3. Write 23
Does not shift!
empty
12
23
45
3
0
4. Write 12
empty
12
23
empty
3
1
5. Read -> 45
Only read pointer incr. at read
6. Write 57
57
12
23
empty
0
1
Wrap-around
7. Write 16
57
12
23
16
1
1
Read and write pointer equal: empty or full
203
FIFO queue
Previous implementation indicates empty/full but does not distinguish between both
Solution:
assume queue depth equals 2 n
read and write pointer are hence n-bit up-counters
select however an (n+1)-bit up-counter:
n-LSB of read and write equal: empty/full
MSB equal: empty
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?
204
FIFO queue
R
E
11-bit Up
counter
Write ptr
R
E
11-bit Up
counter
Read ptr
2-to-1
MUX
1Kx8
RAM
A
CS
R/W’
D
10
0
1
S
8
Reset’
Read/
Write’
Enable
Empty
Data
in/out
=?
Full
MSB
10-LSB
205
Các file đính kèm theo tài liệu này:
bai_giang_digital_electronics_bai_3_pham_ngoc_nam.ppt
