CS计算机代考程序代写 CS 2204: Digital Circuits

CS 2204: Digital Circuits

Lecture 17

Finite state machines
We will now discuss a general method to design sequential
circuits from a “specification”

Example: Car speed-limiter

w = 0 if below_limit,
1 if above limit.

Speed limiter

z = 0 no break,
1 apply break.

Apply break if car exceeds
speed-limit for two consecutive
intervals

State transition diagram

Two/
z=0

One/
z=0

Apply_Break/
z=1

START
w=1 w=1 w=1

w=0

w=0

w=0

Next state table after state assignment

Two
One

Apply_Brake

Dont care

Next state as a function of current state/input

Output as a function of current state
NOTE: but NOT input w. When the output is only a function of
the current state, we call it a “moore” machine.

Next-state Output

Final
implementation

Resetn
input
initializ
es FFs to
0,0 state

Timing diagram

Verilog implementation

Another example: Pattern detector
– Single bit input w.
– Output z = 1 if the last 4 bits are 1011, 0 otherwise.

A
z=0

B
z=0

C
z=0

START

w=1 w=0 w=1

w=0

w=1

w=1
w=0

D
z=0

E
z=1

w=0

w=0

w=1

Practice module pattern (Clock, Resetn, w, z);
input Clock, Resetn, w;

output z;
reg [3:1] y, Y;
parameter [3:1] A=3’b000, B=3’b001 ….;

always @(w,y)
case (y)
A: if(w) Y = B;
else Y = A;
B:….
endcase

Always @(negedge Resetn, posedge Clock)
if (Resetn==0) y<=A; else y <= Y; //Define output assign z = (y==E); endmodule State encoding Recall that you can arbitrarily assign states. two one apply_break New State Assignment Why does this help? Recall that you can arbitrarily assign states. two one apply_break New State Assignment Y1 = w; Y2 = w.y1; z = y2; Optimized circuit “One-hot” encoding A “simple” state encoding that uses N bits if there are N states (note, in theory we only need logN bits). Note: all one-hot encodings have the same circuit size! two one apply_break New spec. We will now discuss a general method to design sequential circuits from a “specification” Example: Car speed-limiter w = 0 if below_limit, 1 if above limit. Speed limiter z = 0 no break, 1 apply break. IMMEDIATELY Apply break if car exceeds speed-limit for two consecutive intervals Timing diagram Previously, brake applied after two consecutive w=1 Now, we want brake applied immediately! Moore Vs. Mealy machines Moore Machine: output depends only on the current state We cant use a Moore machine for immediate braking! Mealy Machine: output depends on current state AND input. Each edge has an associated output value! State transition diagram for mealy machine Two One Apply_Break START w=1/z=0 w=1/z=1 w=1/z=1 w=0/z=0 w=0/z=0 w=0/z=0 A further simplification Two One Apply_Break START w=1/z=0 w=1/z=1 w=1/z=1 w=0/z=0 w=0/z=0 w=0/z=0 MERGE THESE TWO STATES! Simplified state transition graph A B START w=1/z=0 w=1/z=1 w=0/z=0 w=0/z=0 Practice Write Verilog for the 1011 pattern detector Module pattern (Clock, Resent, w, z); input Clock, Resent, w; output z; reg [ : ] y, Y; parameter [ : ] A= …. always @(w,y) case (y) …. endcase Always @(negedge Resetn, posedge Clock) if (Resetn==0) y<=A; else y <= Y; //Define output …. endmodule WHAT CHANGES?