組成原理第二章(v11)2015

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

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

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

4、mod 2一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential51) X= 0.1011 XX原原=1.1011 X=1.1011 X反反=1.0100 X=1.0100 X補(bǔ)補(bǔ)=1.0101=1.01012) X=+0.1011 2) X=+0.1011 X X原原= X= X反反= X= X補(bǔ)補(bǔ)= 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補(bǔ)補(bǔ)= 0.0000=

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

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

7、x反反 + Y反反 =0.11011.010110.0010+ 1 0.0011一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential8 5)補(bǔ)碼中模的概念補(bǔ)碼中模的概念 （符號(hào)位進(jìn)位后所在位的權(quán)值）（符號(hào)位進(jìn)位后所在位的權(quán)值） 設(shè)設(shè)XX補(bǔ)補(bǔ)= X= X0 0.X.X1 1X X2 2X X3 3XnXnXX補(bǔ)補(bǔ)= =X 1X 1 X X 0 02+X =2-|X|2+X =2-|X| 0 0 X X 11mod 2mod 2XX補(bǔ)補(bǔ)= =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一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential9例例3 3 整數(shù)整數(shù) 1 1 用補(bǔ)碼表示，下列哪些用補(bǔ)碼表示，下列哪些( (個(gè)個(gè)) )結(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的補(bǔ)碼形式為的補(bǔ)碼形式為X X0 0X X1 1X X2 2X X3 3X X4 4X X5 5, ,則則-1-1的補(bǔ)碼又如何表示？的補(bǔ)碼又如何表示？ 模是多少？模是多少？解：依題意知：一個(gè)整數(shù)連同符號(hào)位在內(nèi)共有解：依題意知：一

9、個(gè)整數(shù)連同符號(hào)位在內(nèi)共有6 6位位 ， 則則-1-1補(bǔ)補(bǔ)= = 1 1 11111 11111 根據(jù)補(bǔ)碼的定義，其模為根據(jù)補(bǔ)碼的定義，其模為2 26 6一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential10 移碼表示浮點(diǎn)數(shù)的階碼，只有整數(shù)形式，如移碼表示浮點(diǎn)數(shù)的階碼，只有整數(shù)形式，如IEEE754IEEE754中階碼用移碼表示中階碼用移碼表示。 設(shè)定點(diǎn)整數(shù)設(shè)定點(diǎn)整數(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、實(shí)現(xiàn)：數(shù)值位與具體實(shí)現(xiàn)：數(shù)值位與X X的補(bǔ)碼相同，符號(hào)位與補(bǔ)碼相反。的補(bǔ)碼相同，符號(hào)位與補(bǔ)碼相反。 例例4 4 X= +10101 X X= +10101 X補(bǔ)補(bǔ)= =0 010101 X10101 X移移= =1 11010110101 X= 10101 X X= 10101 X補(bǔ)補(bǔ)= =1 101011 X01011 X移移= =0 001011010116) 移碼（增碼）表移碼（增碼）表示示一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential11 例例5 5 將十進(jìn)制值將十進(jìn)制值X(-127X(-127，-1-1，0 0，1 1，127)127)用四種機(jī)器數(shù)表示用四種機(jī)器

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

12、:格式固定、簡(jiǎn)單、數(shù)據(jù)范圍受限格式固定、簡(jiǎn)單、數(shù)據(jù)范圍受限Confederal Confidential13 浮點(diǎn)數(shù)的使用場(chǎng)合浮點(diǎn)數(shù)的使用場(chǎng)合當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時(shí)。當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時(shí)。(1)(1)格式格式( (一般格式一般格式) ) ESE1E2E3EnMSM1M2M3M4.MkE: E: 階碼位數(shù)，決定數(shù)據(jù)的范圍階碼位數(shù)，決定數(shù)據(jù)的范圍M: M: 尾數(shù)位數(shù)，決定數(shù)的精度尾數(shù)位數(shù)，決定數(shù)的精度2)2)浮點(diǎn)數(shù)浮點(diǎn)數(shù)把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。N=Rem一、計(jì)算機(jī)內(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。從而所有浮點(diǎn)。從而所有浮點(diǎn)數(shù)的階碼值都可以變成非負(fù)整數(shù)數(shù)的階碼值都可以變成非負(fù)整數(shù), ,便于浮點(diǎn)數(shù)的比較和排序。便于浮點(diǎn)數(shù)的比較和排序。 IEEE754IEEE754尾數(shù)形式為尾數(shù)形式為1.XXXXXX,1.XXXXXX,其中其中M M部分保存的

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

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

16、非數(shù)值，對(duì)應(yīng)于，表示一個(gè)非數(shù)值，對(duì)應(yīng)于0 / 00 / 0。一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential16一、計(jì)算機(jī)內(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一、計(jì)算機(jī)內(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一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示浮點(diǎn)數(shù)的表示范圍與表示精度浮點(diǎn)數(shù)表示法可以擴(kuò)大數(shù)值表示的范圍浮點(diǎn)數(shù)表示法未增加表示數(shù)值的個(gè)數(shù)絕對(duì)值越大，浮點(diǎn)數(shù)分布越稀疏階碼位數(shù)越多，數(shù)據(jù)表示的范圍就越大尾數(shù)位數(shù)越多，數(shù)據(jù)表示的精度越高02-1262-1252-1242-123-2-126Co

18、nfederal Confidential19一、計(jì)算機(jī)內(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二進(jìn)制存儲(chǔ)浮點(diǎn)數(shù)不是精確數(shù)一個(gè)奇怪的程序Confederal Confidential20一、計(jì)算機(jī)內(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一個(gè)奇怪的程序Confederal Confidential21IEEE754 32位浮點(diǎn)數(shù)與對(duì)應(yīng)真值之間的變換流程位浮點(diǎn)數(shù)與對(duì)應(yīng)真值之間的變換流程一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential22例例5 5 將十進(jìn)制數(shù)將十進(jìn)制數(shù)20.5937520.59375轉(zhuǎn)換成轉(zhuǎn)換成3232位位IEEE754IEEE754格式浮點(diǎn)數(shù)的二進(jìn)制格式浮點(diǎn)數(shù)的二進(jìn)制格式來(lái)存儲(chǔ)。格式來(lái)存儲(chǔ)。解解: :先將十進(jìn)制數(shù)換成二進(jìn)制數(shù)：先將十進(jìn)制數(shù)換成二進(jìn)制數(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) ) 移動(dòng)小數(shù)點(diǎn)，使其變成移動(dòng)小數(shù)點(diǎn)，使其變成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位浮點(diǎn)數(shù)的二進(jìn)制存儲(chǔ)格式為：位浮點(diǎn)數(shù)的二進(jìn)制存儲(chǔ)格式為

21、： 0 0100 0001100 0001 1 1010010 0100 1100 0000 0000 00000100 1100 0000 0000 0000= (41A4C000)= (41A4C000)1616一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential23例例6 6 若某浮點(diǎn)數(shù)若某浮點(diǎn)數(shù)x x的二進(jìn)制存儲(chǔ)格式為的二進(jìn)制存儲(chǔ)格式為(41360000)(41360000)1616 , ,求與其對(duì)應(yīng)求與其對(duì)應(yīng)的的3232位浮點(diǎn)表示的十進(jìn)的值。位浮點(diǎn)表示的十進(jìn)的值。解：解： (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 則上述浮點(diǎn)數(shù)對(duì)應(yīng)的真值為則上述浮點(diǎn)數(shù)對(duì)應(yīng)的真值為 X=(-1)X=(-1)0 0 (1.011011) (1.011011)2 23 3 =(11.375)=(11.375)1010 一、計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示Confederal Confidential24 2. 檢驗(yàn)碼的工作原理檢驗(yàn)碼的工作原理 1. 問(wèn)題的提出：?jiǎn)栴}的提出：檢測(cè)傳輸、處理和存儲(chǔ)中的錯(cuò)誤。檢測(cè)傳輸、處理和存儲(chǔ)中的錯(cuò)誤。檢檢測(cè)測(cè)器器編碼器編碼器 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. 帶校驗(yàn)信息的數(shù)據(jù)形式帶校驗(yàn)信息的數(shù)據(jù)形式 沒(méi)有付出，就不會(huì)有收獲沒(méi)有付出，就不會(huì)有收獲二、校驗(yàn)碼Confederal Confidential25 4.碼距的概念碼距的概念 將一組編碼中任何兩個(gè)合法編碼之間對(duì)應(yīng)位上具有不同數(shù)位的將一組編碼中任何兩個(gè)合法編碼之間對(duì)應(yīng)位上具有不同數(shù)位的最最小值小值稱為該編碼的距離，簡(jiǎn)稱碼距或海明距離。稱為該編碼的距離，簡(jiǎn)稱碼距或海明距離。 四位二進(jìn)制編碼四位二進(jìn)制編碼0011與與0001 的碼距為的碼距為1; 而而0011與與0

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

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

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

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

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

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

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

31、數(shù)據(jù)位和校驗(yàn)位，因此必須滿足：現(xiàn)在數(shù)據(jù)位和校驗(yàn)位，因此必須滿足： 2 2r r - 1 = k + r - 1 = k + r （k k 數(shù)據(jù)位的位數(shù)；數(shù)據(jù)位的位數(shù)； r r 校驗(yàn)位的位數(shù)）校驗(yàn)位的位數(shù)）校驗(yàn)位在海明碼中的分布規(guī)則：校驗(yàn)位在海明碼中的分布規(guī)則： k+r位海明碼中，校驗(yàn)位位海明碼中，校驗(yàn)位Pi分布在海明碼分布在海明碼的的H H2 2i-i-1 1 位上，位上，i=1.ri=1.r二、校驗(yàn)碼Confederal Confidential33(4)海明碼的形成方法海明碼的形成方法海明碼位號(hào)海明碼位號(hào) 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ù)位所用的校驗(yàn)位確定海明碼每位數(shù)據(jù)位所用的校驗(yàn)位根據(jù)每個(gè)校驗(yàn)位校驗(yàn)的位分組：根據(jù)每個(gè)校驗(yàn)位校驗(yàn)的位分組： P1:H3,H5,H7,H9,H11 P2:H3,H6,H7,H10,H11 P3: H5,H6,H7 P4: H9,H10,H11二、校驗(yàn)碼Confederal Confidential34b)校驗(yàn)位的取值（偶校驗(yàn)為例）校驗(yàn)位的取值（偶校驗(yàn)為例）P1=b1 b2 b4 b5 b7 P2=b1 b3 b4 b6 b7P3=b2 b3 b4 P4=b5 b6 b7 假設(shè)假設(shè)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二、校驗(yàn)碼Confederal Confidential35c)指錯(cuò)、糾錯(cuò)原理指錯(cuò)、糾錯(cuò)原理 指錯(cuò)字指錯(cuò)字P1= b1 b2 b4 b5 b7 P2= b1 b3 b4 b6 b7P3=b2 b3 b4 P4=b5 b6 b7 則指錯(cuò)字由則指錯(cuò)字由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二、校驗(yàn)碼Confederal Confidential36G4G3G2G1= 1011表明表明H11出錯(cuò)，改正該位的錯(cuò)誤即可。出錯(cuò)，改正該位的錯(cuò)誤即可。則錯(cuò)誤字為：則錯(cuò)誤字為：(5)海明校驗(yàn)的缺點(diǎn)海明校驗(yàn)的缺點(diǎn) 計(jì)算復(fù)雜計(jì)算復(fù)雜(6)關(guān)于擴(kuò)展的海明編碼（指

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

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

37、小于除數(shù)的位數(shù)時(shí)，該余數(shù)為最后余數(shù)。二、校驗(yàn)碼Confederal Confidential393) CRC編碼方法編碼方法(1)選擇合適的生成多項(xiàng)式選擇合適的生成多項(xiàng)式G(x),其最高位的權(quán)值其最高位的權(quán)值r log2K，其中，其中K為被校驗(yàn)信息的位數(shù)；如為被校驗(yàn)信息的位數(shù)；如K=4位時(shí)，位時(shí)，r=3。(2)將待校驗(yàn)的二進(jìn)制信息將待校驗(yàn)的二進(jìn)制信息Q(X)邏輯左移邏輯左移r位，得到位，得到Q(X)(3)用用Q(X) 按模按模2運(yùn)算法則除運(yùn)算法則除G(x)，將得到的，將得到的r位余數(shù)替換位余數(shù)替換Q(X)最最后的后的r位，就得到位，就得到Q(X)的的CRC編碼。編碼。二、校驗(yàn)碼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碼，生存多項(xiàng)式碼，生存多項(xiàng)式G(x)1011。二、校驗(yàn)碼Confederal Confidential414) CRC糾錯(cuò)糾錯(cuò)(1)檢錯(cuò)檢錯(cuò)接收部件收到接收部件收到CRC碼后，仍用約定的生成多項(xiàng)式碼后，仍用約定的生成多項(xiàng)式G(x)去除收到的去除收到的編碼，若余數(shù)為編碼，若余數(shù)為0，表示傳送正確；若余數(shù)不為，表示傳送正確；若余數(shù)不為0，表示出錯(cuò)，再，表示出錯(cuò)，再由余數(shù)的值由余數(shù)的值來(lái)確定哪一位出錯(cuò)，從而加以糾正。來(lái)確定哪一位出錯(cuò)，從而加以糾正。 二、校驗(yàn)碼Confederal Confidential42(2)糾錯(cuò)糾錯(cuò) 不論錯(cuò)誤出現(xiàn)在哪一位，均要通過(guò)將出錯(cuò)位循環(huán)左移到最左邊的一位上不論錯(cuò)誤出現(xiàn)在哪一位，均要通過(guò)