錯誤檢測和校正

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

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

3、碼。例2：一個（4，2）分組碼（c3,c2,c1,c0），信息碼字(c3,c2)可能為00，01，10，11，校驗碼字定義為c1=c2,c0=c3+c2。則碼字可能為：0000，0111，1001，1110。例1和例2中的發(fā)送碼字為合法碼字，如果接受端收到非法碼字則說明發(fā)生錯誤。例3：奇偶校驗碼 規(guī)則：在k個信息源后加上1位校驗元，使得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 11

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

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

6、種方式的結(jié)合。發(fā)送端發(fā)送的碼即能檢錯，又能糾錯。譯碼器如果發(fā)現(xiàn)錯誤可以糾正就自動糾正，如果錯誤不能糾正，則通知發(fā)端重發(fā)。 CRC,奇偶校驗碼和重復碼都不屬于這類編碼。第2節(jié) CRC（Cyclic Redundancy Code）檢錯編碼基本思想：1、除法被除數(shù)x，除數(shù)y，商z，余數(shù)C。有： x=yz+c x-c=yz所以，x-c肯定可以被y整除。2、二進制數(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（k=

7、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校驗碼。解碼：看收到的數(shù)據(jù)能

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

9、cmmmcmmcmm20321022111000000mmcmmmcmmcmmc2211003322110001 0 1 1 0 0 001 1 1 0 1 0 001 1 0 0 0 1 000 1 1 0 0 0 1mmmmmmHccccccccH為校驗矩陣，當校驗結(jié)果為0，則認為沒有錯，否則有錯證明：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 觀察校驗矩陣HH的每一列都不一樣任意兩列的和都不等于H的其它列第1列加第2列等于第4列加第7列第4，5，6列的和等于第1列第1，4，5，6列的和等于0210

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

11、1001E 11011000011101000110001010110001SHEE S不為0，一定有錯，但不知哪2位出錯。因為任意兩列的和都不等于H的其它列，所以不會誤認為1位錯。有3位錯：11011000111101001110001000110001SHEE 0001110E 11011000111101001110001000110001SHEE S不為0，一定有錯。會誤認為第1位錯，從而誤糾錯。1000000E 有4位錯：01011000011101000110001000110001SHEE 1001110E S為0，誤認為沒有錯。上例編碼的檢糾錯能力：1、能夠檢出1位2位3位錯。

12、2、能夠糾正1位錯。3、能夠?qū)?位錯不誤糾正。4、對3位錯會誤糾。5、對4位錯會誤檢。S等于H中和錯誤圖樣相對應(yīng)的列之和。可以從H得出編碼的糾錯能力。該碼可以用于HCE方式。 在實際應(yīng)用中，比特差錯經(jīng)常成串發(fā)生，而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時才最有效。 為了糾正這些成串發(fā)生的比特差錯，交織技術(shù)對已編碼的信號按一定規(guī)則重新排列，解交織后突發(fā)性錯誤在位置上被分散，使其類似于獨立發(fā)生的隨機錯誤。 交織編碼和糾錯編碼連用。一般來說，在發(fā)端先對數(shù)據(jù)進行糾錯編碼，然后再進行交積處理。第4節(jié) 交織編碼技術(shù)交織的原理圖：光盤用到的編碼技術(shù)：CRC碼RS碼：也是一個（n,k）線性分組碼。但是它有糾正(n-k)/2個錯誤的能力。CIRC碼：RS編碼和交織技術(shù)相結(jié)合形成CIRC碼，用在CD-ROM中。RSPC碼:基本思想用兩次RS編碼對數(shù)據(jù)矩陣的行和列編碼，使得誤碼率進一步降低。ECC碼:在RSPC的基礎(chǔ)上對行和列做交織處理。n檢錯糾錯編碼屬于信道編碼。n選用什么編碼算法首先需要知道信道的特性。n從信息的角度說，糾錯編碼是通過加大數(shù)據(jù)量來換取準確率。n交織技