CS203: Digital Logic Design
Module 5: Sequential Circuit Design
Neeraj Goel
IIT Ropar
M5.07
Interacting state machines
Digital Logic Design:Sequential system
design.
Designing complex sequential systems
• Partitioning into sub-systems
• Define clear interface
• Sub-systems
– Multiple state machines
– Segregating data-path and control path
– Design control path using state machines
Digital Logic Design:Sequential system
design.
Example
• Single input, single output
• Output is one when pattern “1101” is
matched with in block of 256 bits
• Pattern could be overlapping, but should not
cross block boundaries
Digital Logic Design:Sequential system
design.
Single state machine solution
• Each state should remember which bit of the
block it is!
• Each state should remember previous three
bits
• Total number of states required 256x4 = 1024
Digital Logic Design:Sequential system
design.
Multiple state machines
• State machine M1
– That remembers the number of bits received. If
number of bits is 256th it sends signal to M2
• State machine M2
– Remembers the pattern of bits
Digital Logic Design:Sequential system
design.
State machine - interactions
M1 (bits F M2 (pattern Z
counter) match)
Y
Clock
Digital Logic Design:Sequential system
design.
State machine design
M2 state machine, with Y as input, and Z output
S0 0/0
-/1
S0 -/0
1/0
S255 0/0
S1
S1
-/0
-/0 0/0
1/0
1/1
S2
S2
1/0
Si
-/0 0/0
M1 state machine, f output, no input S3
Digital Logic Design:Sequential system
design.
State machine design
M2 state machine, with Y and F as input, and Z output
1x, x0/0
S0
If F is ‘1’, next state will be S0, x0, 1x/0
irrespective of previous state and value of Y 01/0
If F is ‘1’, present state is S3, if Y is 1, S1 1x/0
Output Z = 1 11/1
01/0
01/1 x0/0
If F is ‘0’, state machine will work like S2
State machine without F 01/0
00/0
S3
Digital Logic Design:Sequential system
design.
Summary
• Design procedure
1. Define sub-module
2. Identify the interfaces (I/O)
3. Design the sub-module individually (without
considering the interface)
4. Re-iterate the design of sub-module considering
the interface
Digital Logic Design:Sequential system
design.
M5.08 RTL Design
Digital Logic Design:Sequential system
design.
Register transfer Level (RTL) Design
• Inputs is read from register and output get
written to registers
– Directly or indirectly
– Chaining of operation is permissible
• Operations performed
– Arithmetic, logical, memory read/write
– Example
• R1 <= R1 + 1
• Registers are global clock driven
Digital Logic Design:Sequential system
design.
Typical implementation RTL Design
Output Registers
Input Registers
Input
Output
Combinational circuit
Clock
Next
State Registers
Data path + State
Control path
Current state
Digital System Design 13
Implication of RTL Specification
• Operations performed in each clock cycle is
clear
– How many clock cycles required
– How many hardware resources required
– What is worst case latency
• Separation of data-path and control path
Digital Logic Design:Sequential system
design.
Clock period discussion
1. Find the worst case critical path -> decide the
clock period
a) One operation may slow entire circuit
b) Overall execution time will be large
2. Decide the clock period -> design the data path
accordingly
a) Put a constraint on design
b) Slow operations are converted into multi-cycle
operations
c) Clock period is decided by fastest operation
Digital Logic Design:Sequential system
design.
RTL modelling in Verilog
• Combinational logic
– Use data-flow statement
assign s = a + b;
• Use of always block for sequential statement
always @(posedge clock) begin
RA <= RB + RC
end
– Blocking as well as non-blocking statements are
permissible
Digital Logic Design:Sequential system
design.
Example problem statement
• The hardware intends to calculate GCD of two
numbers X and Y, both 16 bit wide.
• The computation starts when “start” signal
arrives.
• When computation is done output Z is written
and “eoc” is asserted
Digital System Design 17
GCD Input/Output
X Z
Y GCD Hardware
EOC
Start
Clock
Digital System Design 18
GCD Algorithm
Begin
S: wait till (start == 1)
Input x,y; eoc = 0;
While (x != Y) {
if(x > y) then x = x – y;
else y = y – x;
}
z = x; eoc = 1; goto S;
end
Digital System Design 19
Steps to be followed
1. Identify resources required (registers and
function units)
2. Design the datapath associated control and
status signals
3. Identify control flow requirement to
complete control data interface
4. State diagram and synthesis of state diagram
Digital System Design 20
1. Resource required
• 3 registers to store x, y and z
• One comparator
• One subtractor
• Multiplexers
Digital System Design 21
2. Data path
Digital System Design 22
3. Control signals
SelR1
SelR2
LoadR1
LoadR2
SelOp1
SelOp2
EQ
GT
LoadR3
clearEOC
presetEOC
Digital System Design 23
4. State diagram
Initial state
Start’ S0 S1 Reading variable
Eq
S6 S2
Eq’
S3
Gt’
Gt
S4 S5
Digital System Design 24
4. State diagram
State Operations Control
S0 Reset all
S1 Copy X to R1 LoadR1, LoadR2, SelR1,
Copy Y to R2 SelR2
Assign eoc =0
S2 Compare R1 and R2
S3 Compare R1 and R2
S4 R2 = R2 – R1 Selop1=R2, selop2=R1
S5 R1 = R1 – R2 SelOp1=R1, Selop2=R2
S6 R3 = R1 PresetEOC
Digital System Design 25
Summary
Digital Logic Design:Sequential system
design.