VHDL硬件描述語言與數(shù)字邏輯電路設(shè)計(jì)第2章

1、1 1第2章 數(shù)字系統(tǒng)的算法描述2.1 數(shù)字系統(tǒng)算法流程圖描述數(shù)字系統(tǒng)算法流程圖描述2.2 狀態(tài)機(jī)及算法狀態(tài)機(jī)圖描述狀態(tài)機(jī)及算法狀態(tài)機(jī)圖描述2 2在學(xué)習(xí)高級(jí)語言時(shí)，通常用程序流程圖來描述程序所實(shí)現(xiàn)的一種算法。程序流程圖實(shí)際上就是一種算法描述的方法。在對(duì)數(shù)字系統(tǒng)進(jìn)行算法描述時(shí)，為了便于最后進(jìn)行邏輯綜合，常用的算法描述有：算法流程圖描述、算法狀態(tài)機(jī)描述、硬件描述語言描述等。本章將對(duì)算法流程圖描述及狀態(tài)機(jī)描述進(jìn)行詳細(xì)討論。3 3算法流程圖實(shí)際上是從程序流程圖衍生出來的一種描述數(shù)字系統(tǒng)硬件操作功能的方法。兩者在形式上有許多相似或類同的地方。但是，由于算法流程圖描述的是系統(tǒng)的硬件動(dòng)作，某些操作結(jié)果存在并

2、發(fā)性，因此在描述時(shí)與程序流程圖相比會(huì)略有不同，這一點(diǎn)在后面還會(huì)提及，請(qǐng)讀者注意。2.1 數(shù)字系統(tǒng)算法流程圖描述數(shù)字系統(tǒng)算法流程圖描述4 42.1.1 算法流程圖的符號(hào)及其描述方法算法流程圖的符號(hào)及其描述方法算法流程圖由若干種描述符號(hào)構(gòu)成，即啟動(dòng)框、工作框、判斷框、條件框、結(jié)束框及有向線(帶有箭頭的連線)等。1啟動(dòng)框和結(jié)束框啟動(dòng)框和結(jié)束框與程序流程圖一樣，啟動(dòng)框和結(jié)束框僅僅表示該算法流程圖的開始和結(jié)束，使讀者一目了然。一般這兩個(gè)框可以省略，而以文字和箭頭直接表示，如圖2-1所示。5 5圖2-1 啟動(dòng)框和結(jié)束框6 62工作框工作框如圖2-2所示，工作框用一個(gè)矩形框表示，在框內(nèi)用文字說明該工作框所對(duì)

3、應(yīng)的硬件操作內(nèi)容及對(duì)應(yīng)的輸出信號(hào)。通常算法流程圖與硬件功能有極好的對(duì)應(yīng)關(guān)系。也就是說，一個(gè)工作框的功能應(yīng)該很容易地映射成為一個(gè)較基本的邏輯電路。圖2-3(a)描述兩個(gè)二進(jìn)制數(shù)a和b相加，其結(jié)果為輸出c的工作框；圖2-3(b)則是實(shí)現(xiàn)該工作框功能的邏輯電路。在設(shè)計(jì)數(shù)字系統(tǒng)時(shí)，如用算法流程圖描述其功能，則總要經(jīng)歷由粗至細(xì)逐步細(xì)化的過程。所以，在數(shù)字系統(tǒng)描述的初期，一個(gè)工作框的功能不一定完全能用一個(gè)邏輯電路來實(shí)現(xiàn)。但是，隨著描述的逐步細(xì)化，設(shè)計(jì)者應(yīng)考慮每一個(gè)工作框的可實(shí)現(xiàn)性，只有這樣，算法流程圖最后才能被綜合成邏輯電路。7 7 圖2-2 工作框8 8 圖2-3 工作框與硬件之間的對(duì)應(yīng)關(guān)系(a) 工作

4、框；(b) 對(duì)應(yīng)的邏輯電路9 93判斷框判斷框判斷框與程序流程圖中所采用的符號(hào)一樣，用菱形框來描述?？騼?nèi)應(yīng)給出判斷量和判斷條件。根據(jù)不同的判斷結(jié)果，算法流程圖將確定采用什么樣的后繼操作。判斷框必定有兩個(gè)或兩個(gè)以上的后續(xù)操作，當(dāng)后續(xù)操作超過3個(gè)時(shí)可以用若干個(gè)判斷框連接來描述。圖2-4是用算法流程圖中的判斷框描述2-4譯碼器的示例。圖2-4中，輸入為a、b，輸出為y0、y1、y2、y3，用4個(gè)判斷框描述該電路的四種不同的后續(xù)操作。10 104條件框條件框條件框用橢圓形符號(hào)來表示，如圖2-5所示。條件框一定與判斷框的一個(gè)分支相連，且僅當(dāng)該分支條件滿足時(shí)，條件框中所表明的操作才被執(zhí)行。請(qǐng)讀者注意，條件

5、框是算法流程圖中所特有的，它可描述硬件操作的并發(fā)性。與軟件程序圖中的分支程序不同的是，條件框的操作是與判斷結(jié)果同時(shí)發(fā)生的，如圖2-5所示，當(dāng)cnt=7時(shí)，發(fā)光二極管就發(fā)亮(D1)。在時(shí)序上cnt=7和D1 發(fā)生在同一個(gè)標(biāo)定時(shí)刻。這和程序中先判別cnt 是否等于7，如果等于7則再執(zhí)行下一條指令，點(diǎn)亮發(fā)光二極管(D1)的操作過程是有顯著區(qū)別的。11 11 圖2-4 判斷框12 12 圖2-5 條件框13 132.1.2 算法流程圖描述數(shù)字系統(tǒng)實(shí)例算法流程圖描述數(shù)字系統(tǒng)實(shí)例為了熟悉算法流程圖描述方法，現(xiàn)舉幾個(gè)例子加以說明。1串行加法器串行加法器串行加法器是利用一位加法器實(shí)現(xiàn)兩個(gè)多位二進(jìn)制數(shù)據(jù)相加的電

6、路。4位串行加法器的算法流程圖如圖2-6(a)所示，其對(duì)應(yīng)的硬件電路框圖如圖2-6(b)所示。該4位串行加法器電路由5部分組成：加法控制電路、累加器、加數(shù)寄存器、一位全加器和進(jìn)位位寄存器。14 14圖2-6 4位串行加法器(a) 算法流程圖；(b) 對(duì)應(yīng)的硬件框圖15 15加法控制電路產(chǎn)生移位控制信號(hào)sh和時(shí)鐘脈沖clock。當(dāng)啟動(dòng)信號(hào)START有效(START=1)時(shí)，sh=1，該電路還將輸出4個(gè)時(shí)鐘脈沖(clock)，以完成4位二進(jìn)制數(shù)的加法操作。累加器存放被加的4位二進(jìn)制數(shù)。累加器的最高位輸入與加法器輸出端sumi相連；最低位輸出與加法器的一個(gè)輸入端ai相連。當(dāng)sh=1時(shí)，每個(gè)時(shí)鐘脈沖下

7、降沿到來將使累加器向右移一位。4個(gè)時(shí)鐘脈沖過后，累加器中將存放兩數(shù)相加之和。加數(shù)寄存器存放相加的加數(shù)，其最低位輸出與加法器的另一個(gè)輸入端bi相連。另外，還和最高位的移位輸入端相連，構(gòu)成一個(gè)循環(huán)移位寄存器。sh和clock連接同一累加器。16 16進(jìn)位位寄存器存放上一次加法器相加所產(chǎn)生的進(jìn)位位結(jié)果。它實(shí)際上是一個(gè)D觸發(fā)器。一位全加器實(shí)現(xiàn)2個(gè)二進(jìn)制位的相加，其輸入、輸出連接如圖2-6(b)所示。需要說明的是，為簡(jiǎn)化電路，該電路的初始化未包含在上述電路框圖中。如圖2-6(a)所標(biāo)明的一樣，如果算法流程圖描述適當(dāng)，則其各工作框和判斷框等都會(huì)有較好的對(duì)應(yīng)關(guān)系，這樣會(huì)給電路設(shè)計(jì)帶來很大的方便。但是，畢竟算

8、法流程圖更貼近數(shù)字系統(tǒng)的行為描述，當(dāng)數(shù)字系統(tǒng)較復(fù)雜時(shí)這種對(duì)應(yīng)關(guān)系就不那么緊密了。17 172乘法器乘法器乘法器可實(shí)現(xiàn)的算法很多。2個(gè)4位數(shù)乘法的運(yùn)算過程如表2-1所示。18 18表表2-1 2個(gè)個(gè)4位二進(jìn)制數(shù)的相乘過程位二進(jìn)制數(shù)的相乘過程19 19表中有一個(gè)9位寄存器，低4位存放乘數(shù)。如果乘數(shù)的最低位(寄存器的最低位)為“1”，則將被乘數(shù)加到寄存器的b4b7位上；如果為“0”，則不作加法，然后向右移一位。再重復(fù)上述過程，直至將乘數(shù)全部移出9位寄存器為止(此例中要移4位)。將這種算法的運(yùn)算過程用算法流程圖來描述，如圖2-7(a)所示，與該算法流程圖對(duì)應(yīng)的硬件電路框圖如圖2-7(b)所示。該乘法器

9、由3大部分組成：9位長(zhǎng)的累加器ACC、4位加法器和一個(gè)乘法控制電路。乘法控制電路有3個(gè)輸入信號(hào)和4個(gè)輸出控制信號(hào)：2020(1) Load累加器數(shù)據(jù)裝載控制信號(hào)；(2) sh累加器移位控制信號(hào)；(3) Add累加器輸出相加信號(hào)；(4) Done乘法結(jié)束標(biāo)志信號(hào)；(5) clk時(shí)鐘信號(hào)；(6) START啟動(dòng)控制信號(hào)；(7) M加被乘數(shù)控制信號(hào)。21 21圖2-7 乘法器(a) 算法流程圖；(b) 硬件電路框圖2222在啟動(dòng)信號(hào)有效(START=“1”)以前應(yīng)先將乘數(shù)裝入累加器，將被乘數(shù)裝入被乘數(shù)寄存器(該寄存器圖中未畫出)，即初始化完畢。在啟動(dòng)信號(hào)有效以后，經(jīng)4個(gè)時(shí)鐘脈沖，乘法操作完成，其結(jié)果

10、將存于累加器ACC中。如前所述，算法流程圖常用于數(shù)字系統(tǒng)的行為描述，它僅僅規(guī)定了數(shù)字系統(tǒng)的一些操作順序，而并未對(duì)操作的時(shí)間和操作之間的關(guān)系做出嚴(yán)格的規(guī)定。因而它常用于驗(yàn)證數(shù)字系統(tǒng)數(shù)學(xué)模型的正確性，對(duì)其硬件的可實(shí)現(xiàn)性未作更多的關(guān)注。2323眾所周知，數(shù)字系統(tǒng)由控制單元和處理單元兩大部分組成?？刂茊卧诮y(tǒng)一的同步時(shí)鐘控制下，嚴(yán)格按照一定的時(shí)間關(guān)系輸出控制信號(hào)；處理單元一步一步地完成整個(gè)數(shù)字系統(tǒng)的操作。這種工作過程用算法流程圖是無法正確描述的。下面介紹一種用于描述控制器工作過程的方法，即算法狀態(tài)機(jī)圖(Algorithmic State Machine Chart，ASM圖)描述方法。2.2 狀態(tài)機(jī)及

11、算法狀態(tài)機(jī)圖描述狀態(tài)機(jī)及算法狀態(tài)機(jī)圖描述24242.2.1 狀態(tài)機(jī)的分類及特點(diǎn)狀態(tài)機(jī)的分類及特點(diǎn)控制器按一定時(shí)序關(guān)系產(chǎn)生一系列的時(shí)序控制信號(hào)，因此它必定包含時(shí)序電路。根據(jù)時(shí)序輸出信號(hào)產(chǎn)生的機(jī)理不同，時(shí)序電路可以分成兩類：米勒(Mealy)型和摩爾(Moore)型。1米勒型時(shí)序電路米勒型時(shí)序電路米勒型時(shí)序電路的典型結(jié)構(gòu)如圖2-8所示。2525圖2-8 米勒型時(shí)序電路的典型結(jié)構(gòu)2626從圖2-8中可以看到，該電路由一個(gè)組合邏輯電路和一個(gè)狀態(tài)寄存器構(gòu)成。狀態(tài)寄存器的輸入是下一個(gè)狀態(tài)值，而輸出是當(dāng)前的狀態(tài)值。組合邏輯電路的輸入為電路輸入X及當(dāng)前狀態(tài)值，輸出為電路輸出Y及下一個(gè)狀態(tài)值。該電路的特點(diǎn)是：其

12、輸出不僅與當(dāng)前狀態(tài)有關(guān)，還和輸入值有關(guān)。也就是說，輸入X的值不僅決定了電路的下一個(gè)狀態(tài)，而且對(duì)當(dāng)前的輸出值也會(huì)產(chǎn)生影響。下面以四位串行加法器(見圖2-6)的控制電路為例作一說明。參照?qǐng)D2-8所示的米勒型時(shí)序電路的典型結(jié)構(gòu)，此時(shí)串行加法器控制電路的輸入為START，輸出信號(hào)為sh，狀態(tài)寄存器的鎖存信號(hào)為clk，狀態(tài)寄存器的輸出為si，根據(jù)前述工作過程，我們不難列出其狀態(tài)表和狀態(tài)圖，如表2-2和圖2-9所示。2727表表2-2 串行加法器的控制狀態(tài)表串行加法器的控制狀態(tài)表從表2-2中可以看到，控制器的輸入START只有在S0狀態(tài)下才會(huì)對(duì)輸出sh產(chǎn)生影響，它表明該電路一旦啟動(dòng)，一定要做完4位加法才能

13、使其停止工作。2828圖2-9 串行加法器的控制狀態(tài)圖2929在圖2-9中，每一個(gè)圓代表一個(gè)狀態(tài)，在其中標(biāo)出了狀態(tài)名S0、S1、S2、S3。各狀態(tài)之間用帶箭頭的線連接起來，表示狀態(tài)轉(zhuǎn)換的方向。在連接線旁標(biāo)出了箭頭所指狀態(tài)的輸入值和輸出值，如0/0，斜杠左邊為輸入值，右邊為輸出值，本例中應(yīng)為START/sh。30302摩爾型時(shí)序電路摩爾型時(shí)序電路摩爾型時(shí)序電路的典型結(jié)構(gòu)如圖2-10所示。圖2-10中，輸入有輸入信號(hào)X和狀態(tài)鎖存時(shí)鐘clk，輸出只有一個(gè)Y，其值僅與當(dāng)前的狀態(tài)值有關(guān)，而與輸入X無關(guān)。非歸零(NRZ)串行數(shù)據(jù)信號(hào)轉(zhuǎn)換成曼徹斯特(Manchester)串行數(shù)據(jù)信號(hào)的時(shí)序電路就是摩爾型時(shí)序

14、電路的典型實(shí)例。NRZ信號(hào)和Manchester信號(hào)的時(shí)序關(guān)系如圖2-11所示。從圖2-11中可以看出，當(dāng)非歸零信號(hào)由“1”變成“0”或由“0”變成“1”時(shí)，曼徹斯特信號(hào)在一個(gè)碼元寬度的時(shí)間內(nèi)將維持不變，在其它情況下，在每個(gè)碼元中間信號(hào)將發(fā)生一次變化(由“1”變“0”或由“0”變“1”)。據(jù)此，我們可以得出該串行碼轉(zhuǎn)換電路的狀態(tài)表和狀態(tài)轉(zhuǎn)換圖分別如表2-3和圖2-12所示。31 31圖2-10 摩爾型時(shí)序電路的典型結(jié)構(gòu)3232圖2-11 NRZ信號(hào)和Manchester信號(hào)的時(shí)序關(guān)系3333表表2-3 NRZ信號(hào)轉(zhuǎn)換成信號(hào)轉(zhuǎn)換成Manchester碼的狀態(tài)表碼的狀態(tài)表3434圖2-12 NRZ

15、信號(hào)轉(zhuǎn)換成Manchester碼的狀態(tài)圖3535clk的時(shí)鐘周期為碼元寬度的二分之一，每個(gè)時(shí)鐘周期為一個(gè)狀態(tài)，也就是半個(gè)碼元為一個(gè)狀態(tài)。還應(yīng)注意，Manchester碼的輸出相對(duì)于NRZ信號(hào)的輸入將滯后一個(gè)時(shí)鐘周期。產(chǎn)生這個(gè)滯后的原因是：摩爾時(shí)序電路在有效時(shí)鐘邊沿到來以前不能立即響應(yīng)NRZ信號(hào)輸入的變化。這是Moore型電路和Mealy型電路的主要區(qū)別。在Mealy型電路中，只要在下一個(gè)時(shí)鐘脈沖到來以前，輸入的變化立即會(huì)引起輸出的變化。Mealy型和Moore型時(shí)序電路常用于數(shù)字系統(tǒng)控制電路的描述，在許多文獻(xiàn)和著作中也稱它們?yōu)镸ealy狀態(tài)機(jī)和Moore狀態(tài)機(jī)，以表示它們構(gòu)造電路時(shí)的不同機(jī)理。

16、36362.2.2 算法狀態(tài)機(jī)流程圖的符號(hào)及描述方法算法狀態(tài)機(jī)流程圖的符號(hào)及描述方法所謂狀態(tài)機(jī)，就是用來控制數(shù)字系統(tǒng)，使其根據(jù)它的輸出，一步一步地進(jìn)行相應(yīng)的操作和運(yùn)算的機(jī)器(這里應(yīng)理解為電路)。實(shí)際上，時(shí)序電路就是一種狀態(tài)機(jī)。分析狀態(tài)機(jī)的傳統(tǒng)方法是利用狀態(tài)圖和狀態(tài)表。但是，隨著計(jì)算機(jī)技術(shù)及電子設(shè)計(jì)自動(dòng)化(EDA)技術(shù)的發(fā)展，為了提高電路的設(shè)計(jì)效率，人們?cè)噲D用硬件描述語言(Hardware Description Language，HDL)來描述數(shù)字系統(tǒng)的硬件電路。硬件描述語言如VHDL、Verilog-HDL等都是高級(jí)語言。為了編程方便，人們通常用程序流程圖來描述算法和系統(tǒng)的功能。同樣，為了方

17、便地利用硬件描述語言來描述數(shù)字系統(tǒng)，3737在編程前也需要用類似的流程圖來描述數(shù)字系統(tǒng)的狀態(tài)機(jī)，這就是狀態(tài)機(jī)流程圖(State Machine Flowchart)，也稱為算法狀態(tài)機(jī)流程圖(Algorithmic State Machine Flowchart)。算法狀態(tài)機(jī)流程圖也可簡(jiǎn)稱為算法狀態(tài)機(jī)圖，其使用的描述符號(hào)與算法流程圖類同。38381狀態(tài)框狀態(tài)框狀態(tài)框描述符如圖2-13(a)所示，它用一個(gè)方框表示。狀態(tài)框描述符中，上方的箭頭表示進(jìn)入該狀態(tài)；箭頭的右方標(biāo)注該狀態(tài)在系統(tǒng)中的編碼(該編碼在系統(tǒng)中是唯一的)；下方箭頭表示該狀態(tài)轉(zhuǎn)離的方向；方框內(nèi)標(biāo)注狀態(tài)名和輸出信號(hào)清單，斜杠(/)左邊標(biāo)注狀

18、態(tài)名，斜杠右邊標(biāo)注輸出信號(hào)清單。有多個(gè)輸出信號(hào)時(shí)，輸出信號(hào)和輸出信號(hào)之間用空格分隔。39392判斷框判斷框判斷框描述符如圖2-13(b)所示，它用一個(gè)菱形框來表示。判斷框描述符中，上方箭頭表示進(jìn)入該框的方向；左右兩個(gè)箭頭表示根據(jù)框內(nèi)標(biāo)明的條件取值不同而轉(zhuǎn)離的方向。條件判斷值將標(biāo)注在箭線的上方。4040圖2-13 算法狀態(tài)機(jī)圖的描述符(a) 狀態(tài)框；(b) 判斷框；(c) 條件輸出框41 413條件輸出框條件輸出框條件輸出框描述符如圖2-13(c)所示。條件輸出框描述符中，上方箭頭表示條件值轉(zhuǎn)入的方向，該帶箭頭的線一定和判斷框的一個(gè)分支相連，且繼承對(duì)應(yīng)分支的條件值；下方箭頭表示轉(zhuǎn)離方向；框內(nèi)標(biāo)注

19、條件的輸出信號(hào)清單。有多個(gè)輸出信號(hào)時(shí)，輸出信號(hào)和輸出信號(hào)之間同樣用空格隔開。在算法狀態(tài)機(jī)圖中，無論是什么輸出信號(hào)，其輸出只能是兩種值，非“0”即“1”。例如，在條件輸出框中表明的輸出信號(hào)或輸出量，在條件滿足時(shí)輸出為“1”。42422.2.3 算法狀態(tài)機(jī)圖描述實(shí)例算法狀態(tài)機(jī)圖描述實(shí)例算法狀態(tài)機(jī)圖與程序流程圖一樣，在描述過程中有許多不同的方法和技巧。同樣一個(gè)數(shù)字系統(tǒng)可以用多種不同形式的算法狀態(tài)機(jī)圖來描述，以達(dá)到各種不同的目的。1算法狀態(tài)機(jī)圖的化簡(jiǎn)算法狀態(tài)機(jī)圖的化簡(jiǎn)圖2-14(a)和圖2-14(b)所示的兩個(gè)算法流程圖是等效的。從結(jié)構(gòu)來看，圖2-14(a)是圖2-14(b)的簡(jiǎn)化。按圖2-14(a)

20、進(jìn)行編程，其程序要比圖2-14(b)簡(jiǎn)單，這一點(diǎn)是不言而喻的。但是，對(duì)硬件生成來說，不一定愈簡(jiǎn)化愈好，有時(shí)還應(yīng)考慮實(shí)現(xiàn)的方便性和電路的延時(shí)等。4343圖2-14 算法狀態(tài)機(jī)圖的化簡(jiǎn)44442算法狀態(tài)機(jī)圖的反饋通道描述算法狀態(tài)機(jī)圖的反饋通道描述算法狀態(tài)機(jī)圖中可以有內(nèi)部的反饋通道。與程序流程圖畫法不同的是，內(nèi)部反饋通道的箭頭應(yīng)指向某一個(gè)狀態(tài)的輸入線，如圖2-15所示。圖2-15(a)中反饋通道箭頭指向判斷框的輸入，這在程序流程圖中是允許的，但在算法狀態(tài)機(jī)圖中是不允許的，是錯(cuò)誤的。如果改成圖2-15(b)，反饋通道指向S0狀態(tài)的輸入，這樣畫法就正確了。4545圖2-15 算法狀態(tài)機(jī)圖的反饋通道描述(

21、a) 錯(cuò)誤畫法；(b) 正確畫法46463算法狀態(tài)機(jī)圖的串算法狀態(tài)機(jī)圖的串-并結(jié)構(gòu)變換并結(jié)構(gòu)變換在進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)時(shí)，有時(shí)為了節(jié)省硬件(如運(yùn)算器)，所有運(yùn)算工作可分給一個(gè)運(yùn)算器來工作；有時(shí)為了加快處理時(shí)間，數(shù)字系統(tǒng)的運(yùn)算工作又可以分給多個(gè)運(yùn)算器并行工作。這些硬件結(jié)構(gòu)反映在算法狀態(tài)機(jī)圖上就可分為串行方式和并行方式。串-并方式的互相變換是經(jīng)常要進(jìn)行的工作。圖2-16是這兩種結(jié)構(gòu)的等效畫法。4747圖2-16 串、并行結(jié)構(gòu)的等效畫法(a) 并行結(jié)構(gòu)；(b) 串行結(jié)構(gòu)48482.2.4 算法流程圖至狀態(tài)圖的變換方法算法流程圖至狀態(tài)圖的變換方法對(duì)初學(xué)者來說，從算法流程圖直接變換至算法狀態(tài)機(jī)圖是困難的，特

22、別是當(dāng)數(shù)字系統(tǒng)較為復(fù)雜時(shí)更是如此。算法流程圖至狀態(tài)圖的變換主要有以下幾個(gè)步驟：(1) 系統(tǒng)狀態(tài)分配。(2) 確定輸入信號(hào)及狀態(tài)轉(zhuǎn)移條件。從算法流程圖中，如果抽象出上述三種參數(shù)，則可以很容易地畫出狀態(tài)圖。(3) 確定各狀態(tài)的輸出。49491系統(tǒng)狀態(tài)分配系統(tǒng)狀態(tài)分配算法流程圖是由事件驅(qū)動(dòng)的流程圖，而狀態(tài)圖是一種時(shí)鐘驅(qū)動(dòng)的流程圖，它將系統(tǒng)工作過程分成若干個(gè)狀態(tài)，由時(shí)鐘驅(qū)動(dòng)，一個(gè)狀態(tài)接著一個(gè)狀態(tài)，按時(shí)鐘周期節(jié)拍完成系統(tǒng)的工作過程。因此，為了將算法流程圖轉(zhuǎn)換成狀態(tài)圖，首先要對(duì)算法流程圖進(jìn)行抽象，對(duì)其工作過程進(jìn)行劃分。每個(gè)相對(duì)獨(dú)立的操作狀態(tài)就可以定義為一個(gè)狀態(tài)，這個(gè)過程就稱為系統(tǒng)的狀態(tài)分配。下面以4位乘法

23、算法流程圖為例作一說明。50504位乘法器控制算法流程圖如圖2-7所示。下面根據(jù)其工作過程分配各狀態(tài)。(1) 系統(tǒng)復(fù)位狀態(tài)S0；(2) 裝入乘數(shù)和被乘數(shù)S1；(3) 被乘數(shù)與累加器ACC相加S2；(4) 累加器右移1位S3。S0S3包含了4位乘法器控制的4個(gè)基本的獨(dú)立狀態(tài)。如果圖2-7不用循環(huán)結(jié)構(gòu)，那么4位乘法器的狀態(tài)就需10個(gè)(S0S9)，請(qǐng)讀者自行畫出。在較為復(fù)雜的系統(tǒng)中，狀態(tài)圖可以從粗到細(xì)逐步細(xì)化，直至最低層。頂層的一個(gè)狀態(tài)細(xì)化展開以后可能要用含有若干個(gè)子狀態(tài)的狀態(tài)圖來描述。51 512確定輸入信號(hào)及狀態(tài)轉(zhuǎn)移條件確定輸入信號(hào)及狀態(tài)轉(zhuǎn)移條件從圖2-7中可以看到，當(dāng)S0是復(fù)位狀態(tài)時(shí)，STAR

24、T=“0”；當(dāng)START=“1”時(shí)，狀態(tài)由S0轉(zhuǎn)移到S1。下面判斷乘數(shù)最低位是否為“1”(M=“1”)。如果為“1”，則轉(zhuǎn)移至狀態(tài)S2；如果為“0”(M=“0”且K=“0”)，則仍在S1狀態(tài)；若K=“1”且M=“0”，則轉(zhuǎn)移至S3。在S2狀態(tài)下，若未移位4次(K=“0”)，則轉(zhuǎn)移至S1狀態(tài)；如果已移夠4次(K=“1”)，則轉(zhuǎn)移至S3狀態(tài)。S3狀態(tài)的下一個(gè)狀態(tài)一定是S0狀態(tài)。52523確定各狀態(tài)的輸出確定各狀態(tài)的輸出由S0狀態(tài)轉(zhuǎn)移至S1狀態(tài)，需要將被乘數(shù)和乘數(shù)裝入累加器ACC，故需要一個(gè)裝入控制信號(hào)Load。S1狀態(tài)循環(huán)或轉(zhuǎn)移至S3狀態(tài)，需一個(gè)累加器移位控制信號(hào)sh。由S1狀態(tài)轉(zhuǎn)移至S2狀態(tài)需要

25、一個(gè)被乘數(shù)和累加器相加的信號(hào)Add。由S2狀態(tài)轉(zhuǎn)移至S1狀態(tài)需加一個(gè)累加器移位控制信號(hào)sh。由S2狀態(tài)轉(zhuǎn)移至S3狀態(tài)需要一個(gè)累加器移位控制信號(hào)sh。由S3狀態(tài)轉(zhuǎn)移至S0狀態(tài)需要輸出Done乘法結(jié)束狀態(tài)信號(hào)。根據(jù)上面的敘述，我們可以畫出4位乘法器的控制狀態(tài)表和狀態(tài)圖如表2-4和圖2-17所示，圖中K、M表示對(duì)應(yīng)取值為“0”。5353表表2-4 4位乘法器的控制狀態(tài)表位乘法器的控制狀態(tài)表5454圖2-17 4位乘法器的控制狀態(tài)圖5555算法流程圖至狀態(tài)圖的變換結(jié)果不一定是唯一的，它和讀者的變換技巧高低有很大關(guān)系，要做好這一步需要積累一定的工程經(jīng)驗(yàn)。56562.2.5 狀態(tài)圖至算法狀態(tài)機(jī)圖的變換方法

26、狀態(tài)圖至算法狀態(tài)機(jī)圖的變換方法狀態(tài)圖(狀態(tài)轉(zhuǎn)換圖)是傳統(tǒng)描述時(shí)序電路的方法。為了用硬件描述語言進(jìn)行編程，通常要將狀態(tài)圖變換成算法狀態(tài)機(jī)圖(ASM)。變換大約需經(jīng)過以下幾個(gè)步驟。1對(duì)現(xiàn)有的狀態(tài)進(jìn)行編碼對(duì)現(xiàn)有的狀態(tài)進(jìn)行編碼從狀態(tài)圖中我們可以確定某數(shù)字系統(tǒng)有幾個(gè)不同的狀態(tài)，并用二進(jìn)制數(shù)對(duì)每一個(gè)狀態(tài)進(jìn)行賦值。例如，圖2-18(a)是某數(shù)字系統(tǒng)的狀態(tài)圖。5757該系統(tǒng)共有3個(gè)不同的狀態(tài)S0、S1、S2，可以用2位二進(jìn)制數(shù)表示。S000；S101；S211。5858圖2-18 某數(shù)字系統(tǒng)的狀態(tài)圖和算法狀態(tài)機(jī)圖(a) 狀態(tài)圖；(b) 算法狀態(tài)機(jī)圖5959圖2-19 串行加法器的控制算法狀態(tài)機(jī)圖60602各輸

27、出信號(hào)的確定各輸出信號(hào)的確定圖2-18(a)所示的狀態(tài)圖是米勒型和摩爾型狀態(tài)機(jī)混合的狀態(tài)圖，其輸出Za、Zb、Zc僅由狀態(tài)S0、S1和S2確定(Moore型)，而輸出Z1和Z2都由各狀態(tài)值和輸入值共同確定(Mealy型)。根據(jù)算法狀態(tài)機(jī)的畫法規(guī)則，輸出Za、Zb、Zc應(yīng)標(biāo)注在狀態(tài)框中，如S0/Za、S1/Zb、S2/Zc；Z1、Z2除與當(dāng)前狀態(tài)值有關(guān)外，還與輸入值X有關(guān)，因此Z1、Z2應(yīng)用條件輸出框來標(biāo)注。61 613按狀態(tài)編碼順序畫出算法狀態(tài)機(jī)圖按狀態(tài)編碼順序畫出算法狀態(tài)機(jī)圖根據(jù)狀態(tài)編碼及輸出標(biāo)注方法，狀態(tài)用狀態(tài)框描述，輸入不同的X，狀態(tài)轉(zhuǎn)移方向是不一樣的，據(jù)此輸入用判斷框表示。摩爾輸出標(biāo)注

28、在狀態(tài)框中，米勒輸出用條件輸出框標(biāo)注在判斷框的相應(yīng)分支上。這樣就完成了狀態(tài)圖至算法狀態(tài)機(jī)圖的變換，如圖2-18(b)所示。對(duì)于實(shí)際的數(shù)字系統(tǒng)，其狀態(tài)圖可能要復(fù)雜得多，但是基本的變換方法是一致的。下面舉兩個(gè)變換的實(shí)例。6262【例【例2-1】 串行加法器的控制狀態(tài)圖如圖2-9所示。該狀態(tài)圖是米勒型狀態(tài)圖，其輸出由輸入和當(dāng)前狀態(tài)確定。(1) 對(duì)現(xiàn)有狀態(tài)進(jìn)行編碼。圖2-19共有4個(gè)狀態(tài)S0、S1、S2、S3，可用2位二進(jìn)制數(shù)進(jìn)行編碼。S000；S101；S210；S311。6363(2) 確定輸出值。圖2-19中的輸出值為sh，它由輸入值START和狀態(tài)值確定，可用條件輸出框描述。在圖2-19中，只

29、有在S0狀態(tài)下，輸入值START為“1”，才會(huì)發(fā)生狀態(tài)轉(zhuǎn)移，由S0狀態(tài)轉(zhuǎn)至S1狀態(tài)，且輸出sh=“1”。在其它狀態(tài)下，只要有時(shí)鐘脈沖，狀態(tài)就會(huì)向下一個(gè)轉(zhuǎn)換，直至S0，同時(shí)不管此時(shí)的輸入START為何值，其輸出值sh仍繼續(xù)保持為“1”。(3) 畫出串行加法器控制算法狀態(tài)機(jī)圖。根據(jù)上面敘述，我們可以畫出串行加法器控制算法狀態(tài)機(jī)圖如圖2-19所示。6464圖2-20 4位乘法器的控制算法狀態(tài)機(jī)圖6565【例【例2-2】 4位乘法控制器的狀態(tài)圖如圖2-17所示。從狀態(tài)圖中可以看到，它是一個(gè)米勒型狀態(tài)機(jī)圖，其輸出應(yīng)用條件輸出框表示。(1) 對(duì)現(xiàn)有狀態(tài)進(jìn)行編碼。4位乘法器控制電路共有4個(gè)狀態(tài)S0S3，這樣

30、對(duì)應(yīng)狀態(tài)編碼為0011，必須用2位二進(jìn)制數(shù)來表示。6666對(duì)照?qǐng)D2-17可以看到，S0是復(fù)位狀態(tài)。當(dāng)START為“1”時(shí)，系統(tǒng)狀態(tài)將轉(zhuǎn)移到S1，并輸出Load信號(hào)，將被乘數(shù)和乘數(shù)裝入ACC。下一個(gè)狀態(tài)有兩種選擇。如果M=“1”(即乘數(shù)低位為“1”)，則輸出Add信號(hào)，進(jìn)行累加器和被乘數(shù)的加法操作，轉(zhuǎn)移至狀態(tài)S2；如果M=“0”，則輸出sh信號(hào)，控制ACC右移1位，并對(duì)K進(jìn)行檢測(cè)。在S1、S2狀態(tài)下，如果K=1(表明最后一次移位結(jié)束)，則下一個(gè)狀態(tài)為S3；如果K=0，則轉(zhuǎn)移至S1狀態(tài)。在S3狀態(tài)下，Done信號(hào)(完成信號(hào))有效輸出，在下一個(gè)時(shí)鐘脈沖到來后，狀態(tài)返回至S0，一個(gè)4位數(shù)的乘法過程宣布

31、結(jié)束。6767(2) 確定輸出。圖2-20中的輸出都是米勒型輸出，因此這些輸出都應(yīng)用條件輸出框表示。乘法器控制電路的輸出有：Sh移位控制信號(hào)；Add加法控制信號(hào)；Done結(jié)束標(biāo)志信號(hào)；Load加載ACC信號(hào)。(3) 畫出4位乘法器的控制算法狀態(tài)機(jī)圖。根據(jù)圖2-17及上面的敘述，我們可以畫出4位乘法器的控制算法狀態(tài)機(jī)圖如圖2-20所示。68682.2.6 C語言流程圖至算法狀態(tài)機(jī)圖的變換語言流程圖至算法狀態(tài)機(jī)圖的變換在設(shè)計(jì)數(shù)字系統(tǒng)時(shí)首先要建立系統(tǒng)的數(shù)學(xué)模型。最初，通常建立的是行為級(jí)的數(shù)學(xué)模型。為了驗(yàn)證系統(tǒng)數(shù)學(xué)模型的正確性，設(shè)計(jì)人員可以根據(jù)數(shù)學(xué)模型的算法，用C語言程序在計(jì)算機(jī)中進(jìn)行仿真。如果仿真結(jié)

32、果是正確的，那么該C語言程序所描述的系統(tǒng)功能是正確的。如果我們以此C語言程序?yàn)橐罁?jù)，將它變換成系統(tǒng)的算法狀態(tài)機(jī)圖，那么就可以正確地設(shè)計(jì)出該數(shù)字系統(tǒng)的硬件。這種思路是完全可行的，并且前面幾節(jié)內(nèi)容已提供了基本的變換方法和手段。C語言程序很容易變換成算法流程圖，那么從算法流程圖也就很容易變換成算法狀態(tài)機(jī)圖。下面以一個(gè)實(shí)例加以說明。6969圖2-21 例2-4 C語言程序的流程圖和狀態(tài)圖(a) 流程圖；(b) 狀態(tài)圖7070圖2-22 例2-4 C語言程序的算法狀態(tài)機(jī)圖71 71【例【例2-3】 一個(gè)C語言程序。#include int sample (int foo) int bar bar=0；

33、while (barfoo)bar=bar+1； return (bar)；7272眾所周知，C語言程序有三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。在對(duì)程序進(jìn)行抽象和分配狀態(tài)時(shí)大致可以遵循以下規(guī)則。(1) 順序結(jié)構(gòu)。C語言程序中，順序結(jié)構(gòu)部分可以歸結(jié)在一個(gè)狀態(tài)中，因?yàn)橐话沩樞虿僮髦胁粫?huì)改變系統(tǒng)的工作狀態(tài)。(2) 分支結(jié)構(gòu)。在分支結(jié)構(gòu)中程序?qū)?duì)條件量進(jìn)行判斷，條件不同，程序?qū)⑥D(zhuǎn)向不同的分支。分支程序的條件量是系統(tǒng)狀態(tài)的輸入，不同條件將轉(zhuǎn)向不同的狀態(tài)，從而發(fā)生狀態(tài)轉(zhuǎn)移。(3) 循環(huán)結(jié)構(gòu)。循環(huán)程序以循環(huán)變量為條件量，該條件量通常是一個(gè)計(jì)數(shù)值。當(dāng)計(jì)數(shù)值達(dá)到指定值時(shí)，條件滿足，狀態(tài)發(fā)生轉(zhuǎn)移，這一點(diǎn)與分

34、支結(jié)構(gòu)相類似。7373【例【例2-4】 C語言程序的流程圖如圖2-21(a)所示。從該流程圖中可以看到，該程序可以分配3個(gè)狀態(tài)：初始狀態(tài)S0(循環(huán)結(jié)構(gòu)之前部分)、循環(huán)結(jié)構(gòu)部分狀態(tài)S1、結(jié)果輸出狀態(tài)S2。該C語言程序的狀態(tài)圖如圖2-21(b)所示。其中，狀態(tài)輸入信號(hào)如下：fooFlayfoo值刷新標(biāo)志量；M循環(huán)計(jì)數(shù)條件變量；retFlagbar值輸出標(biāo)志量。根據(jù)圖2-21我們可把狀態(tài)圖轉(zhuǎn)換成算法狀態(tài)機(jī)圖，如圖2-22所示。7474【例【例2-5】 用switch語句描述CPU功能的C語言程序如下：#include #define MEMSIZE 34#define std_logic char#

35、define LOAD_ACC 0#define STORE_ACC #define CLR_ACC 2#define INC_ACC 3#define CMP_ACC #define JUMP_EQ 7575#define JUMP_NEQ 6#define JUMP_ALWAYS 7#define WAIT_TIME 8#define SEC_BUFFER 32#define MIN_BUFFER 33int ROMMEMSIZE = /*00*/ CLR_ACC，/*01*/ STORE_ACC，SEC_BUFFER，/*03*/ STORE_ACC，MIN_BUFFER，/*05*/

36、WAIT_TIME，7676/*06*/ LORD_ACC， SEC_BUFFER，/*08*/ INC_ACC，/*09*/ CMP_ACC，60，/*11*/ JUMP_EQ，17，/*13*/ STORE_ACC，SEC_BUFFER，/*15*/ JUMP_ALWAYS，5，/*17*/ CLR_ACC，/*18*/ STORE_ACC， SEC_BUFFER，/*20*/ LORD_ACC， MIN_BUFFER，/*22*/ INC_ACC，/*23*/ CMP_ACC， 60，7777/*25*/ JUMP_NEQ，28，/*27*/ CLR_ACC，/*28*/ STORE_A

37、CC，SEC_BUFFER，/*30*/ JUMP_ALWAYS，5，;void CPU(void)int PC;int ACC;std-logic Flag;int Opcode;7878int Operand;PC=0:while(1) Opcode=ROM PC; PC=PC+1; switch (Opecode) case LOAD_ACC: Operand=ROM PC; ACC=ROM Operand; PC=PC+1; break; case STORE_ACC7979 Operand=ROM PC; ROMOperand=ACC; PC=PC+1; break; case CL

38、R_ACC: ACC=0; break; case INC_ACC: ACC=ACC+1; break;8080 case CMP_ACC: Operand=ROM PC; if (Acc=Operand)Flag=1; else Flag=0; PC=PC+1 break; case JUMP_EQOperand = ROM PC;81 81 if(Flag=1) PC=Operand; else PC=PC+1; break; case JUMP_NEQ: Operand =ROMPC; if (Flag=0) PC=Operand; elsePC=PC+1;8282 break; cas

39、e JUMP_ALWAYS: PC=ROMPC; break; case WAIT_TIME: long unsigned int timer; 1秒等待 for(timer=0; timer1000000;timer+) printf(); break; 8383 printf(%02d%02d￥tPC=%03d， Acc=%03d， Flag=%c￥r，ROM MIN_BUFFER，ROMSEC_BUFFER，PC，ACC，F(xiàn)lag); /*getchar() ; */ void main(void) CPU( ); 8484以上程序描述的僅僅是一個(gè)CPU的行為模型。為了便于狀態(tài)圖描述，我們將該程序用IF和Goto語句來改寫，程序如下：S0: PC =0S1: Opcode = MEM PC;S2: PC =PC+1 S3: if (Opcode=LOAD_ACC) goto S4; else goto S8; S4: Operand =MEMPC；S5: ACC =MEM(Operand);S6: PC =P