7 / 63 · 概念

布尔代数、等价变换与实现成本

利用德摩根定律和提取公因式变换电路，区分逻辑等价与时序特性。

等价表达式对所有输入产生相同输出

简化组合电路的目标不只是缩短表达式。必须在保持功能的同时考虑逻辑级数、扇入、扇出和实际库单元。首先将布尔代数^{布尔代数处理 0、1 及 AND、OR、NOT 的代数。这里的加号通常表示 OR，因此规则与整数加法不同。}中的 $+$ 与乘法记号分别理解为 OR 和 AND。

A+AB=A,\qquad A+\overline A B=A+B

第二个表达式可以分类验证： $A=1$ 时两边都为 1， $A=0$ 时两边都为 $B$ 。使用熟记的恒等式后，仍应能够解释其含义。

\overline{AB}=\overline A+\overline B,\qquad \overline{A+B}=\overline A\,\overline B

例如 $Y=AB+AC$ 等价于 $A(B+C)$ 。前者可画成两个 AND 加一个 OR，后者可画成一个 OR 加一个 AND。不过，输入到达时间或负载不同，门数较少的结构并不一定更快。

共识定理也很有用。

AB+\overline A C+BC=AB+\overline A C

在 $BC=1$ 时，若 $A$ 为 0，则 $\overline A C$ 已为 1；若为 1，则 $AB$ 已为 1，因此 $BC$ 对稳态功能是冗余项。但删除它可能改变转换瞬间的冒险特性。后面的延迟课程会讨论这一差别。

每一列表示一种 ABC 输入组合，而不是时间推进。请检查两个输出是否在所有列都相同。门数与路径可以不同，但对于稳定的 0/1 输入，功能相同。

AB + AC 与 A(B + C) 的等价性

查看波形数据

将变换前后分别记为 y_ref 与 y_opt；对于较小的输入空间，比较全部输入。不能因为通过一两个实例测试就断定等价。

SystemVerilog
assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

在八种 0/1 输入组合中，mismatch 必须始终为 0。包含 X/Z 的四态仿真以及时序电路的等价性，还需要附加条件。明确说明已证明的范围，是设计评审的基本习惯。

简化 $F=\overline A B+AB+A\overline B$ ，并写出需要验证的输入组合数。

阅读解释

前两项为 $B(\overline A+A)=B$ ，所以 $F=B+A\overline B=A+B$ 。只有两个变量，需检查四种组合。表达式等价并不意味着两种实现的传播延迟相同。