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

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