信息與編碼理論 第2版 課件 5.4 線性分組碼的檢錯和糾錯能力

§5.4線性分組碼的檢錯和糾錯能力通過一個例子來討論線性分組碼的檢錯和糾錯能力。圖中和表示兩個合法碼字，它們之間的漢明距離為5，而圖中的實心圓點表示發(fā)送碼字受擾后可能得到的接收向量。根據(jù)最大似然譯碼準(zhǔn)則，如果接收向量落在區(qū)域1則譯碼為，如果接收向量落在區(qū)域2則譯碼為。如果接收向量如圖(a)中的，即離和的距離分別為1和4，那么會將譯碼為。假如是碼字發(fā)生1位錯誤的結(jié)果，那么譯碼器便能實現(xiàn)正確的譯碼；假如是碼字發(fā)生4位錯誤的結(jié)果，那么譯碼器會發(fā)生譯碼錯誤。如果接收向量如圖(b)中的，即與和的距離分別為2和3，那么會將譯碼為。假如是碼字發(fā)生2位錯誤的結(jié)果，那么譯碼器便能實現(xiàn)正確的譯碼；假如是碼字發(fā)生3位錯誤的結(jié)果，那么譯碼器會發(fā)生譯碼錯誤。如果接收向量如圖(c)中的，即與和的距離分別為3和2，那么會將譯碼為。假如是碼字發(fā)生2位錯誤的結(jié)果，那么譯碼器便能實現(xiàn)正確的譯碼；假如是碼字發(fā)生3位錯誤的結(jié)果，那么譯碼器會發(fā)生譯碼錯誤。如果將該碼只用于檢錯，那么所有落在圖中實心圓點上的接收向量均可以被檢測出錯誤，即可以檢查出4位以下的錯誤。但是，如果傳輸過程中發(fā)生了5位錯誤，那么一個合法碼字會被錯譯為另一個合法碼字，此時會發(fā)生不可檢測的譯碼錯誤。從上面的討論可以發(fā)現(xiàn)：線性分組碼的檢錯和糾錯能力與該碼的最小碼距之間有著密切的關(guān)系。求得線性分組碼最小碼距的方法：只需要找到所有合法碼字（全零碼字除外）中漢明重量最小的那個碼字，其重量便是該碼的最小碼距。由線性分組碼的定義可知，任意兩個合法碼字之和仍然是一個合法碼字，即對于某個線性分組碼，如果碼字，則有。對于二進(jìn)制線性分組碼而言，由5.2.3小節(jié)的討論可知，兩個碼字之間的漢明距離實際上就是兩個碼字模2相加結(jié)果的漢明重量。可以證明，對于一個最小碼距為的線性分組碼，關(guān)于其檢錯和糾錯能力有如下結(jié)論：如果該碼只用于糾錯，可以確保能夠糾正的錯誤位數(shù)最多為如果該碼只用于檢錯，可以確保檢測出的錯誤位數(shù)最多為如果該碼同時用于糾正個錯誤、檢測個錯誤（），則要求最小碼距和糾錯能力的關(guān)系：討論1：只用于糾錯的公式對于能夠確保糾正個以下錯誤的碼，也可能具有糾正某些個錯誤的能力。例如表5-5中標(biāo)準(zhǔn)陣列給出的(6,3)碼的最小碼距為，因此可以確保糾正1位錯誤，但是也能糾正一個2位的錯誤。一般來說，能夠糾正個錯誤的線性分組碼一共能夠糾正個錯誤圖樣。討論2：只用于檢錯時的公式對于能夠確保可以檢測出位以下錯誤的碼，也有可能檢測出一部分多于位錯誤的錯誤圖樣。一般來說，線性分組碼一共能夠檢測出個錯誤圖樣。因為該碼共有個可能的非零錯誤圖樣，其中有個與非零碼字相同的錯誤圖樣是不能檢測出來的（一個碼字會錯為另一個碼字），因此共有個可以檢測出的錯誤圖樣。譯碼器不能檢測出錯誤的概率對于線性分組碼，令表示重量為的碼字?jǐn)?shù)量，則稱為該碼的重量分布（WeightDistribution）。假如該碼僅用于檢錯并通過二進(jìn)制對稱信道傳輸（錯誤轉(zhuǎn)移概率為），可以證明譯碼器不能檢測出錯誤的概率為如果該碼的最小碼距為，那么顯然從到的值都是0。【例5-8】如果將表5-3中的碼用于檢錯，并假設(shè)傳輸信道為錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道，求該碼不能檢測出錯誤的概率。由表中的碼字可以統(tǒng)計出：，，，，因此，不能檢測出錯誤的概率為討論3：同時糾正個錯誤、檢測個錯誤（）的公式由上式可知：如果不多于個錯誤發(fā)生，該碼可以檢測和糾正這些錯誤；如果多于個但是小于個錯誤發(fā)生，則該碼可以檢測到錯誤的存在但是僅僅能糾正其中一部分。例如，對于最小碼距為的線性分組碼，可以采用下表中的方案之一來進(jìn)行檢錯或糾錯。糾錯意味著首先要檢錯。比如：當(dāng)發(fā)生3位錯誤時，該碼可以檢測所有錯誤并能進(jìn)行糾正；而當(dāng)發(fā)生5位錯誤時，該碼可以檢測出所有錯誤但是僅能糾正其中1位錯誤的情況?！纠?-9】討論重復(fù)碼和重復(fù)碼的檢錯和糾錯能力?！窘狻肯葋砜紤]重復(fù)碼，顯然兩個合法碼字分別是和，且該碼的碼率為，最小碼距為。如果該碼用于檢錯，由可知該碼最多可以檢測出2個錯誤。例如，當(dāng)發(fā)送碼字為時，只要錯誤比特個數(shù)不超過兩個均可以發(fā)現(xiàn)，如下圖：如果該碼用于糾錯，由可知該碼可以糾正1個錯誤。例如下圖，對于發(fā)送碼字，根據(jù)最小距離譯碼準(zhǔn)則，只有當(dāng)接收向量為、或時才能實現(xiàn)正確譯碼，而當(dāng)接收向量為、或時會被錯誤的糾正為碼字。當(dāng)該碼通過錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道傳輸時，譯碼錯誤概率為接著考慮重復(fù)碼，顯然兩個合法碼字分別是和，且該碼的碼率為，最小距離為。如果該碼用于檢錯，由可知該碼最多可以檢測出3個錯誤。例如當(dāng)發(fā)送碼字為時，只要錯誤個數(shù)不超過三個均可以發(fā)現(xiàn)，如下圖：如果只用于糾錯，由可知該碼只可以糾正1個錯誤，如下面左圖所示；如果同時用于檢錯和糾錯，由可知該碼可以同時糾正1個錯誤、檢查出2個錯誤，如下面右圖所示。接收向量為下列情況時可以實現(xiàn)正確譯碼：接收向量為下列情況時可以檢測出錯誤：接收向量為下列情況時會被錯誤的糾正為其他碼字：當(dāng)該碼通過錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道傳輸時，譯碼錯誤概率為討論：隨著碼長的增加，重復(fù)碼的抗干擾能力會越來越強，但是碼率會越來越低，且隨著的增加會趨近于零?！纠?-10】討論碼長分別為時偶校驗碼的檢錯和糾錯能力?！窘狻肯瓤紤]偶校驗碼，顯然該碼只有2個合法碼字，分別為和，且該碼的碼率為，最小碼距為，因此該碼僅能檢測出1個錯誤。若該碼通過錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道傳輸，顯然發(fā)生2位錯誤時譯碼器不能檢測出錯誤，因此譯碼器不能檢測出錯誤的概率為如果用碼字重量來計算，該碼的重量分布為，于是有接著考慮偶校驗碼，顯然該碼有個碼字，分別為該碼的碼率為，最小碼距為，因此該碼也只能檢測出1個錯誤。若該碼通過錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道傳輸時，顯然發(fā)生2位錯誤時譯碼器不能檢測出錯誤，因此譯碼器不能檢測出錯誤的概率為如果用碼字重量來計算，該碼的重量分布為，，于是有再來考慮偶校驗碼，顯然該碼有個碼字，分別為該碼的碼率為，最小碼距為，由公式可知該碼可以確保檢測出1個錯誤，但是容易發(fā)現(xiàn)實際上該碼也可以檢測出所有的3個錯誤。若該碼通過錯誤轉(zhuǎn)移概率為的二進(jìn)制對稱信道傳輸時，顯然發(fā)生2位或4位錯誤時譯碼器不能檢測出錯誤，