錯(cuò)誤檢測和校正

1、MMTMMTYANGZHOUDAXUE物理科學(xué)與技術(shù)學(xué)院物理科學(xué)與技術(shù)學(xué)院第十一講、錯(cuò)誤檢測和校正第十一講、錯(cuò)誤檢測和校正第1節(jié) 理論基礎(chǔ) 錯(cuò)誤的檢測和校正是通過編碼來實(shí)現(xiàn)的。 檢錯(cuò)編碼的目的是通過解碼能夠發(fā)現(xiàn)數(shù)據(jù)在傳輸過程中出現(xiàn)了錯(cuò)誤 糾錯(cuò)編碼不僅能夠檢測到錯(cuò)誤還能夠糾正過來。 因?yàn)殄e(cuò)誤是在信道傳輸中產(chǎn)生，所以糾錯(cuò)或檢錯(cuò)編碼屬于（通信）信道編碼，而壓縮編碼屬于信源編碼。信源信源編碼信道編碼調(diào)制信道解調(diào)信道譯碼信源譯碼信宿噪聲源 香農(nóng)定理指出：當(dāng)信息傳輸速率（R）低于信道容量時(shí)，通過編譯碼，就能夠使錯(cuò)誤概率為任意小。 信道容量指信道傳輸信息的最大能力或傳輸信息的最大值，單位bit/s，香農(nóng)給出

2、高斯白噪聲信道的信道容量（C）公式：20log (1)(/ )sPCWbit sWNW ：信道帶寬PS :信號功率N0 :噪聲功率密度香農(nóng)第二定理沒有明確指出編譯碼方法。糾（檢）錯(cuò)碼類型：本講只介紹幾種簡單的線性分組碼和交織碼的概念。分組碼的表示： 分組碼將k個(gè)碼元（一般為二進(jìn)制數(shù)）組成一個(gè)信息組。例如k=3，則有000，001，111八種信息組。編碼器根據(jù)信息組按某種規(guī)律產(chǎn)生r個(gè)碼元（校驗(yàn)元），形成一個(gè)長n=k+r的碼字，成為（n,k）分組碼。n表示碼長，k表示信息位的數(shù)目。例1：重復(fù)碼 規(guī)則：k=1，如果信息碼字為1，則發(fā)送111。 如果信息碼子為0，則發(fā)送000。 這是一個(gè)（3，1）分組

3、碼。例2：一個(gè)（4，2）分組碼（c3,c2,c1,c0），信息碼字(c3,c2)可能為00，01，10，11，校驗(yàn)碼字定義為c1=c2,c0=c3+c2。則碼字可能為：0000，0111，1001，1110。例1和例2中的發(fā)送碼字為合法碼字，如果接受端收到非法碼字則說明發(fā)生錯(cuò)誤。例3：奇偶校驗(yàn)碼 規(guī)則：在k個(gè)信息源后加上1位校驗(yàn)元，使得n=k+1個(gè)碼元中0(1)的個(gè)數(shù)為奇（偶）數(shù)個(gè)。例如一個(gè)（4，3）碼，使0的個(gè)數(shù)為偶數(shù)個(gè)，則：Messages codewords 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 11

4、1 1111檢錯(cuò)和糾錯(cuò)重復(fù)碼可以檢出錯(cuò)兩位和錯(cuò)一位的情況，可以糾正錯(cuò)一位的情況。重復(fù)碼譯碼規(guī)則：000 0001 0010 0011 1100 0101 1110 1 1111奇偶校驗(yàn)碼僅是檢錯(cuò)碼，且只能檢出錯(cuò)奇數(shù)位的情況。信道出錯(cuò)的類型 噪聲對傳輸碼元的影響?yīng)毩?，即每一個(gè)差錯(cuò)的出現(xiàn)與否與其前后是否有差錯(cuò)無關(guān)。 這樣的信道稱為無記憶信道。 因?yàn)楹颓昂鬅o關(guān)，出現(xiàn)錯(cuò)誤的機(jī)會可以用獨(dú)立的概率來表示（Pe）。如果僅考慮0和1，又有1錯(cuò)誤的變成0和0錯(cuò)誤的變成1的概率相等，則這樣的信道稱為BSC（Binary Symmetric Channel，二進(jìn)制對稱信道）。表示為下圖：10101-PePePe1-

5、Pe 若信道的錯(cuò)誤不是獨(dú)立出現(xiàn)，而是成串的出現(xiàn)，則稱為有記憶信道。可以采取交織編碼技術(shù)解決。 實(shí)際的信道兩種錯(cuò)誤都可能發(fā)生。差錯(cuò)控制系統(tǒng)分類一、前向糾錯(cuò)（FEC）方式 FEC(Forward Error Control)方式是發(fā)端發(fā)送能夠糾錯(cuò)的碼，收端通過譯碼器糾正這些錯(cuò)誤。例如重復(fù)碼。但不能保證百分之百糾錯(cuò)。二、重傳反饋（ARQ）方式 ARQ(Automatic Repeat Request)方式是發(fā)端發(fā)送能夠檢錯(cuò)的碼，收端發(fā)現(xiàn)有錯(cuò)誤時(shí)，給發(fā)端發(fā)送一個(gè)出錯(cuò)信號要求重發(fā)。例如奇偶校驗(yàn)碼。也不能保證百分之百檢錯(cuò)。三、混合糾錯(cuò)（HEC）方式 HEC(Hybird Error Control)方式是

6、上述兩種方式的結(jié)合。發(fā)送端發(fā)送的碼即能檢錯(cuò)，又能糾錯(cuò)。譯碼器如果發(fā)現(xiàn)錯(cuò)誤可以糾正就自動糾正，如果錯(cuò)誤不能糾正，則通知發(fā)端重發(fā)。 CRC,奇偶校驗(yàn)碼和重復(fù)碼都不屬于這類編碼。第2節(jié) CRC（Cyclic Redundancy Code）檢錯(cuò)編碼基本思想：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的乘除法。編碼： 設(shè)待編碼的數(shù)據(jù)為k位，例110101101

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

8、數(shù)據(jù)能否被10011整除。如果可以，認(rèn)為沒有出錯(cuò)；如果不能，通知發(fā)端重發(fā)。上面的例子是一個(gè)（13，9）檢錯(cuò)碼。第3節(jié) 混合糾錯(cuò)碼舉例一個(gè)（7，3）碼：2103210(, ,)m m m c c c c3202210121010cmmcmmmcmmcmm校驗(yàn)位生成規(guī)則：合法碼字：000000000111010100111011101010011101010011110100111101002103210, , ,m m m c c c c合法碼字生成規(guī)則：2103210210210,1001110, 01001110011101,mmmccccmmmmmmGG為生成矩陣3202210121010

9、cmmcmmmcmmcmm20321022111000000mmcmmmcmmcmmc2211003322110001 0 1 1 0 0 001 1 1 0 1 0 001 1 0 0 0 1 000 1 1 0 0 0 1mmmmmmHccccccccH為校驗(yàn)矩陣，當(dāng)校驗(yàn)結(jié)果為0，則認(rèn)為沒有錯(cuò)，否則有錯(cuò)證明：4 33 400TTHGGH1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1H 觀察校驗(yàn)矩陣HH的每一列都不一樣任意兩列的和都不等于H的其它列第1列加第2列等于第4列加第7列第4，5，6列的和等于第1列第1，4，5，6列的和等于0

10、2103210mmmcEccc出錯(cuò)假設(shè)：E可能有0000001到1111111共127種情況，E稱為出錯(cuò)圖樣。210321000()00mmmHcEH EH ESccc校驗(yàn)：有1位錯(cuò)：1000000010000000100000 , 0 , 0 , 1 , 0 , 0 , 0000010000000100000001E 1011000101100011101001110100,1100010110001001100010110001SHEE S不為0，一定有錯(cuò)，且根據(jù)S的具體值知道哪一位出錯(cuò)。有2位錯(cuò)：1100000E 11011000011101000110001010110001SHEE

11、0001001E 11011000011101000110001010110001SHEE S不為0，一定有錯(cuò)，但不知哪2位出錯(cuò)。因?yàn)槿我鈨闪械暮投疾坏扔贖的其它列，所以不會誤認(rèn)為1位錯(cuò)。有3位錯(cuò)：11011000111101001110001000110001SHEE 0001110E 11011000111101001110001000110001SHEE S不為0，一定有錯(cuò)。會誤認(rèn)為第1位錯(cuò)，從而誤糾錯(cuò)。1000000E 有4位錯(cuò)：01011000011101000110001000110001SHEE 1001110E S為0，誤認(rèn)為沒有錯(cuò)。上例編碼的檢糾錯(cuò)能力：1、能夠檢出1位2位3位錯(cuò)。2、能夠糾正1位錯(cuò)。3、能夠?qū)?位錯(cuò)不誤糾正。4、對3位錯(cuò)會誤糾。5、對4位錯(cuò)會誤檢。S等于H中和錯(cuò)誤圖樣相對應(yīng)的列之和。可以從H得出編碼的糾錯(cuò)能力。該碼可以用于HCE方式。 在實(shí)際應(yīng)用中，比特差錯(cuò)經(jīng)常成串發(fā)生，而信道編碼僅在檢測和校正單個(gè)差錯(cuò)和不太長的差錯(cuò)串時(shí)才最有效。 為了糾正這些成串發(fā)生的比特差錯(cuò)，交織技術(shù)對已編碼的信號按一定規(guī)則重新排列，解交織后突發(fā)性錯(cuò)誤在位置上被分散，使其類似于獨(dú)立發(fā)生的隨機(jī)錯(cuò)誤。 交織編碼和糾錯(cuò)編碼連用。一般來說，在發(fā)端先對數(shù)據(jù)進(jìn)