组合逻辑设计

引言

可以先参考我写的这篇：戳这

数字逻辑电路（logic circuit）是一个可以处理离散值变量的网络。

其中包括：

• 一个或多个离散值输入端（输入的是离散值）
• 一个或多个离散值输出端（输出的是离散值）
• 描述输入和输出关系的功能规范
• 描述当输入改变时输出响应延迟的时序规范

3种逻辑运算：
与：$A\cdot B$ 或 $AB$.
或：$A+B$.
非：$\overline{A}$.

基本概念

变量：可以用大小写英文字母表示，取值只能是0或1.

反变量：即变量的非.

项：变量或它的反变量.

布尔表达式适用于描述组合逻辑电路中输入与输出间的功能规范。

结点和模块

电路由结点和模块组成。

结点是一段导线，通过电压传递离散值变量。

• 输入结点：接收外部的值（如A，B，C）
• 输出结点：输出值到外部（如Y，Z）
• 内部结点：不属于以上两者的结点（如n1）

模块本身是一个带有输入、输出、功能规范和时序规范的电路。

• 每一个模块本身都是一个电路
• 图中的E1，E2，E3

数字逻辑电路的分类

组合逻辑电路（combinational logic）

• 任一时刻的输出仅由该时刻的输入信号决定
• 无记忆的，与电路状态无关

时序逻辑电路（sequential logic）

• 任一时刻的输出由该时刻的输入和电路在该时刻的状态共同决定
• 有记忆的，与电路状态有关

即：输入 $\rightarrow$ 功能规范/时序规范 $\rightarrow$ 输出。

例如计算器就是一个典型的时序逻辑电路。输入为1+1=时，得到输出为2，但是按=得到的输出并不总是为2，而是要看当前的状态。

组合逻辑电路

特点：

• 每个电路模块都是一个组合逻辑电路。
• 每个电路结点：
  • 要么是电路是输入
  • 要么只连接电路模块的一个输出端（并不在意结点连接到多少个输入上，但是只能连接到一个输出）
• 电路中不包含回路

通常用CL符号表示组合逻辑。

思考题：

图2存在回路，图4的n4结点有2个输入，图6存在回路。

布尔代数

3种逻辑运算：

• 与：$A\cdot B或AB$
• 或：$A+B$
• 非：$\overline{A}$

基本概念

变量：可以用大小写英文字母表示，取值只能是0或1.

反变量（complement）：即变量的非.

项（literal）：变量或它的反变量.

布尔表达式适用于描述组合逻辑电路中输入与输出间的功能规范。（因为组合逻辑电路的输出只与输入有关）

对偶（duality）：

设F为任意逻辑表达式，若将F中所有运算符和常量作如下变换：

$$. \rightarrow +$$ $$+ \rightarrow .$$ $$0 \rightarrow 1$$ $$1 \rightarrow 0$$

则变换后得到的是F的对偶式F‘。

对偶是相互的，F和F’互为对偶式。

对偶规则：两个逻辑表达式F和G相等，则对偶式F’和G’也相等。例如：

$$A(B+C)=AB+AC \rightarrow A+BC=(A+B)(A+C)$$

蕴含项（implicant）：项的乘积

如 $AB\overline{C}$, $AC$

最小项（miniterm）：包含全部输入变量的乘积项

如 AB\overline{C}$, $ABC$

最大项（maxterm）：包含全部输入变量的求和项

如 $A+B+C$, $A+\overline{B}+C$

最小项

n个变量逻辑函数的每个最小项，一定是包含n个因子的乘积项，有 $2^n$ 个最小项。

最小项的编号

最小项用 $m_i$ 表示。m表示最小项，下标 i 为使该最小项为1的变量取值所对应的等效十进制数。

最小项 $\overline{A}BC$
要使该最小项为1，A、B、C的取值应为0、1、1.
二进制数011所等效的十进制数为3，所以 $\overline{A}BC=m_3$.

最小项的性质

1. 变量任取一组值，仅有一个最小项为1，其余为0.

2. n变量的全体最小项之和恒为1.

3. n个变量任意两个不同的最小项相与，结果恒为1.

4. 相邻最小项相或，可以合并为一项，并可以消除一个变量：

   相邻：两最小项仅有一个变量因子不同，其他变量均相同

   例如：$ABC+AB\overline{C}=AB$.

   任一n变量的最小项，必定和其他n个不同最小项相邻（每一个变量取反都是相邻项）

最大项

最大项的编号

最大项用 $M_i$ 表示。M表示最大项，下标 i 为使该最大项为0的变量取值所对应的等效十进制数。

最大项 $\overline{A}+B+C$
要使该最小项为0，A、B、C的取值应为1、0、0.
二进制数100所等效的十进制数为4，所以 $\overline{A}+B+C=M_4$.

最大项的性质

1. 变量任取一组值，仅有一个最大项为0，其余为1.

2. n变量的全体最大项之积恒为0.

3. n个变量任意两个不同的最大项相或，结果恒为1.

4. 相邻最大项相与，可以合并为一项，并可以消除一个变量：

   例如：$(A+B+C)(A+B+\overline{C})=A+B$.

相同编号的最小项和最大项互为反函数。

标准与或式和标准或与式

标准与或式（sum-of-products）

由最小项之和构成的逻辑表达式。

例如：

$$F(A,B,C)=\overline{A}B\overline{C}+A\overline{B}\overline{C}+AB\overline{C}=\Sigma(m_2,m_4,m_6)=\Sigma(2,4,6)$$

每个最小项都对应真值表中值为1的一行。

A	B	C	F(A, B, C)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

标准与或式是最小项之间的或运算，与真值表间一一对应。

可以有多个逻辑表达式对应相同的真值表，但是只有一个标准与或式与该真值表对应。

标准与或式具有唯一性。

任一逻辑函数都可以表达为最小项之和的形式，而且是唯一的。

例如：（通常把缺的那一项配上）

$$F(A,B,C)=AB+\overline{A}C=AB(C+\overline{C})+\overline{A}C(B+\overline{B})=ABC+AB\overline{C}+\overline{A}BC+\overline{A}\overline{B}C=\Sigma(1,3,6,7)$$

标准或与式（product-of-sum）

最大项之积构成的逻辑表达式。

例如：

$$F(A,B,C)=(A+B+C)(A+\overline{B}+C)(\overline{A}+B+C)=\prod(M_0,M_2,M_4)=\prod(0,2,4)$$

任何一个逻辑函数也可以写成最大项之积的形式，并且是唯一的。

标准与或式和标准或与式的关系

$$F(A,B,C)=\Sigma(2,4,6)$$ $$\overline{F}(A,B,C)=\Sigma(0,1,3,5,7)$$ $$F=\overline{\overline{F}}=\overline{m_0+m_1+m_3+m_5+m_7}=\overline{m_0}\cdot\overline{m_1}\cdot\overline{m_3}\cdot\overline{m_5}\cdot\overline{m_7}=M_0M_1M_3M_5M_7$$

于是有

$$F=\sum_i m_i=\prod_{j\neq i}M_j$$

推导：

$$F=\sum_i m_i=\overline{\sum_{j\neq i} m_j}=\prod_{j\neq i}\overline{m_j}=\prod_{j\neq i}M_j$$

布尔表达式与真值表的转换

1. 代入法

2. 将表达式转化为标准与或式

3. 直接填表：

   对 $F(A,B,C)=AB+BC$，表示的逻辑含义为：

   1. AB=1时，F=1.

   2. BC=1时，F=1.

   3. 否则F=0.

   于是只有(0,1,1), (1,1,0), (1,1,1)满足条件。

使用定理化简表达式

使与或式中的与项最少，与项中出现的变量最少。

$$例如，A(A+B)=A$$

从逻辑到门

X和Z

非法值

竞争（contention）：电路结点同时被0和1驱动

• 电压值可能介于 $0~V_{DD}$ 之间
• 可能是0，可能是1，也可能处于禁止区域内
• 导致电路的功耗变大、电路发热，并导致损坏

竞争通常是由于电路设计缺陷引起的。

无关项

浮空值

浮空（floating）也称悬空、高阻态（high impedance）、高Z态、开路、断路

浮空不等于逻辑0.

• 使用电压表并不能判断哪个电路结点处于浮空状态
• 测量断路结点的电压（断路）和接地点的电压（短路），在电压表上的读数都是0

当电路的输入结点浮空时，输出不确定。

• 可能为0，可能为1，也可能为某个中间电压（处于禁止区）

产生浮空结点常见的原因是忘记将电压连接到输入端，但浮空结点并不意味着电路一定出错。

浮空表示的是断路。

三态缓冲器

浮空可以用来防止结点处于竞争状态。

三态缓冲器有3种可能输出状态，分别为高电平、低电平和浮空。

上图中输入端是A，输出端是Y，使能端是E。使能端也作为输入，所以是2个输入1个输出。

当E为1时，Y由A决定；当E为0时，Y恒为高阻态，说明此时是断路的。即三态门的使能端无效时输出为高阻态。

卡诺图

卡诺图化简法是将逻辑函数用一种称为“卡诺图”的图形来表示，然后在卡诺图上进行化简的方法。

卡诺图采用相邻两个最小项能够合并，并消掉一个变量的原理进行变量化简。

卡诺图中每个小方格对应一个最小项。

相邻最小项可以是位置相邻

相邻最小项可以是对称相邻

相邻的两个最小项在卡诺图中也是相邻的。卡诺图中相邻的含义：

1. 几何相邻性，即几何位置上相邻，也就是左右紧挨着或者上下相接。
2. 对称相邻性，即图形中位于边缘的单元与对称位置的单元是相邻的。

卡诺图是真值表的一种变形。

卡诺图上合并最小项的规则
规则1：当卡诺图中有最小项相邻时（即有标1的方格相邻），可利用最小项相邻的性质，对最小项合并。（卡诺图中相邻的两个小项合并时，消掉的是取值不同的变量。）
规则2：卡诺图上4个标1方格相邻，可合并为一项，并可消去2个变量。

4个标1方格相邻的特点：同在一行或一列；同在一个田字格中。

规则3：卡诺图上8个标1方格相邻，可以合并为1项，并可消去3个变量.

合并规则总结：在n个变量的卡诺图中，只有2的i次方个相邻的标1方格（必须排列成方形格）才能合并为1项，并且消去i个变量。

减少硬件

所有的逻辑表达式都可以转化为与或式。

理论上，与或式可以用两级门电路实现，但是成本太高。采用多级逻辑可以减少门电路的数量和扇入数。

扇入（fan-in）：单个逻辑门能够接受的数字信号最大输入数。

可以将一个三输入与或门转化成两个二输入与或门：

$$Y=A\oplus B\oplus C=(A\oplus B)\oplus C$$

将二级门电路转成多级门电路来实现时，输出信号的延迟会增大。

与非和或非运算都是完备的，利用与非门和或非门可以实现任何表达式。

（由于德摩根定律）

推气泡：将与非门和或非门转换成与/或门电路用于读取BOOL表达式；将与/非门的电路转换为与/或非门电路用于CMOS实现。

组合逻辑电路设计方法

七段数码管驱动电路：4位输入数据，输入一个十进制数字（4位二进制数可表示一位十进制数）；7位输出控制发光管显示数字0-9.

七段数码管（由7个发光二极管构成）的连接方式有共阴极和共阳极两种方式。共阴极连接时，对应字段高电平时被点亮；共阳极连接时，对应字段低电平时被点亮。

组合逻辑模块

编码器

用n位二进制代码对$N=2^n$个特定信息进行编码的逻辑电路。

例如，设计一个具有4路信号输入的优先级编码器：

输入：X0, X1, X2, X3

输出：A0, A1, EO(EO用于判定是否存在有效输入)

功能：将4个输入信号进行二进制编码（4线-2线编码器）

优先级编码：当有多个信号同时输入时，只对优先权高的一个信号进行编码。

输出使能端：用于判别电路是否有信号输入。用EO表示，EO=0表示有信号输入，EO=1表示无信号输入。

输入	A0	A1	EO
无有效信号	0	0	1
X0有效，X1, X2, X3无效	0	0	0
X1有效，X2, X3无效	0	1	0
X2有效，X3无效	1	0	0
X3有效	1	1	0

因此X0, X1, X2, X3编码分别为：00，01，10，11

于是可以画出真值表。在真值表中，X0先出现(X3=0, X2=0, X1=0, X0=1)就对应A0=0，A1=0，EO=0；X1先出现(X3=0, X2=0, X1=1, X0=0或X3=0, X2=0, X1=1, X0=1)就对应A0=0，A1=1，EO=0…

然后就可以使用X简化真值表：

X3	X2	X1	X0	A1	A0	EO
0	0	0	0	0	0	1
0	0	0	1	0	0	0
0	0	1	X	0	1	0
0	1	X	X	1	0	0
1	X	X	X	1	1	0

由真值表画出X0X1X2X3的卡诺图，即可写出A0、A1、EO的表达式。

译码器

译码时编码的逆过程，有n个输入，$2^n$个输出。

每一种输入的组合对应使能端某个特定时刻的输出信号。

输出使独热（互斥）的，同一时刻只能输出一个有效信号，即每一组输入只能使一条输出线产生有效输出电平。

如果是高电平有效，EO的值在输入信号无效时为1.（于是当EO为0时，输出为高电平）

译码器的每一个输出都对应输入信号的一个最小项。

译码器可以把地址信息当做输入信号，把有效输出信号当成选择信号，来选中特定的设备来工作。

同一时刻只能允许总线上的一个外部设备向处理器发送信息，所以在同一时刻只能允许一个三态缓冲器的使能端输出有效信号。这时就要用到译码器。因为译码器输出的信号就是互斥的。

译码器的每一个输出信号连接到一个外部设备的三态缓冲器上。于是，同一时刻只需发送一个特定的信号，就能确定用哪一个三态缓冲器了。

每个外部设备都有一个地址来唯一标识。计算机想与哪一个外部设备进行数据交换，首先就要知道这个设备的地址，控制这个设备。

但是只知道信号和地址，无法确定数据的流向。因为总线上的数据是双向传递的。

读写控制依赖于输入输出信号（0或1，通过与门或与非门后到达三态缓冲器使能端，由此决定数据传输方向）。高电平时表示设备向处理器发送数据，低电平时表示处理器将数据输送到设备。

数据、地址、控制——三总线。

通过译码器+或门可以构造出更加复杂的表达式。

多路选择器（MUX）

根据选择信号的值从N个可能的输入中选择一个作为输出。

需要使用logN位选择信号（也称地址信号）作为输入，控制输入信号的选择。

3-8译码器对低电平有效，输出值中只有一个是0.

74LS138 3-8译码器

组合逻辑电路的传播延迟是关键路径上每一个元件的传播延迟之和。

传播延迟一般大于最小延迟。

最小延迟是从输入发生变化直到任何一个输出开始改变的最短时间。

传播延迟是从输入改变直到一个或多个输出改变为最终值所经历的最长时间延迟。

由0到1是一个给电容充电的过程，由1到0是一个给电容放电的过程。

产生延迟的原因：

• 电路中的电阻和电容的充放电
• 光速的上限

上升沿和下降沿的延迟可能不同

不同输出的延迟可能不同

电路对温度敏感，电路较热时速度会变慢

组合逻辑电路中，最小延迟是最短路径上每个元件的最小延迟之和。

毛刺的产生是由于电路中，变化的信号从出发点到汇合点所经历的两个路径长度不同所造成的。

毛刺只能在传播延迟的时间范围之内发生，否则传播延迟计算错误。