第23章 数字系统

Note

前几章处理的都是连续变化的模拟信号，这一章进入数字系统（digital system）：信号只有高/低两个状态。全部数字电路的”原子”只是一小组逻辑门（logic gate），而把它们织成有用的功能，靠的是真值表、布尔代数与卡诺图这三件工具。本章还会讲到数字如何用二进制表示与运算、如何编码与检错，是理解计算机一切的起点。

23.1 引言

第 10 章提到有些信息源产生离散信号（如开关、热电偶的通断传感器）。本章专注最常见的二进制信号：单个二进制量可以表示一个开关的状态，组合起来则能表示更复杂的量。

23.2 二进制量与二进制变量

二进制量（binary quantity）只有两种状态，如开关的开/关、阀的开/闭。给每个量起个名字就是二进制变量（binary variable），如开关用 S、灯泡用 L。两个状态常用符号 ‘0’ 和 ‘1’ 表示，映射关系任意但必须约定一致：惯例 ‘1’ = 开/真/高，‘0’ = 关/假/低。

记录变量之间关系的表叫真值表（truth table）：左侧列出输入所有可能状态，右侧给出对应输出，行的顺序按升序二进制排列。

两个开关串联：必须都闭合灯才亮，记为 $L=S_1\text{AND}{S}_2$（例：刹车灯需踩刹车 AND 点火开关打开）。两个开关并联：任一闭合灯即亮，记为 $L=S_1\text{OR}{S}_2$（例：车内阅读灯，司机门开 OR 乘客门开）。“OR”包含两输入都为真的情况，故也叫同或式 OR（Inclusive OR）。串联/并联可推广到任意多个开关：n 个开关对应 $2^n$ 行真值表。混联可用括号消歧义，如 $L=S_1\text{AND}(S_2\text{OR}{S}_3)$。

实际设计中往往是反向过程：给一个真值表或文字描述，要设计出电路。把未知网络看成”黑箱”（black box），输入端是各种二进制传感器（恒温器、液位、接近开关），输出端接灯/加热器/电磁阀。实现数字系统的积木就是逻辑门：对输入二进制信号施加逻辑运算得到输出的器件，每种门有独特符号，其功能可用布尔表达式和真值表两种方式描述。

23.3 逻辑门

23.3.1 三种基本门

门	逻辑符号要点	布尔式	功能口诀
AND（与）	矩形/D 形，输入侧平直	$C=A\cdot B$（点常省略写 $AB$）	全 1 才 1
OR（或）	输入侧凹陷	$C=A+B$	有 1 就 1
NOT（非/反相器）	三角形 + 输出端小圆	$B=\overline{A}$	取反

三种门可有任意多个输入（NOT 除外）。符号上的小圆圈表示反相：三角形不带圈的是缓冲器（buffer），逻辑上 $B=A$、不改变状态，只在电气上增强驱动能力——它通常不算基本门。布尔式中的反相用变量上方一横表示，读作”A bar”。

23.3.2 复合门

• NAND（与非） = AND 后接反相，$C=\overline{AB}$：AND 符号输出端加小圆；
• NOR（或非） = OR 后接反相，$C=\overline{A+B}$：OR 符号输出端加小圆；
• 异或门（Exclusive OR，XOR）：两输入之一为 1 时输出 1，都为 1 时输出 0——即”排除两输入都为真”的情况，故得名。恰好两个输入，符号为 $C=A\oplus B$；
• 同或门（Exclusive NOR，XNOR） = XOR 后接反相，输入相等时输出 1，故又称等值门（equality gate），$C=\overline{A\oplus B}$。

记住 XOR 的两种等价说法：(1) 若 A 或 B 为真、但 A 与 B 不同时为真 → $X=(A+B)\cdot \overline{AB}$；(2) “A 真 B 假，或 A 假 B 真” → $X=A\overline{B}+\overline{A}B$。

Success

三大口诀：NOT 带圈，圈在输出端取反；NAND 先与后非，NOR 先或后非；XOR 全异才 1（不同为 1），XNOR 相同才 1。AND/OR 可多输入，XOR 固定两输入。

23.3.3 用逻辑门实现任意功能

用上述门的适当组合可以实现任何输入输出关系——小到几个门做个控制机构，大到几百万个门构成一台微计算机。设计流程通常为：功能描述 → 真值表/布尔式 → 化简 → 电路图。

23.4 布尔代数

布尔代数（Boolean algebra）提供描述二进制系统的常量、变量、函数与一整套定理。

• 常量：‘0’（假）与 ‘1’（真）；
• 变量：可取 ‘0’ 或 ‘1’ 的符号（如 A、B、X）；
• 函数：AND（·）、OR（+）、NOT（上横线）等运算。

常用恒等式与定律（都可用”代入 0/1”验证）：

恒等式（A 为任意变量）：$A\cdot 0=0$、$A+0=A$、$A\cdot 1=A$、$A+1=1$、$A\cdot A=A$、$A+A=A$、$A\cdot \overline{A}=0$、$A+\overline{A}=1$、$\overline{\overline{A}}=A$（双重取反还原）。

定律：

• 交换律：$AB=BA$，$A+B=B+A$；
• 结合律：$A(BC)=(AB)C$，$A+(B+C)=(A+B)+C$；
• 分配律：$A(B+C)=AB+AC$，$A+BC=(A+B)(A+C)$；
• 吸收律：$A+AB=A$，$A(A+B)=A$；
• 补充：$A+\overline{A}B=A+B$，$A(\overline{A}+B)=AB$；
• 德摩根定理（De Morgan’s law）：$\overline{A+B}=\overline{A}\cdot \overline{B}$，$\overline{A\cdot B}=\overline{A}+\overline{B}$。

Warning

德摩根最容易抄反：把 $\overline{A+B}$ 拆开时，“或”变”与”、每个变量取反——$\overline{A+B}=\bar{A}\bar{B}$，不是 $\bar{A}+\bar{B}$。推广到三项：$\overline{A+B+C}=\bar{A}\bar{B}\bar{C}$。拆线时符号要翻转、逐项取反。

23.5 组合逻辑

数字系统分两类：输出只由当前输入决定的是组合逻辑（combinational logic）；输出还与输入的历史次序有关的是时序逻辑（sequential logic），留到第 24 章。本节讲组合逻辑的四种”翻译”能力。

23.5.1 由布尔式画电路图

把表达式拆成顶层运算结构，逐层向下找各输入如何构成。例：$X=A+B\overline{C}$ —— X 是 A 与 $B\bar{C}$ 相或；$B\bar{C}$ 是 B 与 $\bar{C}$ 相与（C 先经过反相器）。

23.5.2 由电路图写布尔式

反向操作同样直接：从输入向输出走，把每个门输出的布尔式标在图上，一级一级”接力”到最终输出。

23.5.3 由文字描述实现

先把文字翻成布尔式再画图。异或门的两种描述得到两个等价电路（例子见 23.3.2）。布尔表达式不唯一——这是理解化简重要性的关键。

23.5.4 由真值表写出表达式

对每个输出为 1 的行写出一个最小项（minterm）：该行某输入为 1 就用其原变量、为 0 就用其反变量，行内各变量相与。整个表达式 = 所有最小项相或（“积之和”）。例如 3 输入表输出为 1 的行是 001、101、110，则 $X=\bar{A}\bar{B}C+A\bar{B}C+AB\bar{C}$。

Warning

写最小项时反变量容易错位：$\overline{A}\overline{B}C$（A 反、B 反、C 原）对应输入 001，而 $\overline{AB}C$ 对应 AB=11…… 二者完全不同。每个变量要单独决定取不取反。

23.6 用单一类型门实现电路

有的逻辑工艺族（如 TTL 早期）做 NAND 最便宜，另一些做 NOR 最便宜，所以常需把电路改写成只用一种门。

核心依据还是德摩根：

• 全部转 NAND：把 OR 替换为”各输入取反后 NAND”：$A+B+C=\overline{\bar{A}\bar{B}\bar{C}}$。积之和式 $D=ABC+A\bar{B}\bar{C}+\bar{A}B\bar{C}$ 可先整体取双重反再用德摩根展开，得到若干 NAND 的 NAND；
• 全部转 NOR：把 AND 替换为”各输入取反后 NOR”：$ABC=\overline{\bar{A}+\bar{B}+\bar{C}}$。缺点通常是门数略增。

23.7 代数化简

化简的目标是把表达式降到最容易实现的形式（门最少是好起点，但不绝对等于最便宜）。标准形式是积之和（sum-of-products）：若干”输入变量的与项（乘积项）“再相或。注意积之和不允许出现”整串项的反”，如 $\overline{ABCD}$。

基本技巧：用 $A+\bar{A}=1$ 合并互补项。例：$X=ABC+\bar{A}BC+AC+A\bar{C}=BC(A+\bar{A})+A(C+\bar{C})=BC+A$，从三个门降到一个门（严格说 $BC$ 与 $A$ 还需一个或门）。更复杂的表达式（如 $E=B\bar{C}\bar{D}+\bar{A}BD+ABD+BC\bar{D}+\bar{B}CD+\bar{A}\bar{B}\bar{C}D+A\bar{B}\bar{C}D$）可用结合律分组逐级合并最终得到 $E=B+D$。

代数化简的弱点也明显：常常要靠”灵感”找配对，且无法保证得到最优解（如 $E=A\bar{B}\bar{C}+\bar{A}\bar{C}D+ABD+BCD$ 需先展开补全变量再配对）。复杂的表达式要用下面更强的工具。

23.8 卡诺图化简

卡诺图（Karnaugh map）是真值表的图形化表示：输入的每个组合对应网格中的一个格子，格内填该组合的输出。关键的排列原则是——相邻格子（水平或垂直方向）只差一个变量的状态，因此行列标号不是二进制升序而是格雷码（Gray code）序（见 23.12.3）。

• 2 变量：2×2；3 变量：4×2；4 变量：4×4；可扩展到 5、6 变量但图形变复杂。

化简原理：两个相邻的 1 可合并为一项，消去那个”既取 0 又取 1”的变量：

$$WXYZ+WXY\bar{Z}=WXY(Z+\bar{Z})=WXY$$

把相邻 1 圈起来（成对、四方块、$2^n$ 个一组），圈内状态保持不变的变量留在乘积项里，变化的变量被消去。要点：

1. 先圈尽可能大的组（每组 $2^n$ 个）；
2. 再圈较小组合并，直到每个 1 至少被覆盖一次；
3. 去掉冗余组。

Success

卡诺图三诀：相邻只差一位，边对边也算相邻（把图想成上下/左右卷成筒）；合并 $2^n$ 个 1 消 n 个变量；先大圈后小圈，多余圈删掉。

例（23.12）：$D=\bar{A}B\bar{C}+AB\bar{C}+A\bar{B}\bar{C}+\bar{A}\bar{B}C+\bar{A}BC+ABC$，卡诺图化简得 $D=B+A\bar{C}+\bar{A}C$。注意某些 1 被”借用”进多个圈以凑成大组——这完全合法且是得到最简式所必需的。

23.8.1 无关项（Don’t care）

某些输入组合永远不会出现，或某输入变化时输出无关紧要，称为无关项（don’t care），在真值表和卡诺图里记作 X。对输出为 X 的格子，设计者可以自由选择当 0 还是当 1——在卡诺图上把 X 当 1 来凑大圈、从而简化电路，是卡诺图的一大优势。典型例子：BCD 输入只有 0–9 有效，1010–1111 六种组合就是无关项。

Warning

无关项只允许出现在”真不会发生”的输入组合上。若某组合实际会出现而你在化简时把它当成了 1（或 0），电路就会在该组合给出未定义的错误输出——先确认无关，再当 1 用。

对于超过 6 个变量或需要机器自动化的情况，常用表格化的 Quine–McCluskey 化简：对最小项逐对检查能否应用 $AB+A\bar{B}=A$，穷举约简直到无法再简，可手工也可编程实现。

23.10 传播延迟与竞争冒险

真实逻辑门响应输入需要有限时间，称传播延迟（propagation delay），现代器件通常小于 1 ns。但某些情况下它会造成竞争冒险（hazard）——输出出现不该有的瞬时跳变。

典型例子：电路实现 $C=A\cdot B=A\cdot \bar{A}$（把 A 接到 B 端并取反），逻辑上 C 恒为 0。但 A 从 0 变 1 时，反相器延迟使 AND 门短暂看到两个 1，快速 AND 门会吐出一个虚假脉冲。同理，实现 $D=A\bar{B}+BC$ 的电路在 B 变化时，两个与门输出可能”接不上班”，OR 门输出短暂拉低。从卡诺图看，这是输入组合从一组圈跳到另一组圈时经过”空档”。

解法：用卡诺图找出被圈覆盖而跳变时”断路”的相邻组，补一个冗余乘积项（桥接项）把两个圈连起来——函数不变，但跳变时有人”兜底”，冒险消失（代价是多了门）。凡驱动边沿触发电路的场合，消除冒险往往是必须的。

23.11 数制与二进制算术

23.11.1 常用数制

日常十进制：每位是 10 的幂，最左是最高位（MSD）、最右是最低位（LSD）。二进制只有两个数字，所以任何二值器件（开关、灯）都可直接表示一位；用下标区分进制，如 $1101_2$ 与 $1101_{10}$。

$$1101_2=1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0=13_{10}$$

常用的还有八进制（0–7）与十六进制（0–9、A–F）。二进制数一长串既难写又难记，而每 4 位二进制恰好对应 1 位十六进制，转换只需查表，故大数习惯用十六进制书写。

23.11.2 进制转换

• 二进制 → 十进制：把每个 1 所在位的权值相加即可；
• 十进制 → 二进制：整数部分反复除以 2 记余数（余数从下往上读）；小数部分反复乘以 2 取溢出（从上往下读）；
• 十六进制 ↔ 二进制：逐位直接互换，4 位对 1 位，从最右位开始分组、不足补前导 0；
• 非十进制间互转可经十进制中转，或像二↔十六那样找直接捷径。

23.11.3 二进制算术

二进制算术极简单：$0+0=0$、$0+1=1$、$1+1=10$（有进位）。

半加器（half adder）：两输入 A、B，两输出进位 C 与和 S：

$$C=A\cdot B,S=\bar{A}B+A\bar{B}=A\oplus B$$

和输出恰好是异或！相加多位数时，除最右位外每列还要加上来自低位的进位，因此需要全加器（full adder）：三输入（A、B、进位输入 $C_i$），两输出（和 S、进位输出 $C_o$）。由真值表与卡诺图得：

$$C_o=AB+A{C}_i+B{C}_i$$ $$S=\bar{A}\bar{B}{C}_i+\bar{A}B{\bar{C}}_i+A\bar{B}{\bar{C}}_i+AB{C}_i$$

两个半加器也能拼出一个全加器（先加两位再加进位），门少但逻辑深度大、更慢。n 位加法器把若干个全加器级联即可：LSB 用半加器（或全加器接 $C_i=0$），每级进位送下一级。8 位加法若直接用 16 输入真值表将有 $2^{16}$ = 65,536 行——所以逐位处理的分治思路是必须的。逻辑深度（logical depth，信号沿途经过的门数）决定响应快慢：图 23.36(a) 的半加器中进位深度 1、和深度 3，深度不均可能造成瞬时错误输出。

半减器（half subtractor）与此对称：输出差 D 与借位 $B_o$，其中差与半加器的和相同（$A\oplus B$），但借位 $B_o=\bar{A}\cdot B$（仅当 A=0、B=1 时才借）。多位相减用全减器级联。注意这些电路假定结果非负；负数表示留待第 26 章微处理器算术。乘法/除法硬件复杂，一般交给专用器件或微处理器。

23.12 数字与字母编码

23.12.1/23.12.2 普通二进制与 BCD

二进制最常用（省存储、算术简单）。BCD 码（Binary-Coded Decimal）把十进制数的每一位单独转成 4 位二进制，如 $9450_{10}=(1001)(0100)(0101)(0000{)}_{BCD}$。BCD 比纯二进制浪费位，但与十进制互转极简单，故大量用于计算器等人机界面。

23.12.3 格雷码（Gray code）

相邻两个数只有一位不同，故又名反射二进制码（reflected binary code）。生成法：写 0、1；倒序复制前段、每行最前面加 1，不断重复。0–4 的格雷码：0000、0001、0011、0010、0110……正是卡诺图行列用的顺序。

为什么需要它？假想位置传感器从 7（0111）变到 8（1000），普通二进制 4 位全变：若读数恰好发生在翻转瞬间，各位翻转快慢不同，可能读到 0000、1111 乃至 0–15 间任意值。而格雷码从 7（0100）到 8（1100）只变一位，中途读数只会是 7 或 8 之一——非旧即新，绝不出错。因此格雷码用于异步计数器与绝对位置编码器。

23.12.4 ASCII 码

存储文本需要给字母、数字、标点编码，最通行的是 ASCII（美国信息交换标准码，读作”ass-key”）：每字符 7 位，共 128 种——大小写字母、数字 0–9、标点与换行/回车/退格等控制字符。‘A’ = 1000001（41₁₆），‘S’ = 1010011（53₁₆）。注意这些是”字符”的编码，不是数值。7 位容量小且有英语偏向，催生了 Unicode/ISO 10646 等更大字符集。

23.12.5 差错检测与校正

数字系统同样受噪声之苦（第 21 章），传输中数据可能出错：

• 奇偶校验（parity check）：每个数据字补 1 位校验位，使整字（含校验位）中 1 的个数为偶数（偶校验）或奇数（奇校验）。收端数 1 的个数即可知道有无错误。局限：只能发现奇数个错，两个错会互相抵消，且不能定位错误位；
• 校验和（checksum）：把一组数据字求和后随数据传送，收端重算比较，检查整块数据；
• 汉明码（Hamming code）等编码：发送更多冗余位，不仅能检出还能定位并纠正错误位。冗余越多纠错能力越强，但数据率代价越大；任何码都不可能无限纠错。

综合设计示例

例：设计 4 选 1 多路选择器（multiplexer）。多路选择器是”数字多刀开关”：由选择输入 $S_1{S}_0$ 决定把哪一路数据 $A_0$–$A_3$ 送到输出 X。关键洞察：任何信号与 0 相与得 0、与 1 相与保持不变，AND 门可当门控开关。实现 = 选择逻辑（把 $S_1{S}_0$ 译码成四条”选中线”，每条是相应选择变量的与组合）+ 门控逻辑（每条选中线去”使能”对应数据的 AND 门，各 AND 输出再进一个 OR 门）。若直接画 6 输入真值表将有 64 行，分解成”译码 + 门控”后，扩展到 8 路（11 输入、2000+ 行真值表）也轻而易举——这就是结构化设计的价值。

例：BCD→七段译码器：输入 4 位 BCD 数（0–9），输出 7 段 a–g 驱动 LED（12.3 节）。对每段画卡诺图化简，10–15 的输入组合全部是无关项，可大胆利用以简化电路（同一输入接多个段输出，每段一张卡诺图）。

关键要点

• ‘1’/‘0’ 表示二值状态（开/关、真/假）；真值表罗列全部输入组合。
• 基本门 AND、OR、NOT 加上复合门 NAND、NOR、XOR、XNOR 构成所有数字功能。
• 组合逻辑输出只取决于当前输入；时序逻辑还取决于历史。
• 布尔代数（恒等式、交换/结合/分配/吸收律、德摩根定理）用于描述与化简；表达式不唯一。
• 最小项法：真值表每个 1 写一个最小项再相或（积之和）。
• 卡诺图：相邻只差一位的格子圈 $2^n$ 个 1，消 n 个变量；无关项按需当 1。
• 逻辑门有传播延迟，可能产生竞争冒险，用冗余乘积项消除。
• 常用数制：二、八、十、十六进制；乘除 2 法做十进制↔二进制转换；4 位二进 ↔ 1 位十六进制。
• 半加器/全加器构成加法器；半减器/全减器构成减法器。
• BCD、格雷码（相邻只差一位）、ASCII、奇偶校验/校验和/汉明码各有用武之地。

Success

一张表记清核心门输出（两输入）：与”双 1”、或”有 1”、与非”双 1 反”、或非”全 0 才 1”、异或”不同才 1”、同或”相同才 1”。半加器的和就是异或、进位就是与。

Warning

常见三错：德摩根拆线忘翻转符号（$\overline{A+B}\ne \bar{A}+\bar{B}$）；噪声源/无关项概念混淆——无关项只能用于永不出现的输入组合；卡诺图合并忘”边对边相邻”而漏圈最大组，导致表达式不是最简。

自测五题

1. 实现三输入 NAND 的布尔式并写出输出为 1 的行。 $C=\overline{ABC}$。三输入 NAND 输出为 1 当且仅当输入不全为 1，即除 111 外其余 7 行输出都为 1。

2. 用德摩根把 $\overline{A+B}$ 展开，并用它说明 NOR 门可当作什么组合。 $\overline{A+B}=\bar{A}\cdot \bar{B}$：OR 反相后 = 各输入先取反再相与。也可看作”两输入都为 0 时输出 1”。

3. 对最小项法：4 变量表中输出为 1 的行是 0011、1010、1111，写出表达式。 逐行写积：$\bar{A}\bar{B}CD$（0 0 1 1）、$A\bar{B}C\bar{D}$（1 0 1 0）、$ABCD$（1 1 1 1），相或即 $X=\bar{A}\bar{B}CD+A\bar{B}C\bar{D}+ABCD$。

4. 化简 $X=\bar{A}B+AB$ 并说明用了哪条规则。 $X=B(\bar{A}+A)=B\cdot 1=B$（分配律 + 互补律 $A+\bar{A}=1$）。结果与 A 无关。

5. 把 $2E_{16}$ 转十进制、把 $27_{10}$ 转二进制，并说明格雷码相对普通二进制的优势。 $2E_{16}=2\times 16+14=46_{10}$。$27_{10}÷2$ 依次余 1、1、0、1、1 → $11011_2$。格雷码相邻码只差一位，异步读数时非旧即新，不会出现中间乱码。