《計(jì)算機(jī)組成與體系結(jié)構(gòu)（原書(shū)第4版）》 —3.6.4　有限狀態(tài)機(jī)

3.6.4　有限狀態(tài)機(jī)

特性表和時(shí)序圖可用來(lái)描述觸發(fā)器和時(shí)序電路的動(dòng)作。有限狀態(tài)機(jī)（FSM）提供了等效的圖形描述。有限狀態(tài)機(jī)通常使用圓圈表示機(jī)器狀態(tài)，用有向弧表示從一個(gè)狀態(tài)轉(zhuǎn)變到另一個(gè)。每個(gè)圓圈都標(biāo)有它代表的狀態(tài)，每個(gè)圓弧都標(biāo)記有用于該狀態(tài)轉(zhuǎn)換的輸入或輸出。FSM一次只能處于一個(gè)狀態(tài)。這里只對(duì)同步FSM進(jìn)行研究（只有當(dāng)時(shí)鐘到來(lái)時(shí)才允許轉(zhuǎn)換狀態(tài)）。

可以用狀態(tài)機(jī)建模的真實(shí)示例是公共交通燈。它有3種狀態(tài)：綠色、黃色和紅色。當(dāng)硬件中的計(jì)時(shí)器到達(dá)時(shí)狀態(tài)發(fā)生轉(zhuǎn)換。下面是交通燈的FSM。

有許多種不同類(lèi)型的有限狀態(tài)機(jī)，每種都有不同的作用。圖3-24顯示了一個(gè)JK觸發(fā)器的摩爾機(jī)表示。圓圈代表觸發(fā)器的兩種狀態(tài)，標(biāo)記為A和B。輸出Q用括號(hào)表示，圓弧表示狀態(tài)之間的轉(zhuǎn)換。可以在這個(gè)圖中看到，當(dāng)J=1和K=0或J=K=1時(shí)，JK觸發(fā)器從狀態(tài)0變到狀態(tài)1;當(dāng)J=K=1或J=0和K=1時(shí)，它從狀態(tài)1變?yōu)闋顟B(tài)0。這種有限狀態(tài)機(jī)是摩爾型機(jī)器，因?yàn)槊總€(gè)狀態(tài)與機(jī)器的輸出相關(guān)。事實(shí)上，圖中所示的反射電弧是不需要的，因?yàn)闄C(jī)器的輸出僅在狀態(tài)改變時(shí)改變，并且狀態(tài)不通過(guò)反射電弧改變。據(jù)此，可以繪制一個(gè)簡(jiǎn)化的摩爾機(jī)（如圖3-25所示）。摩爾機(jī)以愛(ài)德華·F.摩爾命名，他于1956年發(fā)明了這種類(lèi)型的FSM。

圖3-24　用JK觸發(fā)器表示摩爾機(jī)　　圖3-25　用JK觸發(fā)器表示簡(jiǎn)化的摩爾機(jī)

與愛(ài)德華·摩爾同時(shí)代的喬治H.米莉獨(dú)立發(fā)明了另一種類(lèi)型的FSM，它也是以發(fā)明者命名的。像摩爾機(jī)一樣，米莉機(jī)也是用圓圈表示狀態(tài)，用連接弧表示每個(gè)狀態(tài)過(guò)渡。與摩爾機(jī)不同的是，米莉機(jī)的輸出不但與每個(gè)狀態(tài)相關(guān)（在摩爾機(jī)示例中將0或1放在方括號(hào)中），還與每個(gè)轉(zhuǎn)換相關(guān)。這意味著米莉機(jī)的輸出函數(shù)與當(dāng)前狀態(tài)　圖3-26　用JK觸發(fā)器表示一個(gè)米莉機(jī)及其輸入有關(guān)，而摩爾機(jī)的輸出函數(shù)僅與當(dāng)前狀態(tài)有關(guān)。每個(gè)過(guò)渡弧上用其輸入和輸出分開(kāi)標(biāo)記并用斜杠隔開(kāi)。反射弧不能從米莉機(jī)中刪除，因?yàn)樗鼈兠枥L機(jī)器的輸出。

圖3-26顯示了一個(gè)用于JK觸發(fā)器的米莉機(jī)。

在實(shí)際執(zhí)行摩爾機(jī)或米莉機(jī)時(shí)，有兩件事情是必須要做的：用于存儲(chǔ)當(dāng)前狀態(tài)的存儲(chǔ)器（寄存器），以及控制輸出和從一個(gè)狀態(tài)到另一個(gè)狀態(tài)轉(zhuǎn)換的組合邏輯組件。圖3-27說(shuō)明了這兩個(gè)機(jī)器的邏輯。

圖　3-27

這里提供的摩爾機(jī)或米莉機(jī)的圖形模型和框圖對(duì)于電路行為的高級(jí)概念建模是很有用的。然而，一旦電路變得很復(fù)雜時(shí)，摩爾機(jī)和米莉機(jī)會(huì)變得很麻煩，并且很難捕獲到實(shí)現(xiàn)所需的細(xì)節(jié)。例如，考慮一個(gè)微波爐。微波爐將僅在門(mén)關(guān)閉時(shí)才處于“開(kāi)”狀態(tài)，控制轉(zhuǎn)盤(pán)設(shè)置為“烹飪”或“除霜”，定時(shí)器開(kāi)始顯示時(shí)間。“開(kāi)”狀態(tài)意味著磁控管正在產(chǎn)生微波，爐室中的燈被點(diǎn)亮，并且轉(zhuǎn)盤(pán)正在旋轉(zhuǎn)。如果時(shí)間到了，打開(kāi)門(mén)，或控制從“烹飪”變?yōu)椤瓣P(guān)閉”時(shí)，微波爐變?yōu)椤瓣P(guān)”狀態(tài)。由定時(shí)器提供的范圍連同定義一個(gè)狀態(tài)的大量信號(hào)，很難在摩爾機(jī)和米莉機(jī)中捕獲。因此，克里斯托弗·R.克萊爾發(fā)明了算法狀態(tài)機(jī)（ASM）。正如其名稱(chēng)所示，算法狀態(tài)機(jī)表示將FSM從一個(gè)狀態(tài)提前到另一個(gè)狀態(tài)的算法。

算法狀態(tài)機(jī)由包含狀態(tài)框、標(biāo)簽、可選條件和輸出框的塊組成（見(jiàn)圖3-28）。每個(gè)ASM塊恰好具有一個(gè)入口點(diǎn)和至少一個(gè)出口點(diǎn)。摩爾型輸出（電路信號(hào)）在狀態(tài)塊內(nèi)指示，米莉型輸出在橢圓輸出“盒”中指示。如果信號(hào)在“高”時(shí)置位，則前綴為H；否則，它將以L為前綴。如果信號(hào)立即置位，則它也以I為前綴。否則，在下一個(gè)時(shí)鐘周期信號(hào)有效。導(dǎo)致?tīng)顟B(tài)變化的輸入條件（這是算法部分）由名為條件框的細(xì)長(zhǎng)的六邊形來(lái)表示。任何數(shù)量的條件框都可以放在ASM塊內(nèi)，并且它們的顯示順序并不重要。在示例中微波爐的ASM塊如圖3-29所示。

圖3-28　算法狀態(tài)機(jī)的組件

圖3-29　微波爐的算法狀態(tài)機(jī)

可見(jiàn)，ASM可以表示摩爾機(jī)和米莉機(jī)的行為。摩爾機(jī)和米莉機(jī)可能是等效的，因此可以互換使用。但是，具體使用哪一種取決于實(shí)際應(yīng)用。在大多數(shù)情況下，摩爾機(jī)相比米莉機(jī)需要更多的狀態(tài)（內(nèi)存），但可以得到更簡(jiǎn)單的實(shí)現(xiàn)，因?yàn)槟枡C(jī)的轉(zhuǎn)換更少。無(wú)硬件的機(jī)器摩爾機(jī)和米莉機(jī)只是你在計(jì)算機(jī)科學(xué)文章中遇到的許多不同類(lèi)型有限狀態(tài)機(jī)中的兩種。理解FSM對(duì)于研究編程語(yǔ)言、編譯器、計(jì)算理論和自動(dòng)機(jī)理論至關(guān)重要。我們將這些抽象稱(chēng)為機(jī)器，因?yàn)闄C(jī)器是一組響應(yīng)刺激（事件）的設(shè)備，這些刺激是基于先前事件的歷史（當(dāng)前狀態(tài)）生成的可預(yù)測(cè)響應(yīng)（動(dòng)作）。其中最重要的是有限自動(dòng)機(jī)（DFA）計(jì)算模型。一般來(lái)說(shuō)，在DFA中，M完全由五元組描述，即M=（Q，S，Σ，δ，F(xiàn)），其中：

●Q是表示機(jī)器能承擔(dān)的每一種配置的有限狀態(tài)集合；

●S是Q的元素，表示起始狀態(tài)，它是機(jī)器接收任何輸入之前的初始狀態(tài)；

●Σ是機(jī)器能識(shí)別的輸入字母表或事件集；

●δ是映射Q中的一個(gè)狀態(tài)和輸入字母表中的一個(gè)字母到Q中另一個(gè)（可能相同）狀態(tài)的轉(zhuǎn)換函數(shù)；

●F是最終（或接受）狀態(tài)的一組狀態(tài)（Q的元素）。

DFA在編程語(yǔ)言的研究中特別重要，它們用于識(shí)別語(yǔ)法或語(yǔ)言。要想使用DFA，請(qǐng)從初始狀態(tài)開(kāi)始并處理輸入字符串，一次一個(gè)字符，隨著輸入而改變狀態(tài)。在處理整個(gè)字符串時(shí)，如果你處于最終接受狀態(tài)，則DFA“接受”該合法字符串。否則，字符串被拒絕。

可以　接收一個(gè)變量名的有限狀態(tài)機(jī)使用這個(gè)DFA的定義來(lái)描述一個(gè)機(jī)器，就像在編譯器中從源代碼文件中提取變量名（字符串）一樣。假設(shè)計(jì)算機(jī)語(yǔ)言必須接受以字母開(kāi)頭的變量名，在初始字母之后可以包含無(wú)限字母或數(shù)字流，并由空格字符（制表符、空格、換行符等）終止。變量名的初始狀態(tài)是空字符串，因?yàn)闆](méi)有輸入被讀取。在右圖中用夸張的箭頭（還有幾個(gè)其他符號(hào)）指示這個(gè)初始狀態(tài)。

當(dāng)機(jī)器識(shí)別字母字符時(shí)，它轉(zhuǎn)換到狀態(tài)I，在那里只要輸入了字母或數(shù)字，它就會(huì)保留。在接收到空格字符時(shí)，機(jī)器轉(zhuǎn)換到狀態(tài)A，即它的最終接受狀態(tài)，用雙圈指示。如果輸入了除數(shù)字、字母或空格之外的字符，則機(jī)器進(jìn)入錯(cuò)誤狀態(tài)，這是拒絕字符串的最終狀態(tài)。

我們更感興趣（因?yàn)檎谟懻撚布┑氖蔷哂休敵鰻顟B(tài)的摩爾和米莉FSM。這些FSM和DFA之間的基本區(qū)別是，除了從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的轉(zhuǎn)換函數(shù)以外，摩爾機(jī)和米莉機(jī)也能生成一個(gè)輸出符號(hào)。此外，由于電路沒(méi)有停止或接受字符串的概念，所以它們沒(méi)有最終狀態(tài)集的定義，而是直接輸出。摩爾機(jī)和米莉機(jī)的M都可以由五元組來(lái)完全描述，即M=（Q，S，Σ，Γ，δ），其中：

●Q是表示機(jī)器每個(gè)配置的有限狀態(tài)集合；

●S是Q的元素，表示開(kāi)始狀態(tài)，即機(jī)器在接收任何輸入之前的狀態(tài)；

●Σ是機(jī)器可以識(shí)別的輸入字母表或事件集；

●Γ是有限輸出字母表；

●δ是將狀態(tài)從Q和輸入字母表的字母映射到Q狀態(tài)的轉(zhuǎn)移函數(shù)。

注意，輸入和輸出字母通常是相同的，但不是必須這樣。產(chǎn)生輸出的方式是區(qū)分摩爾機(jī)和米莉機(jī)之間的元素。因此，摩爾機(jī)的輸出函數(shù)嵌入了S的定義，米莉機(jī)的輸出函數(shù)嵌入了轉(zhuǎn)移函數(shù)δ。

如果這看起來(lái)太抽象，那么只要記住一臺(tái)計(jì)算機(jī)可以被認(rèn)為是通用有限狀態(tài)機(jī)。它描述為一臺(tái)機(jī)器加上輸入以及產(chǎn)生（通常）的預(yù)期輸出。有限狀態(tài)機(jī)只是關(guān)于計(jì)算機(jī)和計(jì)算的另一種思考方式。

硬件開(kāi)發(fā)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶(hù)投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶(hù)投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。