什麼是序向邏輯？

到目前為止你看過的所有電路，輸出只取決於當下輸入的組合—— 不管發生過什麼事，\(1 \land 1\) 永遠是 \(1\)。 這稱為組合邏輯（combinational / combinatorial logic）。 它依然非常有用——第二週做的 ALU，正是之後打造 CPU 時要用的那一顆。

但電腦不是純組合邏輯！電腦會維護內部狀態： 變數的值、程式執行到哪一行、螢幕上的畫面…… 要打造電腦，我們必須更進一步——讓電路能「記住」東西。

R-S 閂鎖的行為

第一個能記住東西的電路是 R-S 閂鎖（R-S latch）。 它沒有（正式的）真值表——因為輸出不完全由輸入決定：

• 前三列是普通的邏輯行為； 但當 \(R' = S' = 1\) 時，輸出維持先前的值——這就是「記憶」！

• \(R' = S' = 0\) 的情況我們不在乎：這不是這個電路的預期用法， 如果發生了就代表出了問題。真值表裡的標準寫法是 X（don’t care）。

• 排除 X 的情況下，永遠有 \(Q' = \lnot Q\)。我們把 \(Q\) 視為主要輸出。

撇號是什麼意思？主動低電位與主動高電位

\(R'\)、\(S'\)、\(Q'\) 上的撇號（\('\)）或橫槓（\(\bar{R}\)）正式上沒有任何意義—— 它們只是慣例，常用於資料手冊（datasheet）， 幫助使用者快速理解不熟悉的電路：

• 撇號在輸出上（如 \(Q'\) 或 \(\bar{Q}\)）：表示它是反相輸出—— \(Q' = \lnot Q\)，其中 \(Q\) 才是「真正的」輸出。

• 撇號在輸入上（如 \(R'\) 或 \(\bar{R}\)）：表示它由 1 變 0 時觸發。 這種輸入稱為主動低電位（active low）。

• 由 0 變 1 觸發的輸入則稱為主動高電位（active high）。

時序圖（Timing Diagrams）

序向邏輯不能只靠真值表——輸出隨時間變化， 所以我們改用時序圖：橫軸是時間，每條水平軌跡代表一個訊號的高低。

逐段解讀（\(Q\) 初始為 0）：

• \(t = 1\)：\(S'\) 由 1 掉到 0（set 觸發）\(\Rightarrow Q\) 變 1； \(t = 2\) 時 \(S'\) 回到 1，進入「保持」，\(Q\) 留在 1。

• \(t = 4\)：\(R'\) 掉到 0（reset 觸發）\(\Rightarrow Q\) 變 0； \(t = 5\) 後保持 0。

• \(t = 7\)：\(S'\) 再度觸發 \(\Rightarrow Q\) 回到 1。

• 全程 \(Q' = \lnot Q\)。

傳播延遲（Propagation Delay）

上面的時序圖包含一個微妙的謊言——訊號在 1 與 0 之間 不會瞬間切換！就算 \(R'\)、\(S'\) 真的瞬間切換， \(Q\) 與 \(Q'\) 也不會——電流通過閂鎖需要時間， 這段時間稱為傳播延遲（propagation delay）。

傳播延遲通常以奈秒（ns，\(10^{-9}\) 秒）或皮秒 （ps，\(10^{-12}\) 秒）計。本課程大多忽略它， 但有時它很重要——例如它是 CPU 時脈速度的限制條件 （第 2 章會看到原因）。

拆開神祕盒子：兩個 NAND 閘

R-S 閂鎖的內部只有——兩個 NAND 閘！ 秘訣在於交叉耦合（cross-coupled）：每個閘的輸出接到另一個閘的輸入。

寫成布林式：\(Q = \lnot(S' \land Q')\)、\(Q' = \lnot(R' \land Q)\)—— 輸出出現在自己的定義式裡，這正是回饋（feedback）。 為什麼這樣就能記憶？逐步追蹤兩種情況：

從閂鎖到正反器（From Latches to Flip-Flops）

R-S 閂鎖的三個問題

R-S 閂鎖很好，但有幾個麻煩：

1. 必須小心不能同時觸發 set 與 reset（\(R' = S' = 0\) 禁區）；

2. 如果能把「下一個狀態是什麼」與「何時改變」分開控制， 時序問題會好想得多；

3. 如果把輸出迴接回輸入，事情會變得一團糟！

前兩個問題用 D 閂鎖（D latch）解決； 第三個問題稍後用 D 正反器（D flip-flop）解決。

D 閂鎖：想要的行為

\(en\)（enable）是主動高電位輸入。 \(en\) 高時，\(Q\) 跟隨 \(D\) 的值；\(en\) 低時，\(Q\) 保持不變。 維持 \(Q' = \lnot Q\)。 ——「存什麼」（\(D\)）與「何時存」（\(en\)）分開了！

用 R-S 閂鎖打造 D 閂鎖

回到基本功：用組合邏輯，讓 \(en\) 與 \(D\) 產生 R-S 閂鎖所需的輸入！ 先把想要的行為翻譯成 R-S 閂鎖的輸入：

讀表可得（各欄何時為 0）： \[\boxed{S' = \lnot(en \land D), \qquad R' = \lnot(en \land \lnot D)}\] 兩條都是 NAND！所以 D 閂鎖 = 4 個 NAND + 1 個 NOT：

注意 \(en = 1\) 時 \(R'\)、\(S'\) 恰為 \(D\) 與 \(\lnot D\) 的 NAND—— 兩者永遠不會同時為 0（結構上互補），禁區問題根除 ✓。

位準觸發與邊緣觸發

位準觸發也能用，但必須非常小心控制 \(en\) 維持高電位的時間長度； 邊緣觸發用起來容易得多。下圖對比同一組輸入下， 位準觸發的 D 閂鎖與正緣觸發的 D 正反器的輸出差異：

D 正反器的內部構造：領導者與跟隨者

負緣觸發比較容易做，先從它開始。 把兩個 D 閂鎖串接，並讓第二個的 \(en\) 經過一個 NOT 閘：

左邊的閂鎖稱為領導者（leader）或 primary， 右邊的稱為跟隨者（follower）或 secondary。 （歷史上分別叫 master 與 slave，但這些詞帶有不好的聯想，正逐漸被淘汰。）

逐步追蹤（假設 \(en\) 一開始為高）：

1. \(en\) 高：領導者輸出跟隨 \(D\)； 跟隨者的 \(en\) 經過 NOT 為低，被停用（輸出不受影響）。

2. \(en\) 落下（負緣）：跟隨者的 \(en\) 變高， 它立刻取用領導者當下的輸出——即 \(D\) 在落緣瞬間的值。 之後 \(D\) 再怎麼變都沒用，因為領導者的 \(en\) 已是低。

3. \(en\) 再升起：關鍵一步——即使 \(D\) 已改變， 新的 \(en\) 訊號穿過 NOT 閘的速度比穿過整個領導者快。 所以跟隨者的 \(en\) 先變低（鎖住），領導者的輸出才更新完成—— 跟隨者的輸出不變。

4. 之後 \(D\) 的變化同樣無效，直到下一個負緣。

整體效果：輸出只在 \(en\) 的負緣更新一次——負緣觸發完成！

那要怎麼改成正緣觸發？——在 \(en\) 前面再加一個 NOT 閘！ 這就是（正緣觸發的）D 正反器（D flip-flop）。

時脈（The Clock）

現在可以一舉解決所有時序問題了！ 我們用單一方波驅動所有電路：時脈（clock），常記作 \(CLK\)。

然後用 D 正反器（及其變體）作為時序問題的緩衝：

時脈術語

• 時脈週期（clock cycle）：相鄰兩個上升緣之間的時間區間。

• 週期時間（time period）：一個時脈週期所花的時間長度。

• 頻率（frequency）：每秒的時脈週期數，單位赫茲（Hz）。 1 Hz = 每秒 1 個週期，且 \[\text{頻率（Hz）} = \frac{1}{\text{週期時間（秒）}}\]

• 例：頻率 20 kHz 的時脈，週期時間為 \(1/20{,}000\) 秒，即 50 \(\mu\)s。

時脈訊號通常由專用電路中的壓電石英晶體（piezoelectric crystal） 產生——用的是我們的宿敵：物理。

SI 詞頭速查

例：1 GHz \(= 10^9 = 1{,}000{,}000{,}000\) Hz。 （位元組 byte 有一個惱人的例外，第 4 章詳談。）

從正反器到暫存器（From Flip-Flops to Registers）

時脈電路的記號

所有電路共用同一個時脈，所以畫圖時常省略時脈線： 邊緣觸發的元件以一個三角形記號標示時脈輸入。 例如 D 正反器（DFF）通常這樣畫：

（右邊省略了時脈線，只留三角形——因為大家都接同一個 \(CLK\)。）

1 位元暫存器

跟 DFF 的差別：DFF 每個上升緣都會更新； 暫存器多了一個 \(load\) 開關，可以選擇「這一拍要不要存」。

一個會失敗的設計

直覺想法：把 \(load\) 和 \(CLK\) 做 AND，接到 DFF 的時脈輸入—— 「\(load\) 高的時候才讓時脈通過」。

這個設計會失敗。原因：這樣一來，\(out\) 是在 \[load \land CLK\] 的上升緣取值，而不是 \(CLK\) 的上升緣。 例如 \(CLK\) 為高的期間 \(load\) 若震盪，\(load \land CLK\) 就會產生一堆假的上升緣，\(out\) 隨之不穩定。

正確的做法：回饋 + 多工器

正確思路：用這一個時脈週期的輸出，經組合邏輯決定下一個週期的輸入。 我們想要的行為（X 表示 don’t care）：

可以展開成完整真值表再用 K-map…… 或者直接看出：這就是一個多工器（multiplexer）！ \(load\) 是選擇位：\(load = 0\) 選舊值（保持）、\(load = 1\) 選 \(in\)（載入）： \[out_{\text{new}} = (\lnot load \land out_{\text{old}}) \lor (load \land in)\]

運作：每個時脈上升緣 DFF 都照常更新（時脈路徑乾乾淨淨）， 但 \(load = 0\) 時它存回的是自己原本的值——效果上就是「保持」。✓

多位元暫存器與匯流排

Hack CPU 用的不是 1 位元而是 16 位元暫存器—— 視為各存放一個 16 位元二進位值。 與其畫 16 條線，我們畫一條帶斜線記號的線， 同樣視為承載一個二進位值。這種「二進位線」稱為匯流排（bus）。 （Logisim 的記號略有不同。）

16 位元暫存器的實作很簡單：16 個 1 位元暫存器並排， 共用同一個 \(load\) 與 \(CLK\)，第 \(i\) 個管 \(in_i \to out_i\)。

從暫存器到 RAM（From Registers to RAM）

記憶體是什麼？

介面行為：

• 讀取：\(out\) 永遠等於地址為 \(address\) 的暫存器所存的值—— 立即生效，不等時脈（讀取是組合邏輯）。

• 寫入：若 \(load\) 為高，則在時脈上升緣， 地址為 \(address\) 的暫存器被設為 \(in\)；\(load\) 低則不變。

關鍵術語：

• 每個暫存器的大小稱為字長（word size）；

• 有效地址的集合稱為地址空間（address space）；

• （大暫存器內部的）每個 1 位元暫存器稱為一個記憶胞（cell）。

怎麼打造記憶體？你已經具備全部零件了—— 用 DEMUX 把 \(load\) 導向被選中的暫存器、 用 MUX 從所有暫存器的輸出中選出 \(out\)（見課程作業！）。

RAM 與 ROM

用正反器蓋出來的記憶體是揮發性（volatile）的： 只有持續供電才能保住資料。 揮發性記憶體也稱為 RAM（Random Access Memory，隨機存取記憶體）—— 這名字出於已不再適用的歷史原因。

非揮發性（non-volatile）儲存則相反：斷電後資料仍在。

• ROM（Read-Only Memory，唯讀記憶體）： 只寫入一次（物理性地改變晶片）的非揮發性記憶體。 優點是成本低、存取快——適合放不可升級的韌體（firmware）。

• Hack CPU 使用 16KB RAM 與 32KB ROM（為了實作簡單）。

• 現代多數非揮發性記憶體是 EEPROM （Electrically Erasable Programmable ROM，電子可抹除可程式化 ROM）， 包括快閃記憶體（flash memory）—— 可以（以 CPU 的時間尺度來說很慢地）抹除並重寫。

SRAM 與 DRAM

我們蓋出來的 RAM 類似 SRAM（Static RAM，靜態隨機存取記憶體）：

• SRAM 用高度精簡的設計，每位元只需 4–6 個電晶體 （我們的做法約需 40 個）；原理相似——只要供電就保住資料。

• DRAM（Dynamic RAM，動態隨機存取記憶體）運作方式完全不同： 資料的儲存方式需要每隔幾毫秒以及每次讀取後手動更新 （refresh）。與 SRAM 相比：更便宜、容量更大，但慢得多。

• 現代電腦兩者都用——本課程稍後（記憶體階層）詳談。

• SDRAM（Synchronised DRAM）是由時脈驅動的 DRAM。 現代 DRAM 全是 SDRAM；它與 SRAM 毫無關係（雖然名字很像）。

• DDR（Double Data Rate）1–5 是一族與 DRAM 之間的 資料傳輸協定，不是根本不同的技術。

儲存容量的 SI 單位

記憶體大小「天生」就是 2 的冪次（地址空間 \(= 2^{\text{地址位元數}}\)）， 所以我們通常用這套以 2 為底的替代單位—— 例如 1KB 指 \(1024\) 位元組而非 \(1000\)：

這樣一來，例如兩條 16GB 的 RAM 可以合併成 32GB—— 只要在地址空間多加一個位元。

附錄：對數複習

對數對我們的用處：想知道需要幾個位元來表示無號數 \(x\)、 或替一個 \(x\) 字的記憶體儲存地址，答案就是 \(\log_2 x\) 向上取整。

計算機通常只有 \(\log_{10}\)（log）或 \(\log_e\)（ln，\(e \approx 2.718\)）。 換底公式：對任何底 \(b\)， \[\log_2 x = \frac{\log_b x}{\log_b 2}, \qquad\text{因為}\quad 2^{(\log_b x)/(\log_b 2)} = \left(b^{\log_b 2}\right)^{(\log_b x)/(\log_b 2)} = b^{\log_b x} = x.\]

另外，\(\log_b x\) 的成長極慢：若 \(\log_2 n \geq 50\)， 則 \(n \geq 1\)PB！所以在演算法分析裡（Programming in C 會看到 \(\log_2 n\) 時間的演算法），可以把 \(\log_2 n\) 當成一個「偏大的常數」， 與其他常數因子互相權衡。 ——這就是你（在這個學位裡）需要知道的所有對數知識！

綜合練習題（附詳解）

練習 1：R-S 閂鎖追蹤

一個 R-S 閂鎖初始 \(Q = 0\)，輸入依序發生： （i）\(S'\) 短暫拉低後回高；（ii）\(S'\) 再度短暫拉低； （iii）\(R'\) 短暫拉低後回高。寫出每步之後的 \(Q\)。

練習 2：撇號慣例

資料手冊上有一顆晶片，腳位標著 \(EN'\)、\(OUT\)、\(OUT'\)。 (a) \(EN'\) 如何觸發？(b) \(OUT'\) 與 \(OUT\) 的關係？ (c) 這些撇號在邏輯上有什麼正式意義？

練習 3：NAND 閂鎖的穩定性驗證

R-S 閂鎖由 \(Q = \lnot(S' \land Q')\)、\(Q' = \lnot(R' \land Q)\) 組成。 驗證 \(R' = S' = 1\) 時，\((Q, Q') = (1, 0)\) 與 \((0, 1)\) 都是穩定狀態， 並說明為什麼 \(R' = S' = 0\) 後同時放開會出問題。

練習 4：D 閂鎖公式推導

從 D 閂鎖的四列行為表出發，推導 \(S'\)、\(R'\) 的公式， 並驗證 \(en = 1, D = 1\) 的情況。

練習 5：位準觸發 vs. 邊緣觸發

\(en\)／\(CLK\) 在 \(t \in [2, 5]\) 為高，其餘為低。 \(D\) 在 \(t = 3\) 由 1 變 0、在 \(t = 4\) 由 0 變 1。 初始輸出為 0。分別寫出 (a) D 閂鎖、(b) 正緣觸發 D 正反器的輸出變化。

練習 6：D 正反器的內部機制

在領導者—跟隨者構造中： (a) 為什麼負緣觸發「比較容易」先做出來？ (b) 「NOT 閘比領導者快」這件事為什麼是必要的？

練習 7：時脈換算

(a) 頻率 2.5 GHz 的 CPU，時脈週期是多少？ (b) 週期 50 \(\mu\)s 的時脈，頻率是多少？ (c) 某電路的最大傳播延遲是 0.8 ns，時脈頻率最高可設多少？

練習 8：為什麼不能 gate 時脈？

有人把暫存器設計成「\(load \land CLK\) 接到 DFF 的時脈腳」。 畫出以下情境並指出錯誤：\(CLK\) 在 \(t \in [2, 4]\) 為高； \(load\) 在 \(t = 2.5\) 由 0 升高、\(t = 3\) 落下、\(t = 3.5\) 又升高。

練習 9：暫存器行為追蹤

一個 1 位元暫存器初始 \(out = 0\)，連續五個時脈上升緣時的輸入為：

寫出每個上升緣之後的 \(out\)。

練習 10：地址位元計算

(a) Hack 的 RAM16K 有 \(16{,}384\) 個 16 位元的字，需要幾個地址位元？ 總共有多少個記憶胞？ (b) 一個記憶體有 100 個字，需要幾個地址位元？ (c) 64 KiB 的記憶體、字長 16 位元，需要幾個地址位元？

練習 11：儲存單位陷阱

(a) 32 GiB 是多少位元組（寫成 2 的冪次）？ (b) 某廠商的「1 TB」硬碟實際是 \(10^{12}\) 位元組，換算成 TiB 是多少？ 少了幾percent？

練習 12：記憶體技術判斷題

判斷並解釋： (a)「SSD 是 ROM 的一種，因為它不是 RAM。」 (b)「SDRAM 是 SRAM 的一種。」 (c)「DDR5 是一種全新的記憶體技術，與 DRAM 完全不同。」 (d)「SRAM 斷電後仍能保住資料。」

附錄：速查表

本週元件總覽

時脈公式

名詞中英對照

參考資料

• John Lapinskas, COMSM1302 Week 3 lecture slides（3-1 至 3-4）， University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems（nand2tetris）， Ch. 3 Sequential Logic（Bit、Register、RAM 系列晶片規格）.

• Wikipedia：Flip-flop (electronics)、Metastability (electronics)、 Static random-access memory、Dynamic random-access memory.

• CMU 15-213 Introduction to Computer Systems 講義： The Memory Hierarchy（SRAM/DRAM 比較）.

• Ginosar, Fourteen Ways to Fool Your Synchronizer（IEEE D&T, 2011） ——亞穩態與同步器的經典教程.