Datapath Sequential Logic - Counter

1
 An FSM is a state register and two functions

Output output
Next Logic o
next state
State D Q
input s s
Logic
i
clk
State
Register

2
 A Simple Counter

Suppose you want to build an FSM with the following state diagram

r' r' r' r'

0 1 2 3 31
r r r r

rst count
n

3
 r' r' r' r'
0 1 2 3 31
r r r r

module Counter1(clk,rst,out) ;
input rst, clk ; // reset and clock
output [4:0] out ;
State Next State reg [4:0] next ;
~rst rst DFF #(5) count(clk, next, out) ;
0 1 0
1 2 0 always@(rst, out) begin
casex({rst,out})
2 3 0 6'b1xxxxx: next = 0 ;
. 6'd0: next = 1 ;
6'd1: next = 2 ;
. 6'd2: next = 3 ;
. 6'd3: next = 4 ;
6'd4: next = 5 ;
6'd5: next = 6 ;
30 31 0 6'd6: next = 7 ;
31 0 0 …
6'd30: next = 31 ;
6'd31: next = 0 ;
default: next = 0 ;
endcase
end
endmodule
 Datapath Implementation

r' r' r' r'

0 1 2 3 31
r r r r

State Next State • You can describe the next-state function

~rst rst with a table.
0 1 0 • However, it can more compactly be
1 2 0 described by an expression:
2 3 0 next = r ? 0 : state + 1 ;
.
. • This “counter” is an example of a
. sequential “datapath” – a sequential
circuit where the next state function is
30 31 0 generated by an expression rather than a
31 0 0 table.
 Verilog description

r' r' r' r'

0 1 2 3 31
r r r r

module Counter(clk, rst, count) ;

parameter n=5 ;
input rst, clk ; // reset and clock
output [n-1:0] count ;

wire [n-1:0] next = rst? 0 : count + 1 ;

DFF #(n) count(clk, next, count) ;

endmodule

6
 Make Table Symbolic

State Next State State Next State

~rst rst ~rst rst
0 1 0 a a+1 0
1 2 0
2 3 0
.
.
.

30 31 0
31 0 0

7
Alternate description (symbolic table)
module Counter1(clk,rst,out) ; module Counter1(clk,rst,out) ;
input rst, clk ; // reset and clock input rst, clk ; // reset and clock
output [4:0] out ; output [4:0] out ;
reg [4:0] next ; reg [4:0] next ;

DFF #(5) count(clk, next, out) ; DFF #(5) count(clk, next, out) ;

always@(rst, out) begin always@(rst, out) begin

casex({rst,out}) case(rst)
6'b1xxxxx: next = 0 ; 1'b1: next = 0 ;
6'd0: next = 1 ; 1'b0: next = out+1 ;
6'd1: next = 2 ; endcase
6'd2: next = 3 ; end
6'd3: next = 4 ; endmodule
6'd4: next = 5 ;
6'd5: next = 6 ;
6'd6: next = 7 ;
…
6'd30: next = 31 ;
6'd31: next = 0 ;
default: next = 0 ;
endcase
end
endmodule
 Schematic

A simple counter
next_state = rst ? 0 : state + 1

0
1
n next count
Mux2 D Q
n n
+1 0
n

clk
rst
9
 Sequential Datapath

Output output
Next Logic o
next state
State D Q
input s s
Logic
i
clk
State
Register

10
Datapath Sequential Logic
- UDL counter and timer

11
 An Up/Down/Load (UDL) Counter

A counter that can:

• count up (increment)
• count down (decrement)
• be loaded with a value
Up, down, and load guaranteed to be one-hot. rst overrides.

if rst, next_state = 0 in count

n n
if (!rst & up) next_state = state+1
rst
if (!rst & down) next_state = state-1 up
if (!rst & load) next_state = in down
load
else next_state = state
12
Table version

State Next State

rst up down load
0 0 1 31 in
1 0 2 0 in
2 0 3 1 in
.
.
.

30 0 31 29 in
31 0 0 30 in

13
Symbolic Table version

State Next State

rst up down load else
q 0 q+1 q-1 in q

State In Rst Up Down Load Next

q x 1 x x x 0
q x 0 1 0 0 q+1
q x 0 0 1 0 q-1
x y 0 0 0 1 y
q x 0 0 0 0 q

14
 Schematic of UDL Counter

3
n
in next count
2 D Q
n Mux4 n n
^
+/-1 1
n
0
0 clk
n
4
rst
up
down C
L
load
module UDL_Count1(clk, rst, up, down, load, in, out) ;
parameter n = 4 ;
input clk, rst, up, down, load ;
input [n-1:0] in ;
output [n-1:0] out ;
wire [n-1:0] out ;
reg [n-1:0] next ;

DFF #(n) count(clk, next, out) ;

always@(rst, up, down, load, out) begin

casex({rst, up, down, load})
4'b1xxx: next = {n{1'b0}} ;
4'b0100: next = out + 1'b1 ;
4'b0010: next = out - 1'b1 ;
4'b0001: next = in ;
4'b0000: next = out ;
default: next = {n{1’bx}} ;
endcase
end
endmodule
module UDL_Count1(clk, rst, up, down, load, in, out) ;
parameter n = 4 ;
input clk, rst, up, down, load ;
input [n-1:0] in ;
output [n-1:0] out ;
wire [n-1:0] out, outpm1 ;
reg [n-1:0] next ;

DFF #(n) count(clk, next, out) ;

assign outpm1 = out + {{n-1{down}},1'b1} ; // down ? -1 : 1

always@(rst, up, down, load, in, out, outpm1) begin

casex({rst, up, down, load})
4'b1xxx: next = {n{1'b0}} ;
4'b01xx: next = outpm1 ;
4'b001x: next = outpm1 ;
4'b0001: next = in ;
default: next = out ;
endcase
end
end
endmodule
Timer module

load – loads count

done – asserted when count = 0
count decrements unless load or done is true

Mux3
-1 2
n
in next count done
1 D Q =0
n n n
0
0
n
rst clk
load Select
Logic

18
module Timer(clk, rst, load, in, done) ;
parameter n=4 ;
input clk, rst, load ;
input [n-1:0] in ;
output done ;
reg [n-1:0] next_count ;
wire [n-1:0] count ;

DFF #(n) cnt(clk, next_count, count) ;

always@(rst, load, in, out) begin

casex({rst, load, done})
3'b1xx: next_count = 0 ; // reset
3'b001: next_count = 0 ; // done
3'b01x: next_count = in ; // load
default: next_count = count-1'b1; // count down
endcase
end

assign done = (count == 0) ;

endmodule
 Example: Increment/decrement-by-3 counter

Write a Verilog module for an arbitrary-width counter that after being reset,
increment by 3 each clock if an inc input is asserted, decrement by 3 if a
dec input is asserted, and hold its value otherwise.
module IncDecBy3(clk, rst, inc, dec, out) ;
...

DFF #(n) sr(clk, next, out) ;

wire [n-1: 0] outpm3 = ___________________________ ;

always @(*) begin

casex({rst, inc, dec})
3'b1xx: next = 0 ; // reset
3'b010: next = outpm3 ;
3'b001: next = outpm3 ;
default: next = out ;
endcase
end
endmodule
20
 Summary

• Datapath state machines

– Next state function specified by an expression, not a table
next = rst ? 0 : (inc ? next + 1 : next) ;
– Common “idioms” for datapath FSM
• Counters where next state is derived by incrementing or decrementing the
current state;
• Shift registers where the current state is shifted to produce next state.
• Datapath and control partitioning
– Divide state space into control (deposit, serve, change) and data
– FSM determines control state
– Datapath computes amount
• Status and control signals
– Special case of factoring

21
Datapath Sequential Logic - Shift register

22
 Shift Register

next = rst ? 0 : {state[n-2:0], sin} ;

0
1
n next state
Mux2 D Q
n n
sin shl 0
n

clk
rst
23
module Shift_Register1(clk, rst, sin, out) ;
parameter n = 4 ;
input clk, rst, sin ;
output [n-1:0] out ;

wire [n-1:0] next = rst ? {n{1'b0}} : {out[n-2:0],sin} ;

DFF #(n) cnt(clk, next, out) ;

endmodule

24
Left/Right/Load Shift Register

25
module LRL_Shift_Register1(clk, rst, left, right, load, sin, in, out) ;
parameter n = 4 ;
input clk, rst, left, right, load, sin ;
input [n-1:0] in ;
output [n-1:0] out ;
reg [n-1:0] next ;

DFF #(n) cnt(clk, next, out) ;

always @(*) begin

casex({rst,left,right,load})
4'b1xxx: next = 0 ; // reset
4'b01xx: next = {out[n-2:0],sin} ; // left
4'b001x: next = {sin,out[n-1:1]} ; // right
4'b0001: next = in ; // load
default: next = out ; // hold
endcase
end
endmodule
26
 Summary

• Datapath state machines

– Next state function specified by an expression, not a table
next = rst ? 0 : (inc ? next + 1 : next) ;
– Common “idioms” for datapath FSM
• Counters where next state is derived by incrementing or decrementing the
current state;
• Shift registers where the current state is shifted to produce next state.
• Datapath and control partitioning
– Divide state space into control (deposit, serve, change) and data
– FSM determines control state
– Datapath computes amount
• Status and control signals
– Special case of factoring

27