算法狀態機

算法狀態機（英語：Algorithmic State Machine，縮寫：ASM）方法是設計有限狀態機的一種方法。在數碼電路設計中，算法狀態機圖是對序向邏輯狀態轉移的一種圖形描述。在功能上，算法狀態機圖與狀態圖類似。^[1]:516

與流程圖的區別

參見：流程圖

在外觀上，算法狀態機圖與計算機程式設計的流程圖使用了相當類似的圖形符號，但是二者具有很大的差異。這種差異是軟件設計和硬件設計的本質差異導致的：硬件數碼電路的狀態轉移是根據定時器訊號來實現同步的，即每過一個時脈「步進」一個狀態，因此算法狀態機的狀態轉移包含着時脈的訊號，相鄰狀態的轉移所跨越的時間往往精確單個時間脈衝，而軟件程式設計則一般不包含時間脈衝訊號。^{[2]:81[1]:518[3]}

設計步驟

利用算法狀態機方法來設計有限狀態機，需要依次完成以下步驟：

1. 根據需要完成的狀態跳轉功能，創建一組對應的算法，可以使用偽代碼來描述電路模塊的所需工作流程；
2. 將偽代碼轉換到算法狀態機圖（ASM圖）；
3. 根據算法狀態機圖設計數據路徑；
4. 在數據路徑的基礎上完成算法狀態機圖的其他細節；
5. 為算法狀態機的各個狀態之間的轉移設計控制邏輯單元。

算法狀態機圖

狀態盒

狀態決定盒

條件輸出盒

算法狀態機圖（ASM圖）由四中基本元素：狀態名稱、狀態盒、狀態決定盒和條件輸出盒，後三者之間用箭頭連接起來。由於摩爾型有限狀態機的輸出只與當前的狀態有關，因此其輸出情況被標註在狀態盒內部，而米利型有限狀態機的狀態塊中不會標註輸出情況。^[2]:82

• 狀態名：有限狀態機各個狀態的名稱被標註在一個狀態塊的左上角，有時還可以標註上該狀態所分配到的狀態碼。
• 狀態盒：其外形為一個長方形方塊，摩爾型有限狀態機的輸出由狀態盒表示（輸出只與當前狀態有關^[4]:82）。
• 狀態決定盒：其外形為一個菱形塊，這個方塊會標註上即將被測試的表達式，然後對應不同的測試結果，給出不同的處理路徑。算法狀態機的狀態決定盒一般具有一個輸入路徑和兩個輸出路徑（分別對應條件滿足和條件不滿足）。狀態決定盒的選擇條件表達式是兩個輸入變量的函數。
• 條件輸出盒：其外形為一個圓角方形塊，米利型有限狀態機的輸出由條件輸出盒表示（輸出與當前狀態和輸入訊號同時有關^[4]:82）。

數據路徑

當有限狀態機的序向邏輯電路用寄存器傳輸級硬件描述語言代碼描述之後，綜合工具會自動生成一系列數據路徑部件。過程代碼塊中被賦值的變量在實際的硬件電路中可以通過硬件寄存器來實現數據的儲存。根據不同賦值操作實現的功能，這樣的硬件寄存器可以是單純的寄存器、移位寄存器、計數器或其他含有組合邏輯網絡的正反器電路（組合邏輯網絡可以是加法器、減法器、數據多工器的各種組合方式）。

參考文獻

1. Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. 2002. ISBN 0-07-283878-7.
2. Mark Zwolinski. SystemVerilog数字系统设计（原书名：Digital System Design with SystemVerilog）. 電子工業出版社. ISBN 978-7-121-12456-3.
3. Flowcharts and Algorithmic State Machines (ASM) (PDF). University of Arizona. [2013-07-12]. （原始內容 (PDF)存檔於2014-02-11）.
4. David Money Harris, Sarah L. Harris. 数字设计与计算机体系结构. 機械工業出版社. ISBN 978-7-111-25459-1.

相關條目

• 有限狀態機（摩爾型、米利型）
• 狀態圖、流程圖

外部連結

• Background of the Algorithmic State Machine (ASM) Notation （頁面存檔備份，存於互聯網檔案館）
• Brief Introduction to ASM Charts （頁面存檔備份，存於互聯網檔案館）
• ASM++: a modern Algorithmic State Machine methodology for RTL designs （頁面存檔備份，存於互聯網檔案館）