第3章-kuaisu數(shù)據(jù)表示與運算算法分析

第3章-kuaisu數(shù)據(jù)表示與運算算法分析第一頁，共81頁。本章主要內(nèi)容3.1信息編碼概念、碼制轉(zhuǎn)換3.2數(shù)據(jù)表示——常用的信息編碼3.3二進制數(shù)值數(shù)據(jù)的編碼與運算算法第一頁第二頁，共81頁。數(shù)字化編碼二要素數(shù)值、文字、符號、語音、圖形、圖像等統(tǒng)稱數(shù)據(jù)，在計算機內(nèi)部，都必須用數(shù)字化編碼的形式被存儲、加工和傳送。數(shù)字化編碼二要素:少量簡單的基本符號一定的組合規(guī)則用以表示大量復雜多樣的信息第二頁第三頁，共81頁?；a（二進制碼）只使用兩個基本點符號：１

０符號個數(shù)最少，物理上容易實現(xiàn)與二值邏輯的真

假

兩個值對應(yīng)簡單用二進制碼表示數(shù)值數(shù)據(jù)運算規(guī)則簡單第三頁第四頁，共81頁。進位記數(shù)法與進制轉(zhuǎn)換進位記數(shù)法：N=Dm-1Dm-2Dm-3…D1D0D-1D-2…D-k每個Di的單位值都賦以固定的權(quán)值ri（r稱為基），則上式可寫成：例如：十進制數(shù)1234，可寫成：1234=1*10^3+2*10^2+3*10^1+4*10^0第四頁第五頁，共81頁。十進制轉(zhuǎn)二進制整數(shù)部分除2取余小數(shù)部分乘2取整211222521011010.625*210.25*200.5*210.0除盡為止

求得位數(shù)滿足要求為止低高高低從二進制數(shù)求其十進制的值，逐位碼權(quán)累加求和第五頁第六頁，共81頁。二到八或十六進制轉(zhuǎn)換二到八從小數(shù)點向左右三位一分組（10011100.01)2=(234.2)8010

二到十六從小數(shù)點向左右四位一分組（10011100.01)2=(9C.4)16

0100

說明：整數(shù)部分不足位數(shù)對轉(zhuǎn)換無影響，

小數(shù)部分不足位數(shù)要補零湊足，否則出錯。第六頁第七頁，共81頁。二進制數(shù)據(jù)算術(shù)運算規(guī)則(1)加法運算規(guī)則0+0=0例如：01010+1=1+)00011+0=101101+1=0并產(chǎn)生進位(2)減法運算規(guī)則0-0=0例如：10110-1=1并產(chǎn)生借位-)01011-0=101101-1=0第七頁第八頁，共81頁。二進制數(shù)據(jù)算術(shù)運算規(guī)則乘法運算規(guī)則例如：11010X0=0X)01010X1=011011X0=0+1101001X1=11000001除法運算規(guī)則1101例如：1110101/100110011110101

10011011

10010010011001

0

第八頁第九頁，共81頁。本章主要內(nèi)容3.1信息編碼概念、碼制轉(zhuǎn)換3.2數(shù)據(jù)表示——常用的信息編碼3.3二進制數(shù)值數(shù)據(jù)的編碼與運算算法第九頁第十頁，共81頁。數(shù)據(jù)表示邏輯型數(shù)據(jù)字符型數(shù)據(jù)西文字符漢字字符串多媒體信息圖像/圖形聲音視頻數(shù)值型數(shù)據(jù)定點小數(shù)整數(shù)浮點數(shù)十進制數(shù)（BCD碼）檢錯糾錯碼 奇偶校驗海明校驗循環(huán)冗余校驗第十頁第十一頁，共81頁。邏輯型數(shù)據(jù)邏輯型數(shù)據(jù)只有兩個值：真和

假， 正好可以用二進制碼的兩個符號分別表示。 例如1表示真

0

表示假對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的與或

非等基本邏輯運算。其規(guī)則如下：X

Y

X與YX或YX的非

0

0001

0

1011

1

0010

1

1

110

第十一頁第十二頁，共81頁。字符型數(shù)據(jù)字符是最重要的數(shù)據(jù)類型之一，編碼規(guī)則很多，一些常見編碼或術(shù)語：ASCII編碼擴展ASCII碼EBCDIC碼ANSI編碼（MBCS編碼）GB2312碼、GBK碼、BIG5碼Unicode編碼UTF-8碼AmericanStandardCodeforInformationInterchange，美國信息互換標準代碼，主要用于顯示現(xiàn)代英語和其他西歐語言，是最通用的單字節(jié)編碼系統(tǒng)，包含控制字符（如回車鍵、退格、換行鍵等）和可顯示字符（如英文大小寫字符、阿拉伯數(shù)字和西文符號）用7位表示一個字符，共128字符。見P49表3.4。為表示更多的歐洲常用字符，對ASCII進行了擴展，使用8位表示一個字符，共256字符，擴充出來的符號包括表格符號、計算符號、希臘字母和特殊的拉丁符號。ExtendedBinaryCodedDecimalInterchageCode，是IBM公司為大型操作系統(tǒng)開發(fā)的，根據(jù)早期打孔機式的BCD排列而成，使用8位表示一個字符，共256個字符。但英文字母不連續(xù)。為擴充ASCII碼，以顯示本國語言，各國家和地區(qū)制定的標準，如GB2312,BIG5,JIS等，稱為ANSI編碼，又稱為MBCS（Muilti-BytesCharecterSet，多字節(jié)字符集），多為2字節(jié)。簡體中文中ANSI編碼代表GB2312編碼，日文中ANSI編碼代表JIS編碼。GB2312是一個簡體中文字符集，由6763個常用漢字和682個全角的非漢字字符組成，排列成94行94列，用區(qū)位號表示一個字符編碼.GBK是對GB2312的擴充，增加了對人名、古漢語等方面出現(xiàn)的罕用字。BIG5是一個繁體中文字符集，在臺灣、香港與澳門地區(qū)及其他海外華人中普遍使用。各種ANSI編碼不兼容，易出現(xiàn)亂碼，Unicode編碼將所有符號都納入其中（現(xiàn)在可容納100多萬個符號）。但編碼效率不高，比如UCS-4標準)規(guī)定用4個字節(jié)存儲一個符號，每個英文字母前3個字節(jié)為0，對存儲和傳輸都很耗資源。為提高Unicode編碼的效率，推出了UTF-8碼，它可以根據(jù)不同的符號自動選擇編碼的長度，如英文字母采用1個字節(jié)就夠了。第十二頁第十三頁，共81頁。字符串的表示與存儲字符串是指連續(xù)的一串字符，占據(jù)主存中連續(xù)字節(jié)，每個字節(jié)存放一個字符，表示字符串數(shù)據(jù)要給出串存放的主存起始地址和串的長度。對一個主存字的多個字節(jié)，有按從低位到高位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。例如：IFA>BTHENREAD(C)存放方式有：IFAAFI>BTTB>假定每個字4個字節(jié)HENNEHREADDAER(C))C(第十三頁第十四頁，共81頁。多媒體信息編碼1圖圖像圖形2聲音語音：采集→AD轉(zhuǎn)換→編碼音樂：把樂譜、彈奏的樂器類型、擊鍵力度等用符號記錄效果聲3視頻信息由像素點陣構(gòu)成的位圖，色彩豐富、過渡自然，圖像像素點越多（分辨率高），圖像越清晰，文件就越大。一般通過照相、掃描、攝像得到圖形都是位圖圖像，如bmp、jpg等。由數(shù)學公式表達的輪廓線條構(gòu)成矢量圖；放大后圖形不失真，占用空間較小。工程設(shè)計圖、圖表、插圖經(jīng)常以矢量圖形曲線來表示，如photoshop中的PSD文件。把聲音的波形進行編碼---波形法把數(shù)字式電子樂器的彈奏過程記錄下來---合成法第十四頁第十五頁，共81頁。數(shù)值數(shù)據(jù)在計算機內(nèi)的格式定點小數(shù):N=NNN……...Ns-1-n-2整數(shù):N=NNN...NN01snn-1浮點數(shù):N=M

EE...EE

MM...M

ssm-110-1-2-n符號位

階碼位

尾數(shù)數(shù)碼位

總位數(shù)短浮點數(shù):

1

8

2332長浮點數(shù):1

11

5264臨時浮點數(shù):1

15

64

80IEEE標準：階碼用移碼，尾數(shù)用原碼基為2第十五頁第十六頁，共81頁。

8421碼余3碼循環(huán)碼84-2-100000001100000000100010100000101112001001010011011030011011000100101401000111011001005010110001110101160110100110101010701111010100010018100010111100100091001110001001111十進制數(shù)的編碼（BCD編碼）用4位二進制表示1位十進制，從16個編碼中選10個，有多種方案，例如：8421碼，余3碼，循環(huán)碼8421和84-2-1為有權(quán)碼，即每位上的1代表確定的值，如：8421碼中4個位分別表示8、4、2、1，故編碼0111=0*8+1*4+1*2+1*1=784-2-1碼中4個位分別表示8、4、-2、-1，故編碼0111=0*8+1*4+1*(-2)+1*(-1)=1余3碼和循環(huán)碼為無權(quán)碼：無法確定每位上的1代表的值第十六頁第十七頁，共81頁。檢錯糾錯碼為了提高計算機的可靠性，除了采取選用更高可靠性的器件、更好的生產(chǎn)工藝等措施之外，還可以從數(shù)據(jù)編碼上想一些辦法，即采用一點冗余的線路，在原有數(shù)據(jù)位之外再增加一到幾位校驗位，使新得到的碼字帶上某種特性，之后通過檢查該碼字是否仍保持這種特性，來發(fā)現(xiàn)是否出現(xiàn)了錯誤，甚至自動改正錯誤，這就是檢錯糾錯編碼技術(shù)。第十七頁第十八頁，共81頁。三種常用的檢錯糾錯碼奇偶檢錯碼，用于并行數(shù)據(jù)傳送中海明檢錯與糾錯碼，用于并行數(shù)據(jù)傳送中循環(huán)冗余碼，用于串行數(shù)據(jù)傳送中編碼譯碼傳送原始數(shù)據(jù)碼字結(jié)果數(shù)據(jù)形成校驗位的值，加進特征檢查接送的碼字，發(fā)現(xiàn)/改正錯誤第十八頁第十九頁，共81頁。奇偶校驗碼校驗位用于并行數(shù)據(jù)檢錯原理：在k位數(shù)據(jù)碼之外增加1位校驗位，使K+1位碼字中取值為1的位數(shù)保持為偶數(shù)(偶校驗)或奇數(shù)(奇校驗)。例如： 00011000100001 01010010110101原始信息兩個新的碼字

偶校驗奇校驗第十九頁第二十頁，共81頁。奇偶校驗碼的實現(xiàn)電路出錯指示⊕編碼電路譯碼電路P(校驗位)0D6D5D4D3D2D1D0p⊕編碼電路⊕⊕⊕⊕⊕⊕P奇=D6⊕D5⊕D4⊕D3⊕D2⊕D1P偶=D6⊕D5⊕D4⊕D3⊕D2⊕D1E奇=D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕P奇當E奇=1時為合法碼E偶=D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕P偶當E偶=0時為合法碼奇較驗偶校驗7位數(shù)據(jù)位第二十頁第二十一頁，共81頁。奇偶檢驗碼練習--教材P75：4解：數(shù)據(jù)01010111中有5個1，故：奇校驗：001010111 偶校驗：101010111數(shù)據(jù)11010100中有4個1，故：奇校驗：111010100 偶校驗：011010100第二十一頁第二十二頁，共81頁。海明校驗碼用于并行數(shù)據(jù)檢錯糾錯，如主存的ECC(ErrorCorrectingCode)是海明校驗碼的一種典型應(yīng)用。實現(xiàn)原理：在k個數(shù)據(jù)位中加入r個校驗位，將數(shù)據(jù)代碼的碼距比較均勻地拉開，并把每數(shù)據(jù)位分配在幾個奇偶校驗組中。當某位出錯時，就會引起相關(guān)的幾個校驗位值發(fā)生變化，這不僅可發(fā)現(xiàn)錯誤，還能指出哪一位出錯，為進一步自動糾借提供了依據(jù)。第二十二頁第二十三頁，共81頁。海明校驗碼構(gòu)成r個位可表示2r個碼，用其中一個碼表示是否出錯，用其余2r-1個碼指示出錯位置，則最多可指示2r-1個位，數(shù)據(jù)位和檢驗位都有可能出錯，故校驗位數(shù)r和數(shù)據(jù)位數(shù)k應(yīng)滿足不等式：2r-1≥k＋r，也即k≤2r-1-rk值 最小r值1～4 35～11 412～26 527～57 658～119 7例如，校驗位數(shù)r=4，可表示16個碼，可用于糾正被傳送的最多有效數(shù)據(jù)位k=16-1-4=11。第二十三頁第二十四頁，共81頁。(1)校驗位分布若由k個數(shù)據(jù)碼DkDk-1…D1和r個校驗碼PrPr-1…P1構(gòu)成的海明碼格式為HmHm-1…H3H2H1,m=k+r，則：PrPr-1…P1依次分布在H2r-1、H2r-2、…、H4、H2、H1上，DkDk-1…D1按序分布在剩余位置上。例如：5位信息碼D5D4D3D2D1，需4位檢驗碼P4P3P2P1，則9位海明碼為：H9H8H7H6H5H4H3H2H1D5

P4

D4D3D2

P3

D1

P2

P1海明碼編碼規(guī)則-1第二十四頁第二十五頁，共81頁。(2)校驗關(guān)系指海明碼中每個Hi由哪些P?來校驗，關(guān)系為：被校驗位位號=校驗位位號之和。例如：H3對應(yīng)H2、H1(3=2+1)，故H3處的D1由P2、P1校驗H5對應(yīng)H4、H1(5=4+1)，故H5處的D2由P3、P1校驗H6對應(yīng)H4、H2(6=4+2)，故H6處的D3由P3、P2校驗H7對應(yīng)H4、H2、H1(7=4+2+1)，故D4由P3、P2、P1校驗H9對應(yīng)H8、H1(9=8+1)，故D5在由P4、P1檢驗注意：由于H1、H2、H4、H8、H16…本身是檢驗位，因此不再由其他檢驗位進行檢驗。海明碼編碼規(guī)則-2第二十五頁第二十六頁，共81頁。海明碼編碼規(guī)則-3(3)校驗位的取值H9D5H8P4H7D4H6D3H5D2H4P3H3D1H2P2H1P1P4√√P3√√√√P2√√√√P1√√√√√按行采用偶校驗，各校驗位計算公式如下： P4=D5 P3=D4⊕D3⊕D2 P2=D4⊕D3⊕D1 P1=D5⊕D4⊕D2⊕D1第二十六頁第二十七頁，共81頁。海明碼解碼在收到數(shù)據(jù)解碼時，按奇偶校驗碼解碼方式處理： S4=D5⊕P4 S3=D4⊕D3⊕D2⊕P3 S2=D4⊕D3⊕D1⊕P2 S1=D5⊕D4⊕D2⊕D1⊕P1若S4S3S2S1=0，說明傳送無錯,接收到的代碼無錯;若S4S3S2S1≠0,說明傳送有錯,此時S4S3S2S1代表的十進制數(shù)值就是出錯的位號,故將SS3S2S1稱為指誤字(Symptom)。第二十七頁第二十八頁，共81頁。海明碼舉例---一位出錯例：假設(shè)海明碼數(shù)據(jù)在傳送時第5位發(fā)生錯誤。H9H8H7H6H5H4H3H2H1D5P4D4

D3

D2

P3

D1

P2

P1發(fā)送海明碼00

0

1

0

1

0

1

0(如數(shù)字4,00100)接收的海明碼0

0

0

1

1

1

0

1

0

出錯則：S4=D5⊕P4=0 S3=D4⊕D3⊕D2⊕P3=0⊕1⊕1⊕1=1 S2=D4⊕D3⊕D1⊕P2=0⊕1⊕0⊕1=0 S1=D4⊕D2⊕D1⊕P1=0⊕1⊕0⊕0=1從而得到指誤字S4S3S2S1=0101，說明H5(數(shù)據(jù)位D2)出錯,將D2取反即可。第二十八頁第二十九頁，共81頁。海明碼舉例---兩位出錯例：假設(shè)海明碼數(shù)據(jù)在傳送時第5、6位同時發(fā)生錯誤。H9H8H7H6H5H4H3H2H1D5P4D4

D3

D2

P3

D1

P2

P1發(fā)送海明碼00

0

1

0

1

0

1

0(如數(shù)字4,00100)接收的海明碼0

0

0

0

1

1

0

1

0

出錯則：S4=D5⊕P4=0 S3=D4⊕D3⊕D2⊕P3=0⊕0⊕1⊕1=0 S2=D4⊕D3⊕D1⊕P2=0⊕0⊕0⊕1=1 S1=D4⊕D2⊕D1⊕P1=0⊕1⊕0⊕0=1從而得到指誤字S4S3S2S1=0011，說明H3(數(shù)據(jù)位D1)出錯，與事實不符。結(jié)論:海明碼能查出2位以上的錯誤，但不能定位和糾錯。第二十九頁第三十頁，共81頁。海明碼改進---糾一檢兩增加一個檢驗位，用于區(qū)分是一位錯還是兩位錯。仍以5位數(shù)據(jù)為例，此時檢驗碼需增加到5位，則P4P3P2P1編解碼同前面方案，而P5位于H10，海明碼格式如下：H10H9H8H7H6H5H4H3H2H1

P5D5P4D4

D3

D2

P3

D1

P2

P1且P5的編碼為：P5=H1⊕H2⊕…⊕H9P5的解碼為：S5=H1⊕H2⊕…⊕H9⊕H10(即P5)結(jié)論：當Si(i=1~5)全為0，表示接收無誤；當S5=1，S4S3S2S1=0000，表示P5出錯；當S5=1，S4S3S2S1≠0000，表示一位錯，其值為出錯位置；當S5=0，S4S3S2S1≠0000，表示兩位錯，錯誤位置不確定。第三十頁第三十一頁，共81頁。檢錯糾錯碼小結(jié)(1)K位碼有2K個編碼狀態(tài)，若全用于表示合法碼，則任何一位出錯，均會變成另一個合法碼，不具有檢錯能力。(2)從一個合法碼變成另一個合法碼，至少要改變幾位碼的值，稱為最小碼距(碼距)。(3)K+1位碼，只用其2K個狀態(tài)，可使碼距為2,如果一個合法碼中的一位錯了，就成為非法碼，通過檢查碼字的合法性，就得到檢錯能力，這就是奇偶校驗碼。第三十一頁第三十二頁，共81頁。檢錯糾錯能力(4)對k

位數(shù)據(jù)位，當給出r位校驗位時，要發(fā)現(xiàn)并改正一位錯，須滿足如下關(guān)系：

2r>=k+r+1；

要發(fā)現(xiàn)并改正一位錯，也能發(fā)現(xiàn)兩位錯,則應(yīng)：

2r-1>=k+r

,此時碼距為4。(5)若最小碼距為d(d>=2), 能發(fā)現(xiàn)d-1位錯，或改正(d-2)/2(取整)位錯, 要發(fā)現(xiàn)l位錯,并改正t位錯，應(yīng)滿足如下條件:

d>=

l+t+1(l>=t)

第三十二頁第三十三頁，共81頁。海明碼練習---教材P75：7對8位數(shù)據(jù)進行檢1糾1需4位校驗位，檢2糾1則需5位。H12D8H11D7H10D6H9D5H8P4H7D4H6D3H5D2H4P3H3D1H2P2H1P1P4√√√√√P3√√√√√P2√√√√√√P1√√√√√√數(shù)據(jù)01010111的5個校驗位取值如下：P1=D7⊕D5⊕D4⊕D2⊕D1=1⊕1⊕0⊕1⊕1=0P2=D7⊕D6⊕D4⊕D3⊕D1=1⊕0⊕0⊕1⊕1=1P3=D8⊕D4⊕D3⊕D2=0⊕0⊕1⊕1=0P4=D8⊕D7⊕D6⊕D5=0⊕1⊕0⊕1=0P5=∑Hi=0海明碼為：001010011011

0數(shù)據(jù)00000000，5個校驗位取值如下：P1=D7⊕D5⊕D4⊕D2⊕D1=0P2=D7⊕D6⊕D4⊕D3⊕D1=0P3=D8⊕D4⊕D3⊕D2=0P4=D8⊕D7⊕D6⊕D5=0P5=∑Hi=0海明碼為：00000000000數(shù)據(jù)01010111第三十三頁第三十四頁，共81頁。海明碼練習---教材P75：7若01010111的最低數(shù)據(jù)位由1變成0，即變成01010110，則： 原海明碼001010011011

0 變成0010100110

1

1

0譯碼過程：S1=D7⊕D5⊕D4⊕D2⊕D1⊕P1=1⊕1⊕0⊕1⊕0⊕0=1S2=D7⊕D6⊕D4⊕D3⊕D1⊕P2=1⊕0⊕0⊕1⊕0⊕1=1S3=D8⊕D4⊕D3⊕D2⊕P3=0⊕0⊕1⊕1⊕0=0S4=D8⊕D7⊕D6⊕D5⊕P4=0⊕1⊕0⊕1⊕0=0S5=∑Hi=1根據(jù)譯碼結(jié)果知S5=1，表示1位錯，錯誤位置在0011，即H3，故D1位錯。第三十四頁第三十五頁，共81頁。海明碼練習---教材P75：7若00000000的最低、最高數(shù)據(jù)位由0變成1，即變成10000001，則原海明碼000000000000

0 變成0

100000000

1

0

0譯碼過程：S1=D7⊕D5⊕D4⊕D2⊕D1⊕P1=0⊕0⊕0⊕0⊕1⊕0=1S2=D7⊕D6⊕D4⊕D3⊕D1⊕P2=0⊕0⊕0⊕0⊕1⊕0=1S3=D8⊕D4⊕D3⊕D2⊕P3=1S4=D8⊕D7⊕D6⊕D5⊕P4=1⊕0⊕0⊕0⊕0=1S5=∑Hi=0根據(jù)譯碼結(jié)果知S5=0，S4S3S2S1≠0000，故兩位錯，具體哪兩位不知。第三十五頁第三十六頁，共81頁。循環(huán)冗余校驗(CyclicRedundancyCheck,CRC)碼，簡稱CRC碼，是一種檢錯、糾錯能力很強的數(shù)據(jù)校驗碼，主要用于網(wǎng)絡(luò)、同步通信及磁表面存儲器等場合。CRC碼格式CRC碼的左邊為信息位，右邊為校驗位。若信息位為n位，校驗位為r位，則該校驗碼被稱為(n+r,r)循環(huán)碼。循環(huán)冗余校驗碼信息位校驗位n位r位循環(huán)冗余校驗碼的格式第三十六頁第三十七頁，共81頁。CRC編碼步驟如下：(1)將待編碼的n位有效信息位表示為一個n-1階多項式M(x)。(2)將M(x)左移r位，得到M(x).xr（r由預選的r+1階生成多項式G(x)決定）。(3)用預選的r+1階生成多項式G(x)對M(x).xr作模2除法。(4)把左移r位后的的有效信息位與余數(shù)作模2加法，形成長度為n+r的CRC碼。M(x).xr+R(x)＝Q(x).G(x)CRC編碼方法M(x)·xrG(x)＝Q(x)＋R(x)G(x)第三十七頁第三十八頁，共81頁。模2運算模2加減運算是指不考慮進/借位，即： 0±0＝0,0±1＝1,1±0＝1,1±1＝0， 實際是異或操作。模2除法的上商原則是當部分余數(shù)首位是1時，商取1，即使比除數(shù)小，反之商取0；然后按模2減求余數(shù)。當被除數(shù)除完時的余數(shù)就是校驗位（比除數(shù)少一位）。

第三十八頁第三十九頁，共81頁。CRC編碼舉例例：使用生成多項式為G(X)＝X3＋X＋1，把4位信息1100編成CRC碼。解：步驟1：由于G(X)為3次多項式，故r取3，將信息碼1100左移3位得11000000（相當于M(X)=X3+X2，M(X)·X3=X6+X5）步驟2：由于G(X)多項式系數(shù)對應(yīng)1011，計算模2除法：1100000/1011，得商為1110，余數(shù)為010（相當于計算M(X)·X3/G(X)=(X6+X5)/(X3+X+1)，得Q(X)=X3+X2+X1，R(X)=X）步驟3：將1100000與余數(shù)010進行模2加，即1100000+010=1100010，1100010即為所求的CRC碼（相當于計算M(X)·X3+R(X)）第三十九頁第四十頁，共81頁。CRC碼的糾錯原理由于M(X).Xr＝Q(X).G(X)+R(X)，根據(jù)模2加的規(guī)則M(X).Xr+R(X)=Q(X).G(X)+R(X)+R(X)＝Q(X).G(X)上式表明,合法的CRC碼應(yīng)當能被生成多項式整除。若CRC碼不能被生成多項式整除，說明出現(xiàn)差錯。當出現(xiàn)信息的傳送差錯時，CRC碼被生成多項式整除所得到的余數(shù)與出錯位之間有唯一的對應(yīng)關(guān)系,根據(jù)這一關(guān)系便可立即確定出錯位的位置。若某位出錯，則余數(shù)不為0，對此余數(shù)補0后繼續(xù)作模2除法,此后余數(shù)將按一定順序循環(huán)。對前例，形成010、100、011、110、111、101、001、010的循環(huán)，反復循環(huán)，這就是“循環(huán)碼”一詞的來源。第四十頁第四十一頁，共81頁。CRC生成多項式的選擇被用來生成CRC碼的多項式一般滿足下列要求：（1）任何一位出錯都應(yīng)使余數(shù)不為0。（2）不同位出錯應(yīng)使余數(shù)不同。（3）對余數(shù)繼續(xù)作模2除法，應(yīng)使余數(shù)循環(huán)。（4）必須是r次多項式，且Xr和X0的系數(shù)為1。生成多項式的選擇主要靠經(jīng)驗，但已有幾種多項式具有極高的檢錯率，被廣泛運用，分別是:CRC12＝X12＋X11＋X3＋X2＋X＋1CRC16＝X16＋X15＋X2＋1CRCCCITT＝X16＋X12＋X5＋1第四十一頁第四十二頁，共81頁。本章主要內(nèi)容3.1信息編碼、碼制轉(zhuǎn)換與檢錯糾錯碼3.2數(shù)據(jù)表示——常用的信息編碼3.3二進制數(shù)值數(shù)據(jù)的編碼與運算算法第四十二頁第四十三頁，共81頁。+0.1011+1100–

1100–0.1011帶符號的數(shù)符號數(shù)字化的數(shù)真值機器數(shù)

01011

11011

01100

11100小數(shù)點的位置數(shù)據(jù)的實際值被稱為真值。數(shù)據(jù)在機器內(nèi)要用規(guī)定的編碼來表示，這種表示被稱為機器數(shù)。機器數(shù)與真值第四十三頁第四十四頁，共81頁。定點小數(shù)原碼定義：[X]

原=實例：X=0.10110-0.101100.0000[X]原=0101101101100000010000

X1-X-1<X≤0

0≤X<1結(jié)論：原碼為符號位加數(shù)的絕對值，0正1負原碼零有兩個編碼，+0和-0編碼不同原碼難以用于加減運算，但乘除方便(原因?)第四十四頁第四十五頁，共81頁。定點原碼特點原碼加減法困難：要比較參與加減運算的兩個數(shù)的符號，還要比較它們的絕對值的大小，才能確定運算結(jié)果的數(shù)值和符號。原碼乘除法方便：兩個數(shù)的符號異或，數(shù)值相乘除即可。第四十五頁第四十六頁，共81頁。定點小數(shù)反碼定義：[X]反=實例：X=0.10110-0.101100.0000[X]反

=01011010100100000

11111X(2-2-n)+X-1<X≤0MOD(2-2-n)

0≤

X<1結(jié)論：負數(shù)反碼為符號位跟每位數(shù)值位取反，0正1負

反碼零有二個編碼，分+0和-0

反碼難以用于加減運算，有循環(huán)進位問題(舉例?)第四十六頁第四十七頁，共81頁。定點反碼循環(huán)進位問題如：X=+0.1011，Y=-0.0100，[X]反=01011，[Y]反=11011[X]反+[Y]反=01011+11011=1

00110有進位，結(jié)果再加1，即00110+1=

00111又如：X=+0.1011，Y=0.0100，[X]反=01011[Y]反=00100[X]反+[Y]反=01011+00100=01111沒有進位，01111就是最后結(jié)果。第四十七頁第四十八頁，共81頁。定點小數(shù)模2補碼定義：[X]補=實例：X=0.10110-0.101100.0000[X]補

=01011010101000000X2+X-1≤X≤0MOD2

0≤X<1結(jié)論：補碼最高位是符號位，0正1負

補碼表示為：2*符號位+數(shù)的真值

補碼零只有一個編碼，故能表示-1

補碼能很好地用于加減（乘除）運算（舉例？)第四十八頁第四十九頁，共81頁。補碼加減方便--示例X=+0.1010，Y=-0.0101，則[X]補=01010，[Y]補=11011

[X]補+[Y]補????

01010+11011

1001011丟掉(成進位C)00101是+0.0101的補碼，而X+Y的結(jié)果為+0.0101結(jié)論：[X+Y]補=[X]補+[Y]補第四十九頁第五十頁，共81頁。負數(shù)的[X]原、[X]反、[X]補之間的關(guān)系負數(shù)的[X]補與[X]反的關(guān)系根據(jù)定義：[X]補=2+X，[X]反

=(2–2-n)+X得：[X]補=[X]反

+2-n即：求負數(shù)補碼的簡便方法：[X]反加1；也即符號位取1，數(shù)值位取反，再加1。負數(shù)的[X]補與[X]原的相互轉(zhuǎn)換簡便方法均是符號位不變，數(shù)值位取反，再加1。第五十頁第五十一頁，共81頁。補碼與真值之間的關(guān)系假設(shè)：[X]補=X0.X1X2…Xn,則：當X>=0時，X0=0，[X]補=0.X1X2…Xn=X有：當X<0時，X0=1,[X]補=1.X1X2…Xn=2+X所以：X=1.X1X2…Xn–2=-1+0.X1X2…Xn=-X0+0.X1X2…Xn也有：結(jié)論：[X]補的負系數(shù)加數(shù)值部分，等于真值X例：[X]補=10110，則：X=-1+0.0110=-(1-0.0110)=-0.1010第五十一頁第五十二頁，共81頁。<Ⅰ>[y]補=0y1

y2

yn…y=0.y1y2

yn…y=0.y1

y2

yn…[y]補=1y1

y2

yn+2-n…<Ⅱ>[y]補=1y1

y2

yn…[y]原=1y1y2

yn+2-n…

y=（0.y1y2

yn

+2-n）…

y=0.y1y2

yn+2-n……[y]補=0y1

y2

yn+2-n每位取反，即得[y]補[y]補連同符號位在內(nèi)，末位加1每位取反，即得[y]補[y]補連同符號位在內(nèi)，末位加1已知[y]補如何簡單求[-y]補第五十二頁第五十三頁，共81頁。整數(shù)的編碼表示整數(shù)的原碼

反碼

補碼表示與小數(shù)的三種表示基本相同，小數(shù)點在最低數(shù)值位的右側(cè)N=NsNnNn-1……N2N1因此整數(shù)的取值范圍與整數(shù)位數(shù)有關(guān)。(定點小數(shù)的取值范圍與位數(shù)無關(guān)，精度與位數(shù)有關(guān))例如：整數(shù)六位編碼X=+01110[X]原=001110[X]補=001110X=-01110[X]原=101110[X]補=110010第五十三頁第五十四頁，共81頁。原反補碼表示小結(jié)正數(shù)的原碼、反碼、補碼表示均相同，符號位為0，數(shù)值位同真值。零的原碼和反碼均有2個編碼，補碼只有1個負數(shù)的原碼，反碼，補碼表示均不同，符號位為1，數(shù)值位：原碼為數(shù)的絕對值反碼為每一位均取反補碼為反碼再加1由[X]補求[-X]補：每一位取反后,再在最低位+1n由[X]補求X的真值：X=-X0+Xi*2-ii=1第五十四頁第五十五頁，共81頁。補碼加減法[X+Y]補=[X]補+[Y]補[X-Y]補=[X]補-[Y]補[X-Y]補=[X]補+[-Y]補說明減法可用加法實現(xiàn)如何求[-Y]補？對[Y]補逐位取反，末位再加1，得[-Y]補例：X=+0.1011y=-0.0101，求X+Y和X-Y。解：[X]補=01011,[Y]補=11011，[-Y]補=00101

01011+1101100110則[X+Y]補=00110故X+Y=0.0110

01011+00101

10000則[X-Y]補=10000故X-Y=-1.0000結(jié)果竟為負數(shù)？溢出了!0.1011-0.01010.01100.1011+0.01011.0000故X+Y=+0.0110X-Y=+1.0000人工算第五十五頁第五十六頁，共81頁。補碼加減法溢出判斷(1)正+正得負或負+負得正(2)數(shù)字位向符號位有進位，但符號位不產(chǎn)生向更高位的進位(3)雙符號位的值為01

或10前例：X=+0.1011，Y=-0.0101，采用雙符號位（模4補碼）[X]補=001011,[Y]補=111011 [-Y]補=000101

001011+000101

010000X-Y(溢出)

001011+1110111000110則[X+Y]補=000110故X+Y=0.0110[X]補+[Y]補[X]補+[-Y]補第五十六頁第五十七頁，共81頁。FX實現(xiàn)補碼加減運算的邏輯電路FsFALU目的寄存器源寄存器選通門二選通門選通門F1XYFYXF0101F/YFsOVRZC累加器減法：X

X-YＦ

ＸＦ

ＹＸ

ＦＦ

ＸＦ

/ＹＦ

1Ｘ

Ｆ加法：X

X+Y第五十七頁第五十八頁，共81頁。溢出判斷電路單符號位判斷：正加正得負或負加負得正表明溢出第五十八頁第五十九頁，共81頁。補碼表示中的符號位擴展由[X]補求[X/2]補：

原符號位不變，且符號位與數(shù)值位均右移一位，例如，[X]補=10010則[X/2]補=110010不同位數(shù)的整數(shù)補碼相加減時，位數(shù)少的補碼數(shù)的符號位向左擴展，

0101101011+1

+0

0111101111第五十九頁第六十頁，共81頁。補碼計算練習教材P75：10、11第六十頁第六十一頁，共81頁。第六十一頁第六十二頁，共81頁。原碼一位乘法

例如：X=0.1101Y=-0.10110.1101問題：*0.10111.加法器只有兩個數(shù)據(jù)輸入端11012.加法器與乘運算數(shù)據(jù)位數(shù)相同1101解決方案：00001.每次求出部分積，而不是一次總累加+1101變每次左移被乘數(shù)為右移部分積0.100011112.判乘數(shù)每一位的值用固定的一位線路

手工運算過程第六十二頁第六十三頁，共81頁。

例如：X=0.1101Y=-0.10110.1101*0.1011

1101

11010000+11010.10001111

手工運算過程原碼一位乘運算[X*Y]原=(XＳ⊕YＳ)(|X|*|X|)００００００累加器初值取零值+００１１０１００１１０１初值０加被乘數(shù)０００１１０１部分積右移+００１１０１０１００１１１前次部分積加被乘數(shù)００１００１１

１部分積右移+００００００００１００１１１前次部分積加０+００１１０１０００１００１１

１部分積右移０１０００１１１１前次部分積加０００１００１１１１１部分積右移兩數(shù)符號再異或求積的符號，最終：X*Y=-0.10001111第六十三頁第六十四頁，共81頁。實現(xiàn)原碼一位乘法的邏輯線路圖加法器部分積被乘數(shù)乘數(shù)

F最低位加運算移位線路每位1套

第i位第i位第i+1位第i-1位F/2→XF→XF*2→X移位電路把乘數(shù)放在一個移位寄存器中，該寄存起又用來接受加法器的移位輸出，則判乘數(shù)的某一位也更方便第六十四頁第六十五頁，共81頁。原碼一位乘法0000001011加法器部分積被乘數(shù)乘數(shù)

F最低位加運算移位線路每位1套0000000011011011001101001101000110110110110100110100111101101111110010000010010001100010011011001001001001000100101100010011111101111111110100010100010010001111低位積

第六十五頁第六十六頁，共81頁。已知：X=0.1001，Y=0.1101，計算X*Y。原碼一位乘法運算例2部分積乘數(shù)００００００１１０１＋X

００

１００１

００１００１

１１０１右移一位

０００１００

１１１０＋0

００００００

０００１００

１１１０右移一位

００００１０

０１１１

＋X

００１００１００１０１１

０１１１右移一位

０００１０１

１０１１＋X

００１００１

００１１１０

１０１１右移一位

０００１１１

０１０１

乘積高位乘積低位

XY=０.０１１１０１０１

第六十六頁第六十七頁，共81頁。除法運算在計算機內(nèi)實現(xiàn)除運算時，存在與乘法運算類似的幾個問題：加法器與寄存器的配合，被除數(shù)位數(shù)更長，商要一位一位地計算出來等。這可以用左移余數(shù)得到解決，且被除數(shù)的低位部分可以與最終的商合用同一個寄存器，余數(shù)與上商同時左移。第六十七頁第六十八頁，共81頁。原碼一位除運算 [Y/X]原=(XＳ⊕YＳ)(|Y|/|X|)原碼一位除是指用原碼表示的數(shù)相除，求出原碼表示的商。除操作的過程中，每次求出一位商。恢復余數(shù)除法：確定上商應(yīng)為１還是為０時，用被除數(shù)或中間余數(shù)減去除數(shù)，若求出一個為負的余數(shù)來，通常應(yīng)首先恢復其值為正，再求下一位商。不恢復余數(shù)除法：但計算機內(nèi)一般不用恢復余數(shù)除法，而是直接用求得的負余數(shù)求下一位商。

可以嗎？為什么？第六十八頁第六十九頁，共81頁。加減交替除法原理證明1.若第i-1次求商余數(shù)為+Ri-1，則商1，余數(shù)左移得2Ri-1。2.則第i次求商Ri=2Ri-1-Y3.則第i+1次求商Ri+1=2(Ri+Y)-Y

=2Ri+Y實質(zhì)是:對上次負差直接左移,本次用+Y求商即可。若Ri

≥0則重復步1若Ri<0商0先恢復余數(shù)：Ri+Y，再左移：2(Ri+Y)第六十九頁第七十頁，共81頁。00101111001111111011110000110100100101001011001100010100101011001111110111101000110100011100000開始情形-Y00000

<0,商000000左移1位+Y00001

>0,商100010左移1位-Y00011>0,商100110左移1位-Y00110<0,商001100左移1位+Y0110

1>0,商1被除數(shù)(余數(shù))商+[-Y]補)X=0.1011Y=0.1101X/Y=?[|Y|]補=001101[-|Y|]補=110011原碼一位除運算兩數(shù)符號相同，故：X/Y=0.1101+[Y]補)+[-Y]補)+[-Y]補)+[Y]補)第七十頁第七十一頁，共81頁。

F加法器A被除數(shù)(余數(shù))B除數(shù)10與或門與或門2F→AF→AB→F/B→F

1→FC乘商寄存器上商與或門2C→C計數(shù)器Cd實現(xiàn)原碼一位除法運算的原理邏輯圖第七十一頁第七十二頁，共81頁。教材P76：14、15乘除法練習第七十二頁第七十三頁，共81頁。第七十三頁第七十四頁，共81頁。補碼一位乘法1.補碼[X]補與真值X的轉(zhuǎn)換公式設(shè)[X]補=X0.X1X2…Xn，有2.補碼的右移[X]補擴展右移1位（即符號位右移且符號位取值不變），可得到[X/2]補。證明：即[X/2]補=X0X0X1X2…Xn第七十四頁第七十五頁，共81頁。3.補碼乘法規(guī)則設(shè)[X]補=X0X1X2…Xn，[Y]補=Y0Y1Y2…Yn，則證明略。將上式展開加以變換:[X*Y]補=[X]補*[-Y0+Y12-1+Y22-2+…+Yn2-n]=[X]補*[-Y0+(Y1-Y12-1)+(Y22-1-Y22-2)+…+(Yn2-(n-1)-Yn2-n)]=[X]補*[(Y1-Y0)+(Y2-Y1)2-1+…+(Yn-Yn-1)2-(n-1)+(0-Yn)2-n]

第七十五頁第七十六頁，共81頁。寫成遞推公式如下：[Z0]補=0[Z1]補=2-1{[Z0]補+(Yn+1-Yn)[X]補}(yn+1=0)[Z2]補=2-1{[Z1]補+(Yn-Yn-1)[X]補}┇[Zi]補=2-1{[Zi-1]補+(Yn-i+2-Yn-i+1)[X]補}┇[Zn]補=2-1{[Zn-1]補+(Y2-Y1)[X]補}[Zn+1]補=[Zn]補+(Y1-Y0)[X]補=[X*Y]補Booth算法初始，部分積為0