组合逻辑

组合电路

定义

• 每个电器元件
• 每个电路节点、电路输入、或是链接到外部的电路的一个输出端
• 电路不包含回路（每条路径最多只能经过每个电路节点一次）

电路组成

• 离散输入端
• 离散输出端
• 描述输入输出关系的功能规范（function specification）
• 描述输入改变时输出延迟相应的时序规范（timing specification）

组合电路的输出仅仅取决于输入值。

• 例子：逻辑门
• 特点：无记忆

生产中常用“逻辑综合”，通过逻辑函数化简电路。

逻辑门

• Bubble 圆圈代表取反
• N 输入 XOR 可用于奇偶校验，奇数个 1 时输出 1
• 两输入 XNOR（异或非门）也成为相等门，输入相等为 1

逻辑电平

连续到离散的映射，施加静态约束

组合逻辑

• 极大项：析取（+）
• 极小项：合取（*）
• 主析取范式：极小项析取，为 True 的可能
• 主合取范式：极大项合取，为 False 的可能
  • 以上两者，为二级组合逻辑。
• 详细见离散数学。

多级组合逻辑

用的硬件更少，推气泡法很有用。

X和Z

X：非法值

此节点同时由0和1驱动、未知值（没有初始化）

Z：浮空值

状态取决于系统之前的状态

常用组合电路：

• 优先级电路
• 复用器（多路选择器）：2^N输入的复用器可以通过把合适的输入连接到0或1上，实现任何N输入逻辑函数。可以优化为用2^(N-1)实现N输入逻辑函数。 方法是将变量、0与1作为复用器输入，用变量控制输出。（P49）最后实现将复用器当作查找表。
• 译码器：N个输入，$2^N$ 个输出。
  • 独热：给定时间只有一个输出为高电平。
  • 可以和或门组合实现逻辑函数（译码器每个输出为一个极小项）。
  • 很容易以此表示析取范式。真值表包含M个1的N输入函数，可用N: 2^N译码器和M输入或门实现。
• 编码器：译码的逆过程。
  • 优先编码器：可以同时有多个输入，对优先级最高的编码。
• 数值比较器

算术电路

加法

• 半加器
• 全加器（1 位）
• 进位传播加法器（CPA）（N 位）
  • 分类：
    • 行波进位加法器：
      • 结构：把 N 个全加器串联，前一位的 $C_{out}$ 就是下一级的 $C_{in}$。
      • 缺点：N 比较大时比较慢
    • 先行进位加法器（CLA）:
      • 结构：把加法器分解为若干块，每块有进位时快速确定此块输出进位。
    • 前缀加法器
  • 溢出判断：$Overflow=Ci{n}_{n-1}\oplus Cou{t}_{n-1}$ ，1 则溢出。

减法

将被减数转为补码后相加。

即控制 B 取反（与 1 异或），然后初始进位设为 1。
$Y=A-B=A+\overline{B}+1$

特别注意此时的进位（Carry）：$Borrow=\overline{Carry}$

比较器

• 相等比较器：
  • 功能：产生一个布尔值，说明是否 A == B
  • 实现：按位异或、取或，输出为 0 则相等
• 量值比较器：
  • 功能：产生一个或多个输出，说明 A，B 的关系值。
  • 实现：计算 A - B 的值，以 slt 为例，
    • 有符号：检查符号位，若 1 则 $A<B$，否则 $A\ge B$。实际上，考虑溢出，应该是：$Set=Su{m}_{n-1}\oplus Overflow$
    • 无符号：如果 A - B 发生借位，那么 $A<B$，否则 $A\ge B$，因此 $Set=Cou{t}_{N-1}$。

ALU

将多种算术、逻辑运算组合至一个单元，可以执行加减、量值比较、AND 和 OR 等运算。

移位器和循环移位器

• 作用：移动位，完成 2 的幂的乘除法。
• 分类：
  • 逻辑移位器：0 填充空位
  • 算术移位器：右移补充符号位，左移和逻辑移位器一致
  • 循环移位器：从一端移走的数字重新填充到另一端

时序

组合电路的时序特征包括传播延迟、最小延迟

• 传播延迟（t_pd） 当输入改变，直到一个或者多个输出达到最终值所经历的最长时间
• 最小延迟（t_cd） 当一个输入改变，直到任意一个输出改变的最短时间
  因此路径分为关键路径、最短路径
• 关键路径：经过的门多，耗时最长，最慢，限制了电路运行速度
• 最短路径：经过的门少，耗时最短，最快。
  组合电路的：
• 传播延迟是关键路径的每一个原件的传播延迟之和；
• 最小延迟是最短路径上每个元件的最小延迟之和。
  因此设计电路时：
• 控制关键：关键路径是控制-输出；数据关键：关键路径是数据-输出
• 若控制信号先到达，选择最短数据-输出延迟的设计，vice versa.（后来者要快，不要让先来的等太久）

毛刺（P54）

原因： 时序

• 穿越卡诺图两个圈边缘可能会有毛刺，即下一个合取式对应的信号输入准备好前，由于信号变化，目前合取式的信号改变了，导致输出短暂的“失真”。
• 多个输入上的同时变化也会导致毛刺，无法增加硬件避免。

措施

• 在读取输入前等待传播延迟消逝即可。（选通法）
• 也可以通过增加门电路，增加冗余项，避免直接从卡诺图的一个圈到另一个圈。
• 在电路输出端并联滤波电容的方法消除尖峰脉冲。（滤波法）

并非所有的毛刺都可以消除，因此关键不在于避免，在于意识到其存在。