CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 1Sequential Logic Implementation! Models for representing sequential circuits" Finite-state machines (Moore and Mealy)" Representation of memory (states)" Changes in state (transitions)! Design procedure" State diagrams" State transition table" Next state functionsCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 2Abstraction of State Elements! Divide circuit into combinational logic and state! Localize feedback loops and make it easy to break cycles! Implementation of storage elements leads to variousforms of sequential logicCombinationalLogicStorage ElementsOutputsState OutputsState InputsInputsCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 3Forms of Sequential Logic! Asynchronous sequential logic – state changes occurwhenever state inputs change (elements may be simplewires or delay elements)! Synchronous sequential logic – state changes occur inlock step across all storage elements (using a periodicwaveform - the clock)ClockCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 4In = 0In = 1In = 0In = 1100010110111001Finite State Machine Representations! States: determined by possible values in sequentialstorage elements! Transitions: change of state! Clock: controls when state can change by controllingstorage elements! Sequential Logic" Sequences through a series of states" Based on sequence of values on input signals" Clock period defines elements of sequenceCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 5Example Finite State Machine Diagram! Combination lock from first lectureresetS3closedclosedmux=C1equal& newnot equal& newnot equal& newnot equal& newnot newnot newnot newS1 S2 OPENERRclosedmux=C2equal& newclosedmux=C3equal& newopenCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 6Can Any Sequential System beRepresented with a State Diagram?! Shift Register" Input value shownon transition arcs" Output values shownwithin state node1001101110111010100000010111111100000100D Q D Q D QINOUT1 OUT2 OUT3CLKCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 70101001100110010001011113-bit up-counterCounters are Simple Finite State Machines! Counters" Proceed thru well-defined state sequence in response to enable! Many types of counters: binary, BCD, Gray-code" 3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ..." 3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111, ...CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 8Verilog Upcountermodule binary_cntr (q, clk) inputs clk; outputs [2:0] q; reg [2:0] q; reg [2:0] p; always @(q) //Calculate next state case (q) 3’b000: p = 3’b001; 3’b001: p = 3’b010; … 3’b111: p = 3’b000; endcase always @(posedge clk) //next becomes current state q <= p;endmoduleCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 9How Do We Turn a State Diagram into Logic?! Counter" Three flip-flops to hold state" Logic to compute next state" Clock signal controls when flip-flop memory can change# Wait long enough for combinational logic to compute new value# Don't wait too long as that is low performanceD Q D Q D QOUT1 OUT2 OUT3CLK"1"CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 10FSM Design Procedure! Start with counters" Simple because output is just state" Simple because no choice of next state based on input! State diagram to state transition table" Tabular form of state diagram" Like a truth-table! State encoding" Decide on representation of states" For counters it is simple: just its value! Implementation" Flip-flop for each state bit" Combinational logic based on encodingCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 110101001100110010001011113-bit up-countercurrent state next state0 000 001 11 001 010 22 010 011 33 011 100 44 100 101 55 101 110 66 110 111 77 111 000 0FSM Design Procedure: State Diagramto Encoded State Transition Table! Tabular form of state diagram! Like a truth-table (specify output for all inputcombinations)! Encoding of states: easy for counters – just use valueCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 12C3 C2 C1 N3 N2 N10 0 0 0 0 10 0 1 0 1 00 1 0 0 1 10 1 1 1 0 01 0 0 1 0 11 0 1 1 1 01 1 0 1 1 11 1 1 0 0 0N1 := C1'N2 := C1C2' + C1'C2:= C1 xor C2N3 := C1C2C3' + C1'C3 + C2'C3:= C1C2C3' + (C1' + C2')C3:= (C1C2) xor C3notation to showfunction represent input to D-FFImplementation! D flip-flop for each state bit! Combinational logic based on encoding0 00 11 10 1C1C2C3N30 11 01 00 1C1C2C3N21 10 01 10 0C1C2C3N1CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 13D QQImplementation (cont'd)! Programmable Logic Building Block for Sequential Logic" Macro-cell: FF + logic# D-FF# Two-level logic capability like PAL (e.g., 8 product terms)CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 14In C1 C2 C3 N1 N2 N30 0 0 0 0 0 00 0 0 1 0 0 00 0 1 0 0 0 10 0 1 1 0 0 10 1 0 0 0 1 00 1 0 1 0 1 00 1 1 0 0 1 10 1 1 1 0 1 11 0 0 0 1 0 01 0 0 1 1 0 01 0 1 0 1 0 11 0 1 1 1 0 11 1 0 0 1 1 01 1 0 1 1 1 01 1 1 0 1 1 11 1 1 1 1 1 1N1 := InN2 := C1N3 := C2 Another Example! Shift Register" Input determines next state1001101110111010100000010111111100000100D Q D Q D QINOUT1 OUT2 OUT3CLKCS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 15More Complex Counter Example! Complex Counter" Repeats five states in sequence" Not a binary number representation! Step 1: Derive the state transition diagram" Count sequence: 000, 010, 011, 101, 110! Step 2: Derive the state transition table from thestate transition diagramPresent State Next StateC B A C+ B+ A+0 0 0 0 1 00 0 1 – – –0 1 0 0 1 10 1 1 1 0 11 0 0 – – –1 0 1 1 1 01 1 0 0 0 01 1 1 – – –note the don't care conditions that arise from the unused state codes010000 110101011CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 16C+ := AB+ := B' + A'C'A+ := BC'More Complex Counter Example (cont’d)! Step 3: K-maps for Next State Functions0 0X 10 XX 1ABCC+1 1X 00 XX 1ABCB+0 1X 10 XX 0ABCA+CS 150 - Spring 2007 – Lec #6: Moore and Mealy Machines - 17Self-Starting Counters (cont’d)! Re-deriving state transition table from don't careassignment0 01 10 01 1ABCC+1 11 00 10 1ABCB+0 10 10 00 0ABCA+Present State Next StateC B A C+ B+ A+0 0 0 0 1 00 0 1 1 1 00 1 0 0 1 10 1 1 1 0 11 0 0 0 1 01 0 1 1 1 01 1 0 0 0 01 1 1 1 0 0010000 110101011001111100CS 150 - Spring 2007 – Lec #6: Moore and
View Full Document
Unlocking...