Chap 2 Combinational Logic Circuits¶

逻辑运算¶

逻辑运算的对象是布尔变量，也就是 0/1 二值。

主要的运算就是 与(AND)，或(OR)，非(NOT)，异或(XOR)，以及 与非(NAND)，或非(NOR)，同或(XNOR)。

运算规则挺简单的，在此略去。

比较基础的，需要了解与或非的符号表示。

• A AND B 可写作 \(A\cdot B\) 或者 \(AB\)；
• A OR B 可写作 \(A+B\)；
• NOT A 可写作 \(\overline{A}\)；

由此可以进行一些组合，例如：

• A NOR B 可写作 \(\overline{A+B}\)；
• A NAND B 可写作 \(\overline{A\cdot B}\)；

再次还需要提到的是 德·摩根定律(De Morgan's Laws)，其表述为：

• \(\overline{A+B} = \overline{A}\cdot\overline{B}\)；
• \(\overline{A\cdot B} = \overline{A}+\overline{B}\)；

逻辑门¶

逻辑门是在硬件层面上实现布尔代数的逻辑单元。其操作对象为高低电平。

如图，(a)中绘制了三个常用逻辑门的符号；(b)中则描述了这些运算在 时序图(timing diagram) 中的状态；(c)则描述了在延时（见下）效应下的时序图。

还有一个注意点是，非门其实更多的被称为 inverter，而非 NOT。

但是由于是物理层面的实现，所以会有一些逻辑运算层面不会出现的问题，比如 延时(delay)。

延时的长短与很多因素有关，取决于逻辑门的实现技术。而且通常来说，对于不同运算参数，其延时也会有不同。

此外，与门和或门可能有更多的输入引脚，如下：

至此，给出了 AND, OR, NOT 三个门的符号表示，类似上一小节提到的那样，我们也可以利用这三个基础的门电路来构成其他的门电路（虽然通常来说，我们可能是通过 NAND + NOT 来实现 AND 的）。

于是又引申出一个概念——通用门(Universal Gate)。一个功能完全的，能够表示其他所有门的逻辑门被称为通用门，在我们学过的逻辑门中，NAND 和 NOR 都是通用门。

布尔代数¶

literal ~ 字面量，也就是“变量”。

运算律¶

这张图片总结了布尔运算中的运算律，个人感觉最需要强化记忆的是 15 条，因为布尔代数借用了普通代数的符号，但第 15 条在普通代数中并不成立，所以对于习惯这套符号的人来说可能不太 straightfoward。

在记忆这套运算规律的时候，我个人的一个想法是，一定要建立 与 和 或 是对等的观念。我们习惯用“真”去理解这两个运算，但是实际上如果你以“假”为主体去分析这两个运算，会发现和“真”是完全对称的。换言之， 与 和 或 是完全对称的运算，而非像他们借用的符号 \(\times\) 和 \(+\) 那样存在非对称关系。

但是让这件事变得又没那么简单的事情是，虽然 与 和 或 是对等的，但是我们在借用普通代数符号体系的同时，又人为地给他们添加了优先级（但是这也是必要的，否则表达式就会充满括号）。

优先级从高到低依次为：

1. 括号 / ()；
2. 非 / NOT / \(\overline A\)；
3. 与 / AND / \(\cdot\)；
4. 或 / OR / \(+\)；

个人感觉，这一种思路并不直觉，尤其是借用普通代数的符号体系以后更加混淆，所以可能需要一些练习来摆脱这些“刻板印象”。

运算律推广¶

除此之外，从上面提到的运算律中还能推广出如下几个模型：

对比前三个和后三个，我们再次发现，与 和 或 在逻辑上是对称的。

对偶法则¶

对偶法则(Duality Rule)：一个表达式的 对偶(dual) 为，将所有的 与 和 或 对调得到的式子（注意！需要保证参与运算的结构不能变（是“带括号”的宏展开），比如 一般情况下 \(A\cdot B\) 会被对偶为 \((A+B)\) 以保证运算顺序）。

而一般情况下，除非某个表达式是 自对偶(self-dual) 的，那么它的表现都与原表达式不同。

对偶表达式具有如下性质：

• 如果 F 的对偶是 G，那么 F 也是 G 的对偶，即对偶关系是对成的；
• 如果表达式 F 和 G 等价，那么他们的对偶也等价；

互补函数¶

一个 函数的互补(Complement of a Function) 指的是，将它的 对偶函数 中每一个 变量 都取反得到的函数，而该函数正好等于原函数的 非。

替代法则¶

替代法则(Substitution Rules): 如果将一个等式中 所有的 某个变量 都替换为同一个表达式，则等式依然成立。

一致性定理¶

在简化逻辑表达式的时候，一致性定理(Consensus Theorem) 也很有用：

其证明的第一步是这样的： \(XY+\overline{X}Z+YZ=XY+\overline{X}Z+(X+\overline{X})YZ\)，那后面就很简单了。本质上这个等式是利用了裂项，需要将其中最本质的部分，最小的粒度给裂开来，然后再慢慢消掉。

标准形式与规范形式¶

由于本质上相等的布尔表达式实际上有很多种写法，而且随着变量越来越复杂，他们之间的比较会很困难。所以我们需要定义一种形式，使得所有相同的表达式都能比较方便的“化简”为同一个形式，同时也能辨别出两个表达式是不同的。这就引入了 标准形式(Standard Forms)，包括 SOP 和 POS；以及 规范形式(Canonical Forms)，分别为 最小项之和(Sum of Minterms, SOM) 和 最大项之积(Product of Maxterms, POM)。

为了方便描述，在继续之前，我们先给出这样一张 🌰 真值表。

数值是随便搓的，请留意为什么为要在 Index 特地写出二进制的表述。

在开始之前，我需要强调，我们引入 SOM 和 POM 的目的是寻找一种比较典型的 表达，使得他们能够 确定 一张真值表。即，知道这种 表达 我们就足够写出这张真值表，反之亦然。

最小项之和 SOM¶

课本中对最小项的描述是：

A product term in which all the variables appear exactly once, either complemented or uncomplemented, is called minterm.

Its characteristic property is that it represents exactly one combination of binary variable values in the truth table.

用我的话来说，最小项之和就是挑出真值表中所有结果是 1 的最小项（比较模糊但直观，所以请先囫囵吞枣，我在“追加说明”会进一步说明）然后 OR 起来。显然，最小项之和的含义就是，一旦字面量取值的组合匹配了这几个“最小项”的其中一项，那么结果就是 1，符合了 OR 的“有1得1”的规则。

我们使用符号 \(m_{idx}\) 来表示变量组合 \(idx\) 是一个最小项，其中 \(idx\) 表示描述的那一项在真值表的序号，同时这个下标的二进制也能反映出字面量的组合。

例如，在 🌰 中，output 为 1 的项有：010 100 101 111 这四项，那么我们需要挑出来的最小项表达就分别是 \(m_{2}=\overline{X}Y\overline{Z}, \; m_{4}=X\overline{Y}\overline{Z}, \; m_{5}=X\overline{Y}Z, \; m_{7}=XYZ\)，这些变量表达式都是当且仅当变量组合为对应项时才会取 1 的表达式，可以认为，这写表达式唯一表达了这些真值表中的 1。

if(X == 1 && Y == 0 && Z == 1) {
    Output = 1;
} else {
    Output = 0;
}

if(X == 1 && (!Y) == 1 && Z == 1) {
    Output = 1;
} else {
    Output = 0;
}

Output = (X == 1 && (!Y) == 1 && Z == 1);

至此，我们得到了 🌰 所对应的 SOM：

再次归纳，使用通俗的话来说，最小项之和更像是“枚举了所有 1 的可能”，只要匹配了这个“和”中的某一项（事实上不做化简的话你也只能满足一项的值取到 1），表达式的值就会变成 1；而一个都不匹配的，自然就只能得到 0。

最大项之积 POM¶

就像我之前不断不断不断强调的，所谓的 1 和 0 都只是人为定义的，摆脱潜意识里对这两者之一的倾向（例如我本人就一直很倾向于以 1 为主体研究问题）会对理解最大项之积和逻辑表达式化简很有帮助。

而最大项之积——以我个人的愚见——就是以 0 为主体来研究真值表的特征的。

课本中对最大项的描述是：

A sum term that contains all the variables in complemented or uncomplemented form is called a maxterm.

与最小项对比，无非是把 "product term" 换成了 "sum term"，也就是把 AND 换成了 OR。

而最大项之积，就是挑出所有结果为 0 的最大项（“挑出”的定义我已经在 SOM 的追加说明中给出，在 POM 的追加说明中我还会再一次提及），再做 AND。以 1 为主体描述 AND 是“都1出1”，而以 0 为主体描述 AND 则是“有0出0”，这与 OR 的“有1出1”也是高度对称的（反之亦然）。也就是说，最大项之积的含义是，在最大项之积中，只要字面量取值的组合匹配这几个“最大项”的其中一项，整个表达式的结果就会变成 0。

类似的，我们使用符号 \(M_{idx}\) 来表示变量组合 \(idx\) 是一个最大项，其中 \(idx\) 表示描述的那一项在真值表的序号，同时这个下标的二进制也能反映出字面量的组合。

例如，在 🌰 中，output 为 0 的项有：000 001 011 110 这四项，那么我们需要挑出来的最小项表达就分别是 \(M_{0}=X+Y+Z, \; M_{1}=X+Y+\overline{Z}, \; M_{3}=X+\overline{Y}+\overline{Z}, \; M_{6}=\overline{X}+\overline{Y}+Z\)。可以检验，只有代入他们对应的那一行真值表组合时，他们才会得到 0。

if(X == 1 && Y == 1 && Z == 0){
    Output = 0;
} else {
    Output = 1;
}

if((X == 0 || Y == 0 || (!Z) == 0) == 0){
    Output = 0;
} else {
    Output = 1;
}

// It might be too complex.
Output = !((X == 0 || Y == 0 || (!Z) == 0) == 0);
// So we can simplify it.
Output = (X == 0 || Y == 0 || (!Z) == 0);

至此，我们得到了 🌰 所对应的 POM：

同样再次归纳，使用通俗的话来说，最大项之积更像是“枚举了所有 0 的可能”，只要匹配了这个“积”中的某一项，表达式的值就会变成 0；而一个都不匹配的，自然就只能得到 1。

与最小项相比，一个枚举了所有的 1 的可能，一个枚举了所有是 0 的可能，对于一个二值表达式来说，两种 表达 都是充要的。

此时，我们还能发现：

例如：\(M_5 = \overline{X} + Y + \overline{Z} = \overline{ X\overline{Y}Z } = \overline{m}_5\)

关于这个发现的更多的例子和说明，可以看下面的第一个练习。

练习¶

接下来，我们将通过一些例子来进一步强化这些理解，并且挖掘一些神奇的特性。

题面答案

请分别写出如下真值表中 \(F\) 和 \(\overline{F}\) 的 SOM 和 POM。

答案： $$\begin{aligned} F(X,Y,Z) & = \sum m(0,2,5,7) \\ & = \overline{X}\,\overline{Y}\,\overline{Z} + \overline{X}Y\overline{Z} + X\overline{Y}Z + XYZ \\ & = \prod M(1,3,4,6) \\ & = (X+Y+\overline{Z})(X+\overline{Y}+\overline{Z})(\overline{X}+Y+Z)(\overline{X}+\overline{Y}+Z) \end{aligned}$$ $$\begin{array}{l} \overline{F}(X,Y,Z) & = \sum m(1,3,4,6) \\ & = \overline{X}\,\overline{Y}Z + \overline{X}YZ + X\overline{Y}\,\overline{Z} + XY\overline{Z} \\ & = \prod M(0,2,5,7) \\ & = (X+Y+Z)(X+\overline{Y}+Z)(\overline{X}+Y+\overline{Z})(\overline{X}+\overline{Y}+\overline{Z}) \end{array}$$ 于是我们发现一件很有意思的事情，\(F\) 的 SOM 的下标与 \(\overline{F}\) 的 POM 的下标是一样的；当然对于 \(F\) 的 POM 和 \(\overline{F}\) 的 SOM 也是一样的。这又印证了对称性。

之后的练习等我做了再添加x 如果做了的话x 😋

电路实现与优化¶

成本标准¶

在成本标准中，我们需要介绍的主要有三种标准，分别是：

• 按照字面量字面量计(literal cost)：\(L\)
• 按门输入计，不计非门(gate-input cost)：\(G\)
• 按门输入计，计非门(gate-input cost with NOTs)：\(GN\)

按照字面量字面量计¶

很直白，就是按照表达式中有多少字面量来计算，例如：

• \(F = BD + A\overline{B}C + A\overline{C}\,\overline{D}\) 中 \(L = 8\)；
• \(F = ABC+\overline{A}\,\overline{B}\,\overline{C}\) 中 \(L = 6\)；
• \(F = (A+B+C)(\overline{A}+\overline{B} + \overline{C})\) 中 \(L = 6\)；

可以想象，虽然这种计算方法非常的简单，但是感觉不太靠谱。比如，后面两个例子，虽然他们的 literal cost 是一样的，但是显然开销不太一样（因为一个是 3+3 一个是 2+2+2）。所以我们需要一个更合适的计算方法。

按门输入计¶

按照门输入计就是按照逻辑门输入引脚的总个数来计算，这里的输入并不仅仅是直接来自于字面量输入的那些引脚，也包括字面量做运算后得到的结果作为输入传入下一级逻辑门的引脚。

例如这张对应表达式 \(F = A+BC+\overline{B}\,\overline{C}\) 的图中：

• 绿色原点表示一级输入引脚；
• 蓝色方点表示二级输入引脚；
• 黑色三角表示非门的输入引脚；

也就是说，这里一共有 5 + 2 = 7 个输入引脚，以及 2 个非门输入引脚。

从表达式来看，它可以看作是每一层运算的参数数量求和，不过我们忽略非门。

例如，式子 \(F=AB+\overline{B}C+C\overline{D}\) 中，最顶层的运算是一个三输入或运算，所以有 3 个输入；接下来有三个二输入与运算，所以各计 2 个输入，一共 2 * 3 = 6 个输入，一共是 9 个输入。

当然，实际上从底层往上数更方便：

• A 和 B 各自算一个，AB 整体算一个，一共 3 个；
• 一共有三组类似 AB 的结构，所以一共是 3 * 3 = 9 个；
• 即 \(G=9\)；

总之，就是类似于在做算式化简，每做一次化简都需要计入一次操作数的数量。

而对于 gate-input cost with NOTs，只要再额外计入非门的输入即可。例如上面那个式子：

• 发现有两个被非了的字面量，所以要额外计 2 个，一共是 11 个；
• 即 \(GN=11\)；

接下来放几道例题。

卡诺图¶

卡诺图的思想¶

优化逻辑表达式最直白的思想就是减少门电路，也就是去减少 gate-input cost。那么要如何做呢？

我们考虑到逻辑运算律中的这个推广：\(XY+X\overline{Y}=X(Y+\overline{Y})=X\)，也就是说，如果两个最小项只差一个字面量的非，那么他们是可以合并的；当然，对称的，根据\((X+\overline{Y})(X+Y)=X+Y\overline{Y}=X\)，我们也可以得到这个结论对最大项也成立。

是不是觉得“只差一个”很耳熟？是的！我们想到了格雷码！假设我们将 n 个字面量排列成一个 n bits 的向量，那么只需要按照格雷码排序，一旦发现有相邻的最小项，我们就可以合并他们。

但这还不够充分，例如在一个有三个字面量的逻辑表达式中，“与一个表达式相邻”的表达式其实有三个，但是用线性的表示方法又没法很好的表示这一点，所以我们想到将它写成一张二维的表，即将字面量拆成两组 bit 向量，各自按照格雷码排列，形成一张二维表，这就是 卡诺图(Karnaugh Map)，也叫 K-map。

可以发现，任意两个相邻的格子都只差一个字面量的非，而且是充要的，即所有“相邻”都可以在这张图表现出来。

卡诺图的局限性¶

然而，上面的说法其实很牵强。因为一张二维表中，能与一个元素相邻的元素最多只有四个，也就是说我们撑死也只能用卡诺图表示 4 个字面量的情况（当然更多的变量也有处理的方法，但是多少有点麻烦了）。因此，实际上卡诺图只能用于化简非常简单的逻辑表达式。

卡诺图的结构¶

这里我们以 3 元的逻辑表达式为例，2 元和 4 元的思路是一样的。

同样，举一个 🌰 ：\(F(X,Y,Z) = \sum m(2,3,4,5)\)

首先我们按照比特向量的形式把最小项写出来：

接下来，我们来绘制卡诺图，我们将 bit 向量 [x, y, z] 拆成 [x] 和 [y, z] 做如下表格：

另外一种标注表格的方式是这样，它可能更清晰：

但是他们的本质都是格雷码。

4 元字面量的卡诺图则长这个样子：

使用卡诺图优化¶

已经讲了思想和卡诺图的结构，那么到底要如何利用卡诺图进行优化呢？

让我们回顾优化的方法，即合并相邻两项，也就是找到卡诺图中相邻的部分。但是这不够，我们还要思考是不是能合并已经相邻的部分，比如：

我们通过卡诺图，首先合并了 \(WXYZ\) 和 \(WXY\overline{Z}\)，\(WX\overline{Y}Z\) 和 \(WX\overline{Y}\,\overline{Z}\)，分别得到了 \(WXY\) 和 \(WX\overline{Y}\)，显然这两个东西也是可以合并的；而在卡诺图上，这表现为两个相邻的 1*2 的矩形。

总而言之，这种迭代合并的行为最终可以划归为这样一个行为：

我们在卡诺图中寻找若干 极大 的 2 幂矩形，即元素个数为 2 的幂次（自然边长也都为 2 的幂次）的矩形，而每一个矩形所覆盖的元素都应该是 最小项/最大项（一般都是做最小项）。需要注意，“循环”的性质仍然满足，即第一列和最后一列，第一行和最后一行也可以认为是相邻的。

例如：

例如：

再例如：

都是合理的卡诺图划分。

在得到这些划分后，我们就可以很方便地将这些项拎出来，写出它们的表达式。

而至于如何拎出来——不难发现，如果一个方框中，某一个字面量的值既可以是 0，又可以是 1 时（这里指的是输入的值，并非输出结果），在这个优化项的结果中就可以不用写出这个字面量；反之，如果这个字面量 \(X\) 的值都是 0，则结果中会包含 \(\overline{X}\)，如果都是 1，则结果中会包含 \(X\)。

不定项¶

不定项(Don't Cares) 指的是需要化简的逻辑函数中，没有给出定义的几项，它们可能是：

• 输入组合不会出现；
• 输入组合的输出不被使用；

对于这种项，在卡诺图中用 X 来表示，在最小项之和中用 \(\sum d(...)\) 表示。我们可以随意定义它们的输出，此时就可以利用这些项来方便我们的优化——当我们画出来的极大矩阵越大，成本就越低。

例如，我们定义一个函数，当输入的 BCD 码表示的数字大于等于 5 时返回 1，则它可以通过这样的形式来优化：

根据结果，写出优化后的表达式为：\(F(W,X,Y,Z) = W + XY + XZ\)。

蕴含项、主蕴含项与基本主蕴含项¶

蕴含项(implicant) 分为 主蕴含项(prime implicant) 和 基本主蕴含项(essential prime implicant)。

• 在卡诺图中，一个蕴含项就是任意一个包含 \(2^n\) 个 1 的单元；
• 而主蕴含项则是在卡诺图中的 极大 蕴含项；
  • 对于存在 Dont'cares 的 K-map，如果我们关注的是 1，那我们积极地将他们当作 1 来处理，反之亦然；
  • 但是单独的 X 不会被认为是主蕴含项；
• 基本主蕴含项是包含 只被它(基本主蕴含项)覆盖的 1 的主蕴含项；

如图，左侧的两个主蕴含项因为包括了 ⓵ 和 ⓶ 这两个唯一的 1，所以是基本主蕴含项；

而右侧的蕴含项则是一个冗余的蕴含项；

经典组合电路¶

三态门¶

三态缓冲器(3-State Buffer)

除了输入和输出，它还有一个 使能端(enable) 来控制输出。

所谓的三态指的是：

• 当使能端为 1，且输入为 1 时，输出为 1；
• 当使能端为 1，且输入为 0 时，输出为 0；
• 当使能端为 0，输出为 Hi-Z/Z/z(浮动，高阻态)；

复杂门¶

通过一些基本门组合出来的门，它们的表示方法大致如下：

激励

评论