2數(shù)據(jù)的表示和運算-1

1、計算機組成原理計算機組成原理第第2 2章章 數(shù)據(jù)的表示和運算數(shù)據(jù)的表示和運算主要內(nèi)容：主要內(nèi)容：（一）（一） 數(shù)制與編碼數(shù)制與編碼 1. 1. 進位計數(shù)制及其相互轉(zhuǎn)換進位計數(shù)制及其相互轉(zhuǎn)換 2. 2. 真值和機器數(shù)真值和機器數(shù) 3. BCD3. BCD 碼碼 4. 4. 字符與字符串字符與字符串 5. 5. 校驗碼校驗碼 （二）（二） 定點數(shù)的表示和運算定點數(shù)的表示和運算 1. 1. 定點數(shù)的表示定點數(shù)的表示 ：無符號數(shù)的表示；有符號數(shù)的表示。：無符號數(shù)的表示；有符號數(shù)的表示。 2. 2. 定點數(shù)的運算定點數(shù)的運算 ：定點數(shù)的位移運算；原碼定點數(shù)的加：定點數(shù)的位移運算；原碼定點數(shù)的加/ /減運

2、算；補減運算；補碼定點數(shù)的加碼定點數(shù)的加/ /減運算；定點數(shù)的乘減運算；定點數(shù)的乘/ /除運算；溢出概念和判別方法。除運算；溢出概念和判別方法。 （三）（三） 浮點數(shù)的表示和運算浮點數(shù)的表示和運算 1. 1. 浮點數(shù)的表示浮點數(shù)的表示 ：浮點數(shù)的表示范圍；：浮點數(shù)的表示范圍；IEEE754IEEE754 標準標準 2. 2. 浮點數(shù)的加浮點數(shù)的加/ /減運算減運算 （四）（四） 算術(shù)邏輯單元算術(shù)邏輯單元 ALU ALU 1. 1. 串行加法器和并行加法器串行加法器和并行加法器 2. 2. 算術(shù)邏輯單元算術(shù)邏輯單元 ALUALU 的功能和機構(gòu)的功能和機構(gòu) 計算機組成原理計算機組成原理2.1 數(shù)字

3、信息和二進制編碼數(shù)字信息和二進制編碼 信息：數(shù)值、文字、符號、語音和圖形、圖像等。信息：數(shù)值、文字、符號、語音和圖形、圖像等。在計算機內(nèi)部，信息都必須用數(shù)字化的形式被存儲、加工和在計算機內(nèi)部，信息都必須用數(shù)字化的形式被存儲、加工和傳送，不同信息要通過編碼來表示。傳送，不同信息要通過編碼來表示。 編碼：用少量簡單的基本符號，對大量復(fù)雜多樣信息進行編碼：用少量簡單的基本符號，對大量復(fù)雜多樣信息進行一定規(guī)律的組合表示。一定規(guī)律的組合表示。編碼的兩個要素：少量簡單的基本符號、一定的組合規(guī)則編碼的兩個要素：少量簡單的基本符號、一定的組合規(guī)則數(shù)值數(shù)據(jù)編碼需解決：數(shù)值數(shù)據(jù)編碼需解決： 數(shù)的大?。翰捎檬裁催M位

4、計數(shù)制數(shù)的大?。翰捎檬裁催M位計數(shù)制 數(shù)的符號表示：數(shù)的符號表示：原碼、補碼、反碼原碼、補碼、反碼 小數(shù)點的表示：定點、浮點小數(shù)點的表示：定點、浮點 計算機中普遍選用兩個基本符號：計算機中普遍選用兩個基本符號： 優(yōu)點：優(yōu)點： 基本符號個數(shù)最少，物理上容易實現(xiàn)基本符號個數(shù)最少，物理上容易實現(xiàn)二進制碼表示數(shù)值數(shù)據(jù)運算規(guī)則簡單二進制碼表示數(shù)值數(shù)據(jù)運算規(guī)則簡單與二值邏輯的真、假兩個值對應(yīng)簡單與二值邏輯的真、假兩個值對應(yīng)簡單計算機組成原理計算機組成原理二進制數(shù)據(jù)算術(shù)運算規(guī)則二進制數(shù)據(jù)算術(shù)運算規(guī)則(2) 減法運算規(guī)則 0-0=0 0-1=1 并產(chǎn)生借位 1-0=1 1-1=0(1) 加法運算規(guī)則 0+0=0

5、 0+1=1 1+0=1 1+1=0 并產(chǎn)生進位例如：例如： 0101+) 0001 0110例如：例如： 1011) 0101 0110 0110計算機組成原理計算機組成原理二進制數(shù)據(jù)算術(shù)運算規(guī)則二進制數(shù)據(jù)算術(shù)運算規(guī)則乘法運算規(guī)則 例如： 1101 00=0 ) 0101 01=0 1101 10=0 0000 11=1 1101 1000001 除法運算規(guī)則 0101 例如： 1101 1000001 1000001 / 1101 = 0101 1101 01101 1101 0計算機組成原理計算機組成原理2.1.1 進位計數(shù)制及其相互轉(zhuǎn)換進位計數(shù)制及其相互轉(zhuǎn)換1. 進位計數(shù)制進位計數(shù)制是

6、指按照進位制的方法表示數(shù)，不同的數(shù)制均涉及兩是指按照進位制的方法表示數(shù)，不同的數(shù)制均涉及兩個基本概念：基數(shù)和權(quán)。個基本概念：基數(shù)和權(quán)。基數(shù)：進位計數(shù)制中所擁有數(shù)字的個數(shù)?；鶖?shù)：進位計數(shù)制中所擁有數(shù)字的個數(shù)。權(quán)：每位數(shù)字的值等于數(shù)字乘以所在位數(shù)的相關(guān)常權(quán)：每位數(shù)字的值等于數(shù)字乘以所在位數(shù)的相關(guān)常數(shù)，這個常數(shù)就是權(quán)。數(shù)，這個常數(shù)就是權(quán)。任意一個任意一個r進制數(shù)進制數(shù)N，設(shè)整數(shù)部分為，設(shè)整數(shù)部分為n位，小數(shù)部分為位，小數(shù)部分為m位，則位，則N代表的實際值可表示為：代表的實際值可表示為：1 -nmiiirDNDn-1rn-1 + Dn-2rn-2 + + D0r0 + D-1r-1 + D-2r-2

7、+ + D-mr-m (N)r =計算機組成原理計算機組成原理計算機中常用的 4 種進位數(shù)制（r數(shù)制的基） 二進制(B)：r = 2， 基本符號：0 1 八進制(O) ：r = 8， 基本符號：0 1 2 3 4 5 6 7 十進制(D) ：r = 10，基本符號：0 1 2 3 4 5 6 7 8 9 十六進制(H)：r = 16，基本符號： 0 1 2 3 4 5 6 7 8 9 A B C D E F其中 AF 表示十進制數(shù) 1015 4 種進位數(shù)制之間的關(guān)系：二進制用于計算機內(nèi)部八和十六進制是二進制的縮寫 十進制用于編程、操作人員。進位計數(shù)制進位計數(shù)制2. 不同數(shù)制間的數(shù)據(jù)轉(zhuǎn)換不同數(shù)制

8、間的數(shù)據(jù)轉(zhuǎn)換 二、八、十六進制數(shù)轉(zhuǎn)換成十進制數(shù)二、八、十六進制數(shù)轉(zhuǎn)換成十進制數(shù) 利用上面的公式進行計算：利用上面的公式進行計算： (N)2=Di 2i 、(N)8=Di 8i、 (N)16=Di 16i、。、。 十進制數(shù)轉(zhuǎn)換成二進制數(shù)十進制數(shù)轉(zhuǎn)換成二進制數(shù)通常要對一個數(shù)的整數(shù)部分和小數(shù)部分分別進行處理，各自得出結(jié)果后通常要對一個數(shù)的整數(shù)部分和小數(shù)部分分別進行處理，各自得出結(jié)果后再合并。再合并。n 對整數(shù)部分，對整數(shù)部分，一般采用除一般采用除2取余數(shù)法取余數(shù)法，其規(guī)則如下：，其規(guī)則如下： 將十進制數(shù)除以將十進制數(shù)除以2，所得余數(shù)（，所得余數(shù)（0或或1）即為對應(yīng)二進制數(shù)最低位的值。）即為對應(yīng)二進制

9、數(shù)最低位的值。然后對上次所得商除以然后對上次所得商除以2，所得余數(shù)即為二進制數(shù)次低位的值，如此，所得余數(shù)即為二進制數(shù)次低位的值，如此進行下去，直到商等于進行下去，直到商等于0為止，最后得的余數(shù)是所求二進制數(shù)最高位為止，最后得的余數(shù)是所求二進制數(shù)最高位的值。的值。n 對小數(shù)部分，對小數(shù)部分，一般用乘一般用乘2取整法取整法，其規(guī)則如下：，其規(guī)則如下： 將十進制數(shù)乘以將十進制數(shù)乘以2，所得乘積的整數(shù)部分即為對應(yīng)二進制小數(shù)最高位，所得乘積的整數(shù)部分即為對應(yīng)二進制小數(shù)最高位的值，然后對所余數(shù)的小數(shù)部分部分乘以的值，然后對所余數(shù)的小數(shù)部分部分乘以2，所得乘積的整數(shù)部分為，所得乘積的整數(shù)部分為次高位的值，如

10、此進行下去，直到乘積的小數(shù)部分為次高位的值，如此進行下去，直到乘積的小數(shù)部分為0，或結(jié)果已滿，或結(jié)果已滿足所需精度要求為止。足所需精度要求為止。計算機組成原理計算機組成原理思考題：思考題：請分別將（請分別將（ ）2 和（和（ 0.8125 ）2化成二化成二進制。進制。計算機組成原理計算機組成原理二進制數(shù)、八進制數(shù)和十六進制數(shù)之間的轉(zhuǎn)換二進制數(shù)、八進制數(shù)和十六進制數(shù)之間的轉(zhuǎn)換八進制數(shù)和十六進制數(shù)是從二進制數(shù)演變而來的：八進制數(shù)和十六進制數(shù)是從二進制數(shù)演變而來的：由由3位二進制數(shù)組成位二進制數(shù)組成1位八進制數(shù)；位八進制數(shù)；由由4位二進制數(shù)組成位二進制數(shù)組成1位十六進制數(shù)。位十六進制數(shù)。 對于一個兼

11、有整數(shù)和小數(shù)部分的數(shù)以小數(shù)點為對于一個兼有整數(shù)和小數(shù)部分的數(shù)以小數(shù)點為界，小數(shù)點前后的數(shù)分別分組進行處理，不足界，小數(shù)點前后的數(shù)分別分組進行處理，不足的位數(shù)用的位數(shù)用0補足。補足。 對整數(shù)部分將對整數(shù)部分將0補在數(shù)的左側(cè)，對小數(shù)部分將補在數(shù)的左側(cè)，對小數(shù)部分將0補在數(shù)的右側(cè)。這樣數(shù)值不會發(fā)生差錯。補在數(shù)的右側(cè)。這樣數(shù)值不會發(fā)生差錯。計算機組成原理計算機組成原理二進制數(shù)與八、十六進制數(shù)之間的直接轉(zhuǎn)換法二進制數(shù)與八、十六進制數(shù)之間的直接轉(zhuǎn)換法二二八八000 0001 1010 2011 3100 4101 5110 6111 7要求：迅速、準確，爛熟于心。要求：迅速、準確，爛熟于心。計算機組成原理

12、計算機組成原理2.1.2 數(shù)據(jù)的表示數(shù)據(jù)的表示1. 真值和機器數(shù)真值和機器數(shù)真值：數(shù)據(jù)的數(shù)值通常以正真值：數(shù)據(jù)的數(shù)值通常以正(+)、負、負(-)號后跟絕對值來表示，號后跟絕對值來表示，稱之為稱之為“真值真值”。機器數(shù)：在計算機中正負號也需要數(shù)字化，一般用機器數(shù)：在計算機中正負號也需要數(shù)字化，一般用0表示表示正號，正號，1表示負號。把符號數(shù)字化的數(shù)稱為機器數(shù)。表示負號。把符號數(shù)字化的數(shù)稱為機器數(shù)。邏輯型數(shù)據(jù)邏輯型數(shù)據(jù)字符型數(shù)據(jù)字符型數(shù)據(jù) ASCII 碼碼 EBCDIC 碼碼 字符串字符串 漢字漢字數(shù)值型數(shù)據(jù)數(shù)值型數(shù)據(jù) 定點小數(shù)定點小數(shù) 整數(shù)整數(shù) 浮點數(shù)浮點數(shù) 二二十進制數(shù)（十進制數(shù)（BCD碼）碼

13、） 計算機組成原理計算機組成原理2 . 邏輯型數(shù)據(jù)邏輯型數(shù)據(jù) 邏輯型數(shù)據(jù)只有兩個值：真 和 假，正好可以用二進制碼的兩個符號分別表示，例如 1 表示 真 則 0 表示 假 不必使用另外的編碼規(guī)則。 對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的 與 或 非等基本邏輯運算。其規(guī)則如下：計算機組成原理計算機組成原理邏輯型數(shù)據(jù)基本運算規(guī)則邏輯型數(shù)據(jù)基本運算規(guī)則 一個二進制數(shù)位可以用來表示一個二值邏輯型的變量，更準確的說法應(yīng)該是一個基2碼位而不是二進制的數(shù)位，因為邏輯型數(shù)據(jù)不存在進位關(guān)系（位間獨立）。這里的與、或、非邏輯可以用與門、或門、非門電路實現(xiàn) 。 X Y X與與Y X或或Y X的非的非 0 0 0 0 1 0 1

14、 0 1 1 1 0 0 1 0 1 1 1 1 0 計算機組成原理計算機組成原理3. 字符型數(shù)據(jù)的表示字符型數(shù)據(jù)的表示 字符作為人字符作為人機聯(lián)系的媒介，是最重要的數(shù)據(jù)類型之一，當機聯(lián)系的媒介，是最重要的數(shù)據(jù)類型之一，當前的西文字符集由前的西文字符集由 128 個符號組成，通常用個符號組成，通常用 8 位二進制編位二進制編碼，即碼，即用一個字節(jié)來表示一個字符。用一個字節(jié)來表示一個字符。常用兩個標準字符集：常用兩個標準字符集：EBCDIC碼碼： Extended Binary Coded Decimal Interchange CodeASCII 碼碼： American Standard C

15、ode for Information Interchange ASCII碼用碼用7位二進制表示一個字符，總共位二進制表示一個字符，總共128個字符元個字符元素，包括素，包括10個十進制數(shù)字（個十進制數(shù)字（0-9）、）、52個英文字母（個英文字母（A-Z和和a-z）、）、34個專用符號和個專用符號和32個控制符號。個控制符號。ASCII碼字符碼字符集具體編碼如下表所示：集具體編碼如下表所示： 計算機組成原理計算機組成原理ASCII 碼字符集碼字符集計算機組成原理計算機組成原理4. 字符串的表示與存儲字符串的表示與存儲 字符串是指連續(xù)的一串字符，它們占據(jù)主存中連續(xù)的多個字字符串是指連續(xù)的一串字符

16、，它們占據(jù)主存中連續(xù)的多個字節(jié)，通常每個字節(jié)存放一個字符。節(jié)，通常每個字節(jié)存放一個字符。 字符串的存放字符串的存放 向量存儲法：字符串存儲時，字符串中的所有元素在物理向量存儲法：字符串存儲時，字符串中的所有元素在物理上是鄰接的，上是鄰接的，對一個主存字的多個字節(jié)，有按從低位到高對一個主存字的多個字節(jié)，有按從低位到高位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。 串表存儲法：字符串的每個字符代碼后面設(shè)置一個鏈接字，串表存儲法：字符串的每個字符代碼后面設(shè)置一個鏈接字，用于指出下一個字符的存儲單元的地址。用于指出下一個字符的存儲單元的地址。

17、表示字符串數(shù)據(jù)要給出串存放的主存起始地址和串的長度。表示字符串數(shù)據(jù)要給出串存放的主存起始地址和串的長度。例如：例如：IF AB THEN READ(C)IF AB THEN READ(C) 就可以有如下不同存放方式。就可以有如下不同存放方式。 計算機組成原理計算機組成原理字符串的表示與存儲字符串的表示與存儲IFABTHENREAD(C)494620413e42205448454e20524541442843292008 716 1524 2331按從高位到低位字節(jié)次序存放按從高位到低位字節(jié)次序存放16進制數(shù)據(jù)進制數(shù)據(jù)假定每個主存字假定每個主存字由由 4 4 個字節(jié)組成個字節(jié)組成計算機組成原理計

18、算機組成原理AFITBNEHDAER)C(412046495420423E204E4548444145522029432808 716 1524 2331按從低位到高位字節(jié)次序存放按從低位到高位字節(jié)次序存放16進制數(shù)據(jù)進制數(shù)據(jù)計算機組成原理計算機組成原理5. 漢字的表示與編碼漢字的表示與編碼 通常用兩個字節(jié)表示一個漢字。通常用兩個字節(jié)表示一個漢字。 為了與西文字符編碼相區(qū)別（西文的為了與西文字符編碼相區(qū)別（西文的ASCII碼碼的最高一位編碼值為的最高一位編碼值為 0），表示一個漢字時，把），表示一個漢字時，把兩個字節(jié)的最高一位的編碼值設(shè)定為兩個字節(jié)的最高一位的編碼值設(shè)定為 1，則該編，則該編碼

19、集的最多編碼數(shù)量為碼集的最多編碼數(shù)量為 128 128。 這種編碼方案與西文傳送中的把這種編碼方案與西文傳送中的把 ASCII 碼的碼的最高一位用作奇偶校驗位有矛盾。最高一位用作奇偶校驗位有矛盾。 計算機組成原理計算機組成原理漢字的表示方法漢字的表示方法 漢字內(nèi)碼漢字內(nèi)碼 內(nèi)碼是用于漢字信息的內(nèi)碼是用于漢字信息的存儲、交換、檢索存儲、交換、檢索等操作的機內(nèi)等操作的機內(nèi)代碼，它一般采用兩個字節(jié)的二進制形式表示一個漢字。代碼，它一般采用兩個字節(jié)的二進制形式表示一個漢字。 通訊用漢字字符集（基本集）及其交換碼標準通訊用漢字字符集（基本集）及其交換碼標準，年，年，6763個漢字，個漢字，682個非漢字

20、字符個非漢字字符. 漢字輸入編碼漢字輸入編碼 輸入編碼是為了使用西文標準鍵盤把漢字輸入到計算機輸入編碼是為了使用西文標準鍵盤把漢字輸入到計算機中，其編碼方法主要有中，其編碼方法主要有數(shù)字編碼、拼音碼數(shù)字編碼、拼音碼和和字形編碼等字形編碼等。 漢字字模輸出編碼漢字字模輸出編碼 字模編碼是以點陣方式用來描述字模編碼是以點陣方式用來描述 漢字字形漢字字形的代碼，它是漢字的輸?shù)拇a，它是漢字的輸 出形式。出形式。計算機組成原理計算機組成原理6. 6. 數(shù)值數(shù)據(jù)在計算機內(nèi)的格式數(shù)值數(shù)據(jù)在計算機內(nèi)的格式 符號位符號位 階碼位階碼位 尾數(shù)數(shù)碼位尾數(shù)數(shù)碼位 總位數(shù)總位數(shù) 短浮點數(shù)短浮點數(shù): 1 8 23 32

21、長浮點數(shù)長浮點數(shù): 1 11 52 64 臨時浮點數(shù)臨時浮點數(shù): 1 15 64 80IEEE 標準：標準： 階碼用移碼階碼用移碼 尾數(shù)用原碼尾數(shù)用原碼 基為基為 2定點小數(shù)定點小數(shù): N = N: N = NS S N N-1 -1 N N -2-2 N N-n-n定點整數(shù)定點整數(shù): N = N: N = NS S N Nn-1n-1 N N1 1 N N0 0浮點數(shù)浮點數(shù): N =: N = M MS S E ES S E Em-1m-1 E E1 1 E E0 0 M M-1-1 M M-2 M M-n 計算機組成原理計算機組成原理數(shù)值范圍和數(shù)據(jù)精度數(shù)值范圍和數(shù)據(jù)精度數(shù)值范圍 數(shù)值范圍是

22、指一種類型的數(shù)據(jù)所能表示的最大值和最小值。數(shù)據(jù)精度 通常指實數(shù)所能給出的有效數(shù)字位數(shù)；對浮點數(shù)來說，精度不夠會造成誤差，誤差大量積累會出問題。機內(nèi)處理 數(shù)值范圍與數(shù)據(jù)精度概念不同。在計算機中，它們的值與用多少個二進制位表示某種類型的數(shù)據(jù)，以及怎么對這些位進行編碼有關(guān)。計算機組成原理計算機組成原理二二 十進制碼（十進制碼（BCD碼）碼）BCD碼：在計算機中采用碼：在計算機中采用4位二進制碼對每個十進位二進制碼對每個十進制數(shù)位進行編碼，一個多位的十進制數(shù)被表示為這制數(shù)位進行編碼，一個多位的十進制數(shù)被表示為這種編碼的數(shù)串。種編碼的數(shù)串。4位二進制碼有位二進制碼有16種不同的組合，種不同的組合，從中選

23、出從中選出10種來表示十進制數(shù)位的種來表示十進制數(shù)位的09，用，用0000，0001，1001分別表示分別表示0，1，9，每個數(shù)位，每個數(shù)位內(nèi)部滿足二進制規(guī)則，而數(shù)位之間滿足十進制規(guī)則，內(nèi)部滿足二進制規(guī)則，而數(shù)位之間滿足十進制規(guī)則，故稱這種編碼為故稱這種編碼為“以二進制編碼的十進制（以二進制編碼的十進制（Binary Coded Decimal，簡稱，簡稱BCD）碼）碼”。BCD碼加法運算的修正規(guī)則：碼加法運算的修正規(guī)則：如果兩個一位如果兩個一位BCD碼相加之和小于或等于碼相加之和小于或等于9，不需要修，不需要修正；正；如相加之和大于如相加之和大于9或產(chǎn)生進位，要進行加或產(chǎn)生進位，要進行加6修

24、正，如果修正，如果有進位，要向高位進位。有進位，要向高位進位。計算機組成原理計算機組成原理BCD碼碼BCD碼有多種不同的編碼方案：碼有多種不同的編碼方案： 例如：例如：8421碼，碼， 84-2-1碼，余碼，余 3 碼，格雷碼碼，格雷碼 可以進一步分為有權(quán)碼和無權(quán)碼：可以進一步分為有權(quán)碼和無權(quán)碼： 有權(quán)碼：每位上的有權(quán)碼：每位上的 1 代表確定的值代表確定的值 無權(quán)碼：無法確定每位上的無權(quán)碼：無法確定每位上的 1 代表的值代表的值計算機組成原理計算機組成原理0 0000 0000 0011 00001 0001 0111 0100 00012 0010 0110 0101 00113 0011

25、 0101 0110 00104 0100 0100 0111 01105 0101 1011 1000 11106 0110 1010 1001 10107 0111 1001 1010 10008 1000 1000 1011 11009 1001 1111 1100 0100有權(quán)碼有權(quán)碼 無權(quán)碼無權(quán)碼842184-2-1 余余3碼碼格雷碼格雷碼計算機組成原理計算機組成原理如何判定碼權(quán)如何判定碼權(quán)0 00001 0111 4 +（-2）+（-1）2 0110 4 +（-2） 要驗證每個碼的值3 0101 4 +（-1）4 0100 4 從一編碼求碼權(quán)從一編碼求碼權(quán)5 1011 8 +（-2

26、）+（-1）6 1010 -2 結(jié)論結(jié)論7 1001 -1 證明此編碼系統(tǒng)為有權(quán)碼證明此編碼系統(tǒng)為有權(quán)碼8 1000 89 1111 8 + 4 +（-2）+（-1）計算機組成原理計算機組成原理如何判定碼權(quán)如何判定碼權(quán) 0 0011 2+1 0 驗證各碼的值 1 0100 1 從一編碼求碼權(quán) 2 0101 1 3 0110 2 4 0111 5 1000 6 1001 結(jié)論 7 1010 證明此編碼系統(tǒng)為無權(quán)碼 8 1011 9 1100 計算機組成原理計算機組成原理2.1.3 校驗碼校驗碼 要提高計算機的可靠性，除了采取選用更高可靠要提高計算機的可靠性，除了采取選用更高可靠性的器件，更好的生

27、產(chǎn)工藝等措施之外，還可以針對性的器件，更好的生產(chǎn)工藝等措施之外，還可以針對薄弱環(huán)節(jié)，從數(shù)據(jù)編碼上想一些辦法，即采用少量冗薄弱環(huán)節(jié)，從數(shù)據(jù)編碼上想一些辦法，即采用少量冗余的線路，在原有數(shù)據(jù)位之外再增加一到幾個校驗位，余的線路，在原有數(shù)據(jù)位之外再增加一到幾個校驗位，使新得到的由數(shù)據(jù)位和校驗位構(gòu)成的碼字帶上某種特使新得到的由數(shù)據(jù)位和校驗位構(gòu)成的碼字帶上某種特性，在經(jīng)過薄弱環(huán)節(jié)之后，則通過檢查該碼字是否仍性，在經(jīng)過薄弱環(huán)節(jié)之后，則通過檢查該碼字是否仍保持有這一特性，來判斷碼字中的某一、二位的值是保持有這一特性，來判斷碼字中的某一、二位的值是否發(fā)生了變化，即是否出現(xiàn)了錯誤，甚至于定位錯誤否發(fā)生了變化，即

28、是否出現(xiàn)了錯誤，甚至于定位錯誤后，自動改正這一錯誤，這就是檢錯糾錯編碼技術(shù)或后，自動改正這一錯誤，這就是檢錯糾錯編碼技術(shù)或校驗碼方法。校驗碼方法。計算機組成原理計算機組成原理校驗碼校驗碼數(shù)據(jù)校驗碼是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改錯能數(shù)據(jù)校驗碼是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改錯能力的數(shù)據(jù)編碼方法。其實現(xiàn)原理，是加進一些冗余碼，使力的數(shù)據(jù)編碼方法。其實現(xiàn)原理，是加進一些冗余碼，使合法數(shù)據(jù)編碼出現(xiàn)某些錯誤時，就成為非法編碼。合法數(shù)據(jù)編碼出現(xiàn)某些錯誤時，就成為非法編碼。這樣，可以通過檢測編碼的合法性來達到發(fā)現(xiàn)錯誤的目的。這樣，可以通過檢測編碼的合法性來達到發(fā)現(xiàn)錯誤的目的。合理地安排非法編碼數(shù)量

29、和編碼規(guī)則，可以提高發(fā)現(xiàn)錯誤合理地安排非法編碼數(shù)量和編碼規(guī)則，可以提高發(fā)現(xiàn)錯誤的能力，或達到自動改正錯誤的目的。的能力，或達到自動改正錯誤的目的。 碼距：指任意兩個合法碼之間至少有幾個二進制位不相同。碼距：指任意兩個合法碼之間至少有幾個二進制位不相同。僅有一位不同，稱其碼距為僅有一位不同，稱其碼距為1。 奇偶校驗碼為奇偶校驗碼為2。 合理增大碼距，能提高發(fā)現(xiàn)錯誤的能力，但表示一定合理增大碼距，能提高發(fā)現(xiàn)錯誤的能力，但表示一定數(shù)量的合法碼所使用的二進制位數(shù)要變多，增加了電數(shù)量的合法碼所使用的二進制位數(shù)要變多，增加了電子線路的復(fù)雜性和數(shù)據(jù)存儲、數(shù)據(jù)傳送的數(shù)量。子線路的復(fù)雜性和數(shù)據(jù)存儲、數(shù)據(jù)傳送的數(shù)

30、量。計算機組成原理計算機組成原理幾種常用的校驗碼幾種常用的校驗碼介紹三種常用的校驗碼：奇偶校驗碼：用于奇偶校驗碼：用于串、并行數(shù)據(jù)串、并行數(shù)據(jù)傳送中傳送中循環(huán)冗余校驗碼：用于循環(huán)冗余校驗碼：用于串行數(shù)據(jù)串行數(shù)據(jù)傳送中傳送中海明校驗碼：用于并行數(shù)據(jù)傳送中（不在考試范圍）編碼過程編碼過程原始數(shù)據(jù)原始數(shù)據(jù)形成校驗位的值形成校驗位的值加進特征加進特征譯碼過程譯碼過程結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)檢查收到的碼字檢查收到的碼字發(fā)現(xiàn)發(fā)現(xiàn) / / 改正錯誤改正錯誤運行過程運行過程的的 3 步曲：步曲：傳送傳送碼碼 字字薄弱環(huán)節(jié)薄弱環(huán)節(jié)計算機組成原理計算機組成原理1. 奇偶校驗碼奇偶校驗碼實現(xiàn)原理：是使碼距由實現(xiàn)原理：是使碼

31、距由1增加到增加到2。若編碼中有。若編碼中有1位二位二進制數(shù)出錯了，出錯的編碼就成為非法編碼，就可進制數(shù)出錯了，出錯的編碼就成為非法編碼，就可以知道出現(xiàn)了錯誤。在原有的編碼之上再增加一位以知道出現(xiàn)了錯誤。在原有的編碼之上再增加一位校驗位，原編碼校驗位，原編碼k位，形成新的編碼為位，形成新的編碼為k+1 位。增加位。增加的方法有的方法有2種：種： 奇校驗：增加位的奇校驗：增加位的0或或1要保證整個編碼中要保證整個編碼中1的個數(shù)為奇的個數(shù)為奇數(shù)個。數(shù)個。 偶校驗：增加位的偶校驗：增加位的0或或1要保證整個編碼中要保證整個編碼中1的個數(shù)為偶的個數(shù)為偶數(shù)個。數(shù)個。計算機組成原理計算機組成原理奇校驗奇校

32、驗 1出錯出錯偶校驗偶校驗1出錯出錯D校校為校驗位為校驗位 D校校D0D1D2D3D4D5D6D78 8位數(shù)據(jù)的奇偶校驗碼形成電路及檢碼電路位數(shù)據(jù)的奇偶校驗碼形成電路及檢碼電路計算機組成原理計算機組成原理奇偶校驗碼的實現(xiàn)電路奇偶校驗碼的實現(xiàn)電路 奇校驗 偶校驗譯碼電路譯碼電路+同左側(cè)虛框內(nèi)電路同左側(cè)虛框內(nèi)電路P (校驗位校驗位)D7 D6 D5 D4 D3 D2 D1 D0+編碼電路編碼電路8位數(shù)據(jù)位位數(shù)據(jù)位p偶校驗出錯指示偶校驗出錯指示奇校驗出錯指示奇校驗出錯指示計算機組成原理計算機組成原理 【例例】選擇題：如果需要對選擇題：如果需要對3 3個字節(jié)的數(shù)據(jù)進行縱向奇偶校驗，可再增加個字節(jié)的數(shù)據(jù)

33、進行縱向奇偶校驗，可再增加1 1 個字節(jié)作為縱向校驗字節(jié)，縱向校驗的奇偶性與橫向校驗的奇偶性相同。個字節(jié)作為縱向校驗字節(jié)，縱向校驗的奇偶性與橫向校驗的奇偶性相同。若被校驗的若被校驗的3 3個字節(jié)數(shù)據(jù)分別是個字節(jié)數(shù)據(jù)分別是A9HA9H、B8HB8H和和CFH CFH ，則新增加的校驗字節(jié)數(shù)，則新增加的校驗字節(jié)數(shù)據(jù)是（據(jù)是（ ）。）。 A. AEHA. AEH B. DEH B. DEH C . D6H C . D6HD.5EH D.5EH 【 分析分析】 3 個橫向校驗碼個橫向校驗碼A9H 、B8H 和和CFH 中中1 的個數(shù)均為偶數(shù)個，說明系統(tǒng)采用的個數(shù)均為偶數(shù)個，說明系統(tǒng)采用的是偶校驗，的是

34、偶校驗，4 個字節(jié)（個字節(jié)（3 個數(shù)據(jù)字節(jié)加上縱向校驗字節(jié)）對應(yīng)位中個數(shù)據(jù)字節(jié)加上縱向校驗字節(jié)）對應(yīng)位中1 的個數(shù)也應(yīng)的個數(shù)也應(yīng)當為偶數(shù)個。在當為偶數(shù)個。在4 個選項中只有個選項中只有B 選項符合條件。選項符合條件?！?歸納總結(jié)歸納總結(jié)】 計算機在進行大量字節(jié)（數(shù)據(jù)塊）傳送時，不僅每一個字節(jié)有一個奇計算機在進行大量字節(jié)（數(shù)據(jù)塊）傳送時，不僅每一個字節(jié)有一個奇偶校驗位做橫向校驗，而且全部字節(jié)的同一位也設(shè)置一個奇偶校驗位做縱向校驗，偶校驗位做橫向校驗，而且全部字節(jié)的同一位也設(shè)置一個奇偶校驗位做縱向校驗，這種橫向、縱向同時校驗的方法稱為交叉校驗。這種橫向、縱向同時校驗的方法稱為交叉校驗?！?解題技巧

35、解題技巧】 首先根據(jù)首先根據(jù)3 個字節(jié)數(shù)據(jù)確定校驗規(guī)則的奇偶性，增加的縱向校驗字節(jié)個字節(jié)數(shù)據(jù)確定校驗規(guī)則的奇偶性，增加的縱向校驗字節(jié)要保證縱向每一位也符合同樣的奇偶性。要保證縱向每一位也符合同樣的奇偶性。答案：答案：B 計算機組成原理計算機組成原理2. 2. 循環(huán)冗余校驗碼（循環(huán)冗余校驗碼（CRCCRC）CRCCRC（Cyclical Redundancy CheckCyclical Redundancy Check）校驗碼一般是指）校驗碼一般是指k k位位信息之后拼接信息之后拼接r r位校驗碼。關(guān)鍵問題是如何從位校驗碼。關(guān)鍵問題是如何從k k位信息得到位信息得到r r位校驗碼。進一步：如何從

36、位校驗碼。進一步：如何從k+rk+r位碼字判斷是否出錯，哪位位碼字判斷是否出錯，哪位出錯。出錯。 用于多位串行數(shù)據(jù)傳送中的檢錯、糾錯處理，在用于多位串行數(shù)據(jù)傳送中的檢錯、糾錯處理，在 k k 位數(shù)據(jù)位串行移位輸出的過程中，用帶有異或門控制位數(shù)據(jù)位串行移位輸出的過程中，用帶有異或門控制的移位寄存器形成的移位寄存器形成 r r 個校驗位的值，跟隨在數(shù)據(jù)位個校驗位的值，跟隨在數(shù)據(jù)位之后傳送走。之后傳送走。 在接收端再對在接收端再對 k+r k+r 位的碼字進行合法與出錯檢查，位的碼字進行合法與出錯檢查，若可能則自動改錯。若可能則自動改錯。計算機組成原理計算機組成原理CRCCRC碼的編碼方法碼的編碼方

37、法CRCCRC整個編碼長度為整個編碼長度為 n=k+r n=k+r 位，故位，故CRCCRC碼又叫（碼又叫（n n，k k）碼。其編）碼。其編碼方法如下：碼方法如下： 假設(shè)被傳送的假設(shè)被傳送的k k位二進制信息位用位二進制信息位用C(x)C(x)表示表示, , 系統(tǒng)選定的系統(tǒng)選定的生成多項式用生成多項式用G(X)G(X)表示，將表示，將C(x)C(x)左移左移 G(X)G(X)的最高次冪的最高次冪( (即即等于需要添加的校驗位的位數(shù)等于需要添加的校驗位的位數(shù)r)r)，寫作，寫作 C(x)2 C(x)2 r r 然后將然后將C(x)2 C(x)2 r r除以生成多項式除以生成多項式G(x)G(x

38、)，所得商用，所得商用Q(x)Q(x)表示，表示，余數(shù)用余數(shù)用R(x)R(x)表示。則有：表示。則有： 兩邊同時乘以兩邊同時乘以G(x)G(x)并左移并左移 R(x) R(x) 得到：得到：)()()()(2)(xGxRxQxGxCr)()()(2)(xGxQxRxCr計算機組成原理計算機組成原理故有：故有： 上式中，等式左邊即為所求的上式中，等式左邊即為所求的n n位位CRCCRC碼，其中余數(shù)表達式碼，其中余數(shù)表達式R(x)R(x)就是校驗位就是校驗位(r(r位位) )。且等式兩邊都是。且等式兩邊都是G(x)G(x)的倍數(shù)。的倍數(shù)。 發(fā)送信息時將等式左邊生成的發(fā)送信息時將等式左邊生成的n n

39、位位CRCCRC碼送給對方。當碼送給對方。當接收接收方接到方接到n n位編碼后，同樣除以位編碼后，同樣除以G(x)G(x)，如果傳輸正確則余數(shù)為，如果傳輸正確則余數(shù)為0 0，否則，可以根據(jù)余數(shù)的數(shù)值確定是哪位數(shù)據(jù)出錯。否則，可以根據(jù)余數(shù)的數(shù)值確定是哪位數(shù)據(jù)出錯。)()()(2)(011,101,110,000 xGxQxRxCrCRC編碼采用的是按位加、減法，即不考慮進位與借位，運算編碼采用的是按位加、減法，即不考慮進位與借位，運算規(guī)則為：規(guī)則為： 0 0=0，0 1=1，1 0=1，1 1=0計算機組成原理計算機組成原理【例例】有一個（有一個（7,47,4）碼（即）碼（即CRCCRC碼為碼為

40、7 7位，信息碼為位，信息碼為4 4位），位），已確定生成多項式為：已確定生成多項式為： G G（X X）=X=X3 3+X+1= 1011+X+1= 1011被傳輸?shù)男畔⒈粋鬏數(shù)男畔(x)=1001C(x)=1001，求，求C(x)C(x)的的CRCCRC碼。碼。解：解：C C（x x）左移）左移 r = nk = 3 r = nk = 3 位位 即即 將上式模將上式模2 2采用除法采用除法 除以給定的除以給定的 G(x)=1011G(x)=1011：1001000/1011=1010+110/10111001000/1011=1010+110/1011 得到余數(shù)表達式：得到余數(shù)表達式：R(x) =110 R(x) =110 所求所求CRCCRC碼：碼：1001000210012)(3rxC10011101101001000)(2)(3xRxC計算機組成原理計算機組成原理 110 1011 1000 1011 101010010001011 1