---
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


## Moore FSM 跟 Mealy FSM

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

### Moore

輸出只跟當前的 State 有關

### Mealy

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


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

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

## 簡單的例子

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


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



---

# 紅綠燈 Moore FSM


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

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

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


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

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

## 畫出 Transition 的圖

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


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

## 畫出 State 的真質表

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


## Encoding 以及完成真質表

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

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

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


## Transition Logic 的電路圖


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

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


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


## Output Logic 的電路圖


## 時脈圖

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


:::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 則代表輸入
:::



---

## Mealy

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



---

# 微笑蝸牛

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

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

## Moore 版本


### 真質表與編碼



## 電路圖



## Mealy 版本


### 真質表與編碼


## 電路圖


# 時脈圖


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

---
# Factoring

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


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


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

## 拆解

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



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

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

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

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

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

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