第三章计算机中的逻辑运算与逻辑部件PPT讲稿.ppt

《第三章计算机中的逻辑运算与逻辑部件PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章计算机中的逻辑运算与逻辑部件PPT讲稿.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章计算机中的逻辑运算与逻辑部件第1页，共50页，编辑于2022年，星期二3.1 逻辑代数与基本逻辑运算 逻辑代数是逻辑代数是1847年由英国数学家乔治年由英国数学家乔治布尔（布尔（George Boole)首先创立的，所以通常人们又称逻辑代数为布尔首先创立的，所以通常人们又称逻辑代数为布尔代数。代数。逻辑代数与普通代数有着不同的概念，其所表示的不是逻辑代数与普通代数有着不同的概念，其所表示的不是数值之间的大小关系，而是逻辑函数与逻辑变量之间所数值之间的大小关系，而是逻辑函数与逻辑变量之间所存在的逻辑关系与逻辑规律。存在的逻辑关系与逻辑规律。逻辑规律表示了一种因果关系，如逻辑规律表示了一种因

2、果关系，如“真真”与与“假假”、“有有”和和“无无”、“是是”与与“非非”、“开开”与与“关关”等，这些逻辑关系的一个共同点是它等，这些逻辑关系的一个共同点是它们仅有两种状态，即：们仅有两种状态，即：0和和1，因此又称为二值逻辑。，因此又称为二值逻辑。第2页，共50页，编辑于2022年，星期二它们通常反映在逻辑电路上则是电路的它们通常反映在逻辑电路上则是电路的“通通”与与“断断”、反映在电信号上则是信号电平的反映在电信号上则是信号电平的“髙髙”与与“低低”，所以，所以把这种工作在二值（把这种工作在二值（0、1）状态下的电路称为数字逻）状态下的电路称为数字逻辑电路。逻辑代数是分析和设计数字逻辑系

3、统的数学辑电路。逻辑代数是分析和设计数字逻辑系统的数学基础，而数字逻辑电路则是构成计算机硬件核心电路基础，而数字逻辑电路则是构成计算机硬件核心电路的主要部分。的主要部分。逻辑代数是指：用逻辑代数是指：用0和和1两个基本的数字符号表示逻辑常两个基本的数字符号表示逻辑常量，用取值只能为量，用取值只能为0或或1的任何字母符号表示逻辑变量，的任何字母符号表示逻辑变量，用用“与与”、“或或”、“非非”等基本逻辑符号表示运算关系等基本逻辑符号表示运算关系所构成的代数系统。所构成的代数系统。逻辑代数的自变量取值只有逻辑代数的自变量取值只有0和和1（非（非0即即1）两个数，同）两个数，同样逻辑函数的取值也只有

4、样逻辑函数的取值也只有0和和1（非（非0即即1）两个数，自变）两个数，自变量就是逻辑变量，这种函数就是逻辑函数。量就是逻辑变量，这种函数就是逻辑函数。第3页，共50页，编辑于2022年，星期二3.1.1 基本逻辑门电路 逻辑门是描述数字逻辑电路的最基本单元部件，是计算机硬件电逻辑门是描述数字逻辑电路的最基本单元部件，是计算机硬件电路的基础；由于它的结构与逻辑函数中描述的自变量乘积项及函数逻路的基础；由于它的结构与逻辑函数中描述的自变量乘积项及函数逻辑关系相对应，所以能够实现计算机中的运算、控制、数据存储等功辑关系相对应，所以能够实现计算机中的运算、控制、数据存储等功能部件的逻辑电路描述。基本逻

5、辑门电路有能部件的逻辑电路描述。基本逻辑门电路有与门与门电路电路 或门或门电路电路和和非门非门电路。常用的逻辑门电路还有电路。常用的逻辑门电路还有与非门与非门电路电路 与或门与或门电电路路 与或非门与或非门电路电路 异或门异或门 电路电路 同或门同或门 电路电路 三态门三态门电路电路等。等。在逻辑门电路中，任何信号只存在两种状态，即高电平和低电在逻辑门电路中，任何信号只存在两种状态，即高电平和低电平；通常以高电平来表示逻辑平；通常以高电平来表示逻辑1（正逻辑）、以低电平来表示逻辑（正逻辑）、以低电平来表示逻辑0（负逻辑）。（负逻辑）。第4页，共50页，编辑于2022年，星期二(1)逻辑“与”运

6、算和“与门”电路逻辑“与”又称为逻辑“乘”运算。运算符号：“”,“”,“”,“AND”等。逻辑表达式：L=AB=B=A B=与门电路符号：与门电路：能实现逻辑与功能的数字电路单元真值表：两个输入变量的四种组合与其对应的输出变量之间的关系。A B L=AB0 0 00 1 01 0 01 1 11 (A、B均为1)0 (A、B中任一为0)ABL第5页，共50页，编辑于2022年，星期二(2)逻辑“或”运算和“或门”电路逻辑“或”又称为逻辑加运算。运算符号：“+”、“”、“OR”等。逻辑表达式：L=A+B=AB=或门电路符号：逻辑真值表：A B L=A+B0 0 00 1 11 0 11 1 1L

7、AB1 (A、B中任一为1)0 (A、B均为0)第6页，共50页，编辑于2022年，星期二(3)逻辑“非”运算和“非门”电路逻辑“非”又称为逻辑反运算.运算符号：“”（上横线）逻辑表达式为：L=非门电路符号：逻辑真值表：A L0 11 0A A1 （A=0）0 （A=1）L第7页，共50页，编辑于2022年，星期二（4）常用的组合逻辑门 在数字系统中，除了基本的“与”运算、“或”运算、“非”运算之外，为了方便逻辑关系的描述常常使用一些通过这三种基本逻辑运算关系派生出来的逻辑运算关系，这种派生出来的逻辑运算通常被称为复合运算，常见的复合运算有：与非、或非、同或及异或等。还有很多的组合逻辑门电路，

8、如：全加器、译码器、编码器、多路选择器等等第8页，共50页，编辑于2022年，星期二3.1.2 基本运算规律和公式基本运算：加：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基本公式：吸收律，分配律，交换律，结合律，反演律第9页，共50页，编辑于2022年，星期二#吸收律：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第10页，共50页，编辑于2022年，星期二#分配律：A(B+C)=A

9、B+AC (A+B)(A+C)=A+BC 证明：(A+B)(A+C)=A A+A C+B A+B C =A(1+C+B)+B C =A+B C第11页，共50页，编辑于2022年，星期二#交换律：A+B=B+A AB=BA#结合率：（A+B）+C=A+（B+C）（A B）C=A（B C）#反演律：ABC=A+B+C A+B+C=A B C 第12页，共50页，编辑于2022年，星期二3.2 逻辑函数的三种表示法1逻逻辑辑真真值值表表：将逻辑函数输入（逻辑变量）与输出（函数取值）之间的所有组态关系用数字符号以并列的形式表示出来的表格。这是一种将具体问题的描述转变为逻辑关系的描述的有效工具，也是获

10、得严谨的逻辑函数表达式的最有效方法。2逻逻辑辑函函数数表表达达式式：用与、或、非等基本的逻辑运算关系符和逻辑常量、逻辑变量所组成的表示逻辑函数的数学表达式。形式简洁明了，便于书写和推演变换，根据真值表可以列出其逻辑表达式。3卡诺图卡诺图：n个变量的函数可以由2n个方格构成的平面方格图来表示，每个方格代表逻辑函数中的一个最小项，而任何一个逻辑函数都可以表示成“最小项之和”的形式，因此通过方格阵列可清楚的反映出函数所有最小项之间的关系，这个平面方格图就是卡诺图。利用卡诺图中表示最小项的方格之间的相邻、相对、相重的位置关系进行最小项合并是进行逻辑函数化简的最直接、最有效的方法。第13页，共50页，编

11、辑于2022年，星期二321 逻辑真值表 1、真值表：由逻辑变量的所有可能取值的组合及其对应的逻辑函数值所构成的表格。例：有一个3位二进制数ABC，列出ABC中出现奇数个1的逻辑关系。解：3位二进制数ABC共有8种组合状态，分别定义为m0m7；它们的奇偶性定义为函数F，其中F0表示呈偶性，F1表示呈奇性，将ABC全部的组态关系以及对应的F取值以表格的形式表示出来。该表称为逻辑函数F的真值表。NoA B CFm00 0 00m10 0 11m20 1 01m30 1 10m41 0 01m51 0 10m61 1 00m71 1 11注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数取值

12、，不能有遗漏。注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数取值，不能有遗漏。注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数取值，不能有遗漏。注意：真值表必须列出逻辑变量所有可能的取值及其所对应的函数取值，不能有遗漏。（二个变量有（二个变量有（二个变量有（二个变量有2 22 2=4=4、三个逻辑变量有、三个逻辑变量有、三个逻辑变量有、三个逻辑变量有2 23 3=8=8、四个变量有、四个变量有、四个变量有、四个变量有2 24 41616、n n个变量有个变量有个变量有个变量有2 2n n种可能的取值种可能的取值种可能的取值种可能的取值）。）。）。）。第14页，共50页，编

13、辑于2022年，星期二3.2.2 逻辑表达式：由逻辑变量、逻辑常量和运算符组成的表达式。由逻辑变量、逻辑常量和运算符组成的表达式。它是逻辑变量的函数，也是设计逻辑电路的根据。它是逻辑变量的函数，也是设计逻辑电路的根据。根据真值表可以列出逻辑表达式。根据真值表可以列出逻辑表达式。方法是：方法是：把真值表中所有使函数值为把真值表中所有使函数值为1 1的自变量组合项的自变量组合项 “或或”起来。每一项（最小项）是逻辑变量的本身或其起来。每一项（最小项）是逻辑变量的本身或其 非的与运算。如果变量是非的与运算。如果变量是1 1取其本身；是取其本身；是0 0则取变量的则取变量的 非值非值 例如，上页例题中

14、的逻辑表达式为：例如，上页例题中的逻辑表达式为：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由于逻辑表达式进行化简需要较强的技巧，不熟练者很难判断，由于逻辑表达式进行化简需要较强的技巧，不熟练者很难判断，第15页，共50页，编辑于2022年，星期二323卡诺图（Karnaugh Map）卡诺图是逻辑函数的另一种表示形式，它是

15、一种以图形形式来表达逻辑关系的方法，也是将逻辑函数进行逻辑化简的一种最有效的手段。用卡诺图化简逻辑函数，不但具有简单、直观、方便的特点，而且还较容易的判断出得到结果是否为最简的形式。用卡诺图表示逻辑函数，是将该逻辑函数的每一个最小项取值，按照一定规则填入到所对应的平面方格矩阵内，这个平面方格矩阵图就称为卡诺图。第16页，共50页，编辑于2022年，星期二 卡诺图是一种直观的平面方块图。它根据输入变量的数量n将平面划分为2n 个方格，用来表示全部输入变量组合项或者表示全部输出项。与真值表有些相似，但是和真值表的自变量取值变化的最大不同在于：自变量的取值是按照它们取值之间的最小跳越关系进行排列，即

16、在左边和上边的自变量取值中只能有一个变量的取值是变化（相反）的，其余的保持不变。卡诺图坐标点上的自变量取值可以不连续，但要保持最小跳跃。小方格中所填写的是：根据行列坐标点上自变量的取值关系，找出在逻辑表达式中对应的最小项的位置，在相应的小方格中填写1；即小方格中填写那些使得逻辑函数在所对应的行列坐标点上取值为1的项。卡诺图的书写规则：第17页，共50页，编辑于2022年，星期二二维卡诺图 输入为X1、X2，输出为 F。左下图为真值表，右下图为卡诺图。卡诺图左边和上边书写自变量的可能取值，中间则表明 Mi最小项。最小项即一行真值表中各自变量或其“非”的逻辑乘积项。NO X1 X2 FM0 0 0

17、 F0M1 0 1 F1M2 1 0 F2M3 1 1 F3X101X20 1M0M1M2M3第18页，共50页，编辑于2022年，星期二三维卡诺图输入为X1、X2、X3，输出为 F。左下图为真值表，右下图为卡诺图。卡诺图的左边上边书写自变量的可能取值，规则是最小跳跃。中间则表明最小项。NO X1 X2 X3 FM0 0 0 0 F0M1 0 0 1 F1M2 0 1 0 F2M3 0 1 1 F3M4 1 0 0 F4M5 1 0 1 F5M6 1 1 0 F6M7 1 1 1 F7 M0 M1 M2 M3 M6 M7 M4 M5X1X2X30 100 011110第19页，共50页，编辑于

18、2022年，星期二 CDAB0001111000M0M1M3M201M4M5M7M611M12M13M15M1410M8M9M11M10四维卡诺图输入为A、B、C、D，输出为F。卡诺图的左边上边书写自变量的可能取值，规则是最小跳跃。中间则表明最小项。第20页，共50页，编辑于2022年，星期二请用卡诺图表示下列函数1、F(A,B,C)=ABC+ABC+ABC+ABC CAB01000111111101第21页，共50页，编辑于2022年，星期二卡诺图的化简规则若任何两个标“1”的相邻单元可以形成一个圈，就可以消去一个变量；若任何四个标“1”的相邻单元可以形成一个圈，就可以消去两个变量；若任何八

19、个标“1”的相邻单元可以形成一个圈，就可以消去三个变量；卡诺图化简的过程就是在卡诺图上找出能够覆盖给定函数全部为1的单元的个数最少同时覆盖面尽可能大的圈，然后写出其最简逻辑表达式。需要注意的是，由于卡诺图的最上行、最下行和最左列、最右列以及4个顶点上所对应的小方格在逻辑关系上也是彼此相邻的，圈最小项时也属于相邻关系。第22页，共50页，编辑于2022年，星期二ABCD 00 01 11 100001111011111111例：试用卡诺图化简下面的逻辑表达式。解：根据逻辑表达式做出卡诺图如下：根据卡诺图化简 规则，最后得到 化简后的结果：第23页，共50页，编辑于2022年，星期二ABCD 00

20、 01 11 1011111111例：试用卡诺图化简下面的逻辑表达式。解：根据逻辑表达式做出卡诺图如下：根据卡诺图化简 规则，最后得到 化简后的结果：00011110第24页，共50页，编辑于2022年，星期二3.3 逻辑代数的应用举例3.3.1 数据处理方面的应用例3-3 将寄存器R中的d5位清零，其他位不变。解：利用与运算的特点，对寄存器中的内容按位相“与”，即 第25页，共50页，编辑于2022年，星期二例3-4 将寄存器R中的数据都置为“1”。解：利用或运算的特点，对寄存器中的内容按位相“或”，即 例3-5 设有寄存器R1R2，要求把R1的高4位和R2的低四位拼成一个字节送给寄存器R3

21、。解：可以综合利用与运算和或运算的特点，先分别对R1和R2进行与运算，然后再按位相或。第26页，共50页，编辑于2022年，星期二3.3.2 半加器和全加器 计算机的一个主要功能就是进行数字信息处理，处理中一项很重要的工作就是进行数值的算数运算，通过上一章的介绍我们已经有了一个概念，计算机首先是将各种要处理的数值信息转变成机内的二进制形式进行表示，其中基本的算术运算（加、减、乘、除），都可以以补码的形式通过加法来完成。所以加法器是计算机系统中最基本的也是最重要的部件。由于二进制运算可以用逻辑运算来表示，因此可以用逻辑设计的方法来设计加法运算电路。加法器分为半加器和全加器。第27页，共50页，编

22、辑于2022年，星期二（1）一位半加器设计）一位半加器设计 由于半加器不需要考虑低位向本位产生的进位，因此它只有两个输入端和两个输出端。设加数与被加数（输入端）为A、B；和为S（输出端）、本位产生的向高位进位为Ci（输出端）；它们的取值关系用下列真值表来表示。ABSC0011010101100001ABSCS=AB+AB=AB，Ci=AB第28页，共50页，编辑于2022年，星期二（2）一位全加器的设计 由由于于全全加加器器考考虑虑了了低低位位向向本本位位产产生生的的进进位位关关系系，所所以以它它有有三三个个输输入入端端和和两两个个输输出出端端。设设输输入入变变量量为为：A（被被加加数数）、B

23、（加加数数）、Ci-1（低低位位进进位位），输输出出变变量量为为：和和S、本本位位向向高高位位的的进进位位Ci+1，它它们们的的取取值值关关系系用用下下列列真值表表示。真值表表示。ABCi-1SCi+10000000110010100110110010101011100111111Ci-1CiSABS=ABCi-1+ABCi-1+ABCi-1+ABCi-1 =ABCi-1Ci+1=ABCi-1+ABCi-1+ABCi-1+ABCi-1 =(AB)Ci-1+AB第29页，共50页，编辑于2022年，星期二3.4 计算机中常用的逻辑部件3.4.1 基本存储逻辑电路计算机信息的存储一般是采用两种方式

24、实现的一种是将信息记录在磁性介质上（如磁盘、磁带等）；另一种是采用电子元器件存储信息计算机内部有许多寄存器，其保存一位信息的基本单元器件是触发器，它有两种稳定状态，分别代表数字信号“0”和“1”其状态取决于当前输入和以前的存储状态(时序逻辑电路)。第30页，共50页，编辑于2022年，星期二(1)D触发器D S QCLK CLR Q输入 输出S CLR CLK D Q0 0 1 10 0 0 01 0 X X 10 1 X X 0 电路符号：D为数据输入端；CLK为时钟信号；S为置位信号端；CLR复位信号端；Q为输出信号端。D触发器功能表：正跳变触发有效。第31页，共50页，编辑于2022年，

25、星期二(2)J-K触发器输入 输出S CLR CLK J K Q0 0 0 0 不变0 0 1 0 10 0 0 1 00 0 1 1 翻转0 1 X X X 01 0 X X X 1电路符号：J、K为控制输入端；CLK为时钟信号；S为置位信号端；CLR复位信号端；Q为输出信号端。J-K触发器功能表：（负跳变触发有效）J S QCLKK CLR Q 第32页，共50页，编辑于2022年，星期二3.4.2 寄存器计算机中常用部件，用于暂存二进制信息。寄存器可由多个触发器组成。每个触发器存1Bit，N个触发器储存N位二进制数据。下图为由4个D触发器组成的四位缓冲寄存器。Q3D3 CLKX3 Q2D

26、2 CLKX2 Q1D1 CLKX1 Q0D0 CLKX0控制端寄存器通常可以用来作为数据缓存的缓冲寄存器和进行移位操作的移位寄存器。见书上详细介绍。第33页，共50页，编辑于2022年，星期二3.4.3 计数器 计数器也是一种由若干个触发器组成的寄存器，它的功能是能够在外部计数脉冲的作用下，将存储在触发器中的数字加1。在计算机中，计数器可被用来对取出的指令进行计数，以保证能准确地取出后续指令。计数器也分很多种，有脉冲计数器、同步计数器、程序计数器等。在此仅介绍一种最基本的四位二进制脉冲计数器，电路原理如下页图。第34页，共50页，编辑于2022年，星期二四级二进制并行计数器 J Q CLK

27、K CLR J Q CLK K CLR Q0 Q1 Q2 Q3 清0端控制端计数端 J Q CLK K CLR J Q CLK K CLR CLKQ0Q1Q2Q31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16第35页，共50页，编辑于2022年，星期二3.4.4 三态门D输入端L输出端E使能端当E=1时，其输出等于输入，是同相门；当E=0时，输出与输入呈现高电阻隔离。计算机中用做数据输出器件，当不输出数据时，可令E=0，使对总线无影响，因而多个器件可同时连到总线上。DEL第36页，共50页，编辑于2022年，星期二3.4.5 译码器 译码：把某组编码翻译为唯一的输

28、出。译码器：有38译码器，即8选1译码器 和416译码器，即16选1译码器等多种。例如：38译码器，即8选1译码器的输入信号有三个：C、B、A（A为低位），三位二进制数可 组成8个不同数字，因此可分别选中输出 Y0 到Y7的某一个输出故称为 8选1译码器。第37页，共50页，编辑于2022年，星期二Y0Y1Y2Y3Y4Y5Y6Y7G1G2AG2BCBA下图分别为译码器引脚图和输入输出真值表其中：G1、G2A、G2B为芯片选择端，G1高电平有效，而G2A、G2B为低电平有效。输 入 输 出C B A Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y00000111100110011010101011

29、11111101111110111111011111101111110111111011111101111110111111174LS138第38页，共50页，编辑于2022年，星期二 3.5 计算机中的数据校验方法 计算机中各部件与各部件之间经常需要进行大量的数据存取、传送操作，并且要求传输准确、可靠。为此一方面需要通过硬件电路的可靠性来保障，另一方面还要在传输过程中，需对接收到的数据进行检错、纠错，以便发现和纠正数据在传输过程中产生的错误。常用的数据较验方法有：奇偶检验、循环冗余较验、海明码等。本节将介绍前两种交验方法。第39页，共50页，编辑于2022年，星期二 在被传输的有效数据代码之

30、外，扩充部分校验代码，扩充的部分被称为校验位；将有效数据代码和扩充校验位一起按照某种规则或算法进行统一编码，形成带校验信息的数据，在数据传输时一并进行传送；当接收端收到带有校验信息的编码数据时，再利用约定的规则或算法进行译码（解码），如果所约定的规则或算法没被破坏则表示数据传输正确，否则表明收到的数据信息在传输过程中发生错误，然后根据被破坏后编码信息的某些特征和规则来判断，看是哪一位出错，再进行修正它。冗余校验法的基本原理是：第40页，共50页，编辑于2022年，星期二几个名词概念：码字：由若干代码组成的一个字。如8421码中6（0110），7（0111）码距：一种码制中任意两个码字间的最小距

31、离。距离：两个码字之间不同的代码个数。8421码中，最小的码距为1，如0000和 0001、0010和0011等；最大码距为4，如0111和1000。8421码的码距为1。码距为1，即不能查错也不能纠错。码距越大，查错、纠错能力越强。第41页，共50页，编辑于2022年，星期二3.5.1 奇偶校验码 奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是：在每组数据信息上附加一个校验位，校验位的取值（0或1）取决于这组信息中1的个数和校验方式（奇或偶校验）。如果采用奇校验，则这组数据加上校验码位后数据中1的个数应为奇数个。如果采用偶校验，则这组数据加上校验码位后数据中1的个

32、数应为偶数个。第42页，共50页，编辑于2022年，星期二例如：八位信息10101011中共有5个1，附加校验位后变为九位。若采用奇校验，则附加的校验位应取0值，保证1的个数为奇数个即010101011；若采用偶校验则附加的校验位应取1值,即110101011。奇偶校验的特点：1、奇偶校验法使数据的码距为2，因而可检出 数据传送过程中奇数个数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。第43页，共50页，编辑于2022年，星期二例如 一个实用的8-Bits数据奇偶校验与奇偶校验码形成电路，其中数据用D7D0表示，校

33、验位用P表示。PD7D6D5D4D3D2D1D0P奇形成P偶形成P奇校错P偶校错第44页，共50页，编辑于2022年，星期二3.5.2 循环冗余码（CRC码）循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在k位信息后加r位检验码。N N-1 2 1 信息位（k位）校验位（r位）C1 C2 .C K r 1 r 2 r i 第45页，共50页，编辑于2022年，星期二1、CRC码的编码方法 CRC整个编码长度为 n=k+r 位，故CRC码又叫（n，k）码。其编码方法如下：假设被传送的k位二

34、进制信息位用C(x)表示,系统选定的生成多项式用G(X)表示，将C(x)左移G(X)的最高次幂(即等于需要添加的校验位的位数r)，写作:C(x)2r r 然后将其C(x)2r r除以生成多项式G(x)，所得商用Q(x)表示，余数用R(x)表示。则：两边同时乘以G(x)并左移 R(x)得到：第46页，共50页，编辑于2022年，星期二故有：上式中，等式左边即为所求的n位CRC码，其中余数表达式R(x)就是校验位(r位)。且等式两边都是G(x)的倍数。发送信息时将等式左边生成的n位CRC码送给对方。当接收方接到n位编码后，同样除以G(x).如果传输正确则余数为0，否则则可以根据余数的数值确定是哪位

35、数据出错。由于CRC编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为：第47页，共50页，编辑于2022年，星期二例：有一个（7,4）码（即CRC码为7位，信息码为4位），已确定生成多项式为：G（X）=X3+X+1=1011被传输的信息C(x)=1001，求C(x)的CRC码。解：C（x）左移 r=nk=3位 即：将上式模2(无进/借位),除以给定的 G(x)=1011：1001000/1011=1010+110/1011 得到余数表达式：R(x)=110 所求CRC码为：第48页，共50页，编辑于2022年，星期二 2、CRC码的查错与纠错 收到的CRC码除以约定的生成多项式G(x)，如果余数为0则传输无误，否则传输错误，根据所得余数值就可找出错误并取反纠正。上表详细说明了CRC码1001110在传送时某一位出错后的判断与纠正方法 C(X)=1001、G(x)=1011。第49页，共50页，编辑于2022年，星期二 3、生成多项式G（x）的确定 G(x)是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：任何一位发生错误都应使余数不为0不同位发生错误应使余数不同余数继续做模2除，应使余数循环第50页，共50页，编辑于2022年，星期二