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

1、ddppchapter 7sequential logic design principlesstate, state variablelatches, flip-flopsanalysissynthesischapter 7 2sequential circuitcombinationallogicstorage elementsinputsoutputsstatenextstate the outputs depend not only on its current inputs, but also on the past sequence of time, possibly arbitr

2、arily far back in time.chapter 7 3some 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 stat

3、es of a sequential circuit is always finite. n state variables2n possible stateschapter 7 4some 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

4、 clock edge or signal level.coordinate by signal levelhlcoordinate by signal rising edge or falling edgechapter 7 57.1 bistable element output variable：q，q_l，且，且q_l=q two stable state: q=0、q_l=1 q=1、q_l=0feedback12q is the state variablechapter 7 6analysis with transfer characteristicvout=t(vin)vo1=

5、vi2vi1=vo2stablemetastablestableinv1inv2vinvoutchapter 7 7chapter 7 87.2 latches and flip_flopsbasic building blockbe classified as s-r、d、t、j-k typesdefinition: latch：watches the circuits inputs continuously and can changes the outputs at any time. flip-flops：samples the circuits inputs and changes

6、the output only when a clocking signal is changing.chapter 7 91、sr latchess-r latch built with nor gatesq=qn=q_lholdresetsetforbidden12the stored bit is present on the output q.srqq_l00last qlastq_l010110101100s and r : active high signalfunction tablechapter 7 10进入亚进入亚稳态稳态chapter 7 11 (2) minimum p

7、ulse widththe time of active level of s or r must be keeping longer than minimum pulse width, or else the latch may be go into pagation delay is exist when a transition on s or r input produce a transition on an output signal. schapter 7 12(3) symbol and characteristic equationsrqqqsrq

8、*000000100101011d100110101101111ds=r=1, restricted combination characteristic equation for s-r latch:q*=s+rq （sr=0）current statenext statechapter 7 13 2、s-r latch built with nand gatess_lr_lqq_l00110110100111last qlastq_ls_l 、r_l: active low signalss_lr_lq_lqsrqqholdresetsetforbiddenchapter 7 143、s-

9、r latch with enablescrqqmetastable still existforbiddenchapter 7 154、d latch保持保持rscharacteristic equation q*=d （c=1）transfer data transparentlydcqqwhen c=0，the data is latched on q .chapter 7 16timing diagramdata transfereddata latchedif d changes during the thold and tsetup, the output may become m

10、etastable.chapter 7 175、edge-triggered d flip-flops edge-triggered ：output of flip-flop changes on the clock signals rising edge or falling edge.positive edge（rising edge）negative edge（falling edge）clockchapter 7 18positive-edge-triggered d flip-flopmaster-slave structurea) clk=0，qm=d，us hold last q

11、；b) at the clocks rising edge, us enable， um hold last qm，q=qm；c) clk=1， um hold last qm，so q hold last q。umuschapter 7 19 only at the rising edge of clock signal, d input could be transferred to q output.dynamic-input indicator, meaning edge-triggered.chapter 7 20othersdclkqqclrprpr_l: presetclr: c

12、learnegative-edge-triggered d flip-flopedge-triggered d flip-flop with asynchronous inputsasynchronous inputs: force the output to go into a certain state with ignoring the triggering edge of clock.chapter 7 216、edge-triggered d flop-flop with enablecharacteristic equation ：q*=end+enqd01en110clk01q0

13、1last qlast qlast qq_l10last q_llast q_llast q_lchapter 7 22frequency divider with d f-fsinput(frequency, fin)output(frequency, fout)divide-by-2 dividerdqqclk2inoutffchapter 7 237、scan flip-flop te=1，test operation mode，f-fs take ti data. te=0，normal d f-f-s，take d data.dclkqqtitenormal inputtest en

14、abletest inputchapter 7 24chapter 7 258、master/slave s-r触发器触发器 q*=s+rq （sr=0） c=1, master latch follows 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.scrqqscrqqsrcqq_lqmqm_lmasterslavescrqqchapter 7 26csrqmqm_lqq_ltim

15、ing diagram of s-r f-fschapter 7 279. master/slave j-k flip-flop stucturejkcqq_lfeedbackscrqqscrqqqmqm_lsmrmc=1，master latch follow the input;c goes to 0, q output (slave latch) the final latch value.masterslavechapter 7 28jk flip-flop timing diagram s c r q q s c r q q qm qm_l sm rm jkcqq_lcjkqmqm_

16、lqq_lchapter 7 29featuresj0011k0101c0qlast qlast q01last q_lq_llast q_llast q_l10last qresetsettoggleholdpulse-triggered f-f-sjckqqcharacteristic equations ： q*=jq+kqeliminate the possible metastable which exist in the s-r f-fs (restricted input, s=r=1). but, 1s catching and 0s catching are exist.ho

17、ldchapter 7 301s catching c=1，当上次，当上次q=0，当前，当前jk=0时，若时，若j有有1的出的出现，触发器会捕捉到这一变化，置现，触发器会捕捉到这一变化，置q=1。以后，。以后，j有有1到到0的变化，电路不会响应。的变化，电路不会响应。chapter 7 310s catching 当上次当上次q=1，当前，当前jk=0时，若时，若k有有1的出现，触的出现，触发器会捕捉到这一变化，置发器会捕捉到这一变化，置q=0。以后，。以后，k有有1到到0的变化，电路不会响应。的变化，电路不会响应。chapter 7 3210、edge-triggered j-k flip-

18、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”.jclkkqqjclkkqqchapter 7 33timing diagram of edge-triggered j-k f-fschapter 7 3411、t flip-flop t: toggle functional tableclktqq*1011100 保持保持 symbolt

19、qqclkcharacteristic equation：q*=tq+tqchapter 7 35implementation contribute by d or j-k f-fs.jclkkqqclk q_lqtq_lclkqdclkqqtchapter 7 36t flip-flop with enableen=1，normal t flip-flop;en=0，hold the last valueenqqt clk chapter 7 37summary : latches and flip-flops label by structure： latches：s-r、d latche

20、s 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 store more bits which used to memory states in seq

21、uential circuit. chapter 7 38summary : 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-flopq*=s+rq （sr=0）q*=dq*=dq*=end+enqq*=s+rq （sr=0）q*=jq+kqq*=jq+kqq*=tq+tqchapter 7 397.3 clocked synchronous s

22、tate-machine analysisemphases： basic structuremealy machine and moore machine. understand action of each module and their equations, tables. analysis with d f-fschapter 7 401、stucture（1）mealy machinenext-state logicfstate memoryclockoutput logicginputsexcitationcurrent stateoutputsclock signalconstr

23、uct by combinational 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 mostconstruct by combinational circuit, output=g(current state, input)返回chapter 7 41（2）moore machinenext-state logic f state memo

24、ry clockoutput logicgps: output=g (current state)inputsclock signalexcitationcurrent stateoutputschapter 7 422.analysis examplestate variable：q0、q1excitation：d0、d1output：maxchapter 7 43d0=f（en，q1，q0） =(enq0)+(enq0) =enq0+enqod1=f（en，q1，q0） =enq1+enq1q0 +enq1q0excitation equationchapter 7 44character

25、istic equation of d f-fs：q*=dtransition equation：q1*=d1 = enq1+enq1q0+enq1q0q0*=d0 = enq0+enqotransition equationchapter 7 45transition table and state tableq1q000011011en000011011q1*q0*101101100transition equation ：q1*= enq1+enq1q0+enq1q0q0*= enq0+enqocurrent statesabcden0abcds*1bcdatransition tabl

26、estate tableassign state name to each state:q1q0 s 00 a 01 b 10 c 11 dcurrent stateinputnext statechapter 7 46max=enq1q0output equationenmaxchapter 7 47q1q000011011en000，001，010，011，0q1*q0*，max101，010，011，000，1sabcden0a，0b，0c，0d，0s*，max1b，0c，0d，0a，1transition/output tablestate/output tabletransition

27、/output table, state/output tablechapter 7 48adcbsabcden0a，0b，0c，0d，0s*，max1b，0c，0d，0a，1en=0max=0en=1max=0en=0max=0en=1max=0en=0max=0en=1max=0en=0max=0en=1max=1show the transition direction of current statestate diagramchapter 7 49q1q0state variable combination can be write in the circle directly.00

28、111001en=0max=0en=1max=0en=0max=0en=1max=0en=0max=0en=1max=0en=0max=0en=1max=1chapter 7 50注意：有限状态机的时序分析必须以时钟周期为单注意：有限状态机的时序分析必须以时钟周期为单位依序进行。位依序进行。timing diagramchapter 7 51analysis of moore machingexcitation equation and transition equation are changelessmaxs=q1q0chapter 7 52q1q000011011en000011011q

29、1*q0*（次态）（次态）101101100maxs0001sabcden0abcds*1bcdamaxs0001transition tableindependent of input valuesstate tablechapter 7 53amaxs=0dmaxs=1c maxs=0bmaxs=0en=0en=1en=0en=1en=0en=1en=0en=1show output value inside the circlestate diagramchapter 7 54例例1、2的时序对比分析的时序对比分析chapter 7 55state transition featuret

30、ransition 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.s1i1 sis1snii in transition expressionchapter

31、7 563、analysis with j-k flip-flops(1) excitation equation：j0=k0=1j1=k1=x q0(2) transition equation:q0*=j0q0+k0q0=q0q1*=j1q1+k1q1 =x q0 q1cp1xj0k0j1k1q0q1zjclkkqqjclkkqqchapter 7 57(3) output equation：z=q0q1q1q000011011x001101100q1*q0*111000110z0001(4) transition/output table and state/output tablesa

32、bcdx0bcdas*1dabcz0001assign state name：q1q0 s 00 a 01 b 10 c 11 dchapter 7 58az=0dz=1c z=0bz=0x=1x=0xxxxxxstate diagram chapter 7 59cptiming diagramxq1q0zchapter 7 60 exp3：analyze the following circuittqqclk xclkz(1) excitation equation：t1=xt2=xq1t1t2q1q2(2) transition equation：q1*=t1q1+t1q1= xq1+xq

33、1q2*= t2q2+t2q2= xq1q1+（xq1）q1(3) output equation：z=xq1q2tqqclk chapter 7 617.4 clocked synchronous state-machine designconstruct state/output tablestate minimization（可选）（可选）state assignmentconstruct transition/output tablechoose flip-flopsconstruct excitation tablederiving excitation equationderivi

34、ng output equationdrawing logic circuit diagramchapter 7 62exp1: sequence-detector designdesign a “110” sequence-detector. if the serial input binary number include continuous “110” sequence, the circuit output 1. synthesis by d flip-flops. that is input p：output c：solution 1：moore machine（1）input a

35、nd output variable input：p（每次给电路送一个二进制数码）（每次给电路送一个二进制数码） output：c（表明检测的结果，（表明检测的结果，1位）位） 0 1 1 0 0 1 0 1 1 1 0 1 00 0 0 1 0 0 0 0 0 0 1 0 0first inputchapter 7 63state analysis of exp.10 1 1 0 0 1 0 1 1 1 0 1 00 0 0 1 0 0 0 0 0 0 1 0 0p：c：目标：检测目标：检测110if the previous one input bit is 0, then memory

36、as a state, s0input 0input 1if the previous one input bit is 0, then memory as a state, s1if the previous one input bit is 1, then memory as a state, s2if the previous two input bit is 01, also memory as state s0if the previous two input bit is 1, then memory as a state, s3if the previous two input

37、bit is 1, also memory as state s2chapter 7 64exp1: sequence-detector design defining state： s0 received a single 0 s1 received a single 1 s2 received a continuous “11” s3received a continuous “110”ss0s1s2s3p0s0s0s3s0s*1s1s2s2s1c0001state/output tablechapter 7 65（2）state minimization（3）state assignme

38、nt（状态的分配、赋值）（状态的分配、赋值） n state variables 2n states。then, s states need (?) state variables (flip-flops) to represent. the number of f-fs：m=2，named q0、q1 assign state variable combinations to each symbol state： s： s0 s1 s2 s3 q1q0：00 01 10 112logmschapter 7 66use state combinations to substitute the

39、symbol state.q1q000011011p000001100q1*q0*101101001c0001(4) construct transition/output tables0s1s2s3chapter 7 67(5) construct excitation table choose flip-flops and use application equation to construct excitation table.q1q000011011p000001100d1d0101101001c0001q0011q* 0101d0101q0011d0101q*0101functio

40、n function table of table of d f-f-sd f-f-sapplication application tabletableexcitation excitation tabletableapplication equation：d=q*chapter 7 6810101000pq1q0q1 q0d101011000pq1q0q1 q0d0d1=q1q0+q1q0pd0=q1q0p+q1q0p+q1q0p(6) derive the excitation equationschapter 7 69c=q1q0q1q000011011p000001100q1*q0*

41、101101001c0001(7) derive the output equation思考：若状态赋值时，采用思考：若状态赋值时，采用gray码顺序给各状态赋值，则码顺序给各状态赋值，则电路是怎样的？电路是怎样的？chapter 7 70（1）defining statess0receive a single 0，c=0s1receive a single 1，c=0s2receive continuous “11”，c=0s3receive continuous “110”，c=1ss0s1s2s3p0s0，0s0，0s3，1s0，0s*，c1s1，0s2，0s2，0s1，0solutio

42、n 2 : use mealy machine(2) construct state/output tablechapter 7 71 s0 and s3 are equivalent states，so eliminate s3, and get the minimized state/output table.ss0s1s2s3p0s0，0s0，0s3，1s0，0s*，c1s1，0s2，0s2，0s1，0s0(3) state minimizationchapter 7 72 number of f-fs：named q1、q0q1q0=00，01，10，11 choose 3 to as

43、sign to the 3 known states。like，s0 00，s1 01，s2 11q1q0=10，unused state.2log 32mq1q000011110p000，000，000，1？q1*q0*，c101，011，011，0？transition/output table(4) state assignmentchapter 7 73q1q000011110p000，000，000，100，0q1*q0*，c101，011，011，000，0q1q000011110p000，000，000，1dd，dq1*q0*，c101，011，011，0dd，dminimal

44、riskminimal riskminimal costminimal costdisposition of unused stateschapter 7 74(5) construct excitation table use d f-fs and in minimal cost disposition.q1q000011110p000,000,000,1dd,dd1d0,c101,011,011,0dd,dexcitation excitation tabletableapplication equation：d=q*chapter 7 75(6) derive the excitatio

45、n equations and output equation d1=q0p d0=p c=q1pchapter 7 76another way: synthesis using j-k f-fsq0011q*0101j01ddkdd10application table application table of j-k f-fsof j-k f-fsq1q000011110p00d,0d,00d,d1,0d1,d1,1dd,dd,dj1k1,j0k0,c10d,1d,01d,d0,0d0,d0,0dd,dd,dexcitation tableminimal cost minimal cost

46、 dispositiondispositionchapter 7 77 excitation equations j1=pq0 k1=p j0=p k0=p output equation c=q1pexcitation equations and output equationchapter 7 78课堂练习课堂练习 试写出如下电路的激励方程和转移方程。试写出如下电路的激励方程和转移方程。u1a74ls74d1d21q5 1q61clr11clk31pr4u2b74ls74d1d21q51q61clr11clk31pr4u3a74ls08du4b74ls08du5a74ls32du6b74l

47、s32du7a74ls386du8b74ls386dq1q0yxd0d1clkd1=x q0 q1d0=xq0+q1q1*=d1q0*=d0y=x+q1q0chapter 7 79design examples in book exp1: 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 ）clkabzchapter 7 80 a

48、t the beginning, set state init，z=0 状态状态a0，a收到一个收到一个0，z=0 状态状态a1，a收到一个收到一个1，z=0 状态状态ok0，a收到连续的两个收到连续的两个0，z=1 状态状态ok1，a收到连续的两个收到连续的两个1，z=1 状态状态a001，a收到连续的两个收到连续的两个0后，收到后，收到1，同时，同时b=1，z=1 状态状态a110，a收到连续的两个收到连续的两个1后，收到后，收到0，同时，同时b=1，z=1 状态状态ae10，a已经收到过连续的已经收到过连续的00或或11，收到连续的，收到连续的10，同时同时b=1，z=1 状态状态ae0

49、1，a已经收到过连续的已经收到过连续的00或或11，收到连续的，收到连续的01，同时同时b=1，z=11. find stateschapter 7 81电路开始工作，设置电路开始工作，设置init状态，状态，z=0状态状态a0，a收到第一个收到第一个0，z=0状态状态a1，a收到第一个收到第一个1，z=0状态状态ok0，a收到连续的两个收到连续的两个0，z=1状态状态ok1，a收到连续的两个收到连续的两个1，z=1状态状态a001，a收到连续的两个收到连续的两个0后，收到后，收到1，同时，同时b=1，z=1状态状态a110，a收到连续的两个收到连续的两个1后，收到后，收到0，同时，同时b=1

50、，z=1状态状态ae10，a已经收到过连续已经收到过连续的的00或或11，收到连续的，收到连续的10，同，同时时b=1，z=1状态状态ae01，a已经收到过连续已经收到过连续的的00或或11，收到连续的，收到连续的01，同，同时时b=1，z=1sinita0a1ok0ok1a001a110ae10ae01a b00a0ok0a0ok0a0a0ok0ok0a0s*01a0ok0a0ok0a110ae10ok0ok0ae1011a1a1ok1a001ok1ok1ae01ae01ok110a1a1ok1a1ok1ok1a1a1ok1z000111111chapter 7 82sinita0a1ok0

51、ok1a001a110ae10ae01a b00a0ok0a0ok0a0a0ok0ok0a001a0ok0a0ok0a110ae10ok0ok0ae1011a1a1ok1a001ok1ok1ae01ae01ok110a1a1ok1a1ok1ok1a1a1ok1z000111111equivalent states, eliminate state ae10equivalent states，eliminate state ae01state minimizationchapter 7 83sinita0a1ok0ok1a001a110a b00a0ok0a0ok0a0a0ok0s*01a0ok

52、0a0ok0a110a110ok011a1a1ok1a001ok1ok1a00110a1a1ok1a1ok1ok1a1z0001111equivalent states, eliminate state a001equivalent states，eliminate state a110state minimizationchapter 7 84sinita0a1ok0ok1a b00a0ok0a0ok0a0s*01a0ok0a0ok0ok011a1a1ok1ok1ok110a1a1ok1a1ok1z00011最小化状态个数的状态表最小化状态个数的状态表minimal state tablec

53、hapter 7 85state assignmentpossible state assignmentsassignmentstate namesimplest q1q3decomposed q1q3one-hot q1q5almost one-hot q1q4init000000000010000a0001100000100001a1010101001000010ok0011110010000100ok1100111100001000q1=0, in the init stateq1=1, in the non-init statein the non-init state,q3 give

54、 the previous value of a;q2 indicates that the conditions for a 1 output are satisfied in the current state.chapter 7 86q1q2q3000100101110111a b00100110100110100d1*d2*d3*011001101001101101110110111111111110101101111101111z00011q1q2q3000100101110111a b00100110100110100q1*q2*q3*01100110100110110111011

55、0111111111110101101111101111z00011transition table and excitation tablechapter 7 87q1q2q3000001010011100101110111a b00100110100110100d1*d2*d3*011001101001101101110110111111111110101101111101111z00011？completed excitation tabletwo approaches:minimal costminimal riskdisposition of unused stateschapter

56、 7 88q1q2q3000001010011100101110111a b00100110100110100d1*d2*d3*011001101001101101110110111111111110101101111101111z000000110000111100 01 1110d100000000abq2q300011110q1=0d1111111110001111011111111abq2q300011110q1=1minimal riskd1=q1+q2q3d2, d3z=q1q2chapter 7 89q1q2q3000001010011100101110111a b0010011

57、0100110100d1*d2*d3*011001101001101101110110111111111110101101111101111z0ddd0011dddd111100 01 1110d1ddddddddabq2q300011110q1=0d1111111110001111011111111abq2q300011110q1=1minimal costd1=1d2,d3z=q2chapter 7 90logic diagram in minimal cost for exp1chapter 7 91logic diagram in minimal risk for exp1chapte

58、r 7 92exp2: 1s-counting machinedesign 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.xyz00001001100010010101100110011000100010resetchapter 7 93each state record

59、 the number of 1 input on x and y：multiple of 4 imply that the number of 1 input can be divided by 4. (mod 4=0)n mod 4 =0， z=1 s0n mod 4 =1， z=0 s1n mod 4 =2， z=0 s2n mod 4 =3， z=0 s3naming statechapter 7 94synthesis stepsss0s1s2s3xy00s0s1s2s3s*01s1s2s3s011s2s3s0s110s1s2s3s0z10001、state/output table

60、2、state assignment:s0 00、s1 01、s2 11、s3 103、transition/output table4、application tablechapter 7 95exp3: a combination lockrequirement: (1) unlk=1 if and only if x is 0 and the sequence of inputs received on x at the preceding seven clock ticks of x was 0110111. (2) hint=1 if and only if the current