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

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

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

H7H6H5H4

H3H2

H1

海明碼：P5

D7D7D6D5

P4

D4D3D2P3D1P2P1海明碼的特點(diǎn)每個(gè)校驗(yàn)位由其本身校驗(yàn)；每個(gè)數(shù)據(jù)位由若干校驗(yàn)位校驗(yàn).海明碼的各位與校驗(yàn)位的關(guān)系被校驗(yàn)的每一位的位號(hào)=校驗(yàn)它的各校驗(yàn)位的位號(hào)之和海明碼位號(hào)數(shù)據(jù)位校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)關(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海明碼各校驗(yàn)位的生成海明碼位號(hào)數(shù)據(jù)位校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)關(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海明碼各校驗(yàn)位的生成若采用偶校驗(yàn)碼則P1~P4分別為與它相關(guān)的數(shù)據(jù)位的偶校驗(yàn)位若采用奇校驗(yàn)碼則P1~P4分別為與它相關(guān)的數(shù)據(jù)位的奇校驗(yàn)位校驗(yàn)位可校驗(yàn)的有關(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海明碼各校驗(yàn)位的生成按偶校驗(yàn)寫出校驗(yàn)方程為：

S1=P1D1D2D4D5D7

S2=P2D1D3D4D6D7

S3=P3D2D3D4D8

S4=P4D5D6D7D8S5=P5D1D2D3D5D6D8校驗(yàn)位可校驗(yàn)的有關(guān)數(shù)據(jù)位P11，2，4，5，7P21，3，4，6，7P32，3，4，8P45，6，7，8求得使各方程成立的Pi值即為海明碼校驗(yàn)位的值例：有8位信息代碼：10101100，求它的海明碼，用偶校驗(yàn)。解：信息代碼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海明碼的檢錯(cuò)和糾錯(cuò)S5～S1的值檢錯(cuò)和糾錯(cuò)情況00000無錯(cuò)僅有一位不為0某一校驗(yàn)位出錯(cuò)或三位海明碼同時(shí)出錯(cuò)有兩位不為0兩位海明碼同時(shí)出錯(cuò)，此時(shí)只能檢錯(cuò)，有三位不為0一位信息位出錯(cuò)或三位校驗(yàn)位同時(shí)出錯(cuò)，出錯(cuò)位的位號(hào)由S4～S1編碼值指明，此時(shí)可以糾錯(cuò)。有四位或五位不為0出錯(cuò)情況嚴(yán)重，系統(tǒng)工作可能出現(xiàn)故障，應(yīng)檢查系統(tǒng)硬件的正確性海明碼的檢錯(cuò)和糾錯(cuò)舉例假設(shè)前例中的海明碼1101001101011傳送后，若H11位發(fā)生了錯(cuò)誤，變成了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，看成一個(gè)“指誤字”，因?yàn)?011B=11D，說明H11出了錯(cuò).糾錯(cuò)：將H11取反值即可。1101001101011循環(huán)冗余碼用于多位串行數(shù)據(jù)傳送中的檢錯(cuò)糾錯(cuò)處理在

k

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

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

數(shù)據(jù)位

校驗(yàn)位kr應(yīng)滿足關(guān)系——2r≥r+k+1循環(huán)冗余碼的運(yùn)算基礎(chǔ)——模2運(yùn)算以2為模，按位相加的運(yùn)算，在運(yùn)算中不考慮借位和進(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的編碼原理 任何一個(gè)二進(jìn)制序列中的各位看成一個(gè)多項(xiàng)式的系數(shù)如：11011×X3+1×X2+0×X1+1×X0(k,n)碼——n是有效數(shù)據(jù)的位數(shù)，r是校驗(yàn)位位數(shù)，總長k=n+r位。M(x)——待編碼的有效信息的多項(xiàng)式表示。M(x)×Xr——將M(x)左移r位得到多項(xiàng)式，使低r位全為零。G(x)——生成多項(xiàng)式，G(X)最高項(xiàng)的指數(shù)決定了r的位數(shù)循環(huán)冗余碼—編碼原理這時(shí)將余數(shù)R(X)與M(x)×Xr相加，就得到n+r位CRC編碼：

M(x)×Xr

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

+R(x)因?yàn)椤皟蓚€(gè)相同數(shù)據(jù)的模2和為零”，即R(x)+R(x)=0，所以

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

除以生成多項(xiàng)式G(x)

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

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

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

M(x)×X3=1100000(3)用G(X)對(duì)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

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

1100011/G(X)=1110……001

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

數(shù)據(jù)位

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