CS 150 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – Lec #7: Sequential Implementation – 6D QQBAcloc koutD QQD QQclockoutABMealy and Moore Examples! Recognize A,B = 0,1" Mealy or Moore?CS 150 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – 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 - Spring 2007 – Lec #7: Sequential Implementation – 14Announcements! Review Session Announcement! First Midterm, Thursday, 15 February, 2-3:30 PM,125 Cory Hall" ??? Quiz-like Questions -- Please Read Them
View Full Document