組成原理第二章(v11)2015

1、Confederal Confidential1主講教師：胡迪青、吳非主講教師：胡迪青、吳非e_mail: hudq024e_mail: QQ: QQ: 121374333 121374333 第二章第二章 計算機中的數(shù)據(jù)表示方法計算機中的數(shù)據(jù)表示方法Confederal Confidential2問題提出：問題提出： 1.計算機中數(shù)據(jù)如何表示？計算機中數(shù)據(jù)如何表示？ 2.研究數(shù)據(jù)表示的意義何在？研究數(shù)據(jù)表示的意義何在？（從程序設計和簡化運算器設計、增強系統(tǒng)可靠性等三個角度考慮（從程序設計和簡化運算器設計、增強系統(tǒng)可靠性等三個角度考慮）學習建議：學習建議： 1. 軟件軟件+硬件協(xié)同的全局觀；硬

2、件協(xié)同的全局觀；本章的主要知識點本章的主要知識點數(shù)據(jù)表示：定點和浮點數(shù)據(jù)表示格式（含浮點數(shù)的規(guī)格化）數(shù)據(jù)表示：定點和浮點數(shù)據(jù)表示格式（含浮點數(shù)的規(guī)格化）補碼中模的概念及應用、補碼與真值之間的關系補碼中模的概念及應用、補碼與真值之間的關系校驗的原理、作用和實現(xiàn)方法校驗的原理、作用和實現(xiàn)方法Confederal Confidential31)1)目的目的 組織數(shù)據(jù)，方便計算機硬件直接使用組織數(shù)據(jù)，方便計算機硬件直接使用 2)2)選擇數(shù)據(jù)格式要考慮的因素選擇數(shù)據(jù)格式要考慮的因素 數(shù)的類型數(shù)的類型 數(shù)的范圍數(shù)的范圍 數(shù)的精度數(shù)的精度 存儲和處理的代價存儲和處理的代價 是否有利于軟件的移植是否有利于軟件

3、的移植一、計算機內(nèi)的數(shù)據(jù)表示1.數(shù)據(jù)表示的目的和選擇數(shù)據(jù)格式要考慮的因素數(shù)據(jù)表示的目的和選擇數(shù)據(jù)格式要考慮的因素Confederal Confidential42、數(shù)的機器表示、數(shù)的機器表示1)真值：符號用真值：符號用“+”、“-”表示的數(shù)據(jù)表示方法。表示的數(shù)據(jù)表示方法。2)機器數(shù)：機器數(shù)：符號數(shù)值化的數(shù)據(jù)表示方法，符號數(shù)值化的數(shù)據(jù)表示方法，用用0、1表示符號。表示符號。3)設定點小數(shù)的形式為設定點小數(shù)的形式為X0.X1X2X3Xn X 1 X 01-X 0 X -1X原原 = X 1 X 0 2 + X - 2n 0 X -1X反反 =X補補=X 1 X 02 + X=2-|X| 0 X 1

4、mod 2一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential51) X= 0.1011 XX原原=1.1011 X=1.1011 X反反=1.0100 X=1.0100 X補補=1.0101=1.01012) X=+0.1011 2) X=+0.1011 X X原原= X= X反反= X= X補補= 0.1011= 0.10113)03)0的表示：的表示： +0+0原原 = 0.0000 -0= 0.0000 -0原原 =1.0000 =1.0000 +0 +0反反= 0.0000 -0= 0.0000 -0反反 =1.1111=1.1111 +0 +0補補= 0.0000=

5、-0= 0.0000=-0補補 例例1 1 求下列各數(shù)的原碼、補碼和反碼求下列各數(shù)的原碼、補碼和反碼一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential6原碼：原碼： a)a)表示簡單表示簡單 b)b)運算復雜：要設置加法、減法器。（分同號和異號）運算復雜：要設置加法、減法器。（分同號和異號） c)0c)0的表示不唯一的表示不唯一 4)幾種常見機器數(shù)的特點幾種常見機器數(shù)的特點反碼：反碼： a)a)表示相對原碼復雜表示相對原碼復雜 b)b)運算相對原碼簡單：符號位參加運算運算相對原碼簡單：符號位參加運算, , 只需要設置加法器。只需要設置加法器。 但符號位的進位位需要加到最低位但

6、符號位的進位位需要加到最低位 c)0c)0的表示不唯一的表示不唯一 補碼：補碼： a)a)表示相對復雜表示相對復雜 b)b)運算簡單：運算簡單：只需設置加法器只需設置加法器。 c)0c)0的表示唯一的表示唯一 如如 x反反=0.1101 ， Y反反 = 1.0101 求求 X+Y一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential7例例2 2 已知：已知： x = +0.1101 x = +0.1101 ， Y Y = -0.1010 = -0.1010 用反碼運算求用反碼運算求 X+YX+Y解：解： x反反= 0.1101 ， Y反反 = 1.0101X+Y = 0.0011

7、x反反 + Y反反 =0.11011.010110.0010+ 1 0.0011一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential8 5)補碼中模的概念補碼中模的概念 （符號位進位后所在位的權(quán)值）（符號位進位后所在位的權(quán)值） 設設XX補補= X= X0 0.X.X1 1X X2 2X X3 3XnXnXX補補= =X 1X 1 X X 0 02+X =2-|X|2+X =2-|X| 0 0 X X 11mod 2mod 2XX補補= =X 2X 2n n X X 1 12 2n+1n+1 + X = 2-|X| 0 + X = 2-|X| 0 X X 2 2n n mod 2

8、mod 2n+1n+1一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential9例例3 3 整數(shù)整數(shù) 1 1 用補碼表示，下列哪些用補碼表示，下列哪些( (個個) )結(jié)果是正確的？結(jié)果是正確的？ 1)1)1 11 2)1 2)1 111 3)11 3)1 1111 4)111 4)1 11111 5)1111 5)1 11111111111若整數(shù)若整數(shù)x x的補碼形式為的補碼形式為X X0 0X X1 1X X2 2X X3 3X X4 4X X5 5, ,則則-1-1的補碼又如何表示？的補碼又如何表示？ 模是多少？模是多少？解：依題意知：一個整數(shù)連同符號位在內(nèi)共有解：依題意知：一

9、個整數(shù)連同符號位在內(nèi)共有6 6位位 ， 則則-1-1補補= = 1 1 11111 11111 根據(jù)補碼的定義，其模為根據(jù)補碼的定義，其模為2 26 6一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential10 移碼表示浮點數(shù)的階碼，只有整數(shù)形式，如移碼表示浮點數(shù)的階碼，只有整數(shù)形式，如IEEE754IEEE754中階碼用移碼表示中階碼用移碼表示。 設定點整數(shù)設定點整數(shù)X X的移碼形式為的移碼形式為X X0 0X X1 1X X2 2X X3 3XXn n 則移碼的定義是：則移碼的定義是： XX移移= 2= 2n n + X 2+ X 2n n X X - - 2 2n n 具體

10、實現(xiàn)：數(shù)值位與具體實現(xiàn)：數(shù)值位與X X的補碼相同，符號位與補碼相反。的補碼相同，符號位與補碼相反。 例例4 4 X= +10101 X X= +10101 X補補= =0 010101 X10101 X移移= =1 11010110101 X= 10101 X X= 10101 X補補= =1 101011 X01011 X移移= =0 001011010116) 移碼（增碼）表移碼（增碼）表示示一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential11 例例5 5 將十進制值將十進制值X(-127X(-127，-1-1，0 0，1 1，127)127)用四種機器數(shù)表示用四種機器

11、數(shù)表示一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential121)1)定點數(shù)定點數(shù) 可表示定點小數(shù)和整數(shù)可表示定點小數(shù)和整數(shù) 表現(xiàn)形式：表現(xiàn)形式：X X0 0.X.X1 1X X2 2X X3 3X X4 4.X.Xn n定點小數(shù)定點小數(shù)定點整數(shù)定點整數(shù)定點小數(shù)的表示數(shù)的范圍：定點小數(shù)的表示數(shù)的范圍：1-21-2-n-n |x| |x| 2 2-n-n定點整數(shù)的表示數(shù)的范圍：定點整數(shù)的表示數(shù)的范圍：2 2n n-1 -1 |x| |x| 1 13.計算機中常用的兩種數(shù)值數(shù)據(jù)格式計算機中常用的兩種數(shù)值數(shù)據(jù)格式一、計算機內(nèi)的數(shù)據(jù)表示 定點數(shù)據(jù)表示的優(yōu)點與不足定點數(shù)據(jù)表示的優(yōu)點與不足

12、:格式固定、簡單、數(shù)據(jù)范圍受限格式固定、簡單、數(shù)據(jù)范圍受限Confederal Confidential13 浮點數(shù)的使用場合浮點數(shù)的使用場合當數(shù)的表示范圍超出了定點數(shù)能表示的范圍時。當數(shù)的表示范圍超出了定點數(shù)能表示的范圍時。(1)(1)格式格式( (一般格式一般格式) ) ESE1E2E3EnMSM1M2M3M4.MkE: E: 階碼位數(shù)，決定數(shù)據(jù)的范圍階碼位數(shù)，決定數(shù)據(jù)的范圍M: M: 尾數(shù)位數(shù)，決定數(shù)的精度尾數(shù)位數(shù)，決定數(shù)的精度2)2)浮點數(shù)浮點數(shù)把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。N=Rem一、計算機內(nèi)的數(shù)據(jù)表示Confederal

13、Confidential14(2)IEEE 754(2)IEEE 754格式格式 S S8 8位偏指數(shù)位偏指數(shù)E E2323位有效尾數(shù)位有效尾數(shù)M M單精度單精度1111位偏指數(shù)位偏指數(shù)E E5252位有效尾數(shù)位有效尾數(shù)M MS S雙精度雙精度 指數(shù)采用偏移值指數(shù)采用偏移值, ,其中單精度為其中單精度為127,127,雙精度為雙精度為10231023。從而所有浮點。從而所有浮點數(shù)的階碼值都可以變成非負整數(shù)數(shù)的階碼值都可以變成非負整數(shù), ,便于浮點數(shù)的比較和排序。便于浮點數(shù)的比較和排序。 IEEE754IEEE754尾數(shù)形式為尾數(shù)形式為1.XXXXXX,1.XXXXXX,其中其中M M部分保存的

14、是部分保存的是XXXXXXXXXXXX。這樣可。這樣可以保留更多的有效數(shù)字位以保留更多的有效數(shù)字位, ,進一步提高數(shù)據(jù)表示的精確度。進一步提高數(shù)據(jù)表示的精確度。一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential15與上述與上述IEEE754IEEE754格式相對應的格式相對應的3232位浮點數(shù)的真值可表示為位浮點數(shù)的真值可表示為: :N = (-1)N = (-1)S S 2 2 E-127E-127 1.M 1.M隨隨E E和和M M的取值不同，的取值不同，IEEE754IEEE754浮點數(shù)據(jù)表示具有不同的意義浮點數(shù)據(jù)表示具有不同的意義 E=0 , M =0 E=0 , M

15、 =0 ：表示機器零；：表示機器零； E=0 , M E=0 , M 0 0 ：則：則N = (-1)N = (-1)S S 2 2 -126-126 0.M, 0.M,非規(guī)格化的浮點數(shù)；非規(guī)格化的浮點數(shù)； 1 1 E E 254 254 ：N = (-1)N = (-1)S S 2 2 E-127E-127 1.M 1.M ，規(guī)格化的浮點數(shù)；，規(guī)格化的浮點數(shù)； E=255 , M =0 E=255 , M =0 ：無窮大的數(shù)，對應于：無窮大的數(shù)，對應于x / 0 x / 0（其中（其中x x 0 0）；）； E=255 , M E=255 , M 0 0 ：N= NaNN= NaN，表示一個

16、非數(shù)值，對應于，表示一個非數(shù)值，對應于0 / 00 / 0。一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential16一、計算機內(nèi)的數(shù)據(jù)表示Emax=2046,f=1.1111,1.111122046-1023 =21023(2-2-52) Emin=1, M=0, 1.021-1023 =2-1022 Emax=254, f=1.1111, 1.11112254-127 = 2127(2-2-23) Emin=1, M=0, 1.021-127 = 2-126 最大值最小值格式 Confederal Confidential17一、計算機內(nèi)的數(shù)據(jù)表示E=0,f=0.1111,0

17、.11112-1022 =2-1022(1-2-52) E=0, M=2-52, 2-522-1022 =2-1079E=0, f=0.1111, 0.11112-126 = 2-126(1-2-23) E=0, M=2-23, 2-232-126 = 2-149 最大值最小值格式 Confederal Confidential18一、計算機內(nèi)的數(shù)據(jù)表示浮點數(shù)的表示范圍與表示精度浮點數(shù)表示法可以擴大數(shù)值表示的范圍浮點數(shù)表示法未增加表示數(shù)值的個數(shù)絕對值越大，浮點數(shù)分布越稀疏階碼位數(shù)越多，數(shù)據(jù)表示的范圍就越大尾數(shù)位數(shù)越多，數(shù)據(jù)表示的精度越高02-1262-1252-1242-123-2-126Co

18、nfederal Confidential19一、計算機內(nèi)的數(shù)據(jù)表示main() double a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!=a) printf(nReally? 3.0!=a);3.000000,2?Really?3.0!=a二進制存儲浮點數(shù)不是精確數(shù)一個奇怪的程序Confederal Confidential20一、計算機內(nèi)的數(shù)據(jù)表示main() float a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); i

19、f (3.0!=a) printf(nYeah!);3.000000,2一個奇怪的程序Confederal Confidential21IEEE754 32位浮點數(shù)與對應真值之間的變換流程位浮點數(shù)與對應真值之間的變換流程一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential22例例5 5 將十進制數(shù)將十進制數(shù)20.5937520.59375轉(zhuǎn)換成轉(zhuǎn)換成3232位位IEEE754IEEE754格式浮點數(shù)的二進制格式浮點數(shù)的二進制格式來存儲。格式來存儲。解解: :先將十進制數(shù)換成二進制數(shù)：先將十進制數(shù)換成二進制數(shù)： 20.59375=10100.10011(20.59375=1010

20、0.10011(0.5+0.25+0.125+0.0625+0.031250.5+0.25+0.125+0.0625+0.03125) ) 移動小數(shù)點，使其變成移動小數(shù)點，使其變成1.M1.M的形式的形式 10100.10011=1.010010011 10100.10011=1.0100100112 24 4得到：得到： S=0, e = 4 S=0, e = 4，E= 100+01111111 =E= 100+01111111 =1000001110000011，M =M = 010010011010010011最后得到最后得到3232位浮點數(shù)的二進制存儲格式為：位浮點數(shù)的二進制存儲格式為

21、： 0 0100 0001100 0001 1 1010010 0100 1100 0000 0000 00000100 1100 0000 0000 0000= (41A4C000)= (41A4C000)1616一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential23例例6 6 若某浮點數(shù)若某浮點數(shù)x x的二進制存儲格式為的二進制存儲格式為(41360000)(41360000)1616 , ,求與其對應求與其對應的的3232位浮點表示的十進的值。位浮點表示的十進的值。解：解： (41360000)16 = (0100, 0001, 0011, 0110, 0000, 00

22、00, 0000, 0000)2 s=0 e=10000010-01111111=00000011=(3)10 1.M=1.011011 則上述浮點數(shù)對應的真值為則上述浮點數(shù)對應的真值為 X=(-1)X=(-1)0 0 (1.011011) (1.011011)2 23 3 =(11.375)=(11.375)1010 一、計算機內(nèi)的數(shù)據(jù)表示Confederal Confidential24 2. 檢驗碼的工作原理檢驗碼的工作原理 1. 問題的提出：問題的提出：檢測傳輸、處理和存儲中的錯誤。檢測傳輸、處理和存儲中的錯誤。檢檢測測器器編碼器編碼器 x x1 1 x x2 2 x x3 3 x x

23、4 4 1 11 11 11 11 11 10 00 00 00 01 1F FP P發(fā)送端發(fā)送端 接收端接收端 處處理理/傳傳輸輸3. 帶校驗信息的數(shù)據(jù)形式帶校驗信息的數(shù)據(jù)形式 沒有付出，就不會有收獲沒有付出，就不會有收獲二、校驗碼Confederal Confidential25 4.碼距的概念碼距的概念 將一組編碼中任何兩個合法編碼之間對應位上具有不同數(shù)位的將一組編碼中任何兩個合法編碼之間對應位上具有不同數(shù)位的最最小值小值稱為該編碼的距離，簡稱碼距或海明距離。稱為該編碼的距離，簡稱碼距或海明距離。 四位二進制編碼四位二進制編碼0011與與0001 的碼距為的碼距為1; 而而0011與與0

24、000兩組編碼的兩組編碼的距離為距離為2。 若用四位二進制編碼只表示若用四位二進制編碼只表示0000、0011、0101、0110、1001、1010、1100、1111等八種編碼，則碼距為等八種編碼，則碼距為2。此時，這。此時，這8種編碼中的種編碼中的任何一位發(fā)生改變，如任何一位發(fā)生改變，如0000變成變成1000就從有效編碼變成了無效編就從有效編碼變成了無效編碼，容易檢測到這種錯誤。碼，容易檢測到這種錯誤。 如果用四位二進制編十六種狀態(tài)，情況又如何？如果用四位二進制編十六種狀態(tài)，情況又如何？二、校驗碼Confederal Confidential26 數(shù)據(jù)校驗數(shù)據(jù)校驗在正常編碼的基礎上，通

25、過增加一些附加的校驗位得到。在正常編碼的基礎上，通過增加一些附加的校驗位得到。增加校驗的同時也增加了碼距，當碼距增加到一定程度時，校驗增加校驗的同時也增加了碼距，當碼距增加到一定程度時，校驗碼不僅具有檢錯功能，而且還可具有糾正錯誤的能力。碼不僅具有檢錯功能，而且還可具有糾正錯誤的能力。 5.碼距與數(shù)據(jù)校驗之間的關系碼距與數(shù)據(jù)校驗之間的關系 碼距碼距d與校驗碼的與校驗碼的檢錯檢錯(e)和和糾錯糾錯(t)能力的關系如下：能力的關系如下：(1)d e+1 :可檢測可檢測e個錯誤。個錯誤。(2)d 2t+1 :可糾正可糾正t個錯誤。個錯誤。(3)d e+t+1 :可檢測可檢測e個錯誤并糾正個錯誤并糾正

26、t個錯誤個錯誤(e t) 。二、校驗碼Confederal Confidential27如如 X=1001101 ，則，則C=1 被傳送的數(shù)據(jù)為：被傳送的數(shù)據(jù)為：10011011 接收方對接收到的數(shù)字序列進行下列運算接收方對接收到的數(shù)字序列進行下列運算 F= X0 X1 X2 X n-1 C 若若F=1則正確、則正確、 反之則錯。反之則錯。 即當收到的數(shù)字為即當收到的數(shù)字為10011011時時 F=1 當收到的數(shù)字為當收到的數(shù)字為11011011時時 F=0 ，出錯，要求重發(fā)，出錯，要求重發(fā) 6.奇奇/偶校驗碼偶校驗碼C= X0 X1 X2 X n-1 。 發(fā)送方，通過設置校驗位的值，使待傳數(shù)

27、據(jù)中（含一位校驗位）發(fā)送方，通過設置校驗位的值，使待傳數(shù)據(jù)中（含一位校驗位） 1的個數(shù)為奇數(shù)。設校驗位為的個數(shù)為奇數(shù)。設校驗位為C，則：，則：(1)奇校驗奇校驗二、校驗碼Confederal Confidential28 發(fā)送方發(fā)送方通過設置校驗位的值，使待傳數(shù)據(jù)中（含一位校驗位）通過設置校驗位的值，使待傳數(shù)據(jù)中（含一位校驗位） 1的個數(shù)為偶數(shù)。設校驗位為的個數(shù)為偶數(shù)。設校驗位為C，則：，則： C= X0 X1 X2 X n-1 如如 X=1001101 則則C=0 被傳送的數(shù)據(jù)為：被傳送的數(shù)據(jù)為：10011010 接收方對接收到的數(shù)字序列進行下列運算接收方對接收到的數(shù)字序列進行下列運算 (2

28、)偶校驗偶校驗F= X0 X1 X2 X n-1 若若F=1則正確、則正確、 反之則錯。反之則錯。 即當收到的數(shù)字為即當收到的數(shù)字為10011010 時時 F=1 當收到的數(shù)字為當收到的數(shù)字為11011010時時 F=0，出錯，要求重發(fā)，出錯，要求重發(fā)二、校驗碼Confederal Confidential29簡單簡單碼距為碼距為 2（?）不能檢測同時出現(xiàn)偶數(shù)個位錯誤的錯誤?。ú荒軝z測同時出現(xiàn)偶數(shù)個位錯誤的錯誤！（?）(3)奇奇/偶校驗的特點偶校驗的特點(4)奇偶校驗的應用場合分析奇偶校驗的應用場合分析 近距離近距離 RAID二、校驗碼Confederal Confidential30(5)交

29、叉奇交叉奇/偶校驗偶校驗 (分組分組奇奇/偶校驗偶校驗 )二、校驗碼Confederal Confidential317.海明校驗（海明校驗（Richard Hamming（理查德（理查德海明）海明）1950年提年提出）出）(1)奇偶校驗的不足奇偶校驗的不足 只能檢測奇數(shù)個位錯誤，且不能糾錯，只能檢測奇數(shù)個位錯誤，且不能糾錯， 檢測得出的無錯誤結(jié)果不一定可信。檢測得出的無錯誤結(jié)果不一定可信。 (2)海明校驗海明校驗 具有檢測和糾正錯誤的一種編碼具有檢測和糾正錯誤的一種編碼 （多重奇偶校驗）（多重奇偶校驗） 基本思想基本思想: 將待傳送的信息將待傳送的信息 , 按照某種規(guī)律分成若干組按照某種規(guī)律

30、分成若干組, 每組安排一個校驗位每組安排一個校驗位 , 用于奇偶測試；這樣就提供了多用于奇偶測試；這樣就提供了多 位檢錯信息位檢錯信息, 以指出最大可能是哪一位出錯以指出最大可能是哪一位出錯, 從而糾正。從而糾正。 二、校驗碼Confederal Confidential32(3)具有指出并糾正一位錯誤的海明校驗需要的位數(shù)具有指出并糾正一位錯誤的海明校驗需要的位數(shù)設有設有r r位校驗位，共能表示位校驗位，共能表示2 2r r種不同的狀態(tài)，用一種狀態(tài)表種不同的狀態(tài)，用一種狀態(tài)表示無差錯，剩余的可以表示示無差錯，剩余的可以表示2 2r r -1 -1種錯誤，由于差錯可能出種錯誤，由于差錯可能出現(xiàn)在

31、數(shù)據(jù)位和校驗位，因此必須滿足：現(xiàn)在數(shù)據(jù)位和校驗位，因此必須滿足： 2 2r r - 1 = k + r - 1 = k + r （k k 數(shù)據(jù)位的位數(shù)；數(shù)據(jù)位的位數(shù)； r r 校驗位的位數(shù)）校驗位的位數(shù)）校驗位在海明碼中的分布規(guī)則：校驗位在海明碼中的分布規(guī)則： k+r位海明碼中，校驗位位海明碼中，校驗位Pi分布在海明碼分布在海明碼的的H H2 2i-i-1 1 位上，位上，i=1.ri=1.r二、校驗碼Confederal Confidential33(4)海明碼的形成方法海明碼的形成方法海明碼位號海明碼位號 Hj1 2 3 4 5 6 7 8 9 10 11 P和和b的分布的分布P1 P2

32、b1 P3 b2 b3 b4 P4 b5 b6 b7 a)分組原則：分組原則：確定海明碼每位數(shù)據(jù)位所用的校驗位確定海明碼每位數(shù)據(jù)位所用的校驗位根據(jù)每個校驗位校驗的位分組：根據(jù)每個校驗位校驗的位分組： P1:H3,H5,H7,H9,H11 P2:H3,H6,H7,H10,H11 P3: H5,H6,H7 P4: H9,H10,H11二、校驗碼Confederal Confidential34b)校驗位的取值（偶校驗為例）校驗位的取值（偶校驗為例）P1=b1 b2 b4 b5 b7 P2=b1 b3 b4 b6 b7P3=b2 b3 b4 P4=b5 b6 b7 假設假設b1b2b3b4b5b6b

33、7 = 1011000 則：則：P1= 1 0 1 0 0 = 0 P2 = 1 1 1 0 0=1 P3=0 1 1 = 0 P4=0 0 0 = 0則則H = 0 1 1 0 0 1 1 0 0 0 0二、校驗碼Confederal Confidential35c)指錯、糾錯原理指錯、糾錯原理 指錯字指錯字P1= b1 b2 b4 b5 b7 P2= b1 b3 b4 b6 b7P3=b2 b3 b4 P4=b5 b6 b7 則指錯字由則指錯字由G4G3G2G1組成，其中：組成，其中：G4= P4 b5 b6 b7 G3 = P3 b2 b3 b4 G2= P2 b1 b3 b4 b6 b

34、7G1= P1 b1 b2 b4 b5 b7 上例中上例中 發(fā)送方發(fā)送方H = 0 1 1 0 0 1 1 0 0 0 0如果接收到如果接收到 H = 0 1 1 0 0 1 1 0 0 0 1G4 = 0 0 0 1 = 1 G3 = 0 0 1 1 = 0G2 = 1 1 1 1 0 1 = 1 G1 = 0 1 0 1 0 1 = 1二、校驗碼Confederal Confidential36G4G3G2G1= 1011表明表明H11出錯，改正該位的錯誤即可。出錯，改正該位的錯誤即可。則錯誤字為：則錯誤字為：(5)海明校驗的缺點海明校驗的缺點 計算復雜計算復雜(6)關于擴展的海明編碼（指

35、出并糾正多位錯誤的關于擴展的海明編碼（指出并糾正多位錯誤的海明編碼）海明編碼）， 請查閱相關資料。請查閱相關資料。二、校驗碼Confederal Confidential37(1)CRC 是一種基于模是一種基于模2運算規(guī)則的校驗碼；運算規(guī)則的校驗碼；(2)模模2運算規(guī)則：運算規(guī)則： a)加加/減運算（異或運算，或不帶進位的加法，不帶借位的減法）減運算（異或運算，或不帶進位的加法，不帶借位的減法） 000，011，101，110 b)乘法運算：按模乘法運算：按模2加求部分積之和加求部分積之和 ，不進位，不進位 c)模模2除法除法 按模按模2減，求部分余數(shù)，不借位。減，求部分余數(shù)，不借位。 上商原

36、則是：上商原則是： 部分余數(shù)首位為部分余數(shù)首位為1時，商為時，商為1，減除數(shù)；，減除數(shù)； 部分余數(shù)首位為部分余數(shù)首位為0時，商為時，商為0，減，減0； 當部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。當部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。8)循環(huán)冗余校驗（循環(huán)冗余校驗（CRC，Cyclic Redundancy Check）二、校驗碼Confederal Confidential38部分余數(shù)首位為部分余數(shù)首位為1時，商為時，商為1，減除數(shù)；，減除數(shù)；部分余數(shù)首位為部分余數(shù)首位為0時，商為時，商為0，減，減0；當部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。當部分余數(shù)的位數(shù)

37、小于除數(shù)的位數(shù)時，該余數(shù)為最后余數(shù)。二、校驗碼Confederal Confidential393) CRC編碼方法編碼方法(1)選擇合適的生成多項式選擇合適的生成多項式G(x),其最高位的權(quán)值其最高位的權(quán)值r log2K，其中，其中K為被校驗信息的位數(shù)；如為被校驗信息的位數(shù)；如K=4位時，位時，r=3。(2)將待校驗的二進制信息將待校驗的二進制信息Q(X)邏輯左移邏輯左移r位，得到位，得到Q(X)(3)用用Q(X) 按模按模2運算法則除運算法則除G(x)，將得到的，將得到的r位余數(shù)替換位余數(shù)替換Q(X)最最后的后的r位，就得到位，就得到Q(X)的的CRC編碼。編碼。二、校驗碼Confeder

38、al Confidential40解：解： M(x)1100， r3M(x)2311000001100000 / 1011 按模按模2除法，得商除法，得商Q(x)1110，余數(shù)，余數(shù)R(x)010。 該信息的該信息的CRC碼碼 ：1100010 該該CRC碼稱為（碼稱為（7，4）碼）碼例例8 求有效信息求有效信息1100的的CRC碼，生存多項式碼，生存多項式G(x)1011。二、校驗碼Confederal Confidential414) CRC糾錯糾錯(1)檢錯檢錯接收部件收到接收部件收到CRC碼后，仍用約定的生成多項式碼后，仍用約定的生成多項式G(x)去除收到的去除收到的編碼，若余數(shù)為編碼，若余數(shù)為0，表示傳送正確；若余數(shù)不為，表示傳送正確；若余數(shù)不為0，表示出錯，再，表示出錯，再由余數(shù)的值由余數(shù)的值來確定哪一位出錯，從而加以糾正。來確定哪一位出錯，從而加以糾正。 二、校驗碼Confederal Confidential42(2)糾錯糾錯 不論錯誤出現(xiàn)在哪一位，均要通過將出錯位循環(huán)左移到最左邊的一位上不論錯誤出現(xiàn)在哪一位，均要通過