計算機(jī)組成原理：2-5-1 數(shù)據(jù)的機(jī)器層次表示

復(fù)習(xí)思考題5若某漢字的國標(biāo)碼=3547H，則其機(jī)內(nèi)碼=B5C7H

，區(qū)位碼=1527H。奇校驗碼可以檢查出奇數(shù)位錯誤，偶校驗碼可以檢查出偶數(shù)位錯誤。（錯）交叉校驗的橫向校驗和縱向校驗必須是同為奇校驗或同為偶校驗。（對）交叉校驗可以檢出一個數(shù)據(jù)塊同一字節(jié)的雙錯、糾正一位的錯誤。（對）第2章數(shù)據(jù)的機(jī)器層次表示2.1數(shù)值數(shù)據(jù)的表示2.2機(jī)器數(shù)的定點表示與浮點表示2.3非數(shù)值數(shù)據(jù)的表示2.4十進(jìn)制數(shù)和數(shù)串的表示2.5現(xiàn)代微型計算機(jī)系統(tǒng)中的數(shù)據(jù)表示舉例2.6數(shù)據(jù)校驗碼2.6海明校驗碼海明校驗碼是一種多重奇偶校驗，要使編碼能糾正一位出錯并能發(fā)現(xiàn)兩位錯，則校驗碼必須具有N位數(shù)據(jù)位每一位的位置狀態(tài)K位校驗位每一位的位置狀態(tài)無錯情況的狀態(tài)校驗碼中校驗位數(shù)的確定應(yīng)滿足關(guān)系2K-1≥N+K+1N1~34~1011~2526~56……Kmin4567……數(shù)據(jù)位校驗位NK校驗位在海明碼中的分布校驗位的分布規(guī)則：把位號數(shù)是2的權(quán)值的那些位，分配做奇偶校驗位假設(shè)數(shù)據(jù)位N=8，校驗位位數(shù)K=5,故海明碼的總位數(shù)為13。它們的排列關(guān)系可表示為：海明碼位號:H13H12H11H10H9H8

H7H6H5H4

H3H2

H1

海明碼：P5

D7D7D6D5

P4

D4D3D2P3D1P2P1海明碼的特點每個校驗位由其本身校驗；每個數(shù)據(jù)位由若干校驗位校驗.海明碼的各位與校驗位的關(guān)系被校驗的每一位的位號=校驗它的各校驗位的位號之和海明碼位號數(shù)據(jù)位校驗位參與校驗的校驗位位號關(guān)系H1P111=1H2P222=2H3D11,23=1+2H4P344=4H5D21,45=1+4H6D32,46=2+4H7D41,2,47=1+2+4H8P488=8H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8H12D84,812=4+8海明碼各校驗位的生成海明碼位號數(shù)據(jù)位校驗位參與校驗的校驗位位號關(guān)系H3D11,23=1+2H5D21,45=1+4H6D32,46=2+4H7D41,2,47=1+2+4H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8與P1有關(guān)的數(shù)據(jù)位1，2，4，5，7與P2有關(guān)的數(shù)據(jù)位1，3，4，6，7與P3有關(guān)的數(shù)據(jù)位2，3，4，8與P4有關(guān)的數(shù)據(jù)位5，6，7，8海明碼各校驗位的生成若采用偶校驗碼則P1~P4分別為與它相關(guān)的數(shù)據(jù)位的偶校驗位若采用奇校驗碼則P1~P4分別為與它相關(guān)的數(shù)據(jù)位的奇校驗位校驗位可校驗的有關(guān)數(shù)據(jù)位P11，2，4，5，7P21，3，4，6，7P32，3，4，8P45，6，7，8

P1=D1D2D4D5D7P2=D1D3D4D6D7

P3=D2D3D4D8

P4=D5D6D7D8P5=D1D2D3D5D6D8海明碼各校驗位的生成按偶校驗寫出校驗方程為：

S1=P1D1D2D4D5D7

S2=P2D1D3D4D6D7

S3=P3D2D3D4D8

S4=P4D5D6D7D8S5=P5D1D2D3D5D6D8校驗位可校驗的有關(guān)數(shù)據(jù)位P11，2，4，5，7P21，3，4，6，7P32，3，4，8P45，6，7，8求得使各方程成立的Pi值即為海明碼校驗位的值例：有8位信息代碼：10101100，求它的海明碼，用偶校驗。解：信息代碼8位N=8K=5海明碼共N+K=8+5=13位13121110987654321

P1P2D1

P3D2

D3

D4

P4D5

D6

D70101100P1：1，2，4，5，7001001P2：1，3，4，6，7011101P3:2，3，4，80111P4：5，6，7，80100

1

1

1

0海明碼P5D8

111P5：1，2，3，5，6，800101111海明碼的檢錯和糾錯S5～S1的值檢錯和糾錯情況00000無錯僅有一位不為0某一校驗位出錯或三位海明碼同時出錯有兩位不為0兩位海明碼同時出錯，此時只能檢錯，有三位不為0一位信息位出錯或三位校驗位同時出錯，出錯位的位號由S4～S1編碼值指明，此時可以糾錯。有四位或五位不為0出錯情況嚴(yán)重，系統(tǒng)工作可能出現(xiàn)故障，應(yīng)檢查系統(tǒng)硬件的正確性海明碼的檢錯和糾錯舉例假設(shè)前例中的海明碼1101001101011傳送后，若H11位發(fā)生了錯誤，變成了1111001101011P1P2D1

P3D2

D3

D4

P4D5

D6

D71101100P1，1，2，4，5，7001011P2，1，3，4，6，7011111P3，2，3，4，80110P4，5，6，7，80111

1

1

1

0海明碼P5D8

111P5，1，2，3，5，6，800101011S1：S2：S3:S4：S5：11101S4S3S2S1=1011，看成一個“指誤字”，因為1011B=11D，說明H11出了錯.糾錯：將H11取反值即可。1101001101011循環(huán)冗余碼用于多位串行數(shù)據(jù)傳送中的檢錯糾錯處理在

k

位數(shù)據(jù)位串行移位輸出的過程中，用電路形成r個校驗位的值，跟隨在數(shù)據(jù)位之后傳送走。在接收端再對k+r

位的代碼進(jìn)行合法與出錯檢查，若可能則自動改錯。

數(shù)據(jù)位

校驗位kr應(yīng)滿足關(guān)系——2r≥r+k+1循環(huán)冗余碼的運算基礎(chǔ)——模2運算以2為模，按位相加的運算，在運算中不考慮借位和進(jìn)位

模2加減法：0±0=0，0±1=1，1±0=1，1±1=0

模2乘法：按模2加求部分積之和

模2除法：按模2減求部分余數(shù)

1010×10110100000101010

00101000010111010100000100110101…商…余數(shù)循環(huán)冗余碼—編碼原理CRC的編碼原理 任何一個二進(jìn)制序列中的各位看成一個多項式的系數(shù)如：11011×X3+1×X2+0×X1+1×X0(k,n)碼——n是有效數(shù)據(jù)的位數(shù)，r是校驗位位數(shù)，總長k=n+r位。M(x)——待編碼的有效信息的多項式表示。M(x)×Xr——將M(x)左移r位得到多項式，使低r位全為零。G(x)——生成多項式，G(X)最高項的指數(shù)決定了r的位數(shù)循環(huán)冗余碼—編碼原理這時將余數(shù)R(X)與M(x)×Xr相加，就得到n+r位CRC編碼：

M(x)×Xr

+R(x)=G(x)×Q(x)+R(x)

+R(x)因為“兩個相同數(shù)據(jù)的模2和為零”，即R(x)+R(x)=0，所以

M(x)×Xr+R(x)=G(x)×Q(x)可以看出，所求得的CRC碼是一個可被G(X)表示的數(shù)碼除盡的數(shù)碼。假設(shè)M(x)×Xr

除以生成多項式G(x)

，用R(x)表示余數(shù)，用Q(x)表示商：循環(huán)冗余碼—編碼舉例

例設(shè)有效信息位是M(X)=1100，生成多項式G(X)=1011，試求M(X)的CRC碼。解：(1)因為G(X)有4位長，r+1=4

所以r=3(2)M(X)左移r=3位，

M(x)×X3=1100000(3)用G(X)對M(x)×Xr作“模2除”

1100000/1011=1110……010

R(X)=010(4)M(x)×X3

與R(X)作“模2加”，即可求得它的CRC編碼

M(x)×X3+R(X)=1100000+010=1100010

因為k=7、n=4，所以編好的CRC碼又稱為(7，4)碼。CRC的譯碼及糾錯CRC碼傳送到目標(biāo)部件，用約定的多項式G(x)對收到的CRC碼進(jìn)行“模2除”，若余數(shù)為0，則表明該CRC校驗碼正確；若余數(shù)不為0，則表明有錯，不同的出錯位，其余數(shù)是不同的?？赏ㄟ^查G(X)出錯表定對出錯位定位，再將它求反即可糾正如前例，若接收的為1100011，則

1100011/G(X)=1110……001

查表得a1位出錯，將它求反即可出錯位R(X)a1001a2010a3100a4011a5110a6111a7101

數(shù)據(jù)位

校驗位a7a6a5a4a3a2a1生成多項式應(yīng)滿足下列要求：(1)任何一位發(fā)生錯誤，都應(yīng)使余數(shù)不為零；(2)不同位發(fā)生錯誤，都應(yīng)使余數(shù)不同；(3)用余數(shù)補零，繼續(xù)作“模2除”，應(yīng)使余數(shù)循環(huán)。常用的C