EECC341 - ShaabanEECC341 - Shaaban#1 Lec # 16 Winter 2001 2-6-2002State Machine Design ProcedureState Machine Design Procedure1. Build state/output table (or state diagram) from worddescription using state names.2. Minimize number of states (optional).3. State Assignment: Choose state variables and assign bitcombinations to named states.4. Build transition/output table from state/output table (or statediagram) by substituting state variable combinations insteadof state names.5. Choose flip-flop type (D, J-K, etc.)6. Build excitation table for flip-flop inputs from transition table.7. Derive excitation equations from excitation table.8. Derive output equations from transition/output table.9. Draw logic diagram with excitation logic, output logic, andstate memory elements.EECC341 - ShaabanEECC341 - Shaaban#2 Lec # 16 Winter 2001 2-6-2002State Machine Design Example 1:State Machine Design Example 1:110 Detector110 Detector• Word description (110 input sequence detector):– Design a state machine with input A and output Y.– Y should be 1 whenever the sequence 1 1 0 has been detected onA on the last 3 consecutive rising clock edges (or ticks).– Otherwise, Y = 0– Note: this is a Moore machine, that is the output, Y, depends onlyon inputs at previous clocks rising edges , not on the currentinput.• Timing diagram interpretation of word description (onlyrising clock edges are shown):ACLKY0 1 1 0 0 1 1 1 0 1 1 1EECC341 - ShaabanEECC341 - Shaaban#3 Lec # 16 Winter 2001 2-6-2002State Machine Design Example 1: 110 DetectorState Machine Design Example 1: 110 DetectorStep1: Choosing StatesChoosing States• Possible states (What does the state machine need toremember?):– Initial : power up, no clocks yet Y = 0– No1s : first 1 not found Y = 0– First1 : first 1 found Y = 0– Two1s : at least 2 consecutive 1s found Y = 0– ALL : found 1 1 0 Y = 1• Are all the states needed?– Notice: Initial is equivalent to NO1s– We can drop the state Initial and replace it with state No1sEECC341 - ShaabanEECC341 - Shaaban#4 Lec # 16 Winter 2001 2-6-2002State Machine Design Example 1: 110 DetectorState Machine Design Example 1: 110 DetectorStep 1: State/Output Table and DiagramSNo1sFirst1Two1sALLA0No1sNo1sALLNo1s1First1Two1sTwo1sFirst1Y0001State TableS*NO1s0First10Two1s0ALL1111000State DiagramResetFormat:Arc: input ANode: state/output Y10EECC341 - ShaabanEECC341 - Shaaban#5 Lec # 16 Winter 2001 2-6-2002Step3: State Assignment ConsiderationsStep3: State Assignment Considerations• Why does the choice of state assignment matter?– Has a big effect on the complexity of excitation and output equationsand thus on the amount of combinational logic needed.• How to find the best state assignment?– The only known way is to try all assignments and determine theresulting equations.• N = 2: (22)! = 4! = 24 assignments for 2 state bits• N = 3: (23)! = 8! = 40,320 assignments for three state bits.• N = 4: (24)! = 16! = 20,922,789,888,000assignments for 4 state bits!!!THIS IS NOT PRACTICAL APPROACH!∴ Use heuristic guidelines for pretty good assignments.This is still an active area of research!• There is no effective way to guarantee a “best” assignment. Theheuristic methods sometimes perform poorly!EECC341 - ShaabanEECC341 - Shaaban#6 Lec # 16 Winter 2001 2-6-2002State Assignment StrategiesState Assignment Strategies• Simplest Assignment:– Straight binary, not best; purely arbitrary assignment.• One Hot Assignment:– Redundant encoding, each flip-flop is assigned a state.– Uses the same number of bits as there are states (not useful in largedesigns).– Simple to assign; simple next state logic (no state decoding required)– Output logic is simple! One OR gate per Moore output!• Almost One Hot Assignment:– Almost same as One Hot, but one less state bit.– Use all 0’s to represent a state (usually INIT).– Must now decode state 0 if it is needed.• Decomposed Assignment:– Use the “structure” of the state table to simplify next-state and outputlogic.– An “art” which requires much practice.EECC341 - ShaabanEECC341 - Shaaban#7 Lec # 16 Winter 2001 2-6-2002Example: State Assignment StrategiesExample: State Assignment Strategies Alternative Assignments ABQ1..Q4Q1..Q5Q1Q2Q3 Q1Q2Q3 S 00 01 11 10 Z 0000 00001 000 000 INIT A0 A0 A1 A1 0 0001 00010 100 001 A0 OK0 OK0 A1 A1 0 0010 00100 101 010 A1 A0 A0 OK1 OK1 0 0100 01000 110 011 OK0 OK0 OK0 OK1 A1 1 1000 10000 111 100 OK1 A0 OK0 OK1 OK1 1Almost One Decomposed Simplest One Hot Hot– Example decomposition:• Initial State = all 0’s for easy RESET• INIT state is different, so use Q1 = 1 for non-INIT states; thus D1=1• Z = 1 in only 2 states, so use Q2 =1 for states when Z = 1; thus Z = Q2• Use Q3 = 1 for state transitions caused by A having the value of 1 (alldestination states cause by A = 1, i.e. states A1 and OK1); thus D3=A THUS, simpler next state and output logic!EECC341 - ShaabanEECC341 - Shaaban#8 Lec # 16 Winter 2001 2-6-2002State Assignment Heuristic GuidelinesState Assignment Heuristic GuidelinesStarting from the highest priority to the lowest:• Choose initial coded state that’s easy to produce at reset: (all 0’sor 1’s)– This simplifies the initialization circuitry.• Freely use any of the 2n state codes for best assignment(i.e.. with s states, don’t just use the first s integers 0,1,…,s-1)• Define specific bits or fields that have meaning with respect toinput or output variables (decomposed codes).• Consider using more than minimum number of state variables toallow for decomposed codes.• Minimize number of state variables that change at each transition• Simplify output logic.EECC341 - ShaabanEECC341 - Shaaban#9 Lec # 16 Winter 2001 2-6-2002State Machine Design Example 1: 110 DetectorState Machine Design Example 1: 110 DetectorStep 3: State Assignment• Choose state variable assignments:– Initial state all 0s– Q2 = last A, so Q2* = A– minimize number of transitionsSNo1sFirst1Two1sALLA0No1sNo1sALLNo1s1First1Two1sTwo1sFirst1Y0001S*Q1 Q2 0 0 0 1 1 1 1 0EECC341 - ShaabanEECC341 - Shaaban#10