從閘到元件：抽象階梯

事情已經複雜到不能再用一顆顆 NAND 來思考了！ 我們必須把東西抽象成元件（components）／子電路（subcircuits）—— 多工器、加法器、暫存器、邏輯閘；只有在 NAND 恰好是對的工具時才用 NAND。 而這些元件本身又會成為更大元件的一部分……直到蓋出整台電腦。

暫存器作為積木：計數器（Counter）

怎麼用 16 位元暫存器蓋出 16 位元計數器？ 沿用上週暫存器的思路——寫一張非正式的「真值表」， 用輸入與上一拍的輸出 \(out_{\text{old}}\) 表達想要的下一拍輸出 \(out_{\text{new}}\)：

兩個現成工具： \(out_{\text{old}} + 1\) 用加法器算（第二週！）； 「若 0 則 \(x\)、否則 \(y\)」的選擇邏輯用多工器（第二週！）：

資料流：暫存器輸出 \(out\) 回饋給「\(+1\)」加法器； MUX 依 \(reset\) 在「\(out_{\text{old}} + 1\)」與常數 0 之間二選一， 餵回暫存器（\(load\) 恆為 1）。每個上升緣自動前進一步。

正反器作為積木：單觸發（One-Shot）

（\(in\) 在 \(t \approx 2.3\) 變高並持續到 \(t \approx 5.6\)； \(out\) 只在 \(t = 3\) 的上升緣輸出一拍的 1。） 用途：開機時初始化暫存器、把使用者的長按按鈕轉成方便處理的單拍訊號等。

怎麼用正反器蓋？訣竅是把電路的行為拆解成「狀態」， 存進正反器／暫存器。

狀態圖（State Diagrams）

我們想要單觸發做三件事： (a) 等待 \(in\) 出現 1；(b) 送出一拍脈衝；(c) 等 \(in\) 回到 0，再回到 (a)。 畫成圖（節點 = 狀態，上為名稱、下為該狀態的輸出；箭頭 = 輸入觸發的轉移）：

逐一對照需求：\(S0\) =「等待 1」（輸出 0）； 看到 1 進入 \(S1\) =「送脈衝」（輸出 1，只停留一拍）； 若 \(in\) 仍是 1 進入 \(S2\) =「等待 0」（輸出 0，防止重複觸發）； \(in\) 回 0 才回到 \(S0\)。

打造單觸發（Moore 版）

用兩個正反器 \(XY\) 存狀態：\(S0 = 00\)、\(S1 = 01\)、\(S2 = 10\)。 寫出狀態轉移真值表與輸出真值表：

（狀態 \(11\) 不存在，全部填 X——don’t care 讓化簡更自由。）讀表化簡： \[X_{\text{new}} = (X_{\text{old}} \lor Y_{\text{old}}) \land in, \qquad Y_{\text{new}} = \lnot X_{\text{old}} \land \lnot Y_{\text{old}} \land in, \qquad out = Y.\] 逐條驗證：\(X_{\text{new}} = 1\) 的兩列（\(011\)、\(101\)）都滿足 「舊狀態非 \(S0\) 且 \(in = 1\)」✓； \(Y_{\text{new}} = 1\) 只有一列（\(001\)）：「舊狀態是 \(S0\) 且 \(in = 1\)」✓； 輸出直接取 \(Y\)（利用 don’t care 把 \(11\) 當 1 也無妨）✓。

更好的單觸發：Mealy 機

這樣就最佳了嗎？絕對不是！有很多技巧可以做得更好， 例如非常小心地選擇狀態編碼方式。

這裡示範一招：把輸入本身也存進一個正反器， 讓輸出可以同時依賴舊狀態與舊輸入—— 也就是讓輸出依賴狀態之間的轉移，而不只是狀態本身。

箭頭上的「\(1/0\)」表示：輸入 1 時發生此轉移，輸出 0。 這稱為 Mealy 機（Mealy machine）。 Moore 機與 Mealy 機都是有限狀態機 （finite state machine, FSM）的例子。

實作這台 Mealy 機所需的真值表：

狀態的意義簡化成「上一拍的輸入」； 輸出 =「上一拍輸入是 1、而再上一拍不是」——正是上升緣偵測！ 成本：1 個正反器 + 1 個 AND + 1 個 NOT（Moore 版要 2 個正反器與更多邏輯）。 好多了！還能再省：用狀態正反器的 \(Q'\) 輸出取代 NOT 閘。

通用的 Moore／Mealy 架構

任何 Moore／Mealy 機都能用下列架構實作：

不那麼正式的狀態圖

假設要做一台販賣機： (a) 等使用者輸入零食編號的第一位數字； (b) 等第二位數字，或按「返回」清除第一位； (c) 等投入足夠的錢，或按「返回」取消交易； (d) 出貨（若沒按「返回」）並找零，回到 (a)。

這不會是「純」Moore 或 Mealy 機——例如金額要用暫存器追蹤， 而不是把每種金額都畫成一個狀態。 但我們仍然可以、也應該用追蹤內部狀態的方式來蓋這個電路。

有限狀態機在寫程式時也非常有用， 可以大幅簡化複雜的控制邏輯——例如平台遊戲 Celeste 的角色移動邏輯（原始碼已公開）就是圍繞一台 有限狀態機組織的！

電晶體（Transistors）

從類比到數位

到目前為止我們把電子訊號當成離散的 ON／OFF。 但現實中它們是連續的物理量（例如導線上的電壓）： 邏輯 0 用 0V 表示、邏輯 1 常用 5V 表示…… 那電壓是 0.0001V 或 4.9999V 怎麼辦？

由於電訊號本質連續、必有微小變異， 實際上我們把一段（小）電壓範圍視為邏輯 0 或邏輯 1。 不過我們對精確物理不感興趣，所以把這種連續邏輯抽象掉， 改用離散變數思考：

隨著電晶體愈做愈小，\(V_{dd}\) 也逐步調低——省電、並避免過載燒壞它們！ （5V 是早期標準；現代 CPU 核心電壓已降到 1V 上下。）

矽與半導體

兩大類電晶體：BJT（雙極性接面電晶體）與 MOSFET（金氧半場效電晶體）——本課程看後者。

MOS 電晶體由矽（silicon）製成。矽是半導體（semiconductor）， 也是地球上含量第二豐富的元素。 半導體有個獨特性質：某些條件下導電、其他條件下絕緣（阻斷電流）。 透過摻雜（doping）引入雜質， 可以改變「需要什麼條件才會形成導電通道」。

n 型與 p 型電晶體

摻雜可以給矽結構多餘的電子或電洞（hole） （「該有電子的位置缺了一個電子」）， 造出兩種 MOS 電晶體：

CMOS 邏輯

最簡單的例子：CMOS NOT 閘（反相器）—— 一個 pMOS 疊在一個 nMOS 上，兩個 gate 接在一起當輸入：

• \(A = 0\)：pMOS ON（接通 \(V_{dd}\)）、nMOS OFF \(\Rightarrow Q = 1\)；

• \(A = 1\)：pMOS OFF、nMOS ON（接通 \(V_{ss}\)）\(\Rightarrow Q = 0\)。

注意：必須有到 \(V_{ss}\) 的連接——沒有連接 = 沒有訊號！ （輸出任何時刻都必須被上拉網路或下拉網路恰好其中之一驅動。）

NAND vs NOR：用電晶體蓋邏輯閘

CMOS 閘的設計配方

要用電晶體蓋更複雜的邏輯，我們要設計兩條路徑：

• 上拉網路（pull-up network）：用 p 型電晶體， 定義「什麼時候輸出接到 \(V_{dd}\)（輸出 1）」；

• 下拉網路（pull-down network）：用 n 型電晶體， 定義「什麼時候輸出接到 \(V_{ss}\)（輸出 0）」。

兩條路徑必須互補：任何輸入組合下， 恰好一條形成完整導電通道——輸出永遠是明確的 0 或 1。

工具箱：電晶體串聯 = 「兩個都 ON 才通」（AND 條件）； 並聯 = 「任一個 ON 就通」（OR 條件）。

NOR 閘

真值表：只有 \(A = B = 0\) 時輸出 1。 所以上拉（輸出 1）的條件是「\(A = 0\) 且 \(B = 0\)」 \(\Rightarrow\) 兩個 pMOS 串聯； 下拉（輸出 0）的條件是「\(A = 1\) 或 \(B = 1\)」 \(\Rightarrow\) 兩個 nMOS 並聯：

逐一檢查四種輸入（ON/OFF 狀態）：

任何時刻恰好一條路徑導通——互補成立 ✓。

NAND 閘

同樣的流程：只有 \(A = B = 1\) 時輸出 0。 上拉條件「\(A = 0\) 或 \(B = 0\)」\(\Rightarrow\) 兩個 pMOS 並聯； 下拉條件「\(A = 1\) 且 \(B = 1\)」\(\Rightarrow\) 兩個 nMOS 串聯：

結構速度：為什麼 NAND 是工業標準？

NAND 和 NOR 都用「2 顆並聯 + 2 顆串聯」的相似設計， 為什麼業界標準是 NAND？兩個物理事實：

1. 串聯比並聯慢：電流要依序穿過兩顆電晶體才能到達輸出 （電阻加倍）；並聯只要穿過一顆。

2. p 型比 n 型慢：電洞在矽晶格中的移動速度 比電子慢（載子遷移率低，約差 2–3 倍）。

把兩張表疊起來看：

NOR 的問題：\(V_{dd}\) 訊號要穿過串聯的 p 型電晶體—— 最慢的元件用最慢的接法，是全場最糟的組合。 NAND 則把串聯留給快的 n 型、讓慢的 p 型並聯——兩害相權取其輕。

SRAM vs DRAM：記憶胞的內部構造

SRAM 記憶胞

SRAM 記憶胞的核心是兩個交叉耦合的反相器（cross-coupled inverters）： \(Q\) 餵進一個反相器產生 \(\lnot Q\)、\(\lnot Q\) 再餵回另一個反相器產生 \(Q\)…… 形成雙穩態（bistable）迴圈，位元值就「卡」在裡面 （若 \(Q = 0\) 則 \(\lnot Q = 1\)、於是 \(Q = 0\)……自我維持）。 這跟第三週 NAND 閂鎖的回饋原理一模一樣！

一個 SRAM 記憶胞有兩條輸出線：bitline 與 \(\lnot\)bitline。 當 wordline 輸入為高，它連接的兩顆 n 型存取電晶體都導通， 資料值就能傳入或傳出 bitlines（讀與寫共用同一組線）。

完整電路裡每個反相器就是第 2 章的 CMOS NOT（2 顆電晶體）， 所以標準 SRAM 記憶胞共 \(2 \times 2 + 2 = 6\) 顆電晶體—— 即業界所稱的 6T cell。

DRAM 記憶胞

位元值存在一顆電容（capacitor）上： 充電 = 存 1、放電 = 存 0。 一顆 n 型電晶體把電容接上 bitline：

只有 1 顆電晶體 + 1 顆電容（1T1C）—— 比 SRAM 的 6 顆便宜、緊湊得多。但代價是：

• 導通電晶體去讀或寫時，電容會放掉一些電 （讀取是破壞性的，讀完要寫回）；

• 就算不碰它，電晶體關著也會漏電流—— 所以即使不存取，也必須定期 refresh（每隔幾毫秒充回去）。

三種揮發性記憶體的比較

我們已看過三種揮發性儲存：正反器、SRAM、DRAM。怎麼比較？

• 正反器：資料位元立即出現在輸出——最快； 但要 12–30 顆電晶體，成本、功耗、面積都貴。

• DRAM：延遲比 SRAM 長，因為 bitline 沒有電晶體主動驅動——必須等電荷（相對緩慢地） 從電容流到 bitline；但 1T1C 便宜又緊湊。

• SRAM：4–6 顆電晶體，存取時間介於正反器與 DRAM 之間。

哪種記憶體「最好」？——取決於設計的速度、成本與功耗需求！ （這正是下週記憶體階層的伏筆：三種全都用，各司其職。）

綜合練習題（附詳解）

練習 1：計數器追蹤

一個 4 位元計數器（行為同第 1 章）初始值為 1101， 連續五個上升緣時 \(reset\) 依序為 \(0, 0, 1, 0, 0\)。 寫出每個上升緣之後的輸出（二進位與十進位）。

練習 2：幫計數器加功能

替計數器加一個輸入 \(load\) 與資料輸入 \(in\)（優先序：\(reset > load >\) 計數）。 寫出非正式真值表，並說明硬體上要怎麼改。

練習 3：單觸發 Moore 機追蹤

Moore 版單觸發（\(S0{=}00\)、\(S1{=}01\)、\(S2{=}10\)，公式見第 1 章） 初始在 \(S0\)，輸入序列 \(in = 1, 1, 1, 0, 1, 0\)（每拍一個）。 寫出每一拍結束後的狀態與該拍輸出。

練習 4：驗證單觸發的邏輯式

用第 1 章的轉移真值表逐列驗證 \(X_{\text{new}} = (X_{\text{old}} \lor Y_{\text{old}}) \land in\) 與 \(Y_{\text{new}} = \lnot X_{\text{old}} \land \lnot Y_{\text{old}} \land in\)。

練習 5：設計一台 Moore 機——連續兩個 1 偵測器

設計 Moore 機：輸入序列中最近兩拍都是 1 時輸出 1。 畫狀態圖、選編碼、寫轉移／輸出真值表並化簡。

練習 6：Mealy 版連續兩個 1 偵測器

用 Mealy 機重做練習 5，比較狀態數。

練習 7：Moore vs. Mealy 觀念題

(a) 兩者輸出各依賴什麼？ (b) 為什麼說 Mealy 的輸出「快一拍」？ (c) 什麼情況偏好 Moore？

練習 8：電晶體開關行為

(a) 完成表格：nMOS／pMOS 在 gate \(= 0/1\) 時的 ON/OFF。 (b) 為什麼 CMOS 用 pMOS 上拉、nMOS 下拉，而不是反過來？

練習 9：設計 3 輸入 NAND 的電晶體電路

描述 3 輸入 NAND 的上拉與下拉網路，並給出電晶體數。 一般的 \(n\) 輸入 NAND 呢？

練習 10：AND 閘為什麼要 6 顆電晶體？

(a) 為什麼 CMOS 不能用 4 顆電晶體直接做 AND？ (b) 那 AND 怎麼做？(c) 由此解釋第一週「NAND 是天然積木」的深層原因。

練習 11：NAND vs NOR 速度論證

不看講義，完整重建「NAND 比 NOR 快」的論證鏈。

練習 12：SRAM／DRAM 觀念題

(a) SRAM 記憶胞如何存住一個位元？wordline 的角色？ (b) DRAM 為什麼必須 refresh？兩個原因。 (c) 為什麼 DRAM 讀取比 SRAM 慢？ (d) 一顆 16 Ki \(\times\) 8 位元的 SRAM 晶片（6T cell）， 存儲陣列約需多少電晶體？換成 DRAM 呢？

附錄：速查表

FSM 設計流程

1. 畫狀態轉移圖（規格的抽象實作）；

2. 選狀態編碼（二進位／one-hot／Gray…）；

3. 寫轉移與輸出真值表（不存在的狀態填 X）；

4. 化簡邏輯（K-map 或觀察）；

5. 接線：時脈儲存 + 組合邏輯 + 回饋。

CMOS 閘電晶體數

\(n\) 輸入 NAND／NOR：\(2n\) 顆。CMOS 單級只能做反相函數。

記憶體技術對照

名詞中英對照

參考資料

• John Lapinskas, Building with flip-flops and registers（4-1）， Kira Clements, Transistors／NAND vs NOR／SRAM vs DRAM （4-2 至 4-4），COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems（nand2tetris）， Ch. 3（Counter／PC 晶片）.

• MIT 6.111 Introductory Digital Systems Laboratory： Finite State Machines 講義（狀態編碼、Moore/Mealy level-to-pulse）.

• Harris & Harris, Digital Design and Computer Architecture—— CMOS 閘設計與 FSM 章節.

• Wikipedia：Logical effort、CMOS、 Static random-access memory、Dynamic random-access memory.

• Maddy Thorson & Noel Berry, Celeste 玩家控制原始碼 （公開的 Player.cs，FSM 實例）.