CSE140L: Components and Design CSE140L: Components and Design Techniques for Digital Systems Lab FSMs and implementationsTajana Simunic Rosing1Source: Vahid, KatzUpdatesp• Temperature in the lab?•CSE 140 Midterm #2 TomorrowCSE 140 Midterm #2 Tomorrow– 7 problems + one bonus• Lab #3– Due May 21st– Larger size controller to implement – simplified iPOD ☺–A problem to solvep2Example: heuristics for state assignmentpgSSn01014105213345435513513abai / jk/li/jaci / ji / ji / kcbc/jk / lbdi / jTiming: DefinitionsgTTT su 18T h 05D T su 1.8ns T h 0.5ns T w 331.8ns 0.5 ns T w 33Clk Q 3.3 ns T pd36T pd3.6 ns 1.1 ns3.3 ns dataDQ DQ• Cascaded FFs: 3.6 ns 1.1 ns 1.1 ns clock–Tpd> Th– Tperiod > Tpd + Tsu4Digital combinational lockg• Door combination lock:– Press reset, then punch in 3 4 bit digits followed by enter, if the values match the code the door opens; if there is an error the lock must bematch the code, the door opens; if there is an error the lock must be reset; once the door opens the lock must be reset– inputs: sequence of input values, reset– outputs: door open/close– memory: must remember combination or always have it availableresetvaluenewclock5open/closedDigital combination lock state diagramgg• States: 5 states– represent point in execution of machine– each state has outputs• Inputs: reset, new, results of comparisons•Output: open/closedOutput: open/closedERRC1!=value& newC2!=value&newC3!=value&newclosedclosed closedclosedC1==value& newC2==value& newC3==value& new& new& newresetS1 S2 S3 OPENopen6not newnot newnot newData-path and control structurep• Data-path– storage registers for combination values– multiplexer– comparator• Control– finite-state machine controller– control for data-path (which value to compare)resetnewC1 C2 C3mux 444comparatorvalueequalmultiplexercontrollercontrolclock447open/closedequal4State table for a combination lock• Finite-state machine–refine state diagram to take internal structure into accountg– state table ready for encodingreset new equal state state mux open/closed1 – – – S1 C1 closed00–S1S1C1closed010S1ERR–closednext010S1ERRclosed011S1S2C2closed...011S3OPEN–open...8Encodings for combination lockreset new equal state state mux open/closednextresetnewmux controlg• Encode state table1–––0001 001 00 0 – 0001 0001 001 00 1 0 0001 0000 – 00 1 1 0001 0010 010 0open/closedequalcontrollerclock...0 1 1 0100 1000 – 1...mux is identical to last 3 bits of stateopen/closed is identical to first bit of statetherefore, we do not even need to implement open/closed,pFFs to hold state, just use outputs– state can be: S1, S2, S3, OPEN, or ERR• needs at least 3 bits to encode: 000, 001, 010, 011, 100• and as many as 5: 00001, 00010, 00100, 01000, 10000y ,,,,• choose 4 bits: 0001, 0010, 0100, 1000, 0000– output mux can be: C1, C2, or C3• needs 2 to 3 bits to encode•choose 3 bits: 001 010 1009•choose 3 bits: 001, 010, 100– output open/closed can be: open or closed• needs 1 or 2 bits to encode• choose 1 bit: 1, 0Datapath part of combination lock• Multiplexereasy to implement as combinational logic with few inputsC1i C2i C3ivalue–easy to implement as combinational logic with few inputsC1C2C3mux controlC1C2C3multiplexermux control4444comparatorequal4value10equalMedian filter FSM• Remove single 0s between two 1s (output = NS3)0000ResetI PS1 PS2 PS3 NS1 NS2 NS300000000001000001000100011000Reset0010001001100101000100101XXX01100110010 110111100011101110001001001100101011110111110111 0110011111000101111111001101101XXX1110111111111111Median filter FSM• Realized using the standard procedure and individual FFs and gatesgI PS1 PS2 PS3 NS1 NS2 NS3000000000010000010001001100101000100101XXXNS1 = Reset’ (I)0101XXX0110011011101110001001001100NS2 = Reset’ ( PS1 + PS2 I )NS3 = Reset’ PS2O = PS31010111101111111001101101XXX11101111211101111111111Median filter FSM0000010Reset00010Reset10011001001110101100010 1101110110011110000101101110110011111001110110011101110110011013• But it looks like a shift register if you look at it rightMedian filter FSM – with SR FFsR = ResetRtS = PS2 INS1 = INS2 = PS1NS3 = PS2RSRSRSResetNS3 = PS2O = PS3OutCLKDQ DQDQInThe set input (S) does the median filter function by making the next state 111 whenever the input is 1 and14making the next state 111 whenever the input is 1 and PS2 is 1 (1 input to state x1x)Implementation using PALspg• Programmable logic building block for sequential logic–macro-cell: FF + logicg•D-FF• two-level logic capability like PAL (e.g., 8 product terms)D QQ15Equivalent Mealy and Moore state diagramsqy g• Moore machine–outputs associated with state Mealy machine outputs associated with transitionspN’ D’ + ResetReset(N’ D’ + Reset)/0Reset/0p0¢[0]NN’ D’0¢N/0N’ D’/010¢5¢[0]DNN’ D’5¢D/0N/0N’ D’/010¢[0]15¢DN+DN’ D’R’10¢15¢D/1N+D/1N’ D’/0R’/115¢[1]Reset’15¢Reset’/1Vending machine example (Moore PLD mapping)D0 = reset'(Q0'N + Q0N' + Q1N + Q1D)D1 = reset'(Q1 + D + Q0N)CLKOPEN = Q1Q0DQQ0CLKQ1SeqNDQQ1SeqDDQOpen17ComResetVending machine (synch. Mealy PLD mapping)OPEN = reset'(Q1Q0N' + Q1N + Q1D + Q0'ND +