数字逻辑

1. 布尔代数基础

布尔代数是数字逻辑的数学基础，由 George Boole 于 1854 年提出，变量取值仅为 0 和 1。

1.1 基本运算

1.2 布尔代数定律

基本定律：

• 交换律：$A + B = B + A$，$A \cdot B = B \cdot A$
• 结合律：$(A + B) + C = A + (B + C)$
• 分配律：$A \cdot (B + C) = A \cdot B + A \cdot C$
• 同一律：$A + 0 = A$，$A \cdot 1 = A$
• 补元律：$A + \overline{A} = 1$，$A \cdot \overline{A} = 0$

德摩根定律（De Morgan’s Law）：

$\overline{A \cdot B} = \overline{A} + \overline{B}$

$\overline{A + B} = \overline{A} \cdot \overline{B}$

吸收律：

$A + A \cdot B = A$

$A \cdot (A + B) = A$

1.3 布尔函数化简

卡诺图（Karnaugh Map）：用于4变量以内的布尔函数化简。

2变量卡诺图：

        B=0  B=1
  A=0 |  m0 | m1 |
  A=1 |  m2 | m3 |

奎因-麦克拉斯基法（Quine-McCluskey）：适用于任意变量数的系统化化简方法。

2. 逻辑门电路

2.1 基本逻辑门

2.2 万能门

NAND 和 NOR 门被称为万能门，因为仅用一种即可实现所有逻辑功能：

用 NAND 实现 NOT：

$\overline{A} = \overline{A \cdot A}$

用 NAND 实现 AND：

$A \cdot B = \overline{\overline{A \cdot B}}$

用 NAND 实现 OR：

$A + B = \overline{\overline{A} \cdot \overline{B}}$

2.3 传输延迟

逻辑门的输出不是瞬时变化的，存在传播延迟：

$t_{pd} = \max(t_{pLH}, t_{pHL})$

其中 $t_{pLH}$ 为低→高延迟，$t_{pHL}$ 为高→低延迟。

3. 组合逻辑电路

组合逻辑电路的输出仅取决于当前输入，无记忆功能。

3.1 编码器与译码器

编码器：将 $2^n$ 条输入线编码为 $n$ 位二进制输出。

优先编码器：允许多个输入同时有效，优先级最高的输入被编码。

译码器：将 $n$ 位二进制输入译码为 $2^n$ 条输出线中的一条。

3-8 译码器：
  输入：A2, A1, A0
  输出：Y0~Y7（仅一个为有效）

3.2 多路选择器（MUX）

从 $2^n$ 条输入中选择一条输出：

$Y = \sum_{i=0}^{2^n-1} D_i \cdot m_i$

其中 $m_i$ 为选择变量对应的最小项。

用 MUX 实现任意逻辑函数：$n$ 变量函数可用 $2^{n-1}$ 选 1 的 MUX 实现。

3.3 加法器

半加器：

$S = A \oplus B, \quad C = A \cdot B$

全加器：

$S = A \oplus B \oplus C_{in}$

$C_{out} = A \cdot B + C_{in} \cdot (A \oplus B)$

行波进位加法器（RCA）：$n$ 位加法器延迟为 $O(n)$。

超前进位加法器（CLA）：

生成函数：$G_i = A_i \cdot B_i$

传播函数：$P_i = A_i \oplus B_i$

$C_{i+1} = G_i + P_i \cdot C_i$

延迟为 $O(1)$（理想情况），但硬件复杂度随位数增加而急剧增大。

3.4 比较器

判断两个数的大小关系：

$A > B, \quad A = B, \quad A < B$

$n$ 位比较器从最高位开始逐位比较。

4. 时序逻辑电路

时序逻辑电路的输出不仅取决于当前输入，还与电路的历史状态有关。

4.1 锁存器与触发器

SR 锁存器：

D 触发器：最常用的触发器，在时钟上升沿采样 D 输入：

$Q(n+1) = D$

JK 触发器：

T 触发器：

$Q(n+1) = T \oplus Q(n)$

4.2 寄存器与移位寄存器

• 寄存器：由 $n$ 个 D 触发器组成，存储 $n$ 位数据
• 移位寄存器：支持左移、右移操作
• 通用移位寄存器：支持并行加载、左移、右移、保持

4.3 计数器

同步计数器：所有触发器共用同一时钟。

异步计数器：触发器时钟来自前一级输出，存在延迟累积。

模 $N$ 计数器：计数范围为 $0$ 到 $N-1$。

$n$ 位二进制计数器的模为 $2^n$。

5. 有限状态机（FSM）

5.1 Moore 型状态机

输出仅取决于当前状态：

$\text{输出} = f(\text{当前状态})$

5.2 Mealy 型状态机

输出取决于当前状态和当前输入：

$\text{输出} = f(\text{当前状态}, \text{当前输入})$

5.3 状态机设计步骤

1. 根据问题描述确定输入、输出和状态
2. 绘制状态转换图
3. 状态化简（消除等价状态）
4. 状态编码（二进制编码、独热编码等）
5. 求状态方程和输出方程
6. 画逻辑电路图

5.4 示例：序列检测器

检测输入序列中的 “101”：

状态定义：
  S0: 初始状态
  S1: 检测到 1
  S2: 检测到 10
  S3: 检测到 101（输出=1）

状态转换表：
  S0 --1--> S1  S0 --0--> S0
  S1 --0--> S2  S1 --1--> S1
  S2 --1--> S3  S2 --0--> S0
  S3 --1--> S1  S3 --0--> S2

6. 存储器结构

6.1 存储器分类

6.2 存储器容量扩展

• 位扩展：增加数据位宽（并联芯片）
• 字扩展：增加地址空间（译码器选择芯片）
• 字位同时扩展：两者结合

6.3 存储器访问时间

$\text{访问时间} = t_{AA} \text{（地址到输出有效）}$

$\text{周期时间} \geq \text{访问时间} + \text{预充电时间}$