---
title: Reduction of State Tables and State Assignment|第十四週
tags: 數位系統與實驗
---

# "0101/1001" Detector

這是一個會偵測 0101 或 1001 的偵測器；不過現在的例子比較簡單，是讀到了 4 個 bit 才會進行判定，不像之前的例子是讀到一個 bit，會搭配前面 3 個 bit 進行判定。


那麼如果換我們自己建構的話，要怎麼建構呢？有一個方法就是用樹列出所有可能，但是這樣會有太多餘項：


所以當我們轉成 State Table 的時候，會看到有很多項的 Next State 都是一樣的，並且可以注意到連輸出也是一樣的：


那麼我們就有一個比較值觀的化簡方法，就是將 Next State 一樣並且輸出也一樣的視為一樣的 State；例如上圖除了 J 跟 L 之外， H 到 P 都會被視為同個 State，而 J 跟 L 會被視為同個 State：


所以上圖可以看到我們把他們都單一個 State 代表，於是我們的表格就變得簡潔許多；同時可以發現，D 也因此跟 G 變成同個 State，所以我們又可以重複上述的動作，得到下圖：


而這些圖畫出來的話，就會得到我們上面原先的 State Graph。

# Equivalent State

如果任意兩個 State，不管他們是在同個 Machine，還是不同 Machine，若且為若，**接下來的所有全部 Input**：

- 會得到相同 Output

則這兩個 State 就是 **Equivalent State**。

但是如果要用上面的定義去判定兩個 State 是不是 Equivalent State 有點困難，所以我們有了下面的 Theorem。

## Theorem

如果任意兩個 State，不管他們是在同個 Machine，還是不同 Machine，若且為若，**下一次的任意 Input**：

- 會得到相同 Output
- Next State 為 Equivalent

則這兩個 State 就是 **Equivalent State**。

可以看到這個理論告訴我們，只需要檢查下一次的輸出跟 Next State，就可以知道是不是 Equivalent State。

所以如果確認了輸出是一樣的，那麼我們就只要檢查 Next State 就可以了，這有種交棒給 Next State 的感覺，或者跑遞迴的樣子。

## 例子


例如在上面的例子中，首先我們可以觀察出，S~1~ 鶴立雞群，就他一個人在四種輸入的情況下，輸出都有跟其他三個人不一樣，所以可以知道他跟另外三個人一定不是 Equivalent State。

所以接下來我們檢查 S~0~ 跟 S~2~，可以看到他們輸出都是一樣的，於是我們看看他們的 Next State 是不是 Equivalent State：
- 輸入為 00 的時候，Next State 都是 S~3~，所以之後只要確認 S~3~ 是不是 Equivalent State 就好
- 輸入為 01 的時候，互為彼此的 Next State ，所以我們再往下檢查
- 輸入為 10 的時候，都是 S~1~，所以遇到跟輸入為 00 時一樣的情形，繼續往下檢查
- 輸入為 10 的時候，可以看到一個為 S~0~ 一個為 S~1~，而一開始我們就知道 S~1~ 不會跟所有人是 Equivalent State
- 因此我們就知道 S~0~ 跟 S~2~ 就不是 Equivalent State

總之往下檢查後，可以發現每個人跟另外三個人都不是 Equivalent State。

# Implicant Table

我們需要一個系統性的方式來檢查 Equivalent State，也就是我們的 Implicant Table，首先請看我們的 State Table：


然後我們根據 State Table，建立我們的 Implicant Table，建立方法為：

- 對應到任兩個要等價的 State 的格子，然後列出他們對應要等價的 Next State


例如上面的第 B row 第 A col，如果 A 跟 B 要是等價的，那麼根據 State Table 可以知道：

- D 跟 F 也要是等價的
- F 跟 H 也要是等價的

但是可以看到，第 C row 第 A col，由於 A 跟 C 的輸出並沒有一樣，所以我們畫上了 X。
同時可以看到，第 D row 第 A col，裡面存在「A 跟 D 要是等價的」這一列，這個就跟原本的要求一樣，所以不用考慮。

## 檢查

也就是根據表格中的 X，把其他已經列出來的情形判定出是不是 X：


例如第 B row 第 A col，他的要求是：

- D 跟 F 也要是等價的
- F 跟 H 也要是等價的

但是如果我們查表的話，可以看到第 D row 第 F col 是 X，因此第 B row 第 A col 那格就可以畫上 X。

以此進行下去，會先做好第一輪的去除；接著進行第二輪，直到沒有可以畫上 X 的，他們就是 Equivalent State。

>有種玩數獨的感覺

所以我們的 Equivalent State 就是圖中的 C 跟 E 和 A 跟 D。


所以我們就可以把表格變得清爽一些。

## Two Machine

接下來給個 Two Machine 的例子：


我們根據上面一樣的原則，建立出表格：


例如，如果 A 跟 S~1~ 要是 Equivalent State，則：

- B 跟 S~3~ 也要是 Equivalent State
- A 跟 S~1~ 也要是 Equivalent State

然後進行一樣的畫數獨步驟，把表格畫上更多 X，就會得到上面的結果。

最後一樣，剩下來的就是 Equivalent State：

$$
A \equiv S_{2}\\
B \equiv S_{0}\\
C \equiv S_{3}\\
D \equiv S_{1}\\
$$

## DC

當然也可以加入 DC 討論，此時的自由度就更大了。我們可以把某個 State 的 DC 固定成某個輸出，讓他跟另一個 State 輸出一樣，以湊成可能的 Equivalent State，方便我們找出更簡潔的 Machine


# State Table 跟 Transition Table

其實這兩者是不同的 Table，前者是單純 State 的 Table，後者則是賦予 Code 的 Table。

也就是說，我們進行 State Assignment 後才可以產生 Transition Table


上面就是 State Table 。


上面是根據最常見的 Coding 得到的 Transition Table。也就是看最少用幾個 bit 去給每個 State 一個值。

$$
S_{0} = 000\\
S_{1} = 110\\...
$$

最後再根據我們的 Transition Table，看要以哪種 FF 實作，搭配下面的表格，就可以得到前幾周的結果了。


# Equivalent State Assignments

注意這裡不是 Equivalent State 的 Assignments，而是 Equivalent 的 State Assignments。
簡單來說就是等價的線路，例如：


上面的 DFF，你把 D 取反，其實就跟把 Q 和 Q' 反接會得到一樣的結果。

---

# State Assignment

由於我們實作 Sequential Circuit 的方法，可以用很多種 FF，所以 State Assignment 就成了一門學問，因為好的 State Assignment，可以讓你的各個閘變得很清爽，但是不好的 State Assignment 就會讓你的各個閘變得很冗餘。

也就是說，在卡諾圖上，好的 State Assignment 可以讓 0 跟 1 很靠近，很好化簡。

以下是一些準則，但是只適用於 DFF 跟 JKFF，不適用於 TFF 跟 SRFF。

將以下情形的 State 給予相鄰的 bit，或者說 Adjacent assignments

- 如果兩個 State 吃到同個 Input 會有相同 Next State
- 如果兩個 State 為同一個 State 的其中兩個 Next State
- 如果兩個 State 有相同的輸出

上面依序為下圖：


# One-Hot State Assignment

計概的老朋友。

以上次的某個 State Graph 為例子：


假如我們給三個 State 進行 One-Hot 編碼，也就是說：

| State | Q~0~ | Q~1~ | Q~2~ |
|:-----:|:----:|:----:|:----:|
| S~0~ | 1 | 0 | 0 |
| S~1~ | 0 | 1 | 0 |
| S~2~ | 0 | 0 | 1 |

則我們的 Next State 會變得很直觀：

$$
Q_{0}^{+} = F'R'Q_{0} + F'RQ_{1} + FQ_{2} \\
Q_{1}^{+} = F'R'Q_{1} + F'RQ_{2} + FQ_{0} \\
Q_{2}^{+} = F'R'Q_{2} + F'RQ_{0} + FQ_{1} \\
Z = Z_{0}Q_{0} + Z_{1}Q_{1} + Z_{2}Q_{2}\\
$$

因為 One-Hot 編碼的關係，所以其實 Q~i~ 就代表著 S~i~；也就是說，Q~i~ 為 1 代表進入到了 S~i~。

因此上面的 Q~0~^+^ 就可以翻譯為：

如果要讓 Q~0~^+^ 等於 1，或者說如果要進入 S~0~，那麼：

- 要嘛原先就在 S~0~，並且 F'R' 為 1
- 要嘛原先就在 S~1~，並且 F'R 為 1
- 要嘛原先就在 S~2~，並且 F 為 1

並且，上面是 Moore 的 Machine，輸出變得更簡潔了