数字设计课件 第七章 时序逻辑设计原理

1、ddpp Chapter 7 sequential logic design principles state, state variable latches, flip-flops analysis synthesis sequential circuit Combinational Logic Storage Elements InputsOutputs State Next State the outputs depend not only on its current inputs, but also on the past sequence of time, possibly arb

2、itrarily far back in time. Some important concepts state and state variable state : collection of state variable, contain all the information about the past necessary to account for the circuits future behavior. state variable: the symbol representation of state. finite-state machine the states of a

3、 sequential circuit is always finite. n state variables 2n possible states Some important concepts clock a clock signal is a signal used to coordinate the actions of two or more sequential units. clocked synchronous state machine all memory of the sequential circuit changes only on a clock edge or s

4、ignal level. coordinate by signal level H L coordinate by signal rising edge or falling edge 7.1 Bistable Element Output variable：Q，Q_L，且Q_L=Q Two stable state: Q=0、Q_L=1 Q=1、Q_L=0 feedback 1 2 Q is the state variable analysis with transfer characteristic VOUT=T(VIN) VO1=VI2 VI1=VO2 stable metasta b

5、le stable INV1 INV2 VINVOUT 7.2 Latches and Flip_Flops basic building block be classified as S-R、D、T、J-K types definition: latch：watches the circuits inputs continuously and can changes the outputs at any time. flip-flops：samples the circuits inputs and changes the output only when a clocking signal

6、 is changing. 1、SR Latches S-R latch built with NOR gates Q=QN=Q_L hold reset set forbidden 1 2 the stored bit is present on the output Q. SRQQ_L 00Last QlastQ_L 0101 1010 1100 S and R : active high signal Function table 进入亚进入亚 稳态稳态 (2) symbol and characteristic equation S R Q Q QSRQ* 0000 0010 0101

7、 011d 1001 1010 1101 111d S=R=1, restricted combination characteristic equation for S-R latch: Q*=S+RQ （SR=0） current state next state (3) minimum pulse width the time of active level of S or R must be keeping longer than minimum pulse width, or else the latch may be go into metastable. propagation

8、delay is exist when a transition on S or R input produce a transition on an output signal. S 2、S-R latch built with NAND gates S_LR_LQQ_L 0011 0110 1001 11 Last Q lastQ _L S_L 、R_L: active low signals S_L R_LQ_L QS R Q Q hold reset set forbidden 3、S-R latch with enable S C RQ Q metastable still exis

9、t forbidden 4、D latch 保持保持 R S characteristic equation Q*=D （C=1） transfer data transparently D C Q Q when C=0，the data is latched on Q . timing diagram data transfered data latched if D changes during the thold and tsetup, the output may become metastable. 5、Edge-Triggered D Flip-Flops Edge-Trigger

10、ed ：output of flip-flop changes on the clock signals rising edge or falling edge. positive edge （rising edge） negative edge （falling edge） CLOCK positive-edge-triggered D flip-flop master-slave structure a) CLK=0，QM=D，US hold last Q； b) At the clocks rising edge, US enable， UM hold last QM，Q=QM； c)

11、CLK=1， UM hold last QM，so Q hold last Q。 UM US Only at the rising edge of clock signal, D input could be transferred to Q output. Dynamic-input indicator, meaning edge-triggered. Others D CLK Q Q CLR PR PR_L: preset CLR: clear Negative-edge- triggered D flip- flop edge-triggered D flip-flop with asy

12、nchronous inputs Asynchronous inputs: force the output to go into a certain state with ignoring the triggering edge of clock. 6、edge-triggered D flop-flop with enable characteristic equation ： Q*=END+ENQ D EN CLKQQ_L 0101 1110 0last Q last Q_L 0last Q last Q_L 1last Q last Q_L frequency divider with

13、 D f-fs input (frequency, fin) output (frequency, fout) divide-by-2 divider DQ QCLK 2 in out f f 7、scan flip-flop TE=1，test operation mode，f-fs take TI data. TE=0，normal D f-f-s，take D data. D CLK Q Q TI TE Normal input Test enable Test input 8、master/slave S-R触发器 Q*=S+RQ （SR=0） C=1, master latch fo

14、llows the S-R input; C goes to 0, Q output the final latched value of master latch. It is not edge-triggered f-fs, but pulse- triggered. S C R Q Q S C R Q QS R C Q Q_L QM QM_L MasterSlave S C R Q Q C S R QM QM_L Q Q_L Timing diagram of S-R f-fs 9. master/slave J-K flip-flop stucture J K C Q Q_L feed

15、back S C R Q QS C R Q Q QM QM_L SM RM C=1，master latch follow the input; C goes to 0, Q output (slave latch) the final latch value. MasterSlave JK flip-flop timing diagram S C R Q Q S C R Q Q QM QM_L SM RM J K C Q Q_L features JKCQQ_L 0 last Qlast Q_L 00 last Qlast Q_L 0101 1010 11 last Q_Llast Q re

16、set set toggle hold Pulse-triggered f-f-s J C K Q Q Characteristic equations ： Q*=JQ+KQ Eliminate the possible metastable which exist in the S-R f-fs (restricted input, S=R=1). But, 1s catching and 0s catching are exist. hold 1s catching C=1，当上次Q=0，当前JK=0时，若J有 1的出现，触发器会捕捉到这一变化，置 Q=1。以后，J有1到0的变化，电路不会

17、响 应。 0s catching 当上次Q=1，当前JK=0时，若K有1的出 现，触发器会捕捉到这一变化，置Q=0。以 后，K有1到0的变化，电路不会响应。 10、Edge-triggered J-K Flip-Flop sample the inputs and change the output state at the edge of clock。 characteristic equations： Q*=JQ+KQ eliminate the “1s catching” and “0s catching”. J CLK K Q Q J CLK K Q Q 11、T Flip-Flop

18、T: toggle functional table CLKTQQ* 101 110 0 保持保持 symbol T Q QCLK characteristic equation： Q*=TQ+TQ Implementation Contribute by D or J-K f-fs. J CLK K Q Q CLK Q_L Q T Q_L CLK QD CLK Q Q T T Flip-Flop with enable EN=1，normal T flip-flop; EN=0，hold the last value EN Q Q T CLK summary : latches and fl

19、ip-flops label by structure： latches：S-R、D latches flip-flops：S-R、D、J-K、T flip-flops label by triggering form：pulse-triggered、 edge-triggered one latch or flip-flop is a storage elements, which can store one bit (0 or 1). it also act as a state variable, and more storage elements can be combined to

20、store more bits which used to memory states in sequential circuit. summary : characteristic equation S-R latch D latch D flip-flop D flip-flop with enable M/S S-R flip-flop M/S J-K flip-flop edge-triggered J-K flip- flop T flip-flop Q*=S+RQ （SR=0） Q*=D Q*=D Q*=END+ENQ Q*=S+RQ （SR=0） Q*=JQ+KQ Q*=JQ+K

21、Q Q*=TQ+TQ 7.3 clocked synchronous state- machine analysis emphases： Basic structureMealy machine and Moore machine. understand action of each module and their equations, tables. analysis with D f-fs 1、stucture （1）Mealy machine Next- state logic F state memory clock Output logic G inputs excitation

22、Current state outputs Clock signal construct by analog circuit, the output signal is the excitation input of storage element. next state= F(current state,input) construct by flip- flops, can store 2n state at most construct by analog circuit, output= G(current state, input) 返回 （2）Moore machine Next-

23、 state logic F state memory clock Output logic G PS: output=G (current state) inputs Clock signal excitation Current state outputs 2.analysis example state variable： Q0、Q1 excitation： D0、D1 output： MAX D0=F（EN，Q1，Q0） =(ENQ0)+(ENQ0) =ENQ0+ENQO D1=F（EN，Q1，Q0） =ENQ1+ENQ1Q0 +ENQ1Q0 excitation equation C

24、haracteristic equation of D f-fs： Q*=D Transition equation： Q1*=D1 = ENQ1+ENQ1Q0+ENQ1Q0 Q0*=D0 = ENQ0+ENQO transition equation Transition table and state table Q1Q0 EN 01 000001 010110 101011 111100 Q1*Q0* Transition equation ： Q1*= ENQ1+ENQ1Q0+ENQ1Q0 Q0*= ENQ0+ENQO Current state S EN 01 AAB BBC CCD

25、 DDA S* Transition table State table Assign state name to each state: Q1Q0 S 00 A 01 B 10 C 11 D Current state input Next state MAX=ENQ1Q0 Output equation EN MAX Q1Q0 EN 01 0000，001，0 0101，010，0 1010，011，0 1111，000，1 Q1*Q0*，MAX SEN 01 AA，0B，0 BB，0C，0 CC，0D，0 DD，0A，1 S*，MAX Transition/output tablesta

26、te/output table Transition/output table, state/output table A DC B S EN 01 AA，0B，0 BB，0C，0 CC，0D，0 DD，0A，1 S*，MAX EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=1 Show the transition direction of current state State diagram Q1Q0 State variable combination can b

27、e write in the circle directly. 00 1110 01 EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=0 EN=0 MAX=0 EN=1 MAX=1 注意：有限状态机的时序分析必须以时钟周期为单注意：有限状态机的时序分析必须以时钟周期为单 位依序进行。位依序进行。 Timing diagram Analysis of Moore maching excitation equation and transition equation are changeless MAXS=Q1Q0 Q

28、1Q0 ENMAXS 01 0000010 0101100 1010110 1111001 Q1*Q0* （次态）（次态） S ENMAXS 01 AAB0 BBC0 CCD0 DDA1 S* transition table independent of input values state table A MAXS=0 D MAXS=1 C MAXS=0 B MAXS=0 EN=0 EN=1 EN=0 EN=1 EN=0 EN=1 EN=0 EN=1 show output value inside the circle state diagram 例1、2的时序对比分析 state tr

29、ansition feature transition expression on arcs leaving a particular state must be mutually exclusive and all inclusive. No two transition expressions can equal 1 for the same input combination; For every possible input combination, some transition expression must equal 1. S1 I1 Si S1 Sn Ii In transi

30、tion expression 3、analysis with J-K flip-flops (1) excitation equation： J0=K0=1 J1=K1=X Q0 (2) transition equation: Q0*=J0Q0+K0Q0=Q0 Q1*=J1Q1+K1Q1 =X Q0 Q1 CP 1 X J0 K0 J1 K1 Q0 Q1 Z J CLK K Q Q J CLK K Q Q (3) output equation：Z=Q0Q1 XZ Q1Q001 0001110 0110000 1011010 1100101 Q1*Q0* (4) transition/ou

31、tput table and state/output table XZ S01 ABD0 BCA0 CDB0 DAC1 S* assign state name： Q1Q0 S 00 A 01 B 10 C 11 D A Z=0 D Z=1 C Z=0 B Z=0 X=1 X=0 X X X X X X state diagram CP timing diagram X Q1 Q0 Z Exp3：analyze the following circuit T Q Q CLK X CLK Z (1) excitation equation： T1=X T2=XQ1 T1T2 Q1 Q2 (2)

32、 transition equation： Q1*=T1Q1+T1Q1= XQ1+XQ1 Q2*= T2Q2+T2Q2= XQ1Q1+（XQ1）Q1 (3) output equation： Z=XQ1Q2 T Q Q CLK 7.4 同步时序状态机的设计 提取输入提取输入/输出变量、状态，构造状态输出变量、状态，构造状态/输出表输出表 最小化状态的个数（可选）最小化状态的个数（可选） 状态赋值状态赋值 建立转移建立转移/输出表输出表 选择一种触发器选择一种触发器 构造激励表构造激励表 由激励表导出激励方程由激励表导出激励方程 由转移由转移/输出表推导出输出方程输出表推导出输出方程 画出逻辑电

33、路图画出逻辑电路图 Exp1: sequence-detector design Design a “110” sequence-detector. when serial input binary number include continuous “110” sequence, the circuit output 1. synthsis by D flip-flops. that is input P： output C： solution 1：Moore machine （1）input and output variable input：P（每次给电路送一个二进制数码） output

34、：C（表明检测的结果，1位） state： 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 first input Exp1: sequence-detector design 定义状态： S0收到的是0 S1收到的是1 S2收到连续的11 S3收到连续的110 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 P： C： 目标：检测目标：检测110 S P C 01 S0S0S10 S1S0S20 S2S3S20 S3S0S11 S* state/output table （2）最小

35、化状态的个数 （3）状态的分配（状态的赋值） n个状态变量 2n个状态。 S个状态需（？）个状态变量（触发器）来表 达 需要触发器：m=2，令为Q0、Q1 分配状态变量组合给已命名的状态： S：S0 S1 S2 S3 Q1Q0：00 01 10 11 2 logmS （4）建立转移/输出 表 用已赋值的状态变量 代替状态/输出表中 的状态名 Q1Q 0 P C 01 0000010 0100100 1011100 1100011 Q1*Q0* S0 S1 S2 S3 （5）选择触发器并构建激励表（用于 建立次态逻辑电路） 此处选择D触发器 Q1Q0 P C 01 0000010 0100100

36、 1011100 1100011 D1D0 QQ* D 000 011 100 111 QDQ* 000 011 100 111 功能表功能表 应用表应用表 激励表激励表 应用方程：应用方程： D=Q* 代入转移代入转移/输出表输出表 （6）导出激励方程：由激励表，以Di的值作为 输出，Q1、Q0、P的值作为输入，建立卡诺 图，推导激励方程。 1010 1000 P Q1Q0 Q1 Q0 D1 0101 1000 P Q1Q0 Q1 Q0 D0 D1=Q1Q0+Q1Q0P D0=Q1Q0P+Q1Q0P+Q1Q0P （7）导出输出方程 从转移/输出表得 C=Q1Q0 Q1Q0 P C 01 00

37、00010 0100100 1011100 1100011 Q1*Q0* 思考：若状态赋值时，采用思考：若状态赋值时，采用gray码顺序给各状态赋值，码顺序给各状态赋值， 则电路是怎样的？则电路是怎样的？ 解（二）：建立Mealy型 的同步时序状态机 （1）定义状态 S0收到的是0，C=0 S1收到的是1，C=0 S2收到连续的11 ， C=0 S3收到连续的110， C=1 （2）建立状态/输出表 S P 01 S0S0，0S1，0 S1S0，0S2，0 S2S3，1S2，0 S3S0，0S1，0 S*，C （3）最小化状态个 数 S0和S3是等价状态， 消去S3，得简化的 状态/输出表 S

38、 P 01 S0S0，0S1，0 S1S0，0S2，0 S2S3，1S2，0 S3S0，0S1，0 S*，C S0 （4）状态的赋值 所需触发器个数： 命名Q1、Q0 Q1Q0=00，01，10，11 S=S0，S1，S2 任选其中3个分配给已知状态。 如， S0 00，S1 01，S2 11 Q1Q0=10，是未用状态 2 log 32m Q1Q0 P 01 0000，001，0 0100，011，0 1100，111，0 10 ？ Q1*Q0*，C 建立转移建立转移/输出表输出表 对未用状态的处理 Q1Q0 P 01 0000，001，0 0100，011，0 1100，111，0 100

39、0，000，0 Q1*Q0*，C Q1Q0 P 01 0000，001，0 0100，011，0 1100，111，0 10dd，ddd，d Q1*Q0*，C 最小风险法最小风险法 最小成本法最小成本法 （5）选触发器并导出激励表 按最小成本法处理，触发器选用J-K触发器， QQ*J K 000 d 011 d 10d 1 11d 0 J-K触发器的应触发器的应 用表用表 Q1Q0 P 01 000d,0d,00d,1d,0 010d,d1,01d,d0,0 11d1,d1,1d0,d0,0 10dd,dd,ddd,dd,d J1K1,J0K0,C 激励表激励表 （6）导出激励方程 J1=PQ

40、0 K1=P J0=P K0=P （7）导出输出方程 C=Q1P 课堂练习 试写出如下电路的激励方程和转移方程。 U1A 74LS74D 1D 2 1Q 5 1Q 6 1CLR 1 1CLK 3 1PR 4 U2B 74LS74D 1D 2 1Q 5 1Q 6 1CLR 1 1CLK 3 1PR 4U3A 74LS08D U4B 74LS08D U5A 74LS32D U6B 74LS32D U7A 74LS386D U8B 74LS386D Q1 Q0 Y X D0 D1 CLK D1=X Q0 Q1 D0=XQ0+Q1 Q1*=D1 Q0*=D0 Y=X+Q1Q0 时钟同步状态机设计状态表

41、设计 设计问题： 设计一个具有2个输入（A和B）1个输出（Z）的时钟同步 状态机，Z为1的条件是： 在前2个脉冲触发沿上，A的值相同；或者 从上一次第1个条件为真起，B的值一直为1。 否则，输出为0。 （原文： Design a machine inputs A and B with output Z that is 1 if: A had the same value at the two previous ticks B has been 1 since the last time the above was true ） 1、确定电路可能有的状态 l 电路开始工作，设置INIT状态，Z=

42、0 l 状态A0，A收到一个0，Z=0 l 状态A1，A收到一个1，Z=0 l 状态OK0，A收到连续的两个0，Z=1 l 状态OK1，A收到连续的两个1，Z=1 l 状态A001，A收到连续的两个0后，收到1，同时B=1， Z=1 l 状态A110，A收到连续的两个1后，收到0，同时B=1， Z=1 l 状态AE10，A已经收到过连续的00或11，收到连续的10， 同时B=1，Z=1 l 状态AE01，A已经收到过连续的00或11，收到连续的01， 同时B=1，Z=1 电路开始工作，设置INIT状态， Z=0 l 状态A0，A收到第一个0，Z=0 l 状态A1，A收到第一个1，Z=0 l 状

43、态OK0，A收到连续的两个0， Z=1 l 状态OK1，A收到连续的两个1， Z=1 l 状态A001，A收到连续的两个0 后，收到1，同时B=1，Z=1 l 状态A110，A收到连续的两个1 后，收到0，同时B=1，Z=1 l 状态AE10，A已经收到过连续 的00或11，收到连续的10，同 时B=1，Z=1 l 状态AE01，A已经收到过连续 的00或11，收到连续的01，同 时B=1，Z=1 S A B Z 00011110 INITA0A0A1A10 A0OK0OK0A1A10 A1A0A0OK1OK10 OK0OK0OK0A001A11 OK1A0A110OK1OK11 A001A0

44、AE10OK1OK11 A110OK0OK0AE01A11 AE10OK0OK0AE01A11 AE01A0AE10OK1OK11 S* S A B Z 00011110 INITA0A0A1A10 A0OK0OK0A1A10 A1A0A0OK1OK10 OK0OK0OK0A001A11 OK1A0A110OK1OK11 A001A0AE10OK1OK11 A110OK0OK0AE01A11 AE10OK0OK0AE01A11 AE01A0AE10OK1OK11 S* 等价状态，消去等价状态，消去AE10 等价状态，消去等价状态，消去AE01 S A B Z 00011110 INITA0A0

45、A1A10 A0OK0OK0A1A10 A1A0A0OK1OK10 OK0OK0OK0A001A11 OK1A0A110OK1OK11 A001A0A110OK1OK11 A110OK0OK0A001A11 S* 等价状态，消去等价状态，消去A001 等价状态，消去等价状态，消去A110 S A B Z 00011110 INI T A0A0A1A10 A0OK 0 OK 0 A1A10 A1A0A0OK 1 OK 1 0 OK 0 OK 0 OK 0 OK 1 A11 OK 1 A0OK 0 OK 1 OK 1 1 S* 最小化状态个数的状态表最小化状态个数的状态表 状态赋值：将一个特定的二

46、进制组合赋给一个已定义的状态。 需要的触发器个数（状态变量）： 得 m=3，可提供8个二进制组合（状态编码） 从8种编码中选择5个，有 种方法， 将5个编码赋给5个状态有5！种方式，一共6720种。 依赖经验和实践指南完成状态的赋值。 2 logmS ! ! ()! n mn m 建立转移/输出表、激励表，选定D触发器， 导出激励方程、输出方程 Q1Q2Q3 A B Z 00011110 0001001001011010 1001101101011010 1011001001111110 1101101101111011 1111001101111111 D1*D2*D3* Q1Q2Q3 A

47、B Z 00011110 0001001001011010 1001101101011010 1011001001111110 1101101101111011 1111001101111111 Q1*Q2*Q3* 建立转移/输出表、激励表， 导出激励方程、输出方程 Q1Q2Q3 A B Z 00011110 0001001001011010 001 010 011 1001101101011010 1011001001111110 1101101101111011 1111001101111111 D1*D2*D3* 对未用状态的处理对未用状态的处理：（：（p.414） l最小风险法：给未用

48、状态的次最小风险法：给未用状态的次 态定义一个明确的已用状态。态定义一个明确的已用状态。 l最小成本法：假设电路正常工最小成本法：假设电路正常工 作，不会进入未用状态，忽略未作，不会进入未用状态，忽略未 用状态的次态，视为用状态的次态，视为“无关项无关项”。 ？ Q1Q2Q3 A B Z 00011110 0001001001011010 0010 0100 0110 1001101101011010 1011001001111110 1101101101111011 1111001101111111 D1*D2*D3* 0000 1111 00 01 11 10 D1 0000 0000 A

49、B Q2Q3 00 01 11 10 Q1=0 D1 1111 1111 000111 101111 1111 AB Q2Q3 00 01 11 10 Q1=1 最小风险最小风险 D1=Q1+Q2Q3 Q1Q2Q3 A B Z 00011110 0001001001011010 001d 010d 011d 1001101101011010 1011001001111110 1101101101111011 1111001101111111 D1*D2*D3* dddd 1111 00 01 11 10 D1 dddd dddd AB Q2Q3 00 01 11 10 Q1=0 D1 1111

50、 1111 000111 101111 1111 AB Q2Q3 00 01 11 10 Q1=1 最小成本最小成本 D1=1 注： l 采用最小风险法，除了未用状态的次态被赋予已定义的状 态，对应于未用状态的输出函数值也应该置为0。 l 采用最小成本法，未用状态的次态和输出函数值都是无关 项。 l 上例的输出函数： 最小风险法：Z=Q1Q2 最小成本法：Z=Q2 最小成本法的逻辑电路最小成本法的逻辑电路 最小风险法的逻辑电路最小风险法的逻辑电路 选用J-K触发器进行综合（自学） 例2、1计数器 要求：设计一个有2个输入（X和Y）以及1个输出Z的同步时 序状态机，复位后，当X和Y输入1的个数为

51、4的整数倍时， 输出为1，否则输出为0。 （design a clocked synchronous state-machine with two inputs X and Y, and one output Z, the output should be 1 if the number of 1 inputs on X and Y since reset is a multiple of 4, and 0 otherwise.） X01001110010 Y00110011001 Z11 定义状态： 每个状态要同时记录X和Y输入1的个数，定义： S0 复位后，X和Y输入的1的个数是0 S1

52、复位后，X和Y输入的1的个数是1 S2 复位后，X和Y输入的1的个数是2 S3 复位后，X和Y输入的1的个数是3 S4 复位后，X和Y输入的1的个数是4 只要记录X和Y输入的1的个数N模4的结果即可。 N MOD 4 =0， Z=1 S0 N MOD 4 =1， Z=0 S1 N MOD 4 =2， Z=0 S2 N MOD 4 =3， Z=0 S3 S XY Z 00011110 S0S0S1S2S11 S1S1S2S3S20 S2S2S3S0S30 S3S3S0S1S00 S* 1、状态、状态/输出表：输出表： 2、化简状态的个数：、化简状态的个数： 无等价状态无等价状态 3、状态赋值及建立转、状态赋值及建立转 移移/输出表：输出表： S0 00、S1 01、 S2 11、S3 10 4、由转移、由转移/输出表得输出表得 激励表：激励表： 5、建立激励方程和输、建立激励方程