表达式化简与三态缓冲器

定理化简表达式

我们学习了标准与或式和标准或与式以后，那么以后对于任何一个逻辑表达式都可以使用这种方法进行化简了，最终表示成标准与或式或者标准或与式。如下面这道题：

根据布尔表达式绘制原理图

我们知道任何一个逻辑表达式最终都可以转化成最简的标准与或式或者标准或与式，那么接下来我们在进行原理图绘制主要需要解决的问题就是如何绘制标准与或式或者标准或与式。这里我们只需要使用两级门电路即可以轻松表示与或式和或与式。

例如标准与或式，那么我们先试用一级与门写出所有最小项，然后在使用二级或门将所有的最小项相加即可，如当我们要用电路图表示下面的标准与或式时：

$$Y=\bar{A}\bar{B}\bar{C}+A\bar{B}\bar{C}+A\bar{B}C$$

我们先分别用一级与门分别表示出了三个最小项，然后在使用了一个三输入或门相加就得到了上面的逻辑表达式。

电路原理图绘制原则

原理图绘制需要遵循一致的风格，以便于阅读和检查错误，绘制的原则如下：

1. 输入在原理的左边（或顶部）
2. 输出在原理的右边（或底部）
3. 门电路流应从左到右或者从上到下
4. 尽量使用直线连接
5. T型接头表示两条线有连接
6. 两条线交叉的地方有一个点，表示有连接
7. 两条线交叉的地方没有点，表示没有连接

并且还要尽可能的使用更少的门以降低成本，例如下图中右侧的德摩根表示电路就要好于左边，因为右边的门更少：

多输出电路

多输出电路顾名思义就是有多个输出出口的电路，一般他也会对应着多个输入入口，但是每次只有一个输出出口的信号有效，比如我们这里介绍一下优先级电路。优先级电路，是一种特殊的电路，他在所有输入为真的信号中，选择其中最重要的信号所对应的输出为1，其余输出为0。如下图：

这里的Ai中i越大表示优先级越高，所以当A3为0时，那么Y3就输出0了，，A2A1A0无论是多少都为0。这就是一个多输出的优先级电路。那么我们是如何实现的呢？实际上我们只需要三个门就可以实现如下图：

我们发现为了减少门的使用，实际上使用了更加复杂的三输入甚至四输入门，并且还有不同的取非功能。

多级组合逻辑

所以我们可以知道在多级组合逻辑电路中我们要遵循的规则：

规则1：减少硬件

所有的逻辑表达式都可以转化为与或式，理论上与或式可以使用两级门电路来实现即先与后或，但是二级逻辑可能会带来更高的成本，所以使用多输入门又称为扇入门。但是门电路的扇入数不可能无限制的增加（受工艺、成本等方面的制约）。

这里我们以三输入异或门的实现为例：

我们发现三输入异或门可以用来顶替右侧的复杂的组合逻辑电路，这无疑是更加高效的，但是三输入异或门同样造价高昂，且实现起来很复杂，更不要说五输入异或门等了。所以有时候我们需要在门数和们元件的选择上作一个这种考虑如下：

实际上我们也可以使用两个造价更便宜的异或门来顶替三输入异或门。所以减少硬件的目的并不是盲目追求组合逻辑电路的门数量减少，而是尽可能的使用更加直观简单的电路形式来表示逻辑表达式。

规则2：推气泡

实际上我们发现对于一个标准与或式或者标准或与式的逻辑表达式总是会使用与非门和或非门，即器件上有许多小圆圈符号表示取非，但是我们在绘制组合逻辑电路时如果照搬表达式会有许多取非的过程（同时一般商家也不会卖最后输出端取非的门元件），这很不直观同时也不符合实际情况，但是又难以直接化简逻辑表达式。所以我们可以在照搬逻辑表达式绘制出组合逻辑电路后使用推气泡的方法来简化电路。首先我们介绍一下推气泡的规则：

那么现在我们就可以优化电路了，如下图：

此时我们推完气泡以后发现有4个气泡，实际上是取非输出后又取非了，那么就相当于双重取反等于没去反，所以可以将这四个气泡都消掉。所以我们给出一个规则：

1. 推气泡要从输出端向输入端推
2. 将气泡从电路最后的输出端开始推
3. 如果当前门有一个输入气泡且上一级输出门无气泡，则消除这个门的输入气泡，然后在上一级门的输出加上气泡
4. 如果当前门有一个输入气泡且上一级输出门也有气泡，那么就同时消除两端的气泡

最终我们就会得到一个所有取非都在输入端的门电路，这个才是一个逻辑清晰同时符合实际的电路，如下图：

我们推完气泡以后得到了如下电路（逻辑功能完全相同）:

（画的丑，见谅，但是注意门也改变了）。具体的推气泡过程如下：

非法值（illegal):X

我们其实前面已经讲过了讲个输出电路不能直接相交汇，即节点不能同时连接两个输出，否则会出新冲突，实际上就是节点同时被0和1驱动，0是对应着电压0,1是对应着VDD，那么如果冲突了电压值就会介于0~VDD，那么这个信号可能是0也可能是1，也可能处于禁止区域内（前面将多有一个禁区表示既不是0也不是1，不懂了请看第1讲）。这时我们就成为交汇后的信号值为非法值X，一般出现这种竞争情况都是电路设计缺陷引起的，我们要避免此种情况，因为他会导致电路功耗变大，电路发热，并导致电路损坏。

无关项（Don’t Care):X

无关项一般会出现在优先级电路中，例如之前讲过的优先级电路：

那么很显然如果输入信号A3位输入，那么就不需要考虑其他输入量，此时对于不需要考虑的输入信号量就是用X来表示。

浮空值（floating):Z

浮空值称为悬空、高阻态、高Z态、开路、断路等，即次数电路断开的意思。首先我们要注意，浮空值Z就是指电路断开了，此时信号会介于0~VDD之间，具体是多少不知道，所以使用电压表并不能判断哪个电路节点处于浮空状态（可能这个信号就是0，也可能这个信号是浮空Z并且恰好Z是0），且测量断路节点的电压和接地点的电压，在电压表上的读数都为0。所以浮空值输出不确定，产生浮空节点常见的原因是忘记将电压连接到输入端。

三态缓冲器（tristate buffer)

三态缓冲器就是使用了浮空，他可以用来防止节点处于竞争状态，具体实现如下：

当一个节点同时连接了n个输出时，若其中n-1个输出处于浮空状态（即断开状态），那么当前的节点值就等于驱动正常电平输出端的值。所以使用三态缓冲器就可以允许节点连接多个输出端了，这无疑优化了电路。例如上面的三态缓冲器，有三种输出状态：高电平VDD表示1信号，低电平0表示0信号以及浮空状态表示线路断开。

例如此时A是输入端，Y是输出端，使能端E是控制何时断开的，那么此时当使能端为0时，输出端浮空，表示A->Y的线路断开，那么这个输出信号Y暂时不等于A了，而是浮空值Z了，所以Y就暂时不参与下一级门的逻辑运算了，当E=1时，那么线路连接，Y=A的信号值，所以就可以看成一个导线了，那么Y就会以A信号值参与下一个门的逻辑运算。

三态缓冲器的应用

那么很明显在连接多个芯片的总线时，会用到三态缓冲器，许多不同的设备同时连接到同一总线上，但是某一时刻只允许一个芯片的信号有效，并向总线输出数据，其他芯片的输出必须浮空，以防止总线竞争，任何芯片在任何时刻都可以通过总线读取信息：

to bus表示的就是从设备向总线输出数据的信号，每一次只有一个设备的三态缓冲器使能端为1表示每一次总线只会接受一个设备的信号。但是from bus表示的是设备从总线获取的信号，那么如果这个设备需要，就可以让from bus线上的三态缓冲器使能端为1接受来自总线的信号，并且同一时刻可以有多个设备都接受总线的信号，但是他们接受的信号是相同的。

使用卡诺图化简布尔表达式

我们回忆一下之前我们学习的补1法将布尔表达式转化成标准与或式，他可以使得式子更加符合电路逻辑，便于我们绘制组合逻辑电路，但是对于人类思维却不友好，因此如果我们现在知道标准与或式，我们希望可以将它化简成比较简洁清晰的形式，即变量尽可能的少，此时我们就可以使用卡诺图进行化简。

卡诺图的思想很简单，他就是通过合并项来化简布尔表达式。那么我们该合并哪些项呢？就是相邻最小项，比如PA和P非A，他们相加合并就可以变成P。卡诺图化简法是将逻辑表达式用一种称为“卡诺图”的图形来表示，然后在卡诺图上进行函数化简。下图就是几个卡诺图化简时的中间过程：

我们首先来介绍一下卡诺图的构成：

卡卡诺图是一种包含一些小方块的几何图形，图中的每一个小方块称为一个单元，每个单元对应一个最小项（注意一定要是最小项）。两个相邻的最小项在卡诺图中也必须是相邻的，卡诺图中相邻的含义：

1. 几何相邻性，即几何位置上相邻，也就是左右上下紧挨
2. 对称相邻，即图形中对称位置的单元是相邻的

思考：为什么卡诺图使用的是最小项，而不是最大项？

实际上很好解释，我们知道卡诺图的核心就是合并，那么合并肯定是相加，而与或式就是相加的，他的每一个元素就是最小项，所以使用最小项，而最大项之间的运算是相交，很明显不符合卡诺图的需求。

思考：能否更加详细的解释卡诺图中的相邻？

如下图：

$$\begin{cases} \bar{A}\bar{B}\bar{C}和\bar{A}\bar{B}C是左右相邻\\ \bar{A}\bar{B}\bar{C}和A\bar{B}\bar{C}是上下相邻\\ \bar{A}\bar{B}\bar{C}和\bar{A}B\bar{C}是对称相邻 \end{cases}$$

并且要注意这里的相邻方块内的最小项也是相邻的。即任何两组相邻，只有一位变量取值不同，即符符号循环码排列规则。

思考：卡诺图还有哪些特点

除了方块相邻，我们还要注意对于n为元素，那么就会有2^n个卡诺方块，即2^n个最小项，并且卡诺图的横纵栏排列也是有讲究的，比如上图中的BC一行的值每一次都是只有一个位发生变化：00->01->11->10，所以BC的排列不能是00->01->10->11因为第2个位置和第3个位置两位都不同。并且卡诺图的编号就是按字典序的元素取值拼接出的二进制数，比如上图中的A(0)BC(00)就是二进制的000，所以m编号为0，在比如A(1)BC(01)就是二进制的101，所以m编号是5。

那么接下来我们来举例几个卡诺图熟悉一下卡诺图的特点，首先我们来观察一下二变量和四变量卡诺图：

那么接下来我们看一个较为复杂的五变量卡诺图，他一共会有32个方格，一种编号如下：

一定要注意CDE和AB的排列编号要保证相邻的只有一位取值不同。

使用卡诺图表示逻辑函数

上面我们主要是讲解了卡诺图的构成和对卡诺方块的编号，那么接下来我们来学习以下每一个方格填的值来表示给出的需要化简的布尔表达式，实际上就是布尔表达式中出现的最小项对应的方格填1，其他地方默认填写0。如：

$$F(A,B,C)=\bar{A}BC+A\bar{B}C+ABC$$

那么我们的卡诺图应该如下图：

3,5,7处对应的最小项就是布尔表达式中出现的，所以这几个地方填0。那么接下来我们来介绍一下卡诺图上合并最小项的规则，即化简的规则：

1. 当卡诺图中有最小项相邻时（即：有标1的方格相邻），可以利用最小项相邻的性质，对最小项进行合并。
2. 卡诺图上任何两个相邻的两个标1的方格，可以合并为1项，并可消去1个（取值取反的）变量。
3. 卡诺图上四个标1方格合并，可合并为一项，并可以消去2个变量
4. 四个标1方格的特点是四个方格同在一行或一列，或者同在一个田字格

根据上面的规则，我们可以将卡诺图中的5,7合并，3,7合并：

5,7左右相邻，且标号均为1同时观察菜单栏发现B的标号不同，所以可以消去变量B，同时3,7号合并，变量A取值不同，所以可以消去A，这样我们就得到了F的化简表达式了。

但是规则还没有结束，这只是对应着一种相邻的情况，我们知道还有对称的情况，所以下面的卡诺图也可以进行合并：

0000和0010由于对称相邻，所以可以合并，C取值不同所以合并后消去C，1101和1111左右相邻，可以合并，C不同，所以消去C，所以我们根据上面的卡诺图可以得知这个布尔表达式的原先表达和化简后的表达应为：

$$F=\bar{A}\bar{B}\bar{C}\bar{D}+\bar{A}\bar{B}C\bar{D}+AB\bar{C}D+ABCD$$

$$F=\bar{A}\bar{B}\bar{D}+AB\bar{D}$$

所以我们发现补1法是将布尔表达式转换成标准与或式，而卡诺图化简就是逆过程，是将复杂的标准与或式化简成简单的形式。那么接下来我们再来尝试相除4个格的，如下：

同样的，四个格同在一行，或者同在一列或者同在一个田字格也可以进行合并消除化简。并且此时是2^2个相邻格，所以可以一次消除两个变量，我们横看可以消除一个变量，纵看又可以消除一个方格。

思考：如果我就要按照两个两个的消除可不可以？

可能你会产生疑惑，为什么要按照4个格相邻进行消除，而不是继续看成许许多多个2个格相邻进行消除，我们知道最终要得到的式子尽可能的最简，对比上面两个图我们发现右边的式子最终并不是最简式，因此为了得到最简式，我们必须用尽可能最大的圈去包裹1矩阵。

那么接下来我们练习一下四个格相邻的消除，同时你也可以自己尝试按照2个格消除，最终对比一下化简得到的布尔表达式是否一样。

那么既然可以合并4个，当然也就可以合并8个啦，那么合并8个格的规则是8个格子相邻组成一个8元素矩阵或者有对称的行和列也可以：

最终我们会消除3个变量。如上图图1最终只剩下了一个非A，图2只剩下了非B。

思考：那么可不可以16个格进行合并消除，甚至更多？

当然可以，我们枚举了这几种情况可以总结出如下规律：

在n变量的卡诺图中，会有2^n个方格，只有2的i次方个相邻的标1方格（必须排列成方形格或者矩阵形格的形状）才能圈在一起，合并为一项（当然，有对称的也可以）。该项保留了n-i个相同的变量，也就是说明会消除i个不同的变量。