3.1 组合逻辑

这一章暂时放下软件抽象，直接看与、或、非门如何组合成算术与控制电路。CPU 指令能够执行，最终依赖这些电路在时钟约束下共同工作。

前两章解释了数据的位级表示。本章把 bit 送进逻辑网络，观察输出怎样由当前输入决定；下一篇再引入触发器、时钟与状态。

软件运算落到哪里

电路图上是输入引脚、输出引脚、逻辑门和连线，C 的 + 不能替它们接线。两个二进制数相加，要由逻辑门、连线和电气时序共同完成。

数字电路并不声称物理电压只有 0 和 1。它规定输入低于某个范围被接收为逻辑 0，高于另一个范围被接收为逻辑 1，中间区域不保证解释。具体阈值属于所用逻辑家族和工艺；逻辑设计先在这个抽象上工作。

MOS 晶体管更接近受栅极电压控制的器件，而不是理想机械开关。CMOS 把晶体管网络组合成逻辑门，再由标准单元、布线和存储元件构成处理器。不是每个晶体管都在每个时钟沿翻转，动态功耗也正因实际切换活动而变化。

六种常用逻辑关系

对单 bit 输入 A、B：

A	B	AND	OR	XOR	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

NOT 只需一个输入：NOT 0 = 1，NOT 1 = 0。真值表穷举所有输入组合，因此足以定义一个有限输入的布尔函数。

在 C 中，&&、|| 和 ! 是逻辑运算，会把结果规范为 0 或 1，并且前两者会短路；&、|、^ 和 ~ 是逐 bit 运算。用 C 模拟单 bit 门时，应先规范输入；下面的函数片段把零映射为 0、所有非零整数映射为 1，不能随意混用两组运算符。

static int bit(int value) {
    return value != 0;
}

static int gate_and(int left, int right) {
    return bit(left) & bit(right);
}

static int gate_xor(int left, int right) {
    return bit(left) ^ bit(right);
}

这些函数描述门的逻辑关系，不代表普通 C 编译器会按函数调用顺序摆放晶体管。真正的硬件设计语言描述并发连接，综合工具再映射到目标单元库。

为什么 NAND 可以独立构成任意布尔逻辑

一个门集合若能构造任意布尔函数，就称为 functionally complete。仅用 NAND 可得到 NOT、AND 与 OR：

NOT A     = NAND(A, A)
A AND B   = NAND(NAND(A, B), NAND(A, B))
A OR B    = NAND(NAND(A, A), NAND(B, B))

而 NOT、AND、OR 足以从析取范式等形式表达任意有限布尔函数，所以 NAND 单独具备功能完备性。NOR 也一样。

这是一条逻辑表达能力结论，不表示所有芯片只采用 NAND。实际实现还要权衡延迟、面积、功耗、扇出和布线，单元库通常包含多种门及更复杂的组合单元。

布尔代数帮我们减少不必要的逻辑

常用恒等式包括：

A AND B = B AND A
A OR (B OR C) = (A OR B) OR C
A AND (B OR C) = (A AND B) OR (A AND C)

NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)

A OR (A AND B) = A
A AND (A OR B) = A

等价表达式的门数可能不同，但“门更少”不总等于实现更好。逻辑深度、共享子表达式、扇出和物理布线都会改变关键路径。综合器可以做大规模化简；设计者仍需要理解等价性，才能读懂结果并写出正确约束。

卡诺图适合手工化简少量变量。变量较多时，算法化简与综合工具更实用。无论用哪种方法，先把功能真值表写对。

组合逻辑没有内部状态

组合电路的输出由当前输入决定。抽象模型常写成：

output = F(input)

“当前”不等于物理上的瞬间。输入变化后，信号要经过门和连线传播，输出可能短暂经过中间值，最终才稳定。传播延迟、上升/下降时间和负载由具体实现决定。

组合逻辑与时序逻辑的区别是有没有被电路保存的状态，不是“有没有延迟”。现实中的组合门同样有延迟。

从半加器到全加器

半加器把 A 与 B 相加，输出和 S 与进位 C：

S = A XOR B
C = A AND B

当还要接收低位传来的 Cin 时，全加器的关系是：

P    = A XOR B
S    = P XOR Cin
Cout = (A AND B) OR (P AND Cin)

逐项检查八种输入，可发现 S 是三个输入中 1 的个数的奇偶位，Cout 表示至少两个输入为 1。

把第 i 位的 Cout 接到第 i+1 位的 Cin，就得到行波进位加法器。每一位可以并行产生部分结果，但高位最终输出要等待进位沿链传播。位宽增长时，最坏进位路径也增长。

超前进位、前缀加法器等结构根据 generate 与 propagate 信号并行组合进位信息，以更多硬件和布线换取更短逻辑深度。现代处理器采用的具体结构会随时序、面积和能耗目标变化，并非只有一种“最快加法器”。

用软件模型穷举验证 8-bit 加法器

下面的 C17 代码是行为参考模型。循环模拟八级连接，carry_out 单独返回第九位；carry_in 只取最低位。保存为 ripple_adder.c，用 cc -std=c17 -Wall -Wextra -Werror ripple_adder.c -o ripple_adder 编译，再运行 ./ripple_adder。软件循环不表示真实硬件的执行时序。

#include <assert.h>
#include <stdint.h>

struct Add8Result {
    uint8_t sum;
    uint8_t carry_out;
};

static struct Add8Result ripple_add8(uint8_t left, uint8_t right,
                                     uint8_t carry_in) {
    struct Add8Result result = {0, 0};
    uint8_t carry = (uint8_t)(carry_in & UINT8_C(1));

    for (unsigned int position = 0; position < 8U; position++) {
        uint8_t a = (uint8_t)((left >> position) & UINT8_C(1));
        uint8_t b = (uint8_t)((right >> position) & UINT8_C(1));
        uint8_t propagate = (uint8_t)(a ^ b);
        uint8_t sum_bit = (uint8_t)(propagate ^ carry);

        carry = (uint8_t)((a & b) | (propagate & carry));
        result.sum |= (uint8_t)(sum_bit << position);
    }

    result.carry_out = carry;
    return result;
}

int main(void) {
    for (unsigned int left = 0; left <= UINT8_MAX; left++) {
        for (unsigned int right = 0; right <= UINT8_MAX; right++) {
            for (unsigned int carry = 0; carry <= 1U; carry++) {
                struct Add8Result actual =
                    ripple_add8((uint8_t)left, (uint8_t)right,
                                (uint8_t)carry);
                unsigned int expected = left + right + carry;

                assert(actual.sum == (uint8_t)expected);
                assert(actual.carry_out == (uint8_t)(expected >> 8));
            }
        }
    }
    return 0;
}

这个测试覆盖 131,072 种输入，验证 sum 与 carry_out。穷举在输入位数较少时很有效；更大的模块会配合形式验证、随机测试和覆盖率指标。

同一条进位链也能做减法

对 n-bit 模运算：

A - B = A + (NOT B) + 1  (mod 2^n)

因此可让控制位 Sub 同时完成两件事：

B'[i] = B[i] XOR Sub
Cin   = Sub

Sub 为 0 时计算 A + B，为 1 时计算 A + NOT(B) + 1。这复用了同一条加法路径。

但 carry out、borrow 与 signed overflow 是不同概念。以 n-bit 补码加法为例，有符号溢出可由“最高位的进位输入 XOR 最高位的进位输出”判断，也可从操作数与结果的符号关系判断。例如 4 位 1111 + 0001 = 0000 有无符号进位，但按补码解释为 -1 + 1 = 0，没有有符号溢出；0111 + 0001 = 1000 则相反。对 A + NOT(B) + 1 这条 n 位减法路径，无符号借位是最终进位的反值。ISA 对标志位的命名和极性仍须查明，不能把 carry flag 当作通用的“结果太大”。

MUX 选择数据，译码器选择一路

2-to-1 多路选择器根据选择位 S 输出 A 或 B：

Y = (NOT S AND A) OR (S AND B)

更宽的 MUX 对每一个 bit 并行应用相同选择信号；更多输入可用树形结构或目标库提供的单元实现。MUX 常用于选择 ALU 输入、写回来源或下一条程序计数器。

n-to-2^n 译码器把 n-bit 输入映射成 one-hot 输出。3-to-8 译码器在输入 101 时只拉起编号 5 的输出（从 0 编号，即第六路）。实际内存系统还包含行/列选择、片选、地址映射、时序控制与模拟电路；“地址进译码器就直接读出 DRAM”只是最粗略的一层抽象。

编码器执行近似反方向的映射。若多路输入可能同时有效，普通编码器的输入约束不成立，需要优先编码器或显式错误处理。

一个小型 ALU 是多个结果加一只选择器

一个简化的 8-bit ALU 可以并行计算 AND、OR、XOR 与 ADD，再由操作码选择输出：

and_result = A AND B
or_result  = A OR B
xor_result = A XOR B
add_result = A + B
result     = MUX(op, and_result, or_result, xor_result, add_result)

“并行计算”是结构层面的可能实现，并不要求所有设计都让每条路径持续切换。时钟门控、操作数隔离和不同资源复用会改变功耗与面积。ISA 中的一条 ADD 指令也不等于固定穿过某个单周期电路；微架构可以流水化、复用或安排多个执行单元。

延迟会制造毛刺

考虑 Y = (A AND B) OR ((NOT A) AND C)。当 B=C=1、A 从 1 变 0 时，理想布尔函数始终为 1；若两条路径延迟不同，两个 AND 输出可能短暂同时为 0，使 Y 出现毛刺。这叫 static-1 hazard。

若输出在目的触发器的整个 setup/hold 窗口内保持稳定，同步数据路径可能仍满足功能；仅说“采样前毛刺消失”还不够。若它驱动异步控制、时钟或外部接口，就可能造成严重错误。本例可加共识项 B AND C，保持布尔函数不变，并消除只切换 A 时的 static-1 hazard。其他场景可能需要重新编码、寄存输出或专门的时钟域设计；这些方法各有适用条件，不能只靠理想真值表判断。

动手搭建组合路径

1. 只用 NAND 写出 XOR，并用四行真值表验证。
2. 为全加器列出八行真值表，分别推导 sum-of-products 表达式。
3. 手算 1011₂ + 0110₂ 的逐级进位，并解释第 5 位进位的意义。
4. 设计 4-to-1 MUX 的选择树，标出最坏情况下经过几级 2-to-1 MUX。
5. 为 4-bit 加减器分别给出无符号 carry/borrow 与补码 overflow 测试。
6. 找一个会产生 static hazard 的输入变化，画出两条路径的到达时间。

让结果在下一拍被记住

组合逻辑能计算，却不会自行保存“上一次”的值。处理器需要程序计数器、流水线寄存器和控制状态。下一篇加入锁存器、触发器与同步时序，也会解释为什么建立时间、保持时间和亚稳态不能被一句“时钟是心跳”带过。