Slide 1Mealy and Moore MachinesState and State DiagramState DiagramsState Diagram Examples (Mealy)State Diagram Examples (Moore)Design Example: Sequence RecognizerSequence RecognizerSlide 9State TableLogic Circuits Design StepsLogic Circuits DesignSlide 13Example 2State DiagramSlide 16Logic Circuit DesignSlide 18Vending Machine State MachineSlide 20Slide 21Slide 22Slide 23Logic Circuits of the Vending MachineECE2030 Introduction to Computer EngineeringLecture 16: Finite State MachinesProf. Hsien-Hsin Sean LeeProf. Hsien-Hsin Sean LeeSchool of Electrical and Computer EngineeringSchool of Electrical and Computer EngineeringGeorgia TechGeorgia Tech2Mealy and Moore MachinesCombinationalcircuitsInputs X(t) Outputs Z(t)StorageElementS(t)MEALY MACHINEZ(t) = {S(t), X(t)}CombinationalcircuitsInputs X(t)Outputs Z(t)StorageElementS(t)MOORE MACHINEZ(t) = {S(t)}3State and State Diagram•A state represents the machine snapshot at a given clock period•A clock is typically used to synchronize the state transition•A graph consists of a set of–Circles: •Each represents a state •Use double circle to represent the initial state–Directed arc: each represents a state transition–Inputs/outputs•Mealy machine: –Label input/output along each arc •Moore machine: –Label input along each arc–Label output inside the circle (i.e. state)4State DiagramsExample:State: S(t) {Sk, Sj}Inputs: X(t) {a, b}Outputs: Z(t) {p, q}Initial state: S(0) = SkA Mealy machine example A Moore machine exampleSkSja/pb/qb/pa/qabSk/pSj/qba5State Diagram Examples (Mealy)S0S10/01/11/00/0S0S10/0, 1/10/01/06State Diagram Examples (Moore)S0/1S1/001100, 101S0/0 S1/17Design Example: Sequence Recognizer•A sequential circuit that recognizes the occurrence of a particular bit sequence•Input: X(t) {0, 1}•Output: Z(t) {0, 1} Otherwise 0, 1101t)3,X(t if1,Z(t)8Sequence RecognizerTime 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16X(t) 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 Z(t) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 Otherwise 0, 1101t)3,X(t if 1,Z(t)9Sequence RecognizerTime 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16X(t) 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 Z(t) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1S0S11/0 Otherwise 0, 1101t)3,X(t if 1,Z(t)0/00/0S21/0S30/01/00/01/1A Meanly Machine10State Table001/00/00/01/00/01/00/01/101 10 11Present StatePresent StateInput Input XXNext StateNext StateOutpuOutputtZZP1P1P0P0N1N1N0N00 0 0 0 0 00 0 1 0 1 00 1 0 0 0 00 1 1 1 0 01 0 0 1 1 01 0 1 1 0 01 1 0 0 0 01 1 1 0 1 111Logic Circuits Design Steps•Generate a Boolean function for –Each external output –Each state encoded bit•Simplify the Boolean functions•Draw a D F/F (or register) for each state encoded bit•Draw logic circuits for–External outputs–Each inputs of state encoded bits –Input of state encoded bits = the next state–Output of state encoded bits = the current state12Logic Circuits DesignPresent Present StateStateXXNext StateNext StateZZP1P1P0P0N1N1N0N00 0 0 0 0 00 0 1 0 1 00 1 0 0 0 00 1 1 1 0 01 0 0 1 1 01 0 1 1 0 01 1 0 0 0 01 1 1 0 1 100 01 11 1000 0 0 110 1 0 1 XP1P0N1N10101PPPPXN1 00 01 11 1000 0 0 111 0 1 0 XP1P0N0N001010101PPX)P0P1X(PPXPXPPPXN001PXPZ 13Logic Circuits Design0101PPPPXN1 01PPX)P0P1X(N0 01PXPZ D0F/F1 2P0N0D1F/F1 2P1N1ZD0F/F1 2P0N0XX14Example 2•Input: X(t) {a, b, c}•Output: Z(t) {q, p} Otherwise p, sb' of #odd and sa' of #even has sequence input whenq,Z(t)15State Diagram Otherwise p, sb' of #odd and sa' of #even has sequence input whenq,Z(t)SEO/qA Moore MachinebSEE/pSOO/pSOE/paacbcaCbabc16State Table01/qb00/p10/p11/paacbcaCbabcPresent State Input (a, b, c) Next State OutputP1 P0 X1 X0 N1 N0 Z0 0 0 0 1 1 00 0 0 1 0 1 00 0 1 0 0 0 00 1 0 0 1 0 10 1 0 1 0 0 10 1 1 0 0 1 11 0 0 0 0 1 01 0 0 1 1 1 01 0 1 0 1 0 01 1 0 0 0 0 01 1 0 1 1 0 01 1 1 0 1 1 0SEE = 00SEO = 01SOO = 10SOE = 11 a = 00 b = 01 c = 10 p = 0 q = 117Logic Circuit DesignPresent StateInput Next State OutputP1 P0 X1 X0 N1 N0 Z0 0 0 0 1 1 00 0 0 1 0 1 00 0 1 0 0 0 00 1 0 0 1 0 10 1 0 1 0 0 10 1 1 0 0 1 11 0 0 0 0 1 01 0 0 1 1 1 01 0 1 0 1 0 01 1 0 0 0 0 01 1 0 1 1 0 01 1 1 0 1 1 0X0)(X1P1X1)P1(X0)X0X1(P1P1X1P1X0X0X1P1N100 01 11 10001 0 X 0011 0 X 0110 1 X 1100 1 X 1P1P0X1X0N1X1P0P0X1X1P0N000 01 11 10001 1 X 0010 0 X 1110 0 X 1101 1 X 0P1P0X1X0N0P0P1Z 00 01 11 10000 0 X 0011 1 X 1110 0 X 0100 0 X 0P1P0X1X0Z18Logic Circuit DesignX0)(X1P1N1 P0P1Z D1F/F1 2P1N1D0F/F1 2P0N0X1X0ZX1P0N0 19Vending Machine State Machine•Dispense a Coke when depositing 15 ¢•Inputs–5 = a nickel–10 = a dime–BC = bad coin (including quarters in this example)•Outputs–R = reject–C = coke–N = no coke20State Diagram0 ¢BC/R5 ¢5/N10 ¢10/N5/C10/C5/NBC/R10/CBC/R21State Table0 ¢(00)BC/R5/N10/N5/C10/C5/NBC/R10/CBC/RPresent State (0¢, 5¢, 10¢)Input (5¢, 10¢ , BC)Next State (0¢, 5¢, 10¢)Output (C, N, R)P1 P0 X1 X0 N1 N0 C1 C00 0 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 1 00 1 0 0 1 0 0 00 1 0 1 0 0 0 10 1 1 0 0 1 1 01 0 0 0 0 0 0 11 0 0 1 0 1 0 11 0 1 0 1 0 1 0X X 1 1 X X X X1 1 X X X X X X5 ¢(01)10 ¢(10) 5: 0010: 01BC: 10N: 00C: 01 R: 1022Logic Circuits DesignPresent StateInput Next StateOutputP1 P0 X1 X0 N1 N0 C1 C00 0 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 1 00 1 0 0 1 0 0 00 1 0 1 0 0 0 10 1 1 0 0 1 1 01 0 0 0 0 0 0 11 0 0 1 0 1 0 11 0 1 0 1 0 1 0X X 1 1 X X X X1 1 X X X X X X11001010N1 XPXPPXXP 00 01 11 10000 1 X 0011 0 X 011X X X X100 0 X 1P1P0X1X0N110010101N0 XPXPXXPP 00 01 11 10001 0 X 0010 0 X 111X X X X100 1 X 0P1P0X1X0N023Logic Circuits DesignPresent StateInput Next StateOutputP1 P0 X1 X0 N1 N0 C1 C00 0 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 1 00 1 0 0 1 0 0 00 1 0 1 0 0 0 10 1 1 0 0 1 1 01 0 0 0 0 0 0 11 0 0 1 0 1 0 11 0 1 0 1 0 1 0X X 1 1 X X X X1 1 X X X X X XX1C1 00 01 11 10000 0 X 1010 0 X 111X X X X100 0 X 1P1P0X1X0C1P0X0X1P1C0 00 01 11 10000 0 X 0010 1 X 011X X X X101 1 X 0P1P0X1X0C024Logic Circuits of the Vending MachineX1C1 P0X0X1P1C0
View Full Document
Unlocking...