《錯誤檢測和校正》由會員分享，可在線閱讀，更多相關(guān)《錯誤檢測和校正（31頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,MMT,YANGZHOUDAXUE,物理科學(xué)與技術(shù)學(xué)院,第十一講、錯誤檢測和校正,第,1,節(jié) 理論基礎(chǔ),錯誤的檢測和校正是通過編碼來實(shí)現(xiàn)的。,檢錯編碼的目的是通過解碼能夠發(fā)現(xiàn)數(shù)據(jù)在傳輸過程中出現(xiàn)了錯誤,糾錯編碼不僅能夠檢測到錯誤還能夠糾正過來。,因?yàn)殄e誤是在信道傳輸中產(chǎn)生，所以糾錯或檢錯編碼屬于（通信）信道編碼，而壓縮編碼屬于信源編

2、碼。,信,源,信源,編碼,信道,編碼,調(diào),制,信,道,解,調(diào),信道,譯碼,信源,譯碼,信,宿,噪聲源,香農(nóng)定理指出：當(dāng)信息傳輸速率（,R,）低于信道容量時(shí)，通過編譯碼，就能夠使錯誤概率為任意小。,信道容量指信道傳輸信息的最大能力或傳輸信息的最大值，單位,bit/s,，香農(nóng)給出高斯白噪聲信道的信道容量（,C,）公式：,W,：,信道帶寬,P,S,:,信號功率,N,0,:,噪聲功率密度,香農(nóng)第二定理沒有明確指出編譯碼方法。,糾（檢）錯碼類型：,本講只介紹幾種簡單的線性分組碼和交織碼的概念。,分組碼的表示：,分組碼將,k,個碼元（一般為二進(jìn)制數(shù)）組成一個信息組。例如,k=3,，則有,000,，,001

3、,，,111,八種信息組。編碼器根據(jù)信息組按某種規(guī)律產(chǎn)生,r,個碼元（校驗(yàn)元），形成一個長,n=k+r,的碼字，成為（,n,k,）分組碼。,n,表示碼長，,k,表示信息位的數(shù)目。,例,1,：重復(fù)碼,規(guī)則：,k=1,，如果信息碼字為,1,，則發(fā)送,111,。,如果信息碼子為,0,，則發(fā)送,000,。,這是一個（,3,，,1,）分組碼。,例,2,：一個（,4,，,2,）分組碼（,c3,c2,c1,c0,），信息碼字,(c3,c2),可能為,00,，,01,，,10,，,11,，校驗(yàn)碼字定義為,c1=c2,c0=c3+c2,。則碼字可能為：,0000,，,0111,，,1001,，,1110,。,例

4、,1,和例,2,中的發(fā)送碼字為合法碼字，如果接受端收到非法碼字則說明發(fā)生錯誤。,例,3,：奇偶校驗(yàn)碼,規(guī)則：在,k,個信息源后加上,1,位校驗(yàn)元，使得,n=k+1,個碼元中,0(1),的個數(shù)為奇（偶）數(shù)個。,例如一個（,4,，,3,）碼，使,0,的個數(shù)為偶數(shù)個，則：,Messages codewords,000 0000,001 0011,010 0101,011 0110,100 1001,101 1010,110 1100,111 1111,檢錯和糾錯,重復(fù)碼可以檢出錯兩位和錯一位的情況，可以糾正錯一位的情況。,重復(fù)碼譯碼規(guī)則：,000 0,001 0,010 0,011 1,100 0,

5、101 1,110 1,1,奇偶校驗(yàn)碼僅是檢錯碼，且只能檢出錯奇數(shù)位的情況。,信道出錯的類型,噪聲對傳輸碼元的影響?yīng)毩?，即每一個差錯的出現(xiàn)與否與其前后是否有差錯無關(guān)。,這樣的信道稱為無記憶信道。,因?yàn)楹颓昂鬅o關(guān)，出現(xiàn)錯誤的機(jī)會可以用獨(dú)立的概率來表示（,P,e,）。如果僅考慮,0,和,1,，又有,1,錯誤的變成,0,和,0,錯誤的變成,1,的概率相等，則這樣的信道稱為,BSC,（,Binary Symmetric Channel,，二進(jìn)制對稱信道）。表示為下圖：,1,0,1,0,1-P,e,P,e,P,e,1-P,e,若信道的錯誤不是獨(dú)立出現(xiàn)，而是成串的出現(xiàn)，則稱為有記憶信道?？梢圆扇?交織編碼

6、,技術(shù)解決。,實(shí)際的信道兩種錯誤都可能發(fā)生。,差錯控制系統(tǒng)分類,一、前向糾錯（,FEC,）方式,FEC(Forward Error Control),方式是發(fā)端發(fā)送能夠,糾錯,的碼，收端通過譯碼器糾正這些錯誤。例如重復(fù)碼。但不能保證百分之百糾錯。,二、重傳反饋（,ARQ,）方式,ARQ(Automatic Repeat Request),方式是發(fā)端發(fā)送能夠,檢錯,的碼，收端發(fā)現(xiàn)有錯誤時(shí)，給發(fā)端發(fā)送一個出錯信號要求重發(fā)。例如奇偶校驗(yàn)碼。也不能保證百分之百檢錯。,三、混合糾錯（,HEC,）方式,HEC(Hybird Error Control),方式是上述兩種方式的結(jié)合。發(fā)送端發(fā)送的碼即能檢錯，又

7、能糾錯。譯碼器如果發(fā)現(xiàn)錯誤可以糾正就自動糾正，如果錯誤不能糾正，則通知發(fā)端重發(fā)。,CRC,奇偶校驗(yàn)碼,和重復(fù)碼,都不屬于這類編碼。,第,2,節(jié),CRC,（,Cyclic Redundancy Code,）檢錯編碼,基本思想：,1,、除法,被除數(shù),x,，除數(shù),y,，商,z,，余數(shù),C,。,有：,x=yz+c,x-c=yz,所以，,x-c,肯定可以被,y,整除。,2,、二進(jìn)制數(shù)的模,2,加減法,定義：,0+0=0,，,1+0=1,，,0+1=1,，,1+1=0,0-0=0,，,1-0=1,，,0-1=-1=1,，,1-1=0,可以看到模,2,加法和減法是一樣的。,由模,2,加減法可以定義模,2,的

8、乘除法。,編碼：,設(shè)待編碼的數(shù)據(jù)為,k,位，例,110101101,（,k=9,）,設(shè)除數(shù)為,r+1,位，例,10011(r=4),則余數(shù)最多為,r,位。,令：被除數(shù),=,待編碼的數(shù),2,r,，,1101011010000,，,n=k+r,位,模,2,除法：,則：,1101011010000=10011110000101+1111,有：,1101011010000+1111=10011110000101,1101011011111=10011110000101,1101011011111,就是,CRC,編碼的結(jié)果，最后的,1111,就是,CRC,校驗(yàn)碼。,解碼：看收到的數(shù)據(jù)能否被,10011,

9、整除。如果可以，認(rèn)為沒有出錯；如果不能，通知發(fā)端重發(fā)。,上面的例子是一個（,13,，,9,）檢錯碼。,第,3,節(jié) 混合糾錯碼舉例,一個（,7,，,3,）碼：,校驗(yàn)位生成規(guī)則：,合法碼字：,合法碼字生成規(guī)則：,G,為生成矩陣,H,為校驗(yàn)矩陣，當(dāng)校驗(yàn)結(jié)果為,0,，則認(rèn)為沒有錯，否則有錯,證明：,觀察校驗(yàn)矩陣,H,H,的每一列都不一樣,任意兩列的和都不等于,H,的其它列,第,1,列加第,2,列等于第,4,列加第,7,列,第,4,，,5,，,6,列的和等于第,1,列,第,1,，,4,，,5,，,6,列的和等于,0,出錯假設(shè)：,E,可能有,0000001,到,1111111,共,127,種情況，,E,稱

10、為出錯圖樣。,校驗(yàn)：,有,1,位錯：,S,不為,0,，一定有錯，且根據(jù),S,的具體值知道哪一位出錯。,有,2,位錯：,S,不為,0,，一定有錯，但不知哪,2,位出錯。,因?yàn)槿我鈨闪械暮投疾坏扔?H,的其它列，所以不會誤認(rèn)為,1,位錯。,有,3,位錯：,S,不為,0,，一定有錯。,會誤認(rèn)為第,1,位錯，從而誤糾錯。,有,4,位錯：,S,為,0,，誤認(rèn)為沒有錯。,上例編碼的檢糾錯能力：,1,、能夠檢出,1,位,2,位,3,位錯。,2,、能夠糾正,1,位錯。,3,、能夠?qū)?2,位錯不誤糾正。,4,、對,3,位錯會誤糾。,5,、對,4,位錯會誤檢。,S,等于,H,中和錯誤圖樣相對應(yīng)的列之和。,可以從,

11、H,得出編碼的糾錯能力。,該碼可以用于,HCE,方式。,在實(shí)際應(yīng)用中，比特差錯經(jīng)常成串發(fā)生，而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時(shí)才最有效。,為了糾正這些成串發(fā)生的比特差錯，交織技術(shù),對已編碼的信號按一定規(guī)則重新排列,，解交織后突發(fā)性錯誤在位置上被分散，使其類似于獨(dú)立發(fā)生的隨機(jī)錯誤。,交織編碼和糾錯編碼連用。,一般來說，在發(fā)端先對數(shù)據(jù)進(jìn)行糾錯編碼，然后再進(jìn)行交積處理。,第,4,節(jié) 交織編碼技術(shù),交織的原理圖：,光盤用到的編碼技術(shù)：,CRC,碼,RS,碼：,也是一個（,n,k,）線性分組碼。但是它有糾正,(n-k)/2,個錯誤的能力。,CIRC,碼：,RS,編碼和交織技術(shù)相結(jié)合形成,

12、CIRC,碼，用在,CD-ROM,中。,RSPC,碼,:,基本思想用兩次,RS,編碼對數(shù)據(jù)矩陣的行和列編碼，使得誤碼率進(jìn)一步降低。,ECC,碼,:,在,RSPC,的基礎(chǔ)上對行和列做交織處理。,本章小節(jié),檢錯糾錯編碼屬于信道編碼。,選用什么編碼算法首先需要知道信道的特性。,從信息的角度說，糾錯編碼是通過加大數(shù)據(jù)量來換取準(zhǔn)確率。,交織技術(shù)的目的是為了把可能集中發(fā)生的錯誤分散開。,檢錯糾錯編碼可以連用。,人有了知識，就會具備各種分析能力，,明辨是非的能力。,所以我們要勤懇讀書，廣泛閱讀，,古人說“書中自有黃金屋。,”通過閱讀科技書籍，我們能豐富知識，,培養(yǎng)邏輯思維能力；,通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，,培養(yǎng)文學(xué)情趣；,通過閱讀報(bào)刊，我們能增長見識，擴(kuò)大自己的知識面。,有許多書籍還能培養(yǎng)我們的道德情操，,給我們巨大的精神力量，,鼓舞我們前進(jìn),。,