1BR 2/1/99 1Problem DefinitionBuild a Finite State Machine(FSM) based upon your Student ID number (SID). FSM will have one external input called ODD. If ODD is true, then the FSM will reset to display the LEFTMOST odd digit in your SID, and then the output will sequence over the odd digits in your SSN, skipping over the even digits.If ODD is false, then the FSM will reset to display the LEFTMOST even digit in your SID, and then the output will sequence over the even digits in your SSN, skipping over the odd digits.BR 2/1/99 2Example Output SequencesFor SID = 458 70 2198if ODD is true:5 → 7 → 1 → 9 , repeat (5 → 7 → 1 → 9 → 5 → 7 → 1 → 9 etc)if ODD is false:4 → 8 → 0 → 2 → 8, repeat (4 → 8 → 0 → 2 → 8 → 4 → 8 → 0 → 2 → 8 etc)For SID = 688 99 1234if ODD is true:9 → 9 → 1 , repeat (9 → 9 → 1 → 9 → 9 → 1 etc)if ODD is false:6 → 8 → 8→ 2 → 4, repeat (6 → 8 → 8→ 2 → 4 → 6 → 8 →8→ 2 → 4 etc)BR 2/1/99 3ASM ChartFor ODD = 1Dout = 5 Dout = 7 Dout = 1 Dout = 9 For ODD = 0Dout = 4 Dout = 8 Dout = 0 Dout = 2 Dout = 8 We can combine these states and use ODD as a conditional input.S0S1S2S3S4S0S1S2S32BR 2/1/99 4New ASM Chartodd?01Dout = 4 Dout = 5odd?01Dout = 8 Dout = 7odd?01Dout = 0 Dout = 1To S3 (next page)S0S1S2BR 2/1/99 5New ASM Chart (cont).odd?01Dout = 2 Dout = 9From S2 (prev page)S3S4Dout = 8To S0 (prev page)BR 2/1/99 6State TableInputs Present State Next State OutputsOdd Dout0 S0 S1 4 0 S1 S2 8 0 S2 S3 00 S3 S4 20 S4 S0 81 S0 S1 5 1 S1 S2 71 S2 S3 11 S3 S0 91 S4 S0 8 (S4 onlyfor even)3BR 2/1/99 7State Encodings• Have 5 states, need at least three Flip Flops• Binary Counting order: S0= 000, S1=001, S2=010, S3=011, S4 = 100• Grey Code: S0=000, S1=001, S2=011, S3=010, S4 = 110– Grey Encoding oftens uses less logic than binary counting order• One Hot Encoding (one FF per state):S0 = 00001, S1 = 00010, S2 = 00100, S3=01000,S4 = 1000BR 2/1/99 8What type of FFs to use?• D-FFs are most common in Programmable logic – If a PLD has a FF, it will at least be able to do the DFF function• We will use DFFs for this example• The NextState inputs are simply the D inputs of the FFsBR 2/1/99 9State Table (Grey encoding for states)Inputs Present State Next State OutputsOdd Q2Q1Q0 D2D1D0 Dout0 000 001 0100 0 001 011 1000 0 011 010 00000 010 110 00100 110 000 10001 000 001 0101 1 001 011 01111 011 010 00011 010 000 10011 110 000 10004BR 2/1/99 10Unoptimized Next State equationsD2 = ODD’ Q2’ Q1 Q0’D1 = ODD’ Q2’ Q1’ Q0 + ODD’ Q2’ Q1 Q0 + ODD’ Q2’ Q1 Q0’ + ODD Q2’ Q1’ Q0 + ODD Q2’ Q1 Q0 D0 = ODD’ Q2’ Q1’ Q0’ + ODD’ Q2’ Q1’ Q0 + ODD Q2’ Q1’ Q0’ + ODD Q2’ Q1’ Q0BR 2/1/99 11Unoptimized Output EquationsDOUT(3) = ODD’ Q2’ Q1’ Q0 + Q2 Q1 Q0’ (state S4) + ODD Q2’ Q1 Q0’ DOUT(2) = ODD’ Q2’ Q1’ Q0’ + ODD Q2’ Q1’ Q0’ + ODD Q2’ Q1’ Q0 DOUT(1) = ODD’ Q2’ Q1 Q0’ + ODD Q2’ Q1’ Q0 DOUT(0) = ODD Q2’ Q1’ Q0’ + ODD Q2’ Q1’ Q0 + ODD Q2’ Q1 Q0 + ODD Q2’ Q1 Q0’ For DOUT(3) a simple optimization was done -- if in State S4, DOUT(3) = 1, regardless of ODD input.BR 2/1/99 12State Table (arranged in binary order)Inputs Present State Next State OutputsOdd Q2Q1Q0 D2D1D0 Dout0 000 001 0100 0 001 011 10000 010 110 0010 0 011 010 00000 100 xxx xxxx0 101 xxx xxxx0 110 000 10000 111 xxx xxxx 1 000 001 0101 1 001 011 01111 010 000 1001 1 011 010 00011 100 xxx xxxx1 101 xxx xxxx1 110 000 10001 111 xxx xxxxIllegal states in Red5BR 2/1/99 13Example Optimization Optimize D1Odd,Q2010x1x00Q1,Q0001x10011110x0x1x1x011 10D1 = Q2’Q0 + Odd’Q2’Q1Odd,Q2010x0x00Q1,Q0000x00011110x1x1x1x111 10Optimize Dout(0)Dout(0) = OddBR 2/1/99 14Try One Hot EncodingS0 = 00001, S1 = 00010, S2 = 00100, S3=01000, S4 = 10000Each FF represents a state. Each next state equation can be written as :Dn = (how do I get to this state?) + (how do I stay in this state?)In this FSM, never stay in one state more than clock, so only need to know how to get to that state. By Inspection: D0 = Q4 + Q3Odd D1 = Q0 D2 = Q1D3 = Q2D4 = Q3 Odd’BR 2/1/99 15State TableInputs Present State Next State OutputsOdd Dout0 S0 S1 4 (0100) 0 S1 S2 8 (1000) 0 S2 S3 0 (0000)0 S3 S4 2 (0010)0 S4 S0 8 (1000)1 S0 S1 5 (0101) 1 S1 S2