1CSE140 LInstructor: Thomas Y. P. LeeFebruary 15, 2006Agendaz Lab3  Counters are FSM Finite State Machine Models to represent FSM – Mealy Machine and Moore Machinez FSM Design Procedure State Diagram State Transition Table Next State Logic Functionsz Example One – Vending Machine Mealy Machine Implementation Moore Machine Implementationz Quartus II Tutorial – Finite State Machine Implementationz Improved Vending Machine z Moore Machine Implementation Mealy Machine Implementation2Acknowledgementz Materials in this lecture are courtesy of the following people z Randy H. Katz (University of California, Berkeley, Department ofElectrical Engineering &Computer Science)z MIT Prof. Anantha Chandrakasan and Donald E. Troxel “Introduction to Digital System Design Lab”z Professor C.K.Cheng, CSE140Lz John F. Wakerly, Digital Design, “Principles and Practices”, 3rd edition Counters are FSM0101001100110010001011113-bit up-counterz Countersz proceed through well-defined sequence of states in response to enablez Many types of counters: binary Up/Down, BCD, Gray-code,Divide-by-3,…z 3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ...z 3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111, ...3Finite State Machinez Finite State Machines (FSMs) are a useful abstraction for sequential circuits with “states” of operationz At each clock edge, combinational logic block computes outputs and next state as a function of inputs and present stateTwo Types of FSM - Mealy and Moore4Pipelined State Machinez Often used in PLD-based state machines. Outputs taken directly from flip-flops, valid sooner after clock edge. But the “output logic” must determine output value one clock tick sooner (“pipelined”).Comparison of Mealy and Moore Machinez Mealy machines tend to have less statesz different outputs on arcs (n2) rather than states (n)z Moore machines are safer to usez outputs change at clock edge (always one cycle later)z In Mealy machines, input change can cause output change as soon as logic is done – a big problem when two machines are interconnected – asynchronous feedback may occur if one isn’t carefulz Mealy machines react faster to inputsz react in same cycle – don't need to wait for clockz in Moore machines, more logic may be necessary to decode stateinto outputs – more gate delays after clock edge5State Machine Analysis Stepsz Assumption: Starting point is a logic diagram.z 1. Determine next-state function and output functionz 2. Construct state (transition) table For each state/input combination, determine the excitation value.Using the characteristic equation, determine the corresponding next-state values (trivial with DFF’s)z 3. Construct output table For each state/input combination, determine the output value (Can be combined with state table.)z 4. Draw state diagramVendingMachineFSMNDResetClockOpenCoinSensorReleaseMechanismExample in Katz’s Book: Vending Machinez Release one item after 15 cents are depositedz Single coin slot for dimes, nickelsz No change.-Æ not realisticz The controller’s cause a single item to be released down a chute to the customer -> how to choose different items?6Vending Machine (Cont.)z Suitable abstract representation typical input sequences:z 3 nickelsz nickel, dimez dime, nickelz two dimes draw state diagram:z inputs: N, D, resetz output: open chute assumptions:z assume N and D assertedfor one cyclez each state has a self loopfor N = D = 0 (no coin)S0ResetS2DS6[open]DS4[open]DS1NS3NS5[open]NS8[open]DS7[open]NInitial vending-machine state diagramMinimized Vending Machine’s States Minimize number of states - reuse states whenever possible S4,S5….,S8 have identical behavior=> combine into a single stateMinimized symbolic state transition tablepresent inputs next outputstate D N state open0¢ 0 0 0¢ 001 5¢ 01 0 10¢ 011 X X5¢ 0 0 5¢ 00 1 10¢ 01 0 15¢ 011 X X10¢ 0 0 10¢ 00 1 15¢ 01 0 15¢ 011 X X15¢ X X 15¢ 10¢Reset5¢NNN + D10¢D15¢[open]DMinimized vending-machine state diagram7Vending Machine Encoded State Transition Tablez Uniquely encode statespresent state inputs next state outputQ1 Q0 D N D1 D0 open00 0 0 00 001 01 010 10 011 XX X01 0 0 01 001 10 010 11 011 XX X10 0 0 10 001 11 010 11 011 XX X11 0 0 11 10 1 1 1 1present state inputs next state outputQ1 Q0 D N D1 D0 open00 0 0 00 001 01 010 10 011 XX X01 0 0 01 001 10 010 11 011 XX X10 0 0 10 001 11 010 11 011 XX X11 0 0 11 10 1 1 1 11 0 1 1 11 1 X X XMoore Implementation of Vending MachineD1 = Q1 + D + Q0 ND0 = Q0’ N + Q0 N’ + Q1 N + Q1 DOPEN = Q1 Q0z Mapping to Truth Table00110111XXXX1111Q1D1Q0ND01101011XXXX0111Q1D0Q0ND00100010XXXX0010Q1OpenQ0ND8Encoding in State Machine• State Machine Encoding Style:  Binary, One-hot, Two-hot, Gray code, Johnson Code Binary encoding Requires the least number of FFs. With n FFs, 2nstatescan be encoded. Disadvantages: require more logic, slower. One-hotencodingone FF per state, with n FFs, n states can be encoded. Require the least amount of extra logic and fastest Two- hot encodingPresents two bits active per state. With n FFs, n(n-1)/2 states can be encoded. Gray code encodingAdjacent Gray codes are different in only one bit. n bits Gray code needs n FFs and can represent 2nstates.  Johnson code encodingUse the output pattern of Johnson counter to encode the states. n bits Johnson code needs n FFs and can represent 2n states.Different State EncodingsIn Lab3: We use Binary Code, One-Hot State Encoding Different state encodings leads to different circuit implementation, and thus different hardware cost and performance of state machines  State encoding provides another dimension of optimizations Number of FFsrequired1000000001100111State70100000010010110State60010000001010101State50001000000110100State40000100010001011State30000010001001010State20000001000101001State10000000100011000State0ONEHOT(8 bits)TWOHOTBINARYSTATE853Number of FFsrequired1000000001100111State70100000010010110State60010000001010101State50001000000110100State400001000011State30000010001001010State20000001000101001State10000000100011000State0TWOHOTBINARYSTATEEncoding StyleJohnsonCode (4 bits)GrayCode(3 bits)00030010110101101111011000000000100110111111111101100100049Vending Machine (Cont.)present state inputs next state outputQ3 Q2 Q1 Q0 D N D3 D2 D1 D0