CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 1Sequential Logic Implementation Models for representing sequential circuits Abstraction of sequential elements Finite state machines and their state diagrams Inputs/outputs Mealy, Moore, and synchronous Mealy machines Finite state machine design procedure Verilog specification Deriving state diagram Deriving state transition table Determining next state and output functions Implementing combinational logicCS 150 - Fall 2005 – Lec #7: Sequential Implementation – 2react right away to leaving the wallMealy vs. Moore Machines Moore: outputs depend on current state only Mealy: outputs depend on current state and inputs Ant brain is a Moore Machine Output does not react immediately to input change We could have specified a Mealy FSM Outputs have immediate reaction to inputs As inputs change, so does next state, doesn’t commit untilclocking eventAL’ R’ / TR, FL / TLL’ R / TL, FCS 150 - Fall 2005 – Lec #7: Sequential Implementation – 3D/1E/1B/0A/0C/01000011110resetcurrent nextreset input state state output1 – – A0 0 A B 00 1 A C 00 0 B B 00 1 B D 00 0 C E 00 1 C C 00 0 D E 10 1 D C 10 0 E B 10 1 E D 1Specifying Outputs for a Moore Machine Output is only function of state Specify in state bubble in state diagram Example: sequence detector for 01 or 10CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 4current nextreset input state state output1 – – A 00 0 A B 00 1 A C 00 0 B B 00 1 B C 10 0 C B 10 1 C C 0BAC0/10/00/01/11/01/0reset/0Specifying Outputs for a MealyMachine Output is function of state and inputs Specify output on transition arc between states Example: sequence detector for 01 or 10CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 5state feedbackinputsoutputsregCombinationallogicforNext StateLogicforoutputsinputs outputsstate feedbackregCombinational logic for Next StateLogicforoutputsComparison of Mealy and Moore Machines Mealy Machines tend to have less states Different outputs on arcs (n^2) rather than states (n) Moore Machines are safer to use Outputs change at clock edge (always one cycle later) In Mealy machines, input change can cause output change as soon aslogic is done – a big problem when two machines are interconnected –asynchronous feedback Mealy Machines react faster to inputs React in same cycle – don't need to wait for clock In Moore machines, more logic may be necessary to decode stateinto outputs – more gate delays afterCS 150 - Fall 2005 – Lec #7: Sequential Implementation – 6D QQBAclockoutD QQD QQclockoutABMealy and Moore Examples Recognize A,B = 0,1 Mealy or Moore?CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 7D QQD QQD QQD QQABclockoutD QQD QQABclockoutMealy and Moore Examples (cont’d) Recognize A,B = 1,0 then 0,1 Mealy or Moore?CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 8Registered Mealy Machine (Really Moore) Synchronous (or registered) Mealy Machine Registered state AND outputs Avoids ‘glitchy’ outputs Easy to implement in programmable logic Moore Machine with no output decoding Outputs computed on transition to next state rather thanafter entering View outputs as expanded state vectorInputsOutputsCurrent Stateoutputlogicnext statelogicCS 150 - Fall 2005 – Lec #7: Sequential Implementation – 9// State assignmentparameter zero = 0, one1 = 1, two1s = 2;module reduce (out, clk, reset, in); output out; input clk, reset, in; reg out; reg [1:0] state; // state register reg [1:0] next_state;Verilog FSM - Reduce 1s Example Change the first 1 to 0 in each string of 1’s Example Moore machine implementation100011zero[0]one1[0]two1s[1]CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 10 always @(in or state) case (state) zero: begin // last input was a zero out = 0; if (in) next_state = one1; else next_state = zero; end one1: begin // we've seen one 1 out = 0; if (in) next_state = two1s; else next_state = zero; end two1s: begin // we've seen at least 2 ones out = 1; if (in) next_state = two1s; else next_state = zero; end default: begin // in case we reach a bad state out = 0; next_state = zero; endcaseinclude all signals that are input to state and output equationsMoore Verilog FSM (cont’d)100011zero[0]one1[0]two1s[1]CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 11// Implement the state register always @(posedge clk) if (reset) state <= zero; else state <= next_state;endmoduleMoore Verilog FSM (cont’d)100011zero[0]one1[0]two1s[1]CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 127module reduce (clk, reset, in, out); input clk, reset, in; output out; reg out; reg state; // state register reg next_state; parameter zero = 0, one = 1; always @(in or state) case (state) zero: begin // last input was a zero if (in) next_state = one; else next_state = zero; out = 0; end one: // we've seen one 1 if (in) begin next_state = one; out = 1; end else begin next_state = zero; out = 0; end endcase always @(posedge clk) if (reset) state <= zero; else state <= next_state; endmoduleMealy Verilog FSM for Reduce-1s Example1/00/00/01/1zeroone1CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 137module reduce (clk, reset, in, out); input clk, reset, in; output out; reg out; reg state; // state register reg next_state; reg next_out; parameter zero = 0, one = 1; always @(in or state) case (state) zero: begin // last input was a zero if (in) next_state = one; else next_state = zero; next_out = 0; end one: // we've seen one 1 if (in) begin next_state = one; next_out = 1; end else begin next_state = zero; next_out = 0; end endcase always @(posedge clk) if (reset) begin state <= zero; out <= 0; end else begin state <= next_state; out <= next_out; end endmoduleSynchronous Mealy Verilog FSM forReduce-1s Example1/00/00/01/1zeroone1CS 150 - Fall 2005 – Lec #7: Sequential Implementation – 14Announcements Review Session, Today, 5-6 PM, 125 Cory Hall Examination, Wednesday, 1-2:30 PM, 125 Cory Hall Five Quiz-like Questions -- Please Read Them Carefully! Theyare not intended to be tricky; they should contain all theinformation you need to answer the question correctly No calculators or other gadgets
View Full Document