2019/7/19,1,第2章 數據的表示和運算,2.1 數制與編碼 2.2 定點數的表示和運算 2.3 浮點數的表示和運算 2.4 算術邏輯單元ALU,2019/7/19,2,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 當使用匯編語言或者高級語言編寫程序時，一般都采用十進制形式；有時出于某種需要也采用十六進制形式或者二進制形式來表示。但是在計算機內部，數據的表示、存儲和運算均采用二進制形式。 進位計數制：又稱為數制，即按進位制的原則進行計數。數制由兩大要素組成：基數R和各數位的權W。基數R決定了數制中各數位上允許出現的數碼個數，基數為R的數制稱為R進制數。權W則表明該數位上的數碼所表示的單位數值的大小，權W與數位的位置有關。 計算機中常用的進位計數制有二進制、八進制、十進制和十六進制。,2019/7/19,3,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 假設 任意數值N 用 R進制數 來表示，表示形式為n+k個自左向右排列的符號來表示： N=(Dn-1Dn-2D0 .D-1D-2D-k)R 式中Di(-kin-1)為該數制采用的基本符號，可取值0, 1, 2, , R-1，小數點隱含在D0與D-1之間，整數部分有n位，小數部分有k位，數值N的實際值為：,2019/7/19,4,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 十進制(Decimal) ：基數為10，允許使用的數字有10個（0-9）。主要特點是逢十進一。任意一個十進制數可以表示為：,例如十進制數135.26可以表示為：,2019/7/19,5,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 二進制(Binary) ：基數為2，可使用的數字只有0和1，逢二進一。任意一個二進制數可以表示為 ：,例如二進制數(1100.1011)2可以表示為：,6,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 計算機中數據主要以二進制數的形式存儲，原因有以下幾點 ： 二進制數易于表示，比較容易找到具有二值狀態的物理器件來表示數據和實現存儲。比如脈沖有無、電壓高低等。 二進制數運算規則簡單，運算過程中的輸入狀態和輸出狀態較少，便于使用電子器件和線路加以實現。 二進制數的0和1與邏輯推理中的“真”和“假”相對應，為實現邏輯運算和邏輯判斷提供了便利。,2019/7/19,7,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 八進制(Octal) ：基數為8，可使用的數字有0-7，逢八進一。任意一個八進制數可以表示為 ：,十六進制(Hexadecimal) ：基數為16，可使用的數碼有0-9和A-F(代表10-15)，逢十六進一。任意一個十六進制數可表示為 ：,2019/7/19,8,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 非十進制轉化為十進制 ：非十進制數轉為十進制數時將非十進制數按權展開，然后求和。 【例2.1】將下列非十進制數轉化為十進制。, (1207)8=183282081780=512+128+0+7=(647)10 (A7)16=(10161+7160)10=(160+7)10=(167)10,2019/7/19,9,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 十進制轉化為非十進制 ：十進制數轉換為非十進制數時需將十進制數整數部分和小數部分分別轉換，再將結果寫到一起。 十進制整數轉換為非十進制整數：除R取余法。十進制整數不斷除以R，直至商為0。每除一次取一個余數，從低位排向高位。,例：208轉換成十六進制數 (208)10 = (D0)16 16 208 余 0 16 13 余 13 = DH 0,2019/7/19,10,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 十進小數轉換為非十進制小數：乘R取整法。用轉換進制的基數乘以小數部分，直至小數為0或達到轉換精度要求的位數。每乘一次取一次整數，從最高位排到最低位。,例：0.625轉換成二進制數 0.625 2 1.25 1 (b-1) 0.25 2 0.50 0 (b-2) 0.50 2 1.00 1 (b-3),所以(0.625)10 = (0.101)2,2019/7/19,11,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 【例2.2】將(12.6875)10轉化為二進制數。,整數部分(12)10=(1100)2,2019/7/19,12,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 【例2.2】將(12.6875)10轉化為二進制數。,小數部分(0.6875)10=(0.1011)2. 所以(12.6875)10=(1100.1011)2,2019/7/19,13,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 【課堂練習】將(105.3125)10轉化為二進制數。,(105.3125)10=(1101001.0101)2,2019/7/19,14,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 二進制、八進制與十六進制的轉換： 3位二進制數組成1位八進制數，4位二進制數組成1位十六進制數 二進制轉換為八進制：從小數點開始，向兩邊每3位為一組，整數部分不足3位在前面補“0”，小數部分不足3位在后面補“0”。 八進制轉換為二進制：過程相反，每一位八進制數轉換為3位二進制編碼。 二進制轉換為十六進制：從小數點開始，向兩邊每4位為一組，整數部分不足4位在前面補“0”，小數部分不足4位在后面補“0”。 十六進制轉換為二進制：只需將每一位十六進制數寫成它的4位二進制編碼即可。 八進制與十六進制的轉換先轉換成二進制，然后再轉換為所求的進制數,2019/7/19,15,2.1 數制與編碼 2.1.1 進位計數制及其相互轉換 【例2.3】將(11011.11001)2轉化為八進制、十六進制，將(751)8轉化為十六進制。,(11011.11001)2=(011 011.110 010)2=(33.62)8 (11011.11001)2=(0001 1011.1100 1000)2=(1B.C8)16 (751)8=(111 101 001)2=(0001 1110 1001)2=(1 E 9)16,2019/7/19,16,2.1 數制與編碼 2.1.2 真值和機器數 計算機中的數據可分兩類：無符號數和有符號數。 無符號數：即沒有符號的數，在寄存器中的每一位均可存放數值。 有符號數：即帶有符號的數，存放時需要留出位置存放符號。符號“正”、“負”需要數字化，一般用“0”表示正號，用“1”表示負號，并將它放在有效數字前面。 機器數：符號“數字化”的數 真 值：帶“+”或“-”符號的數 例如，真值是+0.11001，機器數為0.11001；真值為0.11001，機器數為1.11001,2019/7/19,17,2.1 數制與編碼 2.1.3 BCD碼 BCD碼: 使用二進制數編碼來表示十進制數的方法，又叫做二-十進制碼。一般用4位二進制編碼來表示一個十進制數。 常用的BCD碼分為有權碼和無權碼。 有權碼: 每一位都有固定的權值，加權求和的值即為它所表示的十進制數。常用的有權碼有8421碼、2421碼、5211碼等，8421碼的4位二進制數的權從高到低依次是8、4、2、1。一般提到的BCD碼就是指8421碼。這種編碼的優點是這4位二進制數之間滿足二進制的進位規則。,2019/7/19,18,2.1 數制與編碼 2.1.3 BCD碼 在計算機內部實現BCD碼算術運算，要對運算結果進行修正。 BCD碼加法運算修正規則：如果兩個一位BCD碼相加之和小于或等于(1001)2，即(9)10，不需修正；如相加之和大于或等于(10)10，要進行加6修正，并向高位進位，進位可在首次相加或修正時產生。 例如 1+8=9 4+9=13 7+9=16 0 0 0 1 0 1 0 0 0 1 1 1 + 1 0 0 0 + 1 0 0 1 + 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 不需修正 加6修正 加6修正,2019/7/19,19,2.1 數制與編碼 2.1.3 BCD碼 其它幾種有權碼： 2421、5211、4311碼都采用4位有權的二進制碼表示1個十進制數，但這4位二進制之間不符合二進制規則。這幾種有權碼有一特點：任何兩個相加之和等于(9)10的二進制碼互為反碼。 如2421碼中，0(0000)與9(1111)、1(0001)與8(1110)，互為反碼。 表 2.1給出了十進制數的幾種常見的4位有權碼。,2019/7/19,20,2.1 數制與編碼 2.1.3 BCD碼,表2.1 4位有權碼,2019/7/19,21,2.1 數制與編碼 2.1.3 BCD碼 無權碼： 4位二進制編碼的每一位沒有固定的權。在采用的無權碼的一些方案中，采用的比較多的是余3碼，格雷碼 余3碼：把原二進制的每個代碼都加0011值得到的。優點是執行十進制數位相加時，能正確產生進位信號，還給減法運算帶來了方便。余3碼的執行加法運算的規則：當兩個余3碼相加不產生進位時，應從結果中減去0011；產生進位時，應將進位信號送入高位余3碼，同時本位加0011的修正操作。 格雷碼：它的任何兩個相鄰的編碼之間只有1個二進制位的狀態不同，其余3個二進制位必須具有相同狀態。優點：從一個編碼變成下一個相鄰編碼時，只有1位的狀態發生變化，有利于得到更好的譯碼波形，在模擬/數字轉換的電路中得到更好的運行結果。,2019/7/19,22,2.1 數制與編碼 2.1.3 BCD碼,表2.2 4位無權碼,2019/7/19,23,2.1 數制與編碼 2.1.4 字符和字符串 字符：字母、數碼、運算符號、標點符號等，漢字也屬于字符。使用計算機的過程必然要涉及字符。由于計算機只能識別0和1兩種數碼，所以字符也應采用二進制編碼。 目前經常用的是美國國家信息交換標準字符碼，簡稱ASCII(American Standard Code for Information Interchange)碼。 ASCII碼: 7位二進制代碼表示一個字符，稱為標準或基本ASCII碼，如表 2.3所示。,2019/7/19,24,高位b6b5b4,低位b3b2b1b0,7位ASCII碼編碼表,2019/7/19,25,2.1 數制與編碼 2.1.4 字符和字符串 標準ASCII碼：有128種的組合，每種組合可代表一個字符。包括所有大寫和小寫字母，數字 0 到 9、標點符號，及在美式英語中使用的特殊控制字符。 擴充ASCII碼: 在標準ASCII碼前面增加一個二進制位，用8位二進制數來給字符編碼。共有256種組合，可給256個字符編碼。前128個字符的最高位為0，用于表示標準ASCII碼。后128個字符的最高位為1，用于表示128種特殊符號，如制表符等。,2019/7/19,26,2.1 數制與編碼 2.1.4 字符和字符串 漢字編碼：計算機的漢字處理技術必須解決3個問題：漢字的輸入、存儲與交換和漢字的輸出，它們分別對應于漢字的輸入碼、內碼、交換碼和字形碼。 漢字輸入碼: 將漢字輸入到計算機中多用的編碼。 數字輸入法：對每個漢字采用一個數字串進行編碼，例如區位碼、國標碼等。優點是無重復碼，缺點是難以記憶。 字形分解法：將漢字按其規則和筆畫劃分成若干部件，用字母或者數字進行編碼。如五筆字型輸入法、鄭碼輸入法等。 拼音輸入法：是以漢字拼音為基礎的輸入方法。如全拼輸入法、智能ABC輸入法等。優點是無須記憶，缺點是重碼率較高。 音形輸入法：利用拼音輸入法和字形分解法的各自優點，兼顧漢字的音和形，將兩者混合使用。如自然碼輸入法。,2019/7/19,27,2.1 數制與編碼 2.1.4 字符和字符串 漢字內碼：是計算機系統內部處理、存儲漢字所使用的統一代碼，一般采用兩個字節表示一個漢字。漢字的輸入碼可以有多種，但內碼在計算機中是唯一的。 漢字交換碼：不同的具有漢字處理功能的計算機系統之間在交換漢字信息時所用的代碼標準。目前常用的是國標碼，即國家標準化信息用漢字編碼。國標漢字共有6763個，分兩級，一級漢字為常用漢字，共3755個；二級漢字是非常用漢字，共3008個。每個漢字對應4位十六進制數（兩個字節）。,2019/7/19,28,2.1 數制與編碼 2.1.4 字符和字符串 漢字字形碼：目前的漢字處理系統中，字形信息的表示可以分為兩大類：一類是用活字或文字版的母體字形形式，另一類是用點陣表示法、矢量表示法等形式，其中最基本應用最廣泛的是后者。,2019/7/19,29,2.1 數制與編碼 2.1.4 字符和字符串 字符串：連續的一串字符, 通常方式下, 它們占用主存中連續的多個字節, 每個字節存一個字符。 當主存字由2個或4個字節組成時, 在同一個主存字中, 既可以按從低位字節向高位字節的順序存放字符串的內容, 也可以按從高位字節向低位字節的次序順序存放字符串的內容。這兩種存放方式都是常用方式。 如，1F AB THEN READ (C) 就可有兩種不同存放方式。假定每個主存字由4個字節組成, 圖 2.1(a) 是按從高位字節向低位字符的次序存放, 圖 2.1 (b) 按從低位字節向高位字節的次序存放。主存中每個字節存放的是相應字符的ASCII編碼值。,2019/7/19,30,2.1 數制與編碼 2.1.4 字符和字符串,(a) (b),2019/7/19,31,2.1 數制與編碼 2.1.5 數據校驗碼 計算機系統中的數據，在讀寫、存取和傳送的過程中可能產生錯誤（隨機錯誤或突發錯誤）。 為減少和避免這類錯誤，一方面精心設計各種電路，提高計算機硬件的可靠性；另一方面是在數據編碼上找出路，即采用某種編碼法，通過少量附加電路，使之能發現某些錯誤，甚至能確定出錯位置，進而實現自動改錯的能力。,2019/7/19,32,2.1 數制與編碼 2.1.5 數據校驗碼 數據校驗碼是一種常用的帶有發現某些錯誤或自動改錯能力的數據編碼方法。 實現原理：加進一些冗余碼，使合法數據編碼出現某些錯誤時，就成為非法編碼。這樣就可以通過檢測編碼的合法性來達到發現錯誤的目的。 碼距：一個編碼系統中任意兩個合法編碼（碼字）之間不同的二進數位（bit）數叫這兩個碼字的碼距，而整個編碼系統中任意兩個碼字的最小距離就是該編碼系統的碼距。,2019/7/19,33,2.1 數制與編碼 2.1.5 數據校驗碼 圖2.4所示編碼系統，用三個bit表示8個碼字。兩個碼字之間不同的bit數最少為1，故該系統碼距為1。如任何碼字中一位或多位被顛倒，這個碼字不能與其它有效信息區分開。如傳送信息001，而被誤收為011，因011仍是合法碼字，接收機將認為011是正確信息。,圖 2.4 用三個bit來表示8個碼字,2019/7/19,34,2.1 數制與編碼 2.1.5 數據校驗碼 圖2.5所示編碼系統，用4個bit表示8個碼字，碼字間的最小距離增加到2，碼距為2。8個碼字相互間最少有兩bit的差異。如果任何信息的一個數位被顛倒，就成為一個非法碼字。如信息是1001，誤收為1011，接收機知道發生了一個差錯，因為1011不是一個合法碼字。但差錯不能被糾正，偶數個差錯也無法發現。,圖 2.5 用4個bit來表示8個碼字,2019/7/19,35,2.1 數制與編碼 2.1.5 數據校驗碼 為使一個系統能檢查和糾正一個差錯，碼間最小距離必須至少是“3”。最小距離為3時，或能糾正一個錯，或能檢二個錯，但不能同時糾一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進一步提高需要進一步增加碼字間的最小距離。表2.6概括了最小距離為1至7的碼的糾錯和檢錯能力。 常用的數據校驗碼：奇偶校驗碼、 海明校驗碼、循環冗余校驗碼,2019/7/19,36,2.1 數制與編碼 2.1.5 數據校驗碼-奇偶校驗碼 奇偶校驗碼：奇偶檢驗碼是一種最簡單、最直觀、應用最廣泛的檢錯碼，它的碼距為2，因此它只能檢出一位錯。 實現方法：由若干位有效信息(如1個字節)，再加上1個二進制位(校驗位)組成校驗碼。檢驗位的取值(0或1)將使整個校驗碼中“1”的個數為奇數或偶數。當校驗位的取值使整個校驗碼中“1”的個數為奇數時，稱為奇校驗；當“1”的個數為偶數時為偶校驗。 奇偶校驗的編碼和檢驗的電路：常見的有并行奇偶統計電路，如圖2.2所示。,2019/7/19,37,PO = D1 D2 D3 D4 D5 D6 D7 D8,2.1 數制與編碼 2.1.5 數據校驗碼-奇偶校驗碼,圖 2.2 奇偶校驗位的形成及檢驗電路,=,2019/7/19,38,2.1 數制與編碼 2.1.5 數據校驗碼-奇偶校驗碼 下面以奇校驗為例說明對主存信息進行奇偶校驗的全過程： 校驗位形成: 當要把一個字節的代碼D7D0寫入主存時，就將它們送往奇偶校驗邏輯電路，該電路產生的“奇形成”信號就是校驗位。它將與8位代碼一起作為奇校驗碼寫入主存。若D7D0中有偶數個“1”，則“奇形成”=1，若D7D0中有奇數個“1”，則“奇形成”=0。 校驗檢測: 校驗檢測是將讀出的9位代碼(8位信息位和1位校驗位)同時送入奇偶校驗電路檢測。若讀出代碼沒有錯誤，則“奇校驗出錯”=0；若讀出代碼中的某一位上出現錯誤，則“奇校驗出錯”=1，表示這個9位代碼中一定有某一位出現了錯誤，但是具體的錯誤位置是不能確定的。,2019/7/19,39,2.1 數制與編碼 2.1.5 數據校驗碼-奇偶校驗碼 水平垂直奇偶校驗碼：實際工作中還經常采用縱橫都加校驗奇偶校驗位的編碼系統水平垂直奇偶校驗碼。 考慮傳輸若干個長度為m位的信息。如果把這些信息編成每組n個信息的分組，則在這些不同的信息間，也能夠作奇偶校驗。下圖中n個信息的一個分組排列成矩陣式樣，并以水平奇偶（HP）及垂直奇偶（VP）的形式編出奇偶校驗位。,2019/7/19,40,2.1 數制與編碼 【例】(2001年程序員試題) ：由 6 個字符的 7 位 ASCII 編碼排列，加上水平垂直奇偶校驗位構成下列矩陣（最后一列為水平奇偶校驗位，最后一行為垂直奇偶校驗位），則：,X1 X2 X3 X4 處比特分別為？ X5 X6 X7 X8 處比特分別為？ X9 X10 XI1 X12 處比特分別為？ Y1 和 Y2 處的字符分別為？,0,1,1,1,0,0,0,1,1,1,1,0,2019/7/19,41,2.1 數制與編碼 【解】從ASCII碼左起第5列可知垂直為偶校驗。則： 從第1列可知X4=0；從第3行可知水平也是偶校驗。 從第2行可知X3=1；從第7列可知X8=0；從第8列可知X12=1； 從第6列可知X10=0；從第6行可知X9=1；從第2列可知X1=1； 從第1行可知X2=1；從第3列可知X5=1；從第4行可知X6=0； 從第4列（或第5行）可知X7=0；從第7行可知X11=1； 整理一下： X1X2X3X4 = 1110 ， X5X6X7X8 = 1000 X9X10X11X12 = 1011 由字符Y1的ASCII碼1001001=49H知道，Y1即是“I”（由“D”的ASCII碼是1000100=44H推得） 由字符Y2的ASCII碼0110111=37H知道，Y2即是“7”（由“3”的ASCII碼是0110011=33H推得） 假如你能記住“0”的ASCII碼是0110000=30H；“A”的ASCII碼是1000001=41H，則解起來就更方便了,2019/7/19,42,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 這是由Richard Hamming于1950年提出的、目前還被廣泛采用在網絡傳輸等領域。 實現原理：在有效信息位中加入幾個校驗位形成海明碼，使碼距比較均勻的拉大，并把數據的每一個二進制位分配在幾個奇偶校驗組中。當某一位出錯后，就會引起有關的幾個校驗組的值發生變化，這不但可以發現出錯，還能指出是哪一位出錯，為自動糾錯提供了依據。,2019/7/19,43,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 假設校驗位的個數為r，則它能表示2r個信息，用其中的一個信息指出“沒有錯誤”，其余的2r-1個信息指出錯誤發生在哪一位。然而錯誤也可能發生在校驗位，因此只有k=2r-1-r個信息能用于糾正被傳送數據的位數，也就是說要滿足關系。 2rk+r+1 (2.10) 如要能檢測與自動校正一位錯，并發現兩位錯，則應在前一條件下再增加1位總校驗位，此時校驗位的位數r和數據位的位數k應滿足下述關系： 2r-1k+r (2.11) 。,2019/7/19,44,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 可計算出數據位k與校驗位r的對應關系，如表2.7所示。,2019/7/19,45,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 海明碼的編碼規律：數據位k位，校驗位r位，假設海明碼的最高位號為m，最低位號為1，即HmHm-1H2H1 (1) 校驗位與數據位之和為m，每個校驗位Pi在海明碼中被分在位號2i-1的位置，其余各位為數據位，并按從低向高逐位依次排列的關系分配各數據位。 (2) 海明碼的每一位碼Hi(包括數據位和校驗位本身)由多個校驗位校驗，其關系是被校驗的每一位位號要等于校驗它的各校驗位的位號之和。以便校驗的結果能正確反映出出錯位的位號。,2019/7/19,46,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 例如: 校驗位r=5，用P1-P5表示，數據位k=8，用D1-D8表示，5個校驗位P5P1對應的海明碼位號應分別為H13，H8，H4，H2和H1。P5只能放在H13一位上，它已經是海明碼的最高位了，其他4位滿足Pi的位號等于2i-1的關系。其余為數據位Di，則有如下排列關系：P5D8D7D6D5P4D4D3D2P3D1P2P1 按照海明碼的編碼規律，每個海明碼的位號要等于參與檢驗它的幾個檢驗位的位號之和的關系，可以給出如表2.8所示的結果,2019/7/19,47,表2.8 出錯的海明碼位號和校驗位位號的關系,2019/7/19,48,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 由有關數據位形成Pi值的偶校驗的結果: P1 =D1 D2 D4 D5 D7 P2 =D1 D3 D4 D6 D7 P3 =D2 D3 D4 D8 P4 =D5 D6 D7 D8 若要分清是兩位出錯還是一位出錯，還要補充一位P5總校驗位 P5 =D1 D2 D3 D4 D5 D6 D7 D8 P4 P3 P2 P1 每一位數據位，都至少出現在3個Pi值的形成關系中。當任一位數據碼發生變化時，必將引起3個或4個Pi值跟著變化，該海明碼的碼距為4。,2019/7/19,49,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 按如下關系對所得到的海明碼實現偶校驗: S1 = P1 D1 D2 D4 D5 D7 S2 = P2 D1 D3 D4 D6 D7 S3 = P3 D2 D3 D4 D8 S4 = P4 D5 D6 D7 D8 S5 = P5 P4 P3 P2 P1 D1 D2 D3 D4 D5 D6 D7 D8 校驗得到的結果值S5 S1能反應13位海明碼的出錯情況 任何奇數個數出錯， S5一定為1 任何偶數個數出錯， S5一定為0 圖3.11是H=12，數據位k=8，校驗位r=4的海明校驗線路，記作(12，8)分組碼。,2019/7/19,50,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 圖2.3是H=12，數據位k=8，校驗位r=4的海明校驗線路，記作(12，8)分組碼。 圖中，H12 , H11, , H1是被校驗碼， D8 , D7, , D1是糾正后的數據， S4 , S3, S2, S1是用奇偶形成線路得到的。 若S4 S1全0，說明代碼無錯；若為1100或1011，則分別表示H12 或 H11有錯，通過相關譯碼線經異或電路糾正該位。,2019/7/19,51,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼,圖2.3 (12，8)分組碼海明校驗線路,2019/7/19,52,2.1 數制與編碼 2.1.5 數據校驗碼-海明校驗碼 假如要進一步判別是1位錯還是2位錯，則再增加一個校驗位。并用圖2.4來取代圖2.3虛框中的內容，此時增加了一個奇偶形成線路S5。 如為一位錯，仍按圖2.3來糾正數據位；如為兩位錯，則無法糾正錯誤。,圖2.4 判1位/2位錯的附加線路,2019/7/19,53,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC(cyclic redundancy check)碼可以發現并糾正信息存儲或傳送過程中連續出現的多位錯誤，在磁介質存儲和計算機之間通信方面得到廣泛應用; 在數據存儲和數據通訊領域，CRC應用廣泛: 著名通訊協議X.25的FCS(幀檢錯序列)采用CRC. CCITT，ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤驅動器的讀寫采用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。歐洲交換機都使用CRC4。,2019/7/19,54,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC碼是基于模2運算而建立編碼規律的校驗碼; 模2運算特點：運算不考慮進位和借位，規則如下： 模2加和模2減規則相同，按位異或，相同得0，不同得1。即：00=0，01=1，10=1，11=0。 模2乘時按模2加求部分積之和。 模2除是按模2減求部分余數。每求一位商應使部分余數減少一位。上商規則是：當部分余數的首位為1時，商取1，當部分余數的首位為0時，商取0；當部分余數的位數小于除數位數時，該余數即為最后余數。,2019/7/19,55,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 模2乘例子： 模2除例子：,2019/7/19,56,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC碼基本原理是：在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫（N，K）碼。對于一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式; CRC碼的關鍵是如何從K位信息位簡便地得到r位校驗位(編碼)，及如何從K+R位信息碼判斷是否出錯。,2019/7/19,57,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC碼的編碼方法： 將待編碼的k位有效信息位組表達為多項式M(x)： M(x)=Ck-1xk-1+Ck-2xk-2+Cixi+C1x+C0 將信息位組左移r位，則可表示為多項式M(x)xr。可空出r位，以便拼接r位校驗位 。 CRC碼用多項式M(x)xr除以G(x)(生成多項式)所得余數作為校驗位。為了得到r位余數(校驗位)，G(x)必須是r+1位。 設所得余數表達為R(x)，商為Q(x)。將余數拼接在信息位組左移空出的r位上，構成有效信息的CRC碼。多項式表達為： M(x) xr +R(x)=Q(x)G(x)+R(x)+R(x) =Q(x)G(x)+R(x)+R(x)=Q(x)G(x),2019/7/19,58,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC碼的編碼方法： 因此所得CRC碼可被G(x)表示的數碼除盡。 如果CRC碼在傳輸過程中不出錯，其余數必為0； 如果傳輸過程中出錯，則余數不為0，由余數指出哪一位出錯，即可糾正。,2019/7/19,59,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 【例2.4】已知有效信息為011，試用生成多項式為G(x)=10111將其編碼。 解：有效信息M(x)=011=x+1，n=3 由G(x)=10111=x4+x2+x+1 得k+1=5，k=4 將有效信息左移4位后再被G(x)模2除，即M(x)x4=x5+x4 對應的代碼為0110000，用G(x)的二進制編碼10111來除，如下： 所以，M(x)x4+R(x)=0110000+1001=0111001為CRC碼。 總信息位為7位，有效信息位為3位，上述0111001碼稱(7，3)碼,2019/7/19,60,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 【課堂練習】對4位有效信息(1100)求循環校驗編碼，選擇生成多項式(1011) 。 解： M(x)=x3+x2=1100 (k=4) M(x)x3=x6+x5=1100000 (左移r=3位) G(x)=x3+x+1=1011 (r+1=4位) M(x)x3/G(x)=1100000/1011=1110+010/1011 (模2除) M(x)x3+R(x)=1100000+010=1100010 (模2加) 將編好的循環校驗碼稱為(7，4)碼，即n=7,k=4。,練習：假設使用的生成多項式是G(x)=x3+x+1。4位的原始報文為1010，求編碼后的報文。（答案 A: 1010011 ）,2019/7/19,61,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 CRC碼的譯碼與糾錯：將收到的循環冗余碼用生成多項式G(X)去除。若無錯，則余數為0; 若某位出錯，余數不為0。不同出錯位余數不同。表 2.9為(7,3)碼對應G(X)=10111的出錯模式。,2019/7/19,62,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 從表 2.9可以看出，更換不同的待測碼字，余數和出錯位的對應關系不變，只與碼制和生成多項式有關。余數的不同，可以確定出錯位數。 例如，CRC碼字0111001在傳輸過程中若無差錯，接收端用G(X)=10111去除，余數為0；如果在傳輸過程中有差錯，在接收端變成了0111000，用G(X)=10111去除，余數不為0，等于0001，查表 2.9就可找出出錯位為A7 。,2019/7/19,63,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 如果循環碼有一位出錯，被G(x)模2除將得到一個不為0的余數。如果余數補0繼續除下去，將發現各次所得余數將按表 2.9順序循環。 例如，第7位出錯，余數為0001，補0后繼續模2除，第二次余數為0010，以后依次為0100，1000.反復循環，這就是“循環碼”名稱的由來。 該特點便于對糾錯電路的設計。即當出現不為零的余數后，一方面余數補0繼續操作，另一方面將被檢測的校驗碼字循環左移。,2019/7/19,64,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 由表2.9可知，當出現余數為1011時，出錯位為A1，取反糾正A1，然后繼續循環左移7次，即得到一個經過糾正的CRC碼。 需要指出的是，并不是任何一個(k+1)位多項式都可以作為生成多項式。從檢錯和糾錯的要求出發，生成多項式應滿足以下要求： 任何一位發生錯誤，都應該使余數不為零。 不同位發生錯誤應使余數不同。 對余數繼續做模2除，應使余數循環,2019/7/19,65,2.1 數制與編碼 2.1.5 數據校驗碼-循環冗余校驗碼 常用生成多項式： 名稱 生成多項式 標準引用 CRC-4 x4+x+1 ITU G.704 (國際電信聯盟 ) CRC-4 x4+x2+x+1 CRC-8 x8+x5+x4+1 CRC-8 x8+x2+x1+1 CRC-8 x8+x6+x4+x3+x2+x1 CRC-12 x12+x11+x3+x+1 CRC-16 x16+x15+x2+1 IBM SDLC CRC16-CCITT x16+x12+x5+1 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32 x32+x26+x23+.+x2+x+1 DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS,2019/7/19,66,2.2 定點數的表示和運算 2.2.1定點數的表示 計算機進行算術運算時，需要指出小數點的位置。在計算機中根據小數點的位置是否固定可以分為定點數和浮點數兩種數據格式。 在定點數中小數點的位置固定不變。通常，把小數點固定在數位的最前面或末尾，所以定點數可以分為定點小數和定點整數兩類。 根據符號的有無，定點數又分為無符號數和有符號數兩類。,2019/7/19,67,2.2 定點數的表示和運算 2.2.1定點數的表示 無符號數：沒有符號的數，數值的每一位均用來存放數值。 有符號數：帶有符號的數，存儲時需留出位置存放符號。 在機器字長相同時，無符號數與有符號數所對應的數值范圍是不同。以機器字長為16位為例，無符號數的表示范圍為065535，而有符號數的表示范圍為-32768+32767(用補碼表示)。,2019/7/19,68,2.2 定點數的表示和運算 2.2.1定點數的表示 有符號數的表示：在計算機中，常采用機器數來表示數據。常用的有原碼、反碼、補碼、移碼等。 （1）原碼表示法：是一種比較直觀的表示方法，其符號位表示該數的符號，“+”用“0”表示，“-”用“1”表示，而數值部分仍保留著其真值的特征。,2019/7/19,69,2.2 定點數的表示和運算 2.2.1定點數的表示 （1）原碼表示法： 定點小數的原碼形式為x0.x1x2xn，原碼定義是：,式中x是真值 【例2.5】 x=+0.1001,則x原=0.1001 x =-0.1001,則x原=1-(-0.1001)=1+0.1001=1.1001,2019/7/19,70,2.2 定點數的表示和運算 2.2.1定點數的表示 （1）原碼表示法： 定點整數的原碼形式為x0x1x2xn ，原碼定義是：,式中x是真值， n是整數位數 【例2.6】 x=+1001, 則x原=01001 x=-1001, 則x原=24-(-1001)=24+1001=11001,2019/7/19,71,2.2 定點數的表示和運算 2.2.1定點數的表示 （1）原碼表示法： 原碼表示法有兩個特點： (1)零的表示有“+ 0”和“- 0”之分，故有兩種形式： +0原=0.000；-0原=1.000 (2)符號位 x0的取值由下式決定： 其中x是真值。,2019/7/19,72,2.2 定點數的表示和運算 2.2.1定點數的表示 （1）原碼表示法： 原碼表示法的優點: 比較直觀、簡單易懂; 最大缺點: 加減法運算復雜。例如，當兩數相加時，先要判別兩數的符號，如果兩數是同號，則相加；兩數是異號，則相減。而進行減法運算又要先比較兩數絕對值的大小，再用大絕對值減去小絕對值，最后還要確定運算結果的正負號。符號位不能直接參與運算！ 后面介紹的補碼可解決原碼的缺點。,2019/7/19,73,2.2 定點數的表示和運算 2.2.1定點數的表示 （2）補碼表示法： 定點小數的補碼形式為x0.x1x2xn ，則補碼定義：,【例2.7】 x=+0.1001,則x補=0.1001 x =-0.1001,則x補= 10.0000+(-0.1001)=1.0111 x=0，則+0.0000補=0.0000 -0.0000補=2+(-0.0000)=10.00000-0.0000=0.0000,式中x是真值,補碼中的“零”只有一種表示形式,2019/7/19,74,2.2 定點數的表示和運算 2.2.1定點數的表示 （2）補碼表示法： 對于小數，若x=-1，則根據小數補碼定義， 有 x補=2+X=10.0000-1.0000=1.0000。 可見，-1本不屬于小數范圍，但卻有-1補存在. 這是由于補碼中的零只有一種表示形式，故它比 原碼能多表示一個“-1”,2019/7/19,75,2.2 定點數的表示和運算 2.2.1定點數的表示 （2）補碼表示法： 定點整數x0x1x2xn ，則補碼定義：,【例2.8】 x= +1001,則x補01001 x= -1001,則 x補25+(-1001) 100000-1001=10111,式中x是真值，n是整數位數,2019/7/19,76,2.2 定點數的表示和運算 2.2.1定點數的表示 （2）補碼表示法： 補碼表示法進行減法運算要比采用原碼形式簡單。 對于補碼來說，無論是正數還是負數，機器總是做加法運算。 根據補碼定義，求負數的補碼時要做一次減法運算。 從下面介紹的反碼表示法中可以獲得求負數補碼的簡便方法，解決負數的求補問題。,2019/7/19,77,2.2 定點數的表示和運算 2.2.1定點數的表示 （3）反碼表示法： 反碼表示法中，符號的表示法與原碼相同。 正數的反碼與正數的原碼形式相同；負數的反碼符號位為1，數值部分通過將負數原碼的數值部分各位取反(0變1，1變0)得到。,2019/7/19,78,2.2 定點數的表示和運算 2.2.1定點數的表示 （3）反碼表示法： 定點小數的反碼形式為x0.x1x2xn，反碼定義是：,式中x是真值，n是小數位數,【例2.9】 x=+0.0110，x反=0.0110 x =-0. 0110，x反=(2-2-4)+x=1.1111-0. 0110=1.1001,2019/7/19,79,2.2 定點數的表示和運算 2.2.1定點數的表示 （3）反碼表示法： 對于0，反碼有兩種表示形式，即 + 0反 = 0.0000 - 0反 = 1.1111,2019/7/19,80,2.2 定點數的表示和運算 2.2.1定點數的表示 （3）反碼表示法： 定點整數 x0x1xn， 反碼定義是：,式中x是真值，n是整數位數,【例2.10】 x=+1101，x反=01101 x =-1101，x反=(24+1-1)+x=11111-1101=10010,2019/7/19,81,2.2 定點數的表示和運算 2.2.1定點數的表示 （3）反碼表示法： 比較小數與整數的反碼與補碼的公式可得到： x補=x反+ 2-n (0x-1) x補=x反+ 1 (0x -2 -n) 若要求一個負數的補碼，其方法是符號位置 1，其余各位取反，然后在最末位上加 1。 在計算機中，當用串行電路按位將原碼轉換成補碼形式時(或反之)，經常采取以下方法：自低位開始轉換，從低位向高位，在遇到第1個“1”之前，保持各位的“0”不變，第1個“1”也不變，以后的各位按位取反，最后保持符號位不變，經歷一遍后，即可得到補碼。,2019/7/19,82,2.2 定點數的表示和運算 2.2.1定點數的表示 （4）移碼表示法： 移碼通常用于表示浮點數的階碼。階碼是n位的整數，假設定點整數移碼形式為x0x1x2 xn 時，移碼的定義是：,式中x是真值，n是整數位數 由移碼的定義式可知，對于同一個整數，其移碼與其補碼數值位完全相同，而符號位相反。,2019/7/19,83,2.2 定點數的表示和運算 2.2.1定點數的表示 【例2.11】 將十進制真值 x = -127 ,1,0,1,127分別表示為8位原碼、反碼、補碼、移碼值。,2019/7/19,84,2.2 定點數的表示和運算 2.2.2 定點數的運算 定點數的運算包括移位、加、減、乘、除幾種。 1移位運算 對十進制數據，小數點左移一位相當于數據縮小10倍，右移一位相當于數據放大10倍。 計算機中數據以二進制形式存儲，且小數點的位置是固定的，二進制表示的機器數在相對于小數點做n位左移或右移時，其實質是該數乘以或除以2n。 移位運算對計算機有很高的實用價值，用移位指令對數據進行放大或縮小，比乘除運算要快得多。,2019/7/19,85,2.2 定點數的表示和運算 2.2.2 定點數的運算 定點數的運算包括移位、加、減、乘、除幾種。 1移位運算 移位運算分為邏輯移位、算術移位和循環移位三種。 主要區別：符號位和移出的數據位的處理方法不同。與手工移位運算不同，計算機移位寄存器字長固定，當進行左移和右移時，寄存器最低位和最高位會出現空余位，最高位和最低位相應地也會被移出，對空出的空位應該填補0還是1，這與移位種類和機器數編碼方法有關。,2019/7/19,86,2.2 定點數的表示和運算 2.2.2 定點數的運算 邏輯移位 邏輯移位的對象是無符號數，移位結果只是數據各位在位置上發生了變化。 移位規則：邏輯左移時，高位移出，低位補0；邏輯右移時，低位移出，高位補0。移出數據位一般置入標志位C（進位/借位標志）。移位規則如圖 2.5所示 如寄存器內容為01010011，邏輯左移為10100110，邏輯右移為0010100。,圖 2.5 邏輯移位規則,2019/7/19,87,2.2 定點數的表示和運算 2.2.2 定點數的運算 算術移位 算術移位對象是帶符號數，移位結果是在數值的絕對值上進行放大或縮小，同時符號位須保持不變。 對原碼，算術左移，符號位不變, 高位移出, 低位補0；算術右移，符號位不變, 低位移出, 高位補0。 對補碼，算術左移，符號位不變，高位移出，低位補0。當左移移出的數據位正數為1，負數為0時發生溢出。因此，為保證補碼算術左移時不發生溢出，移位的數據最高有效位必須與符號位相同。,2019/7/19,88,2.2 定點數的表示和運算 2.2.2 定點數的運算 算術移位 算術右移時，符號位不變，低位移出，高位正數補0，負數補1。補碼的移碼規則如圖2.6所示。 反碼的算術移位規則：算術左移時，最高有效位移入符號位，低位正數補0，負數補1；算術右移時，符號位不變，高位補符號位，低位移出。,圖 2.6 補碼的算術移位規則規則,2019/7/19,89,2.2 定點數的表示和運算 2.2.2 定點數的運算 循環移位 循環移位是指所有的數據位在自身范圍內進行左移或者右移，左移時最高位移入最低位，右移時最低位移入最高位。 若與CF標志位