计算机组成原理第3章运算方法和运算部件(3-6-7)课件.ppt

计算机组成与结构计算机组成与结构本科生课程教学本科生课程教学计算机学院计算机组成与结构q本课程主要讲授计算机系统的硬件和软件构成方法，包括硬件系统中运算器、控制器、存储器、输入设备和输出设备和总线系统的构成原理等；并与当代先进的计算机技术相结合。是计算机科学与技术本科专业核心课程。q本课程着重计算机系统组成与结构方面的教学和研究。本课程着重计算机系统组成与结构方面的教学和研究。计算机结构定义为系统程序员所能见到的计算机硬件特性；计算机组成是指计算机硬件的具体实现。计算机学院第三章 运算方法和运算部件 q数据的表示方法和转换q带符号数的表示方法及加减运算q二进制乘法运算q二进制除法运算q浮点数的运算方法q运算部件运算部件q数据校验码数据校验码计算机学院3.6 运算部件一、运算部件一、运算部件q定点运算部件定点运算部件由算术逻辑运算部件由算术逻辑运算部件ALUALU、若干个寄存器、若干个寄存器、移位电路、计数器、门电路等组成。移位电路、计数器、门电路等组成。q运算器部件是计算机中进行数据加工的部件，其主要功能运算器部件是计算机中进行数据加工的部件，其主要功能包括：包括：q1.1.执行数值数据的算术加减乘除等运算，执行逻辑数据执行数值数据的算术加减乘除等运算，执行逻辑数据的与或非等逻辑运算，由一个被称为的与或非等逻辑运算，由一个被称为 ALU ALU 的线路完成。的线路完成。q2.2.暂时存放参加运算的数据和中间结果，由多个通用寄暂时存放参加运算的数据和中间结果，由多个通用寄存器来承担。存器来承担。q3.3.运算器通常也是数据传输的通路运算器通常也是数据传输的通路计算机学院3.6 运算部件q书书P95P95，图图3.93.9所所示示是是一一个个能能实实现现定定点点加加、减减、乘乘、除除运运算算的运算部件。的运算部件。q1 1在在进进行行加加法法运运算算时时，应应送送来来AALUAALU、BALUBALU、ALUSALUS、SASA信信号号(高高电电位位)，另另外外还还应应向向ALUALU发发出出加加法法运运算算命命令令(图中未画出图中未画出)。q2 2在在进进行行减减法法运运算算时时，应应送送来来AALUAALU、B BALUALU、1 1、ALUSALUS、SASA信信号号(高高电电位位)，同同样样还还应应向向ALUALU发发出出减减法法运运算命令。算命令。q3 3乘法运算的实现见前面的流程图。乘法运算的实现见前面的流程图。q4 4除法运算的实现见前面的流程图。除法运算的实现见前面的流程图。计算机学院计算机学院3.6 运算部件q浮点运算部件浮点运算部件q通通常常由由阶阶码码运运算算部部件件和和尾尾数数运运算算部部件件组组成成，其其各各自自的的结结构构与与定定点点运运算算部部件件相相似似。但但阶阶码码部部分分仅仅执执行行加加减减法法运运算算。其其尾尾数数部部分分则则执执行行加加减减乘乘除除运运算算，左左规规时时有有时时需需要要左左移移多多位位。为加速移位过程，有的机器设置了可移动多位的电路。为加速移位过程，有的机器设置了可移动多位的电路。qP103 P103 习题习题 3.253.25、3.273.27计算机学院3.6 运算部件二、运算部件二、运算部件AM2901A1、AM2901A逻辑结构及原理图逻辑结构及原理图计算机学院3.6 运算部件q基本组成部件有：q八功能的ALU：完成算术与逻辑运算；q164位寄存器组：寄存加减运算的操作数；q4位Q寄存器：用于接收ALU的输出数据，具有左、右移功能；q3选1和2选1多路开关：用于多路地址、数据的选择。q下图是AM2901A的逻辑原理图。计算机学院3.6 运算部件计算机学院3.6 运算部件2、AM2901A主要特点主要特点q位片式结构，即每片内仅有四位线路，要实现不同位数的运算器，需将几片同样的器件串接起来使用。例如用四片可实现个16位字长的运算器。q该运算器的ALU能实现八种运算功能，它每一位上的两个输入端数据分别用R和S表示，则这八种功能是：三种算术运算功能：五种逻辑运算功能：计算机学院3.6 运算部件q这八种功能的选择控制，是用外部送入的三位编码值I5I4I3实现的，其具体规定如下表所示。ALU的功能选择 ALU的输入选择计算机学院3.6 运算部件qALU的R输入端可以接收外部送入运算器的数据D,寄存器组的组输出A，或接收逻辑0值。ALU的S输入端可以接收寄存器组的一组输出A和另组输出B，还可以接收Q寄存器的输出。这样,R和S接收的数据可以有如下12种组合情况：q R 0000 AAAA DDDDq S ABQ0 ABQ0 ABQ0q 考虑到R和S同时接收0无实用价值，OA与AO组合、AA和AB组合、DA和DB组合可以相互替代,故只需留下八种组合情况即可、此时可用外部送来的三位控制码来决定ALU的输入数据，即区分可用的八种组合。对应关系如上表所示。计算机学院3.6 运算部件q运算器中有1个16X4位的通用寄存器组和一个4位的Q寄存器。寄存器组被设计成能双端口输出的部件。每一个寄存器都可以用A地址或B地址选择，将寄存器中的内容分别送到输出端口A或B)。当A和B地址不同时，在输出端口A和B将得到两个不同寄存器中的内容。该寄存器组的写入控制，只能用B地址实现，写入的数据是ALU的输出经过移位器送到寄存器组的输入端的。移位器可执行直送、左移一位操作，或右移一位的操作，使加减运算和移位操作可在同一个操作步骤中完成。qQ寄存器本身具有移位功能，即它可以接收自己左移一位或右移一位的值。Q寄存器 还可以接收ALU的输出F的值。Q的输出可在经ALU的S输入端送入ALU。计算机学院3.6 运算部件qALU还给出了Cn+4、F3(可用作符号位)、OVR和F=0000四个状态信息，它们分别是本四位运算器产生的向更高位的进位、本片最高位的取值、结果溢出和结果为零的状态。ALU的最低位还接收从更低位片送来的进位信号Cn，ALU还给出了超前进位信号G和P。q移位器还有接收与送出移位数值的引线，它们分别是RAM3、RAM0、Q3和Q0，它们都是用三态门给出的具有双向传送功能的线路实现的。计算机学院3.6 运算部件q运算器的四位输出为Y3一Y0，它可以是ALU的运算结果，也可以是寄存器组A输出端口上的内容。这里用的是三态门电路，仅当OE#信号为低电平时，y的值才是可用的，否则Y输出处于高阻状态。q控制数据传送的方式(移不移位)和数据发送的去向，是用另外三位编码(I8I7I6)来控制的，具体规定如下表所示。计算机学院3.6 运算部件数据传输控制计算机学院3.6 运算部件3、16位字长定点运算器位字长定点运算器q可以用四片Am2901A组成一个16位字长的定点运算器，其连接关系如下图所示。计算机学院3.6 运算部件线路工作原理：线路工作原理：q每片器件上的Q0和Q3端，RAM0与RAM3端都能用于输入和输出，因此，它们用三态门电路实现，在ALU的移位控制信号(由数据传送控制的三位编码I8I7I6给出)控制下，把高位片的Q0、RAM0输出信号送入低位邻片的Q3、RAM3输入端，或把低位片的Q3、RAM3输出信号送入高位片的Q0、RAM0输入端。q四片的数据输入端D3-D0一起作为16位运算器的16个数据输入端D15D0，四片的数据输出端Y3-Y0一起作为16位运算器的16个数据输出端Y15-Y0。计算机学院3.6 运算部件q四片的三组输入信号I2 I1-I0，I5 I4 I3，I8 I7 I6，分别用外部送来的三组信号提供给每片,使四片总使用相同的控制信号，保证它们的并行工作关系(片间有串行数据信号传送)。q 通用寄存器组RAM的两个地址控制端“A”(读)和“B”(读写)、Q寄存器移位用的CP时钟脉冲信号，分别送入每片Am2901A的“A”、“B”和CP输入端。计算机学院3.6 运算部件指令控制过程：指令控制过程：q下述几条指令在运算器部件中的控制方法：q(1)把主存数据寄存器中读得的数据写入通用寄存器组中的某个寄存器中；q(2)把通用寄存器组中某个寄存器的内容写进主存数据寄存器中；q(3)通用寄存器组中的两个寄存器的内容相加。结果写回其中的一个寄存器中。计算机学院3.6 运算部件q按Am2901A的功能规定，可以给出如下表所示的一张信号分配表。计算机学院3.6 运算部件q第一条指令，把主存数据寄存器的输出接到Am2901A的D输入端：用I2I1I0 111作为ALU的输入数据选择(D，0组合)，用I5I4I3 000作为ALU的功能选择(加，即实现D十0)，用I8I7I6011作为ALU的数据传送控制，即把ALU的输出送到通用寄存器组的输入，再写入由“B”地址选择的寄存器中。在此操作过程中，最低位进位输入值给0。计算机学院3.6 运算部件q第二条指令，把通用寄存器中的内容写入主存数据寄存器中：用I2I1I0 011作为ALU的输入选择(0，B组合)，用I5I4I3 000作为ALU的功能选择(加，即实现0+B号寄存器的内容)，用I8I7I6 001作为Am2901A的输出选择并同时给出面信号，Y输出即为B寄存器的内容，可以把Y接到主存数据寄存器的输入端，从而完成向该寄存器的写入操作。计算机学院3.6 运算部件q第三条指令，把A寄存器的内容加上B寄存器的内容，结果写入B寄存器中：用I2I1I0 001作为ALU的输入数据选择，用I5I4I3 000作为ALU的功能选择，用I8I7I6 010作为ALU的数据传送选择，从而完成A寄存器的内容加B寄存器的内容，并把结果写入B寄存器中的操作过程。此时要使OE#取高电平，使输出Y处于高阻状态，而不是输出A寄存器的内容。计算机学院3.6 运算部件q这三条指令的运行结果，应按某种规定设置运算器的状态标志触发器C、y、Z、N，这些触发器要在Am2901A芯片之外实现，将Am2901A的最高位芯片的输出Cn+4、OVR、F0000和F3的值写入这四个标志触发器中。图上省略了这一部分逻辑电路。计算机学院3.6 运算部件计算机学院q提高数据传送的正确性：提高数据传送的正确性：q（1 1）提高计算机硬件的可靠性；）提高计算机硬件的可靠性；q（2 2）在数据编码上找出路，即采用某种编码法，）在数据编码上找出路，即采用某种编码法，通过少量的附加电路，使之能发现某些错误，甚通过少量的附加电路，使之能发现某些错误，甚至能确定出错位置，进而实现自动改错的能力。至能确定出错位置，进而实现自动改错的能力。3.7 数据校验码计算机学院3.7 数据校验码q码距是根据任意两个合法码之间至少有几个二进制位不相同而确定的，仅有一位不同，称其码距为1。例如，用四位二进制表示16种状态，则16种编码都用到了，此时码距为1，就是说，任何一个状态的四位码中的一位或几位出错，就变成另一个合法码，此时无查错能力。若用四个二进制位表示8个状态，就可以只用其中的8种编码，而把另8种编码作为非法编码，此时码距为2。计算机学院3.7 数据校验码一、奇偶校验码一、奇偶校验码q奇偶校验码的原理是在每组代码中增加一个冗余位，使合法编码的最小码距由1增加到2。1、校验码的构成规则校验码的构成规则q偶校验：每个码字(包括校验位)中1的数目为偶数。q奇校验：每个码字(包括校验位)中1的数目为奇数。计算机学院3.7 数据校验码2、校验位的形成校验位的形成q 设有效信息位为：q偶校验，在发送端求校验位：q奇校验，在发送端求校验位：计算机学院3.7 数据校验码(3)校验原理校验原理q偶校验在接收端求：q奇校验在接收端求：q若P=0，则无错；P=1，则有错。计算机学院3.7 数据校验码计算机学院3.7 数据校验码4、局限性、局限性q奇奇偶偶校校验验码码能能发发现现数数据据代代码码中中奇奇数数个个位位出出错错情情况况，并并且且不不能能纠纠正错误，常用于对存储器数据的检查或者传输数据的检查。正错误，常用于对存储器数据的检查或者传输数据的检查。q下面给出对几个字节值的奇偶校验的编码结果：下面给出对几个字节值的奇偶校验的编码结果：q 数据数据 奇校验的编码奇校验的编码 偶校码的编码偶校码的编码q 00000000 l00000000 00000000000000000 l00000000 000000000q 010l0l00 0010l0100 l01010l00 010l0l00 0010l0100 l01010l00q 01ll1lll 0011l1111 10l111l1l 01ll1lll 0011l1111 10l111l1lq其中，最高一位为校验位，其余低八位为数据位。从中可以看其中，最高一位为校验位，其余低八位为数据位。从中可以看到，校验位的值取。还是到，校验位的值取。还是1 1，是由数据位中，是由数据位中1 1的个数决定的。的个数决定的。计算机学院3.7 数据校验码二、海明校验码二、海明校验码q海明校验的基本思想是将有效信息按某种规律分成若干组，每组安排一个校验位进行奇偶测试。在一个数据位组中加入几个校验位，增加数据代码间的码距，当某一位发生变化时会引起校验结果发生变化，不同代码位上的错误会得出不同的校验结果。因此，海明码能检测出2位错误,并能纠正1位错误。q海明校验实质上是一种多重奇偶校验。海明校验实质上是一种多重奇偶校验。计算机学院3.7 数据校验码(1)求海明校验码的步骤。q 确定海明校验位的位数 设K为有效信息的位数，设r为校验位的位数，则整个码字 的位数N应满足不等式：N=Kr2r1若要求海明码能检测出2位错误，则再增加一位校验位。q 确定校验位的位置：位号(1N)为2的权值的那些位，即：20、21、22、2r1 的位置作为校验位，记作P1、P2、Pr，余下的为有效信息位。q 分组:将N位分r组，第i位由校验位号之和等于i的那些校验位所校验。即即被被校校验验的的每每一一位位位位号号要要等等于于校校验验它它的的各各校校验验位位的的位位号号之之和和。这这样样安安排排的的目目的的，是是希希望望校校验验的的结果能正确反映出出错位的位号。结果能正确反映出出错位的位号。计算机学院3.7 3.7 数据校验码数据校验码q例：按上述规律讨论一个字节的海明码。例：按上述规律讨论一个字节的海明码。q每个字节由每个字节由8 8个二进制位组成，此处的个二进制位组成，此处的k k为为8 8，求出校验位的位数，求出校验位的位数r r应为应为5 5（可发现两位错），故海明码的总位数为（可发现两位错），故海明码的总位数为1313，可表示为，可表示为q H H1313H H1212H H1111H H1010H H9 9H H8 8H H7 7H H6 6H H5 5H H4 4H H3 3H H2 2H H1 1q5 5个校验位个校验位P P5 5P P1 1对应的海明码位号应分别为对应的海明码位号应分别为H H1313,H,H8 8,H,H4 4,H,H2 2,H,H1 1。P P5 5只能放在只能放在H H1313一位上，它已经是海明码的最高位了，其他一位上，它已经是海明码的最高位了，其他4 4位满位满足足P Pi i的位号等于的位号等于2 2i-1i-1的关系。其余为数据位的关系。其余为数据位D Di i，则有如下排列关，则有如下排列关系：系：q P P5 5D D8 8D D7 7D D6 6D D5 5P P4 4D D4 4D D3 3D D2 2P P3 3D Dl lP P2 2P P1 1q按前面讲的，每个海明码的位号，要等于参与校验它的几个校按前面讲的，每个海明码的位号，要等于参与校验它的几个校验位的位号之和的关系，可以给出如表验位的位号之和的关系，可以给出如表3 39 9所示的结果。所示的结果。计算机学院3.7 3.7 数据校验码数据校验码q从表中可看出：从表中可看出：5 5个校验位各自个校验位各自只与本身有关，而且校验着它只与本身有关，而且校验着它以后的一些确定位置上的有效以后的一些确定位置上的有效信息。信息。q校验位的取值仍采用奇偶校验校验位的取值仍采用奇偶校验方式确定。方式确定。q从表中可以进一步找出从表中可以进一步找出5 5个校验个校验位各自与哪些数据位有关。位各自与哪些数据位有关。校验位序号校验位序号被校验位位号被校验位位号1（P1）1、3、5、7、9、112（P2）2、3、6、7、10、114（P3）4、5、6、7、128（P4）8、9、10、11、1213（P5）13计算机学院3.7 数据校验码q校验位的形成P1=第一组中的所有位(除P1外)求异或 P2=第二组中的所有位(除P2外)求异或 Pr=第r组中的所有位(除Pr外)求异或q为了能检测两个错误，增加一位校验Pr1，放在最高位。Pr1=所有位(包括P1、P2、Pr)共N位求异或计算机学院3.7 数据校验码(2)校验原理：在接收端分别求S1、S2、S3、SrS1=第一组中的所有位(包括P1)求异或 S2=第二组中的所有位(包括P2)求异或 Sr=第r组中的所有位(包括Pr)求异或 Sr1=Pr1所有位(包括P1、P2、Pr)求异或q当Sr1=1时有一位错：由SrS3S2S1的二进制编码指出出错位号,将其取反，即可纠错。q当Sr1=0时无错或有偶数个错(两个错的可能性比较大):当SrS3S2S1=0000时，接收的数无错，否则有两个错。q根据此原理，能画出指出两个错误并能纠正一位出错位的海明校验逻辑电路。图图311是是H=12，数据位，数据位k=8，校验位，校验位r=4的海明校验线路，记作的海明校验线路，记作(12，8)分组码。分组码。计算机学院3.7 数据校验码q例求信息码01101110的海明校验码，画出能指出和纠正一位出错位的海明校验逻辑电路。【例题分析】【例题分析】q确定海明校验位的位数q设R为校验位的位数，则整个码字的位数应满足不等式：N=KR2R1q设R=3，则231=7，N=83=11，不等式不满足；q设R=4，则241=15，N=83=12，不等式满足。所以R最小取4。q确定校验位的位置：位号(112)为2的权值的那些位，即：20、21、22、23 的位置作为校验位，记作P1、P2、P3、P4，余下的为有效信息位。即：计算机学院3.7 数据校验码q121110987654321qD7D6D5D4P4D3D2D1P3D0P2P1qq分组：有4个校验位，将12位分4组，第i位由校验位号之和等于i的那些校验位所校验。q如：第11位D6由P1(位号为1)、P2(位号为2)、P4(位号为8)所校验，因为128=11。计算机学院3.7 数据校验码计算机学院3.7 数据校验码q校验位的形成P1=第 一 组 中 的 所 有 位(除 P1外)求 异 或=D6D4D3D1D0=10110=1 P2=第 二 组 中 的 所 有 位(除 P2外)求 异 或=D6D5D3D2D0=11110=0 P3=第三组中的所有位(除P3外)求异或=D7D3D2D1=0111=1 P4=第四组中的所有位(除P4外)求异或=D7D6D5D4=0110=0计算机学院3.7 数据校验码q为了能检测两个错误，增加一位校验P5，放在最高位。P5=D7D6D5D4D3D20 D1D0P1P2P3P4 =011011101010=1q【例题答案】例题答案】信息码01101110的海明校验码为：q1 1 0110 0110 1 1 111 111 0 0 0 0 1010计算机学院3.7 数据校验码q(2)校验原理在接收端分别求S1、S2、S3、S4、S5。S1=P1D6D4D3D1D0 S2=P2D6D5D3D2D0 S3=P3D7D3D2D1 S4=P4D7D6D5D4 S5=P5D7D6D5D4D3D2D1D0P1P2P3P4计算机学院3.7 数据校验码q当S5=1时有一位错：由S4S3S2S1的二进制编码指出出错位号。例如S4S3S2S1=1001说明第9位出错，将其取反，即可纠错。q当S5=0时无错或有偶数个错(两个错的可能性比较大)：当S4S3S2S1=0000时，接收的数无错，否则有两个错。q【例题答案】【例题答案】能指出两个错误并能纠正一位出错位的海明校验逻辑电路如图所示。计算机学院3.7 数据校验码计算机学院3.7 数据校验码q习题：有一个（7，4）码，写出代码0011的海明校验码，画出校验电路q解答：(1)求信息码求信息码001的海明校验码。的海明校验码。确定海明效验位的位数 因为是（7，4）码，所以N=7，K=4，效验位的位数为3。确定效验位的位置：位号（17）为2的权值的那些位，即：20、21、22 的位置作为效验位，即：1 2 3 4 5 6 7 P1 P2 D0 P3 D1 D2 D3计算机学院3.7 数据校验码q分组：分组：计算机学院3.7 数据校验码q效验位的形成 P1=D3D1D0=011=0 P2=D3D2D0=001=1 P3=D3D2D1=001=1q所以：信息码0011的海明效验码为：001 1 1 1 1010。(2)海明校验逻辑电路如图所示。计算机学院3.7 数据校验码计算机学院3.7 数据校验码三、循环冗余校验三、循环冗余校验(CRC)CRC)码码q二进制信息沿一条线逐位在部件之间或计算机之间传送称为串行传送。CRC(Cyclic Redundancy Check)码可以发现并纠正信息存储或传送过程中连续出现的多位错误。因此在磁介质存储和计算机之间通信方面得到广泛应用。qCRC码一般是指k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位(编码)，以及如何从k+r位信息码判断是否出错。下面仅就CRC码应用中的问题做简单介绍。计算机学院3.7 数据校验码(1)CRC码的编码码的编码q模2运算模2运算是指以按位模2相加为基础的四则运算，运算时不考虑进位和借位。q模模2加加减减：即按位加，可用异或逻辑实现。模2加与模2减的结果相同，即000，011，101，110。q模模2乘乘:按模2加求部分积之和。q模模2除除:按模2减求部分余数。上商的原则是：当部分余数的首位为1时，商取l；当部分余数的首位为0时，商取0。当部分的余数的位数小于除数的位数时，该余数即为最后余数。计算机学院3.7 数据校验码 CRCCRC码的编码方法码的编码方法q首先，可将待编码的是位有效信息位组表达为多项式首先，可将待编码的是位有效信息位组表达为多项式M(x)M(x)qM(x)=CM(x)=Ck-1k-1x xk-1k-1+C+Ck-2k-2x xk-2k-2+.+C+.+Ci ix xi i+C+C1 1x+Cx+C0 0q式中式中C Ci i为为0 0或或1 1。q若将信息位组左移若将信息位组左移r r位，则可表示为多项式位，则可表示为多项式M(x)xM(x)xr r。这样。这样就可以空出就可以空出r r位，以便拼接位，以便拼接r r位校验位，即位校验位，即计算机学院3.7 数据校验码qCRC码是用多项式M(x)xr除以称为生成多项式的G(x)(产生校验码的多项式)所得余数作为校验位。为了得到r位余数(校验位)，G(x)必须是r1位。设所得余数表达示为R(x)，商为Q(x)。将余数拼接在信息位左移r位后空出的r位上，就构成这个有效信息的CRC码。这个CRC码可用多项式表示为：M(x)xrR(x)Q(x)G(x)R(x)R(x)Q(x)G(x)R(x)R(x)Q(x)G(x)q因此所得CRC码可被G(x)表示的数码除尽。q将编好的循环校验码称为(n，k)码。计算机学院3.7 数据校验码qCRC码的编码电路q若G(x)=xrgr1xr1g2x2g1x11,gi0，1,ir1，2，1,则CRC码的编码电路如下图所示：计算机学院3.7 数据校验码q当gi=1时，开关gi闭合，当gi=0时，开关gi断开。开始发送数据时，开关k置于km位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出，一边进入编码电路循环运算。当信息发送完毕时，寄存器R0，R1，Rr1中的内容即为冗余位的值。此时，开关R断开，开关k置于kr位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。计算机学院3.7 数据校验码q例在CRC校验中，已知生成多项式G(x)x4x31。要求：计算信息序列1101101的校验序列。画出该G(x)的编码电路。q分析：分析：q对应生成多项式G(x)的二进制序列为：11001 在有效信息后面添4个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。计算机学院3.7 数据校验码计算机学院3.7 数据校验码qG(x)=11001,则CRC码的编码电路如下图所示。q开始发送数据时，开关k置于km位置，开关R同时闭合，信息位由输入端从高到低串行输入，一边从码字输出端输出，一边进入编码电路循环运算。当信息发送完毕时，寄存器R0，R1，R2，R3中的内容即为冗余位的值。此时，开关R断开，开关k置于kr位置，冗余位就紧接在信息位的后面输出。至此发送方编码发送完毕。计算机学院3.7 数据校验码计算机学院3.7 数据校验码q在实际工作中,接收方一边接收信息，一边利用译码电路进行差错检测。q若G(x)=xrgr1xr1g2x2g1x11,gi0，1,ir1，2，1,则译码电路如图2.2所示，当gi=1时，开关gi闭合，当gi=0时，开关gi断开。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R0，R1，Rr1中就寄存了余数E(x)。将余数各位进行或运算。得错误特征位E。若E0，则接收正确，将码字中的最末r位去掉，得到原发数据；若E=l，则表示收到的码字有错。计算机学院3.7 数据校验码q(2)CRC的译码与纠错的译码与纠错q在CRC校验中，发送方已知信息序列M(x)和生成多项式G(x)，发送方便可利用编码电路形成传输序列T(x)进行发送。T(x)经信道传输后到达接收方，接收方收到信息T(x),若T(x)T(x)，则传输无错，否则就是出错。接收方只是已知G(x)和收到的T(x),但不知道发送方发送的T(x)。判断T(x)是否有错的方法为：将收到的循环校验码用约定的生成多项式G(x)去除，如果码字无误则余数应为0，如有某一位出错，则余数不为0，不同位数出错余数不同。更换不同的待测码字可以证明：余数与出错位的对应关系是不变的，只与码制和生成多项式有关。对于其他码制或选用其他生成多项式，出错模式将发生变化。计算机学院3.7 数据校验码计算机学院3.7 数据校验码q例，求有效信息1010、0111的CRC校验码，并求循环余数，说明校验原理,画出译码与纠错电路。q分析：分析：(1)求有效信息1010的CRC校验码q确定校验位的位数 设R为校验位的位数，则整个码字的位数应满足不等式：N=KR2R1 设R=3，则231=7，N=43=7，不等式满足。所以R最小取3。q选一个R1位的生成多项式G(x),如G(x)=1011q在有效信息后面添R个0。然后用它和G(x)进行模2除法运算，所得的余数即为所求的校验位。计算机学院3.7 数据校验码计算机学院3.7 数据校验码计算机学院3.7 数据校验码计算机学院3.7 数据校验码计算机学院3.7 数据校验码q(3)校验原理q从以上(1)、(2)的余数循环次序来看，其余数是相同的，实际上只要是4位有效数，他们的余数均相同，而且出错模式也是相同的。计算机学院3.7 数据校验码计算机学院3.7 数据校验码计算机学院3.7 数据校验码q(4)译码与纠错电路q校验的原理是根据余数来判断出错位，取反即可纠错,译码与纠错电路如下。接收方将收到的码字信息逐位送入译码电路计算余数，在码字信息全部进入译码电路后，寄存器R0，R1，R2中就寄存了余数。计算机学院3.7 数据校验码q余数=0译码器的0输出端为高，表示无错；q余数=1译码器的1输出端为高，表示有效信息D1错，取反即可纠错；q余数=2译码器的2输出端为高，表示有效信息D2错，取反即可纠错；q余数=4译码器的4输出端为高，表示有效信息D3错，取反即可纠错；q余数=3译码器的3输出端为高，表示有效信息D4错，取反即可纠错；计算机学院3.7 数据校验码计算机学院3.7 数据校验码q(3)关于生成多项式关于生成多项式并不是任何一个(r1)位多项式都可以作为生成多项式的。从检错及纠错的要求出发，生成多项式应能满足下列要求：q任何一位发生错误都应使余数不为0。q不同位发生错误应当使余数不同。q对余数继续作模2除，应使余数循环。将这些要求反映为数学关系是比较复杂的，对一个(n，k)码来说，可将(xn1)分解为若干质因子，根据编码所要求的码距选取其中的因式或若干因式的乘积作为生成多项式。计算机学院3.7 数据校验码q例例：有一个（7，3）码，生成多项式为G(x)=x4+x3+x2+1,写出代码001的效验码和循环余数。q解：生成多项式为11101，在有效信息后面添个0，然后用它和G(x)进行模2除法运算。计算机学院3.7 数据校验码余数为，所以，所求的CRC效验码为：计算机学院3.7 数据校验码计算机学院3.7 数据校验码计算机学院运算方法和运算部件习题q第三章习题qP.103.3.9；qP.104.3.25;3.26;3.27;3.31END