算法狀態機圖

算法狀態機(ASM)圖是一種描述時序數字系統控制過程的算法流程圖，其結構形式類似於計算機中的程式流程圖。ASM圖是用一些特定符號按規定的連線方式來描述數字系統的功能。套用ASM圖設計數字系統，可以很容易將語言描述的設計問題變成時序流程圖的描述，只要描述邏輯設計問題的時序流程圖一旦形成，狀態函式和輸出函式就容易獲得，從而得出相應的硬體電路。ASM圖描述的是狀態機的行為動作，而不是存儲組件所存儲的內容。

基本介紹

• 中文名：算法狀態機圖
• 外文名：Algorithmic State Machine Chart
• 簡稱：ASM圖
• 領域：計算機
• 釋義：用來描述數字系統算法的流程圖
• 基本元素：狀態框、判斷框、條件輸出框等

簡介

ASM圖是一種用來描述數字系統算法的流程圖，從結構和形式上看，類似於傳統的計算機流程圖。ASM圖在暫存器傳輸級(RTL)描述系統的狀態變化，側重於描述暫存器中信息的傳輸和處理，包括復位、預置、計數和移位等功能。對於一個數字系統，設計者應首先在RTL畫出它的ASM圖，正如編程人員在編寫軟體時需要畫出算法流程圖一樣。

數字系統的控制和數據處理兩部分都可以在ASM圖中表示出來。畫ASM圖時，設計者只要考慮RTL信號的傳輸和處理，對具體底層硬體可以不加理會。對狀態的設定可以“寧多勿少”，多餘的狀態可以藉助EDA軟體消除。另外，把信號都看成暫存器型信號，無須細分信號是組合信號還是時序信號。

ASM圖表面上與通常的軟體流程圖非常相似。但ASM圖表示事件的精確時間間隔序列I而一般軟體流程圖只表事件序列，沒有時間概念，這是兩者的根本差別。

ASM圖的基本元素

組成ASM圖的基本元素是狀態框、判斷框、條件輸出框和輸入、輸出路徑。輸入、輸出路徑就是連線各種方框的有向箭頭；狀態框表示ASM的一個狀態，判斷框表示狀態分支，條件輸出框表示ASM圖的條件輸出，它總是位於滿足狀態分支條件的路徑上。它們的形狀和操作如圖1所示。

圖1 ASM圖的基本組成元素

狀態框

數字系統控制序列中的狀態用一個矩形框表示，稱為狀態框。框內標出在此狀態下實現的暫存器傳輸操作和輸出，狀態的名稱置於狀態框左上角，分配給狀態的二進制代碼位於狀態框的右上角，圖2為狀態框實例。狀態框的名稱是S1，其代碼是010，框內規定的暫存器的操作是BA，輸出信號是Z。圖2中的箭頭表示系統狀態的流向，在時鐘脈衝觸發沿的觸發下，系統進入狀態S1，在下一個時鐘脈衝觸發沿的觸發下，系統離開狀態S1，因此一個狀態框占用一個時鐘脈衝周期。由此看出，ASM圖內蘊涵著事件序列特性。

圖2

控制器的控制命令由控制算法決定，為表示這些輸出命令，將其放入相應狀態框內，在該狀態框內的動作都應在相應該狀態時鐘結束時或結束以前完成。在該狀態期間可以根據需要定義其它輸出信號。

判斷框

當控制算法存在分支時，次態不僅決定於現態，還與現態時的外輸入有關，因此需要有表示分支的方法。表示分支的符號以菱形或矩形加菱形框線表示。判斷框表示狀態變數對控制器工作的影響，如圖1所示。它有一個入口和多個出口，框內填判斷條件，如果條件是真，選擇一個出口，若條件是假，選擇另一個出口。判斷框不占用時間。

條件輸出框

控制器某些狀態只有在一定條件下才能輸出。為與一般的狀態輸出相區別，用橢圓框表示條件輸出。條件輸出框如圖3(a)所示，條件框的入口必定與判斷框的輸出相連。列在條件框內的暫存器操作或輸出是在給定的狀態下，滿足判斷條件才發生的。在圖3(b)的例子中，當系統處於狀態S1時，若條件X=1，則暫存器R被清零，否則R保持不變；不論X為何值系統的下一個狀態都是S2。

圖3

ASM圖示例

下面通過一個例子說明ASM圖的構造方法。假設十字路口交通燈控制器的技術指標為：紅燈顯示45s，黃燈顯示5s，綠燈顯示40s。A、B兩路的顯示數字分別用暫存器信號LEDA、LEDB表示，A路和B路的指示燈用暫存器信號Light表示，Light包括RA(A紅)、YA(A黃)、GA(A綠)和RB(B紅)、YB(B黃)和GB(B綠)。採用ASM圖描述該控制系統的框圖如圖4所示。

圖4 交通燈控制器的ASM圖

ASM圖一共設定了8個狀態框S0～S7，按照自然二進制編碼方式編碼，當然也可以採用1位熱位編碼(One-hot)。S0、S2、S4和S6狀態框完成初始值的預置，其餘狀態框都是執行減1計數功能，這是按照交通燈時間顯示要求來設定的。指示燈暫存器信號Light預置的數值是十進制數，轉換為二進制數就可以發現，S0的預置數33對應於A路紅燈、B路綠燈；S2預置的數值34對應A路紅燈、B路黃燈；S4預置的12對應A路綠燈、B路紅燈；S6預置的20對應A路黃燈、B路紅燈。