计算机逻辑运算和逻辑部.ppt

第二章 计算机中逻辑运算与逻辑器件,计算机是由数字逻辑电路组成的。 逻辑是指条件和结果之间的关系，即因果关系。因果关系是二值逻辑。 电路的输入信号作为条件，输出信号作为结果，输入输出代表一定逻辑关系。 逻辑代数是描述/分析/设计逻辑电路的数学工具。逻辑代数也叫布尔代数。 运用逻辑运算可以设计最简逻辑电路。,2.1 逻辑代数及基本运算,逻辑代数：是由逻辑变量集、常量“0”、“1”及“与”、“或”、“非”等 运算符号构成的代数系统。 逻辑变量集是指逻辑代数中所有可能的变量集合,可用任何字母表示,但变量的取值只能是1或0。 简单逻辑代数可描述任何复杂逻辑网络。,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,2）逻辑“或”运算和“或门”电路,逻辑“或”又称为逻辑加运算。 运算符号：“+”、“v”、 “OR”等。 逻辑表达式： L=A+B=AB= 或门电路符号： 逻辑真值表： 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),3）逻辑“非”运算和“非门”电路,逻辑“或”又称为逻辑反运算. 运算符号：“ ”（上加横线） 逻辑表达式为 L= = 非门电路符号： 逻辑真值表： A L 0 1 1 0,A,A,1 （A=0） 0 （A=1）,L,2、常用的组合逻辑单元,基本逻辑运算可以构成复杂逻辑关系； 基本逻辑电路也可以形成组合逻辑电路。 常见组合逻辑及其电路如下： 1）与非门 逻辑表达式： 真值表： 电路符号： A B L 0 0 1 0 1 1 1 0 1 1 1 0,A B,L,. L=AB,2）或非门 逻辑表达式：L=A+B,真值表： A B L 0 0 1 电路符号： 0 1 0 1 0 0 1 1 0 3）异或门 逻辑表达式：L=AB=AB+AB 真值表： A B L 电路符号： 0 0 0 0 1 1 1 0 1 1 1 0,L,A B, ,L,A B,逻辑表达式：L=AB=AB=AB+AB 真值表： 电路符号： A B L 0 0 1 0 1 0 1 0 0 1 1 1, ,L,A B,4）同或门,3、基本运算规律和公式,基本运算规律： 加：A+0=A，A+1=1，A+A=A，A+A=1 乘：A 0=0，A 1=A，A A=A，A A=0 非：A+A=1，A A=0，A=A 基本公式： 吸收律，分配律，交换律，结合律，反演律,1）吸收律： 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,2）分配律：,A (B+C)=AB+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,3）交换律：,A+B=B+A AB=BA 4）结合率： （A+B）+ C = A+（B+C） （A B） C = A（B C） 5）反演律： ABC=A+B+C A+B+C=A B C,2.2 逻辑函数三种表示法及关系,1、真值表： 由逻辑变量的所有可能取值的组合及其对应的逻辑函数 值所构成的表格。 例：设计三人表 决逻辑电路。得 到真值表如右： ABC为选票， F为选举结果。,NO A B C F M0 0 0 0 0 M1 0 0 1 0 M2 0 1 0 0 M3 0 1 1 1 M4 1 0 0 0 M5 1 0 1 1 M6 1 1 0 1 M7 1 1 1 1,2、逻辑表达式： 由逻辑变量、逻辑常量和运算符组成的表达式。它是逻辑变量的函数， 也是设计逻辑电路的根据。 根据真值表可以列出逻辑表达式。 方法是：把真值表中所有使函数值为1的自变量组合项“或”起来。 如此，前述三人表决真值表的逻辑表达式为： F(A,B,C)=ABC+ABC+ABC+ABC,每个逻辑表达式均可用一个逻辑电路实现。如果能够用最简单的逻辑表达式描述一个逻辑关系，就可以用最简单的电路实现之。因此，化简逻辑表达式具有十分重要的意义。 下面以三人表决逻辑为例说明化简方法：,根据化简后的逻辑表达式 F=AB+BC+AC， 可以画出相应的三人表决逻辑电路如下： 由逻辑表达式进行化简需要较强的技巧，不熟练者很难判断，而卡诺图则直观方便。,A B C,AB BC AC,F,3、卡诺图：,逻辑关系的一种图形表示形式。同时也是化简逻辑表达式的一种非常有效的方法。 卡诺图是一种直观的平面方块图。它根据输入变量的数量n将平面划分为2n 个方格，用来表示全部输入变量组合项或者表示全部输出项。 下面举例对此进行说明。,X1,二维卡诺图 输入为X1、X2，输出为 F。 左下图为真值表，右下图为卡诺图。 卡诺图的左边上边书写自变量的可能取值， 中间则表明 Mi最小项。最小项即一行真 值表中各自变量或其“非”的逻辑乘积项。,NO X1 X2 F M0 0 0 F0 M1 0 1 F1 M2 1 0 F2 M3 1 1 F3,X2,0 1,0 1,M0,M1,M2,M3,三维卡诺图 输入为X1、X2、X3，输出为 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,卡诺图简化规则,A,1 1 1 1,BC,00 01 11 10,0 1,仍以前面所述的三人表决逻辑为例。 根据真值表得到的逻辑表达式为： F(A,B,C)=ABC+ABC+ABC+ABC,BC,AC,AB,根据卡诺图化简结果：F=AB+BC+AC,NO A B C F M0 0 0 0 0 M1 0 0 1 0 M2 0 1 0 0 M3 0 1 1 1 M4 1 0 0 0 M5 1 0 1 1 M6 1 1 0 1 M7 1 1 1 1,卡诺图简化规则,若任何两个标“1”的相邻单元可以形成一个圈，就可以消去一个变量； 若任何四个标“1”的相邻单元可以形成一个圈，就可以消去两个变量； 若任何八个标“1”的相邻单元可以形成一个圈，就可以消去三个变量； 卡诺图化简的过程就是在卡诺图上找出能够覆盖给定函数全部为1的单元的个数最少同时覆盖面尽可能大的圈，然后写出其最简逻辑表达式。,AB,CD,00 01 11 10,00 01 11 10,1,1,1,1,1,1,1,1,例：试用卡诺图化简下面的逻辑表达式 。 解：根据逻辑表达式做出卡诺图如下： 根据卡诺图化简 规则，最后得到 化简后的结果：,AB,CD,00 01 11 10,1,1,1,1,00 01 11 10,1,1,1,1,例：试用卡诺图化简下面的逻辑表达式 。 解：根据逻辑表达式做出卡诺图如下： 根据卡诺图化简 规则，最后得到 化简后的结果：,2.3 逻辑代数的应用 1、逻辑代数在数据处理方面的应用 例：设X=X1X2，Y=Y1Y2是两个二进制 整数，写出判断XY的逻辑表达式。,解：输入变量 X1，X2，Y1，Y2 输出变量 F=1 (XY) F=0 (XY),X1 Y1 X2 Y2 F 1 0 X X 1 1 1 1 0 1 0 0 1 0 1,X1Y1,X2Y2,00 01 11 10,00 01 11 10,1,1,化简上述表达式，得到：,1 1 1 1,若用卡诺图化简， 也得到同样结果：,例： 1）将寄存器R中的d5位清零，其它位不变。 解：R (11011111) R 即 R= R (11011111) 2）将寄存器R中的数据全部置“1”。 解：R+(11111111 ) R 即R= R+ (11111111) 或 R R R R= R R 3）设有八位寄存器R1R2R3，试把R1中的高四 位和R2中的低四位合并成一个字节存入R3 。 解：R3 = R1 (11110000) + R2 (00001111),2、逻辑代数在电路设计方面的应用 例：设计一个一位全加器电路（包括进位位C）,根据题意列出真值表如右： 其中A为被加数，B为加数，C为低级进位信号，S i为和， C i为本级向上进位信号。 根据真值表得到逻辑表达式： S i=ABC+ABC+ABC+ABC C i=ABC+ABC+ABC+ABC,A B C S i C i 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1,现用代数法对“S i”进行化简：,i,对C i采用卡诺图 进行化简得到：,A,1 1 1 1,BC,00 01 11 10,0 1,BC,AC,AB,i,C i=ABC+ABC+ABC+ABC,根据上述结果画出的一位全加器的 逻辑电路图如下：,i,i,C i,S i,2.4 计算机中常用的逻辑部件,1、存储逻辑电路 触发器：计算机中存放一位二进制信息的基本单元器件。 触发器有两种稳定状态，分别表示0，1。其状态取决于当前输入和以前的存储状态。 常用的触发器有基本触发器、RS触发器、JK触发器、T触发器、D触发器等。 介绍两种触发器：D触发器、JK触发器,1）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为数据输入端； CLK为时钟信号； S为置位信号端； CLR复位信号端； Q为输出信号端。 D触发器功能表： 正跳变触发有效。,2）J-K触发器,J S Q CLK K CLR Q,输入 输出 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,电路符号： JK为控制输入端； CLK为时钟信号； S为置位信号端； CLR复位信号端； Q为输出信号端。,J-K触发器功能表： （负跳变触发有效）,2、寄存器,计算机中常用部件，用于暂存二进制信息。 寄存器可由多个触发器组成。每个触发器存 1Bit，N个触发器储存N位二进制数据。 下图为由4个D触发器组成的四位缓冲寄存器。,Q3 D3 CLK,X3,Q2 D2 CLK,X2,Q1 D1 CLK,X1,Q0 D0 CLK,X0,控制端,3、计数器,4、三态门,D输入端 L输出端 E使能端 当E=1时，其输出等于输入，是同相门； 当E=0时，输出与输入呈现高电阻隔离。 计算机中用做数据输出器件，当不输出数据时，可令E=0，使对总线无影响，因而多个器件可同时连到总线上。,5、译码器,译码：把某组编码翻译为唯一的输出。 译码器：有38译码器，即8选1译码器 和416译码器，即16选1译码器等多种。,例如：38译码器，即8选1译码器的输入信号有三个：C、B、A（A为低位），三位二进制数可组成8个不同数字，因此输出为Y0 Y7 8中选1。,下图分别为译码器引脚图和输入输出真值表 其中：G1、G2A、G2B为芯片选择端，G1高电 平有效，而G2A、G2B为低电平有效。,74LS138,6、数据分配器,数据有选择地送往需要的目的地 A1A0 可对数据的去向进行选择,7、数据选择器,从多路数据中有选择地进行输出 A1A0 可对数据的输出来源进行选择,8、移位寄存器,X1 X2 X3 X4,移位脉冲 CLK,串行输入信号DIN,串行输入并行输出右移位寄存器波形图,2.5 计算机中的数据校验方法,冗余校验： 即在基本的有效数据外，再扩充部分位，增加部分（冗余部分）称为校验位。将校验位与数据位一起按某种规则编码，写入存储器或向外发送，当从存储器读出或接收到外部传入的代码时，再按相应的规则进行判读。若约定的规则被破坏，则表示出现错误。从而根据错误的特征进行修正恢复。,几个名词概念： 码字：由若干代码组成的一个字。 如8421码中6（0110），7（0111） 码距：一种码制中任意两个码字间的最小距离。 距离：两个码字之间不同的代码个数。 8421码中，最小的码距为1，如0000和 0001、0010和0011等；最大码距为4， 如0111和1000。8421码的码距为1。 码距为1，即不能查错也不能纠错。 码距越大，查错、纠错能力越强。,2.5.1 奇偶校验法,奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。 奇偶校验法的原理是： 在每组数据信息上附加一个校验位，校验位的取值（0或1）取决于这组信息中1的个数和校验方式（奇或偶校验）。 如果采用奇校验，则这组数据加上校验码位后数据中1的个数应为奇数个。 如果采用偶校验，则这组数据加上校验码位后数据中1的个数应为偶数个。,例如：八位信息10101011中共有5个1，附加校验位后变为九位。若采用奇校验，则附加的校验位应取0值，保证1的个数为奇数个；若采用偶校验则附加的校验位应取1值。 奇偶校验的特点： 1、奇偶校验法使数据的码距为2，因而可检出 数据传送过程中奇数个数位出错的情况； 2、实际中两位同时出错的概率极低，奇偶校验 法简便可靠易行，但它只能发现错误，却不 知错在何处，因而不能自动纠正。,奇校验出错,偶校验 出错,偶形成,奇形成,D0 D1 D2 D3 D4 D5 D6 D7 D8,8位数据的奇偶校验码形成电路及检码电路,D0为校验位 D0,2.5.2 海明码校验方法,海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组，故其码距大于2 。 海明码校验方法能够检测出具体错误并纠正。 原理是在数据中加入k个校验位将数据的码距按照一定规则拉长。k个校验位可以表示2k个信息，除一个表示无误外，其余2k-1信息可以用来标明错误的具体位置，但由于校验位本身也可能在传送中出错，所以只有2k-1-k个信息可用，即k位校验码只可标明2k-1-k个错误信息。 例如：用4个校验位能可靠传输24-1-4=11位信息；而要校验32位数据则需至少6个校验位。,1、编码方法（以四个校验位进行说明）,四个校验位最多可以校验11位数据。设： D10D9D8D7D6D5D4D3D2D1D0为11个数据位， P4P3P2P1分别为四个校验码，则编码规则是： 海明码的总位数等于数据位与校验位之和； 每个校验位Pi排放在2i-1的位置，例如P4排放 在第24-1=8位，其余数据位依序排列。即： D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1 海明码的每一位用多个校验位一起进行校验， 被校验的位号等于校验它的各校验位位号和； 各校验位的值为它参与校验的数据位的异或。 （详细参见教材P45、P46页）,2、检查纠错（以四个校验位进行说明）,海明码数据传送到接收方后，再将各校验 位的值与它所参与校验的数据位的异或结果进 行异或运算。 运算结果称为校验和。校验和共 有四个。 对偶校验来说，如果校验和不为零则传输 过程中间有错误。而错误的具体位置则由四个 校验和依序排列后直接指明。如果四个校验和 S4S3S2S1 依序排列后等于(1001)2=(9)10 时，就 表明海明码的第九位也就是D4发生了错误，此 时只要将D4取反，也就纠正了错误。 （详细参见教材P46、P47页）,例题：采用4位校验位、偶校验方式， 写出10110100110的海明码。,解：D10D9D8D7D6D5D4D3D2D1D0=10110100110 由于被校验位的位号等于校验它的各校验位位号 之和以及各校验位的取值等于它参与校验的数据位取 值的异或。所以校验位的取值以及所求海明码为： P1=D0D1D3D4D6D8D10=1 P2=D0D2D3D5D6D9D10=1 P3=D1D2D3D7D8D9D10=1 P4=D4D5D6D7D8D9D10=0 D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=101101000111011 传送正确时校验和的值为0，如果不等于0，则是几就是 第几位出错，是7则是第7位D3出错，此时将其取反即可 纠正错误。,2.5.3 循环冗余校验方法(CRC码),循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。 CRC编码格式是在k位信息后加r位检验码。 N N-1 2 1 信息位（k位） 校验位（r位）,C1 C2 . C K r 1 r 2 r i,1、CRC码的编码方法,CRC整个编码长度为 n=k+r 位，故CRC码又叫（n，k）码。其编码方法如下： 假设被传送的k位二进制数用C(x)表示。将 C(x)左移 r = n-k 位，写作 C(x) 2 r 然后将其除以事先指定的多项式G(x)，商用Q(x)表示，余数用R(x)表示。则： 两边同时乘以G(x)并左移 R(x) 得到：,故有： 上式中，等式左边