2.1 二進位與數位邏輯基礎#

學習目標#

理解為何電腦採用二進位表示資訊，並能進行二進位、十六進位與十進位之間的轉換。
掌握布林代數的基本運算，理解布林代數與邏輯閘之間的對應關係。
能夠從布林函式出發，組合邏輯閘建構半加器、全加器，進而理解 ALU 的構成。
認識組合邏輯與序向邏輯的差異，理解時脈與暫存器在數位系統中的角色。
建立「數學（布林代數）→ 電路（邏輯閘）→ 運算單元（ALU）→ 處理器」的驅動關係圖像。

2.1.1 為什麼是二進位？#

電腦的核心問題是：如何用物理裝置可靠地表示與運算資訊？

十九世紀的機械計算器使用十進位齒輪，但電子裝置天生不適合十進位。要在電路中區分十種電壓準位，雜訊稍微一干擾就會讓「3」變成「4」。相對地，若只區分兩種狀態——高電壓（1）與低電壓（0）——兩者之間的電壓間隔可以設計得非常寬，即使雜訊造成一定程度的電壓漂移，接收端仍能正確判讀。這就是數位化（digitalization）的本質：用離散的、粗略的準位取代連續的類比訊號，以換取極高的抗雜訊能力。

數學基礎則可追溯到 1854 年英國數學家喬治・布林（George Boole）出版的《思維法則》（The Laws of Thought）。布林證明了邏輯推理可以完全代數化——用一套只包含 0 與 1 的代數系統描述「真」與「假」的運算。1937 年，MIT 的碩士生克勞德・夏農（Claude Shannon）在其著名論文《繼電器與開關電路的符號分析》中指出：開關電路的串聯與並聯，恰好就是布林代數中的 AND 與 OR。這篇論文是數位電路設計的起點——從此，任何邏輯命題都可以機械化地轉成電路，任何電路也都可以用代數化簡。軟體（邏輯）與硬體（電路）從此擁有共同語言。

二進位與我們熟悉的十進位只是「基底」不同。十進位中，數字 \(1357\) 表示 \(1\times10^3+3\times10^2+5\times10^1+7\times10^0\) ；同理，二進位數 \(1011_2\) 表示：

\[ 1011_2 = 1\times2^3 + 0\times2^2 + 1\times2^1 + 1\times2^0 = 11_{10} \]

由於 \(2^4=16\) ，每四位二進位數恰好對應一位十六進位數，因此硬體工程師習慣用十六進位作為二進位的「縮寫」。例如 32 位元的 1011 0100 1101 0010 ... 可以寫成 0xB4D2...。電腦領域還有兩個慣例：1 個位元組（byte）= 8 位元；1 KiB = \(2^{10}\) 位元組、1 MiB = \(2^{20}\) 位元組（硬碟廠商常用的 1 MB = \(10^6\) 位元組，請注意區分）。

負數的表示：二補數（Two's Complement）。減法若用「正負號位元」表示法，需要額外的減法電路。二補數表示法則巧妙地把減法變成加法： \(n\) 位元整數 \(x\) 的相反數定義為 \(2^n - x\) 。以 4 位元為例， \(-3\) 表示為 \(16-3=13=1101_2\) 。此時加法器不用修改， \(3+(-3)=0011+1101=10000\) ，捨棄第五位進位後得 0000，正是零。二補數的算術解讀是：最高位元的權重為 \(-2^{n-1}\) 而非 \(+2^{n-1}\) ：

\[ 1101_2 = -8 + 4 + 1 = -3 \]

這個表示法只有一個零、減法免費、且硬體最簡單，因此成為所有現代處理器（包括 x86 與 RISC-V）的整數標準表示法。本書第 5 章將看到，RISC-V 的條件分支指令（blt、bge）都以二補數的符號解讀位元。

2.1.2 布林代數：數位電路的文法#

布林代數只有三種基本運算：

運算	符號	定義	恆等式示例
AND（及）	\(\cdot\) 或省略	全真才真	\(x\cdot 1 = x\)
OR（或）	\(+\)	有真即真	\(x + 0 = x\)
NOT（非）	\(\overline{x}\)	取反	\(\overline{\overline{x}} = x\)

更重要的是幾條「化簡律」，它們是電路最佳化的依據：

分配律： \(x\cdot(y+z) = x\cdot y + x\cdot z\) （注意：布林代數中 AND 也能分配到 OR，與一般代數不同！）
笛摩根定律（De Morgan's Laws）： \(\overline{x+y} = \overline{x}\cdot\overline{y}\) ， \(\overline{x\cdot y} = \overline{x}+\overline{y}\)
吸收律： \(x + x\cdot y = x\)

笛摩根定律在硬體上意義重大：NAND 閘（NOT+AND）在 CMOS 製程中是所有閘中最簡單、最省電、最快的，任何布林函式都可以只用 NAND 閘實現。這解釋了為何實際晶片中 NAND 閘數量遠多於其他閘——布林代數給了工程師「代數等價、電路更省」的轉換自由。

2.1.3 邏輯閘：布林代數的物理化身#

邏輯閘是把布林運算做成實體電路的基本元件。MOS 電晶體在本質上是一個「由電壓控制的開關」：NMOS 在閘極為高電壓時導通，PMOS 則相反。用電晶體搭建 CMOS 電路的基本手法是：上拉網路用 PMOS（輸出拉到 1），下拉網路用 NMOS（輸出拉到 0），兩個網路互為笛摩根對偶。

以 2 輸入 NAND 為例：下拉網路是兩個 NMOS 串聯（A 與 B 都為 1 時輸出接地），上拉網路是兩個 PMOS 並聯（任一為 0 時輸出接電源）——這正是 \(\overline{A \cdot B}\) 。現代 CPU 中數十億顆電晶體，就是靠這個簡單模式堆疊出來的。

布林函式	邏輯閘	電晶體數（CMOS）
NOT	反相器	2
AND	及閘	6
OR	或閘	6
NAND	反及閘	4
多工器 MUX	選擇器	12–20

多工器（Multiplexer, MUX）值得特別注意：它有資料輸入 \(D_0, D_1, \ldots\) 與選擇訊號 \(S\) ，功能是「根據 \(S\) 選一條路」：

\[ Y = \overline{S}\cdot D_0 + S \cdot D_1 \]

MUX 是資料路徑的「鐵路轉轍器」——之後你會看到，整個處理器的資料路徑就是由大量 MUX 組成，由控制訊號決定資料要從哪裡流向哪裡。2.2 節將談到的「控制單元」，其實就是產生這些 MUX 選擇訊號的電路。

2.1.4 從加法器到 ALU：邏輯閘的第一次大集結#

有了邏輯閘，我們能做的第一件真正「像電腦」的事，就是加法。

半加器（Half Adder）：將兩個一位元 \(a, b\) 相加，輸出和 \(s = a \oplus b\) （異或：相異為真）與進位 \(c = a\cdot b\) 。兩個閘就搞定。但半加器無法接收上一位傳來的進位，無法串接。

全加器（Full Adder）：多一個進位輸入 \(c_{in}\) ：

\[ s = a \oplus b \oplus c_{in}, \qquad c_{out} = a\cdot b + c_{in}\cdot(a \oplus b) \]

將 \(n\) 個全加器串起來，把每個的 \(c_{out}\) 接到下一個的 \(c_{in}\) ，就得到 \(n\) 位元的漣波進位加法器（Ripple-Carry Adder）。它的缺點是延遲隨位元數線性增長——最高位的結果要等進位「漣波」傳過所有位元。為此工程師發明了進位前瞻（Carry-Lookahead）電路，用代數技巧提前算出各級進位，把延遲從 \(O(n)\) 降到 \(O(\log n)\) 。這是「用布林代數化簡換取電路速度」的經典範例。

有了加法器，再加上一點邏輯，就能組出 ALU（Arithmetic Logic Unit，算術邏輯單元）。一個簡化的 1 位元 ALU 長這樣：並聯計算 AND、OR、Adder 的結果，最後用一個 MUX，由兩位元控制訊號 \(F_1F_0\) 決定輸出哪一個：

\(F_1F_0\)	功能
00	AND
01	OR
10	ADD
11	SUB（加法器 + \(b\) 取二補數）

減法如何實作？利用二補數的性質 \(a - b = a + \overline{b} + 1\) ：把 \(b\) 每個位元反相（NOT 閘），再把最低位的 \(c_{in}\) 設為 1 即可。做法是給加法器每個 \(b\) 輸入加一個「二元選擇」： \(Binvert=0\) 時送 \(b\) ， \(Binvert=1\) 時送 \(\overline{b}\) ，同時 \(c_{in}=Binvert\) 。這樣 ADD 與 SUB 共用同一個加法器硬體——硬體復用的美學，將貫穿整門課。

flowchart LR
    A["布林代數<br/>(Boole, 1854)"] -->|Shannon 1937| B["邏輯閘<br/>(CMOS 電晶體)"]
    B --> C["組合電路<br/>加法器 / MUX / 解碼器"]
    C --> D["ALU<br/>算術邏輯單元"]
    D --> E["資料路徑 + 控制單元<br/>(+ 暫存器, 時脈)"]
    E --> F["處理器<br/>執行指令集"]

2.1.5 組合邏輯 vs 序向邏輯：時脈與記憶#

以上電路有一個共同特徵：輸出只由當前輸入決定，稱為組合邏輯（combinational logic）。但電腦必須有記憶——指令一個接一個執行，中間結果必須被「記住」。這需要序向邏輯（sequential logic）：輸出不只依賴當前輸入，還依賴過去的狀態。

最小的記憶元件是正反器（flip-flop）：用兩個反相器交叉耦合即可儲存一個位元，再加上閘控制「何時允許寫入」。關鍵設計是邊緣觸發（edge-triggered）：只在時脈訊號從 0 跳到 1（上升緣）的瞬間接受寫入，其餘時間輸出保持不變。

這個設計讓整台電腦可以同步運作：

flowchart LR
    R["暫存器檔案<br/>(序向邏輯)"] -->|"當前狀態"| C["組合邏輯<br/>(ALU, 加法器)"]
    C -->|"新狀態"| R
    CLK["時脈 CLK"] -.->|"統一節拍"| R

在每個時脈週期內：暫存器輸出舊值 → 組合邏輯（如 ALU）計算出新值 → 下一個上升緣把新值寫回暫存器。時脈頻率的上限，就是週期內最長那條組合邏輯路徑的延遲（稱為關鍵路徑，critical path）。這正是為什麼把運算拆成多個簡短階段、用管線（pipelining，見第 4 章）同時推進，能大幅提升時脈頻率——你現在已經具備理解它的全部基礎。

2.1.6 硬體描述語言：用「寫程式」的方式設計晶片#

現代晶片動輒數億個邏輯閘，不可能徒手畫電路。工程師用硬體描述語言（HDL）如 Verilog 或 VHDL，以文字描述邏輯行為，再由綜合工具（synthesis tool）自動轉成邏輯閘網表。例如一個 4 位元加法器可以寫成：

module adder4(input  logic [3:0] a, b,
              output logic [3:0] sum,
              output logic       cout);
  assign {cout, sum} = a + b;   // 綜合器會自動選擇加法器結構
endmodule

請特別注意思維方式的轉變：HDL 的每一行描述的是「同時存在的硬體連線」，而非「依序執行的指令」。本書附錄將用 SystemVerilog 實作簡化的 RISC-V 處理器，把本章與下一章的知識全部串起來。

本章小結#

電腦選擇二進位，是為了用寬鬆的雙準位電壓換取抗雜訊能力；布林代數（1854）經夏農（1937）連結到開關電路，成為軟硬體的共同數學基礎。
二補數表示法讓減法免費、加法器電路通用，是所有現代處理器的整數標準。
布林代數 → 邏輯閘（NAND 為基本積木）→ 組合電路（加法器、MUX）→ ALU → 資料路徑 → 處理器，這條驅動鏈是本書的主軸。
MUX 是資料路徑的轉轍器，控制訊號驅動 MUX；減法以「取反 + 進位入 1」與加法共用硬體。
序向邏輯（邊緣觸發正反器）+ 時脈，讓組合邏輯分節拍推進；時脈上限由關鍵路徑延遲決定。

習題#

將十進位數 156 轉為二進位與十六進位；再將十六進位數 0x3C 轉為二進位與十進位。
以 8 位元二補數計算 \(-52\) 的表示法，並用加法器驗證 \(52 + (-52) = 0\) （寫出每一步進位）。
用布林代數化簡 \(F = x\,y + x\,\overline{y} + \overline{x}\,y\) ，並畫出化簡前後的邏輯閘電路，比較所需閘數。
設計一個 1 位元全減器（輸入 \(a, b, b_{in}\) ；輸出差 \(d\) 與借位 \(b_{out}\) ），寫出真值表與布林式，並說明如何用「二補數加法」的觀點簡化它。
某組合邏輯路徑延遲為 800 ps。若改為四級管線、每級延遲約 200 ps（外加 20 ps 暫存器開銷），理想加速比為多少？時脈頻率各為多少？