---
# System prepended metadata

title: 第七週
tags: [計概]

---

---
title: 第七週
tags: 計概
---

:::warning
如果真質表太多Don't Care，通常就不會把那些情況寫出來
此時畫卡諾圖是最好的解法，因為：
除非你擁有一顆超強大腦，不然你很難hold住全部可以消掉的可能性

如果真質表沒有Don't care，可以嘗試使用人腦，也就是直接寫出SOP並化簡
通常數量少的例子用人腦即可解決，但是遇上甚麼4X4或5X4的，一樣：
除非你擁有一顆超強大腦，不然你很難巧妙的使用布林邏輯法則消掉可以消的部分
:::


考試跟作業很像，複習嘿嘿

Synchronous 的是最好偵錯的

# FSM

是用來達成特定應用的電路，由兩大部分組成

## Combinational logic

也就是下圖左邊的 ==Transition Logic== 以及右邊的 ==Output Logic==
Transition，顧名思義，就是負責轉換 State
會根據當前的 state 和 input 決定出 Next State
而這個 Next State 會被擋在 CLK 前面，直到 CLK 從 OFF 切到 ON 的瞬間
Output 則會根據當前的 State 去產生輸出

## State register

也就是下圖中間的 ==State memory==，儲存著當前的 State

![](https://drive.google.com/uc?id=1OvA1DoL6LllBM-iG-NI16mVayNZjWX0c&export=download)

## Moore FSM 跟 Mealy FSM

根據==決定輸出的方式==，又分為 Moore FSM 跟 Mealy FSM

### Moore 

輸出只跟當前的 State 有關

### Mealy

Mealy 除了跟當前 State，也跟輸入有關

![](https://drive.google.com/uc?id=18vpURlPgSKPE91ZF6QKDXFFoU1-vZG3G&export=download)

可以看到 Mealy 的輸出是從 State 跟 input 拉線去做判斷

Moore 比 Mealy 容易偵錯，且比較簡單，但是比較沒有彈性

## 簡單的例子

下面是一個只有 State 沒有 Input 的 FSM

![](https://drive.google.com/uc?id=1_0ExRIg9SCJSRui6ZfG0zfwUDKt_Mywy&export=download)

那他的 Transition Logic 的輸入就只有當前的 State
於是老樣子，畫出真質表，用卡諾圖化簡；沒有的狀態，下一個狀態就是don't care
最後就可以得到 Transition Logic 的布林邏輯，你就可以兜出電路圖了

![](https://drive.google.com/uc?id=1UlDCjb3XBqzb84hO_lVyEwMiriOJy7Dg&export=download)

![](https://drive.google.com/uc?id=1gjF9kdFrLOmDHKR6spG-l_1dHrkA5sv3&export=download)


---

# 紅綠燈 Moore FSM

![](https://drive.google.com/uc?id=1MyzlPOX3ywP3cARFI4YhCHOd5erENZim&export=download)

T (traffic) 是感應器，作為輸入
L 是燈，作為輸出

## 規則
1. 如果一條路是綠燈，另一條就是紅燈
2. 如果綠燈路的感測器一直感應到車，就一直是綠燈
3. 如果綠燈路的感測器一感應到沒車，就一轉為黃燈
4. 一旦燈號轉為黃燈，就換轉為紅燈，另一條燈變為綠燈

:::warning
此處的紅綠燈暫不考慮時間
:::

![](https://drive.google.com/uc?id=1r8H2q0dLLADDVGOBiMTz9jTGUJBTy14E&export=download)

:::info
Reset 目的是代表最一開始的情況，主要像是斷電後首次通電
通常題目或是要求，應該要先給你 Reset 後要進入什麼狀態
:::

像下圖就是 Reset 後進入 State 0 (S~0~)

## 畫出 Transition 的圖

就是照著上方的規則
去判定從一個 State 到下一個 State 需要甚麼條件，以及會輸出甚麼
像 S~0~ ，如果 T~A~ 是 True ，就一直保持 S~0~
所以會有一個回到自己的圈圈

![](https://drive.google.com/uc?id=1Fnr3n1BS0kL5zUTqy8vd2-CGscBhkTj0&export=download)

並且可以發現，輸出，也就是燈號，只跟當前的 State 有關
所以是 Moore FSM

## 畫出 State 的真質表

先畫出從一個 State 到下一個 State 的真質表
>沒用到的就是 Don't care，包括在用卡諾圖化簡時

![](https://drive.google.com/uc?id=1lRZnab6c_CTaqStuRoJkAo8AYTJbk2dR&export=download)

## Encoding 以及完成真質表

此時有一個重要的步驟，==Encoding==
也就是幫 State 決定如何表示

這裡需要表示四種 State ，所以就直覺性的用 2 個 bit 表示
>這叫做 complex 法，最下面會提

於是，輸入是4個bit，在下面的電路圖可以看到 S 會拉回去

![](https://drive.google.com/uc?id=1B4TtEW13Vi-9sCUTluslAMUkLlGt5zIL&export=download)

## Transition Logic 的電路圖

![](https://drive.google.com/uc?id=1lKD3cXQxdgEtA64GMTS2kA1atejjilcI&export=download)

## Output Logic 的 Encoding 以及完成真質表

跟 Transition 一樣的步驟，畫出 State 跟 Output 的真質表

![](https://drive.google.com/uc?id=1lN1SyRE6Um1DzDXN-p-upYdVfH7k5G85&export=download)

然後得出布林邏輯，你就可以兜出線路了

![](https://drive.google.com/uc?id=161PMRgREyIwAwUyPNW7I4ahKUIKxUp3F&export=download =50%x)![](https://drive.google.com/uc?id=1PsnqTqfb56TDNsL079Cdtag2v262D9pC&export=download =40%x)

## Output Logic 的電路圖

![](https://drive.google.com/uc?id=1zkkA67LeFFX5lcGqxOmwaD3Qx5s934yp&export=download)

## 時脈圖

加入CLK的判斷
由於 State 有多個 bit ，所以就只能用訊號交叉表示 State 的改變

![](https://drive.google.com/uc?id=1kK2cqVGUs3GqP1xUN80_jEAE3TyzzYxY&export=download)

:::success
ALU的建構基本概念其實跟FSM一樣
不過他們在架CPU的時候需要大量的拆解
:::

---

# ONE HOT

就是用一個 bit 表示一個state
也就是說，有四個 State ，你就用 4 bit 表示各個 State
分別為 0001 0010 0100 1000

通常會讓next state 跟 output 邏輯比較簡單(?
代價是你要畫出一堆東西來

# Meanly FSM

## 回顧一下 moore

:::info
通常state的代號會寫在裡面
而斜線 / 的右邊代表輸出
A/0 代表 A state 輸出 0
線旁邊的 01 則代表輸入
:::

![](https://drive.google.com/uc?id=1T2JoBY4kocDyCbTcXDh7zzllD9Xku9eb&export=download)

![](https://drive.google.com/uc?id=1aC7i2NeqjniiUxEcUxv7ZytNbvycZQmQ&export=download)


---

## Mealy

:::info
線旁邊多了斜線 / ，代表有輸出
:::

![](https://drive.google.com/uc?id=13YuyW7LTqwBy7B-T3b-fMn6Ir01OaHtl&export=download)

![](https://drive.google.com/uc?id=1e4XYudF_6q6VswA6JiIOJU1K3Flfvi14&export=download)


---

# 微笑蝸牛

有一隻蝸牛，他在吃01苔癬，如果連續吃到01這兩個苔蘚
也就是先吃到0，後又吃到1，就會微笑

我們嘗試畫出這隻蝸牛的 FSM ，用苔癬代表輸入；並以0跟1表示輸出不微笑和微笑

## Moore 版本

![](https://drive.google.com/uc?id=1DGRNrZi-GfJKkylhqu4az5xaQOmuf7O2&export=download)

### 真質表與編碼

![](https://drive.google.com/uc?id=1hMvCP7do4wodDDvyPESawHU9MFRLjtaW&export=download)

![](https://drive.google.com/uc?id=1l2Ua2EQPpz7yT9XyRbmPqfB-GMP3OI__&export=download =50%x)![](https://drive.google.com/uc?id=1y1UuICyJtGz8rPVaTq9nxaICT5D-o4N0&export=download =50%x)

## 電路圖

![](https://drive.google.com/uc?id=1EELCA5EU2UkRupPEv8pLjJ-XJY_pPe-P&export=download)


![](https://drive.google.com/uc?id=1VPXB0aeTD3Knw5ZE55g-n6dbeS-Y62Pb&export=download)

## Mealy 版本

![](https://drive.google.com/uc?id=1BtVKZZSGEgSt6fvgJ2VYw8165gDhkNvt&export=download)

### 真質表與編碼

![](https://drive.google.com/uc?id=1azPS_LrwQH4OsGB8XLLYXDlgggbILP67&export=download)

## 電路圖

![](https://drive.google.com/uc?id=1WAIGuxRocr66qjZnUg2NQ1kNExob1n6F&export=download)

# 時脈圖

![](https://drive.google.com/uc?id=1WVAyNzFRNV9j8g5YbOHv1yyxo3K9FyTQ&export=download)

可以發現，因為mealy跟input有關，會被ff擋下來的只有next state
所以output 不會aline with clock，反應比較早一點

---
# Factoring

如果上面紅綠燈的例子，多了Parade mode 遊行模式
P = 1 ，代表有遊行，縱的那條路永遠綠燈，橫的那條路完全紅燈
R = 1 ，代表沒有遊行，也就是正常的紅綠燈模式

![](https://drive.google.com/uc?id=1gvVz3ToQL8IS0RcMcUJc8i7g-lOqVgAP&export=download)

如果直接畫出每個 Transition 的 State 圖，會出人命

![](https://drive.google.com/uc?id=1EVjP9jRBJY27XZjFU7qkj6j0zr9KEjhM&export=download)

所以要將他拆解，這個技巧叫做 Factoring

## 拆解

將遊行模式的判定跟一般模式拆開來；遊行模式的判定會產生一個 input 給一般模式

![](https://drive.google.com/uc?id=1cucXuzBwyYhox4R7-dfm0PHxmaINoQk6&export=download)

![](https://drive.google.com/uc?id=1_77jfkWa9G-mUGi98xe4pDSOxpqm2sqM&export=download =50%x)![](https://drive.google.com/uc?id=1eEwjdTi74y2eajYeiWcOWKHd65nQLWQP&export=download =50%x)

可以發現，只要稍微修改一般模式的 state 判定，也就是下面的 S~2~、S~3~
就又是一尾活龍

:::info
老師說建議 Encoding 用 complex 不要用 one hot
:::

:::success
**Map reducer**
講搜尋引擎利用page rank
找你要的網頁，但是需要處理由rank
得到的龐大矩陣

**Sparse coding**
Ma Yi 
數學的optimization 

老師說，很常會遇到你發現你是對的
但因為太前衛，所以被大咖期刊給reject
你就因此退縮。但是不能因此退縮

考試在103
考試直接寫在考卷上
:::
