邏輯設計筆記序向篇 : Finite State Machine (有限狀態機)

整理完計數器筆記後, 終於來到序向邏輯電路設計的最重要篇章-有限狀態機 (finite state machine, FSM), 前面介紹的暫存器 (register) 與計數器 (counter) 都是從分析 (analytical) 的角度來看序向電路, 而有限狀態機則是從合成 (synthetic) 角度來看. 其實, 暫存器與計數器都是有限狀態機. 本系列之前的筆記參考 :

# 邏輯設計筆記序向篇 : Latch (電栓) 與 Flip-Flop (正反器)
# 邏輯設計筆記序向篇 : Register (暫存器)
# 邏輯設計筆記序向篇 : Counter (計數器)

以下筆記參考了如下幾本書 :

1. 數位邏輯設計附實習 第三版 (楊豐瑞, 陳福春, 旗標出版)
2. 最新數位邏輯電路設計 第三版 (劉紹漢等, 全華全華)
3. 數位邏輯設計 第三版 (黃慶璋, 全華出版)

1. Moore 與 Mealy 狀態機 :

FSM 的數學基礎是源自形式語言的自動機 (automata) 理論, 廣泛地應用在硬體與軟體設計中, 參考 :

# Wiki : 有限狀態機
# Wiki : Finite State Machine

有限狀態機 FSM 有兩種類型 :

1. Mealy Machine (密利機) 
2. Moore Machine (莫爾機) 

主要的差別是 : Moore 機的輸出是由暫存器所儲存之記憶狀態直接輸出或經過組合後輸出, 與輸入不直接相關, 亦即, 輸入的變化不會馬上影響輸出. 而 Mealy 機則是將輸入與暫存器狀態經組合後輸出, 因此輸入的變化馬上會影響輸出, 電路結構如下 :

注意, Moore 機輸出端的組合邏輯電路是可有可無的, 如果正反器狀態就是所要的輸出就不需要此邏輯電路; 反之, 輸出是正反器狀態的組合時就需要, 例如狀態的解碼器.

儲存同樣狀態的有限狀態機可以選擇設計成 Mealy 或 Moore 機, 差別是在輸出的組合電路是否納入要輸入訊號. 但在一個同步系統中, 有時希望輸入的改變可以與時鐘同步, 而不是馬上影響輸出, 這可在 Mealy 機的輸出組合電路後面加上暫存器來達成.

設計有限狀態機時首先須根據設計需求判定這是 Moore 機還是 Mealy 機, 然後按照需求功能繪製狀態變化圖,

具體而言, 就是將狀態圖轉成狀態表, 然後對照正反器激勵表 (excitation table) 填寫正反器之轉態表 (transition table), 再利用卡諾圖 (Karnaugh map) 求出個正反器的輸入方程式 (input equation), 即可繪製最後的電路圖 :

2. 狀態表 (state table) : 

依照設計要求畫出狀態圖後, 必須將其填入狀態表並定義狀態值以利後續設計. Moore 機狀態表範例如下, 包含現態 (current state), 次態 (next state), 以及輸出. 如果有輸入例如 X, 次態需依輸入值排列組合分欄填寫; 否則次態只需一欄即可. 另外, 由於 Moore 機的輸出只與正反器狀態有關, 因此輸出是獨立一欄 :

Mealy 機的狀態表範例如下, 它與 Moore 機最大的不同是, 輸出與輸入有關, 因此輸出與次態寫在一起, 且依照輸入不同分欄填寫 :

狀態表是狀態圖的表格化, 在後續設計流程中, 它將結合正反器激勵表 (excitation) 一起整合為轉態表 (transition).


3. 正反器的激勵表 (excitation table) : 

每一個 latch 與 flip-flop (正反器) 的功能表 (function table) 描述的是輸入所對應的輸出, 而所謂激勵表 (excitation table) 則是反過來, 描述的是要達成輸出狀態的變化所需要的輸入. 以下列出在有限狀態機設計中常用到的四種記憶元件之激勵表 :

(1) SR latch (NOR) :

NOR latch 的電路符號, 功能表, 以及激勵表如下圖所示, function table 輸入 S, R 在左, 輸出 Qn+1 (次態, next state) 在右, 描述輸入-輸出的對應, 反之, excitation table 則是現態 (present state) Qn 變成次態 Qn+1 所需要的輸入環境.

SR NOR latch 激勵表的推導 :

1. 第一列 : 正反器現態為 0 次態為 0, 在 function table 中符合之 SR 輸入有 SR=00 與 SR=01, 前者是因為狀態保持不變入選 (現態為 0  次態為 0), 因此 R 輸入值為 don't care, 所以打一個 X, 而 S 輸入值為 0. 
2. 第二列 : 現態為 0 次態為 1, 在 function table 中符合之 SR 輸入只有一個, 即 SR=10.  
3. 第三列 : 現態為 1 次態為 0, 在 function table 中符合之 SR 輸入只有一個, 即 SR=01. 
4. 第四列 : 現態為 1 次態為 1, 在 function table 中符合之 SR 輸入有 SR=00 與 SR=10, 前者是因為狀態保持不變入選 (現態為 1), 因此 S 輸入值為 don't care, 所以打一個 X, 而 R 輸入值為 0. 

(2) JK flip-flop :

JK flip-flop 的電路符號, 功能表, 以及激勵表如下圖所示 :

JK flip-flop 激勵表的推導 :

1. 第一列 : 正反器現態為 0 次態為 0, 在 function table 中符合之 JK 輸入有 JK=00 與 JK=01, 前者是因為狀態保持不變入選 (現態為 0), 因此 K 輸入值為 don't care, 所以打一個 X, 而 J 輸入值為 0.
2. 第二列 : 現態為 0 次態為 1, 在 function table 中符合之 JK 輸入有 JK=10 與 JK=11, 前者是必然, 後者是因為 toggle 轉態入選 (現態為 0 次態為 1), 因此 K 輸入值為 don't care, 所以打一個 X, 而 J 輸入值為 1. 
3. 第三列 : 現態為 1 次態為 0, 在 function table 中符合之 JK 輸入有 JK=01 與 JK=11, 前者是必然, 後者是因為 toggle 轉態入選 (現態為 1 次態為 0), 因此 J 輸入值為 don't care, 所以打一個 X, 而 K 輸入值為 1.
4. 第四列 : 現態為 1 次態為 1, 在 function table 中符合之 JK 輸入有 JK=10 與 JK=00, 前者是必然, 後者是因為狀態保持不變入選 (現態為 1 次態為 1), 因此 J 輸入值為 don't care, 所以打一個 X, 而 K 輸入值為 0. 

(3) D flip-flop :

D flip-flop 的電路符號, 功能表, 以及激勵表如下圖所示 :

D flip-flop 激勵表的推導 :

1. 第一列 : 現態為 0 次態為 0, 在 function table 中符合之 D 輸入為 D=0.
2. 第二列 : 現態為 0 次態為 1, 在 function table 中符合之 D 輸入為 D=1. 
3. 第三列 : 現態為 1 次態為 0, 在 function table 中符合之 D 輸入為 D=0.
4. 第四列 : 現態為 1 次態為 1, 在 function table 中符合之 D 輸入為 D=1.

由於 D 正反器是 transparent flip-flop (透明的), 因此 D 輸入其實就是次態 Qn+1 之值.

(4) T flip-flop :

T flip-flop 的電路符號, 功能表, 以及激勵表如下圖所示 :

T flip-flop 激勵表的推導 :

1. 第一列 : 現態為 0 次態為 0, 在 function table 中符合之 T 輸入為 T=0.
2. 第二列 : 現態為 0 次態為 1, 在 function table 中符合之 T 輸入為 T=1. 
3. 第三列 : 現態為 1 次態為 0, 在 function table 中符合之 T 輸入為 T=1.
4. 第四列 : 現態為 1 次態為 1, 在 function table 中符合之 T 輸入為 T=0.

由於 T 正反器是 toggle flip-flop (交替的), 因此只要是有轉態, 即 1 變成 0 或 0 變成 1, 其 T 輸入必須為 1 (toggle), 否則 T=0 (keep state).

以上所推導出的四種激勵表是有限狀態機設計所必須, 摘要如下 :

由功能表 (function) 反推出激勵表 (excitation) 之後, 便可以將狀態表與激勵表整合成一張轉態表 (transition table), 以便利用卡諾圖來求得正反器的輸入方程式. 空白的轉態表範例如下所示, 這裡以最常用的 D 與 JK 正反器為例, 假設狀態機有一個輸入 X 與一個輸出 Y, 使用 4 個正反器, 故狀態有 Q0, Q1, Q2, Q3 共四個 :

如果有多個輸出入 (例如 X1, X2, ... Y1, Y2, ...), 需再添加欄位.

有了狀態表與激勵表, 接下來就是將兩者整合為一張轉態表以便求取正反器的輸入方程式, 這必須以實際範例來說明.


範例 1 : Moore 信號偵測器

設計一個信號偵測器, 當位元串流 (bit stream) 中出現 "101" 時輸出 high, 否則輸出 low. 例如 :

首先以 Moore 機來設計, 依據設計要求描述, 因為要偵測的信號標記是 3 個位元, 若使用 Moore 機來設計的話需要四個狀態來記錄已收到之信號, 這是一個逐步接近目標狀態 "101" 之進程 :

S0 : 0 received, output 0 
S1 : 1 received, output 0 
S2 : 10 received, output 0
S3 : 101 received, output 1

狀態圖如下 :

注意, 只有進入 S3 狀態 (已收到 "101") 才會輸出 1, 否則都輸出 0. 其次, 在 S3 收到 0 是進入 S2, 不是 S0, 因為在 S3 已收到 101, 若在收到 0 表示已收到 1010, 後兩位元是 10, 此為 S2 狀態.

狀態圖畫好後需指定狀態值 (即編碼), 四個狀態需要兩個位元編碼, 因為 2**2=4. 編碼可任意指定, 此處指定 S0=00, S1=01, S2=10, S3=11. 然後將狀態圖填入狀態表中 :

填表的方法是先將最左邊 S0~S3 的現態值填好, 然後依據狀態圖由上而下逐列填寫次態與輸出 :

1. 在 S0 狀態時輸出 0, 收到 0 次態為 S0, 收到 1 次態為 S1. 
2. 在 S1 狀態時輸出 0, 收到 0 次態為 S2, 收到 1 次態為 S1. 
3. 在 S2 狀態時輸出 0, 收到 0 次態為 S0, 收到 1 次態為 S3. 
4. 在 S3 狀態時輸出 1, 收到 0 次態為 S2, 收到 1 次態為 S1. 

接著要結合狀態表與正反器為一張轉態表, 以下將使用 D 與 JK 正反器, 其激勵表如下 :

轉態表實際上就是狀態表的延伸, 它將輸入與現態做排列組合, 並多出一個正反器輸入欄位, 依據激勵表填入每一個現態變成次態所需之輸入條件.

例如 JK 正反器的轉態表中, 第一列 Q0 狀態由 0 變 0, 從激勵表可知所需知輸入為 J0=0, K0=X. 第四列 Q1 由 1 變 0, 從激勵表可知所需知輸入為 J0=X, K0=1. 如此這般由上而下依序將第四欄的 JK excitation 填好, 輸出部分因 Moore 機輸出只與現態有關, 因此只在現態 Q0Q1=11 時輸出 1 :

如果用 D 正反器來做, 則轉態表就更容易填寫了, 因為正反器的輸入 D0D1 不用像 JK 那樣要去查看激勵表 (當然, 若背得起來的話是不用查), 直接將次態 (next state) 複製過來就行了 (凡事皆有代價, 這麼方便的代價是電路可能較複雜, 需要較多邏輯閘來實現) :

轉態表填好後就可以用卡諾圖求取正反器的輸入方程式了, 卡諾圖的變數有三個, 一個是輸入 X, 另外是正反器的現態 Q0 與 Q1 一組. 注意, 卡諾圖相鄰只能有一個變化, 因此 Q0Q1 排列依序是 00-01-11-10.

以 J0 為例, 只有在 XQ0Q1=001 (注意這裡 Q0Q1 是指現態) 時 J0 才為 1, XQ0Q1=000, 100, 與 101 時為 0, 其餘的組合均為 X (don't care), 填入卡諾圖後發現 XQ0Q1=001 可與 011 的 X 結合 (因 X 表示可以為 0 也可以為 1, 把它當作 1 比較有利), 這個組合項 X 部分為 0, Q0Q1 部分 Q0 消失只剩 Q1, 因此 J0=/XQ1, 其餘各方程式依此方法求得, 結果如下圖所示 :

如果以 D 正反器來實現, 則其卡諾圖化簡如下圖所示 :

因為 Moore 機輸出只與正反器狀態有關, 與輸入沒有直接相關, 因此不論是用 JK 還是 D, 其輸出都是 Y=Q0Q1 :

輸入方程式求出來後就可以繪製電路圖 :

這樣就完成整個設計.


範例 2 : Mealy 信號偵測器

此設計與上面範例 1 相同, 但改用 Mealy 機來設計. 與 Moore 機最大的不同是輸出與輸入直接相關, 因此只需要三個狀態即可, 狀態定義如下 :

S0 : 0 received, output 0
S1 : 1 received, output 0
S2 : 10 received, output 0

注意, Mealy 機不需要 Moore 機的第 4 個狀態 S3, 這是因為在 S2 時若收到 1 就可以輸出 1 並回到 S1 (即收到 1 的狀態), 若收到 0 就輸出 0 並回到 S0. Moore 機需要 S3 的原因是其輸出是依賴於正反器狀態, 因此需要一個收到 "101" 的 S3 狀態以支持輸出信號.

狀態圖如下 :

將狀態圖轉成如下狀態表 :

然後依據激勵表將狀態表延伸為轉態表 :

注意最底下一列表示現態為 10 時若收到 X=1 輸出 1. 用卡諾圖求取 JK 正反器輸入方程式如下 :

求取 D 正反器輸入方程式與輸出方程式如下 :

注意, 不論是用 JK 或 D 實現, 其輸出方程式都一樣 : Y=XQ0. 電路圖如下 :

以上便是 Mealy 機的設計結果, 看起來比 Moore 機簡單些.

在上一篇的計數器筆記中曾提到, 計數器其實就是一種有限狀態機, 同步計數器電路之構成有特定之規則, 下面就以設計 3-bit 同步計數器來說明這些電路是怎麼來的.


範例 3 : 設計 MOD-8 二元上數計數器

計數器可以直接用正反器狀態做輸出, 因此通常是用 Moore 狀態機來實現, MOD-8 二元計數器需要 8 個狀態來記錄計數值, 其狀態圖如下 :

將狀態圖轉成如下之狀態表並定義狀態值, 八個狀態需要用到 3 個正反器 :

以 JK 正反器來實現, 依據 JK 的激勵表得出轉態表如下, 方法以圖中的 Q0 為例, 現態 1 變為次態 0, 則 J0K0 須為 X1, 其餘均照此方法填寫 :

注意, 因計數器沒有額外輸入且直接以正反器狀態做輸出, 故轉態表無輸出入變數欄位. 接著用卡諾圖求取正反器輸入方程式 :

依據輸入方程式繪製電路圖如下 :

在上一篇計數器筆記中的 MOD-8 二元計數器電路就是這樣得到的. 此範例為上數 (count up) 計數器, 那下數計數器呢? 方法一樣, 只是狀態表不同罷了, 見下面範例.


範例 4 : 設計 MOD-8 二元下數計數器

MOD-8 下數計數器的狀態圖與上數計數器是一樣的, 參考上例, 不一樣的是狀態表, 如下圖所示 :

依據 JK 激勵表將狀態表延伸為轉態表如下 :

從轉態表求出正反器之輸入方程式 :

 依據輸入方程式繪製電路圖 :

可見上數是取 Q 輸出當正反器輸入, 而下數是取 /Q 輸出當正反器輸入.


範例 5 : 設計一個按照 0, 5, 4, 3, 2, 1 順序循環的同步計數器

此計數器有 6 個狀態, 最大狀態值 5 < 8=2**3, 因此需要三個正反器來記憶狀態值, 其狀態表如下, 0 的次態是 5; 1 的次態是 0; 2 的次態是 1, .... 依此類推 :

其 JK 正反器之激勵表與轉態表如下 :

由轉態表求取輸入方程式 :

依據輸入方程式繪製電路圖完成設計 :

OK, 今天終於把有限狀態機筆記整理完畢, 履行了對學生們的承諾, 不到一周就整理了四篇長篇筆記, 真是太佩服自己了, 有這種毅力我應該也可以去征服宇宙了, 呵呵. 真希望學生們有在看, 明天是期末考, 祝福他們都能 pass, 而被邏輯設計折騰了將近兩個月的我, 也總算解放了.

PS : 有空可以追加的範例 : ripple counter, Johnson counter, shift register 等等.

2021-03-05 補充 :

範例 2 的狀態圖 S1 打錯, 右上角應是 1/0 已修正.