1ECE 274 - Digital LogicChapter 8: Synchronous Sequential Circuits Lecture 19 State-Assignment Problem (8.2) Mealy State Model (8.3)2ECE 274 - Digital LogicState EncodingOn2On1 On3Offx=1x=1x=1x=0b’b00011011Outputs: rInputs: aK1 K2 K3 K4r=1 r=1r=0r=1Waitr=0a’a000100001 01101000 01 10ABCbo=1bo=0 bo=0bibibi’bi’bi’biinputs: bioutputs: boinputs: boutputs: xAssigned each state an encoding Unique bit representation to each state Different encodings may optimize size, or tradeoff size and performance Currently using minimum bit-width binary encoding Use smallest number of bits to ensure unique representation33ECE 274 - Digital LogicOriginal Minimum Bit-width Encoding: Consecutive 1’s FSM000100001000001011ddddddOutputsInputss1 s0 w n1 n0 z000001010011100101110111ABCUnused000110Outputs: zBACww’z=1z=0z=0wInputs: ww’w’wConsider our original minimum bit-binary encoding assignment010000 01 11 100001ddn0s0ws1n0 = s1’s0’w001000 01 11 100101ddn1s0ws1n1 = w(s1+s0)000000 01 11 101101ddzs0ws1z = s1Cost = 3 + 7 = 10Delay = 2 gate-delayswn0n1zs1 s0State register44ECE 274 - Digital LogicModified Minimum Bit-width Encoding: Consecutive 1’s FSM000100001100dddddd001111OutputsInputss1 s0 w n1 n0 z000001010011100101110111ABUnusedC Slightly modify bit-binary encoding assignment State C encoding 10 changed to 11011000 01 11 10dd0111n0s0ws1n0 = w001000 01 11 10dd0110n1s0ws1n1 = s0w000000 01 11 10dd0111zs0ws1z = s1000110Outputs: zBACww’z=1z=0z=0wInputs: ww’w’w11Cost = 1 + 2 = 3Delay = 1 gate-delaysVerses…Cost = 3 + 7 = 10Delay = 2 gate-delayswn0n1zs1 s0State register55ECE 274 - Digital LogicOriginal Minimum Bit-width Encoding: Laser Timer FSM Let’s try another FSM Original minimum-bit width state encodingCost = 4 + 8 = 12Delay = 2 gate-delaysOutputs: xInputs: bOn2On1On3Of fx=1x=1x=1x=0b’b00011011000100101011111111000011OutputsInputss1 s0 b n1 n0 x000001010011100101110111OffOn1On2On3010000 01 11 10110100n0s0bs1n0 = s0’(b + s1)001100 01 11 10110100n1s0bs1n1 = s1’s0 +s1s0’= s1 xor s0001100 01 11 10110111s0bs1x = s1 + s0bxn0 n1s1 s0State register66ECE 274 - Digital LogicOriginal Minimum Bit-width Encoding: Laser Timer FSM Slightly modify bit-binary encoding assignment Switch State On2 and On3’s encoding000100111111000011101011OutputsInputss1 s0 b n1 n0 x000001010011100101110111OffOn1On3On2011100 01 11 10000100n0s0bs1n0 = s1’(b +s0)001100 01 11 10000111n1s0bs1n1 = s0001100 01 11 10110111xs0bs1x = s1 + s0Outputs: xInputs: bOn2On1On3Of fx=1x=1x=1x=0b’b000110111110Cost = 3 + 6 = 9Delay = 2 gate-delaysVerses Cost = 4 + 8 = 12Delay = 2 gate-delaysbxn0 n1s1 s0State register70001Inputs: none; Outputs: xx=0x=1AB1110DCx=1x=11000010000010010ECE 274 - Digital LogicOne-Hot Encoding Alternative state encoding scheme - One-hot encoding Encoding length (bits) equal to number of states Only 1 bit in encoding is ‘1’clkn0s3 s2 s1 s0n1n2 n3State registerxCost = 1 + 3 = 4Delay = 1 gate-delayWhat happens with the one-hot encoding?80001Inputs: none; Outputs: xx=0x=1AB1110DCx=1x=1clks1n1xs0n0State registerECE 274 - Digital LogicOne-Hot Encoding Alternative state encoding scheme - One-hot encoding Encoding length (bits) equal to number of states Only 1 bit in encoding is ‘1’Cost = 4 + 8 = 12 (ignore inv)Delay = 2 gate-delaysWhat happens if we stuck with the original minimum-bit width encoding?Verses one hotCost = 1 + 3 = 4Delay = 1 gate-delay99ECE 274 - Digital LogicOriginal Minimum Bit-width Encoding: Consecutive 1’s FSMOutputs: zBACww’z=1z=0z=0wInputs: ww’w’wLet’s try one-hot state encoding with Book example 8.3dd d011000010000dd dOutputsInputss1 s0 w n1 n0 z00X01001110010111XUnusedABUnuseds2000000d0001dn2010011dd d00000101XCUnused11101ddd ddd d10X11XUnusedUnused11ddn2 = s0’wn1 = s0wn0 = w’z = s2wn0n1zs1 s0State registers2n2Cost = 2 + 4 = 6Delay = 1 gate-delaysVerses min bit-widthCost = 3 + 7 = 10Delay = 2 gate-delays00101010010ECE 274 - Digital LogicOne-Hot Encoding Example: Laser Timer Let’s try one-hot encoding using the Laser timer example State table leads to equations: x = s3 + s2 + s1 n3 = s2 n2 = s1 n1 = s0*b n0 = s0*b’ + s3Outputs: xInputs: bOn2On1On3Offx=1x=1x=1x=0b’b00010010 0100 100000111111OutputsInputss3 s2 b b00 000 100 000 101 001 110 010 1OffOn1On3On20000010110100000n3 n20110000000000101n1 n0s1 s00101101000000000s2n1xs1n0State registers3 s0n3n2b11ECE 274 - Digital LogicComparing One-Hot Encoding to Minimum Bit-width Encoding How does it compare? Larger (don’t forget state register is bigger too) Same delay One method is not best for every applicationCost = 3 + 6 = 9Delay = 2 gate-delaysOriginal Min-bit widthbxn0 n1s1 s0State registers2n1xs1n0State registers3 s0n3n2bCost = 4 + 8 = 12Delay = 2 gate-delaysbxn0 n1s1 s0State registerModified Min-bit width One-hot encodingCost = 4 + 9 = 13Delay = 2 gate-delays12ECE 274 - Digital LogicOutput Encoding Another state encoding method - output encoding State encoding is same as the output values Possible if enough outputs, all states with unique output values0001Outputs: x,yxy = 00xy = 11AB1110DCxy = 01xy = 10Use the output values as the state encoding13ECE 274 - Digital LogicOutput Encoding Example: Sequence GeneratorOutputs: w, x, y, zwxyz=0001wxyz=0011ABDCwxyz=1000wxyz=1100n0s3 s2 s1 s0n1n2n3State registerwxyz Create FSM to generate sequence 0001, 0011, 1110, 1000, repeat Use output values as state encoding Create state table Derive equations for next state n3 = s1 + s2; n2 = s1; n1 = s1’s0; n0 = s1’s0 + s3s2’OutputsInputss3 s200001110ABCD00111000n3 n211000001n1 n0s1 s00111000014ECE 274 - Digital LogicOutput Encoding Example: Sequence Generator 2 Create FSM to generate sequence 011, 011, 001, 100, 010, repeat Can we use output values as state encoding? Choice 1 – No, not all outputs unique so try another encoding method Choice 2 – Output encode as many as possible, then choose unique encoding for remaining states  Create state table and derive equations n2 = s1’s0 n1 = s1s0’ n0 = s2’s0’ x = s2 y = s1 + s2’s0’ z = s0 + s2’s1’ Output (x, y, z) may require additional logic and not just the state encodingOutputs: x, y, zxyz = 011xyz = 011ABEDxyz = 010xyz = 100xyz = 001C011000010100001OutputsInputss200001111ACDE01000dddn20100110000ddddddn1 n0s1 s00001101100011011B00001dddx1101101100ddddddyz15ECE 274 - Digital