計(jì)算機(jī)組成原理-路，在腳下——以踏實(shí)·執(zhí)著·進(jìn)取的態(tài)度

1、上次作業(yè)講評　　畫一個4位移位電路的完整邏輯圖，該電路具有直送、循環(huán)左移1位、循環(huán)右移1位的功能，由控制信號 S0、 S1進(jìn)行選擇。,補(bǔ)充題一 根據(jù)狀態(tài)條件C、Z、V、S寫出表示以下數(shù)據(jù)比較結(jié)果狀態(tài)條件的表達(dá)式： 1、無符號數(shù)大于 2、無符號數(shù)小于或等于 3、帶符號數(shù)小于 4、帶符號數(shù)大于或等于習(xí)題P8

2、6　　　 1、2、3、5、10、11（給圖）思考題P86(不用交)　　 4、6、7、8 、12（選）,注意：1、郵件的主題上的學(xué)號與姓名章號,教學(xué)內(nèi)容,教學(xué)大綱規(guī)定: 講解單臺計(jì)算機(jī)的完 整 硬件系統(tǒng) 的基本組成原理與內(nèi)部運(yùn)行機(jī)制T- 單臺：非多機(jī)系統(tǒng)， 非多處理機(jī)結(jié)構(gòu) 基本：不一定是最高性能，最合理的組成, 而是最基礎(chǔ)的必要的組成部分 完整：

3、計(jì)算機(jī)整機(jī)全部的硬件功能部件,輸入設(shè)備,輸出設(shè)備,入出接口和總線,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,第四單元,第五單元,第三單元,第二單元,,,,,,計(jì)算機(jī)硬件系統(tǒng),,,,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),,運(yùn)算器部件是計(jì)算機(jī)中進(jìn)行數(shù)據(jù)加工的部件，其主要功能包括：1. 執(zhí)行數(shù)值數(shù)據(jù)的算術(shù)加減乘除等運(yùn)算， 執(zhí)行邏輯數(shù)據(jù)的與或非等邏輯運(yùn)算， 由一個被稱為 ALU 的線路完成。

4、2. 暫時存放參加運(yùn)算的數(shù)據(jù)和中間結(jié)果， 由多個通用寄存器來承擔(dān)。 3. 運(yùn)算器通常也是數(shù)據(jù)傳輸?shù)耐?。,,,控 制 器,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),控制器是計(jì)算機(jī)中控制執(zhí)行指令的部件：一. 正確執(zhí)行每條指令 1. 首先是取來一條指令， 2. 接著分析這條指令， 3. 再按指令格式和功能執(zhí)行這條指令

5、二. 保證指令按規(guī)定序列 自動 連續(xù) 地 執(zhí)行。三. 對各種異常情況和請求及時響應(yīng)和處理。說到底，控制器要向計(jì)算機(jī)各功能部件提供 每一時刻協(xié)同運(yùn)行所需要的控制信號,,,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),由高速緩沖存儲器，主存儲器，外存儲器所組成的多級（層）存儲器系統(tǒng)，是計(jì)算機(jī)中用于存儲程序和數(shù)據(jù)的子系統(tǒng)。 這三級存儲器所用的存儲

6、介質(zhì)的工作原理和特性各不相同。將作為三個部分分別講解。,,輸入設(shè)備是向計(jì)算機(jī)中送入程序和數(shù)據(jù)的有一定獨(dú)立功能的設(shè)備，通過 接口 和 總線與計(jì)算機(jī)主機(jī)連通，用于人—機(jī)交互聯(lián)系,如計(jì)算機(jī)鍵盤和鼠標(biāo)等。,輸入設(shè)備,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),,,輸入設(shè)備,輸出設(shè)備,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),輸出設(shè)備是計(jì)算機(jī)中用于送出計(jì)算機(jī)內(nèi)部信息的設(shè)

7、備,例如打印機(jī), 顯示器等。,,,輸入設(shè)備,輸出設(shè)備,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,計(jì)算機(jī)硬件系統(tǒng),這些部件和設(shè)備通過總線和接口連接在一起, 構(gòu)成計(jì)算機(jī)整機(jī)系統(tǒng) ,協(xié)同運(yùn)行.,,輸入設(shè)備,輸出設(shè)備,入出接口和總線,外存設(shè)備,主存儲器,高速緩存,控 制 器,運(yùn) 算 器,第四單元,第五單元,第三單元,第二單元,,,,,,計(jì)算機(jī)硬件系統(tǒng),,,第二單元：第 3、4 章,一. 數(shù)據(jù)編碼與表示(基本)

8、二. 數(shù)據(jù)的算術(shù)運(yùn)算(基本) 定點(diǎn)運(yùn)算器的功能與組成(重點(diǎn)) 浮點(diǎn)運(yùn)算與浮點(diǎn)運(yùn)算器五. 檢錯糾錯編碼(難點(diǎn)),,一. 數(shù)據(jù)編碼與表示 1. 信息編碼二要素2. 基二碼應(yīng)用實(shí)例：數(shù)據(jù)表示邏輯數(shù)據(jù)表示字符數(shù)據(jù)表示ASCII EBCDIC字符串 漢字檢錯糾錯碼 奇偶校驗(yàn)碼 海明校驗(yàn)碼 循環(huán)冗余校驗(yàn)碼3. 進(jìn)位記數(shù)法與數(shù)制轉(zhuǎn)換定點(diǎn)小數(shù) 整數(shù)

9、 浮點(diǎn)數(shù)二——十進(jìn)制數(shù)（BCD編碼）,1. 數(shù)字化編碼二要素,數(shù)值 文字 符號 語音 圖形 圖像 等統(tǒng)稱數(shù)據(jù)，在計(jì)算機(jī)內(nèi)部，都必須用數(shù)字化編碼的形式被 存儲 加工 和 傳送 數(shù)字化編碼二要素: 1 .少量簡單的基本符號 2. 一定的組合規(guī)則 用以表示大量復(fù)雜多樣的信息,,,2. 基二碼（二進(jìn)制碼）,只使用兩個基本點(diǎn)符號：　　１０符號個數(shù)最少，物理上容易實(shí)現(xiàn)與二值邏

10、輯的 真假 兩個值對應(yīng)簡單用二進(jìn)制碼表示數(shù)值數(shù)據(jù)運(yùn)算規(guī)則簡單,基二碼應(yīng)用實(shí)例：數(shù)據(jù)表示,邏輯型數(shù)據(jù)字符型數(shù)據(jù)ASCII 碼 EBCDIC 碼字符串 漢字檢錯糾錯碼奇偶校驗(yàn)海明校驗(yàn) 循環(huán)冗余校驗(yàn)數(shù)值型數(shù)據(jù)定點(diǎn)小數(shù) 整數(shù) 浮點(diǎn)數(shù) 二—十進(jìn)制數(shù)（BCD碼）,邏輯型數(shù)據(jù),邏輯型數(shù)據(jù)只有兩個值：真 和 假，正好可以用

11、二進(jìn)制碼的兩個符號分別表示，例如 1 表示 真 則 0 表示 假不必使用另外的編碼規(guī)則。對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的 與 或 非等基本邏輯運(yùn)算。其規(guī)則如下：,,邏輯型數(shù)據(jù)基本運(yùn)算規(guī)則,X Y X與Y X或Y X的非 0 0 0 0 1 0 1

12、 0 1 1 1 0 0 1 0 1 1 1 1 0,,,,,,,,,字符型數(shù)據(jù)的表示,字符作為人—機(jī)聯(lián)系的媒介，是最重要的數(shù)據(jù)類型之一，當(dāng)前的西文字符集由 128 個符號組成，通常用 8 位二進(jìn)制編碼,即用

13、一個字節(jié)來表示每一個符號，當(dāng)前通用的兩個標(biāo)準(zhǔn)字符集是：ASCII 碼： 即 American Standard Code for Information InterchangeEBCDIC碼：即 Extended Binary Coded Decimal Interchage Code ASCII碼字符集具

14、體編碼如下表所示：,P60,ASCII字符編碼集,b6 b5 b4 000 001 010 011 100 101 110 111 b3 b2 b1 b0 0000 NUL DLE SP 0 @ P , p

15、 0001 SOH DC1 ! 1 A Q a q 0010 STX DC2 “ 2 B R b r 0011

16、 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK

17、 % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB ‘ 7

18、 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y

19、 i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K [ k

20、 { 1100 FF FS , N ^ n ~ 1111 SI US / ? O _ o,,,,,,,,P

21、60,字符串的表示與存儲,字符串是指連續(xù)的一串字符，它們占據(jù)主存中連續(xù)的多個字節(jié)，每個字節(jié)存放一個字符，對一個主存字的多個字節(jié)，有按從低位到高位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。表示字符串?dāng)?shù)據(jù)要給出串存放的主存起始地址和串的長度。例如：IF A>B THEN READ(C)就可以有如下不同的存放方式： I F A A F I > B

22、 T T B > 假定每個字 H E N N E H 由 4 個字節(jié) R E A D D A E R 組成 ( C ) ) C

23、 (,,,,,,,,,,,,,,,,,漢字的表示,通常用兩個字節(jié)表示一個漢字為了與西文字符編碼相區(qū)別（西文的ASCII碼的最高一位編碼值為0），表示一個漢字時，把兩個字節(jié)的最高一位的編碼值設(shè)定為1，則該編碼集的最多編碼數(shù)量為128*128。這種編碼方案與西文傳送中的把ASCII碼的最高一位用作奇偶校驗(yàn)位有矛盾。,漢字信息的數(shù)字化,國標(biāo)碼：國家標(biāo)準(zhǔn)信息交換用漢字編碼。國標(biāo)碼采用雙字節(jié)的編碼方式,用兩個7位二進(jìn)制編碼表示一個漢字。,

24、國標(biāo)碼收入6763個漢字，682個西文字符、圖符，構(gòu)成94×94的矩陣。（每一行為“區(qū)”，每一列為“位”：國標(biāo)區(qū)位碼）,機(jī)內(nèi)碼,“啊”：區(qū)位碼“1601” 國標(biāo)碼“3021H”,00110000 00100001,10110000 10100001,“啊”：機(jī)內(nèi)碼“B0A1H”,漢字信息的數(shù)字化,外碼,,輸入程序,,內(nèi)碼,字庫,,,字符,顯示輸出打印輸出,,,,,,,,輸入,輸出,漢字輸入碼(外碼):將漢字通過鍵盤

25、輸入到計(jì)算機(jī)而采用的編碼。拼音：全拼、雙拼字型：五筆字型數(shù)字：區(qū)位碼、電報(bào)碼,漢字機(jī)內(nèi)碼：在漢字信息處理中為漢字的存儲、運(yùn)算與傳輸所編制的代碼,內(nèi)碼與字符一一對應(yīng),漢字的輸出（字庫）,72,128,288,各種漢字編碼之間的關(guān)系,數(shù)字編碼,字音編碼,字形編碼,,內(nèi)碼,字形碼,國標(biāo)碼,顯示漢字,打印漢字,,,,,,,,,進(jìn)位記數(shù)法與進(jìn)制轉(zhuǎn)換,進(jìn)位記數(shù)法,N,=,i=m-1,D,i,*,i,,,,r,-k,N 代表一個數(shù)值,r 是這個

26、數(shù)制的基(Radix),i表示這些符號排列的位號,D,i,是位號為i的位上的一個符號,r,i,是位號為i的位上的一個 1 代表的值,i,r,D,i,*,是第i位的所代表的實(shí)際值,,,,,,表示m+k位的值求累加和,p49,十進(jìn)制轉(zhuǎn)二進(jìn)制,整數(shù)部分除2取余 小數(shù)部分乘2取整,2,,,,1 1,,,,,,,2,2,2,5,2,1,0,,1,,1,,0,,1,,,,0.625 * 2,1,0.25 * 2,0,0.5 *

27、2,1,0.0,除盡為止 求得位數(shù)滿足要求為止,,低,高,,高,低,,,從二進(jìn)制數(shù)求其十進(jìn)制的值，逐位碼權(quán)累加求和,二到八或十六進(jìn)制轉(zhuǎn)換,二到八 從小數(shù)點(diǎn)向左右三位一分組（10 011 100 . 01)2 = ( 234 . 2 )8 010 二到十六 從小數(shù)點(diǎn)向左右四位一分組（1001 1100 . 01)2 = ( 9C . 4 )1

28、6 0100 說明：整數(shù)部分不足位數(shù)對轉(zhuǎn)換無影響， 小數(shù)部分不足位數(shù)要補(bǔ)零湊足， 否則出錯。,二 十進(jìn)制編碼（BCD編碼）,用四位二進(jìn)制表示一位十進(jìn)制， 16個編碼狀態(tài)選用其中的10個編碼有多種方案，例如： 8421碼，余 3 碼，循環(huán)碼又可區(qū)分為：有權(quán)碼：每位上的 1 代表確定的值無權(quán)碼：無法確定每位上的

29、1 代表的值,,0 0000 0011 0000 00001 0001 0100 0001 01112 0010 0101 0011 01103 0011 0110 0010 01014 0100 0111 0110 01005 0101

30、 1000 1110 10116 0110 1001 1010 10107 0111 1010 1000 10018 1000 1011 1100 10009 1001 1100 0100 1111,有權(quán)碼 與 無權(quán)碼,8421,余3碼,循環(huán)碼,84-2-1,,P

31、66-67,如何判定碼權(quán),0 00001 0111 4 +（-2）+（-1）2 0110 4 +（-2） 驗(yàn)證每個碼的值3 0101 4 +（-1）4 0100 4 從一編碼求碼權(quán)5 1011

32、 8 +（-2）+（-1）6 1010 -2 結(jié)論7 1001 -1 證明此編碼系統(tǒng)為有權(quán)碼8 1000 89 1111 8 + 4 +（-2）+（-1）,如何判定碼權(quán),0 00001 0111

33、 4 +（-2）+（-1）2 0110 4 +（-2） 驗(yàn)證每個碼的值3 0101 4 +（-1）4 0100 4 從一編碼求碼權(quán)5 1011 8 +（-2）+（-1）6 1010

34、 -2 結(jié)論7 1001 -1 證明此編碼系統(tǒng)為有權(quán)碼8 1000 89 1111 8 + 4 +（-2）+（-1）,,,,,,如何判定碼權(quán),0 00001 0111 4 +（-2）+（-1）2 0

35、110 4 +（-2） 驗(yàn)證每個碼的值3 0101 4 +（-1）4 0100 4 從一編碼求碼權(quán)5 1011 8 +（-2）+（-1）6 1010 -2

36、 結(jié)論7 1001 -1 證明此編碼系統(tǒng)為有權(quán)碼8 1000 89 1111 8 + 4 +（-2）+（-1）,,,,,,,,,,,,,,,,,,,,如何判定碼權(quán),0 0011 2+1 = 0 驗(yàn)證各碼的值1 0100

37、 1 從一編碼求碼權(quán)2 0101 13 0110 24 01115 1000 6 1001 結(jié)論 7 1010 證明此編碼系統(tǒng)為無權(quán)碼 8 1011

38、9 1100,,,,,,,,,,,,,,,,,數(shù)值數(shù)據(jù)在計(jì)算機(jī)內(nèi)的格式,定點(diǎn)小數(shù): N = N N N ……...N,s,-1,-n,-2,整 數(shù) : N = N N N ... N N,0,1,s,n,n-1,浮點(diǎn)數(shù): N = M E E ...E E M M ...M,s,s,m-1,1,0,-1,-2,-n

39、,符號位 階碼位 尾數(shù)數(shù)碼位 總位數(shù),短浮點(diǎn)數(shù): 1 8 23 32,長浮點(diǎn)數(shù): 1 11 52 64,臨時浮點(diǎn)數(shù): 1 15

40、 64 80,IEEE 標(biāo)準(zhǔn)： 階碼用移碼，尾數(shù)用原碼,基為 2,P63,定點(diǎn)小數(shù)表示: Ns N1 N2 … Nn,[ X ] = [ X ] = [ X ] =,,（純小數(shù)）原碼，反碼，補(bǔ)碼的定義,P68,定點(diǎn)小數(shù)表示: Ns N1 N2 … Nn,原 碼 定義： [ X ] 原 =實(shí)例：X1 = 0.10110 -0.10110

41、 0.0000 [ X ] 原 = 010110 110110 00000 10000 結(jié)論：原碼為符號位加數(shù)的絕對值，0正1負(fù) 原碼零有兩個編碼，+0和 -0編碼不同 原碼難以用于加減運(yùn)算，但乘除方便,,

42、X,1 - X,-1 < X < 0,,0 < X < 1,,,,,,定點(diǎn)小數(shù)表示: Ns N1 N2 … Nn,模 2 補(bǔ)碼 定義： [ X ] 補(bǔ) =實(shí)例：X1 = 0.10110 -0.10110 0.0000 [ X ] 補(bǔ) = 010110 101010 00000結(jié)論：補(bǔ)碼最高一位是符號位，0正 1 負(fù)

43、 補(bǔ)碼表示為 2*符號位 + 數(shù)的真值 補(bǔ)碼零只有一個編碼，故能表示 -1 補(bǔ)碼能很好地用于加減（乘除）運(yùn)算,,X,2 + X,-1 < X < 0 MOD 2,,0 < X < 1,,,,,,,,P69書中5,定點(diǎn)小數(shù)表示: Ns N1 N2 … Nn,反 碼定義：[ X

44、]反 =實(shí)例：X1 = 0.10110 -0.10110 0.0000 [ X ]反 = 010110 101001 00000 11111 結(jié)論：負(fù)數(shù)為符號位跟數(shù)每一位的反，0正 1 負(fù) 反碼零

45、有二個編碼，分+0 和 -0 反碼難以用于加減運(yùn)算,,X,(2-2-n) + X,-1 < X < 0 MOD (2-2-n),,0 < X < 1,,,,,P71,整數(shù)的編碼表示,整數(shù)的 原碼 反碼 補(bǔ)碼 表示與小數(shù)的三種表示基本相同，差別僅表現(xiàn)在小數(shù)點(diǎn)的位置，可以認(rèn)為整數(shù)的小數(shù)點(diǎn)在最低數(shù)值位的右側(cè)因此整數(shù)的模與整數(shù)位數(shù)有關(guān)，講課中不大用整數(shù)講 原 反 補(bǔ) 碼定義例

46、如：整數(shù)八位碼： X = +01110 [X]原= 0 01110 [X]補(bǔ)= 0 01110 X = - 01110 [X]原= 1 01110 [X]補(bǔ)= 1 10010,P72,補(bǔ)碼加減法的實(shí)現(xiàn),規(guī)則：P73[X + Y] = [X] + [Y] [X-Y] = [X] + [-Y][-Y] = 對 [Y] 逐位取反,再在最低位加 1,補(bǔ),補(bǔ),補(bǔ),補(bǔ),

47、補(bǔ),補(bǔ),補(bǔ),補(bǔ),溢出的判斷及其實(shí)現(xiàn),溢出判斷：1、正 + 正 得負(fù) 或 負(fù) + 負(fù) 得正 或 　異號-得？2、最高數(shù)值位有向符號位的進(jìn)位，但符號位不 產(chǎn)生向更高位的進(jìn)位。3、雙符號位的值為 01 或 10 。,P71模4補(bǔ)碼的定義及性質(zhì),溢出的判斷及其實(shí)現(xiàn),注意與浮點(diǎn)數(shù)的溢出有不同,補(bǔ)碼加減法運(yùn)算實(shí)例,X=0.1011 y= -0.0101 模 4 補(bǔ)碼[X] = 00

48、 1011, [Y] = 11 1011 [-Y] = 00 0101 00 1011 00 1011+11 1011 + 00 0101100 0110 01 0000X+Y X-Y (溢出),補(bǔ)

49、,補(bǔ),,補(bǔ),,,,,P71模4補(bǔ)碼,補(bǔ)碼表示中的符號位擴(kuò)展,由 [X]補(bǔ) 求 [X / 2]補(bǔ) 的方法 原符號位不變， 且符號位與數(shù)值位均右移一位，例如，[X]補(bǔ) =10010 則 [X/2]補(bǔ) =110010不同位數(shù)的整數(shù)補(bǔ)碼相加減時， 位數(shù)少的補(bǔ)碼數(shù)的符號位向左擴(kuò)展， 一直擴(kuò)展到與另一數(shù)的符號位對齊。 0101010111000011 010

50、1010111000011 + 1111111110011100 + 0000000000011100,,,,,,PC的16位運(yùn)算,11111111 00000000,0101010101011111 0101010111011111,原 反 補(bǔ)碼表示小結(jié),正數(shù)的 原碼，反碼，補(bǔ)碼表示均相同，符號位為 0，數(shù)值位同數(shù)的真值。零的原碼和反碼均有2個編碼，補(bǔ)碼只一個碼

51、負(fù)數(shù)的 原碼、反碼、補(bǔ)碼表示均不同，符號位為 1，數(shù)值位：原碼為數(shù)的絕對值； 反碼為每一位均取反碼； 補(bǔ)碼為反碼再在最低位1；由[X]補(bǔ)求[-X]補(bǔ)：每一位取反后再在最低位+1；

52、 n由[X]補(bǔ)求X的真值：X= - X0 + Xi * 2-i P70,i=1,檢錯糾錯碼,1、 為提高可靠性：除采用更高可靠性的器件，更好的生產(chǎn)工藝等外，還可從數(shù)據(jù)編碼上想辦法。　　　2、具體辦法：　　　　a、即采用一點(diǎn)冗余的線路　　　　b、在原數(shù)據(jù)位外增加一到幾個校驗(yàn)位，使新的碼字帶上某種特性　　　　c、則傳送后通過檢查該碼字是否仍有此特性，來發(fā)現(xiàn)是否出錯，甚至定位錯并自動改正　　　這檢錯糾錯編碼

53、技術(shù)。,問題的提出,,源信息,目的信息,1,1,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,,,問題的提出,,源信息,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,目的信息,1,0,,,傳送1位2進(jìn)制數(shù),問題的提出,,源信息,目的信息,1,0,WHH,HWN,傳送1位2進(jìn)制數(shù),用一位代碼來表示合法：1、0非法： 無,,,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,問題的提出,,源信息,目的信息,1,非法,WHH,HNW,傳送1位2進(jìn)制數(shù),用二位代碼來表示合法：11

54、-1、00-0非法： 01 、 10,假定1位錯，則傳送正：11-1、00-0傳送誤： 01 、 10,,,11,01,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,問題的提出,,源信息,目的信息,1,非法,WHH,HNW,傳送1位2進(jìn)制數(shù),用二位代碼來表示合法：11-1、00-0非法： 01 、 10,假定1位錯，則傳送正：11-1、00-0傳送誤： 01 、 10,通知重傳或糾錯（知哪位錯）,,,11,

55、01,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,問題的提出,,,,源信息,目的信息,1,1,傳送1位2進(jìn)制數(shù),用二位代碼來表示合法：11-1、00-0非法： 01 、 10,假定1位錯，則傳送正：11-1、00-0傳送誤： 01 、 10,11,11,編碼,譯碼,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,問題的提出,,,,源信息,目的信息,1,1,原始數(shù)據(jù),結(jié)果數(shù)據(jù),11,11,編碼,譯碼,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,傳送碼字,傳送碼

56、字,問題的提出,,,,源信息,目的信息,1,1,原始數(shù)據(jù)也是編碼,結(jié)果數(shù)據(jù),11,11,編碼,譯碼,內(nèi)存讀寫外設(shè)讀寫數(shù)據(jù)傳送,碼字,碼字,編碼過程,譯碼過程,,傳送,,,原始數(shù)據(jù),碼 字,,結(jié)果數(shù)據(jù),形成校驗(yàn)位的值，加進(jìn)特征,檢查接收的碼字，發(fā)現(xiàn) / 改正錯誤,最小碼距(碼距) 從一個合法碼變成另一個合法碼,至少要改變幾位碼的值。,P55,幾種常用的檢錯糾錯碼,我們只介紹三種常用的檢錯糾錯碼：奇偶檢錯碼

57、， 用于并行數(shù)據(jù)傳送中海明檢錯與糾錯碼，用于并行數(shù)據(jù)傳送中循環(huán)冗余碼， 用于串行數(shù)據(jù)傳送中,編碼過程,譯碼過程,,傳送,,,原始數(shù)據(jù),碼 字,,結(jié)果數(shù)據(jù),形成校驗(yàn)位的值，加進(jìn)特征,檢查接收的碼字，發(fā)現(xiàn) / 改正錯誤,非線性碼,線性碼,卷積碼,分組碼,非循環(huán)碼,循環(huán)碼,隨機(jī) 錯誤,突發(fā) 錯誤,糾錯碼,,,,,,,,,校驗(yàn)位與信息位 的形成關(guān)系,信息位與校驗(yàn)位

58、 的約束條件,碼字本身的 結(jié)構(gòu)特點(diǎn),信息位與校驗(yàn)位排列位置關(guān)系,系統(tǒng)碼,非系統(tǒng)碼,糾錯碼分類,,,P56,幾種常用的檢錯糾錯碼,我們只介紹三種常用的檢錯糾錯碼：奇偶檢錯碼， 用于并行數(shù)據(jù)傳送中海明檢錯與糾錯碼，用于并行數(shù)據(jù)傳送中循環(huán)冗余碼， 用于串行數(shù)據(jù)傳送中,編碼過程,譯碼過程,,傳送,,,原始數(shù)據(jù),碼 字,,結(jié)果數(shù)據(jù),形成校驗(yàn)位的值，加進(jìn)特征,檢查接送的碼字，發(fā)現(xiàn) /

59、 改正錯誤,,,,,,,奇偶校驗(yàn)碼,用于并行碼檢錯原理：在 k 位數(shù)據(jù)碼之外增加 1 位校驗(yàn)位，使 K+1 位碼字中取值為 1 的位數(shù)總保持為 偶數(shù)（偶校驗(yàn)）或 奇數(shù)（奇校驗(yàn)）。例如：0 0 0 1 1 0 0 0 1 0 0 0 0 1

60、 0 1 0 1 0 0 1 0 1 1 0 1 0 1 原有數(shù)字位 兩個新的碼字,偶校驗(yàn),奇校驗(yàn),校驗(yàn)位,,,,,,,奇偶校驗(yàn)碼的實(shí)現(xiàn)電路,譯碼電路,D7 D6 D5 D4 D3 D2 D1 D0,編碼電路,奇校驗(yàn),偶校驗(yàn),海明校驗(yàn)碼(Richard Hamming),用于多位并行數(shù)據(jù)檢錯糾錯處理實(shí)現(xiàn)：

61、為 k 個數(shù)據(jù)位設(shè)立 r 個校驗(yàn)位，使 k+r 位的碼字同時具有這樣兩個特性：1. 能發(fā)現(xiàn)并改正 k+r 位中任何一位出錯，2. 能 發(fā) 現(xiàn) k+r 位中任何二位同時出錯， 但已無法改正。,海明碼的編碼方法,用 k 位數(shù)據(jù)形成 r 個校驗(yàn)值　　　即用 k 個數(shù)據(jù)位中不同的數(shù)據(jù)組合,形成每個校驗(yàn)位的值，使任一數(shù)據(jù)位錯時，將使 r 個校驗(yàn)位中不同的校驗(yàn)位組合發(fā)生變化。即，通過檢查哪種校驗(yàn)位組合起了變化，就能確定哪個數(shù)據(jù)位錯

62、，對該位求反則實(shí)現(xiàn)糾錯。有時兩位錯與某種一位錯對校驗(yàn)位組合的影響相同，必須加以區(qū)分與解決。,要能發(fā)現(xiàn)并改正在k+ r位中的任何一位錯，則 k 與 r 必須 滿 足 關(guān) 系： 2r > = k + r +1,檢錯糾錯能力,,,若能發(fā)現(xiàn)并改正一位錯， 也能發(fā)現(xiàn)兩位錯,則應(yīng)增加一位校驗(yàn)位：設(shè)r=r’+1,則 ， r’=r-1代入上式

63、 2r-1 >= k + r,P57,在k+ r位中，若能發(fā)現(xiàn)并改正一位錯， 也能發(fā)現(xiàn)兩位錯,則： 2r-1 >= k + r,檢錯糾錯能力,,P57表3-2,根據(jù)上式可列出下面校驗(yàn)與數(shù)據(jù)位數(shù)對應(yīng)的關(guān)系表,海明碼的實(shí)現(xiàn),編碼方案,已知k位,列號 6 5 3 0 4 2 1,未知r位,,行號 4 3 2

64、1,,如何填此表最上行（P4行）都填“1” Pi行 —— 在Pi列填為“1”，其余填“0” Di列 —— 使I列的值為3、5、6,例如： 設(shè) k =3, 查表則r =4,P58表3-3,對Pi進(jìn)行編碼(方案),行號 4 3 2 1,列號 6 5 3 0 4 2 1,,,已知k位,未知r位,則傳送的碼字即為 D3 D2 D1 P4 P

65、3 P2 P1,總偶校,,1次偶校,海明碼的實(shí)現(xiàn),譯碼方案,譯碼方案,傳送的碼字為 D3 D2 D1 P4 P3 P2 P1,行號 4 3 2 1,例如： 設(shè) k =3, 查表則r =4,譯碼方案,傳送的碼字為 D3 D2 D1 P4 P3 P2 P1,結(jié)論：無錯： S4 S3 S2 S1全為 0，即Pi與Di組合都與傳送前匹配。一位錯： S4 S3 S2 S1對應(yīng)的位錯，取反糾

66、正。校驗(yàn)位錯可不理睬 二位錯：S4 =0，S3 S2 S1 不全是0。（S4反映奇、偶錯）,知道2位錯，D2D1要糾正否？,傳送的碼字為 D3 D2 D1 P4 P3 P2 P1,檢錯分析： 如果出錯：S4=0或1區(qū)分2或1位錯。（S4反映偶、奇位錯） D2D1同時錯，或D3錯，S3S2S1=110。所以上表稱 “出錯模式表”,行號代表 S 的下標(biāo),出錯模式表,P3P2同時錯呢？,三位錯或四位錯不研究,行號 4

67、 3 2 1,不知1位還是2位錯能糾正？,,,,,,,,,P1 = D2 + D1P2 = D3 + D1P3 = D3 + D2,海明碼的實(shí)現(xiàn)方案 例如： k =3, r =4,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 1 1

68、 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1,P4 = P3 + P2 + P1 + D3 + D2 + D1,S1 = P1 + D2 + D