Chapter2 组合逻辑设计

Introduction

数字逻辑电路

  • 数字逻辑电路(logic circuit)是一个可以处理离散值变量的网络;
  • 其中包括:
    • 一个或多个离散值输入端
    • 一个或多个离散值输出端
    • 描述输入和输出关系的功能规范
    • 描述当输入改变时输出响应延迟的时序规范

功能规范与时序规范

结点(node)和模块(element)

  • 电路由节点和模块组成;
  • 结点是一段导线,通过电压传递离散值变量;
    • 输入结点:接收外部的值(图中的A,B,C);
    • 输出结点:输出值到外部(图中的Y,Z);
    • 内部结点:不属于以上两者的结点(图中的n1)。
  • 模块本身是一个带有输入、输出、功能规范和时序规范的电路;
    • 每一个模块本身都是一个电路;
    • 图中的E1,E2,E3。

结点和模块

数字逻辑电路的分类

  • 组合逻辑电路(combinational logic)
    • 任一时刻的输出仅由该时刻的输入信号决定;
    • 无记忆的,与电路状态无关。
  • 时序逻辑电路(sequential logic)
    • 任一时刻的输出由该时刻的输入和电路该时刻的状态共同决定;
    • 有记忆的,与电路状态有关。

数字逻辑电路的分类

组合逻辑电路

  • 每个电路模块都是一个组合逻辑电路;
  • 每个电路结点:
    • 或者是电路的输入;
    • 或者是只连接电路模块的一个输出端。
  • 电路中不包含回路。

组合逻辑电路

判断下列哪写电路是组合逻辑电路

判断

  1. √;
  2. ×,有回路;
  3. √;
  4. ×,连接了两个模块的输出端;
  5. √;
  6. ×,有回路。

布尔代数

基本概念

布尔代数的定义

  • 布尔代数中的变量取值只能为**“真”(True)“假”(False)**;
  • “1”表示真,“0”表示假;
  • 三种基本逻辑运算:
    • “与”,运算符“·”,例:A·B或AB;
    • “或”,运算符“+”,例:A+B;
    • “非”,运算符“上划线”,例:A

基本概念

  • 变量:可以使用A、B、C…或a、b、c…来表示,取值只能为0或1;

  • 反变量(变量的非,Complement):变量上面有一条横线

    ABC

  • 项(Literal):变量或它的反变量

    A,A,B,B,C,C

布尔表达式

  • 适用于描述组合逻辑电路中输入与输出间的功能规范
  • 例如:
    • S=F(A,B,Cin);
    • Cout=F(A,B,Cin)。

布尔表达式

公理和定理

布尔代数的公理

布尔代数的公理

对偶规则

  • 对偶(Duality)

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

      Change

    • 例如:F=AB+CD→F‘=(A+B)(C+D)

    • 则所得新的表达式F’为F的对偶式。

  • 对偶是相互的,F和F’互为对偶式;

  • 对偶规则:两个逻辑表达式F和G相等,则对偶式F’和G’也相等。

对偶规则

单变量定理

单变量定理

单变量定理

单变量定理

多变量定理

多变量定理

德·摩根定律

德·摩根定律

最小项和最大项

基本概念

  • 蕴含项(Implicant):项的乘积

    ABCAC,BC;

  • 最小项(Miniterm):包含全部输入变量的乘积项

    ABC,ABC,ABC;

  • 最大项(Maxterm):包含全部输入变量的求和项(Sum)

    (A+B+C),(A+B+C),(A+B+C)。

最小项

  • 最小项是一种特殊的乘积项("与"项);
  • 最小项特点:
    • n个变量逻辑函数的每个最小项,一定是包含n个因子的乘积项;
    • 在各个最小项中,每个变量必须以原来变量或反变量形式作为因子出现一次,而且仅出现一次;

最小项

最小项的编号

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

最小项实例

三变量最小项编号表

三变量最小项编号表

三变量最小项真值表

三变量最小项真值表

从表中可以看出,每个最小项只有一组变量取值能使其值为1,而其他各组取值该最小项皆为0。由这种“与”函数真值表中1的个数最少,而得名“最小项”。

最小项的性质

  • 变量任取一组值,仅有一个最小项为1,其他最小项为0;

  • n变量的全体最小项(共有2n个)之和恒为1;

  • n个变量任意两个不同的最小项相与,结果恒为0;

  • 两最小项相邻,相邻最小项相"或",可以合并成一项,并可以消去一个变量因子

    • 相邻:两最小项如果仅有一个变量因子不同,其他变量均相同,则称这两个最小项相邻

      例:ABC+ABC=AB;

    • 任一n变量的最小项,必定和其他n个不同最小项相邻(每一变量取反都是相邻项)

      例:ABC与ABC、ABC、ABC相邻。

最大项

  • 最大项是一种特殊的和项("或"项);
  • 最大项特点
    • n个变量构成的每个最大项,一定是包含n个因子的"或"项;
    • 在各个最大项中,每个变量必须以原变量或反变量形式作为因子出现一次,而且仅出现一次。

最大项

最大项编号

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

最大项编号

三变量最大项编号表

三变量最大项编号表

三变量最大项真值表

三变量最大项真值表

每个最大项只有对应的一组变量取值能使其值为0,正因为这种“或”函数真值表中1的个数最多,所以取名“最大项”。

最大项的性质

  • 变量任取一组值,仅有一个最大项为0,其他最大项为1;

  • n变量的全体最大项之积为0;

  • 不同的最大项相或,结果为1;

  • 两相邻的最大项相“与”,可以合并成一项(等于相同因子之和),并可消去一个变量因子

    • 相邻:两最大项如果仅有一个变量因子不同,其他变量均相同,则称这两个最大项相邻;

      Example&Proof

    • 任一n变量的最大项,必定和其他n个不同的最大项相邻。

最小项和最大项的关系

  • 编号下标相同的最小项和最大项互为反函数
  • Example
  • Example

标准与或式和标准或与式

标准或与式(sum-of-products)

  • 由最小项之和构成的逻辑表达式;
  • Example
  • 每个最小项都对应真值表中值为1的一行;
  • 标准与或式是最小项之间的或运算;
  • 标准与或式与真值表间一一对应;
  • 因此,从标准与或式中可以直接判断哪些变量取值可以使表达式为1。

标准与或式具有唯一性

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

标准与或式具有唯一性

标准或与式(product-of-sums)

  • 最大项之积构成的逻辑表达式;
  • Example
  • 任一逻辑函数都可以表达为最大项之积的形式、而且是唯一的。

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

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

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

布尔表达式→真值表

  • 三种方法
  1. 将变量的组合所有取值组合一一带入表达式进行计算得到;

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

    方法2

  3. 根据函数式的逻辑含义直接填表

    方法3

    方法三所得到的真值表

    方法3真值表

  • 通过上述方法所得到的真值表

真值表

真值表→布尔表达式

  • 根据最小项的性质,直接从真值表写出标准与或式

    通过真值表写标准与或式

  • 根据最大项的性质,直接写出标准或与式

    写出标准或与式

例子

条件

解

使用定理化简表达式

  • 例1

1

  • 例2

2

从逻辑到门

由布尔表达式绘制原理图

  • 与或式可以使用两级门电路来实现

    • 第一级:与门;
    • 第二级:或门。
  • 例

图

电路原理图绘制原则

  • 原理图需要遵循一致的风格,以易于阅读和检查错误;
  • 绘制原则如下:
    • 输入在原理图的左边(或顶部);
    • 输出在原理图的右边(或底部);
    • 门电路流应从左至右(或从上至下);
    • 尽量使用直线连接;
    • T型接头表示两条线有连接;
    • 两条线交叉的地方有一个点,表示有连接;
    • 两条线交叉的地方没有点,表示没有连接。

原则

实例

例

多输出电路

  • 构造一个“优先级电路”
    • 在所有输入为真的信号中,选择其中最重要的信号所对应的输出为1;
    • 其余输出为0。

实例

例

例

优先级电路的实现

以上多输出电路实例为例

优先级电路的实现

多级组合逻辑

减少硬件

减少硬件的目的

扇入(fan-in):单个逻辑门能够接受的数字信号的最大输入数。

fan-in

  • 所有的逻辑表达式都可以转化为与或式;
  • 理论上,与或式可以使用两级门电路来实现(先与后或);
  • 使用二级逻辑可能带来更高的成本;
  • 在工程上,门电路的扇入数不可能无限制的增加
    • 受工艺、成本等方面的制约。
  • 采用多级逻辑
    • 可以减少门电路的数量;
    • 可以减少扇入数。

3输入异或门的实现

3输入异或门的实现

使用更少的门电路

使用更少的门电路

推气泡

推气泡

  • CMOS电路中经尝使用与非门和或非门;
  • 不易直接根据电路推导出表达式;
  • 推气泡可以帮助我们重画电路,更容易确定逻辑功能;
  • 向后推
    • 电路符号变化;
    • 将气泡加在输入端;
    • 向后推
  • 向前推
    • 电路符号变化;
    • 将气泡加在输出端;
    • 向前推

写出电路的逻辑表达式

写出电路的逻辑表达式

Y=AB+CD

推气泡的方法

  • 从输出端向输入端推;
  • 将气泡从电路最后的输出端开始推;
  • 如果当前门有一个输入气泡、则消除该气泡,并在其上一级门的输出加上气泡。

推气泡的方法

推气泡的例子

推气泡的例子

X和Z

非法值(illegal):X

  • 竞争(Contention):电路结点同时被0和1驱动
    • 电压值可能介于0~VDD之间;
    • 可能是0,可能是1,也可能处于禁止区域内;
    • 导致电路的功耗变大,电路发热,并导致损坏。
  • 注意:竞争通常是由于电路设计缺陷引起的。

竞争

无关项(Don’t Care):X

  • 在优先级电路中:
    • 如果A3输入为TRUE,则输出不用考虑其他的输入量。
  • 用符号X表示不需要考虑的输入。

无关项

浮空值(floating):Z

  • 浮空也称为悬空、高阻态(High impedance)、高Z态、开路、断路;
  • 浮空不等于逻辑0
    • 使用电压并不能判断哪个电路结点处于浮空状态;
    • 测量断路节点的电压和接地点的电压,在电压表上读数都为0。
  • 当电路的输入结点浮空时,输出不确定
    • 可能为0,可能为1,也可能为某个中间电压(处于禁止区)。
  • 产生浮空结点常见的原因是忘记将电压连接到输入端;
  • 但浮空结点并不意味着电路一定出错。

三态缓冲器(tristate buffer)

  • 浮空可以用来防止结点处于竞争状态;
  • 当一个结点同时连接n个输出时,若其中n-1个输出处于浮空状态,则当前结点的值等于驱动正常电平输出端的值;
  • 三态缓冲器
    • 有三种可能输出状态;
    • 高电平、低电平和浮空;
    • 输入端A,输出端Y,使能端E。

三态缓冲器

三态缓冲器的应用

在连接多个芯片的总线上使用

  • 许多不同的设备同时连接在一总线上;
  • 在某一个时刻只允许一个芯片的使能信号有效,并向总线输出数据;
  • 其他芯片的输出必须浮空,以防止总线竞争;
  • 任何芯片在任何时刻都可以通过总线读取信息。

三态缓冲器的应用

卡诺图

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

卡诺图的构成

三变量卡诺图

二变量、四变量卡诺图

五变量卡诺图

用卡诺图表示逻辑函数

卡诺图上合并最小项的规则

实例

合并规则总结

用卡诺图化简逻辑函数

组合逻辑电路设计方法

设计思路

  1. 对实际逻辑问题进行抽象,定义输入和输出逻辑变量;
  2. 由实际逻辑问题列出真值表;
  3. 由真值表写出表达式;
  4. 化简表达式;
  5. 画出原理图。

7段数码管驱动电路

7

  • 4位输入数据,输入一个十进制数字(4位二进制数可以表示一位十进制数);
  • 7位输出控制发光管显示数字0~9。

7段数码管的两种连接方法

两种连接方法

共阴极:0代表不亮

共阳极:1代表不亮

7段数码管逻辑电路设计思路

  1. 对实际问题进行抽象,定义输入和输出逻辑变量

1

  1. 由实际逻辑问题列出真值表

2

  1. 由真值表写出表达式
  2. 化简表达式

34

  1. 画出原理图

5

考虑无关项

X

组合逻辑模块

编码器

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

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

  • 输入:X0、X1、X2、X3(高电平为有效信号);
  • 输出:A1、A0、EO(用于判定是否存在有效输入);
  • 功能:将4个输入信号进行二进制编码(4线-2线编码器)。

4线-2线编码器

  • 带输出使能的优先级编码器
  • 优先级编码:当有多个信号同时输入时,只对优先权高的一个信号进行编码;
  • 输出使能端:用于判别电路是否有信号输入。

带输出使能的优先级编码器

设计逻辑电路

step

step

step

译码器

  • 译码是编码的逆过程,有n个输入,2n个输出;
  • 每一种输入的组合对应使能某个特定的输出信号;
  • 输出的独热(one-hot,互斥)的,同一时刻只能输出一个有效信号。

与上述4线-2线译码器(高电平为有效信号)相对应,以下为2线-4线译码器(高电平为有效信号)

2线-4线译码器

译码器电路的实现

译码器电路的实现

使用译码器实现复杂逻辑

  • 译码器每个输出都对应一个最小项;
  • 使用译码器+或门可以构造出更加复杂的表达式。

使用译码器实现复杂逻辑

多路选择器

定义

  • 根据选择信号的值从N个可能的输入中选择一个作为输出;
  • 需要使用log2N位选择信号作为输入,控制输入信号的选择。

多路选择器

实现

多路选择器的实现

更多输入的多路选择器

更多输入的多路选择器

使用多路选择器实现复杂逻辑

使用多路选择器实现复杂逻辑

组合逻辑中的时序问题

传播延迟和最小延迟

  • 在实际电路中,输入影响输出的改变需要一定时间;
  • 电路设计中最具有挑战性的问题是时序

缓冲器和缓冲器时序图

定义

  • 传播延迟(propagation delay):tpd
    • 输入改变直到一个或多个输出改变为最终值所经历的最长时间延迟;
  • 最小延迟(contamination delay):tcd
    • 输入发生变化直到任何一个输出开始改变的最短时间。

传播延迟和最小延迟

产生原因

  • 产生延迟的原因包括:
    • 电路中的电阻和电容的充放电;
    • 光速的上限。
  • tpd和tcd的值可能不同
    • 上升沿与下降沿的延迟可能不同;
    • 电路存在多个输入和输出时,不同输出的延迟可能不同;
    • 电路对温度敏感,电路较热时速度会变慢。

关键路径与最短路径

关键路径与最短路径

毛刺

毛刺的产生

  • 一个输入改变引起输出的多次变化;
  • 也成为“冒险”(hazard);

例:观察A=0,C=1时,B由1变0的瞬间发生了什么?

例

上毛刺产生的分析

分析

消除毛刺

  • 当信号的变化在卡诺图中穿越2个主蕴含项的边缘时会出现毛刺;
  • 通过在卡诺图中增加多余的蕴含项来盖住这些边缘以避免毛刺;
  • 卡诺图增加多余蕴含项消除毛刺
  • 多个输入(几乎)同时变化也会产生毛刺;
    • 这些不能通过增加硬件来避免。
  • 毛刺在大多数电路中都存在。