第3章：数字逻辑——从逻辑门到计算机

叙事密度：中高 | 主语言：C | 问题驱动 | 卷三·地心篇

---

元数据卡

属性	内容
卷号	Vol 3 — 深入计算机系统
章节	第3章：数字逻辑
前置	Vol 2（算法与数据结构）；基础电路常识
后置	第4章：CPU 与 ISA
理论深度	（4/5）
C 相关度	≈0%（本章用 C 讲底层抽象，而非运行时）
核心模型	开关网络 → 布尔函数 → 组合/时序电路

---

你在哪

"不知不觉，你已到达地心最底层。这里没有软件，只有硬件——逻辑门像岩石一样层层叠叠，从最简单的与/或/非门到复杂的 ALU。你意识到每个 CPU 指令背后，都是这些基本门的排列组合。"

上一卷结束时，你刚从算法森林里钻出来。递归树的枝叶还在眼前摇曳，动态规划的表格仍然在脑海里自动倒腾着索引——每秒钟几百万次操作，用 C 写出的函数调用链可以嵌套几十层。

但有个问题，你一直没想透：

"这几百万次操作……底层的 '几百万' 是从哪来的？"

C 的 ++i 是一条语句。编译器把它吐成几条指令。指令被 CPU 吃掉。CPU 的时钟每秒钟震荡几十亿次——每个节拍，晶体管开关一次。

晶体管？开关？

对。最底层的计算机，本质上是一张巨大的开关网络。 它不是魔法，不是黑箱，是 0 和 1 按照布尔代数编织起来的逻辑迷宫。

从这一章开始，你要爬进这张迷宫的最深处，手摸到硅片上最原始的几何：逻辑门。

---

你的任务

本章分层

• 必读：从晶体管（开关）到逻辑门（AND/OR/NOT/NAND）的抽象；半加器→全加器→加法器的搭建直觉；D 触发器与寄存器的“记住状态”原理
• 选读：多路选择器与译码器如何“选择”信号路径；时钟信号如何同步所有部件
• 深水区：布尔代数化简与卡诺图；静态冒险与亚稳态 本章不会要求你掌握
• 布尔代数的严格公理体系化简（如奎因-麦克拉斯基算法）
• 建立时间/保持时间的物理成因与 STA（静态时序分析）
• FinFET / GAAFET 等先进制程工艺细节

本章结束时，你将可以：

1. 徒手写出任意布尔函数的真值表与逻辑门实现
2. 用 NAND 门拼出半加器和全加器
3. 解释多路选择器和译码器如何"选择"信号的路径
4. 对比 SR 锁存器与 D 触发器的行为差异
5. 理解时钟信号为什么是所有数字电路的"心跳"

这不是理论课。我们目标很具体——用手头的几根导线和几个逻辑门，搭出能计算的电路。

---

遭遇战 1：从开关到布尔

问题

走廊尽头是一盏灯和两个开关。你要设计一个电路：无论哪个开关的状态改变，灯都翻转——就是卧室门口和床头那种双控开关。

用 C 来描述，无非是：

int light = switch_a ^ switch_b;   // XOR

可是没有 CPU 之前，你要怎么实现这个 ^？

解法：继电器—晶体管—逻辑门

第一代"开关"是继电器。 电磁铁一通电，衔铁吸合，电路通断就变了。但继电器有机械部件，咔嗒咔嗒的频率撑死了几百赫兹。

晶体管改变了一切。 它本质上是一个 没有活动零件的开关——基极（或栅极）的电压控制着集电极和发射极之间是否导通。

把一堆晶体管按照特定方式连起来，你就得到了逻辑门：

门	C 表达	行为口诀
AND &	a && b	全 1 出 1
OR |	a || b	有 1 出 1
NOT !	!a	反转
NAND	!(a && b)	全 1 出 0
NOR	!(a || b)	全 0 出 1
XOR ^	a ^ b	相异出 1

其中 NAND 是万能的——仅用 NAND 就能构造出所有其他门。这是数字电路的第一条根本定理。

// 用 NAND 拼其他门
// NAND(a,b) = !(a && b)
int Not(int a)   { return NAND(a, a); }           // 自反
int And(int a, int b) { return Not(NAND(a, b)); } // NAND + NOT
int Or(int a, int b)  { return NAND(Not(a), Not(b)); } // De Morgan

观察：上面的 C 代码本身就是一种"硬件描述"——它恰好映射到物理门的连接方式。

真值表：逻辑门的身份证

每一个逻辑门都可以用真值表彻底描述。以半加器为例——它把两个二进制位相加，输出和（Sum）与进位（Carry）：

A	B	Sum (A⊕B)	Carry (A·B)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

深水区：以下内容面向对数字逻辑有更深兴趣的读者。主线只需要知道布尔代数存在、以及它能帮助简化电路即可。

获得技能：布尔代数化简

同或操作 ==：!(a ^ b)，等价于 (a & b) | (!a & !b)。

布尔代数有三大公理体系：

• 交换律：A·B = B·A, A+B = B+A
• 结合律：A·(B·C) = (A·B)·C, A+(B+C) = (A+B)+C
• 分配律：A·(B+C) = A·B + A·C, A+B·C = (A+B)·(A+C)

还有两个极其好用的武器：

德摩根定律（De Morgan's Laws）：

!(A && B) = !A || !B
!(A || B) = !A && !B

吸收律：

A + A·B = A
A · (A + B) = A

这看起来就是高中数学——但它在硬件层面决定了你的芯片有多少个晶体管、多少根导线。少一个门，省一部分面积。在台积电 3nm 工艺里，"省一个门"意味着在地球上放进了更多的人造神经元。

---

遭遇战 2：组合逻辑——没有记忆的计算

问题

你有两个 8 位的二进制数 a[7:0] 和 b[7:0]。你要把它们加起来。怎么用逻辑门实现？

C 里面一句话的事：

uint8_t sum = a + b;

但硬件里没有 + 运算符。你得用门搭出来。

半加器 → 全加器 → 行波进位加法器

先解决 1 位：

Sum    = A ⊕ B
Carry  = A · B

这就是 半加器（Half Adder）。

如果考虑到来自低位的进位 Cin：

Sum    = A ⊕ B ⊕ Cin
Carry  = A·B + (A⊕B)·Cin

这就是 全加器（Full Adder）。

把 8 个全加器串联——低位的 Carry 输出接到高位的 Cin 输入——就得到一个 8 位行波进位加法器（Ripple-Carry Adder）：

// 软件模拟
int full_adder(int a, int b, int cin, int *sum, int *cout) {
    *sum  = a ^ b ^ cin;
    *cout = (a & b) | ((a ^ b) & cin);
    return *cout;
}

int add_8bit(int a, int b) {
    int carry = 0;
    int result = 0;
    for (int i = 0; i < 8; i++) {
        int ai = (a >> i) & 1;
        int bi = (b >> i) & 1;
        int si;
        carry = full_adder(ai, bi, carry, &si, &carry);
        result |= (si << i);
    }
    return result;
}

注意：这个 for 循环在硬件里是一排金属导线——每个全加器的进位输出直接焊到下一个的进位输入。没有循环变量，没有迭代，物理连的。

行波进位加法器的代价：进位要一站一站传过去。8 级门延迟 = 8t_pd。64 位就要 64 级。这就是为什么现代 CPU 用超前进位加法器（Carry-Lookahead Adder）。

多路选择器——信号的路由员

你想从 8 个输入信号里选一个出来：

// C 语言：switch 或条件表达式
uint8_t mux8_1(uint8_t sel, uint8_t in[8]) {
    return in[sel];
}

硬件里：用 多路选择器（Multiplexer, MUX）。

一个 2-to-1 MUX：

Y = (S == 0) ? A : B
  = (!S · A) + (S · B)

以这个为积木，可以搭出 4-to-1、8-to-1——构建一棵选择树。

译码器——把"地址"变成"选通"

n 位输入，2ⁿ 位输出——只有一个输出为 1。3-to-8 译码器：

A₂	A₁	A₀	Y₇~Y₀
0	0	0	00000001
0	0	1	00000010
...	...	...	...
1	1	1	10000000

译码器 + 使能线 = 你电脑里的内存地址选通。CPU 送出一个地址，译码器选通一行 DRAM 单元，数据就出来了。

---

常见陷阱：搭一个 4 位二进制加/减法器

把前面的工具凑在一起。

目标是：输入 A[3:0]、B[3:0]，加/减控制位 Sub（0=加，1=减）。

减法等价于：A - B = A + (~B + 1) = A + 补码(B)。

所以：

1. 当 Sub=1 时，把 B 的每一位取反，并且进位输入设为 1
2. 这刚好等于一个 加法器的 Cin 复用做 Sub 控制：

int ALU_AddSub(int a, int b, int sub) {
    int carry = sub;   // 关键：进位注入
    int result = 0;
    for (int i = 0; i < 4; i++) {
        int ai = (a >> i) & 1;
        int bi = (b >> i) & 1;
        int b_xor = bi ^ sub;       // Sub=1 时取反
        int si;
        carry = full_adder(ai, b_xor, carry, &si, &carry);
        result |= (si << i);
    }
    return result;
}

20 个逻辑门。2 个 4 位输入。1 位控制。这，就是 CPU 里 ALU 的原型。

---

遭遇战 3：时序逻辑——记住状态

问题

组合逻辑没有记忆。输入变了，输出立刻变。但计算机需要状态——变量、寄存器、内存——这些东西必须"记住"值。

SR 锁存器——最原始的存储单元

把两个 NOR 门交叉耦合：

         S ──┤NOR ├─ Q
         ┌──┤    │
         │  └────┘
         │
         │  ┌────┐
         └──┤    │
         R ──┤NOR ├─ ~Q
              └────┘

行为：S（Set）和 R（Reset）激活时强制改变输出。当 S=R=0 时，锁存器保持当前状态。

问题来了：S=R=1 同时出现时，Q = ~Q = 0，两个输出一样——打破了"互补"的约定。这叫不允许状态。

D 触发器——时钟同步的解药

SR 锁存器的一个大问题：S 或 R 一变，Q 立刻变——异步的。

D 触发器在输入路径上加了时钟和边沿检测：

CLK ↑ 时：Q = D
其他时间：Q 保持不变

这个"只在时钟上升沿采样"的设计，是整个数字系统的基石。

// D 触发器的行为模型
int d_flipflop(int d, int clk, int *prev_clk, int *q) {
    if (clk == 1 && *prev_clk == 0) {  // 上升沿
        *q = d;
    }
    *prev_clk = clk;
    return *q;
}

寄存器——8 个 D 触发器手拉手

// 8 位寄存器
struct Register8 {
    int q[8];
    int prev_clk;
};

void reg_write(struct Register8 *r, int clk, int data[8]) {
    for (int i = 0; i < 8; i++) {
        r->q[i] = d_flipflop(data[i], clk, &r->prev_clk, &r->q[i]);
    }
}

你刚刚描述了 CPU 里寄存器文件的基本单元。对，就是你用的 int a; 在硬件里的样子。

---

遭遇战 4：时钟与同步——让一切有序

问题

组合逻辑的传播有延迟，时序逻辑需要"恰好在正确的时间点"采样结果。你不可能用手去控制每一个门的时序——需要用一个全局节拍器来同步所有部件。

时钟信号

时钟（Clock）就是一个方波：周期性地在 0 和 1 之间震荡。

    ┌─┐   ┌─┐   ┌─┐
    │ │   │ │   │ │
───┘ └───┘ └───┘ └───

• 时钟周期：一次完整高低震荡的时间
• 占空比：高电平占周期的比例（通常 50%）
• 上升沿：0→1 跳变（大部分触发器在此采样）
• 下降沿：1→0 跳变

为什么需要时钟？

考虑一个加法器 + 寄存器的反馈回路：

寄存器 → 加法器 → 寄存器

没有时钟的节拍约束，加法器的输出一产生就"冲"进寄存器——连锁反应，系统崩溃。

有时钟的话：

1. CLK 上升沿：寄存器输出旧值 A
2. 加法器传播：在半个到几个时钟周期内算出 A + B
3. 下一个 CLK 上升沿：新值写回寄存器

只要时钟周期 > 组合逻辑的最大传播延迟，一切就同步。

这就是冯·诺依曼结构的基本时序契约。

// 时钟驱动的计算
void clock_tick(struct State *s, int clk) {
    // 上升沿：锁存新的输入
    if (rising_edge(clk, &s->prev_clk)) {
        s->pc   = s->next_pc;   // 程序计数器更新
        s->regs = s->next_regs; // 寄存器更新
    }
    // 组合逻辑在电平期间传播
    s->next_pc   = compute_next_pc(s->pc, s->inst);
    s->next_regs = execute_alu(s->inst, s->regs);
}

注意：赋值不是瞬间的，它发生在时钟上升沿那一瞬间。 在你的 C 程序里，a = b + c; 在底层就是：等待一个时钟上升沿，锁存器写入新值。

---

通关挑战

用 VCD 或波形思想完成以下练习（纯纸面也可以）：

挑战 1：只用 NAND 门画出一个 XOR 门的原理图，列出真值表。

挑战 2：用 4 个 2-to-1 MUX 搭一个 4-to-1 MUX。

挑战 3：一个 4 位行波进位加法器，输入 A = 1011₂ (11), B = 0110₂ (6), Cin=0。逐步写出每一级的进位和输出。

挑战 4：比较 SR 锁存器和 D 触发器在以下输入序列下的输出行为：

时间点	SR: S,R	DFF: D, CLK
t₀	0, 0	0, ↑
t₁	1, 0	1, —
t₂	0, 0	1, ↓
t₃	0, 1	0, ↑
t₄	0, 0	1, ↑

---

验收标准

学完本章后，你应当能正确回答：

1. [ ] 为什么 NAND 是万能逻辑门？用 NAND 搭出 AND、OR、NOT。
2. [ ] 用 C 风格的真值表写出半加器和全加器的逻辑表达式。
3. [ ] 解释"行波进位"为什么慢，画出超前进位的思路（选出哪个进位最迟）。
4. [ ] 时钟周期长度受什么因素制约？
5. [ ] 如果去掉所有触发器（把时序电路全变成组合电路），计算机还能工作吗？

如果不能，回退到对应"遭遇战"重读。

---

常见卡点

卡点	解释
"NAND 是万物之源有点反直觉"	实际上，CMOS 工艺造 NAND/NOR 比 AND/OR 更容易。大学教的"先 AND 后 NOT"是逻辑层面的顺序，不是物理层面的顺序。
"时钟和信号谁先谁后"	记住一个基线：时钟是所有时序元件的节拍器，数据传播期间必须走完，在下一个沿到达前稳定住。
"组合逻辑的毛刺是什么"	门延迟不完全一致。比如 A AND (NOT A) 理论永远是 0，但 NOT 的延迟使瞬间出现 1。这叫静态冒险。
"为什么需要建立时间和保持时间"	物理上，D 触发器的输入不能恰好和时钟沿重叠。数字必须提前到达（建立时间）并持续一段（保持时间）。违反了这个，输出可能亚稳态——既不是 0 也不是 1。
"锁存器和触发器有什么区别"	锁存器是电平敏感（CLK=1 时透明），触发器是边沿敏感（只有上升/下降沿采样）。电平敏感意味着随时可能被干扰；边沿敏感意味着只在精准时刻采样。

---

现在不需要理解

• 制造工艺：FinFET、GAAFET、3nm 制程——这些是物理层面的优化。你现在只需要知道晶体管是开关。
• 静态时序分析（STA）：在芯片设计流程中检查每条路径的延迟是否满足时钟约束。这是 EDA 工具的活，不是软件工程师的。
• PLL（锁相环）和时钟树：怎么在芯片上把时钟信号送到每一个触发器。分布均匀本身就是一门学问。
• 亚稳态的数学分析：MTBF（平均无故障时间）公式。知道有这回事就够了，别急着算。

---

旅人笔记

这一章，我们从灯泡开关走到了 ALU 里的加法器。

你亲眼看到了：

• 一个简单的串口 XOR 在物理上是如何用四颗晶体管搭出来的
• 加法、减法在硬件里就是同一套电路加上一个"符号反转"开关
• 你每次写 int x = ...——底层的 32 个 D 触发器就等着时钟沿来把你赋的值锁存起来

计算机不是"会计算东西的电子管"。它是一张精心编织的、不断震荡的逻辑网。 电压在这个网里传播，像潮汐一样准时——每一波潮汐都完成一点计算。

你已经摸到了地心的熔岩。下一站，我们把火花焊成引擎。

---

→ 下一站预告

第4章：CPU 与 ISA——地心引擎

把 ALU、寄存器、译码器、控制单元、时钟全部焊在一起，注入指令，让它自己跑起来。

用一个词定义这一章：熔合（Fusion）。