數(shù)字系統(tǒng)設(shè)計(jì)課件lect1309時(shí)序電路

1、1Spring 2013 ZDMC Lec. #1 1Digital System Design I數(shù)字系統(tǒng)設(shè)計(jì) 1Weidong Wang (王維東) Dept. of Information Science & Electronic EngineeringISEEZhejiang University-時(shí)序電路2Spring 2013 ZDMC Lec. #1 1任課教師王維東 浙江大學(xué)信息與電子工程學(xué)系, 信電樓306Zhejiang UniversityDepartment of Information Science and Electronic EngineeringHangzho

2、u, 310027Tel: 86-571-87953170 (O)TA:聶濤： ; Office Hours;Xindian (High-Tech) Building 308.課程簡(jiǎn)介課程代碼：111C0120參考書閻石, 數(shù)字電子技術(shù)基礎(chǔ), 第5版, 高等教育出版社, 2006.王金明著，數(shù)字系統(tǒng)設(shè)計(jì)與Verilog HDL，電子工業(yè)出版社，第4版補(bǔ)充講義Stanford 大學(xué) 108A課程notes.R.H.Katz, G.Borriello, Contemporary Logic Design, second edition,電子工業(yè)出版社, 2005.M.M.Mano, 數(shù)字設(shè)計(jì)(第四

3、版), 電子工業(yè)出版社, 2010.8/數(shù)字系統(tǒng)設(shè)計(jì)1/2013 教學(xué)工作/考核平時(shí)30% (課程作業(yè)和project，上課出勤率，期中考試)期末閉卷考試 70%答疑信電樓308房間/周二下午2:30-4:30上課課間、課后Email，短信3Spring 2013 ZDMC Lec. #1 34第六章 時(shí)序邏輯電路Spring 2013 ZDMC Lec. #1 15Spring 2013 ZDMC Lec. #1 1Sequential Logic時(shí)序邏輯介紹（序）Sequential Circuits時(shí)序Simple circuits with feedbackLatchesEdge-tr

4、iggered flip-flops啪嗒作響 Timing Methodologies定時(shí)Cascading級(jí)聯(lián) flip-flops for proper operationClock skew時(shí)鐘偏移 6Spring 2013 ZDMC Lec. #1 1C1C2C3comparatorvalueequalmultiplexerresetopen/closednewequalmux controlclockcomb. logicstateSequential CircuitsCircuits with FeedbackOutputs = f(inputs, past inputs, pas

5、t outputs)Basis for building memory into logic circuitsDoor combination lock is an example of a sequential circuitState is memoryState is an output and an input to combinational logicCombination storage elements are also memory7Spring 2013 ZDMC Lec. #1 1X1X2XnswitchingnetworkZ1Z2ZnCircuits with Feed

6、backHow to control feedback?What stops values from cycling around endlessly8Spring 2013 ZDMC Lec. #1 16.1 概述一、時(shí)序邏輯電路的特點(diǎn)功能上：任一時(shí)刻的輸出不僅取決于該時(shí)刻的輸入，還與電路原來的狀態(tài)有關(guān)。例：串行加法器，兩個(gè)多位數(shù)從低位到高位逐位相加2. 電路結(jié)構(gòu)上包含存儲(chǔ)電路和組合電路存儲(chǔ)器狀態(tài)和輸入變量共同決定輸出9Spring 2013 ZDMC Lec. #1 1二、時(shí)序電路的一般結(jié)構(gòu)形式與功能描述方法10Spring 2013 ZDMC Lec. #1 1可以用三個(gè)方程組來描述：1

7、1Spring 2013 ZDMC Lec. #1 1三、時(shí)序電路的分類1. 同步時(shí)序電路與異步時(shí)序電路同步：存儲(chǔ)電路中所有觸發(fā)器的時(shí)鐘使用統(tǒng)一的clk,狀態(tài)變化發(fā)生在同一時(shí)刻異步：沒有統(tǒng)一的clk,觸發(fā)器狀態(tài)的變化有先有后2. Mealy型和Moore型Mealy型： Moore型： 12Spring 2013 ZDMC Lec. #1 1觸發(fā)器Flip-Flop分類邏輯功能分類RS鎖存器JK觸發(fā)器T觸發(fā)器D觸發(fā)器邏輯功能指按觸發(fā)器的次態(tài)和現(xiàn)態(tài)及輸入信號(hào)之間的邏輯關(guān)系.特性表特性方程狀態(tài)轉(zhuǎn)換圖13Spring 2013 ZDMC Lec. #1 1RS 鎖存器特性方程Qn+1=S+RQnRS

8、 Latch的狀態(tài)轉(zhuǎn)換圖特性表/真值表01S=1,R=0S=0,R=1S=X,R=0S=0,R=X S R Qn Qn+1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0保持復(fù)位置位不定14Spring 2013 ZDMC Lec. #1 1JK 觸發(fā)器特性方程:Qn+1=JQn+KQnJK FF的狀態(tài)轉(zhuǎn)換圖特性表/真值表01J=1,K=XJ=X,K=1J=X,K=0J=0,K=X J K Qn Qn+1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1

9、 1 1 1 0保持復(fù)位置位翻轉(zhuǎn)15Spring 2013 ZDMC Lec. #1 1T 觸發(fā)器特性方程:Qn+1=TQn+TQnT FF的狀態(tài)轉(zhuǎn)換圖特性表/真值表T觸發(fā)器：T=1, Qn+1=Qn01T=1T=1T=0T=0 T Qn Qn+1 0 0 0 0 1 1 1 0 1 1 1 0 保持翻轉(zhuǎn)JK觸發(fā)器的兩個(gè)輸入端連在一起作為T端，可以構(gòu)成T Flip-flop16Spring 2013 ZDMC Lec. #1 1D 觸發(fā)器特性方程:Qn+1=DD FF的狀態(tài)轉(zhuǎn)換圖特性表/真值表01D=1D=1D=1D=0 D Qn Qn+1 0 0 0 0 1 0 1 0 1 1 1 1 re

10、setset17Spring 2013 ZDMC Lec. #1 1采用D 觸發(fā)器實(shí)現(xiàn)JK觸發(fā)器DclkQQKJClk18Spring 2013 ZDMC Lec. #1 1時(shí)序邏輯電路時(shí)序電路通常包含組合電路和存儲(chǔ)電路兩部分.存儲(chǔ)電路的輸出狀態(tài)反饋到組合電路的輸入端，與輸入信號(hào)一起，共同決定組合邏輯電路的輸出.任一時(shí)刻的輸出信號(hào)不僅取決于當(dāng)時(shí)的輸入信號(hào)，還取決于電路原來的狀態(tài)（與以前的輸入有關(guān)）.組合邏輯電路存儲(chǔ)電路輸出方程Yi驅(qū)動(dòng)方程Zi狀態(tài)方程 Qi輸入Xi時(shí)序電路的結(jié)構(gòu)框圖19Spring 2013 ZDMC Lec. #1 1時(shí)序電路分類同步時(shí)序電路所有觸發(fā)器狀態(tài)的變化都是在同一個(gè)時(shí)

11、鐘信號(hào)下同時(shí)發(fā)生.異步時(shí)序電路觸發(fā)器狀態(tài)的變化不是同時(shí)發(fā)生的.20Spring 2013 ZDMC Lec. #1 1FSM:有限狀態(tài)機(jī)采用輸入信號(hào)和電路狀態(tài)的邏輯函數(shù)去描述時(shí)序電路邏輯功能的方法Mealy型輸出信號(hào)取決于存儲(chǔ)電路狀態(tài)和輸入變量Moore型輸出只是存儲(chǔ)電路現(xiàn)態(tài)的函數(shù)輸出與時(shí)鐘同步inputsMoore outputsMealy outputsnext statecurrent statecombinationallogiccombinationallogic21Spring 2013 ZDMC Lec. #1 16.2 時(shí)序電路的分析方法6.2.1 同步時(shí)序電路的分析方法分析：

12、找出給定時(shí)序電路的邏輯功能即找出在輸入和CLK作用下，電路的次態(tài)和輸出。一般步驟：從給定電路寫出存儲(chǔ)電路中每個(gè)觸發(fā)器的驅(qū)動(dòng)方程（輸入的邏輯式），得到整個(gè)電路的驅(qū)動(dòng)方程。將驅(qū)動(dòng)方程代入觸發(fā)器的特性方程，得到狀態(tài)方程。從給定電路寫出輸出方程。22Spring 2013 ZDMC Lec. #1 1同步時(shí)序電路分析方法目的是找出電路狀態(tài)和輸出信號(hào)的變換規(guī)律，指出其邏輯功能時(shí)序電路求激勵(lì)方程和輸出方程由特征方程求狀態(tài)方程求狀態(tài)表畫狀態(tài)圖畫波形圖功能描述23Spring 2013 ZDMC Lec. #1 1例：TTL電路24Spring 2013 ZDMC Lec. #1 16.2.2 時(shí)序電路的狀態(tài)

13、轉(zhuǎn)換表、狀態(tài)轉(zhuǎn)換圖、狀態(tài)機(jī)流程圖和時(shí)序圖一、狀態(tài)轉(zhuǎn)換表000001000101000100110011100010010101011100110000111100010000010010201003011041000510106110170000011111000025Spring 2013 ZDMC Lec. #1 1二、狀態(tài)轉(zhuǎn)換圖26Spring 2013 ZDMC Lec. #1 1三、狀態(tài)機(jī)流程圖（State Machine Chart）見書本26727Spring 2013 ZDMC Lec. #1 1四、時(shí)序圖28Spring 2013 ZDMC Lec. #1 1例：29Spri

14、ng 2013 ZDMC Lec. #1 1（4）列狀態(tài)轉(zhuǎn)換表：（5）狀態(tài)轉(zhuǎn)換圖00011011001/010/011/000/1111/100/001/010/030Spring 2013 ZDMC Lec. #1 1*6.2.3 異步時(shí)序邏輯電路的分析方法各觸發(fā)器的時(shí)鐘不同時(shí)發(fā)生例：TTL電路31Spring 2013 ZDMC Lec. #1 1同步時(shí)序電路分析方法目的是找出電路狀態(tài)和輸出信號(hào)的變換規(guī)律，指出其邏輯功能時(shí)序電路求激勵(lì)方程和輸出方程由特征方程求狀態(tài)方程求狀態(tài)表畫狀態(tài)圖畫波形圖功能描述32Spring 2013 ZDMC Lec. #1 1同步時(shí)序電路分析例DclkQQDcl

15、kQQxAABBy狀態(tài)方程: An+1=Ax+Bx Bn+1=Ax狀態(tài)方程是確定觸發(fā)器狀態(tài)轉(zhuǎn)移條件的表達(dá)式33Spring 2013 ZDMC Lec. #1 1輸出方程 y=(A+B)xDclkQQDclkQQxAABBy34Spring 2013 ZDMC Lec. #1 1狀態(tài)表描述/狀態(tài)圖 現(xiàn)態(tài) 輸入 次態(tài) 輸出 A B x An+1 Bn+1 Y 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 現(xiàn)態(tài) 次態(tài) 輸出 x=0 x=1 x=0 x=1

16、 AB AB AB Y 00 00 01 0 0 01 00 11 1 0 10 00 10 1 0 11 00 10 1 000100111ABx/y0/00/11/01/00/11/00/11/0狀態(tài)圖35Spring 2013 ZDMC Lec. #1 1由JK觸發(fā)器構(gòu)成的時(shí)序電路分析對(duì)D觸發(fā)器,狀態(tài)方程與輸入方程一致.JK/T觸發(fā)器,參考對(duì)應(yīng)的特性表或特性方程來得到次態(tài)值.把觸發(fā)器輸入方程表示成現(xiàn)態(tài)和輸入變量的函數(shù).列出每個(gè)輸入方程的二進(jìn)制數(shù)值.利用對(duì)應(yīng)觸發(fā)器的特性表確定狀態(tài)表中的次態(tài)值.36Spring 2013 ZDMC Lec. #1 1JK FF構(gòu)成的時(shí)序電路分析JKJKCLK

17、xAB JK FF輸入方程 JA=B KA=Bx JB=x KB=Ax+Ax37Spring 2013 ZDMC Lec. #1 1JK FF構(gòu)成的時(shí)序電路分析(續(xù))把觸發(fā)器的輸入方程表示成現(xiàn)態(tài)和輸入變量的函數(shù).將輸入方程代入到觸發(fā)器的特性方程中,得到狀態(tài)方程.使用對(duì)應(yīng)的狀態(tài)方程確定狀態(tài)表中的次態(tài). 現(xiàn)態(tài) 輸入 次態(tài) 觸發(fā)器輸入 A B x A B JA KA JB KB 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1

18、0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 JK FF特性方程: Qn+1=JQn+KQn JK FF輸入方程: JA=B KA=Bx JB=x KB=Ax+Ax 狀態(tài)方程: An+1=AB+AB+AX Bn+1=Bx+ABx+ABx38Spring 2013 ZDMC Lec. #1 1JK FF構(gòu)成的時(shí)序電路分析(續(xù))0011011001000111狀態(tài)圖 現(xiàn)態(tài) 輸入 次態(tài) 觸發(fā)器輸入 A B x A B JA KA JB KB 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1

19、 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 狀態(tài)方程: An+1=AB+AB+AX Bn+1=Bx+ABx+ABx39Spring 2013 ZDMC Lec. #1 16.3 若干常用的時(shí)序邏輯電路6.3.1 寄存器和移位寄存器一、寄存器用于寄存一組二值代碼，N位寄存器由N個(gè)觸發(fā)器組成，可存放一組N位二值代碼。只要求其中每個(gè)觸發(fā)器可置1，置0。例1：40Spring 2013 ZDMC Lec. #1 1例：用維-阻觸發(fā)器結(jié)構(gòu)的74HC17541Spring 2013 ZDMC Lec. #

20、1 1二、移位寄存器（代碼在寄存器中左/右移動(dòng)）具有存儲(chǔ) + 移位功能42Spring 2013 ZDMC Lec. #1 143Spring 2013 ZDMC Lec. #1 1器件實(shí)例：74LS 194A，左/右移，并行輸入，保持，異步置零等功能44Spring 2013 ZDMC Lec. #1 1RDS1S0工作狀態(tài)0XX置零100保持101右移110左移111并行輸入 45Spring 2013 ZDMC Lec. #1 1擴(kuò)展應(yīng)用（4位 8位）46Spring 2013 ZDMC Lec. #1 1RSRSRSDQDQDQDQOUT1OUT2OUT3OUT4CLKIN1IN2IN

21、3IN4RS0RegistersCollections of flip-flops with similar controls and logicStored values somehow related (e.g., form binary value)Share clock, reset, and set linesSimilar logic at each stageExamplesShift registersCounters47Spring 2013 ZDMC Lec. #1 1Shift Register: DFF and JK FF48Spring 2013 ZDMC Lec.

22、#1 1clear sets the register contentsand output to 0s1 and s0 determine the shift function s0s1function00hold state01shift right10shift left11load new inputleft_inleft_outright_outclearright_inoutputinputs0s1clockUniversal Shift RegisterHolds 4 valuesSerial or parallel inputsSerial or parallel output

23、sPermits shift left or rightShift in new values from left or right49Spring 2013 ZDMC Lec. #1 1Nth cells0 and s1control mux0123DQCLKCLEARQN-1(left)QN+1(right)InputNto N-1th cellto N+1th cellclears0s1new value10000output001output value of FF to left (shift right)010output value of FF to right (shift l

24、eft)011inputDesign of Universal Shift RegisterConsider one of the four flip-flopsNew value at next clock cycle:50Spring 2013 ZDMC Lec. #1 14位雙向移位寄存器74LS194A的邏輯圖51Spring 2013 ZDMC Lec. #1 1RSRSRSDQDQDQDQOUT1OUT2OUT3OUT4CLKIN1IN2IN3IN4RS0RegistersCollections of flip-flops with similar controls and log

25、icStored values somehow related (e.g., form binary value)Share clock, reset, and set linesSimilar logic at each stageExamplesShift registersCounters52Spring 2013 ZDMC Lec. #1 1DQDQDQDQINOUT1OUT2OUT3OUT4CLKShift RegisterHolds samples of inputStore last 4 input values in sequence4-bit shift register:5

26、3Spring 2013 ZDMC Lec. #1 1Shift Register Verilogmodule shift_reg (out4, out3, out2, out1, in, clk); output out4, out3, out2, out1; input in, clk; reg out4, out3, out2, out1;always (posedge clk) begin out4 = out3; out3 = out2; out2 = out1; out1 = in; endendmodule54Spring 2013 ZDMC Lec. #1 1Shift Reg

27、ister Verilogmodule shift_reg (out, in, clk); output 4:1 out; input in, clk; reg 4:1 out;always (posedge clk) begin out = out3:1, in; endendmodule55Spring 2013 ZDMC Lec. #1 1Shift Register: DFF and JK FF56Spring 2013 ZDMC Lec. #1 1Register with selective loadWe often use registers to hold values for

28、 multiple clocksWait until neededUsed multiple timesHow do we modify our D flip-flop so that it holds the value till we are done with it?A very simple FSMclkDQenableDQenableclkEn State Next0 Q Q1 Q D57Spring 2013 ZDMC Lec. #1 1IQ: Design Register with Set/ResetSet forces state to 1Reset forces state

29、 to 0What might be a useful fourth option?DQSRS R State Next0 0 Q Q0 1 Q 01 0 Q 11 1 Q X58Spring 2013 ZDMC Lec. #1 1clear sets the register contentsand output to 0s1 and s0 determine the shift function s0s1function00hold state01shift right10shift left11load new inputleft_inleft_outright_outclearrigh

30、t_inoutputinputs0s1clockUniversal Shift RegisterHolds 4 valuesSerial or parallel inputsSerial or parallel outputsPermits shift left or rightShift in new values from left or right59Spring 2013 ZDMC Lec. #1 1Nth cells0 and s1control mux0123DQCLKCLEARQN-1(left)QN+1(right)InputNto N-1th cellto N+1th cel

31、lclears0s1new value10000output001output value of FF to left (shift right)010output value of FF to right (shift left)011inputDesign of Universal Shift RegisterConsider one of the four flip-flopsNew value at next clock cycle:60Spring 2013 ZDMC Lec. #1 1Universal Shift Register Verilogmodule univ_shift

32、 (out, lo, ro, in, li, ri, s, clr, clk); output 3:0 out; output lo, ro; input 3:0 in; input 1:0 s; input li, ri, clr, clk; reg 3:0 out;assign lo = out3;assign ro = out0;always (posedge clk or clr) begin if (clr) out = 0; else case (s) 3: out = in; 2: out = out2:0, ri; 1: out = li, out3:1; 0: out M原理

33、：計(jì)數(shù)循環(huán)過程中設(shè)法跳過NM個(gè)狀態(tài)。具體方法：置零法 置數(shù)法97Spring 2013 ZDMC Lec. #1 1例：將十進(jìn)制的74160接成六進(jìn)制計(jì)數(shù)器異步置零法工作狀態(tài)X0XXX置 0（異步）10XX預(yù)置數(shù)（同步）X1101保持（包括C）X11X0保持（C=0）1111計(jì)數(shù)98Spring 2013 ZDMC Lec. #1 1例：將十進(jìn)制的74160接成六進(jìn)制計(jì)數(shù)器異步置零法99Spring 2013 ZDMC Lec. #1 1100Spring 2013 ZDMC Lec. #1 1置數(shù)法 (a)置入0000 (b)置入1001101Spring 2013 ZDMC Lec. #1

34、 12. N M 的計(jì)數(shù)器然后再采用置零或置數(shù)的方法105Spring 2013 ZDMC Lec. #1 1例：用74160接成二十九進(jìn)制工作狀態(tài)X0XXX置 0（異步）10XX預(yù)置數(shù)（同步）X1101保持（包括C）X11X0保持（C=0）1111計(jì)數(shù)106Spring 2013 ZDMC Lec. #1 1例：用74160接成二十九進(jìn)制整體置零（異步）整體置數(shù)（同步）107Spring 2013 ZDMC Lec. #1 1四、移位寄存器型計(jì)數(shù)器1. 環(huán)形計(jì)數(shù)器108Spring 2013 ZDMC Lec. #1 12. 扭環(huán)形計(jì)數(shù)器109Spring 2013 ZDMC Lec. #1

35、 1五、計(jì)數(shù)器應(yīng)用實(shí)例例1，計(jì)數(shù)器+譯碼器順序節(jié)拍脈沖發(fā)生器110Spring 2013 ZDMC Lec. #1 1例2，計(jì)數(shù)器+數(shù)據(jù)選擇器序列脈沖發(fā)生器發(fā)生的序列：00010111111Spring 2013 ZDMC Lec. #1 1環(huán)形計(jì)數(shù)器電路112Spring 2013 ZDMC Lec. #1 1能自啟動(dòng)的環(huán)形計(jì)數(shù)器電路113Spring 2013 ZDMC Lec. #1 1移位寄存器型計(jì)數(shù)器的一般結(jié)構(gòu)形式114Spring 2013 ZDMC Lec. #1 1扭環(huán)型計(jì)數(shù)器電路115Spring 2013 ZDMC Lec. #1 1能自啟動(dòng)的扭環(huán)形計(jì)數(shù)器116Spring

36、 2013 ZDMC Lec. #1 1systemdata-pathcontrolstateregisterscombinationallogicmultiplexercomparatorcoderegistersregisterlogicswitchingnetworksSystem Design Hierarchy117Spring 2013 ZDMC Lec. #1 1Two Kinds of FSMsMoore Machine vs Mealy MachineCombinational Logicstatestate(t+1) = F ( state(t), input)Output

37、 (t) = G( state(t), Input )Inputstatestate(t+1) = F ( state(t), input(t)Output (t) = G( state(t)InputState / outInputStateInput / Out118Spring 2013 ZDMC Lec. #1 1Implementation as a sequential digital systemEncoding:how many bits per input value?how many values in sequence?how do we know a new input

38、 value is entered?how do we represent the states of the system?Behavior:clock wire tells us when its ok to look at inputs(i.e., they have settled after change)sequential: sequence of values must be enteredsequential: remember if an error occurredfinite-state specificationresetvalueopen/closednewcloc

39、kstate119Spring 2013 ZDMC Lec. #1 1closedclosedclosedC1=value& newC2=value& newC3=value& newC1!=value& newC2!=value& newC3!=value& newclosedresetnot newnot newnot newS1S2S3OPENERRopenSequential example: abstract controlFinite-state diagramStates: 5 statesrepresent point in execution of machineeach s

40、tate has outputsTransitions: 6 from state to state, 5 self transitions, 1 globalchanges of state occur when clock says its okbased on value of inputsInputs: reset, new, results of comparisonsOutput: open/closed120Spring 2013 ZDMC Lec. #1 1resetopen/closednewC1C2C3comparatorvalueequalmultiplexerequal

41、controllermux controlclockdata-path vs. controlInternal structuredata-pathstorage for combinationcomparatorscontrolfinite-state machine controllercontrol for data-pathstate changes controlled by clockdatapath121Spring 2013 ZDMC Lec. #1 1closedclosedmux=C1resetequal& newnot equal& newnot equal& newno

42、t equal& newnot newnot newnot newS1S2S3OPENERRclosedmux=C2equal& newclosedmux=C3equal& newopenSequential example :finite-state machineFinite-state machinerefine state diagram to include internal structure122Spring 2013 ZDMC Lec. #1 1resetnewequalstatestatemuxopen/closed1S1C1closed00S1S1C1closed010S1

43、ERRclosed011S1S2C2closed00S2S2C2closed010S2ERRclosed011S2S3C3closed00S3S3C3closed010S3ERRclosed011S3OPENopen 0 OPENOPEN open0 ERRERR closednextSequential example: finite-state machineFinite-state machinegenerate state table (much like a truth-table)closedclosedmux=C1resetequal& newnot equal& newnot

44、equal& newnot equal& newnot newnot newnot newS1S2S3OPENERRclosedmux=C2equal& newclosedmux=C3equal& newopenSymbolic statesEncoding?123Spring 2013 ZDMC Lec. #1 1Sequential example: encoding Encode state tablestate can be: S1, S2, S3, OPEN, or ERRneeds at least 3 bits to encode: 000, 001, 010, 011, 100

45、and as many as 5: 00001, 00010, 00100, 01000, 10000choose 4 bits: 0001, 0010, 0100, 1000, 0000Encode outputsoutput mux can be: C1, C2, or C3needs 2 to 3 bits to encodechoose 3 bits: 001, 010, 100output open/closed can be: open or closedneeds 1 or 2 bits to encodechoose 1 bits: 1, 0binaryOne-hothybri

46、d124Spring 2013 ZDMC Lec. #1 1good choice of encoding!mux is identical to last 3 bits of next stateopen/closed isidentical to first bitof stateSequential example :encodingEncode state tablestate can be: S1, S2, S3, OPEN, or ERRchoose 4 bits: 0001, 0010, 0100, 1000, 0000output mux can be: C1, C2, or

47、C3choose 3 bits: 001, 010, 100output open/closed can be: open or closedchoose 1 bits: 1, 0resetnewequalstatestatemuxopen/closed100010010 00000100010010010000100000011000100100100 00001000100100010001000000011001001001000 0001000100100001001000000001101001000 1 0 10001000 10 0000 0000 0next125Spring

48、2013 ZDMC Lec. #1 1resetopen/closednewequalcontrollermux controlclockresetopen/closednewequalmux controlclockcomb. logicstatespecial circuit element, called a register, for remembering inputswhen told to by clockSequential example :controller implementationImplementation of the controller126Spring 2

49、013 ZDMC Lec. #1 1One-hot encoded FSMEven Parity Checker Circuit:In General:FFs must be initialized for correct operation (only one 1)127Spring 2013 ZDMC Lec. #1 1FSM Implementation NotesGeneral FSM form:All examples so far generate output based only on the present state:Commonly called Moore Machin

50、e(If output functions include both present state and input then called a Mealy Machine)128Spring 2013 ZDMC Lec. #1 1Example: Ant BrainSensors: L and R antennae, 1 if in touching wallActuators: F - forward step, TL/TR - turn left/right slightlyGoal: find way out of mazeStrategy: keep the wall on the

51、right129Spring 2013 ZDMC Lec. #1 1Ant Brain130Spring 2013 ZDMC Lec. #1 1A: Following wall, touching Go forward, turning left slightlyB: Following wall, not touching Go forward, turning right slightlyC: Break in wall Go forward, turning right slightlyD: Hit wall again Back to state AE: Wall in front

52、Turn left until.F: .we are here, same as state BG: Turn left until.LOST: Forward until we touch somethingAnt Behavior131Spring 2013 ZDMC Lec. #1 1Designing an Ant BrainState DiagramRC(TR, F)RL RB(TR, F)L RLRA(TL, F)RL RL + RE/G(TL)L + RLOST(F)L R132Spring 2013 ZDMC Lec. #1 1Synthesizing the Ant Brai

53、n CircuitEncode States Using a Set of State VariablesArbitrary choice - may affect cost, speedUse Transition Truth TableDefine next state function for each state variableDefine output function for each outputImplement next state and output functions using combinational logic2-level logic (ROM/PLA/PA

54、L)Multi-level logicNext state and output functions can be optimized together133Spring 2013 ZDMC Lec. #1 1Transition Truth TableUsing symbolic statesand outputsLOST(F)E/G(TL)A(TL, F)B(TR, F)C(TR, F)RRL RRL RLRL RL + RL + RL RstateLRnext stateoutputsLOST00LOSTFLOST1E/GFLOST1 E/GFA00BTL, FA01ATL, FA1 E

55、/GTL, FB 0CTR, FB 1ATR, F.134Spring 2013 ZDMC Lec. #1 1stateLRnext stateoutputsX,Y,ZX, Y, ZFTRTL0 0 0000 0 01000 0 0010 0 1100.0 1 0000 1 11010 1 0010 1 01010 1 0100 0 11010 1 0110 0 11010 1 1001 0 01100 1 1010 1 0110.LOST- 000E/G- 001A- 010B- 011C- 100it now remainsto synthesizethese 6 functionsSyn

56、thesis5 states : at least 3 state variables required (X, Y, Z)State assignment (in this case, arbitrarily chosen)135Spring 2013 ZDMC Lec. #1 1stateinputsnext stateoutputsX,Y,ZL RX+,Y+,Z+FTRTL0 0 0000 0 01000 0 0-10 0 11000 0 01-0 0 11000 0 1000 1 10010 0 1-10 1 00010 0 11-0 1 00010 1 0000 1 11010 1

57、0010 1 01010 1 01-0 0 11010 1 1-01 0 01100 1 1-10 1 01101 0 0-01 0 01101 0 0-10 1 0110e.g. TR = X + Y ZX+ = X R + Y Z R = R TRSynthesis of Next State and Output Functions136Spring 2013 ZDMC Lec. #1 1Circuit ImplementationOutputs are a function of the current state only - Moore machineLRFTRTLNext Sta

58、teCurrent Stateoutputlogicnext statelogicX+Y+Z+XYZ137Spring 2013 ZDMC Lec. #1 1Verilog Sketchmodule ant_brain (F, TR, TL, L, R) inputs L, R; outputs F, TR, TL; reg X, Y, Z; assign F = function(X, Y, Z, L, R); assign TR = function(X, Y, Z, L, R); assign TL = function(X, Y, Z, L, R); always (posedge c

59、lk) begin X = function (X, Y, Z, L, R); Y = function (X, Y, Z, L, R); Z = function (X, Y, Z, L, R); end endmodule138Spring 2013 ZDMC Lec. #1 1Ant is in deep trouble if it gets in this stateDont Cares in FSM SynthesisWhat happens to the unused states (101, 110, 111)?Exploited as dont cares to minimiz

60、e the logicIf states cant happen, then dont care what the functions doif states do happen, we may be in trouble000(F)001(TL)010(TL, F)011(TR, F)100(TR, F)RRL RRL RLRL RL + RL + RL R111101110139Spring 2013 ZDMC Lec. #1 1State MinimizationFewer states may mean fewer state variablesHigh-level synthesis