Ch2:DataRepresentation

數(shù)據(jù)的機(jī)器級表示第一講

數(shù)值數(shù)據(jù)的表示

第二講非數(shù)值數(shù)據(jù)表示及數(shù)據(jù)的寬度、存儲排列、糾/檢錯第一講：數(shù)值數(shù)據(jù)的表示主要內(nèi)容定點(diǎn)數(shù)的表示進(jìn)位計數(shù)制定點(diǎn)數(shù)的二進(jìn)制編碼原碼、補(bǔ)碼、移碼表示定點(diǎn)整數(shù)的表示無符號整數(shù)、帶符號整數(shù)浮點(diǎn)數(shù)格式和表示范圍浮點(diǎn)數(shù)的規(guī)格化IEEE754浮點(diǎn)數(shù)標(biāo)準(zhǔn)單精度浮點(diǎn)數(shù)、雙精度浮點(diǎn)數(shù)特殊數(shù)的表示形式C語言程序中的整數(shù)類型、浮點(diǎn)數(shù)類型十進(jìn)制數(shù)表示信息的二進(jìn)制編碼計算機(jī)的外部信息與內(nèi)部機(jī)器級數(shù)據(jù)

機(jī)器級數(shù)據(jù)分兩大類：數(shù)值數(shù)據(jù)：無符號整數(shù)、帶符號整數(shù)、浮點(diǎn)數(shù)（實(shí)數(shù)）、十進(jìn)制數(shù)非數(shù)值數(shù)據(jù)：邏輯數(shù)（包括位串）、西文字符和漢字計算機(jī)內(nèi)部所有信息都用二進(jìn)制（即：0和1）進(jìn)行編碼用二進(jìn)制編碼的原因：制造二個穩(wěn)定態(tài)的物理器件容易二進(jìn)制編碼、計數(shù)、運(yùn)算規(guī)則簡單正好與邏輯命題對應(yīng)，便于邏輯運(yùn)算，并可方便地用邏輯電路實(shí)現(xiàn)算術(shù)運(yùn)算真值和機(jī)器數(shù)機(jī)器數(shù)：用0和1編碼的計算機(jī)內(nèi)部的0/1序列真值：機(jī)器數(shù)真正的值，即：現(xiàn)實(shí)中帶正負(fù)號的數(shù)C語言中哪些類型是數(shù)值數(shù)據(jù)？哪些是非…？數(shù)值數(shù)據(jù)的表示數(shù)值數(shù)據(jù)表示的三要素進(jìn)位計數(shù)制定、浮點(diǎn)表示如何用二進(jìn)制編碼即：要確定一個數(shù)值數(shù)據(jù)的值必須先確定這三個要素。例如，機(jī)器數(shù)01011001的值是多少？進(jìn)位計數(shù)制十進(jìn)制、二進(jìn)制、十六進(jìn)制、八進(jìn)制數(shù)及其相互轉(zhuǎn)換定/浮點(diǎn)表示（解決小數(shù)點(diǎn)問題）定點(diǎn)整數(shù)、定點(diǎn)小數(shù)浮點(diǎn)數(shù)（可用一個定點(diǎn)小數(shù)和一個定點(diǎn)整數(shù)來表示）定點(diǎn)數(shù)的編碼（解決正負(fù)號問題）原碼、補(bǔ)碼、反碼、移碼（反碼很少用）答案是：不知道！移碼表示°什么是“移碼表示”？

將每一個數(shù)值加上一個偏置常數(shù)（bias）°一般來說，當(dāng)編碼位數(shù)為n時，bias取2n-1

例如.n=4:E移

=E+23(

bias=23=1000B)-8(+8)~0000B-7(+8)~0001B… 0(+8)~1000B …+7(+8)~1111B°為什么要用移碼來表示指數(shù)（階碼）?

便于浮點(diǎn)數(shù)加減運(yùn)算時的對階操作（比較大小）例：1.01x2-1+1.11x23簡化比較補(bǔ)碼：111<011?(-1)

(3)1.01x2-1+4+1.11x23+4

移碼：011<111

(3)

(7)移碼主要用來表示浮點(diǎn)數(shù)的階碼！0的移碼表示唯一移碼和補(bǔ)碼僅第一位不同Unsignedinteger(無符號整數(shù))機(jī)器中字的位排列順序有兩種方式：（例：32位字:0…010112）高到低位從左到右：00000000000000000000000000001011高到低位從右到左：11010000000000000000000000000000Leftmost和rightmost這兩個詞有歧義，故用LSB(LeastSignificantBit)來表示最低有效位，用MSB來表示最高有效位高位到低位多采用從左往右排列一般在全部是正數(shù)運(yùn)算且不出現(xiàn)負(fù)值結(jié)果的場合下，可使用無符號數(shù)表示。例如，地址運(yùn)算，編號表示，等等無符號數(shù)的編碼中沒有符號位能表示的最大值大于位數(shù)相同的帶符號整數(shù)的最大值（Why？）例如，8位無符號整數(shù)最大是255（11111111）而8位帶符號整數(shù)最大為127（01111111）總是整數(shù)，所以很多時候就簡稱為“無符號數(shù)”MSBLSBSignedinteger（帶符號整數(shù)，定點(diǎn)整數(shù)）計算機(jī)必須能處理正數(shù)(positive)和負(fù)數(shù)(negative)，MSB表示數(shù)符有三種定點(diǎn)編碼方式Signedmagnitude（原碼）

現(xiàn)用來表示浮點(diǎn)（實(shí)）數(shù)的尾數(shù)One’scomplement（反碼）現(xiàn)已不用于表示數(shù)值數(shù)據(jù)Two’scomplement（補(bǔ)碼）

50年代以來，所有計算機(jī)都用補(bǔ)碼來表示定點(diǎn)整數(shù)為什么用補(bǔ)碼表示帶符號整數(shù)？補(bǔ)碼運(yùn)算系統(tǒng)是模運(yùn)算系統(tǒng)，加、減運(yùn)算統(tǒng)一數(shù)0的表示唯一，方便使用比原碼和反碼多表示一個最小負(fù)數(shù)與移碼相比，其符號位和真值的符號對應(yīng)關(guān)系清楚帶符號整數(shù)和無符號數(shù)的比較擴(kuò)充操作有差別例如，MIPS提供了兩種加載指令（loadbyteunsigned/loadbyte）無符號數(shù)：lbu$t0,0($s0);$t0高24位補(bǔ)0（稱為0擴(kuò)展）帶符號整數(shù)：lb$t0,0($s0);$t0高24位補(bǔ)符（稱為符號擴(kuò)展）數(shù)的比較有差異無符號數(shù)：MSB為1的數(shù)比MSB為0的數(shù)大帶符號整數(shù)：MSB為1的數(shù)比MSB為0的數(shù)小例如，MIPS中提供了不同的比較指令，如：無符號數(shù)：sltu$t0,$s0,$s1（setlessthanunsigned）帶符號整數(shù)：slt$t1,$s0,$s1（setlessthan）

假定：$s0=11111111111111111111111111111111 $s1=00000000000000000000000000000001則：$t0和$t1分別為多少？

答案：$t0和$t1分別為0和1。溢出判斷有差異（無符號數(shù)根據(jù)最高位是否有進(jìn)位判斷溢出，通常不判）MIPS規(guī)定：無符號數(shù)運(yùn)算溢出時，不產(chǎn)生“溢出異常”SKIP擴(kuò)展操作舉例例1（擴(kuò)展操作）：在32位機(jī)器上輸出si,usi,i,ui的十進(jìn)制（真值）和十六進(jìn)制值（機(jī)器數(shù)）是什么？ shortsi=-32768; unsignedshortusi=si; inti=si; unsingnedui=usi;si=-327688000usi=327688000i=-32768FFFF8000ui=3276800008000BACK機(jī)器數(shù)真值提示：32768=215=1000000000000000B現(xiàn)象：帶符號整數(shù)：符號擴(kuò)展無符號數(shù)：0擴(kuò)展例如:

尾數(shù)

6.02x1021

基數(shù)°規(guī)格化形式:小數(shù)點(diǎn)前只有一位非0數(shù)°同一個數(shù)有多種表示形式。例：對于數(shù)1/1,000,000,000?唯一的規(guī)格化形式:1.0x10-9?非規(guī)格化形式不唯一:0.1x10-8,10.0x10-10科學(xué)計數(shù)法(ScientificNotation)與浮點(diǎn)數(shù)

尾數(shù)階碼0.101x

2

-10

基數(shù)為2對于二進(jìn)制數(shù):只要對尾數(shù)和指數(shù)分別編碼，就可表示一個浮點(diǎn)數(shù)（即：實(shí)數(shù)）階碼浮點(diǎn)數(shù)(FloatingPoint)的表示范圍例：畫出下述32位浮點(diǎn)數(shù)格式的規(guī)格化數(shù)的表示范圍。

018931

第0位數(shù)符S；

第1～8位為8位移碼表示階碼E（偏置常數(shù)為128）；

第9～31位為24位二進(jìn)制原碼小數(shù)表示的尾數(shù)M。

規(guī)格化尾數(shù)的小數(shù)點(diǎn)后第一位總是1，故規(guī)定第一位默認(rèn)的“1”不明顯表示出來。這樣可用23個數(shù)位表示24位尾數(shù)。S階碼E尾數(shù)M+/-0.1xxxxx

×2E該浮點(diǎn)數(shù)大小為：最大正數(shù)：0.11…1x211…1=(1-2-24)x2127

最小正數(shù)：0.10…0x200…0=(1/2)x2-128

因?yàn)樵a是對稱的，所以其表示范圍關(guān)于原點(diǎn)對稱。機(jī)器0：尾數(shù)為0或落在下溢區(qū)中的數(shù)浮點(diǎn)數(shù)范圍比定點(diǎn)數(shù)大，但數(shù)的個數(shù)沒變多，故數(shù)之間更稀疏，且不均勻

正下溢

負(fù)下溢

-

(1-2-24)

×2127

數(shù)軸

零

可表示的正數(shù)

可表示的負(fù)數(shù)

-2-129

0

2-129

(1-2-24)

×2127

正上溢

負(fù)上溢

浮點(diǎn)數(shù)的表示°規(guī)格化數(shù)形式：

+/-1.xxxxxxxxxx

×2E°32-bit規(guī)格化數(shù)：310

S

階碼E

位數(shù)M1bit?bits?bits

S

是符號位（Sign）

階碼用移碼表示

尾數(shù)

表示xxxxxxxxxxxxx，尾數(shù)部分

(基數(shù)可以是2/4/8/16，約定信息，無需顯式表示)°早期的計算機(jī)，各自定義自己的浮點(diǎn)數(shù)格式問題：浮點(diǎn)數(shù)表示不統(tǒng)一會帶來什么問題？規(guī)定：小數(shù)點(diǎn)前總是“1”，故可隱含表示注意：和前面例子的規(guī)定不太一樣,顯然這里更合理!“Father”oftheIEEE754standard現(xiàn)在所有計算機(jī)都采用IEEE754來表示浮點(diǎn)數(shù)1970年代后期,IEEE成立委員會著手制定浮點(diǎn)數(shù)標(biāo)準(zhǔn)1985年完成浮點(diǎn)數(shù)標(biāo)準(zhǔn)IEEE754的制定

直到80年代初，各個機(jī)器內(nèi)部的浮點(diǎn)數(shù)表示格式還沒有統(tǒng)一

因而相互不兼容，機(jī)器之間傳送數(shù)據(jù)時，帶來較大的麻煩。

Prof.WilliamKahan

/~wkahan/ieee754status/754story.htmlThisstandardwasprimarilytheworkofoneperson,UCBerkeleymathprofessorWilliamKahan.圖靈獎IEEE754浮點(diǎn)數(shù)格式

單精度格式：(雙精度格式類似)

符號S

指數(shù)E

尾數(shù)M

1bit8bits23bits°符號S:1表示負(fù);0表示正°尾數(shù):?規(guī)格化尾數(shù)最高位總是1，所以隱含表示，省1位?1+23bits（單精度），1+52bits（雙精度）°階碼/指數(shù)E:規(guī)格化數(shù)階碼范圍為00000001(-126)~11111110(127)偏移值為127(單精度),(多精度為1023)單:(-1)Sx(1+M)x2(E-127)雙:(-1)Sx(1+M)x2(E-1023)全0和全1用來表示特殊值！為什么用127？若用128,則階碼范圍為多少？00000001(-127)～11111110(126)能表示的最大浮點(diǎn)數(shù)較小規(guī)格化數(shù)：+/-1.xxxxxxxxxxx2E例:ConvertingBinaryFPtoDecimal10111110111000000000000000000000°Sign:1=>negative°Exponent:?011111012=12510?Biasadjustment:125-127=-2°Significand:

1+1x2-1+1x2-2+0x2-3+0x2-4+0x2-5+...=1+2-1+2-2=1+0.5+0.25=1.75°Represents:-1.75tenx2-2=-0.4375(-1)S

x(1+M)x2(E-127)BEE00000H

isthehex.Rep.OfanIEEE754SPFPnumberEx:ConvertingDecimaltoIEEE754SPFP-12.751.Denormalize:-12.752.Convertintegerpart:12=8+4=110023.Convertfractionalpart:.75=.5+.25=.1124.Putpartstogetherandnormalize:1100.11=1.10011x235.Convertexponent:127+3=128+2=10000010211000001010011000000000000000000TheHexrep.isC14C0000HNormalizednumbers（規(guī)格化數(shù)）指數(shù)

尾數(shù)Object1-254任意(隱含整數(shù)1)Norms00?0非零?2550?255非零?前面的定義都是針對規(guī)格化數(shù)（normalizedform）Howaboutotherpatterns?如何表示0

指數(shù):全0

尾數(shù):全0

符號位可取0和1，分別表示+0和-0.+0:00000000000000000000000000000000-0:10000000000000000000000000000000如何表示+∞/-∞

表示+∞/-∞：?指數(shù):

全1(11111111B=255)?尾數(shù):全0

+∞:01111111100000000000000000000000-∞:11111111100000000000000000000000例如：

5.0/0=+∞,-5.0/0=-∞5+(+∞)=+∞,(+∞)+(+∞)=+∞5-(+∞)=-∞,(-∞)-(+∞)=-∞為什么要這樣處理??可以利用+∞/-∞作比較。例如：X/0>Y可作為有效比較在浮點(diǎn)數(shù)表示中,除數(shù)為0的結(jié)果是+/-∞,而不是溢出異常.（整數(shù)除0為異常）怎樣表示“非數(shù)”NaN(NotaNumber)Sqrt(-4.0)=?0/0=?

這些結(jié)果稱為“非數(shù)”，指未定義的數(shù)。例如：

sqrt(-4.0)=NaN0/0=NaNop(NaN,x)=NaN+∞+(-∞)=NaN+∞-(+∞)=NaN∞/∞=NaNetc.怎樣表示“非數(shù)”？

指數(shù)=255

尾數(shù):非零值NaN常用于程序調(diào)試過程Whathavewedefinedsofar?(forSP)RepresentationforDenorms(非規(guī)格化數(shù))

UsedtorepresentDenormalizednumbersExponentSignificandObject00+/-00nonzeroDenorms

1-254anythingNormsimplicitleading12550+/-infinity255nonzeroNaNRepresentationforDenorms2-1262-1252-1242-1231.0…0x2-126~1.1…1x2-1260.0…0x2-126~0.1…1x2-1262-1262-1252-1242-12300GAP

NormalizednumbersDenorms(-1)s×0.aa…a×2-126QuestionsaboutIEEE754What’stherangeofrepresentablevalues?Thelargestnumberforsingle:+1.11…1X2127Howaboutdouble?Whataboutfollowingtypeconverting:notalwaystrue!

if(i==(int)((float)i)){printf(“true”);}if(f==(float)((int)f)){printf(“true”);}HowaboutFPaddassociative?FALSE!

x=–1.5x1038,y=1.5x1038,z=1.0(x+y)+z=(–1.5x1038+1.5x1038)

+1.0=1.0x+(y+z)=–1.5x1038+(1.5x1038+1.0)=0.0Howaboutdouble?

Howaboutdouble?True!Notalwaystrue!約+3.4X1038約+1.8X10308數(shù)值數(shù)據(jù)（numericaldata）的兩種表示Binary(二進(jìn)制數(shù))定點(diǎn)整數(shù)：Fixed-pointnumber(integer)Unsignedandsignedint浮點(diǎn)數(shù)：Floating-pointnumber(realnumber)Decimal(十進(jìn)制數(shù))

用ASCII碼表示用BCD（BinarycodedDecimal）碼表示計算機(jī)中為什么要用十進(jìn)制數(shù)表示數(shù)值？日常使用的都是十進(jìn)制數(shù)，所以，計算機(jī)外部都使用十進(jìn)制數(shù)。在一些有大量數(shù)據(jù)輸入/出的系統(tǒng)中，為減少二進(jìn)制數(shù)和十進(jìn)制數(shù)之間的轉(zhuǎn)換，在計算機(jī)內(nèi)部直接用十進(jìn)制數(shù)表示數(shù)值。

十進(jìn)制數(shù)的表示用ASCII碼表示十進(jìn)制數(shù)前分隔數(shù)字串符號位單獨(dú)用一個字節(jié)表示，位于數(shù)字串之前。正號用“+”的ASCII碼(2BH)表示；負(fù)號用“-”的ASCII碼(2DH)表示例：十進(jìn)制數(shù)+236表示為:2B323336H

00101011001100100011001100110110B十進(jìn)制數(shù)-2369表示為:2D32333639H

0010110100110010001100110011011000111001B后嵌入數(shù)字串符號位嵌入最低位數(shù)字的ASCII碼高4位中。比前分隔方式省一個字節(jié)。正數(shù)不變；負(fù)數(shù)高4位變?yōu)?111.例：十進(jìn)制數(shù)+236表示為:323336H

001100100011001100110110B十進(jìn)制數(shù)-2369表示為:32333679H00110010001100110011011001111001B缺點(diǎn)：占空間大，且需轉(zhuǎn)換成二進(jìn)制數(shù)或BCD碼才能計算。編碼思想:每個十進(jìn)數(shù)位至少有4位二進(jìn)制表示。而4位二進(jìn)制位可組合成16種狀態(tài)，去掉10種狀態(tài)后還有6種冗余狀態(tài)。編碼方案1．十進(jìn)制有權(quán)碼每個十進(jìn)制數(shù)位的4個二進(jìn)制位（稱為基2碼）都有一個確定的權(quán)。8421碼是最常用的十進(jìn)制有權(quán)碼。也稱自然BCD（NBCD）碼。2．十進(jìn)制無權(quán)碼每個十進(jìn)制數(shù)位的4個基2碼沒有確定的權(quán)。在無權(quán)碼方案中，用的較多的是余3碼和格雷碼。3．其他編碼方案（5中取2碼、獨(dú)熱碼等）符號位的表示：“+”：1100；“-”：1101例：+236=(1100001000110110)8421(占2個字節(jié))-2369=(1101

00000010001101101001)8421(占3個字節(jié))用BCD碼表示十進(jìn)制數(shù)補(bǔ)0以使數(shù)占滿一個字節(jié)第一講小結(jié)在機(jī)器內(nèi)部編碼后的數(shù)稱為機(jī)器數(shù)，其值稱為真值定義數(shù)值數(shù)據(jù)有三個要素：進(jìn)制、定點(diǎn)/浮點(diǎn)、編碼整數(shù)的表示無符號數(shù)：正整數(shù)，用來表示地址等；帶符號整數(shù)：用補(bǔ)碼表示C語言中的整數(shù)無符號數(shù)：unsignedint(short/long)；帶符號數(shù)：int(short/long)浮點(diǎn)數(shù)的表示符號；尾數(shù)：定點(diǎn)小數(shù)；指數(shù)（階）：定點(diǎn)整數(shù)（基不用表示）浮點(diǎn)數(shù)的范圍正上溢、正下溢、負(fù)上溢、負(fù)下溢；與階碼的位數(shù)和基的大小有關(guān)浮點(diǎn)數(shù)的精度：與尾數(shù)的位數(shù)和是否規(guī)格化有關(guān)浮點(diǎn)數(shù)的表示（IEEE754標(biāo)準(zhǔn)）：單精度SP（float）和雙精度DP（double）規(guī)格化數(shù)(SP)：階碼1~254，尾數(shù)最高位隱含為1“零”(階為全0，尾為全0)∞(階為全1，尾為全0)NaN(階為全1，尾為非0)非規(guī)格化數(shù)(階為全0，尾為非0，隱藏位為0)（P.42倒數(shù)第9行說明）十進(jìn)制數(shù)的表示：用ASCII碼或BCD碼表示10在計算機(jī)中有幾種可能的表示？

-10呢？“轉(zhuǎn)換”的概念在數(shù)據(jù)表示中的反映感覺媒體信息樹、鏈表等結(jié)構(gòu)化數(shù)據(jù)描述程序定義的int、float等數(shù)據(jù)指令中的寄存器或內(nèi)存中數(shù)據(jù)ALU或總線上的運(yùn)算/傳輸數(shù)據(jù)邏輯門位信息問題(應(yīng)用)算法程序(語言)指令集體系結(jié)構(gòu)(ISA)微結(jié)構(gòu)電路器件(晶體管)具體實(shí)現(xiàn)抽象概括第二講非數(shù)值數(shù)據(jù)、數(shù)據(jù)排列、糾/檢錯主要內(nèi)容非數(shù)值數(shù)據(jù)的表示邏輯數(shù)據(jù)、西文字符、漢字?jǐn)?shù)據(jù)的寬度數(shù)據(jù)的存儲排列大端方式、小端方式數(shù)據(jù)的糾錯和檢錯奇偶校驗(yàn)、海明校驗(yàn)、循環(huán)冗余校驗(yàn)表示用一位表示。例如，真：1/假：0N位二進(jìn)制數(shù)可表示N個邏輯數(shù)據(jù)，或一個位串運(yùn)算按位進(jìn)行如:按位與/按位或/邏輯左移/邏輯右移等識別邏輯數(shù)據(jù)和數(shù)值數(shù)據(jù)在形式上并無差別，也是一串0/1序列，機(jī)器靠指令來識別。位串用來表示若干個狀態(tài)位或控制位（OS中使用較多）

例如，x86的標(biāo)志寄存器含義如下：

邏輯數(shù)據(jù)的編碼表示CFPFAFZFSFTFIFDFOF特點(diǎn)是一種拼音文字，用有限幾個字母可拼寫出所有單詞只對有限個字母和數(shù)學(xué)符號、標(biāo)點(diǎn)符號等輔助字符編碼所有字符總數(shù)不超過256個，使用7或8個二進(jìn)位可表示表示（常用編碼為7位ASCII碼）十進(jìn)制數(shù)字：0/1/2…/9英文字母：A/B/…/Z/a/b/…/z專用符號：+/-/%/*/&/……控制字符（不可打印或顯示）操作字符串操作，如:傳送/比較等

西文字符的編碼表示必須熟悉對應(yīng)的ASCII碼！特點(diǎn)漢字是表意文字，一個字就是一個方塊圖形。漢字?jǐn)?shù)量巨大，總數(shù)超過6萬字，給漢字在計算機(jī)內(nèi)部的表示、漢字的傳輸與交換、漢字的輸入和輸出等帶來了一系列問題。編碼形式有以下幾種漢字代碼：輸入碼：對漢字用相應(yīng)按鍵進(jìn)行編碼表示，用于輸入內(nèi)碼：用于在系統(tǒng)中進(jìn)行存儲、查找、傳送等處理字模點(diǎn)陣或輪廓描述:

描述漢字字模點(diǎn)陣或輪廓，用于顯示/打印

漢字及國際字符的編碼表示問題：西文字符有沒有輸入碼？有沒有內(nèi)碼？有沒有字模點(diǎn)陣或輪廓描述？向計算機(jī)輸入漢字的方式：

①手寫漢字聯(lián)機(jī)識別輸入，或者是印刷漢字掃描輸入后自動識別，這兩種方法現(xiàn)均已達(dá)到實(shí)用水平。②用語音輸入漢字，雖然簡單易操作，但離實(shí)用階段還相差很遠(yuǎn)。③利用英文鍵盤輸入漢字：每個漢字用一個或幾個鍵表示，這種對每個漢字用相應(yīng)按鍵進(jìn)行的編碼稱為漢字“輸入碼”，又稱外碼。輸入碼的碼元為按鍵。是最簡便、最廣泛的漢字輸入方法。

常用的方法有：搜狗拼音、五筆字型、智能ABC、微軟拼音等使用漢字輸入碼的原因：

①鍵盤面向西文設(shè)計，一個或兩個西文字符對應(yīng)一個按鍵，非常方便。②漢字是大字符集，專門的漢字輸入鍵盤由于鍵多、查找不便、成本高等原因而幾乎無法采用。漢字的輸入碼問題：西文字符常用的內(nèi)碼是什么？對于漢字內(nèi)碼的選擇，必須考慮以下幾個因素：①不能有二義性，即不能和ASCII碼有相同的編碼。②盡量與漢字在字庫中的位置有關(guān)，便于漢字查找和處理。③編碼應(yīng)盡量短。國標(biāo)碼（國標(biāo)交換碼）1981年我國頒布了《信息交換用漢字編碼字符集·基本集》(GB2312—80)。該標(biāo)準(zhǔn)選出6763個常用漢字，為每個漢字規(guī)定了標(biāo)準(zhǔn)代碼，以供漢字信息在不同計算機(jī)系統(tǒng)間交換使用可在漢字國標(biāo)碼的基礎(chǔ)上產(chǎn)生漢字機(jī)內(nèi)碼字符集與漢字的內(nèi)碼其內(nèi)碼就是ASCII碼。由三部分組成：①字母、數(shù)字和各種符號，包括英文、俄文、日文平假名與片假名、羅馬字母、漢語拼音等共687個②一級常用漢字，共3755個，按漢語拼音排列③二級常用漢字，共3008個，不太常用，按偏旁部首排列漢字的區(qū)位碼碼表由94行、94列組成，行號為區(qū)號，列號為位號，各占7位指出漢字在碼表中的位置，共14位，區(qū)號在左、位號在右漢字的國標(biāo)碼每個漢字的區(qū)號和位號各自加上32（20H），得到其“國標(biāo)碼”國標(biāo)碼中區(qū)號和位號各占7位。在計算機(jī)內(nèi)部，為方便處理與存儲，前面添一個0，構(gòu)成一個字節(jié)GB2312-80字符集漢字內(nèi)碼至少需2個字節(jié)才能表示一個漢字內(nèi)碼。為什么？由漢字的總數(shù)決定！可在GB2312國標(biāo)碼的基礎(chǔ)上產(chǎn)生漢字內(nèi)碼為與ASCII碼區(qū)別，將國標(biāo)碼的兩個字節(jié)的第一位置“1”后得到一種漢字內(nèi)碼

例如，漢字“大”在碼表中位于第20行、第83列。因此區(qū)位碼為00101001010011，國標(biāo)碼為0011010001110011，即3473H。前面的34H和字符“4”的ACSII碼相同，后面的73H和字符“s”的ACSII碼相同，將每個字節(jié)的最高位各設(shè)為“1”后，就得到其內(nèi)碼：B4F3H(1011010011110011B)，因而不會和ASCII碼混淆。區(qū)位碼→國標(biāo)碼→內(nèi)碼國際字符集國際字符集的必要性不同地區(qū)使用不同字符集內(nèi)碼，如中文GB2312

/

Big5、日文Shift-JIS

/

EUC-JP等。在安裝中文系統(tǒng)的計算機(jī)中打開日文文件，會出現(xiàn)亂碼。為使所有國際字符都能互換，必須創(chuàng)建一種涵蓋全部字符的多字符集。國際多字符集通過對各種地區(qū)性字符集規(guī)定使用范圍來唯一定義各字符的編碼。國際標(biāo)準(zhǔn)ISO/IEC10646提出了一種包括全世界現(xiàn)代書面語言文字所使用的所有字符的標(biāo)準(zhǔn)編碼，有4個字節(jié)編碼(UCS-4)和2字節(jié)編碼(UCS-2)。我國（包括香港、臺灣地區(qū)）與日本、韓國聯(lián)合制訂了一個統(tǒng)一的漢字字符集（CJK編碼），共收集了上述不同國家和地區(qū)共約2萬多漢字及符號，采用2字節(jié)編碼(即：UCS-2)，已被批準(zhǔn)為國家標(biāo)準(zhǔn)(GB13000)。Windows操作系統(tǒng)(中文版)已采用中西文統(tǒng)一編碼，收集了中、日、韓三國常用的約2萬漢字，稱為“Unicode”，采用2字節(jié)編碼，與UCS-2一致。

為便于打印、顯示漢字，漢字字形必須預(yù)先存在機(jī)內(nèi)字庫(font)：所有漢字形狀的描述信息集合不同字體(如宋體、仿宋、楷體、黑體等)對應(yīng)不同字庫從字庫中找到字形描述信息，然后送設(shè)備輸出問題：如何知道到哪里找相應(yīng)的字形信息？漢字內(nèi)碼與其在字庫中的位置有關(guān)！！字形主要有兩種描述方法：字模點(diǎn)陣描述（圖像方式）輪廓描述（圖形方式）直線向量輪廓曲線輪廓（TrueType字形）漢字的字模點(diǎn)陣碼和輪廓描述區(qū)位碼←國標(biāo)碼←內(nèi)碼數(shù)據(jù)的基本寬度比特（bit）是計算機(jī)中處理、存儲、傳輸信息的最小單位二進(jìn)制信息的計量單位是“字節(jié)”(Byte)，也稱“位組”現(xiàn)代計算機(jī)中，存儲器按字節(jié)編址字節(jié)是最小可尋址單位(addressableunit)

如果以字節(jié)為一個排列單位，則LSB表示最低有效字節(jié)，MSB表示最高有效字節(jié)除比特和字節(jié)外，還經(jīng)常使用“字”(word)作為單位“字”和“字長”的概念不同IA-32中的“字”有多少位？字長多少位呢？DWORD：32位QWORD：64位16位32位數(shù)據(jù)的基本寬度“字”和“字長”的概念不同“字長”指定點(diǎn)運(yùn)算數(shù)據(jù)通路的寬度。（數(shù)據(jù)通路指CPU內(nèi)部數(shù)據(jù)流經(jīng)的路徑以及路徑上的部件，主要是CPU內(nèi)部進(jìn)行數(shù)據(jù)運(yùn)算、存儲和傳送的部件，這些部件的寬度基本上要一致，才能相互匹配。因此，”字長”等于CPU內(nèi)部總線的寬度、運(yùn)算器的位數(shù)、通用寄存器的寬度等。）“字”表示被處理信息的單位，用來度量數(shù)據(jù)類型的寬度。字和字長的寬度可以一樣，也可不同。例如，x86體系結(jié)構(gòu)定義“字”的寬度為16位，但從386開始字長就是32位了。數(shù)據(jù)量的度量單位存儲二進(jìn)制信息時的度量單位要比字節(jié)或字大得多容量經(jīng)常使用的單位有：“千字節(jié)”(KB)，1KB=210字節(jié)=1024B“兆字節(jié)”(MB)，1MB=220字節(jié)=1024KB“千兆字節(jié)”(GB)，1GB=230字節(jié)=1024MB“兆兆字節(jié)”(TB)，1TB=240字節(jié)=1024GB

通信中的帶寬使用的單位有：“千比特/秒”(kb/s)，1kbps=103b/s=1000bps“兆比特/秒”(Mb/s)，1Mbps=106b/s

=1000kbps“千兆比特/秒”(Gb/s)，1Gbps=109b/s=1000Mbps“兆兆比特/秒”(Tb/s)，1Tbps=1012b/s=1000Gbps如果把b換成B，則表示字節(jié)而不是比特（位）例如，10MBps表示10兆字節(jié)/秒程序中數(shù)據(jù)類型的寬度高級語言支持多種類型、多種長度的數(shù)據(jù)例如，C語言中char類型的寬度為1個字節(jié)，可表示一個字符（非數(shù)值數(shù)據(jù)），也可表示一個8位的整數(shù)（數(shù)值數(shù)據(jù)）不同機(jī)器上表示的同一種類型的數(shù)據(jù)可能寬度不同程序中的數(shù)據(jù)有相應(yīng)的機(jī)器級表示方式和相應(yīng)的處理指令

(在第五章指令系統(tǒng)介紹具體指令)C聲明典型32位機(jī)器CompaqAlpha機(jī)器charshortintintlongint12441248char*48floatdouble4848C語言中數(shù)值數(shù)據(jù)類型的寬度(單位：字節(jié))從表中看出：同類型數(shù)據(jù)并不是所有機(jī)器都采用相同的寬度，分配的字節(jié)數(shù)隨機(jī)器字長和編譯器的不同而不同。

CompaqAlpha是一個針對高端應(yīng)用的64位機(jī)器，即字長為64位數(shù)據(jù)的存儲和排列順序80年代開始，幾乎所有通用機(jī)器都用字節(jié)編址ISA設(shè)計時要考慮的兩個問題：如何根據(jù)一個地址取到一個32位的字？-字的存放問題一個字能否存放在任何地址邊界？-字的邊界對齊問題例如，若inti=-65535，存放在內(nèi)存100號單元（即占100#～103#），則用“取數(shù)”指令訪問100號單元取出i時，必須清楚i的4個字節(jié)是如何存放的。msblsb103102101100littleendianword100#100101102103bigendianword100#Word:FFFF0001大端方式（BigEndian）:MSB所在的地址是數(shù)的地址

e.g.IBM360/370,Motorola68k,MIPS,Sparc,HPPA小端方式（LittleEndian）:LSB所在的地址是數(shù)的地址

e.g.Intel80x86,DECVAX

有些機(jī)器兩種方式都支持，可通過特定控制位來設(shè)定采用哪種方式。65535=216-1[-65535]補(bǔ)=FFFF0001HBIGEndianversusLittleEndianEx1:MemorylayoutofanumberABCDHlocatedin1000Ex2:Memorylayoutofanumber00ABCDEFHlocatedin1000InLittleEndian:ABCD10011000InBigEndian:

CDAB100110001000100110021003InBigEndian:

00ABCDEFInLittleEndian:00ABCDEF1003100210011000BIGEndianversusLittleEndianEx3:Memorylayoutofainstructionlocatedin1000假定小端機(jī)器中指令：movAX,0x12345(BX)其中操作碼mov為40H，寄存器AX和BX的編號分別為0001B和0010B，立即數(shù)占32位，則存放順序?yàn)椋?/p>

若在大端機(jī)器上，則存放順序如何？401200012345401245230100000123451240452301001240100510041003100210011000地址只需要考慮指令中立即數(shù)的順序！ByteSwapProblem（字節(jié)交換問題）785634120123increasingbyteaddressBigEndian123456780123LittleEndian

每個系統(tǒng)內(nèi)部是一致的，但在系統(tǒng)間通信時可能會發(fā)生問題！因?yàn)轫樞虿煌枰M(jìn)行順序轉(zhuǎn)換音、視頻和圖像等文件格式或處理程序都涉及到字節(jié)順序問題

ex.Littleendian:GIF,PCPaintbrush,MicrosoftRTF,etc

Bigendian:AdobePhotoshop,JPEG,MacPaint,etc

上述存放在0號單元的數(shù)據(jù)（字）是什么？12345678H？78563412H？存放方式不同的機(jī)器間程序移植或數(shù)據(jù)通信時，會發(fā)生什么問題？Alignment(對齊)目前機(jī)器字長一般為32位或64位，而存儲器地址按字節(jié)編址指令系統(tǒng)支持對字節(jié)、半字、字及雙字的運(yùn)算，也有位處理指令各種不同長度的數(shù)據(jù)存放時，有兩種處理方式:

按邊界對齊（假定存儲字的寬度為32位，按字節(jié)編址）字地址：4的倍數(shù)(低兩位為0)半字地址：2的倍數(shù)(低位為0)字節(jié)地址：任意不按邊界對齊壞處：可能會增加訪存次數(shù)！（學(xué)了第四章存儲器組織后會更明白！）Alignment:要求數(shù)據(jù)的地址是相應(yīng)的邊界地址每4個字節(jié)可同時讀寫按邊界對齊

邊界不對齊00040812160字節(jié)1字節(jié)2字節(jié)3字節(jié)0004081216字節(jié)0字節(jié)1

字節(jié)2

字節(jié)3Alignment(對齊)

如：inti,shortk,doublex,charc,shortj,……

則：&i=0;&k=4;&x=8;&c=16;&j=18;……

則：&i=0;&k=4;&x=6;&c=14;&j=15;……x：3個周期j：2個周期x：2個周期j：1個周期雖節(jié)省了空間，但增加了訪存次數(shù)！需要權(quán)衡，目前來看，浪費(fèi)一點(diǎn)存儲空間沒有關(guān)系！存儲器按字節(jié)編址每次只能讀寫某個字地址開始的4個單元中連續(xù)的1個、2個、3個或4個字節(jié)ikxc,jAlignment(對齊)舉例例如，考慮下列兩個結(jié)構(gòu)聲明：structS1{ int i；

char c；

int j；}；structS2{ int i；

int j；

char c；}；在要求對齊的情況下，哪種結(jié)構(gòu)聲明更好？S1：icXXXj048S2：icj048需要12個字節(jié)只需要9個字節(jié)對于“structS2d[4]”，只分配9個字節(jié)能否滿足對齊要求？S2：icXXXj048不能！也需要12個字節(jié)S2比S1好數(shù)據(jù)的檢/糾錯（ErrorDetect/Correct）為什么要進(jìn)行數(shù)據(jù)的錯誤檢測與校正？

存取和傳送時，由于元器件故障或噪音干擾等原因會出現(xiàn)差錯。措施：

(1)從計算機(jī)硬件本身的可靠性入手，在電路、電源、布線等各方面采取必要的措施，提高計算機(jī)的抗干擾能力；(2)采取相應(yīng)的數(shù)據(jù)檢錯和校正措施，自動地發(fā)現(xiàn)并糾正錯誤。如何進(jìn)行錯誤檢測與校正？大多采用“冗余校驗(yàn)”思想，即除原數(shù)據(jù)信息外，還增加若干位編碼，這些新增的代碼被稱為校驗(yàn)位。存儲器或傳輸線路ff比較糾正器MPM’P”P’M出錯信號數(shù)據(jù)輸出數(shù)據(jù)輸入P為校驗(yàn)位數(shù)據(jù)的檢/糾錯比較的結(jié)果為以下三種情況之一：

①沒有檢測到錯誤，得到的數(shù)據(jù)位直接傳送出去。②檢測到差錯，并可以糾錯。數(shù)據(jù)位和比較結(jié)果一起送入糾錯器，將正確數(shù)據(jù)位傳送出去。③

檢測到錯誤，但無法確認(rèn)哪位出錯，因而不能進(jìn)行糾錯處理，此時，報告出錯情況。BACK存儲器或傳輸線路ff比較糾正器MPM’P”P’M出錯信號數(shù)據(jù)輸出數(shù)據(jù)輸入碼字和碼距什么叫碼距？由若干位代碼組成的一個字叫“碼字”兩個碼字中具有不同代碼的位的個數(shù)叫這兩個碼字間的“距離”碼制中各碼字間最小距離為“碼距”，它就是這個碼制的距離。問題：“8421”碼的碼距是幾？2（0010）和3（0011）間距離為1，“8421”碼制的碼距為1。數(shù)據(jù)校驗(yàn)中“碼字”指數(shù)據(jù)位和校驗(yàn)位按某種規(guī)律排列得到的代碼碼距與檢錯、糾錯能力的關(guān)系（當(dāng)d≤4）

①若碼距d為奇數(shù)，則能發(fā)現(xiàn)d-1位錯，或能糾正(d-1)/2位錯。②若碼距d為偶數(shù)，則能發(fā)現(xiàn)d/2位錯，并能糾正(d/2-1)位錯。常用的數(shù)據(jù)校驗(yàn)碼有：

奇偶校驗(yàn)碼、海明校驗(yàn)碼、循環(huán)冗余校驗(yàn)碼。奇偶校驗(yàn)碼

基本思想：增加一位奇（偶）校驗(yàn)位并一起存儲或傳送，根據(jù)終部件得到的相應(yīng)數(shù)據(jù)和校驗(yàn)位，再求出新校驗(yàn)位，最后根據(jù)新校驗(yàn)位確定是否發(fā)生了錯誤。

實(shí)現(xiàn)原理：假設(shè)數(shù)據(jù)B=bn-1bn-2...b1b0從源部件傳送至終部件。在終部件接收到的數(shù)據(jù)為B’=bn-1’bn-2’...b1’b0’。第一步：在源部件求出奇（偶）校驗(yàn)位P。

若采用奇校驗(yàn)，則P=bn-1⊕bn-2⊕...⊕b1⊕b0⊕1。若采用偶校驗(yàn)，則P=bn-1⊕bn-2⊕...⊕b1⊕b0。第二步：在終部件求出奇（偶）校驗(yàn)位P’。

若采用奇校驗(yàn)，則P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’⊕1。若采用偶校驗(yàn)，則P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’。第三步：計算最終的校驗(yàn)位P*，并根據(jù)其值判斷有無奇偶錯。

假定P在終部件接受到的值為P’’，則P*=P’⊕P”①若P*=1，則表示終部件接受的數(shù)據(jù)有奇數(shù)位錯。②若P*=0，則表示終部件接受的數(shù)據(jù)正確或有偶數(shù)個錯。奇偶校驗(yàn)法的特點(diǎn)問題：奇偶校驗(yàn)碼的碼距是幾？為什么？碼距d=2。在奇偶校驗(yàn)碼中，若兩個數(shù)中有奇數(shù)位不同，則它們相應(yīng)的校驗(yàn)位就不同；若有偶數(shù)位不同，則雖校驗(yàn)位相同，但至少有兩位數(shù)據(jù)位不同。因而任意兩個碼字之間至少有兩位不同。特點(diǎn)根據(jù)碼距和糾/檢錯能力的關(guān)系，它只能發(fā)現(xiàn)奇數(shù)位出錯，不能發(fā)現(xiàn)偶數(shù)位出錯，而且也不能確定發(fā)生錯誤的位置，不具有糾錯能力。開銷小，適用于校驗(yàn)一字節(jié)長的代碼，故常被用于存儲器讀寫檢查或按字節(jié)傳輸過程中的數(shù)據(jù)校驗(yàn)因?yàn)橐蛔止?jié)長的代碼發(fā)生錯誤時，1位出錯的概率較大，兩位以上出錯則很少，所以可用奇偶校驗(yàn)。海明校驗(yàn)碼由RichardHamming于1950年提出，目前還被廣泛使用。主要用于存儲器中數(shù)據(jù)存取校驗(yàn)。基本思想：奇偶校驗(yàn)碼對整個數(shù)據(jù)編碼生成一位校驗(yàn)位。因此這種校驗(yàn)碼檢錯能力差，并且沒有糾錯能力。如果將整個數(shù)據(jù)按某種規(guī)律分成若干組，對每組進(jìn)行相應(yīng)的奇偶檢測，就能提供多位檢錯信息，從而對錯誤位置進(jìn)行定位，并將其糾正。海明校驗(yàn)碼實(shí)質(zhì)上就是一種多重奇偶校驗(yàn)碼。處理過程：最終比較時按位進(jìn)行異或，以確定是否有差錯。這種異或操作所得到的結(jié)果稱為故障字（syndromeword）。顯然，校驗(yàn)碼和故障字的位數(shù)是相同。每一組一個校驗(yàn)位，校驗(yàn)碼位數(shù)等于組數(shù)！每一組內(nèi)采用一位奇偶校驗(yàn)！校驗(yàn)碼位數(shù)的確定假定數(shù)據(jù)位數(shù)為n，校驗(yàn)碼為k位，則故障字位數(shù)也為k位。k位故障字所能表示的狀態(tài)最多是2K，每種狀態(tài)可用來說明一種出錯情況。若只有一位錯，則結(jié)果可能是：數(shù)據(jù)中某一位錯(n種可能)校驗(yàn)碼中有一位錯(k種可能)無錯(1種可能)假定最多有一位錯，則n和k必須滿足下列關(guān)系：2K≥1+n+k，即：2K-1≥n+k有效數(shù)據(jù)位數(shù)和校驗(yàn)碼位數(shù)間的關(guān)系當(dāng)數(shù)據(jù)有8位時，校驗(yàn)碼和故障字都應(yīng)有4位。說明：4位故障字最多可表示16種狀態(tài)，而單個位出錯情況最多只有12種可能（8個數(shù)據(jù)位和4個校驗(yàn)位），再加上無錯的情況，一共有13種。所以，用16種狀態(tài)表示13種情況應(yīng)是足夠了。1+n+k種情況有效數(shù)據(jù)位數(shù)和校驗(yàn)碼位數(shù)間的關(guān)系

單糾錯單糾錯/雙檢錯數(shù)據(jù)位數(shù)校驗(yàn)位數(shù)增加率校驗(yàn)位數(shù)增加率8450562.516531.25637.532618.75721.87564710.94812.512886.2597.0325693.52103.91n和k的關(guān)系：2K-1≥n+k（n和k分別為數(shù)據(jù)位數(shù)和校驗(yàn)位數(shù)）海明碼的分組基本思想:n位數(shù)據(jù)位和k位校驗(yàn)位按某種方式排列為一個（n+k）位的碼字，將該碼字中每個出錯位的位置與故障字的數(shù)值建立關(guān)系，通過故障字的值確定該碼字中哪一位發(fā)生了錯誤，并將其取反來糾正。

根據(jù)上述基本思想，按以下規(guī)則來解釋各故障字的值。

規(guī)則1：

若故障字每位全部是0，則表示沒有發(fā)生錯誤。

規(guī)則2：若故障字中有且僅有一位為1，則表示校驗(yàn)位中有一位出錯，因而不需糾正。

規(guī)則3：若故障字中多位為1，則表示有一個數(shù)據(jù)位出錯，其在碼字中的出錯位置由故障字的數(shù)值來確定。糾正時只要將出錯位取反即可。海明碼的分組

以8位數(shù)據(jù)進(jìn)行單個位檢錯和糾錯為例說明。假定8位數(shù)據(jù)M=M8M7M6M5M4M3M2M1，4位校驗(yàn)位P=P4P3P2P1。根據(jù)規(guī)則將M和P按一定的規(guī)律排到一個12位碼字中。

據(jù)規(guī)則1，故障字為0000時，表示無錯。

據(jù)規(guī)則2，故障字中有且僅有一位為1時，表示校驗(yàn)位中有一位出錯。此時，故障字只可能是0001、0010、0100、1000，將這四種狀態(tài)分別代表校驗(yàn)位中P1、P2、P3、P4位發(fā)生錯誤，因此，它們分別位于碼字的第1、2、4、8位。據(jù)規(guī)則3，將其他多位為1的故障字依次表示數(shù)據(jù)位M1~M8發(fā)生錯誤的情況。因此，數(shù)據(jù)位M1~M8分別位于碼字的第0011(3)、0101(5)、0110(6)、0111(7)、1001(9)、1010(10)、1011(11)、1100(12)位。即碼字的排列為：

M8M7M6M5P4M4M3M2P3M1P2P1這樣，得到故障字S=S4S3S2S1的各個狀態(tài)和出錯情況的對應(yīng)關(guān)系表，可根據(jù)這種對應(yīng)關(guān)系對整個數(shù)據(jù)進(jìn)行分組。是邏輯順序，物理上M和P是分開的！海明校驗(yàn)碼分組情況數(shù)據(jù)位或校驗(yàn)位出錯一定會影響所在組的奇偶性。碼字：M8M7M6M5P4M4M3M2P3M1P2P1例：若M2出錯，則故障字為0101，因而會改變S3和S1所在分組的奇偶性。故M2同時被分到第3(S3)組和第1(S1)組。問題：若P1出錯，則如何？若M8出錯，則如何？P1~0001，分在第1組；M8~1100，分在第4組和第3組故障字S4S3S2S1每一位的值反映所在組的奇偶性SKIP校驗(yàn)位的生成和檢錯、糾錯分組完成后，就可對每組采用相應(yīng)的奇（偶）校驗(yàn)，以得到相應(yīng)的一個校驗(yàn)位。假定采用偶校驗(yàn)(取校驗(yàn)位Pi，使對應(yīng)組中有偶數(shù)個1)，則得到校驗(yàn)位與數(shù)據(jù)位之間存在如下關(guān)系：

P4=M5⊕M6⊕M7⊕M8 P3=M2⊕M3⊕M4⊕M8P2=M1⊕M3⊕M4⊕M6⊕M7

P1=M1⊕M2⊕M4⊕M5⊕M7

碼字：M8M7M6M5P4M4M3M2P3M1P2P1海明校驗(yàn)過程根據(jù)公式求出每一組對應(yīng)的校驗(yàn)位Pi(i=1,2,3,4)數(shù)據(jù)M和校驗(yàn)位P一起被存儲，根據(jù)讀出數(shù)據(jù)M’得新校驗(yàn)位P’讀出校驗(yàn)位P’’與新校驗(yàn)位P’按位進(jìn)行異或操作，得故障字S=S4S3S2S1根據(jù)S的值確定：無錯、僅校驗(yàn)位錯、某個數(shù)據(jù)位錯存儲器或傳輸線路ff比較糾正器MPM’P”P’M出錯信號數(shù)據(jù)輸出數(shù)據(jù)輸入海明碼舉例

假定一個8位數(shù)據(jù)M為：M8M7M6M5M4M3M2M1=01101010，根據(jù)上述公式求出相應(yīng)的校驗(yàn)位為：P4=M5⊕M6⊕M7⊕M8=0⊕1⊕1⊕0=0 P3=M2⊕M3⊕M4⊕M8=1⊕0⊕1⊕0=0P2=M1⊕M3⊕M4⊕M6⊕M7=0⊕0⊕1⊕1⊕1=1P1=M1⊕M2⊕M4⊕M5⊕M7=0⊕1⊕1⊕0⊕1=1假定12位碼字(M8M7M6M5P4M4M3M2P3M1P2P1)讀出后為：(1)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=P=0011

(2)數(shù)據(jù)位M’=01111010，校驗(yàn)位P’’=P=0011(3)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=

1011

要求分別考察每種情況的故障字。(1)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=P=0011，即無錯。因?yàn)镸’=M，所以P’=P，因此S=P’’⊕P’=P⊕P=0000。海明碼舉例(2)數(shù)據(jù)位M’=01111010，校驗(yàn)位P’’=P=0011，即M5錯。對M’生成新的校驗(yàn)位P’為： P4’

=M5’⊕M6’⊕M7’⊕M8’=1⊕1⊕1⊕0=1 P3’=M2’⊕M3’⊕M4’⊕M8’=1⊕0⊕1⊕0=0P2’

=M1’⊕M3’⊕M4’⊕M6’⊕M7’=0⊕0⊕1⊕1⊕1=1 P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=0⊕1⊕1⊕1⊕1=0故障字S為：

S4=P4’⊕P4’’=1⊕0=1

S3=P3’⊕P3’’=0⊕0=0 S2=P2’⊕P2’’=1⊕1=0 S1=P1’⊕P1’’=

0⊕1=1因此，錯誤位是第9位，排列的是數(shù)據(jù)位M5，所以檢錯正確,糾錯時，只要將碼字的第9位（M5）取反即可。海明碼舉例(3)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=1011，即：校驗(yàn)碼第4位(P4)錯。因?yàn)镸’=M，所以P’=P，因此故障位S為：S4=P4’⊕P4’’=0⊕1=1S3=P3’⊕P3’’=0⊕0=0S2=P2’⊕P2’’=1⊕1=0S1=P1’⊕P1’’=

1⊕1=0錯誤位是第1000位(即第8位)，這位上排列的是校驗(yàn)位P4，所以檢錯時發(fā)現(xiàn)數(shù)據(jù)正確，不需糾錯。單糾錯和雙檢錯碼單糾錯碼（SEC）問題：上述(n=8/k=4)海明碼的碼距是幾？碼距d=3。因?yàn)椋粲幸晃怀鲥e，則因該位至少要參與兩組校驗(yàn)位的生成，因而至少引起兩個校驗(yàn)位的不同。兩個校驗(yàn)位加一個數(shù)據(jù)位等于3。

例如，若M1出錯，則故障字為0011，即P2和P1兩個校驗(yàn)位發(fā)生改變，12位碼字中有三位（M1、P2和P1）不同。根據(jù)碼距與檢錯、糾錯能力的關(guān)系，知：這種碼制能發(fā)現(xiàn)兩位錯，或?qū)蝹€位出錯進(jìn)行定位和糾錯。這種碼稱為單糾錯碼（SEC）。單糾錯和雙檢錯碼單糾錯和雙檢錯碼（SEC-DED）具有發(fā)現(xiàn)兩位錯和糾正一位錯的能力，稱為單糾錯和雙檢錯碼（SEC-DED）。若要成為SEC-DED，則碼距需擴(kuò)大到d=4。為此，還需增加一位校驗(yàn)位P5，將P5排列在碼字的最前面，即：P5M8M7M6M5P4M4M3M2P3M1P2P1，并使得數(shù)據(jù)中的每一位都參與三個校驗(yàn)位的生成。從表中可看出除了M4和M7外，其余位都只參與了兩個校驗(yàn)位的生成。因此P5按下式求值：P5=M1⊕M2⊕M3⊕M5⊕M6⊕M8當(dāng)任意一個數(shù)據(jù)位發(fā)生錯誤時，必將引起三個校驗(yàn)位發(fā)生變化，所以碼距為4。SKIP循環(huán)冗余碼

循環(huán)冗余校驗(yàn)碼（CyclicRedundancyCheck），簡稱CRC碼具很強(qiáng)的檢錯、糾錯能力。用于大批量數(shù)據(jù)存儲和傳送(如：外存和通信)中的數(shù)據(jù)校驗(yàn)。

為什么大批量數(shù)據(jù)不用奇偶校驗(yàn)？在每個字符后增加一位校驗(yàn)位會增加大量的額外開銷；尤其在網(wǎng)絡(luò)通信中，對傳輸?shù)亩M(jìn)制比特流沒有必要再分解成一個個字符，因而無法采用奇偶校驗(yàn)碼。通過某種數(shù)學(xué)運(yùn)算來建立數(shù)據(jù)和校驗(yàn)位之間的約定關(guān)系。

奇偶校驗(yàn)碼和海明校驗(yàn)碼都是以奇偶檢測為手段的。網(wǎng)絡(luò)或通信課程中會學(xué)到。CRC碼的檢錯方法

基本思想：數(shù)據(jù)信息M(x)為一個n位的二進(jìn)制數(shù)據(jù)，將M(x)左移k位后，用一個約定的“生成多項(xiàng)式”G(x)相除，G(x)是一個k+1位的二進(jìn)制數(shù)，相除后得到的k位余數(shù)就是校驗(yàn)位。校驗(yàn)位拼接到M(x)后，形成一個n+k位的代碼，稱該代碼為循環(huán)冗余校驗(yàn)(CRC)碼，也稱（n+k,n）碼。一個CRC碼一定能被生成多項(xiàng)式整除，當(dāng)數(shù)據(jù)和校驗(yàn)位一起送到接受端后，只要將接受到的數(shù)據(jù)和校驗(yàn)位用