EECS 150 - Components and Design Techniques for Digital Systems Lec 06 – Using FSMs 9-13-07OutlineReview: Typical Controller: stateTypical Controller: state + outputTypical Controller: state + output + inputReview: Two Kinds of FSMsReview: Finite State Machine RepresentationsReview: Formal Design ProcessFormal Design ProcessFormal Design ProcessReview: What’s an FSM?How to quickly implement the State Transition Diagram?One Answer: Xilinx 4000 CLBTwo 4-input functions, registered output5-input function, combinational outputRecall: Parallel to Serial ConverterExample: Byte-bit streamByte-bit stream with Rate MatchingAnother example: bus protocolsExample: Pentium System OrganizationArbitration for the bus…Simple Synchronous ProtocolProcessor Side of Protocol - sketchSimple Synchronous Protocol (cont)AnnouncementsFundamental Design PrincipleForms of Sequential LogicGeneral Model of Synchronous CircuitComposing FSMs into larger designsComposing Moore FSMsComposing Mealy FSMs …Recall: What makes Digital Systems tick?Recall 61C: Single-Cycle MIPSRecall 61C: 5-cycle Datapath - pipelineFSM timingFinite State Machines in VerilogVerilog FSM - Reduce 1s exampleMoore Verilog FSM: combinational partMoore Verilog FSM: state partMealy Verilog FSM for Reduce-1s exampleRestricted FSM Implementation StyleSingle-always Moore Machine (Not Allowed!)Slide 43Finite State MachinesSummary9/13/07EECS150 F07 Culler Lec 61EECS 150 - Components and Design Techniques for Digital Systems Lec 06 – Using FSMs9-13-07 David CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp:/inst.eecs.berkeley.edu/~cs1509/13/07EECS150 F07 Culler Lec 62Outline•Review FSMs•Mapping to FPGAs•Typical uses of FSMs•Synchronous Seq. Circuits – safe composition•Timing•FSMs in verilog9/13/07EECS150 F07 Culler Lec 63Review: Typical Controller: state Combinational Logicstatestate(t+1) = F ( state(t) )state Next statei2 i1 i0 o2 o1 o00 0 0 0 0 10 0 1 0 1 10 1 0 1 1 00 1 1 0 1 01 0 0 0 0 01 0 1 1 0 01 1 0 1 1 11 1 1 1 0 1Example: Gray Code Sequence000001 011010110111 1011009/13/07EECS150 F07 Culler Lec 64Typical Controller: state + outputCombinational Logicstatestate(t+1) = F ( state(t) )state Next statei2 i1 i0 o2 o1 o00 0 0 0 0 10 0 1 0 1 10 1 0 1 1 00 1 1 0 1 01 0 0 0 0 01 0 1 1 0 01 1 0 1 1 11 1 1 1 0 1Output (t) = G( state(t) )01101001odd000/0001/1 011/0010/1110/0111/1 101/0100/19/13/07EECS150 F07 Culler Lec 65Typical Controller: state + output + inputCombinational Logicstatestate(t+1) = F ( state(t), input (t) )state Next statei2 i1 i0 o2 o1 o00 0 0 0 0 10 0 1 0 1 10 1 0 1 1 00 1 1 0 1 01 0 0 0 0 01 0 1 1 0 01 1 0 1 1 11 1 1 1 0 1Output (t) = G( state(t) )000000001 x x x 0 0 0clr000/0001/1 011/0010/1110/0111/1 101/0100/1Input01101001oddclr=1clr=0clr=?9/13/07EECS150 F07 Culler Lec 66Review: Two Kinds of FSMs•Moore Machine vs Mealy MachineCombinational Logicstatestate(t+1) = F ( state(t), input)Output (t) = G( state(t), Input )Inputstatestate(t+1) = F ( state(t), input(t))Output (t) = G( state(t))InputState / outInputStateInput / Out9/13/07EECS150 F07 Culler Lec 67In = 0In = 1In = 0In = 1100010110111001Review: Finite State Machine Representations•States: determined by possible values in sequential storage elements•Transitions: change of state•Clock: controls when state can change by controlling storage elements•Sequential Logic–Sequences through a series of states–Based on sequence of values on input signals–Clock period defines elements of sequence9/13/07EECS150 F07 Culler Lec 68Review: Formal Design Process•Circuit Diagram:–XOR gate for ns calculation–DFF to hold present state–no logic needed for outputLogic equations from table:OUT = PSNS = PS xor INnsps•Review of Design Steps:1. Circuit functional specification2. State Transition Diagram3. Symbolic State Transition Table4. Encoded State Transition Table5. Derive Logic Equations6. Circuit DiagramFFs for stateCL for NS and OUTTake this seriously!9/13/07EECS150 F07 Culler Lec 69Formal Design Process •“State Transition Diagram”–circuit is in one of two states.–transition on each cycle with each new input, over exactly one arc (edge).–Output depends on which state the circuit is in.ParityCheckerINOUTbit stream0 if even parity1 if odd parityexample: 0 0 1 1 1 0 1 even even odd even odd odd evenCLKtime9/13/07EECS150 F07 Culler Lec 610Formal Design Process•State Transition Table:•Invent a code to represent states:Let 0 = EVEN state, 1 = ODD statepresent nextstate OUT IN state EVEN 0 0 EVEN EVEN 0 1 ODD ODD 1 0 ODD ODD 1 1 EVENpresent state (ps) OUT IN next state (ns) 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0Derive logic equations from table (how?):OUT = PSNS = PS xor IN9/13/07EECS150 F07 Culler Lec 611Review: What’s an FSM?•Next state is function of state and input•Moore Machine: output is a function of the state•Mealy Machine: output is a function of state and inputOften PLAsState / outputinputAinputBState inputA/outputAinputB/outputBWhich is which?9/13/07EECS150 F07 Culler Lec 612How to quickly implement the State Transition Diagram?9/13/07EECS150 F07 Culler Lec 613One Answer: Xilinx 4000 CLB9/13/07EECS150 F07 Culler Lec 614Two 4-input functions, registered output9/13/07EECS150 F07 Culler Lec 6155-input function, combinational output9/13/07EECS150 F07 Culler Lec 616Recall: Parallel to Serial Converter//Parallel to Serial convertermodule ParToSer(LD, X, out, CLK); input [3:0] X;input LD, CLK;output out; reg out;reg [3:0] Q;assign out = Q[0];always @ (posedge CLK) beginif (LD) Q <= X;else Q <= {1’b0,Q[3:1]};endendmodule // ParToSerOne common use of FSMs is in adapters from one subsystem to another.• different data widths• different bit rates• different protocols, …9/13/07EECS150 F07 Culler Lec 617Example: Byte-bit streamByte FIFOpopSerial linkShift registercontrollerLDbit 0/popbit 1bit 2bit 3bit 4bit 5bit 6bit 7 / LDinit / LD9/13/07EECS150 F07 Culler Lec 618Byte-bit stream with Rate Matching•How would you implement this FSM?Byte FIFOpopSerial linkShift registercontrollerLDbit 0/popbit 1bit 2bit 3bit 4bit 5bit 6bit 7 / LDinit / LDrdybit
View Full Document
Unlocking...