計(jì)算機(jī)組成原理課件（第三版）第二章 計(jì)算機(jī)中的數(shù)據(jù)表示

計(jì)算機(jī)組成原理 主編： 石磊 教授 鄭州大學(xué)信息工程學(xué)院計(jì)算機(jī)系 2 第一章 概述 第二章 計(jì)算機(jī)中的數(shù)據(jù)表示 第三章 運(yùn)算方法和運(yùn)算器 第四章 存儲器及存儲系統(tǒng) 第五章 指令系統(tǒng) 第六章 中央處理器 第七章 總線系統(tǒng) 第八章 輸入輸出系統(tǒng) 第九章 計(jì)算機(jī)外部設(shè)備 第十章 計(jì)算機(jī)系統(tǒng)及發(fā)展 目錄 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 3頁 第 2章 計(jì)算機(jī)中的數(shù)據(jù)表示 計(jì)算機(jī)組成原理 清華大學(xué)出版社教學(xué)目標(biāo) 教學(xué)重點(diǎn) 教學(xué)過程 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 4頁 教學(xué)目標(biāo) 數(shù)據(jù)在計(jì)算機(jī)中的表示方法及編碼形式 掌握進(jìn)位計(jì)數(shù)制和數(shù)制之間的轉(zhuǎn)換 掌握數(shù)與字符的表示方法及校驗(yàn)方法 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 5頁 教學(xué)重點(diǎn) 進(jìn)位計(jì)數(shù)制和數(shù)制之間的轉(zhuǎn)換 定點(diǎn)數(shù)和浮點(diǎn)數(shù) 帶符號數(shù)的表示方法 字符編碼 數(shù)據(jù)校驗(yàn)碼 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 6頁 教學(xué)過程 據(jù)、信息和媒體 位計(jì)數(shù)制 點(diǎn)數(shù)和浮點(diǎn)數(shù) 符號數(shù)的表示方法 進(jìn)制數(shù)據(jù)表示 符編碼 據(jù)校驗(yàn)碼 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 7頁 據(jù)、信息和媒體 (1/4) 數(shù)據(jù)：是對事實(shí)、概念或指令的一種特殊表達(dá)形式，可以用人工方式或自動化裝置進(jìn)行通信、翻譯轉(zhuǎn)換或加工處理。 數(shù)值型數(shù)據(jù)：具有特定值的一類數(shù)據(jù)，可用來表示數(shù)量的多少，可比較其大小。 非數(shù)值型數(shù)據(jù)：包括字符數(shù)據(jù)、邏輯數(shù)據(jù)、圖畫、聲音和活動圖像數(shù)據(jù)等。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 8頁 據(jù)、信息和媒體 (2/4) 信息：對人有用的數(shù)據(jù)，這些數(shù)據(jù)可能影響到人們的行為和決策。 信息處理：通過數(shù)據(jù)的采集和輸入，有效地把數(shù)據(jù)組織到計(jì)算機(jī)中，由計(jì)算機(jī)系統(tǒng)對數(shù)據(jù)進(jìn)行相應(yīng)的處理加工（如：存儲、建庫、轉(zhuǎn)換、合并、分類、計(jì)算、統(tǒng)計(jì)、匯總、傳送等操作），最后向人們提供有用的信息的全過程。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 9頁 據(jù)、信息和媒體 (3/4) 媒體：承載信息的載體。與計(jì)算機(jī)信息處理有關(guān)的媒體： 感覺媒體：能使人聽覺、視覺、嗅覺、味覺和觸覺器官直接產(chǎn)生感覺的一類媒體，如聲音、文字、圖畫、氣味等，它們是人類使用信息的有效形式。 表示媒體：為了使計(jì)算機(jī)有效地加工、處理、傳輸感覺媒體而在計(jì)算機(jī)內(nèi)部采用的特殊表示形式，即聲、文、圖、活動圖像的二進(jìn)制編碼表示。 存儲媒體：用于存放表示媒體以便計(jì)算機(jī)隨時(shí)加工處理的物理實(shí)體，如磁盤、光盤、半導(dǎo)體存儲器等。 表現(xiàn)媒體：用于把感覺媒體轉(zhuǎn)換成表示媒體進(jìn)而轉(zhuǎn)換為感覺媒體的物理設(shè)備，如計(jì)算機(jī)的輸入輸出設(shè)備。 傳輸媒體：用來將表示媒體從一臺計(jì)算機(jī)傳遞到另一臺計(jì)算機(jī)的通信載體，如同軸電纜、光纖、電話線等。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 10頁 據(jù)、信息和媒體 (4/4) 數(shù)字化編碼：用少量最簡單的基本符號，對大量復(fù)雜多樣的信息進(jìn)行一定規(guī)律的組合。 一切信息編碼的兩大要素 基本符號的種類 組合規(guī)則 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 11頁 計(jì)算機(jī)內(nèi)部采用的二進(jìn)制表示方式的原因 二進(jìn)制只有兩個(gè)數(shù)碼“ 0”和“ 1”，易于用物理器件表示。這些物理狀態(tài)都是不同的質(zhì)的變化，形象鮮明、易于區(qū)別，并且數(shù)的存儲、傳送和處理可靠性高。 運(yùn)算規(guī)則簡單，操作實(shí)現(xiàn)容易。 二進(jìn)制加、減、乘、除運(yùn)算，可以歸結(jié)為加、減、移位三種操作。 理論和實(shí)踐證明，采用 R= e =儲設(shè)備最省，取 3比取 2更節(jié)省設(shè)備，但二進(jìn)制比三進(jìn)制易于表示。 二進(jìn)制中的“ 1”和“ 0”與邏輯命題中的“真”、“假”相對應(yīng)，為計(jì)算機(jī)實(shí)現(xiàn)邏輯運(yùn)算和程序中的邏輯判斷創(chuàng)造了良好條件。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 12頁 位計(jì)數(shù)制 位基數(shù)和位的權(quán)數(shù) 進(jìn)制數(shù)制 進(jìn)制數(shù)制 六進(jìn)制數(shù)制 制之間的相互轉(zhuǎn)換 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 13頁 位基數(shù)和位的權(quán)數(shù) 基數(shù)：計(jì)數(shù)制中用到的數(shù)碼的個(gè)數(shù)，用 位權(quán)：以基數(shù)為底的指數(shù)，指數(shù)的冪是數(shù)位的序號。 對一個(gè)數(shù) S，其基數(shù)為 R，則： 1 ) )( 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 14頁 計(jì)算機(jī)常用各種進(jìn)制數(shù)的表示 進(jìn)位制 二進(jìn)制 八進(jìn)制 十進(jìn)制 十六進(jìn)制 規(guī)則 逢二進(jìn)一 逢八進(jìn)一 逢十進(jìn)一 逢十六進(jìn)一 基數(shù) R=2 R=8 R=10 R=16 基本符號 0,1 0,1,2,7 0,1,2,9 0,1,.,9,A,.,F 權(quán) 2i 8i 10i 16i 形式表示 B O D H 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 15頁 制之間的相互轉(zhuǎn)換 二、八、十六進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù) 十進(jìn)制數(shù)轉(zhuǎn)換為二、八、十六進(jìn)制數(shù) 十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制 十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制、十六進(jìn)制數(shù) 二進(jìn)制數(shù)和八進(jìn)制數(shù)、十六進(jìn)制數(shù)的轉(zhuǎn)換 二進(jìn)制數(shù)轉(zhuǎn)換為八、十六進(jìn)制數(shù) 八、十六進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù) 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 16頁 二、八、十六進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù) （ 1/2） 例 2將 (轉(zhuǎn)換為十進(jìn)制數(shù) 解： (2 =1 24+1 23+0 22+1 21+1 20+1 2 2(0 1 ) )( 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 17頁 二、八、十六進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù) （ 2/2） 例 2將 (轉(zhuǎn)換為十進(jìn)制數(shù) 解： ( =7 82+3 81+2 80+6 8(0 例 2將 (6轉(zhuǎn)換為十進(jìn)制數(shù) 解： (6 =10 162+5 161+12 160+11 16 16(0 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 18頁 十進(jìn)制轉(zhuǎn)換為二進(jìn)制數(shù) （ 1/3） 任一十進(jìn)制數(shù) N， N=將這兩部分分開轉(zhuǎn)換 整數(shù)部分的轉(zhuǎn)換：采用“除 2求余法”，轉(zhuǎn)換方法為：連續(xù)用 2除，求得余數(shù)（ 1或 0）分別為 ，直到商為 0，所有余數(shù)排列 2為所轉(zhuǎn)換的二進(jìn)制整數(shù)部分。 小數(shù)部分的轉(zhuǎn)換：采用“乘 2取整法”。轉(zhuǎn)換方法為：連續(xù)用 2乘，依次求得各整數(shù)位（ 0或 1） 、 到乘積的小數(shù)部分為 0。在小數(shù)轉(zhuǎn)換過程中，出現(xiàn) 時(shí)，可按精度要求確定二進(jìn)制小數(shù)的位數(shù)。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 19頁 十進(jìn)制轉(zhuǎn)換為二進(jìn)制數(shù) （ 2/3） 例 2求 (43)10的二進(jìn)制表示 解： 除以 2 商 余數(shù) 3/2 21 21/2 10 10/2 5 5/2 2 2/2 1 1/2 0 (43)10=(101011)2 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 20頁 十進(jìn)制轉(zhuǎn)換為二進(jìn)制數(shù) （ 3/3） 例 2求 (0的二進(jìn)制值 解： 乘以 2 小數(shù) 數(shù) 2 2 2 2 (0=( 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 21頁 十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)、十六進(jìn)制數(shù) 將十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)、十六進(jìn)制數(shù)時(shí)，使用的方法與十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的方法基本相同，只是求整數(shù)部分時(shí)是用商除以 8或 16，取其余數(shù)；小數(shù)部分改用乘以 8或 16，取其整數(shù)即可。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 22頁 二進(jìn)制數(shù)與八進(jìn)制、十六進(jìn)制數(shù)間的轉(zhuǎn)換 二進(jìn)制轉(zhuǎn)化成八 (十六 )進(jìn)制 整數(shù)部分：從右向左按三 (四 )位分組，不足補(bǔ)零 小數(shù)部分：從左向右按三 (四 )位分組，不足補(bǔ)零 例 2001 011 010 11 100) 2= ( 8 1 3 2 6 5 3 4 例 20101 010) 2= (16 5 D 5 A 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 23頁 八進(jìn)制、十六進(jìn)制數(shù)與二進(jìn)制數(shù)間的轉(zhuǎn)換 八 (十六 )進(jìn)制轉(zhuǎn)化成二進(jìn)制 一位八進(jìn)制數(shù)對應(yīng)三位二進(jìn)制數(shù) 一位十六進(jìn)制數(shù)對應(yīng)四位二進(jìn)制數(shù) 例 2= (010 100 11)2 例 216= (1111 0101 1010 011) 2 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 24頁 點(diǎn)數(shù)和浮點(diǎn)數(shù) 數(shù)據(jù)的表示 定點(diǎn)表示法 浮點(diǎn)表示法 任何一個(gè)二進(jìn)制數(shù) N=2ES 其中 為數(shù) 2為階碼的基數(shù)， 為數(shù) 數(shù) 的全部有效數(shù)據(jù)，階碼示數(shù)據(jù)的大小范圍。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 25頁 點(diǎn)數(shù)表示法 階碼 若 E=0，小數(shù)點(diǎn)固定在最高位之前，則該數(shù)是一個(gè)純小數(shù)或定點(diǎn)小數(shù)。 例如 N=20 若 E=n (，則把小數(shù)點(diǎn)定在尾數(shù)最末位之后，表示一個(gè)純整數(shù) (定點(diǎn)整數(shù) )。 例如 N=27 1011010 2016年 3月 14日 26 定點(diǎn)數(shù)的表示方法 定點(diǎn)表示 ： 約定機(jī)器中所有數(shù)據(jù)的小數(shù)點(diǎn)位置是固定不變的。通常將數(shù)據(jù)表示成 純小數(shù) 或 純整數(shù) 定點(diǎn)數(shù) x 定點(diǎn)機(jī)中表示如下 (0代表正號， 1代表負(fù)號 ) 定點(diǎn)整數(shù)的小數(shù)點(diǎn)位置 定點(diǎn)小數(shù)的小數(shù)點(diǎn)位置 定點(diǎn)數(shù)例 例： X=+1010110. 純整數(shù)： X = 01010110. 正數(shù)，符號位取 0 Y= - 1101001. 純整數(shù)： Y = 11101001. （原碼） 負(fù)數(shù)，符號位取 1 X=+=號位取 0 純小數(shù)： X = 號位取 1 純小數(shù)： X = 原碼） 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 28頁 點(diǎn)數(shù)的表示 浮點(diǎn)數(shù)的格式 階碼位數(shù) 2n 即表示階碼的值應(yīng)保證實(shí)際的小數(shù)點(diǎn)可以在整個(gè)尾數(shù)的位格中移動。 浮點(diǎn)數(shù)的表示形式 階碼 階符 尾數(shù) 尾符 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 29頁 階碼和尾數(shù) 用定點(diǎn)小數(shù)表示 ，給出有效數(shù)字的位數(shù)決定了浮點(diǎn)數(shù)的表示精度 表達(dá)指數(shù)部分 用整數(shù)形式表示 ， 指明小數(shù)點(diǎn)在數(shù)據(jù)中的位置決定浮點(diǎn)數(shù)的表示范圍 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 30頁 點(diǎn)數(shù)的表示 規(guī)格化浮點(diǎn)數(shù) 所謂浮點(diǎn)數(shù)的規(guī)格化，就是通過移動尾數(shù)，使尾數(shù) 。即 |S|X0 負(fù)整數(shù) 0X 整數(shù) X補(bǔ) = 2n+1X S + X， 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 40頁 性質(zhì) 整數(shù)的補(bǔ)碼與真值之間的關(guān)系 補(bǔ)碼與真值的關(guān)系 設(shè) X補(bǔ) = 1X補(bǔ) = 2n+1X S + X，可以證明： X = X補(bǔ) - 2n+1X S = s + 1 補(bǔ)碼的一項(xiàng)算術(shù)運(yùn)算特性 X/2補(bǔ) 是把 X補(bǔ) 中各位連同符號位一起都右移一位，符號位保持不變。 器數(shù)的補(bǔ)碼表示 （ 4/8） ） X 0，擴(kuò)展后高 8位全為 0，低 8 位包括符號位仍為原來的數(shù)碼位。 若 2n 即無論 律加上 2n，稱 2 移碼與補(bǔ)碼的關(guān)系：真值是正數(shù)時(shí)，移碼是補(bǔ)碼的最高位加 1；真值是負(fù)數(shù)時(shí)，移碼是補(bǔ)碼的最高位減 1。即 若 X補(bǔ) = 1 則 X移 =1 例 2=1001， X補(bǔ) =01001 ，可求得 X移 =11001 X=X補(bǔ) =10111 ，可求得 X移 =00111 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 49頁 器數(shù)的移 (增 )碼表示法 （ 2/2） 性質(zhì)： (1) 0的移碼唯一。 整數(shù) 0 +0移 = 2n + 000 = 1000 = 2n - 000 = 1000 (2) 機(jī)器 0的形式為 000 ，它表示的真值是 X移 所能表示的最小的數(shù)。 (3) 移碼的最高位是符號位，但表示的意義與原碼和補(bǔ)碼的意義相反。符號為 0時(shí)，表示負(fù)數(shù)；符號為 1，表示正數(shù)。 (4) 移碼一般只進(jìn)行加減運(yùn)算，運(yùn)算后需要對結(jié)果進(jìn)行修正，修正量為 2n，即要對結(jié)果的符號位取反后，才能得到移碼形式的結(jié)果。 (5)通過比較兩個(gè)移碼的大小， 可得知其對應(yīng)的真值大小。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 50頁 種編碼的比較 相同點(diǎn)： 1、 三種編碼（原碼、反碼、補(bǔ)碼）的最高位都是符號位。 2、 當(dāng)真值為正時(shí)，三種編碼的符號位都用 0表示，數(shù)值部分與真值相同。 即它們的表示方法是相同的。 3、 當(dāng)真值為負(fù)時(shí)，三種編碼的符號位都用 1表示，但數(shù)值部分的表示各不相同，數(shù)值部分存在這樣的關(guān)系：補(bǔ)碼是原碼的“求反加 1”(整數(shù) )，或者“求反末位加 1”(小數(shù) )；反碼是原碼的“每位求反”。 4、 它們所能表示的數(shù)據(jù)范圍基本一樣， n 1111 S / ? O _ o 4計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 66頁 展 8位二進(jìn)制編碼，可以表示 256個(gè)編碼狀態(tài)，但只選用其中一部分。 主要用在 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 67頁 字的表示 特點(diǎn)： （ 1）漢字是一種象形文字，據(jù)統(tǒng)計(jì)，從甲骨文至今約有六萬左右的漢字。目前常見的漢字有約七千個(gè)。 （ 2）漢字字形結(jié)構(gòu)復(fù)雜，筆劃繁多。 （ 3）漢字同音字多，多音字多。 涉及多種編碼： 輸入碼 國標(biāo)碼 字形碼 機(jī)內(nèi)碼 地址碼 漢字輸出 漢字輸入 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 68頁 漢字的輸入編碼 數(shù)字編碼 國標(biāo) 區(qū)位碼 ，用數(shù)字串代表一個(gè)漢字輸入 字音編碼 以漢字拼音為基礎(chǔ)的輸入方法 字形編碼 用漢字的形狀（筆劃）來進(jìn)行的編碼 例如 五筆字形 混合編碼 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 69頁 漢字交換碼 漢字交換碼是不同的漢字處理系統(tǒng)之間交換信息用的編碼 漢字也是一種字符 1981年我國制定了 信息交換用漢字編碼字符集基本集 國家標(biāo)準(zhǔn)（簡稱 國標(biāo)碼 ）。每個(gè)漢字的二進(jìn)制編碼用兩個(gè)字節(jié)表示。共收錄一級漢字 3755個(gè)，二級漢字 3008個(gè)，各種符號 682個(gè)，共計(jì) 7445個(gè) 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 70頁 漢字內(nèi)碼 漢字內(nèi)碼 是用于漢字信息的存儲、檢索等操作的 機(jī)內(nèi)代碼 ，一般采用兩個(gè)字節(jié)表示 漢字內(nèi)碼有多種方案，常以國標(biāo)碼為基礎(chǔ)的編碼 例如，將國標(biāo)碼兩字節(jié)的最高位置 1后形成 漢字“啊”的國標(biāo)碼 3021H (0011 0000 0010 0001) 對應(yīng)的漢字內(nèi)碼 1011 0000 1010 0001) 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 71頁 字模碼 漢字的字模碼為： 16位 16位 =32字節(jié) 漢字字模點(diǎn)陣及編碼 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 72頁 漢字的表示方法 漢字的輸入編碼 、 交換碼 、 漢字內(nèi)碼 、 字模碼是計(jì)算機(jī)中用于輸入 、內(nèi)部處理 、 交換 、 輸出四種不同用途的編碼 。 顯示輸出 打印輸出 機(jī)內(nèi)碼向字形碼轉(zhuǎn)換 機(jī)內(nèi)碼 輸入碼向機(jī)內(nèi)碼轉(zhuǎn)換 字符代碼化（輸入） 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 73頁 據(jù)校驗(yàn)碼 校驗(yàn)碼：能夠發(fā)現(xiàn)甚至糾正信息傳輸或存儲過程中出現(xiàn)錯(cuò)誤的編碼 檢錯(cuò)碼：僅能檢測出錯(cuò)誤的編碼 糾錯(cuò)碼：能夠發(fā)現(xiàn)并糾正錯(cuò)誤的編碼 最簡單且應(yīng)用廣泛的檢錯(cuò)碼： 奇偶校驗(yàn)碼 偶校驗(yàn)碼 明校驗(yàn)碼 環(huán)冗余校驗(yàn)碼 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 74頁 據(jù)校驗(yàn)碼 1、數(shù)據(jù)校驗(yàn)的實(shí)現(xiàn)原理：數(shù)據(jù)校驗(yàn)碼是在合法的數(shù)據(jù)編碼之間，加進(jìn)一些不允許出現(xiàn)的 (非法的 )編碼，使合法的數(shù)據(jù)編碼出現(xiàn)錯(cuò)誤時(shí)成為非法編碼。這樣就可以通過檢測編碼的合法性達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。 2、碼距：指任何一種編碼的任兩組二進(jìn)制代碼中，其對應(yīng)位置的代碼最少有幾個(gè)二進(jìn)制位不相同。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 75頁 例： 用奇校驗(yàn)和偶校驗(yàn)進(jìn)行編碼 數(shù)據(jù) 10101010 01010100 00000000 01111111 11111111 偶校驗(yàn)碼 10101010 0 01010100 1 00000000 0 01111111 1 11111111 0 奇校驗(yàn)碼 10101010 1 01010100 0 00000000 1 01111111 0 11111111 1 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 76頁 偶校驗(yàn)碼 1、碼距： 2 2、方法：它是在被傳送的 加上一個(gè)二進(jìn)制位作為校驗(yàn)位，使配置后的 n+1位二進(jìn)制代碼中 1的個(gè)數(shù)為奇數(shù) ( 奇校驗(yàn) )或偶數(shù)(偶校驗(yàn) )。 3、奇偶校驗(yàn)碼只能檢測出數(shù)據(jù)代碼中一位出錯(cuò)的情況，但無法判斷差錯(cuò)所發(fā)生的位置。常用于存儲器讀寫檢查，或 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 77頁 明校驗(yàn)碼 （ 1/8） 1原理：在數(shù)據(jù)位中加入幾個(gè)校驗(yàn)位，將數(shù)據(jù)代碼的碼距均勻地拉大，并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會引起有關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出是哪一位出錯(cuò)，為進(jìn)一步自動糾錯(cuò)提供依據(jù)。 2編碼規(guī)則：若海明碼最高位號為 m，最低位號為 1，即 海明碼的編碼規(guī)則是： 校驗(yàn)位與數(shù)據(jù)位之和為 m，每個(gè)校驗(yàn)位 余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位。 海明碼的每一位位碼 括數(shù)據(jù)位和校驗(yàn)位）由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系是被校驗(yàn)的每一位位號要等于校驗(yàn)它的各校驗(yàn)位的位號之和。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 78頁 明校驗(yàn)碼 （ 2/8） 3增添校驗(yàn)位：假設(shè)欲檢測的有效信息為 增加的校驗(yàn)位為 校驗(yàn)碼的長度為 n+驗(yàn)位的狀態(tài)組合，應(yīng)當(dāng)具有指出 n+需要區(qū)別出 n+k+1種狀態(tài)。應(yīng)滿足關(guān)系式：2kn+k+1 ，此關(guān)系式稱為海明不等式，若信息位長度 此可得到校驗(yàn)位 設(shè)數(shù)據(jù)位是 7位二進(jìn)制編碼，據(jù)上所述，校驗(yàn)位的位數(shù) 海明碼的總位數(shù)為 11。它們的排列關(guān)系可表示為： 位置號： 10 8 6 4 2 明碼： 4 3 1 上 知： 每個(gè)校驗(yàn)位由其本身校驗(yàn)； 每個(gè)數(shù)據(jù)位由若干校驗(yàn)位校驗(yàn)。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 79頁 明校驗(yàn)碼 （ 3/8） 4校驗(yàn)位校驗(yàn)任務(wù)的分配：根據(jù)海明碼編碼規(guī)則，每一位海明碼都有多個(gè)校驗(yàn)位，且被校驗(yàn)每一位的位號等于參與校驗(yàn)的幾個(gè)校驗(yàn)位的位號之和。 占據(jù)各權(quán)位上的校驗(yàn)位按權(quán)組成的 8421碼，正好等于海明碼的位號，即海明碼的位號 例如： 23 22 21 這說明了 校驗(yàn)位 驗(yàn)位 驗(yàn)位 驗(yàn)位 據(jù)校驗(yàn)時(shí)采用奇校驗(yàn)或偶校驗(yàn)，可以寫出相應(yīng)的校驗(yàn)方程。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 80頁 明校驗(yàn)碼 （ 4/8） 例：設(shè)有一個(gè) 7位信息碼位 0110001，求它的海明碼。 解： n=7，根據(jù)海明不等式，可求得校驗(yàn)位最短長度 k=4。 其海明碼先表示如下： 海明碼位號： 10 8 5 2 明碼： 0 1 1 0 0 0 1 偶校驗(yàn)寫出校驗(yàn)方程為： 5 11 0 （ 7 11 0 （ 5 7 0 （ 9 11 0 （ 由此可得： 0、 0、 0、 0，所以 0110001的海明碼為01100000100。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 81頁 明校驗(yàn)碼 （ 5/8） 5檢錯(cuò)與糾錯(cuò) 方法：將錯(cuò)了的碼字重新代入校驗(yàn)方程校驗(yàn)一次即可。設(shè)上例中的海明碼 01100000100傳送后，若 成了 01100100100，代入偶校驗(yàn)方程如下： 5 11 0 1 0 0 1 0 = 0 = 2 7 11 0 1 1 0 1 0 =1 = 4 0 0 1 0 = 1 = 811 0 1 1 0 = 0 = 把 0110看成一個(gè)“指誤字”，其二進(jìn)制碼為 0110，說明 ，所以要糾錯(cuò)，糾錯(cuò)時(shí)將 它恢復(fù)到正確值 0。糾錯(cuò)后，即可得到正確的海明碼 01100000100。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 82頁 明校驗(yàn)碼 （ 6/8） 6討論：設(shè)有效信息 n=4位，據(jù)海明不等式，得校驗(yàn)位 k=3， 海明碼位號： 6 4 2 明碼： 3 1 以得到： 1、 1、 2、 采用偶校驗(yàn)，則： 1 4 1 4 2 4 上述編碼中，兩個(gè)正確碼之間若有一位有效信息不同，則由于該位至少參加兩組的奇偶校驗(yàn)，故至少會影響到兩位校驗(yàn)位的不同，碼距 =3（可檢測兩位錯(cuò)，或檢測并糾正一位錯(cuò)） 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 83頁 明校驗(yàn)碼 （ 7/8） 若按下述關(guān)系對所得的海明碼進(jìn)行偶校驗(yàn)： 1 4 2 4 3 4 則 2 （ 1）若 2 00，無錯(cuò) （ 2）若欲傳的海明碼 =0101101，收到 0111101，則 4=1110=1， ， 表明第 5位（ 錯(cuò) （ 3）若欲傳的海明碼 =0101101，收到 0110101，則 ， ， 表明有錯(cuò)，但無法判斷是第 1位出錯(cuò)，還是 4、 5位同時(shí)出錯(cuò)。 問題？ 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 84頁 明校驗(yàn)碼 （ 8/8） 7改進(jìn)：增加一個(gè)校驗(yàn)位 4 4= 1） ， 00，無錯(cuò) （ 2） ， ，表明有兩位出錯(cuò) （ 3） ， ，根據(jù) 在這種情況下，因多增加一位校驗(yàn)位，則海明不等式改為： 2n+k，稱為擴(kuò)展海明碼，其碼距 =4，可發(fā)現(xiàn)兩位錯(cuò)并糾正一位錯(cuò)。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 85頁 環(huán)冗余校驗(yàn)碼 （ 1/7） 1 長k= n+r 位，稱（ k， n）碼。 設(shè)待編碼的有效信息以多項(xiàng)式 M(x)表示，將 M(x)左移 (x) 低 便與 用多項(xiàng)式 M(x) (x)，求得的余數(shù)即為校驗(yàn)位。為了得到 校驗(yàn)位 )， G(X)必須是 r+1位的。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 86頁 環(huán)冗余校驗(yàn)碼 （ 2/7） 假設(shè) M(x) (x) ，求得的余數(shù)用表達(dá)式 R(x)表示，商的表達(dá)式用 Q(x)表示，它們之間的關(guān)系如下： 這時(shí)將 (X)與左移 (x) 得到 n+ M(x) (x) = Q(x) G(x) + R(x) + R(x) 因?yàn)椤皟蓚€(gè)相同數(shù)據(jù)的模 2和為零”，即 R(x) + R(x) = 0，所以， M(x) (x) = Q(x) G(x) 可以看出，求得的 (X)表示的數(shù)碼除盡的數(shù)碼。 )()()(G ( X ) x ) 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 87頁 環(huán)冗余校驗(yàn)碼 （ 3/7） 例 2設(shè)四位有效信息位是 1100，選用生成多項(xiàng)式 G(X)=1011，試求有效信息位 1100的 解： (1) 將有效信息位 1100表示為多項(xiàng)式 M(x) M(X) = + = 1100 (2) M(X)左移 r=3位，得 M(x) (x) = + = 1100000 (3) 用 r+1位的生成多項(xiàng)式 G(X)，對 M(x) 2除” 1100000/1011 = 1110 + 010/1011 (4) M(x) (X) 作“模 2加”，即可求得 M(x) R(X) = 1100000 + 010 = 1100010 (模 2加 ) 因?yàn)?k=7、 n=4，所以編好的 7， 4)碼。 計(jì)算機(jī)組成原理 第二章計(jì)算機(jī)中的數(shù)據(jù)表示 2016年 3月 14日 第 88頁 環(huán)冗