逻辑代数与计算机中常用逻辑部件.ppt

1 计算机硬件技术 大连理工大学 计算机硬件技术 三 计算机基础课系列课程 2 计算机硬件技术 大连理工大学 第三章逻辑代数与计算机中常用逻辑部件 本章基本要求掌握与 或 非的逻辑运算规则 掌握用真值表 逻辑表达式 卡诺图表示及处理逻辑函数的方法 了解计算机内常用逻辑器件 基本门电路 三态门 触发器 寄存器 计数器 译码器的基本功能及作用 了解计算机在传输数据时常用的校验方法 奇 偶校验方法与CRC校验方法 3 计算机硬件技术 大连理工大学 3 1逻辑代数基础与逻辑函数的三种表示法 基本概念逻辑代数是1847年由英国数学家乔治 布尔 GeorgeBoole 首先创立的 所以通常人们又称逻辑代数为布尔代数 逻辑代数与普通代数有着不同的概念 其所表示的不是数值之间的大小关系 而是逻辑函数与逻辑变量之间所存在的逻辑关系与逻辑规律 逻辑规律表示了一种因果关系 如 真 与 假 有 和 无 是 与 非 开 与 关 等 这些逻辑关系的一个共同点是它们仅有两种状态 即 0和1 因此又称为二值逻辑 二值逻辑通常反映在逻辑电路上则是电路的 通 与 断 反映在电信号上则是信号电平的 髙 与 低 所以把这种工作在二值 0 1 状态下的电路称为数字逻辑电路 逻辑代数是分析和设计数字逻辑系统的数学基础 而数字逻辑电路则是构成计算机硬件核心电路的主要部分 4 计算机硬件技术 大连理工大学 逻辑代数的三种表示法 1 逻辑真值表 将逻辑函数输入 逻辑变量 与输出 函数取值 之间的所有组态关系用数字符号以并列的形式表示出来的表格 这是一种将具体问题的描述转变为逻辑关系的描述的有效工具 也是获得严谨的逻辑函数表达式的最有效方法 2 逻辑函数表达式 用与 或 非等基本的逻辑运算关系符和逻辑常量 逻辑变量所组成的表示逻辑函数的数学表达式 形式简洁明了 便于书写和推演变换 根据真值表可以列出其逻辑表达式 3 卡诺图 n个变量的函数可以由2n个方格构成的平面方格图来表示 每个方格代表逻辑函数中的一个最小项 而任何一个逻辑函数都可以表示成 最小项之和 的形式 因此通过方格阵列可清楚的反映出函数所有最小项之间的关系 这个平面方格图就是卡诺图 利用卡诺图中表示最小项的方格之间的相邻 相对 相重的位置关系进行最小项合并是进行逻辑函数化简的最直接 最有效的方法 5 计算机硬件技术 大连理工大学 3 1 1逻辑代数的基本定义与运算 逻辑代数是指 用0和1两个基本的数字符号表示逻辑常量 用取值只能为0或1的任何字母符号表示逻辑变量 用 与 或 非 等基本逻辑符号表示运算关系所构成的代数系统 逻辑代数的自变量取值只有0和1 非0即1 两个数 同样逻辑函数的取值也只有0和1 非0即1 两个数 自变量就是逻辑变量 这种函数就是逻辑函数 6 计算机硬件技术 大连理工大学 1 逻辑代数基本定义 1 所有可能出现的数只有0和1两个取值 2 基本逻辑运算关系只有 与 或 非 三种 与运算 逻辑与 逻辑乘 定义为 AND 为与运算符 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 或运算 逻辑或 逻辑加 定义为 OR 为或运算符 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 非运算 取反 定义为 0 1 1 0 7 计算机硬件技术 大连理工大学 2 基本运算规律和公式 2 基本公式 吸收律 分配律 交换律 结合律 反演律 8 计算机硬件技术 大连理工大学 吸收律 A A B A证明 A A B A 1 B A 1 AA A B A证明 A A A B A A B AA A B A B证明 A A B A A B A B A A A B A 1 B A B 9 计算机硬件技术 大连理工大学 分配律 A B C A B A C A B A C A B C证明 A B A C A A A C B A B C A 1 C B B C A B C 10 计算机硬件技术 大连理工大学 交换律 A B B AA B B A结合率 A B C A B C A B C A B C 反演律 A B C A B CA B C A B C具体例题请看教材介绍 11 计算机硬件技术 大连理工大学 3 1 2逻辑真值表 真值表 由逻辑变量的所有可能取值的组合及其对应的逻辑函数值所构成的表格 例 有一个3位二进制数ABC 列出ABC中出现奇数个1的逻辑关系 解 3位二进制数ABC共有8种组合状态 分别定义为m0 m7 它们的奇偶性定义为函数F 其中F 0表示呈偶性 F 1表示呈奇性 将ABC全部的组态关系以及对应的F取值以表格的形式表示出来 该表称为逻辑函数F的真值表 注意 真值表必须列出逻辑变量所有可能的取值及其所对应的函数取值 不能有遗漏 二个变量有22 4 三个逻辑变量有23 8 四个变量有24 16 n个变量有2n种可能的取值 12 计算机硬件技术 大连理工大学 由于逻辑表达式进行化简需要较强的技巧 不熟练者很难判断 而采用卡诺图则直观方便 定义 由逻辑变量 逻辑常量和运算符组成的表达式 它是逻辑变量的函数 也是设计逻辑电路的根据 根据真值表可以列出逻辑表达式 方法 把真值表中所有使函数值为1的自变量组合项 或 起来 3 1 3逻辑表达式 13 计算机硬件技术 大连理工大学 3 1 4卡诺图 KarnaughMap 卡诺图是逻辑函数的另一种表示形式 它是一种以图形形式来表达逻辑关系的方法 也是将逻辑函数进行逻辑化简的一种最有效的手段 用卡诺图化简逻辑函数 不但具有简单 直观 方便的特点 而且还较容易的判断出得到结果是否为最简的形式 用卡诺图表示逻辑函数 是将该逻辑函数的每一个最小项取值 按照一定规则填入到所对应的平面方格矩阵内 这个平面方格矩阵图就称为卡诺图 14 计算机硬件技术 大连理工大学 卡诺图是一种直观的平面方块图 它根据输入变量的数量n将平面划分为2n个方格 用来表示全部输入变量组合项或者表示全部输出项 与真值表有些相似 但是和真值表的自变量取值变化的最大不同在于 自变量的取值是按照它们取值之间的最小跳越关系进行排列 即在左边和上边的自变量取值中只能有一个变量的取值是变化 相反 的 其余的保持不变 卡诺图坐标点上的自变量取值可以不连续 但要保持最小跳跃 小方格中所填写的是 根据行列坐标点上自变量的取值关系 找出在逻辑表达式中对应的最小项的位置 在相应的小方格中填写1 即小方格中填写那些使得逻辑函数在所对应的行列坐标点上取值为1的项 卡诺图的书写规则 15 计算机硬件技术 大连理工大学 二维卡诺图 输入为X1 X2 输出为F 左下图为真值表 右下图为卡诺图 卡诺图左边和上边书写自变量的可能取值 中间则表明Mi最小项 最小项即一行真值表中各自变量或其 非 的逻辑乘积项 NOX1X2FM000F0M101F1M210F2M311F3 X1 01 X2 01 M0 M1 M2 M3 16 计算机硬件技术 大连理工大学 三维卡诺图输入为X1 X2 X3 输出为F 左下图为真值表 右下图为卡诺图 卡诺图的左边和上边书写自变量的可能取值 规则是最小跳跃 中间则表明最小项 NOX1X2X3FM0000F0M1001F1M2010F2M3011F3M4100F4M5101F5M6110F6M7111F7 M0M1M2M3M6M7M4M5 X1X2 X3 01 00011110 17 计算机硬件技术 大连理工大学 四维卡诺图输入为A B C D 输出为F 下图为卡诺图 卡诺图的左边上边书写自变量的可能取值 规则是最小跳跃 中间则表明最小项 18 计算机硬件技术 大连理工大学 请用卡诺图表示下列函数 1 F A B C ABC ABC ABC ABC 19 计算机硬件技术 大连理工大学 2 F A B C D ABCD BCD BCD ABCD 在此处 需要对BCD和BCD进行特殊处理 这就涉及到卡诺图的化简规则了 20 计算机硬件技术 大连理工大学 卡诺图的化简规则 若任何两个标 1 的相邻单元可以形成一个圈 就可以消去一个变量 若任何四个标 1 的相邻单元可以形成一个圈 就可以消去两个变量 若任何八个标 1 的相邻单元可以形成一个圈 就可以消去三个变量 卡诺图化简的过程就是在卡诺图上找出能够覆盖给定函数全部为1的单元的个数最少同时覆盖面尽可能大的圈 然后写出其最简逻辑表达式 需要注意的是 由于卡诺图的最上行 最下行和最左列 最右列以及4个顶点上所对应的小方格在逻辑关系上也是彼此相邻的 圈最小项时也属于相邻关系 21 计算机硬件技术 大连理工大学 AB CD 00011110 00011110 1 1 1 1 1 1 1 1 例 试用卡诺图化简下面的逻辑表达式 解 根据逻辑表达式做出卡诺图如下 根据卡诺图化简规则 最后得到化简后的结果 22 计算机硬件技术 大连理工大学 AB CD 00011110 1 1 1 1 1 1 1 1 例 试用卡诺图化简下面的逻辑表达式 解 根据逻辑表达式做出卡诺图如下 根据卡诺图化简规则 最后得到化简后的结果 23 计算机硬件技术 大连理工大学 3 2逻辑门与常用的逻辑部件 逻辑门是描述数字逻辑电路的最基本单元部件 是计算机硬件电路的基础 由于它的结构与逻辑函数中描述的自变量乘积项及函数逻辑关系相对应 所以能够实现计算机中的运算 控制 数据存储等功能部件的逻辑电路描述 基本逻辑门电路有 与门 电路 或门 电路和 非门 电路 常用的逻辑门电路还有 与非门 电路 与或门 电路 与或非 门电路 异或 门电路 同或 门电路 三态门电路等 在逻辑门电路中 任何信号只存在两种状态 即高电平和低电平 通常以高电平来表示逻辑 1 正逻辑 以低电平来表示逻辑 0 负逻辑 24 计算机硬件技术 大连理工大学 3 2 1基本的逻辑门电路 1 逻辑 与 运算和 与门 电路 逻辑 与 又称为逻辑 乘 运算 运算符号 AND 等 逻辑表达式 L A B A B 与门电路符号 真值表 用表格说明输入输出变量之间的关系 ABL A B000010100111 1 A B均为1 0 A B中任一为0 AB L 25 计算机硬件技术 大连理工大学 2 逻辑 或 运算和 或门 电路 逻辑 或 又称为逻辑加运算 运算符号 OR 等 逻辑表达式 L A B A B 或门电路符号 逻辑真值表 ABL A B000011101111 L AB 1 A B中任一为1 0 A B均为0 26 计算机硬件技术 大连理工大学 3 逻辑 非 运算和 非门 电路 逻辑 非 又称为逻辑反运算 运算符号 上横线 逻辑表达式为 L 非门电路符号 逻辑真值表 AL0110 A A 1 A 0 0 A 1 L 27 计算机硬件技术 大连理工大学 3 2 2常用的组合逻辑门 在数字系统中 除了基本的 与 运算 或 运算 非 运算之外 为了方便逻辑关系的描述常常使用一些通过这三种基本逻辑运算关系派生出来的运算逻辑关系 这种派生出来的逻辑运算通常被称为复合运算 常见的复合运算有 与非 或非 同或及异或等 还有很多的组合逻辑门电路 如 全加器 译码器 编码器 多路选择器等等 下面只介绍加法器和译码器 28 计算机硬件技术 大连理工大学 1 半加器和全加器 计算机的一个主要功能就是进行数字信息处理 处理中一项很重要的工作就是进行数值的算数运算 通过上一章的介绍我们已经有了一个概念 计算机首先是将各种要处理的数值信息转变成机内的二进制形式进行表示 其中基本的算术运算 加 减 乘 除 都可以以补码的形式通过加法来完成 所以加法器是计算机系统中最基本的也是最重要的部件 由于二进制运算可以用逻辑运算来表示 因此可以用逻辑设计的方法来设计加法运算电路 加法器分为半加器和全加器 29 计算机硬件技术 大连理工大学 1 一位半加器设计 由于半加器不需要考虑低位向本位产生的进位 因此它只有两个输入端和两个输出端 设加数与被加数 输入端 为A B 和为S 输出端 本位产生的向高位进位为Ci 输出端 它们的取值关系用下列真值表来表示 S AB AB A B Ci AB 30 计算机硬件技术 大连理工大学 2 一位全加器的设计 由于全加器考虑了低位向本位产生的进位关系 所以它有三个输入端和两个输出端 设输入变量为 A 被加数 B 加数 Ci 1 低位进位 输出变量为 和S 本位向高位的进位Ci 1 它们的取值关系用下列真值表表示 S ABCi 1 ABCi 1 ABCi 1 ABCi 1 A B Ci 1Ci 1 ABCi 1 ABCi 1 ABCi 1 ABCi 1 A B Ci 1 AB 31 计算机硬件技术 大连理工大学 2 译码器 译码 把某组编码翻译为唯一的输出 译码器 有3 8译码器 即8选1译码器和4 16译码器 即16选1译码器等多种 例如 3 8译码器 即8选1译码器的输入信号有三个 C B A A为低位 三位二进制数可组成8个不同数字 因此可分别选中输出Y0到Y7的某一个输出故称为8选1译码器 32 计算机硬件技术 大连理工大学 下图分别为3 8译码器引脚图和输入输出真值表其中 G1 G2A G2B为芯片选择端 G1高电平有效 而G2A G2B为低电平有效 74LS138 33 计算机硬件技术 大连理工大学 3 2 3触发器 功能 计算机中存放一位二进制信息的基本单元器件 稳定状态 触发器有两种稳定状态 分别表示0 1 其状态取决于当前输入和以前的存储状态 时序逻辑电路 常用的基本触发器 有D触发器和J K触发器等 下面介绍两种触发器 34 计算机硬件技术 大连理工大学 1 D触发器 DSQCLKCLRQ 输入输出SCLRCLKDQ0011000010XX101XX0 电路符号 D为数据输入端 CLK为时钟信号 S为置位信号端 CLR复位信号端 Q为输出信号端 D触发器功能表 正跳变触发有效 35 计算机硬件技术 大连理工大学 2 J K触发器 输入输出SCLRCLKJKQ0000不变00101000100011翻转01XXX010XXX1 电路符号 J K为控制输入端 CLK为时钟信号 S为置位信号端 CLR复位信号端 Q为输出信号端 J K触发器功能表 负跳变触发有效 36 计算机硬件技术 大连理工大学 3 2 4几种计算机常用逻辑部件 1 寄存器 功能 计算机中常用部件 用于暂存二进制信息 组成 寄存器可由多个触发器组成 每个触发器存1Bit N个触发器储存N位二进制数据 下图为由4个D触发器组成的四位缓冲寄存器 寄存器通常可以用来作为数据缓存的缓冲寄存器和进行移位操作的移位寄存器 见教材详细介绍 37 计算机硬件技术 大连理工大学 2 计数器 组成 也是一种由若干个触发器组成的寄存器 功能 是能够在外部计数脉冲的作用下 将存储在触发器中的数字加1 在计算机中 计数器可被用来对取出的指令进行计数 以保证能准确地取出后续指令 常用计数器 有脉冲计数器 同步计数器 程序计数器等很多种 在此仅介绍一种最基本的四位二进制脉冲计数器 电路原理如下页图 38 计算机硬件技术 大连理工大学 四级二进制并行计数器 39 计算机硬件技术 大连理工大学 3 三态门 D 输入端L 输出端E 使能端当E 1时 其输出等于输入 是同相门 当E 0时 输出与输入呈现高电阻隔离 计算机中用做数据输出器件 当不输出数据时 可令E 0 使对总线无影响 因而多个器件可同时连到总线上 40 计算机硬件技术 大连理工大学 3 3计算机中的数据校验方法 计算机中各部件与各部件之间经常需要进行大量的数据存取 传送操作 并且要求传输准确 可靠 为此一方面需要通过硬件电路的可靠性来保障 另一方面还要在传输过程中 需对接收到的数据进行检错 纠错 以便发现和纠正数据在传输过程中产生的错误 常用的数据校验方法有 奇偶校验 循环冗余校验 海明码等 本节将介绍前两种校验方法 41 计算机硬件技术 大连理工大学 名词概念 码字 由若干代码组成的一个字 如8421码中6 0110 7 0111 码距 一种码制中任意两个码字间的最小距离 距离 两个码字之间不同的代码个数 8421码中 最小的码距为1 如0000和0001 0010和0011等 最大码距为4 如0111和1000 8421码的码距为1 码距为1 即不能查错也不能纠错 码距越大 查错 纠错能力越强 42 计算机硬件技术 大连理工大学 3 3 1奇偶校验码 奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法 奇偶校验法的原理 在每组数据信息上附加一个校验位 校验位的取值 0或1 取决于这组信息中 1 的个数和校验方式 奇或偶校验 如果采用奇校验 则这组数据加上校验码位后数据中 1 的个数应为奇数个 如果采用偶校验 则这组数据加上校验码位后数据中 1 的个数应为偶数个 43 计算机硬件技术 大连理工大学 例如 八位信息 10101011 中共有5个 1 附加校验位后变为九位 若采用奇校验 则附加的校验位应取 0 值 保证1的个数为奇数个即010101011 若采用偶校验 则附加的校验位应取 1 值 保证1的个数为偶数个即110101011 奇偶校验的特点 1 奇偶校验法使数据的码距为2 因而可检出数据传送过程中奇数个数位出错的情况 2 实际中两位同时出错的概率极低 奇偶校验法简便可靠易行 但它只能发现错误 却不知错在何处 因而不能自动纠正 44 计算机硬件技术 大连理工大学 例如一个实用的8 Bits数据奇偶校验与奇偶校验码形成电路 其中数据用D7 D0表示 校验位用P表示 D偶校错 D奇校错 P偶形成 D奇形成 45 计算机硬件技术 大连理工大学 3 3 2循环冗余码 CRC码 循环冗余校验方式 通过某种数学公式建立信息位和校验位之间的约定关系 能够校验传送信息的对错 并且能自动修正错误 广泛用于通信和磁介存储器中 CRC编码格式是在k位信息后加r位检验码 NN 121信息位 k位 校验位 r位 C1C2 CKr1r2 ri 46 计算机硬件技术 大连理工大学 在被传输的有效数据代码之外 扩充部分校验代码 扩充的部分被称为校验位 将有效数据代码和扩充校验位一起按照某种规则或算法进行统一编码 形成带校验信息的数据 在数据传输时一并进行传送 当接收端收到带有校验信息的编码数据时 再利用约定的规则或算法进行译码 解码 如果所约定的规则或算法没被破坏则表示数据传输正确 否则表明收到的数据信息在传输过程中发生错误 然后根据被破坏后编码信息的某些特征和规则来判断 看是哪一位出错 再进行修正它 冗余校验法的基本原理是 47 计算机硬件技术 大连理工大学 1 CRC码的编码方法 CRC