數(shù)字系統(tǒng)的算法描述

數(shù)字系統(tǒng)的算法描述2.1數(shù)字系統(tǒng)算法流程圖描述2.2狀態(tài)機(jī)及算法狀態(tài)機(jī)圖描述習(xí)題與思考題

2.1數(shù)字系統(tǒng)算法流程圖描述

2.1.1算法流程圖的符號(hào)及描述方法算法流程圖由若干種描述符號(hào)構(gòu)成，即啟動(dòng)框、工作框、判斷框、條件框、結(jié)束框及有向線(帶有箭頭的連線)等。

1．啟動(dòng)框和結(jié)束框

與程序流程圖一樣，啟動(dòng)框和結(jié)束框僅僅表示該算法流程圖的開(kāi)始和結(jié)束，使讀者一目了然。一般這兩個(gè)框可以省略，而以文字和箭頭直接表示，如圖2-1所示。

圖2-1啟動(dòng)框和結(jié)束框

2．工作框

如圖2-2所示，工作框用一個(gè)矩形框表示，在框內(nèi)用文字說(shuō)明該工作框所對(duì)應(yīng)的硬件操作內(nèi)容及對(duì)應(yīng)的輸出信號(hào)。

圖2-2工作框

(a)工作框；(b)對(duì)應(yīng)的邏輯電路圖2-3工作框與硬件之間的對(duì)應(yīng)關(guān)系

通常算法流程圖與硬件功能有極好的對(duì)應(yīng)關(guān)系。也就是說(shuō)，一個(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ì)化的過(guò)程。所以，在數(shù)字系統(tǒng)描述的初期，一個(gè)工作框的功能不一定完全能用一個(gè)邏輯電路來(lái)實(shí)現(xiàn)。但是，隨著描述的逐步細(xì)化，設(shè)計(jì)者應(yīng)考慮每一個(gè)工作框的可實(shí)現(xiàn)性，只有這樣，算法流程圖最后才能被綜合成邏輯電路。

3．判斷框

判斷框與程序流程圖中所采用的符號(hào)一樣，用菱形框來(lái)描述?？騼?nèi)應(yīng)給出判斷量和判斷條件。根據(jù)不同的判斷結(jié)果，算法流程圖將確定采用什么樣的后繼操作。判斷框必定有兩個(gè)或兩個(gè)以上的后續(xù)操作，當(dāng)后續(xù)操作超過(guò)3個(gè)時(shí)可以用若干個(gè)判斷框連接來(lái)描述。圖2-4是用算法流程圖中的判斷框描述2-4譯碼器的示例。圖2-4中，輸入為a、b，輸出為y0、y1、y2、y3，用4個(gè)判斷框描述該電路的四種不同的后續(xù)操作。

圖2-4判斷框圖2-5條件框

2.1.2算法流程圖描述數(shù)字系統(tǒng)實(shí)例

為了熟悉算法流程圖描述方法，現(xiàn)舉幾個(gè)例子加以說(shuō)明。

1．串行加法器

串行加法器是利用一位加法器實(shí)現(xiàn)兩個(gè)多位二進(jìn)制數(shù)據(jù)相加的電路。4位串行加法器的算法流程圖如圖2-6(a)所示，其對(duì)應(yīng)的硬件電路框圖如圖2-6(b)所示。該4位串行加法器電路由5部分組成：加法控制電路、累加器、加數(shù)寄存器、一位全加器和進(jìn)位位寄存器。

(a)算法流程圖；(b)對(duì)應(yīng)的硬件框圖圖2-64位串行加法器

一位全加器實(shí)現(xiàn)2個(gè)二進(jìn)制位的相加，其輸入、輸出連接如圖2-6(b)所示。

需要說(shuō)明的是，為簡(jiǎn)化電路，該電路的初始化未包含在上述電路框圖中。

如圖2-6(a)所標(biāo)明的一樣，如果算法流程圖描述適當(dāng)，則其各工作框和判斷框等都會(huì)有較好的對(duì)應(yīng)關(guān)系，這樣會(huì)給電路設(shè)計(jì)帶來(lái)很大的方便。但是，畢竟算法流程圖更貼近數(shù)字系統(tǒng)的行為描述，當(dāng)數(shù)字系統(tǒng)較復(fù)雜時(shí)這種對(duì)應(yīng)關(guān)系就不那么緊密了。

2．乘法器

乘法器可實(shí)現(xiàn)的算法很多。2個(gè)4位數(shù)乘法的運(yùn)算過(guò)程如表2-1所示。

表中有一個(gè)9位寄存器，低4位存放乘數(shù)。如果乘數(shù)的最低位(寄存器的最低位)為“1”，則將被乘數(shù)加到寄存器的b4～b7位上；如果為“0”，則不作加法，然后向右移一位。再重復(fù)上述過(guò)程，直至將乘數(shù)全部移出9位寄存器為止(此例中要移4位)。將這種算法的運(yùn)算過(guò)程用算法流程圖來(lái)描述，如圖2-7(a)所示，與該算法流程圖對(duì)應(yīng)的硬件電路框圖如圖2-7(b)所示。

(a)算法流程圖；(b)硬件電路框圖圖2-7乘法器

該乘法器由3大部分組成：9位長(zhǎng)的累加器ACC、4位加法器和1個(gè)乘法控制電路。乘法控制電路有3個(gè)輸入信號(hào)和4個(gè)輸出控制信號(hào)：

(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)。

在啟動(dòng)信號(hào)有效(START

=

1)以前應(yīng)先將乘數(shù)裝入累加器，將被乘數(shù)裝入被乘數(shù)寄存器(該寄存器圖中未畫(huà)出)，即初始化完畢。在啟動(dòng)信號(hào)有效以后，經(jīng)4個(gè)時(shí)鐘脈沖，乘法操作完成，其結(jié)果將存于累加器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)注。

2.2狀態(tài)機(jī)及算法狀態(tài)機(jī)圖描述

眾所周知，數(shù)字系統(tǒng)由控制單元和處理單元兩大部分組成。控制單元在統(tǒng)一的同步時(shí)鐘控制下，嚴(yán)格按照一定的時(shí)間關(guān)系輸出控制信號(hào)；處理單元一步一步地完成整個(gè)數(shù)字系統(tǒng)的操作。這種工作過(guò)程用算法流程圖是無(wú)法正確描述的。面介紹一種用于描述控制器工作過(guò)程的方法，即算法狀態(tài)機(jī)圖(AlgorithmicStateMachineFlowchart，ASM圖)描述方法。

2.2.1狀態(tài)機(jī)的分類(lèi)及特點(diǎn)

控制器按一定時(shí)序關(guān)系產(chǎn)生一系列的時(shí)序控制信號(hào)，因此它必定包含時(shí)序電路。根據(jù)時(shí)序輸出信號(hào)產(chǎn)生的機(jī)理不同，時(shí)序電路可以分成兩類(lèi)：米勒(Mealy)型和摩爾(Moore)型。

1．米勒型時(shí)序電路

米勒型時(shí)序電路的典型結(jié)構(gòu)如圖2-8所示。

圖2-8米勒型時(shí)序電路的典型結(jié)構(gòu)．

從圖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)是：其輸出不僅與當(dāng)前狀態(tài)有關(guān)，還和輸入值有關(guān)。也就是說(shuō)，輸入X的值不僅決定了電路的下一個(gè)狀態(tài)，而且對(duì)當(dāng)前的輸出值也會(huì)產(chǎn)生影響。下面以4位串行加法器(見(jiàn)圖2-6)的控制電路為例作一說(shuō)明。

參照?qǐng)D2-8所示的米勒型時(shí)序電路的典型結(jié)構(gòu)，此時(shí)串行加法器控制電路的輸入為START，輸出信號(hào)為sh，狀態(tài)寄存器的鎖存信號(hào)為clk，狀態(tài)寄存器的輸出為si，根據(jù)前述工作過(guò)程，我們不難列出其狀態(tài)表和狀態(tài)圖，如表2-2和圖2-9所示。

圖2-9串行加法器的控制狀態(tài)圖

2．摩爾型時(shí)序電路

摩爾型時(shí)序電路的典型結(jié)構(gòu)如圖2-10所示。圖中，輸入有輸入信號(hào)X和狀態(tài)鎖存時(shí)鐘clk，輸出只有一個(gè)Y，其值僅與當(dāng)前的狀態(tài)值有關(guān)，而與輸入X無(wú)關(guān)。

圖2-10摩爾型時(shí)序電路的典型結(jié)構(gòu)

非歸零(NRZ)串行數(shù)據(jù)信號(hào)轉(zhuǎn)換成曼徹斯特(Manchester)串行數(shù)據(jù)信號(hào)的時(shí)序電路就是摩爾型時(shí)序電路的典型實(shí)例。NRZ信號(hào)和Manchester信號(hào)的時(shí)序關(guān)系如圖2-11所示。

圖2-11NRZ信號(hào)和Manchester信號(hào)的時(shí)序關(guān)系

從圖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所示。

表2-3NRZ信號(hào)轉(zhuǎn)換成Manchester碼的狀態(tài)表

圖2-12

NRZ信號(hào)轉(zhuǎn)換成Manchester

碼的狀態(tài)圖

周期為碼元寬度的二分之一，每個(gè)時(shí)鐘周期為一個(gè)狀態(tài)，也就是半個(gè)碼元為一個(gè)狀態(tài)。還應(yīng)注意，Manchester碼的輸出相對(duì)于NRZ信號(hào)的輸入將滯后一個(gè)時(shí)鐘周期。產(chǎn)生這個(gè)滯后的原因是：摩爾時(shí)序電路在有效時(shí)鐘邊沿到來(lái)以前不能立即響應(yīng)NRZ信號(hào)輸入的變化。這是Moore型電路和Mealy型電路的主要區(qū)別。在Mealy型電路中，只要在下一個(gè)時(shí)鐘脈沖到來(lái)以前，輸入的變化立即會(huì)引起輸出的變化。

Mealy型和Moore型時(shí)序電路常用于數(shù)字系統(tǒng)控制電路的描述，在許多文獻(xiàn)和著作中也稱它們?yōu)镸ealy狀態(tài)機(jī)和Moore狀態(tài)機(jī)，以表示它們構(gòu)造電路時(shí)的不同機(jī)理。

2.2.2算法狀態(tài)機(jī)流程圖的符號(hào)及描述方法

所謂狀態(tài)機(jī)，就是用來(lái)控制數(shù)字系統(tǒng)，使其根據(jù)它的輸出，一步一步地進(jìn)行相應(yīng)的操作和運(yùn)算的機(jī)器(這里應(yīng)理解為電路)。實(shí)際上，時(shí)序電路就是一種狀態(tài)機(jī)。

1．狀態(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)注狀態(tài)名，斜杠右邊標(biāo)注輸出信號(hào)清單。有多個(gè)輸出信號(hào)時(shí)，輸出信號(hào)和輸出信號(hào)之間用空格分隔。

狀態(tài)框；(b)判斷框；(c)條件輸出框圖2-13算法狀態(tài)機(jī)圖的描述符

3．條件輸出框

條件輸出框描述符如圖2-13(c)所示。條件輸出框描述符中，上方箭頭表示條件值轉(zhuǎn)入的方向，該帶箭頭的線一定和判斷框的一個(gè)分支相連，且繼承對(duì)應(yīng)分支的條件值；下方箭頭表示轉(zhuǎn)離方向；框內(nèi)標(biāo)注條件輸出信號(hào)清單。有多個(gè)輸出信號(hào)時(shí)，輸出信號(hào)和輸出信號(hào)之間同樣用空格隔開(kāi)。

在算法狀態(tài)機(jī)圖中，無(wú)論是什么輸出信號(hào)，其輸出只能是兩種值，非“0”即“1”。例如，在條件輸出框中表明的輸出信號(hào)或輸出量，在條件滿足時(shí)輸出為“1”。

2.2.3算法狀態(tài)機(jī)圖描述實(shí)例

算法狀態(tài)機(jī)圖與程序流程圖一樣，在描述過(guò)程中有許多不同的方法和技巧。同樣一個(gè)數(shù)字系統(tǒng)可以用多種不同形式的算法狀態(tài)機(jī)圖來(lái)描述，以達(dá)到各種不同的目的。

1．算法狀態(tài)機(jī)圖的化簡(jiǎn)

圖2-14(a)和圖2-14(b)所示的兩個(gè)算法流程圖是等效的。從結(jié)構(gòu)來(lái)看，圖2-14(a)是圖2-14(b)的簡(jiǎn)化。

圖2-14算法狀態(tài)機(jī)圖的化簡(jiǎn)

2．算法狀態(tài)機(jī)圖的反饋通道描述

算法狀態(tài)機(jī)圖中可以有內(nèi)部的反饋通道。與程序流程圖畫(huà)法不同的是，內(nèi)部反饋通道的箭頭應(yīng)指向某一個(gè)狀態(tài)的輸入線，如圖2-15所示。

(a)錯(cuò)誤畫(huà)法；(b)正確畫(huà)法圖2-15算法狀態(tài)機(jī)圖的反饋通道描述

圖2-15(a)中反饋通道箭頭指向判斷框的輸入，這在程序流程圖中是允許的，但在算法狀態(tài)機(jī)圖中是不允許的，是錯(cuò)誤的。如果將圖2-15(a)改成圖2-15(b)，反饋通道指向S0狀態(tài)的輸入，這樣畫(huà)法就正確了。

3．算法狀態(tài)機(jī)圖的串-并結(jié)構(gòu)變換

在進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)時(shí)，有時(shí)為了節(jié)省硬件(如運(yùn)算器)，所有運(yùn)算工作可分給一個(gè)運(yùn)算器來(lái)工作；有時(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)的等效畫(huà)法。

(a)并行結(jié)構(gòu)；(b)串行結(jié)構(gòu)圖2-16串、并行結(jié)構(gòu)的等效畫(huà)法

2.2.4算法流程圖至狀態(tài)圖的變換方法

對(duì)初學(xué)者來(lái)說(shuō)，從算法流程圖直接變換至算法狀態(tài)機(jī)圖是困難的，特別是當(dāng)數(shù)字系統(tǒng)較為復(fù)雜時(shí)更是如此。

算法流程圖至狀態(tài)圖的變換主要有以下幾個(gè)步驟：

(1)系統(tǒng)狀態(tài)分配。

(2)確定輸入信號(hào)及狀態(tài)轉(zhuǎn)移條件。從算法流程圖中，如果抽象出上述三種參數(shù)，則可以很容易地畫(huà)出狀態(tài)圖。

(3)確定各狀態(tài)的輸出。

1．系統(tǒng)狀態(tài)分配

算法流程圖是由事件驅(qū)動(dòng)的流程圖，而狀態(tài)圖是一種時(shí)鐘驅(qū)動(dòng)的流程圖，它將系統(tǒng)工作過(guò)程分成若干個(gè)狀態(tài)，由時(shí)鐘驅(qū)動(dòng)，一個(gè)狀態(tài)接著一個(gè)狀態(tài)，按時(shí)鐘周期節(jié)拍完成系統(tǒng)的工作過(guò)程。因此，為了將算法流程圖轉(zhuǎn)換成狀態(tài)圖，首先要對(duì)算法流程圖進(jìn)行抽象，對(duì)其工作過(guò)程進(jìn)行劃分。每個(gè)相對(duì)獨(dú)立的操作狀態(tài)就可以定義為一個(gè)狀態(tài)，這個(gè)過(guò)程就稱為系統(tǒng)的狀態(tài)分配。下面以4位乘法算法流程圖為例作一說(shuō)明。

4位乘法器控制算法流程圖如圖2-7所示。下面根據(jù)其工作過(guò)程分配各狀態(tài)。

(1)系統(tǒng)復(fù)位狀態(tài)——S0；

(2)裝入乘數(shù)和被乘數(shù)——S1；

(3)被乘數(shù)與累加器ACC相加——S2；

(4)累加器右移1位——S3。

S0～S3包含了4位乘法器控制的4個(gè)基本的獨(dú)立狀態(tài)。如果圖2-7不用循環(huán)結(jié)構(gòu)，那么4位乘法器的狀態(tài)就需10個(gè)(S0～S9)，請(qǐng)讀者自行畫(huà)出。

在較為復(fù)雜的系統(tǒng)中，狀態(tài)圖可以從粗到細(xì)逐步細(xì)化，直至最低層。頂層的一個(gè)狀態(tài)細(xì)化展開(kāi)以后可能要用含有若干個(gè)子狀態(tài)的狀態(tài)圖來(lái)描述。

2．確定輸入信號(hào)及狀態(tài)轉(zhuǎn)移條件

從圖2-7中可以看到，當(dāng)S0是復(fù)位狀態(tài)時(shí)，START?=

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)。

3．確定各狀態(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)需要一個(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ù)上面的敘述，我們可以畫(huà)出4位乘法器的控制狀態(tài)表和狀態(tài)圖如表2-4和圖2-17所示，圖中K'、M'表示對(duì)應(yīng)取值為“0”。

表2-44位乘法器的控制狀態(tài)表

圖2-174位乘法器的控制狀態(tài)圖

2.2.5狀態(tài)圖至算法狀態(tài)機(jī)圖的變換方法

狀態(tài)圖(狀態(tài)轉(zhuǎn)換圖)是傳統(tǒng)描述時(shí)序電路的方法。為了用硬件描述語(yǔ)言進(jìn)行編程，通常要將狀態(tài)圖變換成算法狀態(tài)機(jī)圖(ASM)。變換大約需經(jīng)過(guò)以下幾個(gè)步驟。

1．對(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)圖。該系統(tǒng)共有3個(gè)不同的狀態(tài)S0、S1、S2，可以用2位二進(jìn)制數(shù)表示：S0——

00；S1——

01；S2——

11。

(a)狀態(tài)圖；(b)算法狀態(tài)機(jī)圖圖2-18某數(shù)字系統(tǒng)的狀態(tài)圖和算法狀態(tài)機(jī)圖

2．各輸出信號(hào)的確定

圖2-18(a)所示是米勒型和摩爾型狀態(tài)機(jī)混合的狀態(tài)圖，其輸出Za、Zb、Zc僅由狀態(tài)S0、S1和S2確定(Moore型)，而輸出Z1和Z2都由各狀態(tài)值和輸入值共同確定(Mealy型)。

根據(jù)算法狀態(tài)機(jī)的畫(huà)法規(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)用條件輸出框來(lái)標(biāo)注。

3．按狀態(tài)編碼順序畫(huà)出算法狀態(tài)機(jī)圖

根據(jù)狀態(tài)編碼及輸出標(biāo)注方法，狀態(tài)用狀態(tài)框描述，輸入不同的X，狀態(tài)轉(zhuǎn)移方向是不一樣的，據(jù)此輸入用判斷框表示。摩爾輸出標(biāo)注在狀態(tài)框中，米勒輸出用條件輸出框標(biāo)注在判斷框的相應(yīng)分支上。這樣就完成了狀態(tài)圖至算法狀態(tài)機(jī)圖的變換，如圖2-18(b)所示。

【例2-1】串行加法器的控制狀態(tài)圖如圖2-19所示。該狀態(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)行編碼。

S0——00；

S1——01；

S2——10；

S3——11。

圖2-19串行加法器的控制算法狀態(tài)機(jī)圖

(2)確定輸出值。

圖2-19中的輸出值為sh，它由輸入值START和狀態(tài)值確定，可用條件輸出框描述。在圖2-19中，只有在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)畫(huà)出串行加法器控制算法狀態(tài)機(jī)圖。

根據(jù)上面敘述，我們可以畫(huà)出串行加法器控制算法狀態(tài)機(jī)圖如圖2-19所示。

【例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)S0～S3，這樣對(duì)應(yīng)狀態(tài)編碼為00～11，必須用2位二進(jìn)制數(shù)來(lái)表示。

對(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í)鐘脈沖到來(lái)后，狀態(tài)返回至S0，一個(gè)4位數(shù)的乘法過(guò)程宣布結(jié)束。

圖2-204位乘法器的控制算法狀態(tài)機(jī)圖

(2)確定輸出。

圖2-20中的輸出都是米勒型輸出，因此這些輸出都應(yīng)用條件輸出框表示。乘法器控制電路的輸出有：

sh——移位控制信號(hào)；

Add——加法控制信號(hào)；

Done——結(jié)束標(biāo)志信號(hào)；

Load——加載ACC信號(hào)。

(3)畫(huà)出4位乘法器的控制算法狀態(tài)機(jī)圖。

根據(jù)圖2-17及上面的敘述，我們可以畫(huà)出4位乘法器的控制算法狀態(tài)機(jī)圖如圖2-20所示。

2.2.6C語(yǔ)言流程圖至算法狀態(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語(yǔ)言程序在計(jì)算機(jī)中進(jìn)行仿真。如果仿真結(jié)果是正確的，那么該C語(yǔ)言程序所描述的系統(tǒng)功能是正確的。如果我們以此C語(yǔ)言程序?yàn)橐罁?jù)，將它變換成系統(tǒng)的算法狀態(tài)機(jī)圖，那么就可以正確地設(shè)計(jì)出該數(shù)字系統(tǒng)的硬件。這種思路是完全可行的，并且前面幾節(jié)內(nèi)容已提供了基本的變換方法和手段。C語(yǔ)言程序很容易變換成算法流程圖，那么從算法流程圖也就很容易變換成算法狀態(tài)機(jī)圖。

【例2-3】一個(gè)C語(yǔ)言程序。

#include<stdio.h>

intsample(intfoo)

{intbar

bar=0;

while(bar<foo)

bar=bar+1;

return(bar);

}

眾所周知，C語(yǔ)言程序有三種基本結(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語(yǔ)言程序中，順序結(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)與分支結(jié)構(gòu)相類(lèi)似。．

【例2-4】C語(yǔ)言程序的流程圖如圖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語(yǔ)言程序的狀態(tài)圖如圖2-21(b)所示。圖中，狀態(tài)輸入信號(hào)如下：

fooFlag——foo值刷新標(biāo)志量；

M——循環(huán)計(jì)數(shù)條件變量；

retFlag——bar值輸出標(biāo)志