数字逻辑

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,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,A=B,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{周期时间}\ge \text{访问时间}+\text{预充电时间}$