组合逻辑电路

• 二值逻辑和逻辑门
  • 二值逻辑
    • 参考命题逻辑和布尔代数。
    • 数字逻辑中的表示与记号：
      • 与：$AB$
      • 或：$A+B$
      • 非：$\overline A$
  • 逻辑门
    • 
    • 逻辑门具有门延时，电路的时钟一般比其大一两个数量级。
  • 定时图
    • 定时图的横坐标是时间，纵坐标是 $0$ 或 $1$。
• 布尔代数
  • 布尔函数
    • 布尔函数的变量取值为 $0$ 或 $1$，用与、或、非等运算组合表达式。
  • 反函数
    • 求反函数的方法：
      • 利用德摩根律。
      • 求原函数的对偶式再将每个变量取反。
  • 标准形式
    • 标准形式是最小项 / 极小项的和或最大项 / 极大项的积。
    • 最小项之和可以记作 $\sum m(x_1,x_2,\dots)$，最大项之积可以记作 $\prod m(x_1,x_2,\dots)$。
    • 对标准形式进行化简，可以得到积之和和和之积。
• 卡诺图和两级电路优化
  • 电路的成本标准
    • 文字成本 L：布尔函数中的文字总数。
    • 门输入成本 G：电路中逻辑门的输入端口总数，不考虑非门。
    • 考虑非门的门输入成本 GN：类似 G，同一个变量的非门只计算一次。
  • 卡诺图
    • 卡诺图是一个二维表，行和列的头部是变量的格雷码序列。
    • 单元格与最小项对应，将行和列编码组合就得到最小项编号，写在右上角。
    • 布尔函数表示为卡诺图时，所有最小项在对应单元格中写 $1$，其他不写。
      • $1$ 格子为函数的最小项，也是反函数的最大项。
      • $0$ 格子为函数的最大项，也是反函数的最小项。
    • 卡诺图的边界是循环的，即左右两个边界相邻，上下两个边界相邻。
  • 积之和优化
    • 首先画出真值表对应的卡诺图。
    • 概念介绍：
      • 蕴涵项：卡诺图中完全包含 $1$ 的矩形，且矩形的包含的格子数为 $2^n$。
      • 主蕴涵项：无法再继续扩大的蕴涵项。
      • 质主蕴涵项：存在一个格子仅被当前矩形覆盖的主蕴涵项。
    • 优化方法：
      • 找出所有的主蕴涵项，在卡诺图中用矩形框出。
      • 确认每个主蕴涵项是否是质主蕴涵项，并选择所有质主蕴涵项。
      • 若所有质主蕴涵项不能覆盖所有 $1$ 格子，则再尝试选择一些主蕴涵项。
      • 选择的每个主蕴涵项表示一个乘积项
        • 若同时覆盖变量 $X$ 的两种文字 $X, \overline X$，则乘积项中不包含 $X$。
        • 若只覆盖变量 $X$ 的一种文字 $X$ 或 $\overline X$，则则乘积项中包含 $X$ 或 $\overline X$。
      • 将每个主蕴涵项对应的乘积项相加，得到积之和。
  • 和之积优化
    • 画出函数 $F$ 真值表对应的卡诺图，在图中标记取值为 $0$ 的格子。
    • 用类似积之和优化方法合并 $0$ 格子，得到 $\overline F$ 的积之和。
    • 对 $\overline F$ 求对偶式在取反变量，得到 $F$ 的和之积。
  • 无关最小项优化
    • 某些情况下，不需要考虑一些最小项对应的函数取值，这些最小项称为无关最小项。
    • 卡诺图将无关最小项标记为 $\times$。
    • 无论是积之和优化还是和之积优化，合并格子时都可以选择合并无关最小项或者不合并。
• 工艺映射
  • 完备逻辑门
    • 与非门和或非门都是完备逻辑门，所有逻辑门可以展开为与非门和或非门。
    • 与非门和或非门有多个种类，每个种类拥有不同数量的输入端口。
    • 工艺映射就是将使用其他逻辑门的电路展开为使用与非门和或非门的电路并优化。
  • 映射为与非门电路
    • 映射规则：
      • 非门可以看作单输入的与非门和或非门。
      • 与门展开为 $\overline{\operatorname{NAND}(X_1, X_2, \dots)}$。
      • 或门展开为 $\overline{\operatorname{NAND}(\overline X_1, \overline X_2, \dots)}$。
      • 可以将非门推过并联电路的分支点，干路上的一个非门和每个支路上都有一个非门可以互相转化。
      • 在同一条路上的两个非门可以压缩。
    • 应用这些规则，尽可能减少逻辑门数量。
  • 映射为或非门电路
    • 映射规则：
      • 非门可以看作单输入的或非门。
      • 与门展开为 $\overline{\operatorname{NOR}(\overline X_1, \overline X_2, \dots)}$。
      • 或门展开为 $\overline{\operatorname{NOR}(X_1, X_2, \dots)}$。
      • 其他与“映射为与非门电路”类似。