計(jì)算機(jī)組成與系統(tǒng)結(jié)構(gòu)課件：計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)表示

計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)表示2.1概述2.2定點(diǎn)數(shù)2.3浮點(diǎn)數(shù)2.4BCD碼2.5非數(shù)值數(shù)據(jù)2.6檢錯(cuò)與糾錯(cuò)碼

2.1概述

2.1.1數(shù)的進(jìn)制及轉(zhuǎn)換

常見(jiàn)的進(jìn)位計(jì)數(shù)制有十進(jìn)制、二進(jìn)制、八進(jìn)制和十六進(jìn)制。十進(jìn)制數(shù)中有0~9十個(gè)數(shù)碼,其計(jì)數(shù)特點(diǎn)及進(jìn)位原則為“逢十進(jìn)一”。十進(jìn)制的基數(shù)為10,位權(quán)為10i(i是整數(shù))。十進(jìn)制數(shù)的后面常用字母D標(biāo)記或不加標(biāo)記。計(jì)算機(jī)中常用的計(jì)數(shù)制還有二進(jìn)制、八進(jìn)制、十六進(jìn)制。

任何一種進(jìn)位計(jì)數(shù)制表示的數(shù)都可以寫(xiě)成按權(quán)展開(kāi)的多項(xiàng)式之和,即任意一個(gè)r進(jìn)制數(shù)N可表示為

其中,Di為該數(shù)制采用的基本數(shù)碼,ri

是權(quán),r是基數(shù)。數(shù)值數(shù)據(jù)是表示數(shù)量多少和數(shù)值大小的數(shù)據(jù),即在數(shù)軸上能找到其對(duì)應(yīng)點(diǎn)的數(shù)據(jù)。

各種數(shù)值數(shù)據(jù)在計(jì)算機(jī)中表示的形式稱(chēng)為機(jī)器數(shù)。機(jī)器數(shù)對(duì)應(yīng)的實(shí)際數(shù)值稱(chēng)為數(shù)的真值。

2.1.2無(wú)符號(hào)數(shù)與有符號(hào)數(shù)的定義

1.無(wú)符號(hào)數(shù)

所謂無(wú)符號(hào)數(shù),即沒(méi)有符號(hào)的數(shù),數(shù)中的每一位均用來(lái)表示數(shù)值。所以8位二進(jìn)制無(wú)符號(hào)數(shù)所表示的數(shù)值范圍是0~255,而16位無(wú)符號(hào)數(shù)的表示范圍為0~65535。

2.有符號(hào)數(shù)

由于機(jī)器無(wú)法直接識(shí)別“+”(正)、“-”(負(fù))符號(hào),而“正”“負(fù)”恰好是兩種截然不同的狀態(tài),因此若用“0”表示“正”,用“1”表示“負(fù)”,則符號(hào)可被數(shù)字化,再按規(guī)定將符號(hào)放在有效數(shù)字的前面就組成了有符號(hào)數(shù)。

2.1.3定點(diǎn)數(shù)與浮點(diǎn)數(shù)的定義

1.定點(diǎn)數(shù)

在機(jī)器數(shù)表示中,若約定小數(shù)點(diǎn)的位置固定不變,則稱(chēng)為定點(diǎn)數(shù)。有兩種形式的定點(diǎn)數(shù),即定點(diǎn)整數(shù)(純整數(shù),規(guī)定小數(shù)點(diǎn)在數(shù)據(jù)最低有效數(shù)位之后)和定點(diǎn)小數(shù)(純小數(shù),規(guī)定小數(shù)點(diǎn)在數(shù)據(jù)最高有效數(shù)位之前),如圖2.1所示。圖2.1有符號(hào)定點(diǎn)數(shù)的表示形式

2.浮點(diǎn)數(shù)

基數(shù)為2的數(shù)F的浮點(diǎn)表示為

其中,M稱(chēng)為尾數(shù),E稱(chēng)為階碼。尾數(shù)為帶符號(hào)的純小數(shù),階碼為帶符號(hào)的純整數(shù)。

按式(2.2)表示的數(shù)據(jù)既可以是純整數(shù),也可以是純小數(shù),還可以是同時(shí)含有整數(shù)和小數(shù)的數(shù)據(jù),其小數(shù)點(diǎn)的位置是不固定的,故稱(chēng)為浮點(diǎn)數(shù)。計(jì)算機(jī)中常用的一種浮點(diǎn)數(shù)的編碼格式如圖2.2所示,其中數(shù)符(即數(shù)據(jù)的符號(hào))就是尾符(即尾數(shù)的符號(hào))。圖2.2浮點(diǎn)數(shù)的編碼格式之一

2.2定點(diǎn)數(shù)

2.2.1原碼原碼是機(jī)器數(shù)中最簡(jiǎn)單的一種表示形式,其符號(hào)位為0表示正數(shù),符號(hào)位為1表示負(fù)數(shù),數(shù)值位即真值的絕對(duì)值。

1.整數(shù)原碼的定義

根據(jù)圖2.1(a),若整數(shù)用二進(jìn)制n位表示,則整數(shù)原碼的定義為

式中,X為真值,n-1為整數(shù)數(shù)值位的位數(shù)。

原碼可用定義表示,也可用符號(hào)位后面緊跟數(shù)的絕對(duì)值表示。

例2.1當(dāng)X=+35或X=-35時(shí),若采用8位二進(jìn)制編碼,其原碼如何表示?

解當(dāng)X=+35時(shí),有

當(dāng)X=-35時(shí),有

從本例可以看到,符號(hào)位總是在最高位。原碼又稱(chēng)作帶符號(hào)的絕對(duì)值表示,即在符號(hào)的后面跟著的就是該數(shù)據(jù)的絕對(duì)值。

2.小數(shù)原碼的定義

根據(jù)圖2.1(b),若小數(shù)用二進(jìn)制n位表示,則小數(shù)原碼的定義為

根據(jù)式(2.4),純小數(shù)的原碼可以表示為

值得注意的是,在計(jì)算機(jī)中小數(shù)點(diǎn)是隱含的,是不用出現(xiàn)的,上面編碼中出現(xiàn)小數(shù)點(diǎn)是為了強(qiáng)調(diào)小數(shù)點(diǎn)的位置。在本書(shū)各章節(jié)中,所有編碼中若出現(xiàn)小數(shù)點(diǎn),其作用與此處相同,都僅僅是為了提示。

例2.2若純小數(shù)X=0.46875或X=-0.46875,試用包括符號(hào)位在內(nèi)的8位定點(diǎn)原碼表示。

解當(dāng)X=0.46875時(shí),有

當(dāng)X=-0.46875時(shí),有

3.原碼的特點(diǎn)

(1)數(shù)值原碼表示法簡(jiǎn)單直觀,但加減運(yùn)算很麻煩。

(2)對(duì)于數(shù)值0,用原碼表示不是唯一的。以8位原碼表示,有

(3)n位原碼(包括一位符號(hào)位)純整數(shù)可表示的數(shù)值范圍為-(2n-1-1)~+(2n-1-1),純小數(shù)可表示的數(shù)值范圍為-(1-2-(n-1))~+(1-2-(n-1))。

2.2.2補(bǔ)碼

1.補(bǔ)數(shù)的概念

在日常生活中,常會(huì)遇到補(bǔ)數(shù)的概念。例如,當(dāng)前時(shí)鐘指針指示在6點(diǎn),欲使它指示3點(diǎn),既可按順時(shí)針?lè)较驅(qū)⒎轴樲D(zhuǎn)9圈,也可按逆時(shí)針?lè)较驅(qū)⒎轴樲D(zhuǎn)3圈,其結(jié)果是一致的。由于時(shí)鐘的時(shí)針轉(zhuǎn)一圈能指示12個(gè)小時(shí),因此時(shí)鐘指針兩個(gè)方向轉(zhuǎn)動(dòng)產(chǎn)生的效果在數(shù)學(xué)上稱(chēng)為模12運(yùn)算,寫(xiě)作mod12。

2.補(bǔ)碼的定義

1)整數(shù)補(bǔ)碼的定義根據(jù)圖2.1(a),若整數(shù)用二進(jìn)制n位表示,則整數(shù)補(bǔ)碼的定義為

由式(2.5)可以看到,對(duì)正數(shù)來(lái)說(shuō),補(bǔ)碼與原碼的定義完全一樣。

2)小數(shù)補(bǔ)碼的定義

若小數(shù)用二進(jìn)制n位表示,則小數(shù)補(bǔ)碼的定義為

根據(jù)式(2.6),純小數(shù)的補(bǔ)碼同樣可以表示為

同樣地,小數(shù)點(diǎn)是隱含的。

例2.4若純小數(shù)X=0.46875或X=-0.46875,試用包括符號(hào)位的8位定點(diǎn)補(bǔ)碼表示。

解當(dāng)X=0.46875時(shí),有

對(duì)于負(fù)數(shù)純小數(shù),構(gòu)成補(bǔ)碼表示所采用的方法與整數(shù)一樣。因此,當(dāng)X=-0.46875時(shí),[X]補(bǔ)=1.1000100。

3.補(bǔ)碼的特點(diǎn)

(1)n位補(bǔ)碼表示的整數(shù)數(shù)值范圍為-2n-1~+(2n-1-1),n位補(bǔ)碼表示的小數(shù)數(shù)值范圍為-1~+(1-2-n+1)。

(2)0的表示是唯一的。以8位小數(shù)編碼為例,有

(3)變形碼。當(dāng)模數(shù)為4時(shí),可形成雙符號(hào)位補(bǔ)碼,如X=-0.1001B,對(duì)mod22而言,有

這種雙符號(hào)位補(bǔ)碼又叫作變形補(bǔ)碼,它在階碼運(yùn)算和溢出判斷中有其特殊作用。

(4)求補(bǔ)運(yùn)算。許多處理器中設(shè)置有求補(bǔ)指令,其功能是對(duì)操作數(shù)取負(fù)數(shù)(即正數(shù)變負(fù)數(shù),負(fù)數(shù)變正數(shù))?？梢圆捎蒙鲜龅呢?fù)數(shù)補(bǔ)碼的3種編碼方法之一實(shí)現(xiàn)。

(5)簡(jiǎn)化加減法。利用補(bǔ)碼實(shí)現(xiàn)兩數(shù)相加是很方便的,補(bǔ)碼加法的運(yùn)算規(guī)則為

即兩數(shù)和的補(bǔ)碼就等于兩數(shù)補(bǔ)碼之和。

因此,減法運(yùn)算就可以用加法運(yùn)算來(lái)實(shí)現(xiàn),即

這樣在運(yùn)算器中就可以不設(shè)置減法器,從而簡(jiǎn)化了運(yùn)算器的結(jié)構(gòu)。

(6)算術(shù)或邏輯左移。對(duì)補(bǔ)碼表示的數(shù)值做算術(shù)或邏輯左移一位(即編碼各位依次向左移動(dòng)一位,最高位移出,最低位補(bǔ)0),如果移位結(jié)果沒(méi)有超出所規(guī)定的數(shù)值范圍,則相當(dāng)于該數(shù)值乘2。

(7)算術(shù)右移。對(duì)補(bǔ)碼表示的數(shù)值做算術(shù)右移一位(即編碼各位依次向右移動(dòng)一位,最低位移出,最高位保持原符號(hào)不變),相當(dāng)于該數(shù)值除以2。

2.2.3反碼

反碼通常用來(lái)作為由原碼求補(bǔ)碼或者由補(bǔ)碼求原碼的中間過(guò)渡。

1.反碼的定義

1)整數(shù)反碼的定義

整數(shù)反碼的定義為

2)小數(shù)反碼的定義

小數(shù)反碼的定義為

2.2.4移碼

1.移碼的由來(lái)

當(dāng)真值用補(bǔ)碼表示時(shí),由于符號(hào)位和數(shù)值部分一起編碼,與習(xí)慣上的表示法不同,因此人們很難從補(bǔ)碼的形式上直接判斷其真值的大小。例如:

十進(jìn)制數(shù)X=+31,對(duì)應(yīng)的二進(jìn)制數(shù)為+11111,若用8位表示,則[X]補(bǔ)=00011111；

十進(jìn)制數(shù)X=-31,對(duì)應(yīng)的二進(jìn)制數(shù)為-11111,若用8位表示,則[X]補(bǔ)=11100001。

上述補(bǔ)碼表示中,從代碼形式看,符號(hào)位也是一位二進(jìn)制數(shù)。如果按這8位二進(jìn)制代碼比較其大小,會(huì)得出11100001>00011111,而實(shí)際情況恰恰相反。

2.移碼的定義

由于移碼多用于浮點(diǎn)數(shù)中表示階碼,均為整數(shù),因此這里只介紹定點(diǎn)整數(shù)的移碼表示。當(dāng)用包括符號(hào)位在內(nèi)的n位字長(zhǎng)時(shí),整數(shù)移碼的定義為

要獲得整數(shù)的移碼表示,可以利用定義計(jì)算,也可以先求出該數(shù)的補(bǔ)碼后將符號(hào)位取反。

3.移碼的特點(diǎn)

(1)移碼就是在其真值上加一個(gè)常數(shù)2n-1。移碼在數(shù)軸上所表示的范圍恰好對(duì)應(yīng)其真值在數(shù)軸上的范圍向軸的正方向移動(dòng)2n-1個(gè)數(shù)據(jù),如圖2.3所示。圖2.3移碼在數(shù)軸上的表示

(2)移碼與補(bǔ)碼的關(guān)系。由圖2.4可知,移碼與補(bǔ)碼間的關(guān)系十分密切,只要將補(bǔ)碼的符號(hào)位取反,補(bǔ)碼就轉(zhuǎn)換成了相應(yīng)的移碼;同樣,只要將移碼的符號(hào)位取反,移碼就轉(zhuǎn)換成了相應(yīng)的補(bǔ)碼。進(jìn)而可以想到,只要字長(zhǎng)相同,補(bǔ)碼與移碼所能表示的數(shù)值范圍是相同的。圖2.4移碼與補(bǔ)碼的關(guān)系

(3)移碼碼值的大小反映了數(shù)值的大小,因此,正數(shù)移碼的碼值一定大于負(fù)數(shù)移碼的碼值。也就是說(shuō),大碼值所表示的數(shù)值一定大于小碼值所表示的數(shù)值。

由于具有上述突出優(yōu)點(diǎn),移碼目前已被廣泛采用。

2.2.5不同編碼的比較

原碼表示很直觀。若采用原碼做乘除運(yùn)算,可取其絕對(duì)值(原碼的數(shù)值部分)直接運(yùn)算,并按同號(hào)相乘除取正,異號(hào)相乘除取負(fù)的原則,單獨(dú)處理符號(hào)位,比較方便。但原碼加減運(yùn)算時(shí),其運(yùn)算比較復(fù)雜。例如,當(dāng)兩個(gè)操作數(shù)符號(hào)不同且要作加法運(yùn)算時(shí),先要判斷兩個(gè)數(shù)的絕對(duì)值的大小,然后用絕對(duì)值大的數(shù)減去絕對(duì)值小的數(shù),結(jié)果的符號(hào)以絕對(duì)值大的數(shù)為準(zhǔn),運(yùn)算步驟既復(fù)雜又費(fèi)時(shí),且本來(lái)是加法運(yùn)算卻要用減法器實(shí)現(xiàn)。

而機(jī)器數(shù)采用補(bǔ)碼,找到一個(gè)與負(fù)數(shù)等價(jià)的正數(shù)來(lái)代替該負(fù)數(shù),即可用加法代替減法操作,這樣在計(jì)算機(jī)中就可以只設(shè)加法器。但是根據(jù)補(bǔ)碼的定義,在形成補(bǔ)碼的過(guò)程中又出現(xiàn)了減法,因此引入了反碼,作為由原碼求補(bǔ)碼或者由補(bǔ)碼求原碼的中間過(guò)渡,這樣由真值通過(guò)原碼求補(bǔ)碼就可避免減法運(yùn)算。

因此,原碼、反碼、補(bǔ)碼、移碼的特點(diǎn)可歸納如下:

(1)當(dāng)真值為正時(shí),原碼、補(bǔ)碼和反碼的表示形式均相同,即符號(hào)位用“0”表示,數(shù)值部分與真值相同。

(2)當(dāng)真值為負(fù)時(shí),原碼、補(bǔ)碼和反碼的表示形式不同,但其符號(hào)位都用“1”表示,而數(shù)值部分的關(guān)系為:反碼是原碼“每位取反”,補(bǔ)碼是反碼“加1”,補(bǔ)碼是原碼“求反加1”。

(3)移碼較為特殊,當(dāng)符號(hào)位為“0”時(shí),表示真值為負(fù)數(shù);當(dāng)符號(hào)位為“1”時(shí),表示真值為正數(shù)。移碼與補(bǔ)碼編碼僅符號(hào)位相反。

表2.1列出了8位字長(zhǎng)的二進(jìn)制編碼與無(wú)符號(hào)整數(shù)及定點(diǎn)整數(shù)的原碼、補(bǔ)碼、反碼和移碼所代表真值的對(duì)應(yīng)關(guān)系。

2.3浮點(diǎn)數(shù)

2.3.1浮點(diǎn)數(shù)的表示方法由于計(jì)算機(jī)字長(zhǎng)的限制,當(dāng)需要表示的數(shù)據(jù)有很大的數(shù)值范圍(如電子的質(zhì)量為9×10-28克,太陽(yáng)的質(zhì)量為2×1033克)時(shí),它們不能直接用定點(diǎn)小數(shù)或定點(diǎn)整數(shù)表示,而必須用浮點(diǎn)數(shù)表示。由于計(jì)算機(jī)采用二進(jìn)制,所以浮點(diǎn)數(shù)的一般表示形式為式(2.2)。

例如,二進(jìn)制數(shù)F=11.0101,用浮點(diǎn)數(shù)可表示為下列不同形態(tài),即

其中,尾數(shù)與階碼均用二進(jìn)制數(shù)表示,基數(shù)(為2)用十進(jìn)制數(shù)表示。這里可以看到,一個(gè)包含整數(shù)與小數(shù)的數(shù)據(jù)用浮點(diǎn)數(shù)表示時(shí)有多種形態(tài),那么計(jì)算機(jī)中采用哪種形態(tài)來(lái)表示這個(gè)浮點(diǎn)數(shù)呢?

1.浮點(diǎn)數(shù)的編碼表示

根據(jù)浮點(diǎn)數(shù)的一般表示式(2.2),只要確定了尾數(shù)M和階碼E(基數(shù)是固定值),浮點(diǎn)數(shù)即被確定。但同一個(gè)浮點(diǎn)數(shù)又有多種表現(xiàn)形態(tài),如上述例子,所以需要對(duì)M和E的形態(tài)做出合理選擇,浮點(diǎn)數(shù)才能在計(jì)算機(jī)中有效編碼。

浮點(diǎn)數(shù)編碼的規(guī)則如下:

(1)尾數(shù)M必須為小數(shù),用n+1位有符號(hào)定點(diǎn)小數(shù)表示,可以采用的編碼有原碼、補(bǔ)碼。階碼E必須為整數(shù),用k+1位有符號(hào)定點(diǎn)整數(shù)表示,可以采用的編碼有原碼、補(bǔ)碼、移碼。浮點(diǎn)數(shù)編碼位數(shù)為m=(n+1)+(k+1)。

(2)浮點(diǎn)數(shù)編碼格式有多種,使用較多的格式如圖2.2和圖2.5所示,格式的選擇可由計(jì)算機(jī)設(shè)計(jì)人員決定。圖2.5浮點(diǎn)數(shù)的編碼格式之二

需要強(qiáng)調(diào)的是:

(1)階碼是整數(shù),其位數(shù)k+1決定了浮點(diǎn)數(shù)表示的數(shù)值范圍,也就是決定了數(shù)據(jù)的大小,或小數(shù)點(diǎn)在數(shù)據(jù)中的真實(shí)位置。階符決定階碼的正負(fù)。

(2)尾數(shù)是小數(shù),其位數(shù)n+1決定了浮點(diǎn)數(shù)的精度。如果尾數(shù)采用小數(shù)且位數(shù)n足夠長(zhǎng),則當(dāng)浮點(diǎn)數(shù)運(yùn)算需要對(duì)尾數(shù)運(yùn)算結(jié)果舍入時(shí),造成的數(shù)據(jù)精度損失會(huì)比較小。

(3)尾數(shù)的符號(hào)表示浮點(diǎn)數(shù)的正負(fù)。

2.非規(guī)格化浮點(diǎn)數(shù)

當(dāng)對(duì)尾數(shù)M只要求是小數(shù)而無(wú)其他限制時(shí),此時(shí)的浮點(diǎn)數(shù)被稱(chēng)為非規(guī)格化浮點(diǎn)數(shù)。設(shè)浮點(diǎn)數(shù)為非規(guī)格化數(shù),階碼數(shù)值位取k位,階符為1位,且采用補(bǔ)碼表示,尾數(shù)數(shù)值位取n位,尾符為1位,同樣采用補(bǔ)碼表示,則階碼和尾數(shù)可以表示的數(shù)值范圍如表2.2所示。

此時(shí),在數(shù)軸上表示的非規(guī)格化浮點(diǎn)數(shù)范圍如圖2.6所示。因?yàn)榉且?guī)格化浮點(diǎn)數(shù)的尾數(shù)可以為0,也就是非規(guī)格化浮點(diǎn)數(shù)可以為0,因此非規(guī)格化浮點(diǎn)數(shù)范圍為圖2.6非規(guī)格化浮點(diǎn)數(shù)的數(shù)值范圍

3.規(guī)格化浮點(diǎn)數(shù)

由于非規(guī)格化浮點(diǎn)數(shù)對(duì)小數(shù)形式的尾數(shù)沒(méi)有進(jìn)一步的限制,因此造成同一數(shù)據(jù)有不同的編碼,使數(shù)據(jù)表示的通用性變差。為了使有限字長(zhǎng)的二進(jìn)制尾數(shù)能表示更多的有效數(shù)位,同時(shí)使浮點(diǎn)數(shù)有統(tǒng)一的表示形式,浮點(diǎn)數(shù)通常采用規(guī)格化形式來(lái)表示。

所謂規(guī)格化浮點(diǎn)數(shù),就是將尾數(shù)的絕對(duì)值限定在規(guī)定的數(shù)值范圍內(nèi),即1/2≤M<1。要使尾數(shù)的絕對(duì)值在此范圍內(nèi),通過(guò)改變小數(shù)點(diǎn)的位置(相應(yīng)地改變階碼)便可以做到。

若尾數(shù)M用補(bǔ)碼表示,則當(dāng)M≥0時(shí),規(guī)格化尾數(shù)的形式必須為

其中,×為任意二進(jìn)制值。

當(dāng)M<0時(shí),規(guī)格化尾數(shù)的形式必須為

其中,×為任意二進(jìn)制值。

根據(jù)規(guī)格化浮點(diǎn)數(shù)的定義,可以得到規(guī)格化尾數(shù)的數(shù)值范圍如表2.3所示。

對(duì)于規(guī)格化浮點(diǎn)數(shù)來(lái)說(shuō),其階碼所表示的數(shù)值范圍與非規(guī)格化浮點(diǎn)數(shù)的是一樣的。因此,可以確定規(guī)格化浮點(diǎn)數(shù)所能表示的數(shù)值范圍如圖2.7所示。圖2.7規(guī)格化浮點(diǎn)數(shù)的數(shù)值范圍

比較圖2.6和圖2.7可以發(fā)現(xiàn),非規(guī)格化浮點(diǎn)數(shù)和規(guī)格化浮點(diǎn)數(shù)所能表示的數(shù)值范圍的主要不同是絕對(duì)值最小的有效數(shù)值。由圖2.7可知,規(guī)格化浮點(diǎn)數(shù)的數(shù)值范圍如下:

當(dāng)浮點(diǎn)數(shù)階碼大于最大階碼時(shí),稱(chēng)為“上溢”,此時(shí)機(jī)器停止運(yùn)算,進(jìn)行溢出中斷處理;當(dāng)浮點(diǎn)數(shù)階碼小于最小階碼時(shí),稱(chēng)為“下溢”,此時(shí)“溢出”的數(shù)的絕對(duì)值很小,通常將尾數(shù)各位強(qiáng)置為零,按機(jī)器零處理,機(jī)器可以繼續(xù)運(yùn)行。圖2.7表示了浮點(diǎn)數(shù)所能表示的數(shù)值范圍及溢出的情況。

一旦浮點(diǎn)數(shù)的位數(shù)確定后,不同的階碼和尾數(shù)位數(shù)劃分將直接影響浮點(diǎn)數(shù)的表示范圍和精度,所以需要合理分配階碼和尾數(shù)的位數(shù)。利用數(shù)值的浮點(diǎn)數(shù)表示,可實(shí)現(xiàn)用有限字長(zhǎng)的二進(jìn)制編碼表示更大的數(shù)值范圍。

4.規(guī)格化處理

浮點(diǎn)數(shù)在運(yùn)算前和運(yùn)算后,若其尾數(shù)不是規(guī)格化數(shù),就要通過(guò)修改階碼并同時(shí)左右移動(dòng)尾數(shù)使其變成規(guī)格化數(shù)。將非規(guī)格化數(shù)轉(zhuǎn)換成規(guī)格化數(shù)的過(guò)程叫作規(guī)格化。

當(dāng)尾數(shù)M用二進(jìn)制補(bǔ)碼編碼時(shí),規(guī)格化數(shù)應(yīng)符合[M]補(bǔ)=0.1××…×和[M]補(bǔ)=1.0××…×的規(guī)定。規(guī)格化時(shí),尾數(shù)左移1位,階碼減1,這種規(guī)格化叫作向左規(guī)格化,簡(jiǎn)稱(chēng)左規(guī);尾數(shù)右移1位,階碼加1,這種規(guī)格化叫作向右規(guī)格化,簡(jiǎn)稱(chēng)右規(guī)。

5.定點(diǎn)數(shù)和浮點(diǎn)數(shù)的比較

(1)當(dāng)浮點(diǎn)計(jì)算機(jī)和定點(diǎn)計(jì)算機(jī)中數(shù)據(jù)的位數(shù)相同時(shí),浮點(diǎn)數(shù)的表示范圍比定點(diǎn)數(shù)大得多。

例如,對(duì)于16位二進(jìn)制編碼,無(wú)符號(hào)數(shù)的范圍為0~65535,補(bǔ)碼定點(diǎn)整數(shù)的范圍為-32768~+32767。對(duì)于浮點(diǎn)數(shù),可有多種表示方案。假定階碼7位(含階符1位),用移碼表示,尾數(shù)9位(含數(shù)符1位),用補(bǔ)碼表示,則該非規(guī)格化浮點(diǎn)數(shù)所能表示的數(shù)值范圍是-263~+(1-2-8)×263?？梢?jiàn),同樣字長(zhǎng)的浮點(diǎn)數(shù)所能表示的數(shù)值范圍要大得多。

(2)當(dāng)浮點(diǎn)數(shù)為規(guī)格化數(shù)時(shí),其精度比相同位數(shù)的定點(diǎn)數(shù)高。

(3)浮點(diǎn)數(shù)運(yùn)算分為階碼部分和尾數(shù)部分,而且運(yùn)算結(jié)果要求規(guī)格化,故浮點(diǎn)運(yùn)算步驟比定點(diǎn)運(yùn)算步驟多,運(yùn)算速度比定點(diǎn)低,運(yùn)算電路比定點(diǎn)復(fù)雜。

(4)在溢出的判斷方法上,浮點(diǎn)數(shù)對(duì)規(guī)格化數(shù)的階碼進(jìn)行判斷,而定點(diǎn)數(shù)對(duì)數(shù)值本身進(jìn)行判斷。

總之,浮點(diǎn)數(shù)在數(shù)的表示范圍、數(shù)的精度、溢出處理和程序編程方面(不取比例因子)均優(yōu)于定點(diǎn)數(shù)。但在運(yùn)算規(guī)則、運(yùn)算速度及硬件成本方面又不如定點(diǎn)數(shù)。因此,究竟選用定點(diǎn)數(shù)還是浮點(diǎn)數(shù),應(yīng)根據(jù)具體應(yīng)用綜合考慮。一般來(lái)說(shuō),通用的大型計(jì)算機(jī)大多采用浮點(diǎn)數(shù),或同時(shí)采用定點(diǎn)數(shù)和浮點(diǎn)數(shù);小型、微型及某些專(zhuān)用機(jī)、控制機(jī)則大多采用定點(diǎn)數(shù)。當(dāng)需要作浮點(diǎn)運(yùn)算時(shí),可通過(guò)軟件實(shí)現(xiàn),也可外加浮點(diǎn)擴(kuò)展硬件(如協(xié)處理器)來(lái)實(shí)現(xiàn)。

例2.8將十進(jìn)制數(shù)x=+13/128寫(xiě)成二進(jìn)制定點(diǎn)數(shù)和浮點(diǎn)數(shù)(尾數(shù)數(shù)值部分取7位,階碼數(shù)值部分取7位,階符和數(shù)符各取1位,階碼采用移碼,尾數(shù)用補(bǔ)碼表示),并分別寫(xiě)出該數(shù)的定點(diǎn)數(shù)和浮點(diǎn)數(shù)的編碼(采用圖2.2所示的編碼格式)。圖2.8例2.8中浮點(diǎn)數(shù)的表示形式

例2.9設(shè)浮點(diǎn)數(shù)字長(zhǎng)為16位,其中階碼為6位(含1位階符),尾數(shù)為10位(含1位數(shù)符),階碼用移碼,尾數(shù)用補(bǔ)碼,寫(xiě)出十進(jìn)制數(shù)x=-(53/512)對(duì)應(yīng)的規(guī)格化浮點(diǎn)數(shù)編碼(采用圖2.5所示的編碼格式)。圖2.9例2.9中浮點(diǎn)數(shù)的表示形式

例2.10已知規(guī)格化浮點(diǎn)數(shù)字長(zhǎng)16位,其中7位階碼(含一位階符),用移碼表示,9位尾數(shù)(含一位數(shù)符),用補(bǔ)碼表示,其格式及編碼值如圖2.10所示,請(qǐng)寫(xiě)出該數(shù)的真值。圖2.10例2.10中浮點(diǎn)數(shù)的編碼

解該浮點(diǎn)數(shù)尾數(shù)為1.01011001,真值為-0.10100111。階碼為1000111,真值為7,因此浮點(diǎn)數(shù)的真值為

2.3.2IEEE754標(biāo)準(zhǔn)

1985年,IEEE發(fā)表了一份關(guān)于單精度和雙精度浮點(diǎn)數(shù)的表示標(biāo)準(zhǔn),這個(gè)標(biāo)準(zhǔn)官方稱(chēng)為IEEE7541985。以后又不斷加以發(fā)展,SUN公司于2005年推出《數(shù)值計(jì)算指南》(中譯本名),對(duì)該標(biāo)準(zhǔn)進(jìn)行了更加詳細(xì)和深入的討論,給出了多種格式及程序。因此,《數(shù)值計(jì)算指南》更加全面、實(shí)用。目前IEEE754標(biāo)準(zhǔn)已獲得了廣泛的認(rèn)可,并已用于當(dāng)前所有處理器和浮點(diǎn)協(xié)處理器中。

IEEE754規(guī)定了單精度和雙精度兩種基本的浮點(diǎn)格式以及雙精度擴(kuò)展等多種浮點(diǎn)格式。常用的IEEE754格式參數(shù)如表2.4所示。

1.單精度浮點(diǎn)數(shù)

1)編碼IEEE754標(biāo)準(zhǔn)規(guī)定,單精度浮點(diǎn)數(shù)的真值一般表示為

IEEE754單精度浮點(diǎn)數(shù)的編碼格式如圖2.11所示。其編碼格式由三個(gè)字段構(gòu)成:數(shù)符s為1位,尾數(shù)編碼f為23位,階碼編碼e為8位(含1位階符),每字段的位模式如表2.5所示。圖2.11IEEE754單精度浮點(diǎn)數(shù)的編碼格式

由表2.5可以看到,正規(guī)數(shù)尾數(shù)有效數(shù)字的前導(dǎo)位(小數(shù)點(diǎn)左側(cè)的位)為1,與23位尾數(shù)一起提供了24位的精度。次正規(guī)數(shù)有效數(shù)字的前導(dǎo)位為0,在IEEE754標(biāo)準(zhǔn)中,單精度格式次正規(guī)數(shù)也稱(chēng)為單精度格式非規(guī)格化數(shù)。表中符號(hào)u為任意值。

2)說(shuō)明

根據(jù)上述描述,可以得到關(guān)于IEEE754標(biāo)準(zhǔn)單精度浮點(diǎn)數(shù)的如下結(jié)論:

(1)由于規(guī)定階碼真值E=e-127,并且0<e<255(即規(guī)定編碼e在+1~+254內(nèi)為正規(guī)數(shù)),因此階碼真值E的取值范圍為-126~+127。

(2)所能表示的正規(guī)數(shù)范圍:正數(shù)為+2+127×(1+1-2-23)~+2-126×(1+0),負(fù)數(shù)為-2+127×(1+1-2-23)~-2-126×(1+0)。

(3)當(dāng)e=0或e=255時(shí),在IEEE754標(biāo)準(zhǔn)中表示特殊的數(shù)。

例2.11利用IEEE754標(biāo)準(zhǔn)將十進(jìn)制數(shù)176.0625表示為單精度浮點(diǎn)數(shù)。．

解首先將該十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù),有

對(duì)二進(jìn)制數(shù)規(guī)格化,有

(1)單精度浮點(diǎn)數(shù)的23位尾數(shù)f為01100000001000000000000;

(2)單精度浮點(diǎn)數(shù)階碼真值E=e-127=7,即e=(7+127)10=(134)10=(10000110)2,則e就是階碼編碼;

(3)將(176.0625)10表示為IEEE754標(biāo)準(zhǔn)的單精度浮點(diǎn)數(shù),有

例2.12若浮點(diǎn)數(shù)x的IEEE754編碼為(41360000)16,求其浮點(diǎn)數(shù)的十進(jìn)制值。解將十六進(jìn)制數(shù)展開(kāi)為二進(jìn)制數(shù),有

2.對(duì)雙精度浮點(diǎn)數(shù)的說(shuō)明

下面簡(jiǎn)要說(shuō)明一下IEEE754標(biāo)準(zhǔn)雙精度浮點(diǎn)數(shù)。

(1)階碼真值E的取值范圍為-1022~+1023,將其偏移+1023即得編碼e,e編碼值為+1~+2046。

(2)雙精度浮點(diǎn)規(guī)格化數(shù)表示N為

(3)所能表示的規(guī)格化數(shù)范圍:正數(shù)為+2+1023×(1+1-2-52)~+2-1022×(1+0),負(fù)數(shù)為-2+1023×(1+1-2-52)~-2-1022×(1+0)。

(4)當(dāng)e=0或e=2047時(shí),在IEEE754標(biāo)準(zhǔn)中表示特殊的數(shù)。

2.4BCD碼

在計(jì)算機(jī)中,采用4位二進(jìn)制編碼來(lái)表示1位十進(jìn)制數(shù),這種編碼稱(chēng)為BCD碼(Binary-CodedDecimal,二十進(jìn)制數(shù))。4位二進(jìn)制有16種編碼,從中取出10種表示十進(jìn)制數(shù)的0~9十個(gè)數(shù)字,有多種方案。因此有多種BCD碼,其中使用最多的是8421碼。

在8421碼中,表示1位十進(jìn)制數(shù)的4位二進(jìn)制編碼,從最高位到最低位的權(quán)值依次為8、4、2、1。因此可用0000、0001、0010、…、1001這十個(gè)編碼分別表示十進(jìn)制數(shù)0、1、2、…、9,剩余的6個(gè)編碼對(duì)8421碼而言是非法的,是不允許出現(xiàn)的。

例如十進(jìn)制數(shù)49,用8421碼表示為01001001。

8421碼為有權(quán)碼,即4個(gè)二進(jìn)制位上有確定的權(quán)值。其他的有權(quán)碼還有5421碼、2421碼、5211碼、4311碼、8421碼等。另外還有無(wú)權(quán)碼,即二進(jìn)制各位上沒(méi)有確定的權(quán)值,如余3碼、格雷碼等。

2.5非數(shù)值數(shù)據(jù)

2.5.1ASCII碼現(xiàn)代計(jì)算機(jī)不僅處理數(shù)值領(lǐng)域的問(wèn)題,而且處理大量非數(shù)值領(lǐng)域的問(wèn)題。這樣,必然要引入文字、字母以及某些專(zhuān)用符號(hào),以便表示文字語(yǔ)言、邏輯語(yǔ)言等信息。例如,人機(jī)交互信息時(shí)使用英文字母、標(biāo)點(diǎn)符號(hào)、十進(jìn)制數(shù)以及諸如$、%、+等符號(hào)。然而,計(jì)算機(jī)只能處理二進(jìn)制數(shù)據(jù),上述信息應(yīng)用到計(jì)算機(jī)時(shí),都必須表示成二進(jìn)制數(shù)據(jù),即字符信息也要用數(shù)據(jù)表示,稱(chēng)為符號(hào)數(shù)據(jù)。

ASCII碼編碼格式如圖2.12所示,低4位組d3d2d1d0用作行編碼,高3位組d6d5d4用作列編碼,可表示128個(gè)符號(hào)。ASCII編碼表見(jiàn)表2.6。圖2.12ASCII碼的編碼格式

字符串是指連續(xù)的一串字符。通常方式下,它們占用主存中連續(xù)的多個(gè)字節(jié)單元,每個(gè)字節(jié)單元存儲(chǔ)一個(gè)字符。當(dāng)主存字由2個(gè)或4個(gè)字節(jié)組成時(shí),在同一個(gè)主存字中,既可按從低位字節(jié)向高位字節(jié)的順序存放字符串內(nèi)容,也可按從高位字節(jié)向低位字節(jié)的順序存放字符串內(nèi)容。這兩種存放方式都是常用方式。

2.5.2漢字編碼

英文是一種拼音文字,只需要配備26個(gè)字母鍵,并規(guī)定26個(gè)字母的編碼(比如通用的ASCII碼)就能方便地輸入英文信息了。漢字字形結(jié)構(gòu)復(fù)雜,僅部首就有數(shù)百種,漢字的字?jǐn)?shù)也很多,因此漢字的計(jì)算機(jī)處理技術(shù)遠(yuǎn)比拼音文字復(fù)雜。

從ASCII、GB2312—80、GBK到GB18030—2005,這些字符集是向下兼容的,即同一個(gè)字符在這些方案中總是有相同的編碼,后面的標(biāo)準(zhǔn)支持更多的字符。中英文被統(tǒng)一處理,區(qū)分中文、英文的方法是看最高字節(jié)的最高位,為0即是ASCII碼,為1則為中文(雙字節(jié)或四字節(jié))。

2.5.3Unicode與UTF-8

為了統(tǒng)一表示世界各國(guó)的文字,1993年國(guó)際標(biāo)準(zhǔn)化組織公布了國(guó)際標(biāo)準(zhǔn)ISO/IEC10646,簡(jiǎn)稱(chēng)UCS。這一標(biāo)準(zhǔn)為包括漢字在內(nèi)的各種正在使用的文字規(guī)定了統(tǒng)一的編碼方案,因此又稱(chēng)為Unicode。Unicode已獲得了一些程序設(shè)計(jì)語(yǔ)言(如Java)和操作系統(tǒng)(如Windows)的支持。

Unicode的基本思路是給每一個(gè)字符和符號(hào)分配一個(gè)永久的、唯一的16位值,稱(chēng)為碼點(diǎn)(CodePoint)。例如,漢字“計(jì)”的碼點(diǎn)為0x8BA1,記為U+8BA1。Unicode系統(tǒng)最多有65536個(gè)碼點(diǎn),而全世界的語(yǔ)言大概有20萬(wàn)個(gè)符號(hào),因此碼點(diǎn)就成為一種稀缺資源,不能隨意分配。Unicode的編碼空間大概分為六部分,如表2.7所示。其中,ASCII字符的碼點(diǎn)定義為0~127,因此ASCII碼與Unicode之間的轉(zhuǎn)換規(guī)則十分簡(jiǎn)單。

為此又設(shè)計(jì)出了Unicode字符集的編碼方案,如UTF-8、UCS-2、UTF-16、UCS-4和UTF-32,其中最常用的是UTF-8。UTF-8以8位一個(gè)字節(jié)為單位,是一種可變長(zhǎng)度的編碼。它將Unicode的碼點(diǎn)編碼為1~4個(gè)字節(jié),具體編碼方案如表2.8所示

例如,漢字“計(jì)”的碼點(diǎn)為U+8BA1,屬于表2.8的第三行范圍,編碼為三個(gè)字節(jié),“計(jì)”的UTF-8的編碼為E8AEA1,其編碼方法如圖2.13所示。圖2.13漢字“計(jì)”的UTF-8編碼方法

UTF-8的優(yōu)點(diǎn)在于:編碼0~127分配給了ASCII碼,并且用一個(gè)字節(jié)表示,因此純ASCII碼的字符串也是UTF-8的合法字符串,兩者一致,這樣原先以ASCII碼存儲(chǔ)的文件或處理ASCII碼的程序,不用改動(dòng)即可兼容UTF-8;UTF-8編碼中的第一個(gè)字節(jié)指明了這個(gè)字符一共有幾個(gè)字節(jié),若第一個(gè)字節(jié)最高位是“0”,則該字符只有一個(gè)字節(jié),若第一個(gè)字節(jié)最高位是“1”,則有幾個(gè)連續(xù)“1”就表明該字符有幾個(gè)字節(jié)。后面的字節(jié)都以“10”開(kāi)頭,這樣在傳輸或存儲(chǔ)中出錯(cuò)時(shí),很容易跳過(guò)出錯(cuò)字節(jié),直接找到下一個(gè)字符的起始字節(jié),即擁有自同步能力。當(dāng)前UTF-8在互聯(lián)網(wǎng)上被廣泛使用。

2.6檢錯(cuò)與糾錯(cuò)碼

元件故障、噪聲干擾等各種因素常常導(dǎo)致計(jì)算機(jī)在傳輸、存儲(chǔ)或處理信息的過(guò)程中出現(xiàn)錯(cuò)誤。例如,將一位1從部件A傳送到部件B,可能由于傳送信道中的噪聲干擾而受到破壞,以至于接收部件B收到的是0而不是1。為了防止這種錯(cuò)誤,可采用專(zhuān)門(mén)的邏輯電路對(duì)信號(hào)進(jìn)行編碼以便于檢測(cè)錯(cuò)誤,甚至校正錯(cuò)誤。

2.6.1碼距與校驗(yàn)位位數(shù)

假設(shè)數(shù)據(jù)有n位,為了具備檢錯(cuò)或糾錯(cuò)能力,必須增添k位校驗(yàn)位,則數(shù)據(jù)加校驗(yàn)位一共有m=n+k位,稱(chēng)為m位碼字。

任意兩個(gè)m位的碼字,其對(duì)應(yīng)位不同的數(shù)目稱(chēng)為這兩個(gè)碼字的海明碼距。設(shè)碼字x=xm-1xm-2…x0和y=ym-1ym-2…y0,則x與y的海明碼距d定義為

例如,兩個(gè)8位碼字為01001000與11001011,其碼距為3。求海明碼距只需將兩個(gè)碼字異或后看有多少位是1即可。

對(duì)于n位數(shù)據(jù),所有的2n個(gè)編碼都是合法編碼。而增加k位校驗(yàn)位變成m=n+k位的碼字后,在2m個(gè)碼字中,仍然只有2n個(gè)碼字是合法的。在這2n個(gè)合法碼字之間,兩兩碼字之間海明碼距的最小值dmin,稱(chēng)為這種編碼的海明碼距。

編碼的檢錯(cuò)與糾錯(cuò)能力取決于其海明碼距dmin。如果要檢測(cè)r位錯(cuò),則編碼的碼距dmin至少應(yīng)為r+1,使得一個(gè)合法碼字的r位出錯(cuò)時(shí)不會(huì)成為另一個(gè)合法碼字。而要糾正r位錯(cuò),則編碼的碼距dmin至少應(yīng)為2r+1,使得一個(gè)合法碼字r位出錯(cuò)時(shí),得到的碼字與原合法碼字的碼距(為r)一定比它與其他合法碼字間的碼距(大于等于r+1)要小,因此,只要選取與該錯(cuò)誤碼字碼距最小的合法碼字作為正確的碼字,就實(shí)現(xiàn)了糾錯(cuò)。

例如,一種只有4個(gè)合法碼字的編碼為000000、000111、111000、111111,其海明碼距為3,則可以糾1位錯(cuò)誤。對(duì)于非法碼字010111來(lái)說(shuō),碼距最近的合法碼字為000111,所以000111就是010111的糾錯(cuò)結(jié)果。這是假定只出現(xiàn)1位錯(cuò)誤的前提下做出的糾錯(cuò)結(jié)果。如果允許出現(xiàn)兩位錯(cuò)誤,比如碼字111111變成了010111,則無(wú)法糾錯(cuò),因?yàn)闆](méi)辦法判斷到底是一位出錯(cuò)還是兩位出錯(cuò),所以無(wú)法確定應(yīng)該糾錯(cuò)為000111還是111111。

對(duì)于n位數(shù)據(jù),為使其具有糾一位錯(cuò)的能力,增添k位校驗(yàn)位組成m=n+k位編碼。在2n個(gè)合法的碼字中,其m個(gè)二進(jìn)制位中任何一位出錯(cuò)都會(huì)得到一個(gè)非法碼字,從而可以發(fā)現(xiàn)錯(cuò)誤。為了能糾正這個(gè)一位錯(cuò)誤,這些非法碼字彼此必須是不同的(反之,如果一個(gè)非法碼字可能從兩個(gè)合法碼字分別錯(cuò)一位得到,則無(wú)法糾錯(cuò))。因此,每個(gè)合法碼字對(duì)應(yīng)了m個(gè)與之碼距為1的非法碼字,再加上其自身,每個(gè)合法碼字對(duì)應(yīng)了m+1個(gè)碼字,則總的碼字?jǐn)?shù)目至少為2n×(m+1)個(gè)。而m位編碼至多有2m種碼字組合,因此要滿足2m≥2n×(m+1),將m=n+k代入,可得

在確保具有一位糾錯(cuò)能力時(shí),由式(2.16)可求得數(shù)據(jù)長(zhǎng)度n所需的校驗(yàn)位位數(shù)k,如表2.9所示。

2.6.2奇偶校驗(yàn)碼

例2.13試確定二進(jìn)制數(shù)X=01010100和Y=01010101的奇校驗(yàn)編碼。

解當(dāng)X=01010100時(shí),奇校驗(yàn)位c必須為0,則加了奇校驗(yàn)的數(shù)據(jù)X'=001010100。

當(dāng)Y=01010101時(shí),奇校驗(yàn)位c必須為1,則加了奇校驗(yàn)的數(shù)據(jù)Y'=101010101。

2.偶校驗(yàn)

偶校驗(yàn)的概念與奇校驗(yàn)是一樣的,就是加上偶校驗(yàn)后,必須保證數(shù)據(jù)(包括偶校驗(yàn)位在內(nèi))的n+1位中1的個(gè)數(shù)為偶數(shù),即必須保證:

當(dāng)數(shù)據(jù)X=x0x1…xn-1加上偶校驗(yàn)時(shí),可利用下式求出偶校驗(yàn)位c:

也就是說(shuō),偶校驗(yàn)位等于數(shù)據(jù)各位的模2加。

同樣,當(dāng)數(shù)據(jù)加上偶校驗(yàn)后,便可以存儲(chǔ)或傳輸。在從存儲(chǔ)器讀出或通信對(duì)方收到該數(shù)據(jù)后,可利用式(2.19)進(jìn)行計(jì)算。若式(2.19)成立,則認(rèn)為在存儲(chǔ)或傳輸過(guò)程中未發(fā)生1位出錯(cuò)。

例2.14試確定二進(jìn)制數(shù)X=01010100和Y=01010101的偶校驗(yàn)編碼。

解當(dāng)X=01010100時(shí),偶校驗(yàn)位c必須為1,則加了偶校驗(yàn)的數(shù)據(jù)X'=101010100。

當(dāng)Y=01010101時(shí),偶校驗(yàn)位c必須為0,則加了偶校驗(yàn)的數(shù)據(jù)Y'=001010101。

由上述分析可見(jiàn),當(dāng)數(shù)據(jù)位中有1位變化時(shí),校驗(yàn)位也會(huì)跟著變化,因此奇偶校驗(yàn)碼的碼距為2,可以檢測(cè)出1位錯(cuò)誤(或奇數(shù)位錯(cuò)誤,但多于1位錯(cuò)誤的概率很小),無(wú)法檢測(cè)出2位或偶數(shù)位錯(cuò),也無(wú)法定位錯(cuò)誤位置,從而無(wú)法糾錯(cuò)。由于奇偶校驗(yàn)原理簡(jiǎn)單,實(shí)現(xiàn)容易,因此這種方法得到了廣泛應(yīng)用。

2.6.3海明校驗(yàn)碼

RichardHamming于1950年提出的海明碼可以達(dá)到滿足式(2.16)的最少的校驗(yàn)位數(shù)。

1.海明碼的編碼

設(shè)有效信息為16位數(shù)據(jù),用D15~D0表示由高到低的各位。根據(jù)式(2.16)計(jì)算或查表2.7可知,若要糾正1位錯(cuò)誤,需要在有效信息中添加5個(gè)校驗(yàn)位H4~H0。此時(shí)海明碼的碼長(zhǎng)為m=n+k=16+5=21。表2.10所示為21位海明碼的生成及校驗(yàn)方程的構(gòu)建。

(1)構(gòu)建海明碼編碼格式。先將21位碼的位置編號(hào)列于表2.10第1行中,編號(hào)從1開(kāi)始,在表中按順序排列。在十進(jìn)制位置編號(hào)為2i之處放置各校驗(yàn)位Hi,i從0開(kāi)始,見(jiàn)表2.10中第2行。在除Hi之外的剩余位置編號(hào)之處,將數(shù)據(jù)D15~D0的各位從低位到高位在表2.10中第3行從右到左按順序填入,然后合并第2、3行得到海明碼編碼格式,如圖2.14所示。圖2.14海明碼編碼格式

(2)對(duì)表2.10第4~8行進(jìn)行打“√”操作。第4行從位置1(即20,對(duì)應(yīng)H0)開(kāi)始,從右到左每打1個(gè)“√”空1個(gè)位置,直到最高位置。第5行從位置2(即21,對(duì)應(yīng)H1)開(kāi)始,從右到左每打2個(gè)“√”空2個(gè)位置,直到最高位置。第6行從位置4(即22,對(duì)應(yīng)H2)開(kāi)始,從右到左每打4個(gè)“√”空4個(gè)位置,直到最高位置。第7行從位置8(即23,對(duì)應(yīng)H3)開(kāi)始,從右到左每打8個(gè)“√”空8個(gè)位置,直到最高位置。第8行從位置16(即24,對(duì)應(yīng)H4)開(kāi)始,從右到左每打16個(gè)“√”空16個(gè)位置,直到最高位置。

2.海明碼的校驗(yàn)

(1)構(gòu)建生成方程。在該編碼方案中,每個(gè)校驗(yàn)位對(duì)所有二進(jìn)制位置編號(hào)對(duì)應(yīng)位為1的那些數(shù)據(jù)位進(jìn)行校驗(yàn)。

(2)構(gòu)成海明碼。利用生成方程產(chǎn)生海明碼校驗(yàn)位后,將數(shù)據(jù)與校驗(yàn)位按照?qǐng)D2.14編碼格式組織就構(gòu)成了該數(shù)據(jù)的海明碼,之后可以對(duì)海明碼進(jìn)行存儲(chǔ)或傳輸。

(3)構(gòu)建校驗(yàn)方程。當(dāng)獲得一個(gè)海明碼時(shí),使用校驗(yàn)方程來(lái)判斷該編碼的正確性。

3.海明碼的糾錯(cuò)

根據(jù)校驗(yàn)方程即可直接確定海明碼是否有錯(cuò)或者出錯(cuò)位置編號(hào)。知道出錯(cuò)位置,對(duì)該位求反,就實(shí)現(xiàn)了糾錯(cuò)。所以海明碼也被稱(chēng)作糾錯(cuò)碼,具有糾正一位錯(cuò)誤的能力。

圖2.15是針對(duì)12位海明碼(8位數(shù)據(jù)+4位校驗(yàn))糾錯(cuò)的電路。將4-16譯碼器74LS154輸入端接P3P2P1P0,選擇16個(gè)譯碼輸出(低有效)中對(duì)應(yīng)8位數(shù)據(jù)的輸出端加反相器,再與相應(yīng)的數(shù)據(jù)位做異或運(yùn)算,這樣就可以實(shí)現(xiàn)海明碼無(wú)錯(cuò)時(shí)8位數(shù)據(jù)直接輸出,有錯(cuò)時(shí)對(duì)出錯(cuò)數(shù)據(jù)位求反糾正。圖2.15糾錯(cuò)電路原理圖

4.單糾錯(cuò)雙檢錯(cuò)碼

觀察表2.10中n=8、k=4時(shí)海明碼的生成方程可以發(fā)現(xiàn),每一個(gè)數(shù)據(jù)位至少出現(xiàn)在兩個(gè)生成方程中,即被兩個(gè)校驗(yàn)位校驗(yàn)。因此當(dāng)一個(gè)數(shù)據(jù)位變化時(shí),至少有兩個(gè)校驗(yàn)位也隨之變化,這意味著兩個(gè)合法碼字之間的碼距至少為3。實(shí)際上,n=8、k=4時(shí)海明碼的碼距就是3。根據(jù)2.6.1節(jié)中的分析,它可以糾正1位錯(cuò)誤,或者發(fā)現(xiàn)2位錯(cuò)誤而不糾正。那么,能否同時(shí)糾正1位錯(cuò)誤及發(fā)現(xiàn)2位錯(cuò)誤呢?這就需要進(jìn)一步擴(kuò)大碼距。

方案是:增加一個(gè)所有數(shù)據(jù)位異或得到的校驗(yàn)位(即偶校驗(yàn))。若該校驗(yàn)位校驗(yàn)錯(cuò)誤,表示可能有1位錯(cuò)誤(實(shí)際上說(shuō)明有奇數(shù)位錯(cuò)誤),進(jìn)一步根據(jù)P3~P0具體確定錯(cuò)誤位的位置,并糾錯(cuò);反之,若該校驗(yàn)位校驗(yàn)正確,而P3~P0不是全零,則表示有2位錯(cuò)誤(實(shí)際上為偶數(shù)位錯(cuò)誤),只給出校驗(yàn)錯(cuò)誤信息,不糾錯(cuò),這就是半導(dǎo)體存儲(chǔ)器中常用的單糾錯(cuò)雙檢錯(cuò)(Single-Error-Correcting,Double-Error-Detecting,SEC-DED)碼。

海明碼不僅用于主存儲(chǔ)器的校驗(yàn),在通信傳輸、磁盤(pán)記錄中同樣可以使用。

2.6.4循環(huán)冗余校驗(yàn)碼

循環(huán)冗余校驗(yàn)(CyclicRedundancyCheck,CRC)碼可以發(fā)現(xiàn)并糾正信息在存儲(chǔ)或傳送過(guò)程中出現(xiàn)的錯(cuò)誤。因