第 5 章　组合逻辑：从门到加法器

5.1组合逻辑：输出只看「当下」

由逻辑门拼成、没有「记忆」的电路，叫 组合逻辑电路（combinational logic）。它的定义很纯粹：输出只由「此时此刻」的输入决定，一旦输入变了，输出立刻跟着变。

正因为没有记忆，组合逻辑不能「记住」任何历史。它就像一个纯函数：同样的输入，永远得到同样的输出。这一章，我们先用组合逻辑完成一件看似简单、实则奠基的大事——做加法。

在动手搭电路之前，先把「怎么描述一个组合逻辑」说透。工程师手里有三种等价的语言，说的是同一件事：

• 真值表：把每一种输入组合对应的输出列成一张表。它是「需求说明书」——先说清楚要什么，不关心怎么实现。
• 布尔表达式：用与、或、非、异或把输入和输出的关系写成代数式。它是「数学模型」——可以像解方程一样被化简、变形、验证。
• 门电路图：用具体的门把表达式「翻译」成电路。它是「施工图」——最终交给晶体管去实现。

数字设计的日常流程就是在这三种语言之间来回翻译：设计时从真值表出发，写出表达式，化简后画出门电路；排查故障时则反过来——从实际电路反推真值表，看它到底在「按什么规则办事」。三种语言互相咬合，你后面每一章都会反复用到这套流程。

不过真值表有个要命的软肋：行数随输入个数指数爆炸——n 个输入就有 2ⁿ 行。3 个输入 8 行，手写无妨；10 个输入 1024 行，勉强能打印；20 个输入超过一百万行，人类已经没法逐行读完。所以真实工程里，工程师不会硬啃一张巨型真值表，而是把大函数按功能切成小块：表决、比较、选择、进位……每块行数可控，各自写成小表达式，再组合起来。本章后面每一节（加法器、译码器、MUX）本质上都是在做这种「功能切块」——切块，是人对抗指数爆炸的第一件武器。

还有一点需要提前澄清：定义里说「输入一变，输出立刻跟着变」——这个「立刻」其实并不严格成立。信号穿过任何一个门都需要时间，通常在皮秒到纳秒量级，我们记每个门的延迟为 τ（tau，希腊字母，工程里常用来表示时间常数）。输入变化后，输出要经过若干个 τ 才「追」到新值并稳定下来。这一点点延迟平时无关紧要，但当几百个门串成一条长链（比如 5.4 节的行波加法器），延迟就会层层累积，成为电路快慢的决定因素。「传播延迟」（propagation delay）这个词，请先记住，马上会用到。

这类「多个条件里凑够几个才放行」的逻辑，在工程里有个正式名字，叫多数表决（majority voting）：核电站控制、飞行关键系统的传感器判读（比如三余度温度传感器取「至少两个一致」的读数），都靠它提高容错——个别一路传感器坏了、报错了，表决器依然能给出正确结论。你刚推的表达式 AB+AC+BC，就是最常用的三输入表决电路。

更贴近航空维护的例子是联锁（interlock）：例如「舱门关闭」信号与「锁定销入位」信号都为 1，才允许执行下一步操作——这就是一个两输入与门。测试台上密密麻麻的通电条件、告警条件，剥开看几乎全是「与、或、非」的组合逻辑。可以说，凡是「条件判断」，就是组合逻辑的主场。

最后把这一节与下一章的关系用一张表钉牢，学完第 6 章回来对照，你会豁然开朗：

5.2半加器：先算 1+1

两个一位的二进制数相加，一共只有四种情况：

观察这张表，你能发现两个熟悉的门：

• 和（Sum）那一列：两个输入不同时为 1，相同为 0——这正是 异或门（XOR，exclusive OR）的行为。
• 进位（Carry）那一列：两个输入都为 1 时才为 1——这正是与门。

把「一个异或门 + 一个与门」拼起来，就得到能算一位加法的 半加器（half adder）。

半加器解决了「一位加法」，但它有个明显的缺口：它没有考虑「低位传上来的进位」。真正做多位数加法时，每一位除了 A、B，还得加上前一位进过来的进位。这就需要升级版——全加器。

为什么偏偏是异或和与这两个门？这背后其实是算术本身的规定。二进制「逢二进一」，两个一位数相加，结果不外乎 0、1、2、3 四种，写成「本位＋进位」就是：00、01、10、11（进位写在前）。观察规律：

也就是说：「和」是除以 2 的余数，「进位」是除以 2 的商。而异或门恰好就是电路版的「mod 2」——它数一数输入里有奇数个 1 还是偶数个 1（奇数个 1 输出 1）；与门则恰好是 1 bit 乘法（都为 1 才为 1）。两个门各司其职，一位加法器就这样从算术规定里「长」了出来。把这个 mod 2 的视角记住，下一节的全加器你会看得飞快。

顺带把异或的代数展开式也留在这里，化简电路时经常用到：

对照真值表读一遍这个式子：00 行两项都为 0；01 行 Ā·B = 1·1 = 1；10 行 A·B̄ = 1；11 行两项都为 0。四个「1」与异或门的行为完全一致——代数式与真值表又一次互为印证。

这个例子暴露了一个朴素但重要的工程事实：同一个真值表，可以有无数种电路实现，但只有一种最省的。真值表是「合同」，化简是「优化」，门电路是「施工」。今天的芯片设计早就交给 EDA 工具（综合器）自动做这件事，工程师只要提交真值表或高级描述；但工具给出的结果要不要信、为什么长这样，仍需要人懂卡诺图这层原理——尤其是航空电子这类对每一个门都要斤斤计较的场合。

最后辨析一个字眼：半加器的「半」是什么意思？它不是「功能减半」，而是只完成了「本位相加」这一半任务，没接「外来进位」那一半。就像一个只会现做现吃、不会接收别人递碗的厨房：单独用没问题，一到流水线（多位相加）就缺一环。补上这一环的，就是全加器。

5.3全加器：把进位也考虑进去

全加器（full adder）有三个输入：A、B，以及来自低位的进位 C_in；产生两个输出：本位的和 Sum，以及传给高位的进位 C_out。

全加器的电路，本质上就是两个半加器串起来：先用一个半加器算 A+B，得到中间和与进位；再用第二个半加器把「中间和」与 C_in 相加；两个进位再过一个或门合并，得到最终 C_out。

从代数上给全加器把把关。三个一位数相加，总和取值 0～3。「本位和」依然是除以 2 的余数，「进位」是商是不是 0。把 5.2 节的 mod 2 视角直接推广：

注意 Sum 这一行：三个变量连着异或，数的是「1 的个数的奇偶」——奇数个 1 输出 1。对照真值表数一遍：111 行有三个 1，Sum=1；110 行有两个 1，Sum=0；101 行两个 1，Sum=0……与表格严丝合缝。这就是异或门的「奇偶校验」天赋，将来数据校验（奇偶校验位）用的正是它。

再看两个半加器方案的正确性关键：两个半加器各吐一个进位，最后用一个或门合并——凭什么或门合并不会「丢进位」或「多进位」？把两个进位写出来：第一个半加器的进位 c₁ = A·B，第二个半加器的进位 c₂ = C_in·(A ⊕ B)。假如 c₁ = 1，说明 A、B 都为 1，那么 A ⊕ B = 0，于是 c₂ 必为 0——两个进位不可能同时为 1。既然互斥，「或」起来就既不丢也不重，正是总和的进位。一个看似随手画上的或门，背后藏着一次严格的互斥论证——读电路图时要能看出这层「为什么对」。

工程世界里，全加器早已是「标准件」：芯片设计库里躺着现成的、验证过的全加器单元（cell），设计 64 位加法器时不需要重新发明它，直接像搭积木一样例化 64 次，再把注意力放在更高级的进位优化上。复用已验证的模块，而不是每次从头推——这是硬件工程与手工作坊的分水岭。你在例题 3 做的逐门追踪，本质上就是芯片验证工程师每天用仿真器做的工作：把输入打进去，逐拍检查每个内部信号，和「笔算预期」对账。

留一个辨析：既然可以直接做三输入异或门（Sum 一项就够了），为什么教科书都讲「两个半加器级联」？两个原因：其一，C_out 反正要单独的逻辑，而半加器级联把 Sum 与 C_out 的逻辑「打包」在两个熟悉的模块里，出错率低；其二，工程美学——用最少种类的模块搭出一切（还记得与非门完备性吗），比门数省一两个更重要。数字设计里「模块化优先于极致精简」是常态，你会在 CPU 一章再次看到这个哲学。

5.4多位加法器：串联起来算大数

有了全加器，算多位数就简单了：把一个全加器的进位输出，接到下一个全加器的进位输入，一位一位串起来。这种结构叫 行波进位加法器（ripple-carry adder）。

为什么叫「行波」？因为进位信号要一个全加器接一个全加器地「爬」过去——低位算完，进位才传给高位，高位才能开始算。位数越多，这个「波浪」爬得越久，所以行波加法器位数多了会变慢。后面 CPU 一章会看到，工程师如何用「超前进位」等技巧来加速。

「爬得越久」到底久多久？现在把 5.1 节埋下的传播延迟 τ 请出来，算一笔明白账。在全加器内部，从 C_in 到 C_out 的进位路径要穿过两个门（半加器 2 的异或、再加或门），即每级 2τ；进位行波爬过 n 级后，最高位还要求和（再过 1τ），于是 n 位行波加法器的最坏总延迟约为：

更关键的问题是：为什么这个进位只能串行爬，不能大家并行算？因为第 i 位的进位输出，恰恰是第 i+1 位的输入——第 3 位要等第 2 位的进位才知道自己的三个输入是什么，而第 2 位又要等第 1 位……信息本身就是按位逐级产生的，电路再快也绕不开这个因果链。想打破它只有一个办法：用更多的门把每一位的进位直接从原始输入「预测」出来——这就是超前进位（carry lookahead）：C₁ = A₀B₀，C₂ = A₁B₁ + A₀B₀C₁ = A₁B₁ + (A₀+B₀)·A₁B₁……一路代入展开，进位不再等待，但门的数量和扇入随位数急剧膨胀。快，是用面积换来的。

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def ripple_add(A, B):          # 4 位行波进位加法
    c, out = 0, 0
    for i in range(4):
        s, c = full_adder((A >> i) & 1, (B >> i) & 1, c)
        out |= s << i
    return out | (c << 4)

print(ripple_add(0b0110, 0b1101))   # 6 + 13 = ?

回望历史会更有感觉：1970 年代初的 4 位微处理器，一次加法正好要在几个时钟周期里等行波爬完，算 8 位数就得「低半字节加一次、高半字节带着进位标志再加一次」。那句「多字节运算靠进位标志接力」，到现在依然是嵌入式工程师的基本功——CPU 里专门有「带进位加」（ADC）这条指令，就是为接力准备的。今天的 64 位 CPU 早已用超前进位把一次加法压进一个周期，但例题 4 那笔账，永远是理解「快是拿什么换来的」的起点。

把行波与超前进位摆在一起，就看清了数字设计最核心的一组权衡：

没有免费的午餐——要么花门，要么花时间。往后你在任何一本体系结构书里看到「加法器优化」，本质都是在这两个极端之间找平衡点。

5.5减法与补码：加法器通吃

你可能要问：那减法呢？难道还要单独造一台「减法器」？——不需要。这正是第 2 章补码埋下的伏笔：减去一个数 = 加上它的补码。

回忆补码的「取反加一」。在电路里，这一步出奇地简单：

• 取反：让每一位都过一个非门，成本极低。
• 加一：把「1」当作最低位的那一个进位 C_in，喂进加法器即可。

于是，A − B 就变成「A + (B 的取反) + 1」，全程只用一个加法器。工程师在加法器外面套上「取反 + 选位」的小电路，就同时得到了加法和减法两套能力。

这个思想可以继续推广：乘法和除法也能拆成一连串加法和移位（乘法 = 多次累加；除法 = 多次累减）。所以，一台看似强大的 CPU，最底层往往只靠一个加法器在默默工作。

把「套在加法器外面的那圈小电路」画具体一点。逐位取反用非门当然可以，但工程师有更巧的一招——用异或门做「条件取反」。异或有个妙用：X ⊕ 0 = X（直通），X ⊕ 1 = X̄（取反）。于是在 B 的每一位前面放一个异或门，异或门的另一端全部并到一根线上，这根线叫 Sub 控制信号：Sub = 0，B 原样进加法器（做加法）；Sub = 1，B 逐位取反（做减法的一半）。而「加一」呢？把同一根 Sub 线再接到最低位的 C_in 上——Sub = 1 时，加法器白捡一个「＋1」。一根线，同时完成「取反＋加一」两个动作，这就是教科书上经典的加减两用电路（add/sub unit）：

这套电路还牵出两个必须分清的「标志位」概念，它们是 CPU 条件判断的基石：

• 进位标志 C：最高位 C_out 直接引出来。它对无符号数有意义——C=1 表示结果超出了 0～2ⁿ−1 的范围。
• 溢出标志 V：两个有符号数相加，若「正＋正得负」或「负＋负得正」，说明有符号解释下结果装不下了。判定式非常漂亮：V = 最高位的进位输入 ⊕ 最高位的进位输出——一进一出不相等，即溢出。

注意 C 和 V 经常「意见不合」：同一个 0110+1101，无符号看是 6+13=19，C=1 表示「无符号溢出」；补码看是 6+(−3)=3，完全合法。所以 CPU 干脆两个标志都存，程序按自己的数据类型选用。第 8 章讲条件跳转时，它们会反复登场。

这套「标志位 + 加减两用电路」的组合拳，正是 CPU 里 ALU（下一章的常客）的雏形：控制器把 Sub 拉高或拉低，同一套门阵列立即切换身份。航空电子里也一样——机载计算机的加减运算、飞控增益的计算、燃油量的累减，底层都是这同一台加法器在转，工程师只需相信它，把精力放在系统层。

最后澄清一个容易绕晕的说法：既然「减法器不存在」，为什么 CPU 明明有 SUB（减法）指令？——指令是软件视角，电路是硬件视角。SUB 指令被执行时，控制器发出的控制信号恰好是「Sub=1」：取反阵列打开、进位口置 1，加法器顺路完成减法。指令层的「减」，在晶体管层面自始至终只有加法。「一个模块、两种人格」——按什么人格工作，由控制信号说了算。这个思想（控制信号给同一套硬件赋予不同能力）会在第 8 章 CPU 内部反复出现。

5.6编码器、译码器与多路选择器

加法器之外，还有几个「组合逻辑家族」的明星，它们在计算机里到处当配角，却不可或缺。

译码器（decoder）：1 条线变成 N 条

译码器把 n 位输入，翻译成 2ⁿ 条输出线中的恰好一条为 1。比如 2 位输入 00、01、10、11，对应点亮 4 条线中的一条。它常用来「选中」某一行内存、某个寄存器——是寻址的基础。

译码器为什么天然适合「选中」？把它的行为写成代数：第 i 条输出线 Y_i = 1，当且仅当输入正好等于 i 的二进制写法——也就是说，每条输出线对应一个最小项（minterm）。2 位输入的全部 4 个最小项，正好一一分配给 4 条输出线，不多不少、不重不漏。所以译码器又常被叫作「最小项发生器」：给它一个编号，它就把那一路的「灯」点亮。寻址时 CPU 把地址码送进来，哪条线亮，哪行存储单元、哪个寄存器就被「叫到」——这就是「选通」。

顺带一个日常工程案例：老式数字仪表上的七段数码管，靠的就是一种特殊的译码器——BCD 七段译码器，把 4 位二进制数字（0～9）翻译成 a～g 七段亮/灭的组合，你才能一眼读出 3 或 8。万用表、时钟、座舱仪表的旧式显示，全有它一份功劳。

编码器（encoder）：N 条线变回 1 条

编码器是译码器的逆过程：在多条输入线中，检测哪一条为 1，输出它的编号。键盘里的「哪个键被按下」，就是靠编码器把「那一条线」变成「那个键的编码」。

实际键盘还有个现实问题：人手很快，两三个键可能「同时按下」。普通编码器遇到多线同时为 1 会输出错乱的编号。于是工程上给编码器加上优先级——优先编码器：约定编号大的优先（或小的优先），同时多键按下时只报优先级最高的那个。键盘控制器、中断控制器里，排队靠的都是它。

多路选择器（multiplexer，MUX）：多选一的开关

多路选择器（MUX）像一个「多路切换开关」：有多路数据输入，用几根「选择线」决定把哪一路接到输出。可以把它理解成一个「电子旋转开关」，它是 CPU 内部数据通路的关键组件。

看懂图 5-5 的内部结构，MUX 就再也不是黑盒：选择线 S1S0 先经过译码，产生「四选一」的选通信号；每个数据 D_i 和自己的选通信号做与——选中的那一路「与 1」原样通过，没选中的「与 0」被强行清零；最后或门把幸存的那一路送出去。写成代数就是一个漂亮的通式：

这个式子透露了一个惊人的能力：既然任何真值表都能写成「最小项之和」，那只要把数据端 D_i 按真值表接 0 或接 1，一个 MUX 就能实现任意逻辑函数。三变量的函数，用 8 选 1 MUX，把 8 个数据端按真值表对应接死即可——不用化简、不用卡诺图，MUX 就是一块「万能函数发生器」。CPU 里数据从哪个寄存器流向 ALU、总线占用让给谁，都是 MUX 在一拍一拍地扳道岔。

MUX 还能级联扩容：两个 4 选 1 加一级 2 选 1，就是 8 选 1（高位选择线决定用哪一组，低位选择线在组内挑路）；同理四个 4 选 1 加一级 4 选 1，就是 16 选 1。像搭积木一样一层层往上堆，数据通路的「路口」越修越宽——CPU 里的多路选择网络，就是这么一层层长出来的。

把译码器与 MUX 摆在一起对照一次：译码器输出线上的 1 是「选通通知」（点名哪一路，线上不跑数据）；MUX 输出的是「数据本身」（被选中的那一路的内容）。实际系统里两者经常成对出现：先用译码器点名（片选），再让数据进场（读写）。分清「通知」和「内容」，是读懂数据手册的第一步。