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

计算机硬件技术 （三） 计算机基础课系列课程计算机基础课系列课程 1 1 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 第三章 逻辑代数与 计算机中常用逻辑部件 本章基本要求 1. 掌握与、或、非的逻辑运算规则； 2. 掌握用真值表、逻辑表达式、卡诺图表示及 处理逻辑函数的方法； 3. 了解计算机内常用逻辑器件：基本门电路、 三态门、 触发器、寄存器、计数器、译码 器的基本功能及作用； 4. 了解计算机在传输数据时常用的校验方法： 奇、偶校验方法与CRC校验方法。 2 2 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.1 逻辑代数基础与逻辑函数的三种表示法 基本概念 l逻辑代数是1847年由英国数学家乔治布尔（George Boole)首 先创立的，所以通常人们又称逻辑代数为布尔代数。 l逻辑代数与普通代数有着不同的概念，其所表示的不是数值之 间的大小关系，而是逻辑函数与逻辑变量之间所存在的逻辑关 系与逻辑规律。 l逻辑规律表示了一种因果关系，如“真”与“假”、“有”和“无”、“ 是”与“非”、“开”与“关”等，这些逻辑关系的一个共同点是它们 仅有两种状态，即：0和1，因此又称为二值逻辑。 l二值逻辑通常反映在逻辑电路上则是电路的“通”与“断”、反映 在电信号上则是信号电平的“髙”与“低”，所以把这种工作在二 值（0、1）状态下的电路称为数字逻辑电路。逻辑代数是分析 和设计数字逻辑系统的数学基础，而数字逻辑电路则是构成计 算机硬件核心电路的主要部分。 3 3 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 逻辑代数的三种表示法 1逻辑真值表：将逻辑函数输入（逻辑变量）与输出（函数取值 ）之间的所有组态关系用数字符号以并列的形式表示出来的表格 。，这是一种将具体问题的描述转变为逻辑关系的描述的有效工 具，也是获得严谨的逻辑函数表达式的最有效方法。 2逻辑函数表达式：用与、或、非等基本的逻辑运算关系符和逻 辑常量、逻辑变量所组成的表示逻辑函数的数学表达式。形式简 洁明了，便于书写和推演变换，根据真值表可以列出其逻辑表达 式。 3卡诺图：n个变量的函数可以由2n个方格构成的平面方格图来表 示，每个方格代表逻辑函数中的一个最小项，而任何一个逻辑函 数都可以表示成“最小项之和”的形式，因此通过方格阵列可清楚 的反映出函数所有最小项之间的关系，这个平面方格图就是卡诺 图。利用卡诺图中表示最小项的方格之间的相邻、相对、相重的 位置关系进行最小项合并是进行逻辑函数化简的最直接、最有效 的方法。 4 4 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.1.1 逻辑代数的基本定义与运算 l逻辑代数是指：用0和1两个基本的数字符号表示 逻辑常量，用取值只能为0或1的任何字母符号表 示逻辑变量，用“与”、“或”、“非”等基本逻辑符 号表示运算关系所构成的代数系统。 l逻辑代数的自变量取值只有0和1（非0即1）两个 数，同样逻辑函数的取值也只有0和1（非0即1） 两个数，自变量就是逻辑变量，这种函数就是逻 辑函数。 5 5 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 1.逻辑代数基本定义 （1）所有可能出现的数只有0和1两个取值 。 （2）基本逻辑运算关系只有“与”、“或”、“非”三种： l 与运算（逻辑与、逻辑乘）定义为：（、AND、 为与运算符） 000，010，100，111； 0 00，0 10，1 00，1 11； l或运算（逻辑或、逻辑加）定义为：（、OR、 为或运算符） 000，011，101，111； 000，011，101，111； l非运算（取反）定义为： 01 ， 10 6 6 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2.2.基本运算规律和公式基本运算规律和公式 （1 1）基本运算：）基本运算： 加：加：A+0=A，A+1=1，A+A=A，A+A=1 乘：乘：A0=0， A1=A，AA=A，AA=0 非：非：A+A=1，AA=0，A=A （2 2）基本公式：）基本公式： 吸收律，分配律，交换律，结合律，反演律吸收律，分配律，交换律，结合律，反演律 7 7 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 & 吸收律： A+AB=A 证明：A+AB=A（1+B）=A1=A A（A+B）=A 证明：AA+AB=A+AB=A A+AB=A+B 证明：A+AB=A+AB+AB =A+（A+A）B=A+1B=A+B 8 8 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 & 分配律分配律： A A (B+C)=A(B+C)=A B+AB+A C C (A+B) (A+B) (A+C)=A+B(A+C)=A+B C C 证明：证明： ( (A+B) (A+C)A+B) (A+C) =A A+A C+B A+B C =A A+A C+B A+B C =A(1+C+B)+B C =A(1+C+B)+B C =A+B C =A+B C 9 9 计算机硬件技术大连理工大学计算机硬件技术大连理工大学 & 交换律：交换律： A+B=B+A AA+B=B+A AB=BAB=BA & 结合率：结合率： （A+BA+B）+ C = A+ C = A+（B+CB+C） （A A B B） C = A C = A（B B C C） & 反演律：反演律： ABC=A+B+C ABC=A+B+C A+B+C=A B C A+B+C=A B C 具体例题请看教材介绍。 1010计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.1.2 3.1.2 逻辑真值表逻辑真值表 真值表：真值表：由逻辑变量的所有可能取由逻辑变量的所有可能取 值的组合及其对应的逻辑函数值所值的组合及其对应的逻辑函数值所 构成的表格。构成的表格。 例：例：有一个有一个3 3位二进制数位二进制数ABCABC，列出列出 ABCABC中出现奇数个中出现奇数个1 1的逻辑关系。的逻辑关系。 解：解：3 3位二进制数位二进制数ABCABC共有共有8 8种组合状种组合状 态，分别定义为态，分别定义为m0m0m7m7；它们的奇它们的奇 偶性定义为函数偶性定义为函数F F，其中其中F F0 0表示呈表示呈 偶性，偶性，F F1 1表示呈奇性，将表示呈奇性，将ABCABC全部全部 的组态关系以及对应的的组态关系以及对应的F F取值以表格取值以表格 的形式表示出来。该表称为逻辑函的形式表示出来。该表称为逻辑函 数数F F的真值表。的真值表。 NoA B CF m00 0 00 m10 0 11 m20 1 01 m30 1 10 m41 0 01 m51 0 10 m61 1 00 m71 1 11 注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数 取值，不能有遗漏。（二个变量有取值，不能有遗漏。（二个变量有2 2 2 2 =4 =4、三个逻辑变量有、三个逻辑变量有2 2 3 3 =8 =8、四、四 个变量有个变量有2 2 4 4 1616、n n个变量有个变量有2 2 n n 种可能的取值种可能的取值）。 1111计算机硬件技术大连理工大学计算机硬件技术大连理工大学 由于逻辑表达式进行化简需要较强的技巧，不熟练者很难由于逻辑表达式进行化简需要较强的技巧，不熟练者很难 判断，而采用卡诺图则直观方便。判断，而采用卡诺图则直观方便。 定义：定义：由逻辑变量、逻辑常量和运算符组成的表达式。由逻辑变量、逻辑常量和运算符组成的表达式。 它是逻辑变量的函数，也是设计逻辑电路的根据。它是逻辑变量的函数，也是设计逻辑电路的根据。 根据真值表可以列出逻辑表达式。根据真值表可以列出逻辑表达式。 方法：方法：把真值表中所有使函数值为把真值表中所有使函数值为1 1的自变量组合项的自变量组合项“或或”起来。起来。 例如：例如：上页例题中的逻辑表达式为：上页例题中的逻辑表达式为： F=1: F=1: F(A,B,C)=m(1,2,4,7)=ABC+ABC+ABC+ABC F(A,B,C)=m(1,2,4,7)=ABC+ABC+ABC+ABC F=0: F=0: F(A,B,C)=m(0,3,5,6)=ABC+ABC+ABC+ABC F(A,B,C)=m(0,3,5,6)=ABC+ABC+ABC+ABC 3.1.3 3.1.3 逻辑表达式逻辑表达式 1212计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.1.4 卡诺图（Karnaugh Map） 卡诺图是逻辑函数的另一种表示形式，它是一种以图卡诺图是逻辑函数的另一种表示形式，它是一种以图 形形式来表达逻辑关系的方法，也是将逻辑函数进行逻辑形形式来表达逻辑关系的方法，也是将逻辑函数进行逻辑 化简的一种最有效的手段。用卡诺图化简逻辑函数，不但化简的一种最有效的手段。用卡诺图化简逻辑函数，不但 具有简单、直观、方便的特点，而且还较容易的判断出得具有简单、直观、方便的特点，而且还较容易的判断出得 到结果是否为最简的形式。到结果是否为最简的形式。 用卡诺图表示逻辑函数，是将该逻辑函数的每一个用卡诺图表示逻辑函数，是将该逻辑函数的每一个 最小项取值，按照一定规则填入到所对应的平面方格矩阵最小项取值，按照一定规则填入到所对应的平面方格矩阵 内，这个平面方格矩阵图就称为卡诺图。内，这个平面方格矩阵图就称为卡诺图。 1313计算机硬件技术大连理工大学计算机硬件技术大连理工大学 卡诺图是一种直观的平面方块图。它根据输入变量的数卡诺图是一种直观的平面方块图。它根据输入变量的数 量量n n将平面划分为将平面划分为2 2 n n 个方格个方格，用来表示全部输入变量组合，用来表示全部输入变量组合 项或者表示全部输出项。项或者表示全部输出项。 与真值表有些相似，但是和真值表的自变量取值变化的与真值表有些相似，但是和真值表的自变量取值变化的 最大不同在于：自变量的取值是按照它们取值之间的最大不同在于：自变量的取值是按照它们取值之间的最最 小跳越小跳越关系进行排列，即在左边和上边的自变量取值中关系进行排列，即在左边和上边的自变量取值中 只能有一个变量的取值是变化（相反）的，其余的保持只能有一个变量的取值是变化（相反）的，其余的保持 不变。不变。 卡诺图坐标点上的自变量取值可以不连续，但要保持最卡诺图坐标点上的自变量取值可以不连续，但要保持最 小跳跃。小跳跃。 小方格中所填写的是：根据行列坐标点上自变量的取值小方格中所填写的是：根据行列坐标点上自变量的取值 关系，找出在逻辑表达式中对应的最小项的位置，在相关系，找出在逻辑表达式中对应的最小项的位置，在相 应的小方格中填写应的小方格中填写1 1；即小方格中填写那些使得逻辑函数；即小方格中填写那些使得逻辑函数 在所对应的行列坐标点上在所对应的行列坐标点上取值为取值为1 1的项的项。 卡诺图的书写规则：卡诺图的书写规则： 1414计算机硬件技术大连理工大学计算机硬件技术大连理工大学 二维卡诺图 输入为输入为X1X1、X2X2，输出为输出为 F F。 左下图为真值表，右下图为卡诺图。左下图为真值表，右下图为卡诺图。 卡诺图左边和上边书写自变量的可能取值，中间则表明卡诺图左边和上边书写自变量的可能取值，中间则表明 MiMi最小最小 项。最小项即一行真值表中各自变量或其项。最小项即一行真值表中各自变量或其“非非”的逻辑乘积项。的逻辑乘积项。 NO X1 X2 F M0 0 0 F0 M1 0 1 F1 M2 1 0 F2 M3 1 1 F3 X1 0 1 X2 0 1 M0M1 M2M3 1515计算机硬件技术大连理工大学计算机硬件技术大连理工大学 三维卡诺图 输入为输入为X1X1、X2X2、X3X3，输出为输出为 F F。 左下图为真值表，右下图为卡诺图左下图为真值表，右下图为卡诺图。 卡诺图的左边和上边书写自变量的可能取值，规则是卡诺图的左边和上边书写自变量的可能取值，规则是最小跳跃最小跳跃 。中间则表明最小项。中间则表明最小项。 NO X1 X2 X3 F M0 0 0 0 F0 M1 0 0 1 F1 M2 0 1 0 F2 M3 0 1 1 F3 M4 1 0 0 F4 M5 1 0 1 F5 M6 1 1 0 F6 M7 1 1 1 F7 M0 M1 M2 M3 M6 M7 M4 M5 X1X2 X3 0 1 00 01 11 10 1616计算机硬件技术大连理工大学计算机硬件技术大连理工大学 CD AB 00011110 00M0M1M3M2 01M4M5M7M6 11M12M13M15M14 10M8M9M11M10 四维卡诺图 输入为输入为A A、B B、C C、D D，输出为输出为F F。 下图为卡诺图下图为卡诺图。 卡诺图的左边上边书写自变量的可能取值，规则是卡诺图的左边上边书写自变量的可能取值，规则是最小跳跃最小跳跃。 中间则表明最小项。中间则表明最小项。 1717计算机硬件技术大连理工大学计算机硬件技术大连理工大学 请用卡诺图表示下列函数 1. F(A,B,C)=ABC+ABC+ABC+ABC C AB 01 00 0111 111 101 1818计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2.F(A,B,C,D)=ABCD+BCDBCD+ABCD CD AB 00011110 00 01111 1111 101 在此处在此处, ,需要对需要对BCDBCD和和BCDBCD进行特殊处理进行特殊处理, ,这就涉及这就涉及 到卡诺图的化简规则了。到卡诺图的化简规则了。 1919计算机硬件技术大连理工大学计算机硬件技术大连理工大学 卡诺图的化简规则 若任何两个标“1”的相邻单元可以形成一个圈，就可以 消去一个变量； 若任何四个标“1”的相邻单元可以形成一个圈，就可以 消去两个变量； 若任何八个标“1”的相邻单元可以形成一个圈，就可以 消去三个变量； 卡诺图化简的过程就是在卡诺图上找出能够覆盖给定函 数全部为1的单元的个数最少同时覆盖面尽可能大的圈， 然后写出其最简逻辑表达式。 需要注意的是，由于卡诺图的最上行、最下行和最左列 、最右列以及4个顶点上所对应的小方格在逻辑关系上也 是彼此相邻的，圈最小项时也属于相邻关系。 2020计算机硬件技术大连理工大学计算机硬件技术大连理工大学 AB CD 00 01 11 10 00 01 11 10 11 11 11 11 例：试用卡诺图化简下面的逻辑表达式例：试用卡诺图化简下面的逻辑表达式 。 解：根据逻辑表达式做出卡诺图如下：解：根据逻辑表达式做出卡诺图如下： 根据卡诺图化简根据卡诺图化简 规则，最后得到规则，最后得到 化简后的结果：化简后的结果： 2121计算机硬件技术大连理工大学计算机硬件技术大连理工大学 AB CD 00 01 11 10 1111 1111 例：试用卡诺图化简下面的逻辑表达式例：试用卡诺图化简下面的逻辑表达式 。 解：解：根据逻辑表达式做出卡诺图如下：根据逻辑表达式做出卡诺图如下： 根据卡诺图化简根据卡诺图化简 规则，最后得到规则，最后得到 化简后的结果：化简后的结果： 2222计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.2 逻辑门与常用的逻辑部件 逻辑门是描述数字逻辑电路的最基本单元部件，是计算逻辑门是描述数字逻辑电路的最基本单元部件，是计算 机硬件电路的基础；由于它的结构与逻辑函数中描述的自变机硬件电路的基础；由于它的结构与逻辑函数中描述的自变 量乘积项及函数逻辑关系相对应，所以能够实现计算机中的量乘积项及函数逻辑关系相对应，所以能够实现计算机中的 运算、控制、数据存储等功能部件的逻辑电路描述。运算、控制、数据存储等功能部件的逻辑电路描述。 基本逻辑门电路有基本逻辑门电路有与门与门电路电路或门或门电路和电路和非非 门门电路。常用的逻辑门电路还有电路。常用的逻辑门电路还有与非门与非门电路电路与或与或 门门电路电路与或非与或非门电路门电路异或异或门电路门电路同或同或 门电路门电路三态门电路等。三态门电路等。 在逻辑门电路中，任何信号只存在两种状态，即高电平和 在逻辑门电路中，任何信号只存在两种状态，即高电平和 低电平；通常以高电平来表示逻辑低电平；通常以高电平来表示逻辑11（正逻辑）、以低电平（正逻辑）、以低电平 来表示逻辑来表示逻辑00（负逻辑）。（负逻辑）。 2323计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.2.1 基本的逻辑门电路 1.1.逻辑逻辑“与与”运算和运算和“与门与门”电路电路 逻辑“与”又称为逻辑“乘”运算。 运算符号：“”,“” ,“AND”等。 逻辑表达式：L=AB = AB= 与门电路符号： 真值表：用表格说明输入输出变量之间的关系。 A B L= AB 0 0 0 0 1 0 1 0 0 1 1 1 1 (A、B均为1) 0 (A、B中任一为 0) A B L 2424计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2. 2. 逻辑逻辑“或或”运算和运算和“或门或门”电路电路 逻辑逻辑“或或”又称为逻辑加运算。又称为逻辑加运算。 运算符号：运算符号：“ “+” ”、“ “” ”、 “ “OROR” ”等。等。 逻辑表达式：逻辑表达式：L=A+B=AL=A+B=ABB= 或门电路符号：或门电路符号： 逻辑真值表：逻辑真值表： A B L=A+B 0 0 0 0 1 1 1 0 1 1 1 1 L A B 1 (A、B中任一为 1) 0 (A、B均为0) 2525计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3. 3. 逻辑逻辑“非非”运算和运算和“非门非门” 电路电路 逻辑逻辑“非非”又称为逻辑反运算又称为逻辑反运算. . 运算符号：运算符号：“ ”（上横线） 逻辑表达式为：逻辑表达式为： L= = 非门电路符号：非门电路符号： 逻辑真值表：逻辑真值表： A L 0 1 1 0 A A 1 （A=0） 0 （A=1） L 2626计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.2.2 3.2.2 常用的组合逻辑门常用的组合逻辑门 在数字系统中，除了基本的在数字系统中，除了基本的“ “与与” ”运算、运算、“ “或或” ”运算、运算、“ “非非” ”运算之运算之 外，为了方便逻辑关系的描述常常使用一些通过这三种基本逻辑运外，为了方便逻辑关系的描述常常使用一些通过这三种基本逻辑运 算关系派生出来的运算逻辑关系，这种派生出来的逻辑运算通常被算关系派生出来的运算逻辑关系，这种派生出来的逻辑运算通常被 称为复合运算，常见的复合运算有：与非、或非、同或及异或等。称为复合运算，常见的复合运算有：与非、或非、同或及异或等。 还有很多的组合逻辑门电路，如：全加器、译码器、编码器、 多路选择器等等，下面只介绍加法器和译码器。 0 0 1 0 1 0 1 0 0 1 1 1 = A B+A B 2727计算机硬件技术大连理工大学计算机硬件技术大连理工大学 1.1.半加器和全加器半加器和全加器 计算机的一个主要功能就是进行数字信息处理计算机的一个主要功能就是进行数字信息处理 ，处理中一项很重要的工作就是进行数值的算数运，处理中一项很重要的工作就是进行数值的算数运 算，通过上一章的介绍我们已经有了一个概念，计算，通过上一章的介绍我们已经有了一个概念，计 算机首先是将各种要处理的数值信息转变成机内的算机首先是将各种要处理的数值信息转变成机内的 二进制形式进行表示，其中基本的算术运算（加、二进制形式进行表示，其中基本的算术运算（加、 减、乘、除），都可以以补码的形式通过加法来完减、乘、除），都可以以补码的形式通过加法来完 成。所以加法器是计算机系统中最基本的也是最重成。所以加法器是计算机系统中最基本的也是最重 要的部件。由于二进制运算可以用逻辑运算来表示要的部件。由于二进制运算可以用逻辑运算来表示 ，因此可以用逻辑设计的方法来设计加法运算电路，因此可以用逻辑设计的方法来设计加法运算电路 。加法器分为半加器和全加器。加法器分为半加器和全加器。 2828计算机硬件技术大连理工大学计算机硬件技术大连理工大学 （1 1）一位半加器设计）一位半加器设计 由于半加器不需要考虑低位向本位产生的进位，因此它只由于半加器不需要考虑低位向本位产生的进位，因此它只 有两个输入端和两个输出端。设加数与被加数（输入端）为有两个输入端和两个输出端。设加数与被加数（输入端）为 A A、B B ；和为和为S S（输出端）、本位产生的向高位进位为输出端）、本位产生的向高位进位为C C i i （输输 出端）；它们的取值关系用下列真值表来表示。出端）；它们的取值关系用下列真值表来表示。 ABSC 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 S=AB+AB=AB，Ci=AB A B S C 2929计算机硬件技术大连理工大学计算机硬件技术大连理工大学 （2 2）一位全加器的设计）一位全加器的设计 由于全加器考虑了低位向本位产生的进位关系，所以它有三个输入由于全加器考虑了低位向本位产生的进位关系，所以它有三个输入 端和两个输出端。设输入变量为：端和两个输出端。设输入变量为：A A（被加数）、被加数）、B B（加数）、加数）、 C Ci-1 i-1 （低位进位），输出变量为：和低位进位），输出变量为：和S S、本位向高位的进位本位向高位的进位C Ci+1 i+1， ，它们的它们的 取值关系用下列真值表表示。取值关系用下列真值表表示。 ABCi-1SCi+1 00000 00110 01010 01101 10010 10101 11001 11111 Ci-1 Ci S A B S=ABCi-1+ABCi-1+ABCi-1+ABCi-1 =ABCi-1 Ci+1=ABCi-1+ABCi-1+ABCi-1+ABCi-1 =(AB)Ci-1+AB 3030计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2 2译码器译码器 译码：译码：把某组编码翻译为唯一的输出。把某组编码翻译为唯一的输出。 译码器：译码器：有有3838译码器，即译码器，即8 8选选1 1译码器译码器 和和416416译码器，即译码器，即1616选选1 1译码器等多种。译码器等多种。 例如：3838译码器，译码器， 即即8 8选选1 1译码器的输入信号有三个：译码器的输入信号有三个： C C、B B、A A（A A为低位），三位二进制数可为低位），三位二进制数可 组成组成8 8个不同数字，因此可分别选中输出个不同数字，因此可分别选中输出 Y Y 0 0 到到Y Y 7 7 的某一个输出故称为的某一个输出故称为 8 8选选1 1译码器。译码器。 3131计算机硬件技术大连理工大学计算机硬件技术大连理工大学 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 G1 G2A G2B C B A 下图分别为下图分别为3-83-8译码器引脚图和输入输出真值表译码器引脚图和输入输出真值表 其中：其中：G G 1 1 、G G2A 2A、 、G G2B 2B为芯片选择端， 为芯片选择端，G G 1 1 高电高电 平有效，而平有效，而G G2A 2A、 、G G2B 2B为低电平有效。 为低电平有效。 输 入 输 出 C B A Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 74LS138 3232计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.2.3 3.2.3 触发器触发器 功能：功能：计算机中存放一位二进制信息的基本单元器件。计算机中存放一位二进制信息的基本单元器件。 稳定状态：稳定状态：触发器有两种稳定状态，分别表示触发器有两种稳定状态，分别表示0 0，1 1。 其状态取决于当前输入和以前的存储状态其状态取决于当前输入和以前的存储状态( (时序逻辑电路时序逻辑电路) ) 。 常用的基本触发器：常用的基本触发器：有有D D触发器和触发器和J-KJ-K触发器等。触发器等。 下面下面介绍两种触发器。介绍两种触发器。 3333计算机硬件技术大连理工大学计算机硬件技术大连理工大学 1.1.D D触发器触发器 D S Q CLK CLR Q 输入 输出 S CLR CLK D Q 0 0 1 1 0 0 0 0 1 0 X X 1 0 1 X X 0 电路符号：电路符号： D D为数据输入端；为数据输入端； CLKCLK为时钟信号；为时钟信号； S S为置位信号端；为置位信号端； CLRCLR复位信号端；复位信号端； Q Q为输出信号端。为输出信号端。 D D触发器功能表：触发器功能表： 正跳变触发有效。正跳变触发有效。 3434计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2. J-K2. J-K触发器触发器 输入 输出 S CLR CLK J K Q 0 0 0 0 不变 0 0 1 0 1 0 0 0 1 0 0 0 1 1 翻转 0 1 X X X 0 1 0 X X X 1 电路符号：电路符号： J J、K K为控制输入端；为控制输入端； CLKCLK为时钟信号；为时钟信号； S S为置位信号端；为置位信号端； CLRCLR复位信号端；复位信号端； Q Q为输出信号端。为输出信号端。 J-KJ-K触发器功能表：触发器功能表： （负跳变触发有效）（负跳变触发有效） J S Q CLK K CLR Q 3535计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.2.4 3.2.4 几种计算机常用逻辑部件几种计算机常用逻辑部件 1 1、寄存器、寄存器 功能：功能：计算机中常用部件，用于暂存二进制信息。计算机中常用部件，用于暂存二进制信息。 组成：组成：寄存器可由多个触发器组成。每个触发器存寄存器可由多个触发器组成。每个触发器存 1Bit1Bit，N N个触发器储存个触发器储存N N位二进制数据。位二进制数据。 下图为由下图为由4 4个个D D触发器组成的四位缓冲寄存器。触发器组成的四位缓冲寄存器。 Q3 D3 CLK X3 Q2 D2 CLK X2 Q1 D1 CLK X1 Q0 D0 CLK X0 控制端 寄存器通常可以用来作为数据缓存的缓冲寄存器和进行移位寄存器通常可以用来作为数据缓存的缓冲寄存器和进行移位 操作的移位寄存器。见教材详细介绍。操作的移位寄存器。见教材详细介绍。 3636计算机硬件技术大连理工大学计算机硬件技术大连理工大学 2.2.计数器计数器 组成：组成：也是一种由若干个触发器组成的寄存器。也是一种由若干个触发器组成的寄存器。 功能：功能：是能够在外部计数脉冲的作用下，将存储是能够在外部计数脉冲的作用下，将存储 在触发器中的数字加在触发器中的数字加1 1。 在计算机中，计数器可被用来对取出的指令进行在计算机中，计数器可被用来对取出的指令进行 计数，以保证能准确地取出后续指令。计数，以保证能准确地取出后续指令。 常用计数器：常用计数器：有脉冲计数器、同步计数器、程序有脉冲计数器、同步计数器、程序 计数器等很多种。在此仅介绍一种最基本的四位二计数器等很多种。在此仅介绍一种最基本的四位二 进制脉冲计数器，电路原理如下页图进制脉冲计数器，电路原理如下页图。 3737计算机硬件技术大连理工大学计算机硬件技术大连理工大学 四级二进制并行计数器四级二进制并行计数器 J Q CLK K CLR J Q CLK K CLR Q0 Q1 Q2 Q3 清0端 控制端 计 数 端 J Q CLK K CLR J Q CLK K CLR CLK Q0 Q1 Q2 Q3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3838计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.3.三态门三态门 DD输入端输入端 LL输出端输出端 E E 使能端使能端 当当E=1E=1时，时，其输出等于输入，是同相门；其输出等于输入，是同相门； 当当E=0E=0时，时，输出与输入呈现高电阻隔离。输出与输入呈现高电阻隔离。 计算机中用做数据输出器件，当不输出数据时计算机中用做数据输出器件，当不输出数据时 ，可令，可令E=0E=0，使对总线无影响，因而多个器件可同使对总线无影响，因而多个器件可同 时连到总线上。时连到总线上。 D E L 3939计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.3 计算机中的数据校验方法 计算机中各部件与各部件之间经常需要进行大量计算机中各部件与各部件之间经常需要进行大量 的数据存取、传送操作，并且要求传输准确、可靠。的数据存取、传送操作，并且要求传输准确、可靠。 为此一方面需要通过硬件电路的可靠性来保障，另一为此一方面需要通过硬件电路的可靠性来保障，另一 方面还要在传输过程中，需对接收到的数据进行检错方面还要在传输过程中，需对接收到的数据进行检错 、纠错，以便发现和纠正数据在传输过程中产生的错、纠错，以便发现和纠正数据在传输过程中产生的错 误。误。 常用的数据校验方法有：奇偶校验、循环冗余校常用的数据校验方法有：奇偶校验、循环冗余校 验、海明码等。验、海明码等。 本节将介绍前两种校验方法。本节将介绍前两种校验方法。 4040计算机硬件技术大连理工大学计算机硬件技术大连理工大学 名词概念：名词概念： 码字：码字：由若干代码组成的一个字。由若干代码组成的一个字。 如如84218421码中码中6 6（01100110），），7 7（01110111） 码距：码距：一种码制中任意两个码字间的最小距离。一种码制中任意两个码字间的最小距离。 距离：距离：两个码字之间不同的代码个数。两个码字之间不同的代码个数。 84218421码中，最小的码距为码中，最小的码距为1 1，如，如00000000和和 00010001、00100010和和00110011等；最大码距为等；最大码距为4 4， 如如01110111和和10001000。84218421码的码距为码的码距为1 1。 码距为码距为1 1，即不能查错也不能纠错。，即不能查错也不能纠错。 码距越大，查错、纠错能力越强。码距越大，查错、纠错能力越强。 4141计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.3.1 3.3.1 奇偶校验码奇偶校验码 奇偶校验法是计算机中广泛采用的检查传输数据奇偶校验法是计算机中广泛采用的检查传输数据 准确性的方法。准确性的方法。 奇偶校验法的原理奇偶校验法的原理： 在每组数据信息上附加一个校验位，校验位的取 值（0或1）取决于这组信息中1的个数和校验 方式（奇或偶校验）。 如果采用奇校验，则这组数据加上校验码位后如果采用奇校验，则这组数据加上校验码位后 数据中数据中11的个数应的个数应为奇数个为奇数个。 如果采用偶校验，则这组数据加上校验码位后如果采用偶校验，则这组数据加上校验码位后 数据中数据中1 1的个数应的个数应为偶数个为偶数个。 4242计算机硬件技术大连理工大学计算机硬件技术大连理工大学 例如：例如：八位信息八位信息 1010101110101011中共有中共有5 5个个 11，附加校，附加校 验位后变为九位。验位后变为九位。 若采用奇校验，则附加的校验位应取若采用奇校验，则附加的校验位应取 00值，保证值，保证 1 1的个数为奇数个即的个数为奇数个即0 010101011 10101011 ； 若采用偶校验，则附加的校验位应取若采用偶校验，则附加的校验位应取 11值值, ,保证保证1 1 的个数为偶数个即的个数为偶数个即1 110101011 10101011 。 奇偶校验的特点：奇偶校验的特点： 1 1、奇偶校验法使数据的码距为、奇偶校验法使数据的码距为2 2，因而可检出，因而可检出 数据传送过程中奇数个数位出错的情况；数据传送过程中奇数个数位出错的情况； 2 2、实际中两位同时出错的概率极低，奇偶校验法简、实际中两位同时出错的概率极低，奇偶校验法简 便可靠易行，但它只能发现错误，却不知错在何处，便可靠易行，但它只能发现错误，却不知错在何处， 因而不能自动纠正。因而不能自动纠正。 4343计算机硬件技术大连理工大学计算机硬件技术大连理工大学 例如例如 一个实用的一个实用的8-Bits8-Bits数据奇偶校验与奇偶校验码形成电路，数据奇偶校验与奇偶校验码形成电路， 其中数据用其中数据用D D 7 7 D D 0 0 表示，校验位用表示，校验位用P P表示。表示。 P D7 D6 D5 D4 D3 D2 D1 D0 D偶校错 D奇校错 P偶形成 D奇形成 4444计算机硬件技术大连理工大学计算机硬件技术大连理工大学 3.3.2 3.3.2 循环冗余码（循环冗余码（CRCCRC码）码） 循环冗余校验方式：循环冗余校验方式：通过某种数学公式建立信息通过某种数学公式建立信息 位和校验位之间的约定关系位和校验位之间的约定关系能够校验传送信息能够校验传送信息 的对错，并且能自动修正错误。广泛用于通信和的对错，并且能自动修正错误。广泛用于通信和 磁介存储器中。磁介存储器中。 CRCCRC编码格式是在编码格式是在k k位信息后加位信息后加r r位检验码。位检验码。 N N-1 2 1 信息位（k位） 校验位（r位） C1 C2 . C K r 1 r 2 r i 4545计算机硬件技术大连理工大学计算机硬件技术大连理工大学 在被传输的有效数据代码之外，扩充部分校验代在被传输的有效数据代码之外，扩充部分校验代 码，扩充的部分被称为校验位；码，扩充的部分被称为校验位； 将有效数据代码和扩充校验位一起按照某种规则将有效数据代码和扩充校验位一起按照某种规则 或算法进行统一编码，形成带校验信息的数据，在数或算法进行统一编码，形成带校验信息的数据，在数 据传输时一并进行传送；据传输时一并进行传送； 当接收端收到带有校验信息的编码数据时，再利当接收端收到带有校验信息的编码数据时，再利 用约定的规则或算法进行译码（解码），如果所约定用约定的规则或算法进行译码（解码），如果所约定 的规则或算法没被破坏则表示数据传输正确，否则表的规则或算法没被破坏则表示数据传输正确，否则表 明收到的数据信息在传输过程中发生错误，然后根据明收到的数据信息在传输过程中发生错误，然后根据 被破坏后编码信息的某些特征和规则来判断，看是哪被破坏后编码信息的某些特征和规则来判断，看是哪 一位出错，再进行修正它。一位出错，再进行修正它。 冗余校验法的基本原理是：冗余校验法的基本原理是： 4646计算机硬件技术大连理工大学计算机硬件技术大连理工大学 1.1.CRCCRC码的编码方法码的编码方法 CRCCRC整个编码长度为整个编码长度为 n=k+rn=k+r 位，故位，故CRCCRC码又叫码又叫（n n，k k）码。码。 其编码方法如下：其编码方法如下： 1)1) 假设被传送的假设被传送的k k位二进制信息位用位二进制信息位用C(x)C(x)表示表示, , 系统选定的生成多项式用系统选定的生成多项式用G(X)G(X)表示；表示； 2)2) 将将C(x)C(x)左移左移G(X)G(X)的最高次幂的最高次幂( (即等于需要添