本篇笔记概述了组合逻辑设计的基本概念与自动化过程，包括逻辑表示方法、设计过程、工艺映射、集成电路的分类、基本逻辑函数、译码器与编码器的功能，以及加法器和减法器的实现。通过分层设计和不同的设计方法，笔记详细探讨了如何优化和验证逻辑设计，确保其在实际应用中的有效性和效率。（由 gpt-4o-mini 生成摘要）

1. 设计概念与自动化 Design Concepts and Automation

1.1. 表示逻辑的方法

• 真值表
• 布尔函数
• 卡诺图
• 时序图(timing diagram)
• 逻辑电路图(logic circuit)

2. 设计过程 Design Procedure

1. 系统描述(specification): 指定所需的行为。
2. 形式化(formalization)：以布尔方程或真值表的方式对系统的输入输出关系进行形式化
3. 优化(optimization)：优化逻辑的表示，减少成本。
4. 工艺映射(technology mapping)：将优化后的逻辑设计工艺映射到可以实现的工艺上。
5. 验证(verification)：验证设计的正确性。

2.1. 分层设计 Hierarchical Design

对于复杂的数字系统，一种典型的设计方法为分层设计(hierarchical design)，即将复杂问题模块化分解为若干层次，然后逐个抽象解决。

• 最小层的模块(block) 叫做原子模块(primitive block)。Any block that cannot be further decomposed is called a primitive block.
• 由不同层级的基本块组成的集合叫做层次结构(hierarchy)。The collection of all blocks including the decomposed ones is a hierarchy.

分层设计的设计方法可以分为

• 自顶向下的设计(top-down design)：分解功能设计。A top-down design proceeds from an abstract, high-level specification to a more and more detailed design by decomposition and successive refinement. Top-down design answers: What are we building?
• 自底向上的设计(bottom-up design)：根据现有的元件去组合成目标功能。A bottom-up design starts with detailed primitive blocks and combines them into larger and more complex functional blocks. Bottom-up design answers: How do we build it?

一般从两个方向同时进行设计。一般 top-down 设计控制复杂度，bottom-up 设计聚焦于细节。

2.2. 工艺映射 Technology Mapping

工艺映射是指将优化后的逻辑设计工艺映射到有限的工艺上。

比如：因为 NAND 门和 NOR 门是通用门(universal gate)，我们可以将任意逻辑电路映射到仅使用 NAND 门或仅使用 NOR 门的电路上。

2.2.1. 无传播延迟子电路 Fan-out Free Subcircuit

传播延迟(fan-out)：一个逻辑门的输出连接到多个其他逻辑门的输入时，负载增加将导致的延迟增加。

无传播延迟子电路(fan-out free subcircuit)：寄存器的输出不直接连接到其他逻辑门的输入，而是通过一个专门的数据总线或信号线连接到其他部分。a circuit in which a single output cell drives only one other cell.

课件 P38，还没太懂这一部分想干嘛

3. 集成电路 Integrated Circuits

集成电路(integrated circuit)，即芯片(chip)，分为如下若干等级：

• 小规模集成电路(small-scale integrated, SSI)：内含不到 10 个门；
• 中等规模集成电路(medium-scale integrated, MSI)：内含 10 ~ 100 个门；
• 大规模集成电路(large-scale integrated, LSI)：内含成百上千个门；
• 超大规模集成电路(very large-scale integrated, VLSI)：内含成千上亿个门。

4. 基本逻辑函数 Rudimentary Logic Functions

四个初等组合逻辑函数：

• 定值函数(value-fixing function)：$F=1$ or $F=0$, no Boolean operator. 可以表示接电源或接地。
• (transfering)：$F=X$, no Boolean operator.
• (inverting)：$F=\overline{X}$, involves one logical gate.
• 使能函数(enabling function)：$F=X\cdot EN$ or $F=X+\overline{EN}$, involves one or two logic gates.这里 $F=X\cdot EN$ 在使能信号 $EN$ 为 $1$ 是被激活，否则恒为 $0$。$F=X+\overline{EN}$ 同样需要使能信号 $EN$ 为 $1$ 来激活，但未激活时恒为 $1$。

5. 译码器 Decoder

译码(decoding)：把 $n$ 位二进制输入转化到 $m$ 位二进制输出的过程。保证 $n\le m\le 2^n$ 使得每一个合法输入都有一个不同的输出。

5.1. 二进制译码器 Binary Decoder

给定 $n$ 位二进制代码，将 decode 为其对应的最小项。

因为任意组合逻辑函数都可以写成 sum of minterms 的形式，我们可以用二进制译码器+或门来表示任意组合逻辑

5.2. 译码器与使能结合 Decoder with Enable

在普通译码器的基础上多一个使能信号(enable) EN 来控制，当 EN 为 0 时无论 $A_{0}\sim A_{n-1}$ 什么值都输出全零，否则输出对应的最小项。

5.3. 多路分配器 Demultiplexer

cm：不考。

我们可以通过带使能信号的译码器，将来自一条输入线上的信息传送到 $2^n$ 条输入线中的指定一条，实现分配(distribution) 功能。

实现这一功能的电路称为多路分配器(demultiplexer = demux)。一个带使能的 $n$-$2^n$ 译码器又是一个 1-$2^n$ 多路分配器。其中 1 指的是输入信号的位宽(bit width) 是 1，这一输入直接接到 EN 输入处。

5.4. 7 位数码管译码器 BCD-to-Segment Decoder

实现 7 位数码管译码器，可以通过逻辑门实现布尔函数，也可以直接用上面实现多路分配器。

关于 7 位数码管内部构造，可采用共阳极(common anode) 接法或共阴极(common cathode) 接法，其中前者是 0 触发，后者是 1 触发。参见下图：

6. 编码器 Encoder

编码(encoding)：the conversion of an $m$-bit input code to a $n$-bit output code with $n\le m\le 2^n$ such that each valid code word produces a unique output code.

6.1. 优先编码器 Priority Encoder

优先编码器(priority encoder) 的作用是的当多个输入同时为 1 时，优先级最高的输入需要被优先处理。所以我们需要实现一个编码器，输出优先级最高的为 1 的输入是多少。其真值表如下：

可以提供不少无关项用于化简。

6.2. 多路选择器 Multiplexer

用一组 $n$ 位的输入信号（称为选择输入(selection input)）选择 $2^n$ 位的输入信号中的一路到输出，实现这一功能的电路称为多路选择器(multiplexer = mux)，也被叫作多路分配器。

7. 二进制加法器 Adder

7.1. 半加器 Half-Adder

半加器(half-adder)：实现两位相加的组合电路。

真值表	卡诺图	逻辑函数

如果我们选用不同的逻辑函数，就可以有不同的电路实现。其中，最常见的半加器实现如下：

一个只使用 NAND 门的半加器实现如下：

7.2. 全加器 Full-Adder

全加器(full-adder)：实现三位相加（两位及一位进位(carry-in bit)）的组合电路。

真值表	卡诺图

• 进位产生函数(carry generate function) - $X\cdot Y$：当 $X$ 和 $Y$ 都是 $1$ 时就会发生进位。一般简写成 $G$。

• 进位传递函数(carry propagate function) - $X \oplus Y$：当 $X$ 和 $Y$ 中恰有一个是 $1$ 的话，如果收到一个来自低位的进位，就一定会传递给高位。一般简写成 $P$。

一个全加器相当于由两个半加器组成，因为实际上你就是把 $X,Y,C$ 三个数加起来，用了两个半加：

7.3. 行波加法器 Ripple-Carry Binary Adders

7.4. 超前进位加法器 Carry Lookahead Adder

通过把进位展开，我们直接计算最后产生的进位，这里以 4bit 的超前进位加法器为例：

其电路实现如下：

考察超前进位加法器的性能：

• 全加器部分：从 $A_i,B_i$ 变成 $G_i$，只需要经过一个异或门，消耗 3 单位时间。
• CLA 部分：虽然看起来有很多个 AND、看起来电路很复杂，但是注意到与门可以多输入同时做，故实际信号只经过了一个与门和一个或门，消耗 2 单位时间。
• 再回到全加器部分：像 $C_1,C_2,C_3$ 信号，不像 $C_4$ 可以直接输出，需要回到全加器部分再经过一个异或门，消耗 $3$ 单位时间。

这样我们就得到了一个最大延迟只有 $3+2+3=8$ 个单位的 4bit 超前进位加法器。

那如果我们需要 16-bit 的超前进位加法器呢？注意到中间门电路的输入数量是 $O(n^2)$ 级别的，如果一味增大 CLA，消耗的成本太高。实际上，只需要把上面电路图中的全加器替换成 CLA，就是一个 16 位的超前进位加法器。（4-bit：全加器 $\rightarrow$ CLA；16-bit：全加器 $\rightarrow$ CLA $\rightarrow$ CLA）

计算此实现下的 16-bit 超前进位的性能：

8. 二进制减法器 Subtractor

• 被减数(minuend)
• 减数(subtrahend)

8.1. 无符号减法 Unsigned Subtraction

方法如下：

8.2. 有符号减法 Signed Subtraction

8.3. 溢出检测 Overflow Detection

在同符号数字相加、异符号数相减时可能发生溢出。