数字逻辑设计及应用教学英文课件：Lec18-chap 7

1、1Digital Logic Design and ApplicationLecture #18Clocked Synchronous State-Machine AnalysisUESTC, Spring 20137.3.1 state machine structure2Finite state（有限状态）：实际时序电路的状态个数是可列的有限个，因此时序电路又被称为有限状态机（Finite state machine）。（log2n）7.3.1 state machine structure32 D F.F can store four states.7.3.1 state machine

2、 structure4时钟信号 触发类型取决于内部的FF类型；Edge trigger，pulse trigger时序电路的输出变化与CLK的关系取决于状态机的类型。Mealy，Moore，Pipelined output57.3.1 state machine structureState-machine structureMealy machine modelMealy machine的名字来自这个概念的提出者，在1951年写了A Method for Synthesizing Sequential Circuits的状态机的先驱 G. H. MealyOutput=G(current s

3、tate, inputs)Next state=F(current state, inputs)Next-Statelogic FStateMemoryOutputlogic G7.3.1 Finite state machine structure6NextState Logic FStateMemoryclockOutputLogicGState-machine structure Moore machine modelMoore状态机是输出只由当前状态直接确定的有限状态机。Output= G (current state)7ENENQ0Q0Q1Q1ENMAXQ0Q1CLKD0D1Meal

4、y machineMoore machineMAXSExample state machineA Mealy machine has equivalent Moore machine model.7.3.4 state machine analysis8Current Output=G( )Q（Qk, Q1）Q*（Q*k, Q*1）Next Output = G (Q*, I*)I（Ik, I1）I*（Ik, I1）Q*=T ( )T输出逻辑output equation Excitation/input=下一状态逻辑转移方程transition equationF (Q, I) predic

5、tioncurrent state, inputs9Clocked Synchronous State Machine AnalysisDerive excitation equation from circuit diagram F (Q, I) Derive output equation from the circuit diagram Y=G (Q, I)Determine transition equation Q*=T (F (Q, I)7.3.4 state machine analysisCombinationalCombinationalSequentialConstruct

6、 transition/output tableDraw state （transition）diagramDraw timing diagram (optional) 10ENENQ0Q0Q1Q1ENMAXQ0Q1CLKD0D1Mealy machineMoore machineMAXSExample state machineFig. 7-38Example state machine analysisDrive excitation equation11Drive transition equationDrive output equationD0=Q0 EN+Q0 END1=Q1 EN

7、+Q1 Q0 EN+ Q1 Q0 EN (1)Q0*=D0Q1*=D1 (2)Substitute (1) into (2)Q0*= Q0 EN+Q0ENQ1*= Q1 EN+Q1 Q0 EN+ Q1 Q0 ENMAX=Q1 Q0 EN (3)MAX=.Example state machine analysisConstruct state /output table120 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1MAX000111100000000101100110Q0*= Q0 EN+Q0ENQ1*= Q1 EN+Q1 Q0 EN+ Q1 Q0 ENC

8、onstruct transition state /output tableQ1Q0=00,01,10,11 S=A, B, C, DExample state machine analysisDraw state （transition）diagram130001EN=11011Q1Q0=00,01,10,11 S=A, B, C, DEN=1MAX=0EN=0MAX=0EN=0MAX=0EN=1MAX=0MAX=0EN=1MAX=1EN=0MAX=0EN=0MAX=0ABCD0/01/01/01/01/10/00/00/0Mealymachine14ENENQ0Q0Q1Q1ENMAXQ0

9、Q1CLKD0D1Moore machineMAXSExample state machineFig. 7-3815MAXS= Q1 Q0Q0*= Q0 EN+Q0ENQ1*= Q1 EN+Q1 Q0 EN+ Q1 Q0 EN0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1MAXs000111100000001101100110Example state machine analysisQ1Q0=00,01,10,11 S=A, B, C, DMaxs=0, 0, 0, 1 一一对应16AMAXS=0BMAXS=0CMAXS=0DMAXS=101111000Ex

10、ample state machine analysisMooremachinenodenodeTransition expressionoutputFrom Current Input and state, predict the current output and next state. MooremachinePrepared by Jin17MooremachineMealymachineMAXMAXS7.3.4 state machine analysis18Outputs of Moore machine only changes shortly after the trigge

11、r moment . The change of current inputs will not be seen until the next clock trigger moment.Outputs of Mealy machine changes with current input, et. It may change at any moment in a clock period.Respond earlier than Moore machineAlert to noise than Moore machineA Mealy machine has equivalent Moore

12、machine model.19Y = X Q2 Q1 J1 = (X Q2)K1 = (X Q2) J2 = X Q1K2 = (X Q1)1. Derive excitation equations from the circuit diagram2. Derive output equationCPXYJ QCLK K Q&J QCLK K Q&FF1FF2= X+Q2Example : State Machine Analysis (J-K flip-flop)203. Write transition equation characteristic equation: Q* = JQ

13、 + KQ Q1* = J1 Q1 + K1 Q1= (X+Q2) Q1 + X Q2 Q1= Q2Q1 + XQ1 + XQ2Q1 = X Q1 Q2 + X Q1 Q2 Q2* = J2 Q2 + K2 Q2Y = X Q2 Q1 J1 = (X Q2)K1 = (X Q2) J2 = X Q1K2 = (X Q1)1. Derive excitation equations from the circuit diagram2. Derive output equation= X+Q2214. List transition/output table Q1* = Q2Q1 + XQ1 +

14、XQ2Q1 Q2* = X Q1 Q2 + X Q1 Q2 Y = X Q2 Q1001011100110000000000001transition/output truth table X Q2 Q1 Q2* Q1* Y0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1S0 00 11 01 1X0 100, 010, 011, 000, 001, 001, 001, 000, 1Q2*Q1*, YQ2Q1X Q2 Q1 + X Q2 Q1 22S0 00 11 01 1X0 100, 010, 011, 000, 001, 001, 001, 000, 1Q

15、2*Q1*, YQ2Q1001/0 0/0 当X连续出现1001时Y输出1 1001序列检测器5. Draw state diagram011/01/0100/0110/00/0 1/1X/YX: 0100100111001100100Y: 000010000000100010023Exercise: State Machine Analysis11、24Exercise 11 2 3Y = Q2 Q3 J1 = (Q2 Q3)K1 = 1 J2 = Q1K2 = (Q1 Q3) J3 = Q1 Q2K3 = Q21. Derive excitation equations from the

16、circuit diagram2. Derive output equation from the circuit diagram25Y = Q2 Q3 J1 = (Q2 Q3)K1 = 1 J2 = Q1K2 = (Q1 Q3) J3 = Q1 Q2K3 = Q21. Derive excitation equations from the circuit diagram2. Derive output equation from the circuit diagram3. Write transition/output equations characteristic equation:

17、Q* = JQ + KQ Q1* = J1 Q1 + K1 Q1 Q2* = J2 Q2 + K2 Q2 Q3* = J3 Q3 + K3 Q3= (Q2 Q3) Q1 = Q1 Q2 + Q1 Q3 Q2 = Q1 Q2 Q3 + Q2 Q3 2600011100000000114. List state transition/output tableQ1* = (Q2 Q3) Q1 Q2* = Q1 Q2 + Q1 Q3 Q2 Q3* = Q1 Q2 Q3 + Q2 Q3 Y = Q2 Q3Q1* = Q3 Q1 + Q2 Q1 Q2* = Q2 Q1 + Q3 Q2 Q1 Q3* = Q

18、3 Q2 Q1 + Q3 Q2Y = Q3 Q20 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1Y0110100010101000274. List state transition/output table5. Draw state diagram000/0Q3Q2Q1/Y010/0011/0100/0101/0110/1001/0111/1能自启动的模7 加法计数器，对时钟信号计数，输出为进位脉冲 自启动的 00011100000000110 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1Y0110100010101000286. Draw timing diagram (optional ) 注意是主从J-K触发器 Exercise: State Machine Analysis1. Derive excitation equations from the circuit diagram2. Derive output equation from the circuit diagram303. Write transition/output equatio