運(yùn)算方法和運(yùn)算部件2.1帶符號(hào)的數(shù)據(jù)表示方法2.1.1定點(diǎn)數(shù)的數(shù)據(jù)表示2.1.2浮點(diǎn)數(shù)的數(shù)據(jù)表示2.2機(jī)器數(shù)的運(yùn)算方法2.2.1定點(diǎn)數(shù)加減運(yùn)算2.2.2二進(jìn)制乘法運(yùn)算2.2.3二進(jìn)制除法運(yùn)算2.2.4浮點(diǎn)數(shù)的運(yùn)算

第

2

章2.3數(shù)據(jù)校驗(yàn)碼2.3.1奇偶校驗(yàn)碼2.3.2循環(huán)冗余校驗(yàn)碼2.3.3海明碼2.4算術(shù)邏輯單元2.4.1ALU電路2.4.2快速進(jìn)位鏈1/15/20231數(shù)據(jù)的表示（定點(diǎn)數(shù)和浮點(diǎn)數(shù)）；補(bǔ)碼的加減運(yùn)算及溢出判斷；定點(diǎn)數(shù)的原碼、補(bǔ)碼的乘除法，實(shí)現(xiàn)過(guò)程；掌握3種數(shù)據(jù)校驗(yàn)碼（奇偶校驗(yàn)、海明碼、循環(huán)冗余碼）的編碼方法、譯碼方法，功能及應(yīng)用場(chǎng)合。算術(shù)邏輯單元的工作原理教學(xué)要求1/15/20232第2.1節(jié)帶符號(hào)的數(shù)據(jù)表示方法1/15/20233一、基本概念1.真值計(jì)算機(jī)外界的數(shù).現(xiàn)表示為二進(jìn)制.X1=+1011000BX2=-101100B2.機(jī)器數(shù)在計(jì)算機(jī)中表示的帶符號(hào)的二進(jìn)制數(shù),機(jī)器數(shù)有三種表示方式：原碼、補(bǔ)碼和反碼。機(jī)器數(shù)的長(zhǎng)度受字長(zhǎng)限制。3.無(wú)符號(hào)數(shù)表示范圍:8位0～25516位0～65535N位0～2N-12.1帶符號(hào)的數(shù)據(jù)表示方法1/15/202344.有符號(hào)數(shù)計(jì)算機(jī)中正負(fù)數(shù)的表示

76543210符號(hào)位

數(shù)值位若機(jī)器字長(zhǎng)為16位符號(hào)位=0正數(shù)

數(shù)值位

=

1負(fù)數(shù)1514131211109876543210若機(jī)器字長(zhǎng)為8位H.O.ByteL.O.ByteH.O.NibbleL.O.Nibble2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/202351.原碼表示法符號(hào)__絕對(duì)值法

【例】n=8bit

[+3]原碼=0,0000011B=03H[-3]原碼=1,0000011B=83H[+0]原碼=0,0000000B=00H[-0]原碼=1,0000000B=80H

0的表示不惟一2.1.1定點(diǎn)數(shù)的數(shù)據(jù)表示1/15/20236優(yōu)點(diǎn):真值和原碼對(duì)應(yīng)關(guān)系簡(jiǎn)單,容易轉(zhuǎn)化;乘法運(yùn)算規(guī)則簡(jiǎn)單缺點(diǎn)：運(yùn)算（加、減法）復(fù)雜,低效;0有兩個(gè)表示原碼表示法的特點(diǎn)2.1.1定點(diǎn)數(shù)的數(shù)據(jù)表示2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/20237

【例】n=8bit[+5]反碼=0,0000101B=05H[-5]反碼=1,1111010B=FAH[+0]反碼=0,0000000B=00H[-0]反碼=1,1111111B=FFH

反碼表示法特點(diǎn):反碼的和等于和的反碼；

0的表示不惟一

2.反碼表示法2.1帶符號(hào)的數(shù)據(jù)表示方法

正數(shù)的反碼:同原碼

負(fù)數(shù)的反碼:是對(duì)該數(shù)的原碼除符號(hào)位外各位求反1/15/202383.補(bǔ)碼表示法正數(shù)的補(bǔ)碼：同原碼負(fù)數(shù)的補(bǔ)碼:(1)求出該負(fù)數(shù)相對(duì)應(yīng)正數(shù)的補(bǔ)碼(2)按位求反(3)末位加12.1帶符號(hào)的數(shù)據(jù)表示方法[+1]補(bǔ)=00000001B[+127]補(bǔ)=01111111B[+0]補(bǔ)=00000000B[-1]補(bǔ)=11111111B[-127]補(bǔ)=10000001B[-0]補(bǔ)=00000000B定義:[-128]補(bǔ)=10000000補(bǔ)碼的特性1[X]補(bǔ)碼

[-X]補(bǔ)碼求補(bǔ)1/15/20239

十進(jìn)制二進(jìn)制十六進(jìn)制十進(jìn)制十六進(jìn)制

n=8n=16+127011111117F+327677FFF+126011111107E+327667FFE......……...+20000001002+20002+10000000101+100010000000000000000-111111111FF-1FFFF-211111110FE-2FFFE......……...-1261000001082-327668002-1271000000181-327678001-1281000000080-327688000n位二進(jìn)制補(bǔ)碼的表示范圍：

-2n-1≤N≤2n-1-1n位無(wú)符號(hào)整數(shù)的表示范圍：

0≤N≤2n-1

2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/202310補(bǔ)碼特點(diǎn):當(dāng)補(bǔ)碼加法運(yùn)算的結(jié)果不超出機(jī)器范圍時(shí)，可得出以下重要結(jié)論：補(bǔ)碼表示的兩數(shù)進(jìn)行加法運(yùn)算，其結(jié)果仍為補(bǔ)碼[X+Y]補(bǔ)=[X]補(bǔ)+[Y]補(bǔ)。符號(hào)位與數(shù)值位一樣參與運(yùn)算。2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/202311求補(bǔ)概念：求某數(shù)的相反數(shù)求補(bǔ)方法：對(duì)一個(gè)二進(jìn)制數(shù)按位求反、末位加一2.1帶符號(hào)的數(shù)據(jù)表示方法補(bǔ)碼的特性1.求補(bǔ)特性

[X]補(bǔ)碼[-X]補(bǔ)碼[X]補(bǔ)碼

求補(bǔ)求補(bǔ)補(bǔ)碼減法可轉(zhuǎn)換為補(bǔ)碼加法2.加法規(guī)則

[X+Y]補(bǔ)碼=[X]補(bǔ)碼+[Y]補(bǔ)碼3.減法規(guī)則

[X-Y]補(bǔ)碼=[X]補(bǔ)碼+[-Y]補(bǔ)碼

1/15/202312利用加法規(guī)則(X+Y)補(bǔ)=X補(bǔ)+Y補(bǔ)【例】求X+Y3)X=3Y=–2X補(bǔ)=00011BY補(bǔ)=11110B00001B∴

X+Y=+12)X=–3Y=–2X補(bǔ)=11101BY補(bǔ)=11110B11011B∴

X+Y=–51)X=3Y=2X補(bǔ)=00011BY補(bǔ)=00010B00101B∴

X+Y=+54)X=–3Y=2X補(bǔ)=11101BY補(bǔ)=00010B11111B∴

X+Y=–11/15/202313【例】求X–YY補(bǔ)

(–Y)補(bǔ)：

求補(bǔ)符號(hào)位連同數(shù)值位全部按位取反，末位加1。利用減法規(guī)則(X-Y)補(bǔ)=X補(bǔ)+(-Y)補(bǔ)1)X=4Y=–5X補(bǔ)=00100BY補(bǔ)=11011B(-Y)補(bǔ)=00101B01001B(X-Y)補(bǔ)=01001B∴

X-Y=+92)X=–4Y=5X補(bǔ)=11100BY補(bǔ)=00101B(-Y)補(bǔ)=11011B10111B(X-Y)補(bǔ)=10111B∴

X-Y=-91/15/202314【注意】區(qū)別補(bǔ)碼表示與求補(bǔ)運(yùn)算1/15/202315

符號(hào)位不變數(shù)值位不變(符號(hào)位為0)變反(符號(hào)位為1)

+,–←→0,1

數(shù)值位不變

數(shù)值位不變(符號(hào)位為0)

變反加1(符號(hào)位為1)

符號(hào)位不變

[X]反X真值

[X]原[X]補(bǔ)【例】真值為-52[-52]原=10110100B[-52]反=11001011B[-52]補(bǔ)=11001100B4.原碼、反碼和補(bǔ)碼之間的轉(zhuǎn)換2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/2023165.討論機(jī)器數(shù)的表示范圍

以1個(gè)字節(jié)長(zhǎng)為例原碼：11111111B----01111111B（-127到+127）注意0有兩種表示：00000000B與10000000B反碼：10000000B----01111111B（-127到+127）0也有兩種表示補(bǔ)碼：10000000B----01111111B（-128到+127）0只有一種表示

2.1帶符號(hào)的數(shù)據(jù)表示方法1/15/202317在計(jì)算機(jī)中的數(shù)據(jù)有定點(diǎn)數(shù)和浮點(diǎn)數(shù)兩種表示方式：

1．定點(diǎn)數(shù)定點(diǎn)數(shù):是指小數(shù)點(diǎn)固定在某個(gè)位置上的數(shù)據(jù).一般有小數(shù)和整數(shù)兩種表示形式。定點(diǎn)小數(shù)是把小數(shù)點(diǎn)固定在數(shù)據(jù)數(shù)值部分的左邊，符號(hào)位的右邊；整數(shù)是把小數(shù)點(diǎn)固定在數(shù)據(jù)數(shù)值部分的右邊。

2.1.2浮點(diǎn)數(shù)的數(shù)據(jù)表示1/15/2023182．浮點(diǎn)數(shù)【引例】76.687D=102*0.766871001.101B=2100*0.1001101定點(diǎn)機(jī)中具有相同的E,即小數(shù)點(diǎn)是固定不變的(通常E=0)【例】定點(diǎn)數(shù)N=0.1101011B定點(diǎn)機(jī)中表示:NF1101011故:任意二進(jìn)制數(shù)可表示為:N=2E*SN的尾數(shù)N的階碼階碼的底1/15/202319第2.2節(jié)機(jī)器數(shù)的運(yùn)算方法1/15/202320溢出的概念:當(dāng)運(yùn)算結(jié)果超出機(jī)器數(shù)所能表示的范圍時(shí)，稱(chēng)為溢出。進(jìn)位的概念:由于運(yùn)算結(jié)果超出了位數(shù),最高有效位向前的進(jìn)位，這一位自然丟失，一般不表示結(jié)果的對(duì)錯(cuò)。比較溢出和進(jìn)位2.2機(jī)器數(shù)的運(yùn)算方法1/15/2023212.2.1定點(diǎn)數(shù)加減運(yùn)算1/15/202322溢出的判斷原則:同號(hào)數(shù)相加,其結(jié)果相異。異號(hào)數(shù)相減,其結(jié)果與被減數(shù)相異。(異號(hào)相加或同號(hào)相減，不會(huì)發(fā)生溢出。)溢出的判斷方法:有兩種采用最高有效位的進(jìn)位判斷采用變形補(bǔ)碼加減法運(yùn)算的溢出處理2.2.1定點(diǎn)數(shù)的加減運(yùn)算1/15/20232301100110所以:這四種情況全都是溢出。01011101010101110111+01000+11000+01001+10101100111011011010001100若最高數(shù)值位向符號(hào)位的進(jìn)位值與符號(hào)位產(chǎn)生的進(jìn)位輸出值不相同，表明加減運(yùn)算產(chǎn)生了溢出。方法1:采用最高有效位的進(jìn)位判斷2.2.1定點(diǎn)數(shù)的加減運(yùn)算1/15/202324結(jié)果符號(hào)位是01，正溢出將符號(hào)位擴(kuò)展為兩位，稱(chēng)為變形補(bǔ)碼。采用變形補(bǔ)碼可根據(jù)運(yùn)算結(jié)果的兩個(gè)符號(hào)位是否一致來(lái)判斷發(fā)生溢出?！纠恳阎猉=63，Y=66，求X+Y63+66=12900，0111111+00，100001001，0000001方法2:采用變形補(bǔ)碼判斷2.2.1定點(diǎn)數(shù)的加減運(yùn)算1/15/202325【例】已知X=51，Y=45，求X-Y解：[X]補(bǔ)=00,110011B，[Y]補(bǔ)=00,101101B[X-Y]補(bǔ)=[X]補(bǔ)+[-Y]補(bǔ)=00,110011B+11,010011B自然丟失100,000110B結(jié)論:

變形補(bǔ)碼的結(jié)果符號(hào)位為[X-Y]補(bǔ)=00,000110B，X-Y=+6，無(wú)溢出。00，表示結(jié)果為正數(shù)，無(wú)溢出

01，表示結(jié)果為正溢出10，表示結(jié)果為負(fù)溢出

11，表示結(jié)果為負(fù)數(shù)，無(wú)溢出2.2.1定點(diǎn)數(shù)的加減運(yùn)算1/15/2023262.2.2二進(jìn)制乘法運(yùn)算1/15/2023272.2.2二進(jìn)制乘法運(yùn)算

移位操作移位類(lèi)型邏輯移位：數(shù)碼位置變化，數(shù)值不變。左移時(shí)低位補(bǔ)0右移時(shí)高位補(bǔ)0算術(shù)移位：數(shù)碼位置變化,數(shù)值變化,符號(hào)位不變。左移一位相當(dāng)于帶符號(hào)數(shù)乘以2右移一位相當(dāng)于帶符號(hào)數(shù)除以22.2.2二進(jìn)制乘法運(yùn)算1/15/202328（1）單符號(hào)位：0011101110

（2）雙符號(hào)位：001110

000111（3）移位規(guī)則左移右移右移001110

0011左移左移右移右移011100

001110000111數(shù)符不變（單：符號(hào)位不變；雙：第一符號(hào)位不變）。空位補(bǔ)0（右移時(shí)第二符號(hào)位移至尾數(shù)最高位）。2.正數(shù)補(bǔ)碼移位規(guī)則易出錯(cuò)處：001110：001100

左右011100：000110

2.2.2二進(jìn)制乘法運(yùn)算1/15/202329（1）單符號(hào)位：1101110110

（2）雙符號(hào)位：101100

110110（3）移位規(guī)則左移右移右移1

10111

1101左移右移右移110110111011數(shù)符不變（單：符號(hào)位不變；雙：第一符號(hào)位不變）。左移空位補(bǔ)0（第二符號(hào)位移至尾數(shù)最高位）。易出錯(cuò)處：110110：111100

左右101100：111110

右移空位補(bǔ)13.負(fù)數(shù)補(bǔ)碼移位規(guī)則2.2.2二進(jìn)制乘法運(yùn)算1/15/202330一、定點(diǎn)原碼一位乘法1/15/2023310.1101×0.101111011101000011010.10001111部分積運(yùn)算規(guī)則：取操作數(shù)絕對(duì)值參加運(yùn)算，符號(hào)位單獨(dú)處理。計(jì)算機(jī)中實(shí)現(xiàn)方法：將n位乘法轉(zhuǎn)換為n次累加與n次右移完成。問(wèn)題：1）加數(shù)增多（由乘數(shù)位數(shù)決定）。2）加數(shù)的位數(shù)增多（與被乘數(shù)、乘數(shù)位數(shù)有關(guān)）。改進(jìn)：將一次相加改為分步累加。【例】X=+0.1101B，Y=+0.1011B1.手算過(guò)程1/15/202332原理：每次將一位乘數(shù)所對(duì)應(yīng)的部分積與原部分積的累加和相加，并移位。設(shè)置寄存器：A：存放部分積累加和、乘積高位B：存放被乘數(shù)C：存放乘數(shù)、乘積低位

設(shè)置初值：

A=00.0000BB=X=00.1101BC=Y=.1011B

2.分步乘法1/15/2023333.計(jì)算機(jī)實(shí)現(xiàn)方法將n位乘法轉(zhuǎn)換為n次“累加與移位”完成(每步求出一位乘數(shù)所對(duì)應(yīng)的新部分積，并與原部分積作一次累加，然后累加的結(jié)果右移一位)BA+B→A右移一位到C高位中1101×1011110111010000+110110001111乘積CA+B→A右移一位到C高位中A+0→A右移一位到C高位中A+B→A右移一位到C高位中AC1/15/202334

步數(shù)條件操作A（部分積）C(乘數(shù)）

00.0000.1011

1）Cn=1+|X|Cn+00.110100.110100.01101.1012）Cn=1+00.110101.001100.100111.103）Cn=0+0+00.000000.100100.0100111.14）Cn=1+00.110101.000100.10001111X0Y0=0(XY)原=0.10001111B∴X·Y=+0.10001111B+|X|+|X|1/15/202335操作數(shù)、結(jié)果用原碼表示絕對(duì)值運(yùn)算，符號(hào)單獨(dú)處理被乘數(shù)(B)、累加和(A)取雙符號(hào)位

乘數(shù)末位Cn為判斷位，其狀態(tài)決定下步操作

作n次循環(huán)（累加、右移）4.原碼一位乘法運(yùn)算規(guī)則2.2.2二進(jìn)制乘法運(yùn)算【例】已知X=1001B，Y=-1100B，求X*Y。解:(X)原=00,1001B,(Y)原=1,1100B1/15/202336步數(shù)條件操作AC00.0000.1100

1）Cn=0+0Cn+00.000000.000000.00000.1102）Cn=0+0+00.000000.000000.000000.113）Cn=1+B+00.100100.100100.0100100.14）Cn=1+B+00.100100.110100.01101100XY=-01101100BX0Y0=1(XY)原=1.01101100B1/15/202337二.定點(diǎn)補(bǔ)碼一位乘法1/15/2023381.算法分析

X補(bǔ)=X0.X1X2……Xn（1）Y為正：Y補(bǔ)=0.Y1Y2……Yn

(XY)補(bǔ)=X補(bǔ)(0.Y1Y2……Yn)（2）Y為負(fù)：Y補(bǔ)=1.Y1Y2……YnY=Y補(bǔ)–2=0.Y1Y2……Yn–1XY=X(0.Y1Y2……Yn)-X

(XY)補(bǔ)=X補(bǔ)(0.Y1Y2……Yn)+(-X)補(bǔ)（3）Y符號(hào)任意：

(XY)補(bǔ)=X補(bǔ)(0.Y1Y2……Yn)+(-X)補(bǔ)Y0符號(hào)位一、補(bǔ)碼一位乘法1/15/202339【例1】仿照計(jì)算機(jī)計(jì)算過(guò)程,用補(bǔ)碼乘法計(jì)算x*Y=?假定：X=-0.1101By=-0.1011B則：[x]補(bǔ)=11.0011B[-x]補(bǔ)=00.1101B

[y]補(bǔ)

=1.0101B

1/15/202340步數(shù)條件操作AC

00.0000.0101

1）Cn=1+[x]補(bǔ)Cn+11.001111.001111.10011.0102）Cn=0+0+00.000011.100111.110011.013）Cn=1+[x]補(bǔ)+11.001110.111111.0111111.04）Cn=0+0+00.000011.011111.10111111+00.110100.1000+[-x]補(bǔ)1111[x*Y]補(bǔ)=0.10001111BXY=+0.10001111B1/15/202341

(XY)補(bǔ)=X補(bǔ)(0.Y1Y2……Yn)+(-X)補(bǔ)Y0

=X補(bǔ)(0.Y1Y2……Yn)-X補(bǔ)Y0

=X補(bǔ)(-Y0+2Y1+2Y2+……+2Yn)-1

-2

-n

=X補(bǔ)-Y0+(Y1-2Y1)+(2Y2-2Y2)+…-1

-1-2-(n-1)-n

+(2Yn-2Yn)+0

=X補(bǔ)

(Y1-Y0)+2(Y2-Y1)+2(Y3-Y2)+…-1-2

+2(0

-Yn)-n0

=X補(bǔ)

(Y1-Y0)+2(Y2-Y1)+2(Y3-Y2)+…-1-2

+2(-Yn)-nYn+1附加位，初值為02.展開(kāi)為部分積的累加和形式1/15/2023423.機(jī)器順序執(zhí)行的遞推公式[P0]補(bǔ)=0[P1]補(bǔ)={[P0]補(bǔ)+(YN+1-YN)[X]補(bǔ)}2-1[P2]補(bǔ)={[P1]補(bǔ)+(YN-YN-1)[X]補(bǔ)}2-1…[Pi]補(bǔ)={[Pi-1]補(bǔ)+(YN-I+2-YN-I+1)[X]補(bǔ)}2-1………….[Pn]補(bǔ)={[Pn-1]補(bǔ)+(Y2-Y1)[X]補(bǔ)}2-1∴[x*y]補(bǔ)=[Pn+1]補(bǔ)=[Pn]補(bǔ)+(Y1-Y0)[X]補(bǔ)1/15/202343(1)將部分積初始化為0；(2)參加的數(shù)用補(bǔ)碼表示；(3)A、B取雙符號(hào)位，符號(hào)位參與運(yùn)算；(4)C取單符號(hào)位，符號(hào)參加移位，以決定最后是否修正；(5)乘數(shù)的尾部增加1位符號(hào)位Yn+1（即C末位Cn+1）,

初值為0；CnCn+1組成判斷位，決定運(yùn)算操作；4.Booth公式一位乘法運(yùn)算規(guī)則1/15/202344

YnYn+1(高位)(低位)00011011

1/2A補(bǔ)1/2(A補(bǔ)+X補(bǔ))1/2(A補(bǔ)-X補(bǔ))1/2A補(bǔ)01-10(6)比較相鄰兩位乘數(shù)Yn+1與Yn，決定+X補(bǔ)、-X補(bǔ)或+0。Yn+1-Yn(7)運(yùn)算完成后，部分積右移1位，得到新的部分積；(8)反復(fù)n+1次，但最后一次不移位，結(jié)果即為[X*Y]補(bǔ)操作(A補(bǔ)為部分積)4.Booth公式一位乘法運(yùn)算規(guī)則（續(xù)）1/15/202345【例2】已知X=－0.1101B,Y=－0.1011B,用Booth算法求XY?！窘狻?/p>

初值A(chǔ)=00.0000B,B=[X]補(bǔ)=11.0011B,則[x]補(bǔ)=11.0011B-B=[-X]補(bǔ)=00.1101BC=[Y]補(bǔ)=1.0101B1/15/202346步數(shù)條件操作AC00.00001.0101

1）10-X補(bǔ)Cn+00.110100.110100.011011.01012）01+X補(bǔ)+11.001111.100111.1100111.0103）10-X補(bǔ)+00.110100.100100.01001111.014）01+X補(bǔ)+11.001111.011111.101111111.00

Cn+1CnCn+15）10-X補(bǔ)+00.110100.10001111(XY)補(bǔ)=0.10001111BXY=+0.10001111B1/15/2023472.2.3二進(jìn)制除法運(yùn)算1/15/2023481．定點(diǎn)原碼一位除法有恢復(fù)余數(shù)法和加減交替法兩種方法，在計(jì)算機(jī)中常用的是加減交替法，因?yàn)樗牟僮鞑襟E少，而且也不復(fù)雜。兩個(gè)原碼數(shù)相除，其商的符號(hào)為兩數(shù)符號(hào)的異或值，數(shù)值則為兩數(shù)絕對(duì)值相除后的結(jié)果。

2.2.3二進(jìn)制除法運(yùn)算1/15/202349除法若干余數(shù)與除數(shù)加減、移位。【例】0.10110B÷0.11111B0.1011011010.01111110.11111000111111101010111111101100.00000.0.商：0.10110余數(shù)：0.10110×25實(shí)現(xiàn)除法的關(guān)鍵：比較余數(shù)、除數(shù)絕對(duì)值大小，以決定上商。手工計(jì)算過(guò)程:2.2.3二進(jìn)制除法運(yùn)算1/15/2023501.算法2×余數(shù)-除數(shù)=新余數(shù)為正:夠減,商1。為負(fù):不夠減,商0,恢復(fù)原余數(shù)一、原碼恢復(fù)余數(shù)法

2.規(guī)則：（1）商的符號(hào)位獨(dú)立運(yùn)算，即XsYs；（2）比較被除數(shù)X與除數(shù)Y的大??；若余數(shù)大于等于0，商上1，余數(shù)左移1位；若余數(shù)小于0，商上0，恢復(fù)余數(shù)，余數(shù)左移1位；（3）重復(fù)上述過(guò)程n次（除數(shù)的尾數(shù)位數(shù)），得到商及余數(shù).2.2.3二進(jìn)制除法運(yùn)算1/15/202351【例】被除數(shù)X=0.1011B，除數(shù)Y=0.1101B，

[Y]補(bǔ)=00.1101B，[–Y]補(bǔ)=11.0011B余數(shù)=0.0111B2–4商=0.1101B被除數(shù)(余數(shù))商操作說(shuō)明00101100000開(kāi)始情形+110011+[–Y]補(bǔ)

11111000000不夠減,上商0001101+[Y]補(bǔ)001011恢復(fù)正余數(shù)000101000

11夠減,上商1←01011000000左移110011+[–Y]補(bǔ)00100100001

夠減,上商1←01001000010左移110011+[–Y]補(bǔ)11110100110

不夠減,上商0←01010001100左移

00011101101

夠減,上商1←00101000110左移110011+[–Y]補(bǔ)001101+[Y]補(bǔ)001010恢復(fù)正余數(shù)110011+[–Y]補(bǔ)1/15/2023522.2.4浮點(diǎn)數(shù)的運(yùn)算1/15/202353浮點(diǎn)數(shù):是指小數(shù)點(diǎn)位置可浮動(dòng)的數(shù)據(jù)，通常表示：

N=M*RE

其中N——浮點(diǎn)數(shù)，M——尾數(shù)(純小數(shù))E——階碼(整數(shù))R——“階的基數(shù)(底)”,R為常數(shù),一般為2、8或16。

1.浮點(diǎn)數(shù)的概念2.2.4浮點(diǎn)數(shù)的運(yùn)算1/15/202354一些浮點(diǎn)數(shù)表示方式把尾數(shù)符號(hào)與尾數(shù)放在一起的。1位1位n位m位MSESEMMs——尾數(shù)的符號(hào)位，設(shè)置在最高位上。E——階碼，一般為整數(shù)，其中有一位符號(hào)位，設(shè)置在E的最高位上，用來(lái)表示正階或負(fù)階。常用補(bǔ)碼和移碼表示.M——尾數(shù)，有m位，由Ms和M組成一個(gè)定點(diǎn)小數(shù),常用補(bǔ)碼表示;Ms=0，表示正號(hào);Ms＝1，表示負(fù)號(hào)2.浮點(diǎn)數(shù)的機(jī)內(nèi)表示一般采用以下形式2.2.4浮點(diǎn)數(shù)的運(yùn)算1/15/202355

3.浮點(diǎn)數(shù)規(guī)格化(1)浮點(diǎn)數(shù)規(guī)格化:是指尾數(shù)的第一位為1的浮點(diǎn)數(shù)N1=201×0.1101（√）N2=-201×0.1101（√）N3=211×0.0101(2)規(guī)格化方法:階碼每遞減1次,尾數(shù)的小數(shù)點(diǎn)便右移1位,直到尾數(shù)的第一位是1為止。N3=211×0.0101=210×0.1010N4=20100×0.0011=20100-10×0.1100=20010*0.11002.2.4浮點(diǎn)數(shù)的運(yùn)算1/15/2023564.機(jī)器零機(jī)器零:當(dāng)數(shù)據(jù)小于機(jī)器能表示的最小數(shù)時(shí),稱(chēng)為機(jī)器零。機(jī)器零判別：●當(dāng)浮點(diǎn)數(shù)的尾數(shù)為0，（無(wú)論階碼大小）；或階碼的值比能在機(jī)器中表示的最小值還小時(shí)?！窦次矓?shù)為0,階碼最小。2.2.4浮點(diǎn)數(shù)的運(yùn)算1/15/202357一、浮點(diǎn)數(shù)的加減法運(yùn)算1/15/202358在大型計(jì)算機(jī)和高檔微型機(jī)中，浮點(diǎn)加減法運(yùn)算是由硬件完成的；低檔的微型機(jī)浮點(diǎn)加減法運(yùn)算是由軟件完成；無(wú)論用硬件實(shí)現(xiàn)或由軟件實(shí)現(xiàn)加減法運(yùn)算，基本原理是一致的。在補(bǔ)碼浮點(diǎn)運(yùn)算中，階碼與尾數(shù)可以都用補(bǔ)碼表示。在硬件實(shí)現(xiàn)的運(yùn)算中，階符和數(shù)符采取雙符號(hào)位，正數(shù)數(shù)符用00表示，負(fù)數(shù)數(shù)符用11表示。2.2.4浮點(diǎn)數(shù)的運(yùn)算●浮點(diǎn)數(shù)加減法的運(yùn)算特點(diǎn)1/15/202359一、浮點(diǎn)加減運(yùn)算步驟1、對(duì)階2、尾數(shù)加減法運(yùn)算3、規(guī)格化4、舍入問(wèn)題5、檢查階碼是否溢出1/15/2023601、對(duì)階

該操作是將兩個(gè)加數(shù)的小數(shù)點(diǎn)對(duì)齊。設(shè)X=Mx×2Ex，Y=My×2Ey，求X±Y=？

對(duì)階規(guī)則：是小階向大階看齊對(duì)階：E=Ex-Ey；階碼較小的數(shù)，其尾數(shù)向右移，每右移一位，階碼加“1”，直到兩數(shù)階碼相同為止。這里要注意符號(hào)位擴(kuò)展1/15/202361【例如】[A]補(bǔ)=00,010;00.110110

[B]補(bǔ)=00,100;11.010101↑↑↑↑階階數(shù)尾符碼符數(shù)

其中數(shù)A的階碼小于數(shù)B的階碼，則將數(shù)A的尾數(shù)向右移2位，階碼加“2”，即[A]補(bǔ)=00，100；00.0011011/15/2023622、尾數(shù)加減法運(yùn)算

兩數(shù)階碼對(duì)齊,即可進(jìn)行尾數(shù)運(yùn)算，所求的和的階碼為對(duì)階后的階碼。尾數(shù)運(yùn)算規(guī)則：尾數(shù)連同符號(hào)相加減

尾數(shù)部分求和：[A尾數(shù)]補(bǔ)+[B尾數(shù)]補(bǔ)00.001101+)11.01010111.100010結(jié)果為：[A+B]補(bǔ)=00，100；11.1000101/15/2023633、規(guī)格化

在浮點(diǎn)機(jī)器運(yùn)算中，為了增加有效數(shù)字的位數(shù)，提高機(jī)器運(yùn)算的精確度，都必須將運(yùn)算結(jié)果規(guī)格化。

規(guī)格化的目的：尾數(shù)盡量以絕對(duì)值最大值的形式出現(xiàn)。1/15/202364若尾數(shù)為原碼，其規(guī)格化表示形式為：00.1X2…Xn11.1X2…Xn規(guī)格化的形式符合規(guī)格化左規(guī)并非真正溢出，右規(guī)若尾數(shù)為補(bǔ)碼，通過(guò)運(yùn)算可能出現(xiàn)6種形式為：00.1X2…Xn11.0X2…Xn00.0X2…Xn11.1X2…Xn01.X1X2…Xn10.X1X2…Xn1/15/2023654、舍入問(wèn)題從加法運(yùn)算中看到，當(dāng)尾數(shù)右移時(shí)，末幾位超出機(jī)器允許的位數(shù)而丟失，因此就造成了誤差，通常要進(jìn)行舍入處理。（1）舍入時(shí)應(yīng)滿(mǎn)足兩個(gè)要求：每一次運(yùn)算的結(jié)果要保證不超過(guò)給定的范圍。其次在大量的運(yùn)算過(guò)程中要保證誤差的平衡，即在每一次運(yùn)算時(shí)，使運(yùn)算結(jié)果增加和減少的機(jī)會(huì)是均等的，否則會(huì)產(chǎn)生很大的積累誤差。1/15/202366（2）常用的舍入辦法：“0舍1入”法如超出機(jī)器位數(shù)而丟失的數(shù)字的最高位是“0”，則舍去不管；如最高位是“1”，則將機(jī)器運(yùn)算結(jié)果末尾加1【例】用“0舍1入”法[X]原=0.11011舍入后[X]原=0.1110[X]原=0.11100舍入后[X]原=0.1110[X]補(bǔ)=1.00101舍入后[X]補(bǔ)=1.0011[X]補(bǔ)=1.00100舍入后[X]補(bǔ)=1.00101/15/2023675、檢查階碼是否溢出方法：尾數(shù)規(guī)格化后，由階碼的符號(hào)決定沒(méi)溢出：階碼表示形式：00，XXXX……X：11，XXXX……X上溢：數(shù)據(jù)的絕對(duì)值大于機(jī)器中浮點(diǎn)數(shù)所表示的最大值階碼表示形式：01，XXXX……X機(jī)器停止運(yùn)算，做溢出中斷處理下溢：數(shù)據(jù)的絕對(duì)值小于機(jī)器中浮點(diǎn)數(shù)所表示的最小值階碼表示形式：10，XXXX……X機(jī)器不做溢出處理，而是按機(jī)器零處理。1/15/202368【例】已知：X＝2010.0.11011011，y＝2100.(-0.10101100),求X+Y1）對(duì)階ΔE＝[Ex]補(bǔ)+[-EY]補(bǔ)=00,010+11,100=11,110=-2X階碼小，Mx右移2位,[Mx]補(bǔ)=00.0011011011則X補(bǔ)=00,100；00.0011011011下劃線上的數(shù)是右移出去而保留的附加位。解：X和Y在機(jī)器中的浮點(diǎn)補(bǔ)碼表示形式(雙符號(hào)位)階符階碼數(shù)符尾數(shù)

X補(bǔ)=00，010；00.11011011Y補(bǔ)=00，100；11.01010100

1/15/202369

2）尾數(shù)相加

[Mx]補(bǔ)+[MY]補(bǔ)=00.00110110

11+11.01010100=11.1000101011[X+Y]補(bǔ)=00，100；11.10001010113）規(guī)格化

左規(guī)，尾數(shù)左移1位，階碼-1

結(jié)果：

[X+Y]補(bǔ)=00，011；11.0001

0101

10；1/15/2023704）舍人

附加位最高位為1，在所得結(jié)果的最低位+1，

[M]補(bǔ)=11.00010110M=-0.11101010[X+Y]補(bǔ)=00，011；11.00010110X+Y=2011.（-0.11101010）5）判溢出

階碼符號(hào)位為00，故不溢出、最終結(jié)果為：

X+Y=2011.（-0.11101010）1/15/202371二、浮點(diǎn)數(shù)的乘除法運(yùn)算1/15/202372浮點(diǎn)數(shù)的乘除法運(yùn)算X*Y=（Mx*My）*2（Ex+Ey）浮點(diǎn)乘除運(yùn)算規(guī)則：階碼相加，尾數(shù)相乘浮點(diǎn)乘除運(yùn)算步驟：1、求階碼2、尾數(shù)相乘3、規(guī)格化4、舍入問(wèn)題5、檢查階碼是否溢出1/15/2023731.檢測(cè)操作數(shù)是否為0，若其中一個(gè)操作數(shù)為0，則結(jié)果為0；2.階碼相加：階符相同的加可能會(huì)溢出，若溢出，則作溢出處理；上溢階碼表示形式：01，XXXX……X，機(jī)器停止運(yùn)算，做溢出中斷處理下溢階碼表示形式：10，XXXX……X，機(jī)器不做溢出處理，而是按機(jī)器零處理。一、浮點(diǎn)數(shù)的乘法運(yùn)算規(guī)則1/15/2023743.尾數(shù)相乘；相乘前不需對(duì)階。4.尾數(shù)乘積規(guī)格化一般左規(guī),若左規(guī)發(fā)生階碼下溢，做機(jī)器零處理5.舍入處理：運(yùn)算過(guò)程中保留右移中移出的若干高位的值，然而再按某種規(guī)則用這些位上的值修正尾數(shù)。6.判溢出一、浮點(diǎn)數(shù)的乘法運(yùn)算規(guī)則(續(xù)）1/15/202375第2.3節(jié)數(shù)據(jù)校驗(yàn)碼1/15/202376奇偶校驗(yàn)碼的校驗(yàn)方法，應(yīng)用場(chǎng)合CRC碼的編碼、譯碼方法、應(yīng)用場(chǎng)合海明碼的編碼、譯碼方法、應(yīng)用場(chǎng)合◆奇偶校驗(yàn)碼

◆循環(huán)冗余校驗(yàn)碼（CRC碼）（★）

◆海明碼教學(xué)內(nèi)容掌握重點(diǎn)2.3數(shù)據(jù)校驗(yàn)碼1/15/202377數(shù)據(jù)校驗(yàn)碼：是一種常用的帶有發(fā)現(xiàn)某些錯(cuò)誤或自動(dòng)改錯(cuò)能力的數(shù)據(jù)編碼方法。編碼系統(tǒng)的碼距：一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼（碼字）之間最少變化的二進(jìn)制位數(shù)（bit）,稱(chēng)為這個(gè)編碼系統(tǒng)的碼字的碼距。即:整個(gè)編碼系統(tǒng)中任意兩個(gè)碼字的的最小距離。一、基本理論2.3數(shù)據(jù)校驗(yàn)碼1/15/202378兩個(gè)碼字最小值為1，故這個(gè)系統(tǒng)的碼距為1。如果任何碼字中一位或多位被顛倒了，結(jié)果這個(gè)碼字就不能與其它有效信息區(qū)分開(kāi)。[例如]如果傳送信息為001，誤接收的信息為011.會(huì)被認(rèn)為是合法的碼字?信息序列二進(jìn)碼字a２a１a０００００１００１２０１０３０１１４１００５１０１６１１０７１１１如圖所示的編碼系統(tǒng)2.3數(shù)據(jù)校驗(yàn)碼1/15/202379碼字間的最小距離可以增加到2。在這個(gè)系統(tǒng)中，偶數(shù)個(gè)（2或4）差錯(cuò)無(wú)法發(fā)現(xiàn)。為使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò),碼間最小距離必須至少是“3”.[例如]如果傳送信息是1001，誤收為1011,接收機(jī)發(fā)生了一個(gè)差錯(cuò)，但無(wú)法糾正。假定只有一個(gè)數(shù)位是錯(cuò)的,可能的正確碼字有哪些?信息序列二進(jìn)碼字a3a2a1a0０0000１1001２1010３0011４1100５0101６0110７1111如圖所示的編碼系統(tǒng)2.3數(shù)據(jù)校驗(yàn)碼1/15/202380●碼距≥2的數(shù)據(jù)校驗(yàn)碼，開(kāi)始具有檢錯(cuò)能力；

●為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò),碼間最小距離必須至少是3。

●碼距越大，檢錯(cuò)糾錯(cuò)能力就越強(qiáng)，但數(shù)據(jù)冗余也越大，編碼效率低。

●碼距的選擇要取決于特定系統(tǒng)的參數(shù)。碼距檢錯(cuò)

糾錯(cuò)12345670

01

02或12加12加23加23加32.3數(shù)據(jù)校驗(yàn)碼1/15/202381通過(guò)函數(shù)f對(duì)數(shù)據(jù)進(jìn)行計(jì)算，以產(chǎn)生一種代碼，代碼和數(shù)據(jù)都被存儲(chǔ)，如果原數(shù)據(jù)字長(zhǎng)為M位，校驗(yàn)碼長(zhǎng)為K位，則實(shí)際存儲(chǔ)的字長(zhǎng)應(yīng)為M+K位。加進(jìn)冗余碼，當(dāng)合法數(shù)據(jù)編碼出現(xiàn)某些錯(cuò)誤時(shí)，就成為非法編碼?？梢酝ㄟ^(guò)檢測(cè)編碼的合法性來(lái)達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。二、實(shí)現(xiàn)原理2.3數(shù)據(jù)校驗(yàn)碼1/15/202382當(dāng)原先存儲(chǔ)的字讀出時(shí)，這個(gè)代碼用于檢錯(cuò)和糾錯(cuò)，在M位數(shù)據(jù)中產(chǎn)生一組新的K位代碼，與取出的代碼進(jìn)行比較：結(jié)果一致，無(wú)差錯(cuò)，取出的數(shù)據(jù)位傳送出去；檢測(cè)到差錯(cuò)，并可以糾正，數(shù)據(jù)位和糾錯(cuò)位一起送入糾正器，然后產(chǎn)生一組正確的M位數(shù)據(jù)位；檢測(cè)到差錯(cuò)，但無(wú)法糾正，報(bào)告出錯(cuò)。2.3數(shù)據(jù)校驗(yàn)碼1/15/2023832.3.1奇偶校驗(yàn)碼

一、奇偶校驗(yàn)碼的特點(diǎn)開(kāi)銷(xiāo)最小；增加二進(jìn)制傳輸系統(tǒng)最小距離的簡(jiǎn)單和廣泛采用的方法；適用于并行數(shù)據(jù)傳送；碼距為2，可以檢測(cè)1位錯(cuò)誤（或奇數(shù)位錯(cuò)誤）。但不能確定是哪一位錯(cuò),也不能發(fā)現(xiàn)偶數(shù)個(gè)位錯(cuò)。常用于存儲(chǔ)器讀寫(xiě)檢查，或ASCII字符傳送過(guò)程中的檢查。

2.3數(shù)據(jù)校驗(yàn)碼1/15/202384二、奇偶校驗(yàn)碼的編碼方法不管數(shù)據(jù)位長(zhǎng)度多少，校驗(yàn)位只有一位。奇校驗(yàn):數(shù)據(jù)位和校驗(yàn)位一起所含“1”的個(gè)數(shù)為奇數(shù)。偶校驗(yàn):數(shù)據(jù)位和校驗(yàn)位一起所含“1”的個(gè)數(shù)為偶數(shù)。校驗(yàn):對(duì)奇校驗(yàn)，如接收端收到是偶碼，表示傳送有誤，因此可發(fā)現(xiàn)一位錯(cuò)(奇位錯(cuò))。1/15/202385[例]

數(shù)據(jù)奇校驗(yàn)的編碼偶校驗(yàn)的編碼00000000 10000000000000000001010100 001010100 10101010001111111 001111111 1011111111/15/202386三、實(shí)現(xiàn)原理使碼距由1增加到2。通常是為一個(gè)字節(jié)補(bǔ)充一個(gè)二進(jìn)制位（稱(chēng)為校驗(yàn)位）；設(shè)置校驗(yàn)位的值為0或1，使字節(jié)的8位和該校驗(yàn)位含有1值的個(gè)數(shù)為奇數(shù)或偶數(shù)。進(jìn)行校驗(yàn)時(shí)用奇校驗(yàn)或偶校驗(yàn)。依據(jù)8位的數(shù)據(jù)位中1值的個(gè)數(shù)確定校驗(yàn)位的值；2.3數(shù)據(jù)校驗(yàn)碼1/15/202387四、實(shí)現(xiàn)方式D7D6D5D4D3D2D1D0D校偶校驗(yàn)位形成

=D0⊕D1⊕D2⊕…⊕D7奇校驗(yàn)位形成

=NOT（D0⊕D1⊕D2⊕…⊕D7）偶校驗(yàn)出錯(cuò)

=D0⊕D1⊕D2⊕…⊕D7⊕D校奇校驗(yàn)出錯(cuò)=NOT（D0⊕D1⊕D2⊕…⊕D7⊕D校奇性檢測(cè)等效于所有碼字的模二加，并能夠由所有碼字的異或運(yùn)算來(lái)確定。奇偶校驗(yàn)位可由硬件電路（異或門(mén)）產(chǎn)生：1/15/202388五、分組奇偶校驗(yàn)碼

實(shí)際中經(jīng)常采用縱橫都加校驗(yàn)的奇偶校驗(yàn)位的編碼系統(tǒng)--分組奇偶校驗(yàn)碼(交叉奇偶校驗(yàn))。某一個(gè)系統(tǒng)，它傳輸若干個(gè)長(zhǎng)度為m位的信息。如果把這些信息都編成每組n個(gè)信息的分組，則在這些不同的信息間，也如對(duì)單個(gè)信息一樣，能夠作奇偶校驗(yàn)。n個(gè)信息分組排列成矩形式樣，以橫向奇偶（HP）及縱向奇偶（VP）的形式編出奇偶校驗(yàn)位。

2.3數(shù)據(jù)校驗(yàn)碼1/15/202389縱橫奇偶校驗(yàn)的分組奇偶校驗(yàn)碼

結(jié)論：分組奇偶校驗(yàn)碼不僅能檢測(cè)許多形式的錯(cuò)誤。并且在給定的行或列中產(chǎn)生孤立的錯(cuò)誤時(shí)，還可對(duì)該錯(cuò)誤進(jìn)行糾正。

m位數(shù)字橫向奇偶位n個(gè)碼字a1a2…am-1amHP1b1b2…bm-1bmHP2c1c2…cm-1cmHP3………………n1n2…nm-1nmHPn縱向奇偶位VP1VP2…VPm-1VPmHPn+12.3數(shù)據(jù)校驗(yàn)碼1/15/202390[例]由6個(gè)字符的7位ASCII編碼排列，再加上水平垂直奇偶校驗(yàn)位構(gòu)成下列矩陣求:1）X1X2X3X4;X5X6X7X8;X9X10X11X12的比特分別為_(kāi)_2）Y1和Y2處的字符分別為_(kāi)_和__。1）X1X2X3X4=1110;X5X6X7X8=1000;X9X10X11X12=10112）字符Y1的ASCII碼49H,Y1即是“I”(“D”的ASCII碼是44H);字符Y2的ASCII碼37H,Y2即是“7”(“3”的ASCII碼是33H）字符7位ASCII碼HP30X1X200110Y1100100X31+X41010110Y201X5X61111D100X710X80=0X9111X1011VP00111X111X12“A”的ASCII碼是41H“0”的ASCII碼是30H1/15/2023912.3.1循環(huán)冗余校驗(yàn)(CRC)碼一、循環(huán)冗余校驗(yàn)(CRC)碼的特點(diǎn)

CRC碼可以發(fā)現(xiàn)并糾正信息串行讀寫(xiě)、存儲(chǔ)或傳送過(guò)程中出現(xiàn)的一位、多位錯(cuò)誤；適用于串行數(shù)據(jù)傳送（磁盤(pán)、通訊）；在磁介質(zhì)存儲(chǔ)器讀寫(xiě)和計(jì)算機(jī)之間通信方面得到廣泛應(yīng)用。CRC也是給信息碼加上幾位校驗(yàn)碼，以增加整個(gè)編碼系統(tǒng)的碼距和查錯(cuò)糾錯(cuò)能力。

2.3數(shù)據(jù)校驗(yàn)碼1/15/202392在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼又叫（N，K）碼。校驗(yàn)碼的基本原理編碼組成:K位（信息位）R位（校驗(yàn)位）二、循環(huán)冗余校驗(yàn)碼基本原理2.3數(shù)據(jù)校驗(yàn)碼發(fā)送信息用信息多項(xiàng)式C(X)表示；將C(x)左移R位，則可表示成C(x)*XR，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)C(x)*XR除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。

1/15/202393三、多項(xiàng)式與二進(jìn)制數(shù)碼的關(guān)系

多項(xiàng)式包括：生成多項(xiàng)式G(x)和信息多項(xiàng)式C(x)。它們與二進(jìn)制數(shù)碼的直接對(duì)應(yīng)關(guān)系為：x的最高冪次對(duì)應(yīng)二進(jìn)制數(shù)的最高位，以下各位對(duì)應(yīng)多項(xiàng)式的各冪次；有此冪次項(xiàng)對(duì)應(yīng)1，無(wú)此冪次項(xiàng)對(duì)應(yīng)0。x的最高冪次為R,轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)有R+1位。[例]生成多項(xiàng)式為G(x)=x4+x3+x+1，可轉(zhuǎn)換為二進(jìn)制數(shù)碼為11011。發(fā)送信息位1111轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為：C(x)=x3+x2+x+1。2.3數(shù)據(jù)校驗(yàn)碼1/15/202394常用的對(duì)應(yīng)于不同碼制的生成多項(xiàng)式

NK碼距dG(x)多項(xiàng)式G(x)743x3+x+11011743x3+x2+11101734x4+x3+x2+111101734x4+x2+x+11011115113x4+x+1100111575x8+x7+x6+x4+111101000131263x5+x2+110010131215x10+x9+x8+x6+x5+x3+11110110100163573x6+x+1100001163515x12+x10+x5+x4+x2+1101000011010110411024

x16+x15+x2+1110000000000001011/15/202395四、生成多項(xiàng)式生成多項(xiàng)式是接受方和發(fā)送方的一個(gè)約定，在整個(gè)傳輸過(guò)程中，這個(gè)數(shù)始終保持不變。發(fā)送方利用生成多項(xiàng)式對(duì)信息多項(xiàng)式做模2除生成校驗(yàn)碼。接受方利用生成多項(xiàng)式對(duì)收到的編碼多項(xiàng)式做模2除檢測(cè)和確定錯(cuò)誤位置。2.3數(shù)據(jù)校驗(yàn)碼生成多項(xiàng)式：對(duì)于一個(gè)給定的（N，K）碼，生成多項(xiàng)式G(x)最高次冪為R=N-K；根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。1/15/202396[結(jié)論]生成多項(xiàng)式應(yīng)滿(mǎn)足的條件生成多項(xiàng)式的最高位和最低位必須為1。當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做模2除后應(yīng)該使余數(shù)不為0。不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。對(duì)余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。

2.3數(shù)據(jù)校驗(yàn)碼1/15/202397五、CRC碼的編碼方法模：計(jì)量器的容量（M表示）[例]4位二進(jìn)制數(shù),從0-15,再加1,記數(shù)值又為0，故：M=24=16模2運(yùn)算：指以按位模2相加為基礎(chǔ)的四則運(yùn)算，運(yùn)算時(shí)不考慮進(jìn)位和借位。(1)模2加減（按位加，可用異或邏輯實(shí)現(xiàn)）0土0=0，0土1＝1，1土0＝1，1土1＝0。

兩個(gè)相同的數(shù)據(jù)的模2和為0。2.3數(shù)據(jù)校驗(yàn)碼1/15/2023980.1010×101101000001010100010(2)模2乘法——按模2加求部分積之和。2.3數(shù)據(jù)校驗(yàn)碼1/15/202399[例]

1111000÷1101111100001010110111010100001000111011010111(3)模2除法

1101商=1011；余數(shù)=111按模2減求部分余數(shù)。每求一位商應(yīng)使部分余數(shù)減少一位。上商的原則是:

當(dāng)部分余數(shù)的首位為1時(shí)，商取1；當(dāng)部分余數(shù)的首位為0時(shí)，商取0。當(dāng)部分的余數(shù)的位數(shù)小于除數(shù)的位數(shù)時(shí)，該余數(shù)即為最后余數(shù)。2.3數(shù)據(jù)校驗(yàn)碼1/15/2023100六、CRC碼的生成步驟

1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*XR。3、C(x)*XR/G(X)的二進(jìn)制數(shù)（做模2除），得到R位的余數(shù)。4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。2.3數(shù)據(jù)校驗(yàn)碼1/15/2023101【例】假設(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。

4位的原始報(bào)文為1010，求編碼后的報(bào)文。

解：

1、將生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)1011。2、生成多項(xiàng)式有4位（R+1），要把原始報(bào)文C(x)左移3位（R）變成10100003、C(X)*X4／G(X)=1010000／1011

1001---商011----余數(shù)（校驗(yàn)位）4、編碼后的報(bào)文（CRC碼）：1010000+

0111010011

1/15/2023102出錯(cuò)模式改變了C(x)（碼字），只會(huì)改變表中碼字內(nèi)容，不改變余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系。

[例]已知G(x)=1011，C(x)=1010收到的CRC碼字余數(shù)出錯(cuò)位碼位A6A5A4A3A2A1A0正確1010011000無(wú)錯(cuò)誤101001000111010001010210101111003101101101141000011110511100111116001001110171/15/2023103七.糾錯(cuò)方法[例]第一位出錯(cuò)，余數(shù)為001，依次補(bǔ)0作模2除得到余數(shù)為：010，100，0ll…，反復(fù)循環(huán)。如果循環(huán)碼有1位出錯(cuò)，如果對(duì)余數(shù)補(bǔ)0用G(x)作模2除，將得到一個(gè)不為0的余數(shù)。一個(gè)有趣的結(jié)果：各次余數(shù)將按上頁(yè)圖順序循環(huán)根據(jù)不同的余數(shù)來(lái)糾正不同的出錯(cuò)位,當(dāng)最高位變成101時(shí)（出錯(cuò)位移到A6),則最高位取反糾錯(cuò)。2.3數(shù)據(jù)校驗(yàn)碼1/15/2023104八、通信與網(wǎng)絡(luò)中常用的CRC

突發(fā)錯(cuò)誤：幾乎是連續(xù)發(fā)生的一串錯(cuò)，突發(fā)長(zhǎng)度就是指從出錯(cuò)的第一位到出錯(cuò)的最后一位的長(zhǎng)度。一般取r=16，標(biāo)準(zhǔn)的16位生成多項(xiàng)式有

CRC-16＝x16+x15+x2+1

一般情況下，對(duì)r=16的情況，就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于16的突發(fā)錯(cuò)以及99．997%的突發(fā)長(zhǎng)度為17的突發(fā)錯(cuò)和99．998%的突發(fā)長(zhǎng)度大于17的突發(fā)錯(cuò)。所以CRC碼的檢錯(cuò)能力還是很強(qiáng)的。

2.3數(shù)據(jù)校驗(yàn)碼1/15/2023105【思考題】某CRC碼的生成多項(xiàng)式

G(x)＝x3+x2+1,用此生成多項(xiàng)式產(chǎn)生的冗余位，加在信息位后形成CRC碼。若發(fā)送信息位1111和1100則它的CRC碼分別為＿A＿和＿B＿。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯(cuò)的CRC碼，例如碼字＿C＿、＿D＿、和＿E＿A:①1111100②1111101③1111110④1111111B:①1100100②1100101③1100110④1100111C~E:①0000000②1111101③0010111④0011010⑤1000110⑥1001111⑦1010001⑧10110001/15/2023106解：A：G(x)＝1101，C(x)＝1111C(x)*23÷G(x)＝1111000÷1101＝1011余111得到的CRC碼為1111111B：G(x)＝1101，C(x)＝1100C(x)*2