第二章數(shù)據(jù)編碼和數(shù)據(jù)運(yùn)算1

第二章數(shù)據(jù)編碼和數(shù)據(jù)運(yùn)算2.1

數(shù)據(jù)與文字的編碼數(shù)字計(jì)算機(jī)中采用二進(jìn)制的數(shù)據(jù)表示方式，因?yàn)槎M(jìn)制數(shù)能方便可靠地用數(shù)字電路的邏輯電平表示。在計(jì)算機(jī)中表示的二進(jìn)制數(shù)據(jù)稱為機(jī)器數(shù)。它是一系列位數(shù)固定而且數(shù)量有限的二進(jìn)制代碼，表示的數(shù)值范圍也是有限的。計(jì)算機(jī)中表示的機(jī)器數(shù)是一系列離散的數(shù)據(jù)。一個(gè)機(jī)器數(shù)所代表的實(shí)際數(shù)值稱為真值2.1.1數(shù)制的轉(zhuǎn)換十進(jìn)制數(shù)采用十個(gè)計(jì)數(shù)符號(hào)計(jì)數(shù)規(guī)則逢十進(jìn)一一個(gè)n位的十進(jìn)制數(shù)x0x1…xn-2xn-1代表的數(shù)值為：x0*10n-1+x1*

10n-2+…+xn-2*

101+xn-1*

100

二進(jìn)制數(shù)采用2個(gè)計(jì)數(shù)符號(hào)逢2進(jìn)1一個(gè)n位的二進(jìn)制數(shù)x0x1…xn-2xn-1代表的數(shù)值為：x0*2n-1+x1*

2n-2+…+xn-2*

21+xn-1*

20

r進(jìn)制數(shù)采用r個(gè)計(jì)數(shù)符號(hào)逢r進(jìn)1一個(gè)n位的r進(jìn)制數(shù)x0x1…xn-2xn-1代表的數(shù)值為：x0*rn-1+x1*

rn-2+…+xn-2*

r1+xn-1*

r00≤xi≤r-1(0≤i≤n-1)有小數(shù)的情形數(shù)制轉(zhuǎn)換將二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)從小數(shù)點(diǎn)的位置開(kāi)始每三位一組分別轉(zhuǎn)換成相應(yīng)的八進(jìn)制數(shù)的計(jì)數(shù)符號(hào)不足三位時(shí)補(bǔ)0將二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)四位一組進(jìn)行轉(zhuǎn)換例0010101102=1268=5616數(shù)制轉(zhuǎn)換將八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)從小數(shù)點(diǎn)的位置開(kāi)始每一位八進(jìn)制數(shù)分別轉(zhuǎn)換成三位二進(jìn)制數(shù)將八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)整數(shù)部分采用除2取余法小數(shù)部分采用乘2取整法x02n-1+x12n-2+…+xn-221+xn-120【例1】

將十進(jìn)制整數(shù)100轉(zhuǎn)換成二進(jìn)制整數(shù)。解：用2連續(xù)除100，直至商小于2，算式如下：運(yùn)算結(jié)果：100=1100100B【例2】

將十進(jìn)制小數(shù)0.618轉(zhuǎn)換成二進(jìn)制小數(shù)。解：用2連續(xù)乘以0.618，小數(shù)部分為0或保留4位小數(shù)，算式如下：

運(yùn)算結(jié)果：0.618≈0.1001B。不同數(shù)制之間的轉(zhuǎn)換規(guī)則：二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)——采用“四位合一位”法十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)——采用“一位分四位”法二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)——按權(quán)展開(kāi)后相加

十六進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)——按權(quán)展開(kāi)后相加

十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)——采用“除以2取余”法十進(jìn)制整數(shù)轉(zhuǎn)換成十六進(jìn)制整數(shù)——采用“除以16取余”法十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)——采用“乘2取整”法十進(jìn)制小數(shù)轉(zhuǎn)換成十六進(jìn)制小數(shù)——采用“乘16取整”法

2.1.2定點(diǎn)數(shù)的編碼定點(diǎn)數(shù)是指小數(shù)點(diǎn)位置固定不變的數(shù)據(jù)。在計(jì)算機(jī)中，通常采用兩種類型的定點(diǎn)數(shù)表示。一種定點(diǎn)數(shù)把小數(shù)點(diǎn)定在最低位數(shù)的右面，這種定點(diǎn)數(shù)稱為定點(diǎn)整數(shù)，因?yàn)樗鼘?shí)際沒(méi)有小數(shù)。另一種定點(diǎn)數(shù)把小數(shù)點(diǎn)固定在最高位數(shù)的后面，即純小數(shù)表示，稱為定點(diǎn)小數(shù)，它只保留小數(shù)點(diǎn)后面的數(shù)據(jù)，小數(shù)點(diǎn)前面的一位數(shù)據(jù)固定為零。這種二進(jìn)制定點(diǎn)數(shù)的表示可以直接在計(jì)算機(jī)中表示，計(jì)算機(jī)中表示無(wú)符號(hào)數(shù)就直接用這種二進(jìn)制的表示作為數(shù)據(jù)的編碼機(jī)器數(shù)計(jì)算機(jī)中表示的二進(jìn)制數(shù)據(jù)真值一個(gè)機(jī)器數(shù)所代表的實(shí)際數(shù)值定點(diǎn)數(shù)定點(diǎn)整數(shù)定點(diǎn)小數(shù)2.1.2定點(diǎn)數(shù)的編碼機(jī)器數(shù)無(wú)符號(hào)數(shù)半字、字、雙倍字、四倍字有符號(hào)數(shù)原碼、反碼、補(bǔ)碼、移碼1位符號(hào)位

無(wú)符號(hào)數(shù)的編碼定點(diǎn)整數(shù)數(shù)值表示

x=x0x1x2…xn xi={0,1},0≤i≤n

x02n+x12n-1+…+xn-121+xn數(shù)值范圍 0≤x≤2n+1-1無(wú)符號(hào)數(shù)的編碼

定點(diǎn)小數(shù)數(shù)值表示

x=x0.

x1x2…xn

x0=0,xi={0,1},0≤i≤n x12-1+…+xn-12-n+1+xn2-n

數(shù)值范圍

0≤x≤1-2-n有符號(hào)數(shù)的編碼計(jì)算機(jī)中的數(shù)據(jù)編碼都是有一定的表示范圍的，離散的；而不像數(shù)學(xué)中的數(shù)可以是任意大的，連續(xù)的。在數(shù)據(jù)編碼中，如果數(shù)據(jù)值超過(guò)了編碼所能表示的數(shù)值范圍，則稱為數(shù)值溢出。計(jì)算機(jī)中表示一個(gè)帶符號(hào)數(shù)的方法有：原碼表示法、反碼表示法、補(bǔ)碼表示法和移碼表示法四種。1.原碼表示法特點(diǎn)：簡(jiǎn)便編碼方法（加符號(hào)位）例： [3]原

=00000011 [-3]原=100000111.原碼表示法零有兩種表示方式例設(shè)x=101010，y=-101010，求[x]原和[y]原解： [x]原=00101010 [y]原=10101010例設(shè)x=0.1010，y=-0.1010，求[x]原和[y]原解： [x]原=0.101010 [y]原=1.1010102.補(bǔ)碼表示法特點(diǎn)：便于運(yùn)算例： [3]補(bǔ)

=00000011 [-3]補(bǔ)=111111012‘scomplementcoding2.補(bǔ)碼表示法方法1正數(shù)：直接取其原來(lái)的二進(jìn)制碼（加符號(hào)位0）負(fù)數(shù)：對(duì)其二進(jìn)制碼按位取反之后再在最低位加1例：[010101]補(bǔ)=00010101

[-010101]補(bǔ)=11101010+1=11101011方法2正數(shù)：直接取其原來(lái)的二進(jìn)制碼負(fù)數(shù)：從二進(jìn)制碼的最低位開(kāi)始，對(duì)遇到的0和第一個(gè)1取其原來(lái)的二進(jìn)制編碼，從第一個(gè)1以后開(kāi)始直到最高位均取其相反編碼。例：[101010]補(bǔ)=0101010 [-101010]補(bǔ)=1010110定點(diǎn)小數(shù)的補(bǔ)碼編碼x=x0.x1…xn數(shù)值范圍：-1≤x≤1-2-n例設(shè)x=0.101010，y=-0.101010，求[x]補(bǔ)和[y]補(bǔ)。解： [x]補(bǔ)=0.101010 [y]補(bǔ)=1.010110補(bǔ)碼求值的方法公式法x=-x02n+x12n-1+…+xn-12+xn例如：10000100的真值為-128+4=-124求補(bǔ)法[x]補(bǔ)與[-x]補(bǔ)的關(guān)系例:[x]補(bǔ)=11111100 [-x]補(bǔ)=00000100

-x=4

x=-43.反碼表示法例：[1010]反=01010[-1010]反=101011‘scomplementcoding反碼的表示法是用對(duì)負(fù)值的各位取反的表示方法.對(duì)于給定的反瑪[x]反的代碼，其數(shù)值：3.反碼表示法編碼方法正數(shù)的反碼與原碼相同負(fù)數(shù)的反碼是將二進(jìn)制位按位取反數(shù)值范圍 -2n

+1≤x≤2n-1定點(diǎn)小數(shù)-1+2-n

≤x≤1-2-n零有兩個(gè)編碼：000…0和111…14.移碼表示法編碼方法[x]移=2n+x數(shù)值范圍-2n≤x≤2n-1符號(hào)位：1表示正號(hào)，0代表負(fù)號(hào)0有惟一的編碼保持了數(shù)據(jù)原有的大小順序定點(diǎn)小數(shù)沒(méi)有移碼定義4.移碼表示法例設(shè)x=101010，y=-101010，求[x]移和[y]移。解： [x]移=1000000+101010=10101010 [y]移=1000000+(-101010)=10000000-0101010=01010110四種編碼的例子數(shù)據(jù)真值與數(shù)據(jù)編碼數(shù)據(jù)的真值中可以把最高位的0省略數(shù)據(jù)編碼中不能忽略任何位置上的0或1數(shù)據(jù)編碼的最高位代表數(shù)據(jù)的符號(hào)數(shù)據(jù)真值的最高位則不代表符號(hào)x表示真值[x]xx表示編碼2.1.3浮點(diǎn)數(shù)的編碼

E的編碼：移碼或補(bǔ)碼

S與M的編碼：原碼或補(bǔ)碼

R進(jìn)制的含義：多個(gè)二進(jìn)制位構(gòu)成一組，代表一個(gè)R進(jìn)制位例：0001111100000000或00111,1.1100000000浮點(diǎn)數(shù)的編碼規(guī)格化0.12=0.1×20=0.01×21要求數(shù)值中小數(shù)點(diǎn)后第一位為非零為了在尾數(shù)中表示最多的有效數(shù)據(jù)位為了數(shù)據(jù)表示的唯一性機(jī)器零全部為0特殊的數(shù)據(jù)編碼規(guī)格化的編碼基數(shù)為2的浮點(diǎn)數(shù)規(guī)格化尾數(shù)的絕對(duì)值在1/2到1之間基數(shù)為R的浮點(diǎn)數(shù)規(guī)格化尾數(shù)的絕對(duì)值在1/R到1之間原碼數(shù)據(jù)位的最高位為1補(bǔ)碼小數(shù)點(diǎn)前后兩位互不相同尾數(shù)0.1010和1.0101是規(guī)格化的尾數(shù)0.0101和1.1010是非規(guī)格化的x.1xxxxxx0.1xxxxxx1.0xxxxxx規(guī)格化的編碼例2-1

對(duì)數(shù)據(jù)12310作規(guī)格化浮點(diǎn)數(shù)的編碼，假定1位符號(hào)位，基數(shù)為2，階碼5位，采用移碼，尾數(shù)10位，采用補(bǔ)碼。解：12310=11110112=0.11110110002×27

[7]移=10000+00111=10111 [0.1111011000]補(bǔ)=0.1111011000 [123]浮=0101111111011000浮點(diǎn)數(shù)的表示范圍浮點(diǎn)數(shù)的溢出表現(xiàn)為階碼的溢出浮點(diǎn)數(shù)的上溢(overflow)數(shù)據(jù)大于階碼所能表示的數(shù)據(jù)浮點(diǎn)數(shù)的下溢(underflow)數(shù)據(jù)小于階碼所能表示的數(shù)值時(shí)2.1.4文字的編碼1.西文字符的編碼ASCII碼2.漢字的編碼輸入碼數(shù)字編碼、拼音碼和字形碼機(jī)內(nèi)碼用于漢字信息存儲(chǔ)、交換、檢索等操作3.十進(jìn)制數(shù)的編碼漢字的存放漢字的表示方法（一級(jí)漢字3755個(gè)，二級(jí)漢字3008個(gè)）輸入碼國(guó)標(biāo)碼一級(jí)（16~55）*94二級(jí)（56~87）*94圖形符號(hào)（682個(gè)）（01~09）*94拼音、五筆漢字內(nèi)碼：漢字信息的存儲(chǔ)，交換和檢索的機(jī)內(nèi)代碼，兩個(gè)字節(jié)組成，每個(gè)字節(jié)高位都為1（區(qū)別于英文字符）漢字字模碼：漢字字形點(diǎn)陣漢字庫(kù)十進(jìn)制數(shù)的編碼編碼的方法字符串形式ASCII碼的高位置0壓縮的十進(jìn)制數(shù)串形式對(duì)每一位十進(jìn)制數(shù)用四個(gè)二進(jìn)制位編碼表示BCD碼(binarycodeddecimal)用4位編碼中的剩余6個(gè)代碼表示符號(hào)2.1.5檢錯(cuò)碼和糾錯(cuò)碼能夠發(fā)現(xiàn)某些錯(cuò)誤或具有自動(dòng)糾錯(cuò)能力的數(shù)據(jù)編碼在代碼中增加冗余位以使代碼具有某種特征分組碼卷積碼1.奇偶校驗(yàn)碼奇校驗(yàn)：

xk+1=x1+x2+…+xk

+1mod2偶校驗(yàn)：

xk+1=x1+x2+…+xk

mod2例：偶校驗(yàn)

000000000 000100011 001000101奇偶校驗(yàn)碼的原理碼距兩個(gè)合法代碼對(duì)應(yīng)位上編碼不同的位數(shù)海明距離在編碼中引入一定的冗余，增加代碼的最小碼距，使得編碼中出現(xiàn)一個(gè)錯(cuò)誤時(shí)就成為非法代碼。問(wèn)題某一個(gè)檢錯(cuò)碼具有以下4個(gè)碼字，指出各碼字之間的碼距：0000000000000001111111111000001111111111如果碼距更大...合法代碼合法代碼非法代碼非法代碼非法代碼非法代碼非法代碼合法代碼? 2.海明碼海明碼：（n,k） 碼長(zhǎng) n=2m-1

信息位數(shù) k=2m-m-1

校驗(yàn)位數(shù) m=n-k

最小碼距 d=3(7,4)海明碼的例子

c1=x1+x2+x3 c2=x2+x3+x4 c3=x1+x2+x4將這些信息位和校驗(yàn)位構(gòu)成碼字w，即w={x1,x2,x3,x4,c1,c2,c3}={w1,w2,w3,w4,w5,w6,w7}校驗(yàn)方程：

w1+w2+w3+w5=0

w2+w3+w4+w6=0

w1+w2+w4+w7=0(7,4)海明碼的例子例用上述定義的海明碼對(duì)數(shù)據(jù)1010進(jìn)行編碼。解：根據(jù)上述海明碼定義，得

c1=x1+x2+x3=0 (mod2)

c2=x2+x3+x4=1 (mod2)

c3=x1+x2+x4=1 (mod2)所以編碼的結(jié)果為1010011。練習(xí)對(duì)于海明碼校驗(yàn)方程

w1+w2+w3+w5=0

w2+w3+w4+w6=0

w1+w2+w4+w7=0假如出現(xiàn)了碼字

{w1,w2,w3,w4,w5,w6,w7}={0,1,0,1,0,1,0}問(wèn)該碼字是否合法？如果不合法，是哪一位發(fā)生了錯(cuò)誤？應(yīng)該糾正成什么碼字？3.循環(huán)碼定義線性碼中若一個(gè)n位編碼V={vn-1,vn-2,…,