---
title: Derivation of State Graphs and Tables|第十三週
tags: 數位系統與實驗
---

# 如何畫出 Finte State Machine / FSM

老師說，有時候打造一個 FSM 是蠻靠直覺的，順著你對問題的理解，依照直覺寫出來，然後同時確認邏輯是正確的就對了。

當然課本有給一些建議：

- 先畫出一些例子幫助自己理解題目要的條件
- 就很像寫題目的時候自己想一些測資那樣子
- 然後想一下甚麼狀態會回到 Initial State，然後也可以先定義怎樣是 Initial State
- 如果很多情況都會讓輸出都是 1，那麼可以直接來構建
- 或者去想有什麼樣的情況是必須要被記錄的，這樣的話他就是一個 State
- 當要建立一個箭頭的時候，要去想清楚到底是要接到已經建立的 State，還是要建立新的 State
- 建立好後，要確認每次接到一個輸入，不會讓你走到兩種 State 以上，或是讓你無法移動到任何 State 包括自己
- 畢竟 FSM 就是你接到一個輸入，就一定會跳到下一個 State

但是老師還是建議照著自己的直覺與正確的邏輯，會比較容易打造。

## 例子：010 和 1001 偵測器

假如我們現在要打造一個偵測器，在最近的 3 個 bit 他偵測到 010 的話就會輸出 1；或者在最近的 4 個 bit 他偵測到 1001 的話就會輸出 1。其他都是輸出 0。

下面的敘述請搭配著圖來看：


- S~0~：初始狀態，或者說 Reset。
- S~1~：讀到了 0。由於 S~0~ 是 Reset，所以可以知道當前狀態是：
- 0
- 而不是 10 或 100
- S~2~：讀到了 1。由於 S~1~ 是讀到 0，所以可以知道當前狀態是：
- 01
- S~3~：讀到了 0。由於 S~2~ 是讀到 1，所以可以知道當前狀態是：
- 10
- S~4~：讀到了 1。由於 S~0~ 是 Reset，所以可以知道當前狀態是：
- 1
- 而不是 01，01 是 S~2~
- S~5~：從 S~3~ 之後讀到 0，所以可以知道當前狀態是：
- 100

---

# Serial Data Transmission

在傳送數據的時候，除了要傳送的序列數據，我們還會連同 CLK 一起傳送，這樣接收方才知道要不要讀入該值；但是有時候我們不是直接傳 CLK 過去，而是某種程度包含在我要傳的資料「裡面」，所以我們會需要給他還原。


## Coding schemes

下面介紹幾種常見的對資料編碼的方式，初始值都是 0：

- NRZ：就是讀到的資料 D，沒有任何改變
- NRZI：如果讀到的 D 是 0，代表「不會改變」，但如果讀到的是 1，代表「要改變」
- 一開始讀到的 D 是 0，所以就不改變 0，然後讀到了 1，所以把 0 改變得到 1
- 然後又讀到 1，所以再把 1 改變得到 0
- RZ：就是把讀到的資料 D ，如果讀到 1 就拆成兩半，讀到 0 保持 0
- Manchester：把讀到的資料 D 都拆成兩半，讀到 1 拆成 10，讀到 0 拆成 01


## Schemes Conversion


假如我現在有一個 NRZ 的資料，我想要把他轉成 Manchester 編碼，下面用我們學到的兩種 FSM 實作：

## Mealy

由於從 NRZ 一次讀到的 1 個 bit，在 Manchester 中長度會變成兩倍，也就是等同讀到兩個 bit，所以可以看到我們的狀態圖長相非常簡單。


例如 S~0~ 從 NRZ 讀到 一個 1，但是其實對 Manchester 來說是讀到 2 個 1，所以可以看到我們是先跳去 S~2~，輸出 1，然後又跳回來，輸出 0。

下面就是時序圖當中，第二行的 Manchester 是我們想要達成的目標，而底下的 Z 是我們藉由 Mealy 達成的樣子；可以看到樣子很像，不過多了一些 Glitches。


## Moore

如果換成用 Moore 來實作的話樣子也差不多，然後也會因為 NRZ 的 1 個 bit 等同 Manchester 的 2 個 bit 的原因，可以看到 S~0~ 跟 S~3~ 之間和 S~1~ 跟 S~2~ 之間都有雙向箭頭。


下面的時序圖也可以看到我們使用 Moore 打造出沒有 Glitch 的 Z；不過因為 Moore 完全只有在 CLK 變動時會更改值，這裡是 Falling 才會更改值，所以整體向右移動了一個 CLK。


---

# Alphanumeric State Graph

有時候狀態不一定要用 0 跟 1 來表示，我們可以用字母來表示想要輸出的值，例如：


其中 F Forward 代表前進， R Reverse 代表後退。

但是用字母表示的時候，要小心少判斷情況，像上面的例子中，其實有可能 FR 同時為 1 或同時為 0，但是我的狀態圖並沒有說明這種時候要跳到哪裡，所以我們有了更完整的版本：


像這樣把全部的判斷做好，比較正確。可以看到這裡有給予優先順序，要先看 F 是不是 1。

## Completely Specified State Graph

如果上面的用字母表示的狀態圖，符合下面兩個情形，那麼我們就保證這個狀態圖每次都只有一條路可以走：

- 把全部的路徑可能情況 OR 起來，並且結果得到 1
- 以上面的例子來說就是 F + F'R' + F'R
- 這個可以很明顯的看出結果是 1
- 代表說我考慮了全部的狀態，任何 input 進來我都可以判斷
- 從任何一個狀態出去的路徑，任兩個的情況 AND 起來，並且結果得到 0
- 以 S~0~ 作為例子，可以知道有下面 3 種選擇：
- $F'R'\bullet F$
- $F'R'\bullet F'R$
- $F'R\bullet F$
- 這些都是 0，代表我一次只有一條路可以走