第三章 运算方法与运算器部件.ppt

1、1,第三章运算方法和运算部件,2,主要内容,3.1数据的表示方法和转换,3.2带符号数据的表示方法与加减运算,3.3二进制乘法运算,3.5浮点数的运算方法,3.6运算部件,3.7计算机中的数据校验方法,3.4定点除法运算,3,3.1数制,3.1.1数值型数据的表示和转换,3.1.2十进制数的编码与运算,4,1、进位计数制基数（base或radix）：所用到的数字符号个数。例如10进制：0-9十个数码，基数为10权：进位制中各位“1”所表示的值为该位的权.常见的进位制：2，8，10，16进制。二进制：Binary八进制:Octal十进制：Decimal十六进制：Hexadecimal,3.1.1

2、数值型数据的表示和转换,5,2、进位计数制之间的转换,按权展开法:先写成多项式,然后计算十进制结果.N=dn-1dn-2d1d0d-1d-2d-m=dn-1Rn-1+dn-2Rn-2+d1R1+d0R0+d-1R-1+d-2R-2+d-mR-m,1)R进制转换成十进制的方法,6,例如:写出(1101.01)2,(237)8,(10D)16的十进制数,(1101.01)2=123+122+021+120+02-1+12-2=8+4+1+0.25=13.25(237)8=282+321+720=128+24+7=159(10D)16=1162+13160=256+13=269,7,2)十进制转换成

3、二进制方法,一般分为两个步骤：整数部分的转换除2取余法（基数除法）小数部分的转换乘2取整法（基数乘法）,8,例如：将(327)10转换成二进制数,2327余数,21631,2811,2401,2200,2100,250,221,210,201,(327)10=(101000111)2,最高位,最低位,9,乘基取整法(小数部分的转换),例如:将(0.8125)10转换成二进制小数.整数部分20.8125=1.625120.625=1.25120.25=0.5020.5=1.01(0.8125)10=(0.1101)2,10,例:将(0.2)10转换成二进制小数,0.22=0.400.42=0.8

4、00.82=1.610.62=1.210.22=0.400.42=0.800.82=1.610.62=1.21(0.2)10=0.001100110011.2,整数部分,11,3)其它进制之间的直接转换法,二八00000011010201131004101511061117,10008100191010A1011B1100C1101D1110E1111F,二十六,0000000011001020011301004010150110601117,12,二进制转换成八进制,例：(10110111.01101)2,(10110111.01101)2=(267.32)8,八进制:267.32,二进制:

5、010,110,111.011,010,二进制:10,110,111.011,01,13,八进制转换二进制,例如:(123.46)8=(001,010,011.100,110)2=(1010011.10011)2,14,二进制转换成十六进制,例：(110110111.01101)2,(10110111.01101)2=(1B7.68)16,十六进制:1B7.68,二进制:0001,1011,0111.0110,1000,二进制:1,1011,0111.0110,1,15,十六进制转换成二进制,例如:(7AC.DE)16=(0111,1010,1100.1101,1110)2=(11110101

6、100.1101111)2,16,3、数值符号的表示,带符号数的编码名词解释：真值和机器数真值:正、负号加某进制数绝对值的形式。如二进制真值：X=+1011y=-1011机器数：符号数码化的数称为机器数如：X=01011Y=11011,17,3.1.2十进制数的编码与运算,1、BCD码8421码为有权代码，数值为N=8d3+4d2+2d1+1d0十进制数63.29的BCD码为:01100011.001010012421码为有权代码，数值为N=2d3+4d2+2d1+1d0十进制数63.29的BCD码为:11000011.00101111余3码为无权代码，对应8421码加3而得。除上述三种BCD

7、码之外，还有5421码、格雷码等,18,BCD码,19,二进制码格雷码,二进制码-格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变；格雷码-二进制码（解码）：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）.,20,十进制编码的加法运算,1)“8421”BCD码加法运算BCD码运算应将每4位二进制数分为一组，组与组之间直接运算，逢十进一。但计算机中无法区分BCD码，一概作为二进制数处理，因此，计算机做此运算后须进行调整。调整方法：和9(1001)2，不调整和9(1001)2，加6(0110)2修

8、正,21,0111+10001111+011010101,1000+100110001+011010111,例:5+3=8,7+8=15,8+9=17,0101+00111000,向高位进位,22,2、数字串在机内的表示与存储,主要有两种形式:(l)字符形式：用一个字节存放一个十进制数位或符号位，存放的是09十个数字和正负号的ASCll编码值。例如，123的编码为2B313233，占用4个连续的字节。这种方式高4位不具有数值意义,运算起来很不方便，主要用在非数值计算的应用领域。,23,(2)压缩的十进制数形式。用一个字节存放两个十进制数位，其值用BCD码或ASCll码的低4位表示。符号位也占半

9、个字节并放在最低数字位之后，其值可从4位二进制码中的6种冗余状态中选用。例，用C(l2)表示正号；D(13)表示负号。并规定数字和符号位个数之和必须为偶数，否则在最高数字之前补一个0。例如，123被表示成123C（2个字节），一12被表示成012D（2个字节）。,24,3.2带符号数据的表示方法与加减运算,机器数：计算机中表示的带符号的二进制数.四种表示方法即原码、补码、反码和移码。,3.2.1原码、补码、反码和移码及运算,3.2.2定点数和浮点数计算机中的两种表示方式,3.2.3数字化信息的编码及表示,25,3.2.1原码、补码、反码和移码及运算,1、原码表示法原码表示法用“0”表正号，用“

10、1”表负号，有效值部分用二进制的绝对值表示。课件以下的n表示数值位数(机器字长为n+1位),小数：X1X0X原=1-X=1+|X|0X-1,26,原码的表示范围:+0原=00000000;-0原=10000000整数最大值:2n-1；最小值:-(2n-1)小数最大值：1-2-n；最小值-（1-2-n）表示数的个数:2n+1-1,若二进制的位数是8,求其表示的最大值、最小值及表示数的个数,整数127，-127；小数127/128，-127/128；个数：255,27,原码特点：,表示简单，易于同真值之间进行转换，实现乘除运算规则简单。进行加减运算十分麻烦。,28,2、补码表示法,模：计量器具的容

11、量，或称为模数。例如：4位字长的机器表示的二进制16种状态，模为16=24。整数N位字长的模值为2n，一位符号位的纯小数的模值为2。补码的定义：正数的补码就是正数的本身，负数的补码是原负数加上模。,29,补码的表示范围:,N+1位纯整数:2n-1，-2nN+1位纯小数:1-2-n，-1均能表示2n+1个数,小数：X1X0X补=2+X=2-|X|0X-1,30,原码求补码正数：X补=X原负数：符号除外，各位取反，末位加1例：X=-01001001X原=11001001X补=10110110+1=10110111X补=28+X=100000000-1001001=10110111100000000

12、-100100110110111,原码与补码之间的转换,31,由X补求-X补（求机器负数）,运算过程是连同符号一起将各位取反，末位再加1。设字长N=8位例：X=+1001001X补=01001001-X补=10110111,32,最大的优点就是将减法运算转换成加法运算。,X补-Y补=X补+-Y补例如X=(11)10=(1011)2Y=(5)10=(0101)2已知字长n=5位X补-Y补=X补+-Y补=01011+11011=100110=00110=(6)10注：最高1位已经超过字长故应丢掉,33,3、反码表示法,正数的表示与原、补码相同，负数的补码符号位为1，数值位是将原码的数值按位取反，就

13、得到该数的反码表示。,小数：X1X0X反=2-2-n+X0X-1,34,整数的表示形式,X0X2nX原=2n-X=2n+|X|-2nX0,X0X2nX补=2n+1+X=2n+1-|X|-2nX0,X0X2nX反=2n+1-1+X-2nX0,35,4、移码表示法,X移=2n+X-2nX2n,X1=+1010101X1补=01010101X1移=11010101X2=-01010101X2补=10101011X2移=00101011,36,码制表示法小结,X原、X反、X补用“0”表示正号，用“1”表示负号；X移用“1”表示正号，用“0”表示负号。如果X为正数，则X原=X反=X补。如果X为0，则X补

14、、X移有唯一编码，X原、X反有两种编码。移码与补码的数值形式相同，只是符号位相反。,37,6、数值的运算方法,计算机中，常用补码进行加减运算补码可将减法变加法进行运算补码运算特点：符号位和数值位一同运算定点补码运算在加法运算时的基本规则：X+Y补=X补+Y补定点补码运算在减法运算时的基本规则:X-Y补=X补+-Y补,38,例如：已知机器字长n=8，X=44，Y=53，求X+Y=？,解：X原=00101100，Y原=00110101,X补=00101100，Y补=00110101,X补=00101100+Y补=00110101,1,0,0,0,0,1,1,0,X+Y=+97,39,例：已知机器字

15、长n=8，X=-44，Y=-53，求X+Y=？,解：44补=00101100,53补=00110101X补=-44补=11010011+1=11010100,Y补=-53补=11001010+1=11001011,X补=11010100+Y补=11001011X+Y补=110011111超出8位，舍弃模值X+Y=-01100001，X+Y=（-97）,40,例：已知机器字长n=8，X=44，Y=53，求X-Y=？,解：X补=00101100，Y补=00110101,-Y补=11001011X补=00101100+-Y补=1100101111110111X-Y补=11110111，X-Y=-00

16、01001=（-9）,41,例：已知机器字长n=8，X=-44，Y=-53，求X-Y=？,解：X补=11010100，Y补=11001011,-Y补=00110101X补=11010100+-Y补=00110101100001001超出8位（模值），舍弃X-Y补=00001001，X-Y=+0001001=(+9),42,溢出问题,例：已知机器字长n=8，X=120，Y=10，求X+Y=？,43,解：X补=01111000，Y补=00001010,X补=01111000+Y补=0000101010000010X+Y补=10000010，X+Y原=11111110X+Y的真值=-1111110=

17、(-126)10运算结果超出机器数值范围发生溢出错误。,44,溢出判断规则与判断方法,两个相同符号数相加，其运算结果符号与被加数相同，若相反则产生溢出；两个相异符号数相加，不会产生溢出。溢出判断方法：1.双符号法，2.进位判断法。,45,（1）双符号位溢出判断法Sf1Sf2（也被称为变形补码）,双符号含义：00表示运算结果为正数；01表示运算结果正向溢出；10表示运算结果负向溢出；11表示运算结果为负数。亦即：OVR=Sf1Sf2=1有溢出OVR=Sf1Sf2=0无溢出第一位符号位为运算结果的真正符号位。,46,例：X=0.1001,Y=0.0101,求X+Y,解:X补=00.1001+Y补=

18、00.0101X+Y补=00.1110两个符号位相同，运算结果无溢出X+Y=+0.1110,47,例：X=-0.1001，Y=-0.0101，求X+Y=？,解:X补=11.0110+1=11.0111+Y补=11.1010+1=11.1011X+Y补=111.0010最高位1丢掉两个符号位相同,运算结果无溢出X+Y=-0.1110,48,例：X=0.1011，Y=0.0111，求X+Y=？,解:X补=00.1011+Y补=00.0111X+Y补=01.0010两个符号位为01,运算结果正向溢出,49,例：X=-0.1011，Y=0.0111，求X-Y=？,解:X补=11.0100+1=11.0

19、101Y补=00.0111-Y补=11.1001X补=11.0101+-Y补=11.1001X+Y补=110.1110两个符号位10不同,运算结果负向溢出,50,（2）进位溢出判断法SC,两单符号位的补码进行加减运算时，若最高数值位向符号位的进位值C与符号位产生的进位输出值S相同时则无溢出，否则溢出。例：X补=1.101+Y补=1.001X+Y补=10.110C=0，S=1，有溢出X+Y=+0.010,X补=1.110+Y补=0.100X+Y补=10.010C=1,S=1,无溢出,51,3.2.2定点数和浮点数,数值范围：一种数据类型所能表示的最大值和最小值数据精度：实数所能表示的有效数字位数

20、。数值范围和数据精度均与使用多少位二进制位数以及编码方式有关。计算机用数字表示正负，隐含规定小数点。采用“定点”、“浮点”两种表示形式。,52,1、数的定点表示方法,定点整数小数点位置固定在数的最低位之后如：DnDn-1D1D0.定点小数小数点位置固定在数的符号位之后、数值最高位之前。如：D0.D1D-(n-1)D-n,53,（1）浮点数的表示：是把字长分成阶码和尾数两部分。其根据就是：N=MREJEm-2.E0SD-1D-(n-1)阶符阶码值数符.尾数值SJEm-2.E0D-1D-(n-1)数符阶符阶码值.尾数值通常，阶码为补码或移码定点整数，尾数为补码或原码定点小数。,2、数的浮点表示方法

21、,54,（2）浮点数的规格化,目的：字长固定的情况下提高表示的精度,方法：调整阶码使尾数满足下列关系：尾数用原码表示时，无论正负应满足1/2dd-1，即1.0 x.x,55,例题：某机器用32位表示一个实数，阶码8位（含1位阶符），用定点整数补码表示；尾数24位（含数符1位），用规格化定点小数补码表示，基数为2。则：,1）X=256.5的第一种浮点表示格式X=(256.5)10=+(100000000.1)2=+(0.10000000012+9)28位阶码为：+9补=0000100124位尾数为：+0.1000000001补=0.10000000010000000000000所求256.5的浮

22、点表示格式为：00001001010000000010000000000000用16进制表示此结果则为：(09402000)16,56,Y=-(256.5)10=-(100000000.1)2=-0.10000000012+98位阶码为：+9补=0000100124位尾数为：-0.1000000001补=1.01111111110000000000000所求-256.5的浮点表示格式为：00001001101111111110000000000000用16进制表示此结果则为：09BFE000H,2）求Y=-256.5的第一种浮点表示格式,57,3.3二进制乘法运算,1.软件编程方法实现(时序控

23、制乘法器）由手算到机器实现，要解决三个问题：符号问题、部分积相加进位问题、移位问题。原码乘法是先取绝对值相乘，再根据同号相乘为正、异号相乘为负，单独决定符号位。补码乘法则让符号位直接参加运算，算法将会复杂一些。2.硬件快速乘法器实现利用中大规模集成电路芯片，在一拍节中实现多项部分积的相加，成为阵列乘法器。,58,乘法运算,1.分析笔算乘法,A=0.1101B=0.1011,AB=0.10001111,0.1101,0.1011,1101,1101,0000,1101,0.10001111,符号位单独处理,乘数的某一位决定是否加被乘数,4个位积一起相加,乘积的位数扩大一倍,乘积的符号心算求得,？

24、,59,3.3.1定点数一位乘法,1、定点原码一位乘,2、定点补码一位乘法,60,例:设X=0.1101,Y=0.1011,求XY。其中寄存器B=X,计数器Cd=4。计算过程如下:,00000010110011010011010001101101001101010011001001111000000000100100010011110011010100010010001111,+x右移一位+x右移一位+0右移一位+x右移一位,部分积A乘数C,乘积高位乘积低位,1(丢失)1(丢失)0(丢失)1(丢失),XY=0.10001111,61,例,已知x=0.1110y=0.1101求xy原,解：,数值

25、部分的运算,0.0000,0.1110,0.1110,0.0000,0.1110,0.1110,部分积初态z0=0,逻辑右移,逻辑右移,62,数值部分按绝对值相乘,x*y*=0.10110110,则xy原=1.10110110,特点,绝对值运算,逻辑移位,结果,用移位的次数判断乘法是否结束,63,2、定点补码一位乘法,原码乘法存在的缺点是符号位需要单独运算，并要在最后给乘积冠以正确的符号。补码乘法是指采用操作数的补码进行乘法运算，最后乘积仍为补码，能自然得到乘积的正确符号。,64,实现补码乘法有两种方法，现在广泛使用的是Booth算法，也称为比较法。这种方法在机器实现中要在乘数末位（最低位后）

26、Yi之后再增加一个附加位Yi+1,并令其初始值为0。然后根据比较Yi、Yi+1的值决定下一步操作，规则如下：(设置部分积初始值为0)YiYi+1操作00原部分积右移一位01原部分积加X补后再右移一位10原部分积加-X补后再右移一位11原部分积右移一位,65,初始值与符号位：A寄存器存放部分累加和，初始为0，采用双符号位。第1符号位指示累加和的正负，以控制右移时补0或补1。B中存放被乘数的补码，双符号位。基本操作：用C寄存器最末两位作判断位，决定下一步的操作。移位:在右移时，第2符号位值移入位数的最高位，第1符号位值不变且移入第2符号位，而A寄存器末位移入C寄存器。步数与最后一步操作:乘数有效位

27、是n=4位，共作n+1=5步。注意，最后一步不移位因为这一步是用来处理符号位的。,66,例3.35:设X=-0.1101,Y=0.1011,即X补=11.0011,Y补=0.1011,-X=00.1101求XY补.计算过程如下:,0000000.10110初始值,最后一位补0001101Y4Y5=10+-X补001101000110101011右移一位000000Y3Y4=11+0000110000011010101右移一位110011Y2Y3=01+X补110110111011001010右移一位001101Y1Y2=10+-X补001000000100000101右移一位110011Y0Y

28、1=01+X补1101110001,+,部分积乘数YYiYi+1说明,乘积高位乘积低位,XY补=1.01110001,XY=-0.10001111,67,3、阵列乘法器为了进一步提高乘法器运算速度，可采用类似人工计算的方法，用一个阵列乘法器完成X*Y乘法运算。阵列的每一行送入乘数Y的每一位数，而各行错开形成的每一斜列则送入被乘数的每一数位。每一个基本单元可用1个与门和1位全加器。该方案所用加法器数量较多，内部结构规则性强，适用超大规模集成电路实现。,68,定点补码一位除法（加减交替法）,n位数相除，要求被除数的位数要扩展成除数位数n的两倍2n位，没包括符号位在内；由于不能自动判溢出，故需在|X

29、|1）时，需右规,81,例,解：,x补=00,010;00.110100,y补=00,001;00.101100,对阶,尾数求和,j补=jx补jy补,=00,010,11,111,100,001,阶差为+1,y补=00,010;00.010110,Sx补=00.110100,Sy补=00.010110,对阶后的Sy补,01.001010,+,+,尾数溢出需右规,82,右规,x+y补=00,010;01.001010,x+y补=00,011;00.100101,右规后,x+y=0.100101211,舍入操作：0舍1入或恒置1,在对阶和右规过程中，可能出现尾数末位丢失引起误差，需考虑舍入,(1)

30、0舍1入法,(2)恒置“1”法,83,例,解：,x补=11,011;11.011000,y补=11,100;00.111000,对阶,j补=jx补jy补,=11,011,00,100,11,111,阶差为1,x补=11,100;11.101100（尾数补码右移最高数值位补1。）,x=(0.101000)2-101,y=(0.111000)2-100,+,84,尾数求和,Sx补=11.101100,Sy补=11.001000,+,110.110100,右规,x+y补=11,100;10.110100,x+y补=11,101;11.011010（采用0舍1入方式，无进位。将其转换二进制真值后为：,

31、右规后,xy=(0.100110)2-11,85,例：求=?0舍1入后为恒置1例2：求=?0舍1入后为恒置1判断结果的正确性(即结果的阶码是否溢出),86,2、浮点数的乘、除法运算,一、运算规则两浮点数相乘其乘积的阶码为相乘两数阶码之和,其尾数应为相乘两数的尾数之积。两个浮点数相除，商的阶码为被除数的阶码减去除数的阶码得到的差，尾数为被除数的尾数除以除数的尾数所得的商。参加运算的两个数都为规格化浮点数，乘除运算都可能出现结果不满足规格化要求的问题，因此也必须进行规格化、舍入和判溢出等操作。规格化时要修改阶码。,87,浮点乘除运算,x=Sx2jx,y=Sy2jy,1.乘法,xy=(SxSy)2j

32、x+jy,2.除法,(1)阶码采用补码(或移码)定点加减运算,(2)尾数乘除同定点运算,3.步骤,(3)规格化,(4)舍入,88,例题3.47：设：X=0.1110011*2-5，Y=(-0.1110010)*23,浮点数表示阶码4位（移码），尾数8位（补码），结果取8位尾数。运算过程中阶码取双符号位。解：1.求乘积的阶码（为两阶码之和）-5原=1.101-5补=1.011-5移=0.011EX+EY移=EX移+EY补=00011+00011=001102.两位数相乘（运算过程略）X*Y补=1.00110011001010(尾数部分）高位部分低位部分3.规格化处理,89,4.舍入根据0舍1法，

33、尾数乘积低位部分的最高位为1，在乘积高位部分的最低位加1，因此：X*Y补=1.0011010（尾数部分）5.判溢出阶码未溢出，故结果为正确。X*Y:011010011010阶码（移码）尾数（补码）X*Y=(-0.1100110)*2-2,90,3.6运算部件,1.定点运算部件定点运算部件由算术逻辑运算部件ALU、若干个寄存器、移位电路、计数器、门电路等组成。ALU部件主要完成加减法算术运算及逻辑运算（其功能可参考242节），其中还应包含有快速进位电路。2.浮点运算部件通常由阶码运算部件和尾数运算部件两部分组成。阶码运算器是一个定点运算部件。它的功能包含：阶码大小的比较、执行加减法运算、调整其增

34、量或减量。尾数部分是一个定点小数运算部件。它的功能包含：左移、右移、尾数加减乘除运算。为加速移位过程，有的机器设置了可移动多位的电路。,91,浮点运算电路,92,3.7计算机中的数据校验方法,采用冗余校验方法：即在基本的有效数据外，再扩充部分位，增加部分（冗余部分）被称为校验位。将校验位与数据位一起按某种规则编码，写入存储器或向外发送。当从存储器读出或接收到外部传入的代码时，再按相应的规则进行判读。若约定的规则被破坏，则表示出现错误。根据错误的特征进行修正恢复。,93,几个名词概念：码制：一种已经规定好的组合，如8421编码、余3编码等。码字：由若干代码组成的一个字。如8421码中6（0110

35、），7（0111）码距：一种码制中任意两个码字间的最小距离。距离：两个码字之间不同的代码个数。8421码中，最小的码字间的距离为1，如0000和0001、0010和0011等；最大码字间的距离为4，如0111和1000。所以8421码制的码距为1。码距为1码制，即不能查错也不能纠错。码距越大的码制，查错、纠错能力越强。,94,3.7.1奇偶校验法,奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是：在每组数据信息上附加一个校验位，校验位的取值（0或1）取决于这组信息中1的个数和校验方式（奇或偶校验）。如果采用奇校验，则这组数据加上校验码位后数据中1的个数应为奇数个。奇校

36、验位形成公式:C=X0X1Xn-1如果采用偶校验，则这组数据加上校验码位后数据中1的个数应为偶数个。偶校验位形成公式:C=X0X1Xn-1,95,例如：八位信息10101011中共有5个1，附加校验位后变为九位。若采用奇校验，则附加的校验位应取0值，保证1的个数为奇数个即010101011；若采用偶校验则附加的校验位应取1值即110101011。奇偶校验的特点：1、奇偶校验法使数据的码距为2，因而可检出数据传送过程中奇数个数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。,96,奇校验1出错,偶校验1出错,偶形成,奇形

37、成,D校为校验位,D校D0D1D2D3D4D5D6D7,8位数据的奇偶校验码形成电路及检码电路,97,3.7.2海明码校验方法,海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组，故其码距大于2。海明码校验方法能够检测出具体错误并纠正。原理是在数据中加入r个校验位，将数据的码距按照一定规则拉长。r个校验位可以表示2r个信息，除一个表示无误信息外，其余2r-1信息可以用来标明错误的具体位置，但由于校验位本身也可能在传送中出错，所以只有2r-1-r个信息可用，即r位校验码只可标明2r-1-r个错误信息。或2rk+r+1k是被传送数据的位数。例如：用4个校验位能可靠传输24-1-4=11位信

38、息；而要校验32位数据则需至少6个校验位。,98,如要能检测与自动校正一位错井发现两位错此时校验位的位数r和数据位的位数k应满足下述关系：2r-1k+r（3.19）按式（3.19），可计算出数据位k与校验位r的对应关系，如教材表3.8所示。,99,一、编码方法（以四个校验位进行说明）,四个校验位最多可以校验11位数据。设：D10D9D8D7D6D5D4D3D2D1D0为11个数据位，P4P3P2P1分别为四个校验码，则编码规则是：海明码的总位数等于数据位与校验位之和；每个校验位Pi排放在2i-1的位置，例如P4排放在第24-1=8位，其余数据位依序排列。即：D10D9D8D7D6D5D4P4D

39、3D2D1P3D0P2P1海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；各校验位的值为它参与校验的数据位的异或。,100,海明码校验表,101,各校验位形成公式：P1=D0D1D3D4D6D8D10(1)P2=D0D2D3D5D6D9D10(2)P3=D1D2D3D7D8D9D10(3)P4=D4D5D6D7D8D9D10(4)按上述方式Pi的取值是采用偶校验时的取值，当采用奇校验时，Pi则取反。这样Pi连同数据位一起形成了海明码的各位。,102,二、检查纠错（以四个校验位进行说明）,海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进

40、行异或运算。运算结果称为校验和。校验和共有四个。对偶校验来说，如果校验和不为零则传输过程中间有错误。而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和S4S3S2S1依序排列后等于(1001)2=(9)10时，就表明海明码的第九位也就是D4发生了错误，此时只要将D4取反，也就纠正了错误。,103,校验和Si的表达式：S1=D0D1D3D4D6D8D10P1S2=D0D2D3D5D6D9D10P2S3=D1D2D3D7D8D9D10P3S4=D4D5D6D7D8D9D10P4当采用偶校验方式其传送数据正确时，校验和S1S4的值分别都为0；当采用奇校验方式其传送数据正确时，校验和S1

41、S4的值分别都为1。当不为上述值时，传送就发生了错误。,104,解：已知D10D9D8D7D6D5D4D3D2D1D0=10110100110由于被校验位的位号等于校验它的各校验位位号之和以及各校验位的取值等于它参与校验的数据位取值的异或。所以校验位的取值以及所求海明码为：P1=D0D1D3D4D6D8D10=1P2=D0D2D3D5D6D9D10=1P3=D1D2D3D7D8D9D10=1P4=D4D5D6D7D8D9D10=0D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=101101000111011传送正确时校验和的值为0，如果不等于0，则是几就是第几位出错，是7则是第

42、7位D3出错，此时将其取反即可纠正错误。,例题：采用4位校验位、偶校验方式，写出10110100110的海明码。,105,106,以上图3.11是H=12，数据位k=8，校验位r=4的海明校验线路，记作（l2.8）分组码。图3.ll中的H12,H11,.,H1是被校验码，D8,D7,.，D1是纠正后的数据。在线路中，先用奇偶形成线路得到S4,S3,S2,S1，如果S4S1为全“0”，说明代码无错，则D8D7.DI=H12H11H10H9H7H6H5H3。如果S4S1不为全0，说明有错。若为1100或1011，则分别表示H12或Hll位错，对应这两种出错情况，相关的两条译码线之一为“l”，它与相

43、应的数据使经异或线路，就把该位校正过来，得到正确编码输出。依此类推如S4S3S2S1为1010，1001，0111，0110，0101或0011，分别表示H10，H9,H7,H6,H5或H3位错，用相同的方法予以纠正、如错误发生在校验位上。则相关的译码线（1000，0l00，0010，0001）之一为l，在图311中未画出。如前所述，假如要进一步判别是1位错还是2位错，则再增加一个校验位、并用图3.12来取代图3.11虚框中的内容，此时增加了一个奇偶形成线路S5。如为一位错，仍按图3.11来纠正数据位；如为两位错，则无法纠正错误。,107,C1C2.CKr1r2ri,3.7.3循环冗余校验方法(CRC码),环冗余校验方式：通过某种数学公式建立信息位