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

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

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

10n-2+…+xn-2*

101+xn-1*

100

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

2n-2+…+xn-2*

21+xn-1*

20

r進制數(shù)采用r個計數(shù)符號逢r進1一個n位的r進制數(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)換將二進制數(shù)轉(zhuǎn)換成八進制數(shù)從小數(shù)點的位置開始每三位一組分別轉(zhuǎn)換成相應的八進制數(shù)的計數(shù)符號不足三位時補0將二進制數(shù)轉(zhuǎn)換成十六進制數(shù)四位一組進行轉(zhuǎn)換例0010101102=1268=5616數(shù)制轉(zhuǎn)換將八進制數(shù)轉(zhuǎn)換成二進制數(shù)從小數(shù)點的位置開始每一位八進制數(shù)分別轉(zhuǎn)換成三位二進制數(shù)將八進制數(shù)轉(zhuǎn)換成二進制數(shù)十進制數(shù)轉(zhuǎn)換成二進制數(shù)整數(shù)部分采用除2取余法小數(shù)部分采用乘2取整法x02n-1+x12n-2+…+xn-221+xn-120【例1】

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

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

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

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

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

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

無符號數(shù)的編碼定點整數(shù)數(shù)值表示

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

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

定點小數(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有符號數(shù)的編碼計算機中的數(shù)據(jù)編碼都是有一定的表示范圍的，離散的；而不像數(shù)學中的數(shù)可以是任意大的，連續(xù)的。在數(shù)據(jù)編碼中，如果數(shù)據(jù)值超過了編碼所能表示的數(shù)值范圍，則稱為數(shù)值溢出。計算機中表示一個帶符號數(shù)的方法有：原碼表示法、反碼表示法、補碼表示法和移碼表示法四種。1.原碼表示法特點：簡便編碼方法（加符號位）例： [3]原

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

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

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

-x=4

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

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

≤x≤1-2-n零有兩個編碼：000…0和111…14.移碼表示法編碼方法[x]移=2n+x數(shù)值范圍-2n≤x≤2n-1符號位：1表示正號，0代表負號0有惟一的編碼保持了數(shù)據(jù)原有的大小順序定點小數(shù)沒有移碼定義4.移碼表示法例設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ù)的符號數(shù)據(jù)真值的最高位則不代表符號x表示真值[x]xx表示編碼2.1.3浮點數(shù)的編碼

E的編碼：移碼或補碼

S與M的編碼：原碼或補碼

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

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

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

xk+1=x1+x2+…+xk

+1mod2偶校驗：

xk+1=x1+x2+…+xk

mod2例：偶校驗

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

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

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

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

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

w1+w2+w3+w5=0

w2+w3+w4+w6=0

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

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

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

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

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}問該碼字是否合法？如果不合法，是哪一位發(fā)生了錯誤？應該糾正成什么碼字？3.循環(huán)碼定義線性碼中若一個n位編碼V={vn-1,vn-2,…,