---
# System prepended metadata

title: 第五週
tags: [計概]

---

---
title: 第五週
tags: 計概
---
# 前半部

## Finite State Machine / FSM

![image alt](https://drive.google.com/uc?id=1Tx6tt-BEPe0b4gZYJVmFSI6EhyZ7hehO&export=download)
這是 Right Shift 的 FSM
Moore形式的，請見第七週

以前的電腦都是為了特定的面向而創造
這種就叫做finite state machine

    Transition logic 會接受算好的訊號
    判斷要跳到哪裡(?
    一樣請見第七週
    以前是用tree記錄搭配if else判斷
    但是現在是直接通過一個函數 使用機器學習
    判斷要不要執行

## Markov Model
![image alt](https://drive.google.com/uc?id=1MKUTuSrk3gI5qeIoA6B_QkvWLDESAbOX&export=download)
>不會考
行為只跟當前的狀態有關

做語音 推薦 猜測的系統

## Hidden Markov Model / HMM
![image alt](https://drive.google.com/uc?id=14MXFzEW7Z9FF2YmIOgtBygRKifCsVCk9&export=download)
狀態的序列，也就是馬可夫可以得到的行為序列
在 HMM 上是不能被發現的，但是跟你觀測到的另一個東西
或是外在的行為是相關的
藉此去推測你的機制

用了很多機率
這個東西模擬未來序列很強
序列就是像 基因 語言翻譯

## Recurrent Neural Networks / RNN
![](https://drive.google.com/uc?id=1QWI46bRfudccNJq7efOceC5pm_uBc01d&export=download)
### Sequence to Sequence Model 
![](https://drive.google.com/uc?id=1EE09gH7IV8tbnJHIUQQL-Xfvghtr88bh&export=download)
程式要去猜出中間的函數要長怎樣
LSTM中間的那串比較嚴格複雜
 
最後再決定要跳到哪一個狀態

:::info
語言翻譯中間有個bottle neck
是 STM RNN-based (? 待搜尋

但老師說現在比較常用RNN 還有GRU

>深度學習用了很多線性代數的優化
:::

# Memory
>long term 比較難記憶
目前 D FLIP FLOP 是記憶體的主流
因為用 NAND NOR 成本比較好

Sequential logic 的輸出跟 上一次 以及 當前的 輸入有關
1. State
    用來判斷一個電路未來狀況的資訊
    其實就是當前的狀態
2. State Elements
    可以儲存 State 的電路
    1. Bistablecircuit
    2. SR Latch
    3. D Latch
    4. D Flip-flop
4. Latches and flip-flops
    儲存一個 bit 的 State
    是為一個 state elements
4. Synchronous sequential circuits
    Combinational logic 加上一些 flip-flops
    達到攔截的功能
5. Sequential Circuits
    1. 有一序列的事件(?
    2. 有記憶 短期的記憶
    3. 使用輸出當作給輸入的回饋
        藉此儲存資訊
>老師又提到了三個雜誌
>Communication of ACM
IEEE spectrum
IEEE signal processing-magzine

## Bistable Circuit
![](https://drive.google.com/uc?id=1wd_cyjml-XRftSVrs3mFjhzDQbbzBueM&export=download)![](https://drive.google.com/uc?id=1ueaX4Yexbr3mIEjON5wD99rejyyK3dqo&export=download)
最一開始的構想，可以儲存 1 bit 的 state
可以多拉兩個腳出去表示輸出，但是沒有輸入
![](https://drive.google.com/uc?id=1WEnJ11xG2Q6XejR_gqeXgCyluHy5OlFB&export=download)![](https://drive.google.com/uc?id=120jM9P2Fz4Ai22WKLgGrhg-QNVXpBNHm&export=download)
上面可能儲存的兩種情況
## SR Latch
>老師說 NAND也可以做
>
![](https://drive.google.com/uc?id=1-wE6vgB6GizIE3l2t2WHQOIXO_YLYSzB&export=download)
![](https://drive.google.com/uc?id=1_jveBmD4dVzVCElySJsZ19zi0R61XWXO&export=download)![](https://drive.google.com/uc?id=18aO01Fw1nkw3_XKHSSjPCWzghF7JiH8I&export=download)
當 SR 相異時，就採用當前的輸入

    S 代表的是 Set，使輸出為 1 的意思
    R 代表的是 Reset，使輸出為 0 的意思
![](https://drive.google.com/uc?id=1MyTTzrRPw_aYj9ptXm6NJSMxj9dacZ6j&export=download)
當 SR 都是 0 時，就保留上一次的輸出
也就是儲存的效果
![](https://drive.google.com/uc?id=1m64tHZOnnWypmmZ5dzxbhZ5PIRnsbnW8&export=download)
但是 SR 都是 1 時，會出問題
所以必須做點甚麼避免掉 11 的情況
![](https://drive.google.com/uc?id=1UVV5txnXWpqv4zwFnn5gkvSZ02Lv5lIh&export=download)
這是電路中的表示符號

## D Latch
![](https://drive.google.com/uc?id=1yCZnLlML1Am4a9sg9aMdCGxbhab9xnnX&export=download)![](https://drive.google.com/uc?id=1hhEloCm9yKqRxHJRU0CdEN_vV7sCVfIb&export=download)
>老師說有更多額外的機制去控制
不一定都要用clock

![](https://drive.google.com/uc?id=1wjl9Rq9j3U-IlSUE7XBi7f-fPHgTiMDP&export=download)
使用了 CLK(Clock) 跟 D(Data)作為 input
巧妙的避開了 11 的情況
- 當 CLK 是 1 的時候就讓 D 通過
- 當 CLK 是 0 的時候就保持原本的資料
  或者說，讓SR同時為0

:::warning
但是有一個缺點，就是一旦 CLK 是 1 的狀態
D 就會直接過去，在那期間資料是可以變動的
可是有時候資料必須得同步才不會出錯
於是，為了同步，又有了新的改良
:::

# D Flip-Flop
![](https://drive.google.com/uc?id=1tV0xMy9dnike4loH6mVhtwLNuPsplkvo&export=download)![](https://drive.google.com/uc?id=1E9gf2N19k3BMp2nzWgDIz4uy5ujTFIXU&export=download)
將兩個 D Latch 相連，共用 CLK 
但是做了點變化，有一個是取反的
這樣的用意是：
- CLK 為 0 時，東西都會被擋在第一個 D Latch
- CLK 變成 1 時，原先被擋在第一個 D Latch 的資料就會通過，但是被擋在第二個 D Latch
- 要等到下一次 CLK 轉為 1 時才能通過
這樣可以達到以下需求：
:::info
整體上看來
**只有在 CLK 0 轉為 1 的瞬間
D 才會從 D Flip-Flop 通過**
:::
![](https://drive.google.com/uc?id=1aHuRvcUjxMW7H107TJTYzpReBvSGsdEn&export=download)
這個圖形題目，一定會考；可以看出
1. 延遲
2. 一開始兩個不確定的資料類型
    1. FF 因為只有在改變的瞬間的資料才會通過
        而那當下通過的 D 是 0 所以才都變成 0
    3. L 則是因為會一直受到變動，所以在後面 D 變成 1 時
    也因此變動了值

        


## Enabled Flip-Flops
![](https://drive.google.com/uc?id=1ANe4fadCCHBHEyCU6NO1YuWxCzIAWP4M&export=download)
顧名思義，就是有一個 Enable
- EN = 1 時，D 會通過，也就是正常的 FF
正常的由 CLK 決定要不要通過
- EN = 0 時，改輸出 Q，可以發現 Q 被拉了回來
這時候不論 CLK 要不要讓它通過，都還是原始值，也就等同強制保留

>可以回顧前一週的 MUX 的記號

## Resettable Flip-Flops
![](https://drive.google.com/uc?id=1UxofaglpkrCZcn8BpcLFFrzQ-9LmiS45&export=download)

- Reset = 0 時，D 會通過，也就是正常的 FF
正常的由 CLK 決定要不要通過
- Reset = 1 時，Q 被強制重設為 0 
有兩種：
1. **Synchronous**
    只有當 CLK 切換的瞬間才會 Reset
    **那要怎麼畫呢？**
2. **Asynchronous**
    一旦 Reset 為 1 立馬重設 D

    ![](https://drive.google.com/uc?id=16S87vaCzRt7BfsNQpCJAf1y-tJhhUiL6&export=download)

## Settable Flip-Flops
![](https://drive.google.com/uc?id=1_Yrwlq7impFBFuP7iE0pFImakMXKb3xR&export=download)
- t = 0 時，D 會通過，也就是正常的 FF
正常的由 CLK 決定要不要通過
- Reset = 1 時，Q 被強制設為 1 

    看來電路也是要自己畫
## Clock
![](https://drive.google.com/uc?id=12lpARueVHJnvda0IXau-_XLooQ_gUO4Z&export=download)
通俗來說，一個 Clock 是由 tick + tock  組成
現實中，一個 Clock 是由震盪器 oscillator 產生
>下圖中出現的三角形就是震盪器的意思
>可以做變形(？
>

---

# Register
![](https://drive.google.com/uc?id=1vq9l_y884Pwtn5H9yXEn5Mnc-emYDvM1&export=download)

上圖是一個 4-bit 暫存器
Reg 會共享同個 CLK
一條 node 上有一撇斜線，並寫一個 4 代表是 4 個 bit 的輸入

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

記憶體內，通常修改是一次改一個區塊 WORD
> WORD 是記憶體帶寬 memory bus width
> 通常現在電腦的記憶體是 64-bit

而不是單獨一個 bit 因為成本會變高


---

## Register File
![](https://drive.google.com/uc?id=1lTkoSxSVQ-hnQElDp4JFE4AjDhWYAq_u&export=download)

1. **n × k Register File**
代表有 n 個 Reg，每個 Reg 內有 k bit

2. Read 跟 Write 是指對單一個 Reg 的資料
像上圖中，因為是 16-bit 的 Reg，所以讀寫也是 16-bit
3. 定址的 bit，或者說 Selector，只會在右下角
4. 只有當 CLK (那個三角形)跟 W 是 True 的時候
    Write Data 才會寫入
    
![](https://drive.google.com/uc?id=1vYvkqjZrG9p5ejZ-AK4OVqvwCzMGkssd&export=download)
1. 可以看到在 Write Data 是由 Decoder 搭配定址的 bit 決定要將資料傳到哪一個 Reg
    - 同時搭配CLK跟W組合成...新的CLK
3. Read Data 則是由 MUX 搭配定址的 bit 決定哪個 Reg 的資料要輸出
4. 每個 Reg 共享同個 CLK，符合上面老師說的
    不會一次只修一個 bit ，而是 Reg 內全部的資料
:::info
上面介紹的是一個一個更動資料
但是這樣太慢了，所以有 share 記憶體 
或是 GPU 有 swap 等等
總之
搬遷記憶體是一件麻煩的事
:::
:::success
要注意圖片中
如果線是粗的或有畫斜線
要記得代表該線是有多個 node 的
:::


---

## Counter
![](https://drive.google.com/uc?id=1aLh4_2ySdCECO6DWKo-zgRYuZB_f2fvL&export=download)
1. in：將 state 設為某個基準值
1. inc：每個 clock cycle 增加一次 state
2. load：維持 state 防止超過
3. reset：重設 state

>以上不太確定，老師也沒有講很細

決定現在要執行哪段的機器碼
在記憶體中會有一個queue放著要工作的機器碼，由program counter決定循序
通常往下一階PC會加1
有些還會有判斷

而正在執行的就會載到cpu

---

# Sequential Logic
![](https://drive.google.com/uc?id=1IdTbyAWliEVMvPQdHqNMy39-c18n2lS8&export=download)
![](https://drive.google.com/uc?id=1BZr7-_KXAFoSmjRZrP5M4gQamIUJGaN8&export=download)
會震盪，以及因為 Inverter 產生的短短的 delay
這個情況要避免
而我們的 FF 剛好就是因為
只有在切換的當下才會輸出，所以可以避免這種情形
## Sequential Logic 的 同步法則

### synchronize定義
:::info
system synchronized to the clock
state changes at clock edge
:::

1. 任何一個線路單元 circuit element 要嘛是暫存器，要嘛是combinational circuit
2. 至少要有一個線路單元是暫存器
3. 全部暫存器共享同個 CLK
4. 每個環狀線一定要有一個暫存器（或記憶體）

## 題目：判斷是否同步
![](https://drive.google.com/uc?id=1gf8qHJK9O1yzM3YJjYp3mfV_KQJ5LubA&export=download)
:::success
CL 是 Combinational Logic
也就是像上面提到的 Enable、Resettable、Settable 等等

要注意圖片中
如果線是粗的或有畫斜線
要記得代表該線是有多個node的
:::
- c 沒有同步 因為那是Latch 不能同步
    如果上線在 FF 結果出來前就又傳來資料
    就會產生其他結果

- h 也不是 因為他多了兩個inverter
    跟上面產生震盪的inverter一樣
    會有延遲
    

---

# 總結
下禮拜要把上面那些弄到很熟
因為下禮拜要大量的用

老師有說到 同步的精神就是
CLK 會把 Combination Logic 的值卡在記憶體的外面
只有 CLK 變動的瞬間發生的 才是真的
~~其他都是假的~~
