計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu)整理ppt

1、計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第六講宏偉 學(xué)時(shí)：64第3章數(shù)據(jù)表示、數(shù)據(jù)運(yùn)算算法和邏輯電路實(shí)現(xiàn)本章主要內(nèi)容信息編碼、碼制轉(zhuǎn)換與檢錯(cuò)糾錯(cuò)碼數(shù)據(jù)表示常用的信息編碼二進(jìn)制數(shù)值數(shù)據(jù)的編碼與運(yùn)算算法3數(shù)字化編碼二要素?cái)?shù)值 文字 符號 語音 圖形 圖像 等統(tǒng)稱數(shù)據(jù)，在計(jì)算機(jī)內(nèi)部，都必須用數(shù)字化編碼的形式被 存儲(chǔ) 加工 和 傳送 數(shù)字化編碼二要素:少量簡單的基本符號一定的組合規(guī)則用以表示大量復(fù)雜多樣的信息P624 基二碼（二進(jìn)制碼）只使用兩個(gè)基本點(diǎn)符號：符號個(gè)數(shù)最少，物理上容易實(shí)現(xiàn)與二值邏輯的 真假 兩個(gè)值對應(yīng)簡單用二進(jìn)制碼表示數(shù)值數(shù)據(jù)運(yùn)算規(guī)則簡單P635進(jìn)位記數(shù)法與進(jìn)制轉(zhuǎn)換進(jìn)位記數(shù)法N=i=m-1Di*ir-kN

2、 代表一個(gè)數(shù)值r 是這個(gè)數(shù)制的基(Radix)i表示這些符號排列的位號Di是位號為i的位上的一個(gè)符號ri是位號為i的位上的一個(gè) 1 代表的值irDi*是第i位的所代表的實(shí)際值表示m+k位的值求累加和P646十進(jìn)制轉(zhuǎn)二進(jìn)制整數(shù)部分除2取余 小數(shù)部分乘2取整2 1 1222521011010.625 * 210.25 * 200.5 * 21 0.0 除盡為止 求得位數(shù)滿足要求為止低高高低從二進(jìn)制數(shù)求其十進(jìn)制的值，逐位碼權(quán)累加求和P657二到八或十六進(jìn)制轉(zhuǎn)換二到八 從小數(shù)點(diǎn)向左右三位一分組（10 011 100 . 01)2 = ( 234 . 2 )8 010 二到十六 從小數(shù)點(diǎn)向左右四位一分組

3、（1001 1100 . 01)2 = ( 9C . 4 )16 0100 說明：整數(shù)部分不足位數(shù)對轉(zhuǎn)換無影響， 小數(shù)部分不足位數(shù)要補(bǔ)零湊足,否則出錯(cuò)。P678計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第七講主講教師：趙宏偉 學(xué)時(shí)：64二進(jìn)制數(shù)據(jù)算術(shù)運(yùn)算規(guī)則(1) 加法運(yùn)算規(guī)則 0+0=0 例如： 0101 0+1=1 +) 0001 1+0=1 0110 1+1=0 并產(chǎn)生進(jìn)位(2) 減法運(yùn)算規(guī)則 0-0=0 例如： 1011 0-1=1 并產(chǎn)生借位 -) 0101 1-0=1 0110 1-1=010二進(jìn)制數(shù)據(jù)算術(shù)運(yùn)算規(guī)則乘法運(yùn)算規(guī)則 例如： 1101 0X0=0 X) 0101 0X1=0 1101 1X0

4、=0 1101 1X1=1 1000001除法運(yùn)算規(guī)則 1101 例如： 1110101/1001 1001 1110101 1001 1011 1001 01001 1001 0 0000P6811二進(jìn)制數(shù)據(jù)邏輯運(yùn)算規(guī)則（5）邏輯或運(yùn)算規(guī)則 （7）邏輯非運(yùn)算規(guī)則 00=0 /0=1 01=1 /1=0 10=1 11=1（6）邏輯與運(yùn)算規(guī)則 （8）邏輯異或運(yùn)算規(guī)則 00=0 00=0 01=0 01=1 10=0 10=1 11=1 11=0 000012計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第八講主講教師：趙宏偉 學(xué)時(shí)：64檢錯(cuò)糾錯(cuò)碼 為了提高計(jì)算機(jī)的可靠性，除了采取選用更高可靠性的器件，更好的生產(chǎn)工藝等

5、措施之外，還可以從數(shù)據(jù)編碼上想一些辦法，即采用一點(diǎn)冗余的線路，在原有數(shù)據(jù)位之外再增加一到幾位校驗(yàn)位，使新得到的碼字帶上某種特性，之后則通過檢查該碼字是否仍保持有這一特性，來發(fā)現(xiàn)是否出現(xiàn)了錯(cuò)誤，甚至于定位錯(cuò)誤后，自動(dòng)改正這一錯(cuò)誤，這就是我們這里說的檢錯(cuò)糾錯(cuò)編碼技術(shù)。P7014非線性碼線性碼卷積碼分組碼非循環(huán)碼循環(huán)碼隨機(jī) 錯(cuò)誤 突發(fā) 錯(cuò)誤糾錯(cuò)碼校驗(yàn)位與信息位 的形成關(guān)系信息位與校驗(yàn)位 的約束條件碼字本身的 結(jié)構(gòu)特點(diǎn)信息位與校驗(yàn)位排列位置關(guān)系系統(tǒng)碼非系統(tǒng)碼糾錯(cuò)碼分類P7015幾種常用的檢錯(cuò)糾錯(cuò)碼我們只介紹三種常用的檢錯(cuò)糾錯(cuò)碼：奇偶檢錯(cuò)碼， 用于并行數(shù)據(jù)傳送中海明檢錯(cuò)與糾錯(cuò)碼，用于并行數(shù)據(jù)傳送中循環(huán)冗

6、余碼， 用于串行數(shù)據(jù)傳送中編碼過程譯碼過程傳送原始數(shù)據(jù)碼 字結(jié)果數(shù)據(jù)形成校驗(yàn)位的值，加進(jìn)特征檢查接送的碼字，發(fā)現(xiàn) / 改正錯(cuò)誤16奇偶校驗(yàn)碼用于并行碼檢錯(cuò)原理：在 k 位數(shù)據(jù)碼之外增加 1 位校驗(yàn)位，使 K+1 位碼字中取值為 1 的位數(shù)總保持為 偶數(shù)（偶校驗(yàn)）或 奇數(shù)（奇校驗(yàn)）。例如：0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 原有數(shù)字位 兩個(gè)新的碼字 偶校驗(yàn)奇校驗(yàn)校驗(yàn)位P7117奇偶校驗(yàn)碼的實(shí)現(xiàn)電路+ 奇較驗(yàn) 偶校驗(yàn) 出錯(cuò)指示+同左側(cè)電路編碼電路譯碼電路P (校驗(yàn)位)八位數(shù)據(jù)位D7 D6 D5 D4 D3 D2 D1 D0

7、p18海明校驗(yàn)碼用于多位并行數(shù)據(jù)檢錯(cuò)糾錯(cuò)處理實(shí)現(xiàn)：為 k 個(gè)數(shù)據(jù)位設(shè)立 r 個(gè)校驗(yàn)位，使 k+r 位的碼字同時(shí)具有這樣兩個(gè)特性：能發(fā)現(xiàn)并改正 k+r 位中任何一位出錯(cuò)，能 發(fā) 現(xiàn) k+r 位中任何二位同時(shí)出錯(cuò)，但已無法改正。19海明碼的編碼方法合理地用 k 位數(shù)據(jù)位形成 r 個(gè)校驗(yàn)位的值，即保證用 k 個(gè)數(shù)據(jù)位中不同的數(shù)據(jù)位組合來形成每個(gè)校驗(yàn)位的值，使任何一個(gè)數(shù)據(jù)位出錯(cuò)時(shí)，將影響 r 個(gè)校驗(yàn)位中不同的校驗(yàn)位組合起變化。換言之，通過檢查是哪種校驗(yàn)位組合起了變化，就能確定是哪個(gè)數(shù)據(jù)位錯(cuò)，對該位求反則實(shí)現(xiàn)糾錯(cuò)。有時(shí)兩位錯(cuò)與某種情況的一位錯(cuò)對校驗(yàn)位組合的影響相同，必須加以區(qū)分與解決。20P1 = D2

8、 + D1P2 = D3 + D1P3 = D3 + D2海明碼的實(shí)現(xiàn)方案 例如： k =3, r =4D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 P4 = P3 + P2 + P1 + D3 + D2 + D1S1 = P1 + D2 + D1S2 = P2 + D3 + D1S3 = P3 + D3 + D2S4 = P4 + P3 + P2 + P1 + D3 + D2 + D1+ ：異或編碼方案譯碼方案P7221檢錯(cuò)糾錯(cuò)碼小結(jié)(1) K位碼有2K 個(gè)編碼狀態(tài)，全用于表示合法碼，

9、則任何一位出錯(cuò), 均會(huì)變成另一個(gè)合法碼，不具有檢錯(cuò)能力。(2) 從一個(gè)合法碼變成另一個(gè)合法碼，只少要改變幾位碼的值，稱為最小碼距(碼距)。(3) K+1 位碼，只用其 2K 個(gè)狀態(tài)，可使碼距 為 2 , 如果一個(gè)合法碼中的一位錯(cuò)了，就成為非法碼，通過檢查碼字的合法性，就得到檢錯(cuò)能力，這就是奇偶校驗(yàn)碼。22檢錯(cuò)糾錯(cuò)能力(4) 對 k 位數(shù)據(jù)位，當(dāng)給出 r 位校驗(yàn)位時(shí)，要發(fā)現(xiàn)并改正一位錯(cuò)， 須滿足如下關(guān)系： 2r = k + r +1 ； 要發(fā)現(xiàn)并改正一位錯(cuò)，也能發(fā)現(xiàn)兩位錯(cuò),則應(yīng)： 2r-1 = k + r , 此時(shí)碼距為 4。 (5) 若最小碼距為 d (d=2), 能發(fā)現(xiàn) d-1 位錯(cuò)，或改正

10、 (d-2)/2 (取整) 位錯(cuò),要發(fā)現(xiàn) l 位錯(cuò),并改正 t 位錯(cuò)，應(yīng)滿足如下條件: d = l + t + 1 ( l = t )23計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第九講主講教師：趙宏偉 學(xué)時(shí)：64本章主要內(nèi)容信息編碼、碼制轉(zhuǎn)換與檢錯(cuò)糾錯(cuò)碼數(shù)據(jù)表示常用的信息編碼二進(jìn)制數(shù)值數(shù)據(jù)的編碼與運(yùn)算算法25基二碼應(yīng)用實(shí)例：數(shù)據(jù)表示邏輯型數(shù)據(jù)字符型數(shù)據(jù)ASCII 碼 EBCDIC 碼字符串 漢字檢錯(cuò)糾錯(cuò)碼奇偶校驗(yàn)海明校驗(yàn) 循環(huán)冗余校驗(yàn)數(shù)值型數(shù)據(jù)定點(diǎn)小數(shù) 整數(shù) 浮點(diǎn)數(shù) 二十進(jìn)制數(shù)（BCD碼） 26邏輯型數(shù)據(jù)邏輯型數(shù)據(jù)只有兩個(gè)值：真 和 假，正好可以用二進(jìn)制碼的兩個(gè)符號分別表示，例如 1 表示 真 則 0 表示 假

11、不必使用另外的編碼規(guī)則。對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的 與 或 非等基本邏輯運(yùn)算。其規(guī)則如下：27邏輯型數(shù)據(jù)基本運(yùn)算規(guī)則 X Y X與Y X或Y X的非 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 28字符型數(shù)據(jù)的表示 字符作為人機(jī)聯(lián)系的媒介，是最重要的數(shù)據(jù)類型之一，當(dāng)前的西文字符集由 128 個(gè)符號組成，通常用 8 位二進(jìn)制編碼,即用一個(gè)字節(jié)來表示每一個(gè)符號，當(dāng)前通用的兩個(gè)標(biāo)準(zhǔn)字符集是：ASCII 碼： 即 American Standard Code for Information InterchangeEBCDIC碼：即 Extended Binary C

12、oded Decimal Interchage Code ASCII碼字符集具體編碼如下表所示： 29ASCII字符編碼集 b6 b5 b4 000 001 010 011 100 101 110 111 b3 b2 b1 b0 0000 NUL DLE SP 0 P , p 0001 SOH DC1 ! 1 A Q a q 0010 STX DC2 “ 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ET

13、B 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K k 1100 FF FS , N n 1111 SI US / ? O _ o P7530字符串的表示與存儲(chǔ)字符串是指連續(xù)的一串字符，它們占據(jù)主存中連續(xù)的多個(gè)字節(jié)，每個(gè)字節(jié)存放一個(gè)字符，對一個(gè)主存字的多個(gè)字節(jié)，有按從低位到高位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。表示字符串?dāng)?shù)據(jù)要給出串存放的主存起始地址和串的長度。例如：IF AB THEN READ(C)就可以有如下不同的存放方式：

14、 I F A A F I B T T B 假定每個(gè)字 H E N N E H 由 4 個(gè)字節(jié) R E A D D A E R 組成 ( C ) ) C (31漢字的表示 通常用兩個(gè)字節(jié)表示一個(gè)漢字 為了與西文字符編碼相區(qū)別（西文的ASCII碼的最高一位編碼值為0），表示一個(gè)漢字時(shí)，把兩個(gè)字節(jié)的最高一位的編碼值設(shè)定為 1，則該編碼集的最多編碼數(shù)量為 128 X 128。 這種編碼方案與西文傳送中的把ASCII碼的最高一位用作奇偶校驗(yàn)位有矛盾。32數(shù)值數(shù)據(jù)在計(jì)算機(jī)內(nèi)的格式定點(diǎn)小數(shù): N = N N N .Ns-1-n-2整 數(shù) : N = N N N . N N01snn-1浮點(diǎn)數(shù): N = M

15、E E .E E M M .M ssm-110-1-2-n符號位 階碼位 尾數(shù)數(shù)碼位 總位數(shù) 短浮點(diǎn)數(shù): 1 8 23 32長浮點(diǎn)數(shù): 1 11 52 64 臨時(shí)浮點(diǎn)數(shù): 1 15 64 80IEEE 標(biāo)準(zhǔn)： 階碼用移碼，尾數(shù)用原碼 基為 2P7633二 十進(jìn)制編碼（BCD編碼）用四位二進(jìn)制表示一位十進(jìn)制， 16個(gè)編碼狀態(tài)選用其中的10個(gè)編碼有多種方案，例如：8421碼，余 3 碼，循環(huán)碼又可區(qū)分為：有權(quán)碼：每位上的 1 代表確定的值無權(quán)碼：無法確定每位上的 1 代表的值340 0000 0011 0000 00001 0001 0100 0001 01112 0010 0101 0011 0

16、1103 0011 0110 0010 01014 0100 0111 0110 01005 0101 1000 1110 10116 0110 1001 1010 10107 0111 1010 1000 10018 1000 1011 1100 10009 1001 1100 0100 1111有權(quán)碼 無權(quán)碼8421余3碼循環(huán)碼84-2-1P7935計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第十講主講教師：趙宏偉 學(xué)時(shí)：64本章主要內(nèi)容信息編碼、碼制轉(zhuǎn)換與檢錯(cuò)糾錯(cuò)碼數(shù)據(jù)表示常用的信息編碼二進(jìn)制數(shù)值數(shù)據(jù)的編碼與運(yùn)算算法37定點(diǎn)小數(shù)表示: Ns N1 N2 Nn X = X = X =原 X 1 - X -1 X

17、 0反 X(2 - 2 )+ X-n0 X 1-1 X 0補(bǔ) X 2 + XMod ( 2 - 2 )0 X 1-1 X 0Mod 20 X 1-n（純小數(shù)）原碼，反碼，補(bǔ)碼的定義P8238定點(diǎn)小數(shù)表示: Ns N1 N2 Nn 原 碼定義： X 原 =實(shí)例： X1 = 0.10110 -0.10110 0.0000 X 原 = 010110 110110 00000 10000 結(jié)論：原碼為符號位加數(shù)的絕對值，0正 1負(fù) 原碼零有兩個(gè)編碼，+0 和 -0編碼不同 原碼難以用于加減運(yùn)算，但乘除方便 X 1 - X -1 X 00 X 1P8339定點(diǎn)小數(shù)表示: Ns N1 N2 Nn模 2 補(bǔ)

18、碼 定義： X 補(bǔ) =實(shí)例： X1 = 0.10110 -0.10110 0.0000 X 補(bǔ) = 010110 101010 00000結(jié)論：補(bǔ)碼最高一位是符號位，0 正 1 負(fù) 補(bǔ)碼表示為：2*符號位 + 數(shù)的真值 補(bǔ)碼零只有一個(gè)編碼，故能表示 -1 補(bǔ)碼能很好地用于加減（乘除）運(yùn)算 X 2 + X -1 X 0 MOD 20 X 1P8340定點(diǎn)小數(shù)表示: Ns N1 N2 Nn 反 碼定義： X 反 =實(shí)例： X1 = 0.10110 -0.10110 0.0000 X 反 = 010110 101001 00000 11111 結(jié)論：反碼負(fù)數(shù)為符號位跟每位的反, 0 正 1 負(fù) 反碼零有二個(gè)編碼，分+0 和 -0 反碼難以用于加減運(yùn)算，有循環(huán)進(jìn)位問題 X (2-2-n) + X -1 X 0 MOD (2-2-n)0 X 0 則i若 R 0 商 0i恢復(fù)余數(shù)為正且左移得 2(R + Y )ii+1ii62 F 加法器A 被除數(shù)(余數(shù))B 除數(shù) 1 0與或門與或門2FAFABF/BF 1FC 乘商寄存器