信息論與編碼理論-信道編碼-線性分組碼2

2023/2/51Tochoosetimeistosavetime2023/2/526.2.1一般概念6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2.3線性分組碼的生成矩陣6.2.4線性分組碼的編碼6.2.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力6.2.6線性分組碼的譯碼6.2.7線性分組碼的性能6.2.8漢明碼6.2.9由已知碼構(gòu)造新碼的方法6.2.10線性分組碼的碼限6.2線性分組碼2023/2/53(2)糾錯(cuò)譯碼①最佳譯碼準(zhǔn)則（最大似然譯碼）通信是一個(gè)統(tǒng)計(jì)過程，糾、檢錯(cuò)能力最終要反映到差錯(cuò)概率上。對(duì)于FEC方式，采用糾錯(cuò)碼后的碼字差錯(cuò)概率為pwe，p(C)：發(fā)送碼字C的先驗(yàn)概率p(C/R)：后驗(yàn)概率若碼字?jǐn)?shù)為2k，對(duì)充分隨機(jī)的消息源有p(C)=1/2k，所以最小化的pwe等價(jià)為最小化p(C’≠C│R)，又等價(jià)為最大化p(C’=C│R)；6.2.6線性分組碼的譯碼2023/2/54對(duì)于BSC信道：最大化的p(C’=C│R)等價(jià)于最大化的p(R│C)，最大化的p(R│C)又等價(jià)于最小化d(R,C)，所以使差錯(cuò)概率最小的譯碼是使接收向量R與輸出碼字C’距離最小的譯碼。6.2.6線性分組碼的譯碼2023/2/55②標(biāo)準(zhǔn)陣列碼矢參數(shù)發(fā)送碼矢：取自于2k個(gè)碼字集合{C}；接收矢量：可以是2n個(gè)n重中任一個(gè)矢量。譯碼方法把2n個(gè)n重劃分為2k個(gè)互不相交的子集，使得在每個(gè)子集中僅含一個(gè)碼矢；根據(jù)碼矢和子集間一一對(duì)應(yīng)關(guān)系，若接收矢量Rl落在子集Dl中，就把Rl譯為子集Dl含有的碼字Cl；當(dāng)接收矢量R與實(shí)際發(fā)送碼矢在同一子集中時(shí)，譯碼就是正確的。標(biāo)準(zhǔn)陣列：是對(duì)給定的(n,k)線性碼，將2n個(gè)n重劃分為2k個(gè)子集的一種方法。6.2.6線性分組碼的譯碼2023/2/56標(biāo)準(zhǔn)陣列構(gòu)造方法先將2k個(gè)碼矢排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全0碼矢C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個(gè)n重中選取一個(gè)重量最輕的n重E2放在全0碼矢C1下面，再將E2分別和碼矢相加，放在對(duì)應(yīng)碼矢下面構(gòu)成陣列第二行；在第二次剩下的n重中，選取重量最輕的n重E3，放在E2下面，并將E3分別加到第一行各碼矢上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到表6.2.2所示的給定(n,k)線性碼的標(biāo)準(zhǔn)陣列。6.2.6線性分組碼的譯碼2023/2/576.2.6線性分組碼的譯碼2023/2/58標(biāo)準(zhǔn)陣列的特性定理6.2.5：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且2n個(gè)n重中任一個(gè)n重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。[證明]：因?yàn)殛嚵兄腥我恍卸际怯伤x出某一n重分別與2k個(gè)碼矢相加構(gòu)成的，而2k個(gè)碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)，是用完全部n重為止，因而每個(gè)n重必出現(xiàn)一次；每個(gè)n重只能出現(xiàn)一次。假定某一n重X出現(xiàn)在第l行第i列，那么X＝El+Ci，又假設(shè)X出現(xiàn)在第m行第j列，那么X＝Em+Cj，l<m，6.2.6線性分組碼的譯碼2023/2/59因此El+Ci=Em+Cj，移項(xiàng)得Em=El+Ci+Cj

而Ci+Cj也是一個(gè)碼矢，設(shè)為Cs，于是Em=El+Cs，這意味著Em是第l行中的一個(gè)矢量，但Em是第m行(m>l)的第一個(gè)元素，而按陣列構(gòu)造規(guī)則，后面行的第一個(gè)元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。6.2.6線性分組碼的譯碼2023/2/510定理6.2.6(線性碼糾錯(cuò)極限定理)：二元(n,k)線性碼能糾2n－k個(gè)錯(cuò)誤圖樣。這2n－k個(gè)可糾的錯(cuò)誤圖樣，包括0矢量在內(nèi)，即把無錯(cuò)的情況也看成一個(gè)可糾的錯(cuò)誤圖樣。[證明]：(n,k)線性碼的標(biāo)準(zhǔn)陣列有2k列（和碼矢矢量相等），2n/2k=2n－k行，且任何兩列和兩行都沒有相同的元素。陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。陪集首：每個(gè)陪集的第一個(gè)元素叫做陪集首。每一列包含2n－k個(gè)元素，最上面的是一個(gè)碼矢，其它元素是陪集首和該碼矢之和，例如第j列為6.2.6線性分組碼的譯碼2023/2/511若發(fā)送碼矢為Cj，信道干擾的錯(cuò)誤圖樣是陪集首，則接收矢量R必在Dj中；若錯(cuò)誤圖樣不是陪集首，則接收矢量R不在Dj中，則譯成其它碼字，造成錯(cuò)誤譯碼；當(dāng)且僅當(dāng)錯(cuò)誤圖樣為陪集首時(shí)，譯碼才是正確的?？杉m正的錯(cuò)誤圖樣：這2n－k個(gè)陪集首稱為可糾正的錯(cuò)誤圖樣。6.2.6線性分組碼的譯碼2023/2/512線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系：一個(gè)可糾t個(gè)錯(cuò)誤的線性碼必須滿足

上式中等式成立時(shí)的線性碼稱為完備碼。即[證明]：糾一個(gè)錯(cuò)誤的(n,k)線性碼，必須能糾正個(gè)錯(cuò)誤圖樣，因此6.2.6線性分組碼的譯碼2023/2/513對(duì)糾兩個(gè)錯(cuò)誤的(n,k)線性碼，必須能糾個(gè)錯(cuò)誤圖樣，所以依此類推，一個(gè)糾t個(gè)錯(cuò)誤的(n,k)線性碼必須滿足對(duì)于完備碼，由碼的糾錯(cuò)能力所確定的伴隨式數(shù)恰好等于可糾的錯(cuò)誤圖樣數(shù)，所以完備碼的(n－k)個(gè)監(jiān)督碼元得到了充分的利用。6.2.6線性分組碼的譯碼2023/2/514定義：(n,k)線性碼的所有2n－k個(gè)伴隨式，在譯碼過程中若都用來糾正所有小于等于個(gè)隨機(jī)錯(cuò)誤，以及部分大于t的錯(cuò)誤圖樣，則這種譯碼方法稱為完備譯碼。限定距離譯碼：任一個(gè)(n,k)線性碼，能糾正個(gè)隨機(jī)錯(cuò)誤，如果在譯碼時(shí)僅糾正t’<t個(gè)錯(cuò)誤，而當(dāng)錯(cuò)誤個(gè)數(shù)大于t’時(shí)，譯碼器不進(jìn)行糾錯(cuò)而僅指出發(fā)生了錯(cuò)誤，稱這種方法為限定距離譯碼。6.2.6線性分組碼的譯碼2023/2/515從多維矢量空間的角度看完備碼：假定圍繞每一個(gè)碼字Ci放置一個(gè)半徑為t的球，每個(gè)球內(nèi)包含了與該碼字漢明距離小于等于t的所有接收碼字R的集合；這樣，在半徑為t=[(dmin－1)/2]的球內(nèi)的接收碼字?jǐn)?shù)是因?yàn)橛?k個(gè)可能發(fā)送的碼字，也就有2k個(gè)不相重疊的半徑為t的球。包含在2k個(gè)球中的碼字總數(shù)不會(huì)超過2n個(gè)可能的接收碼字。于是一個(gè)糾t個(gè)差錯(cuò)的碼必然滿足不等式如果上式中等號(hào)成立，表示所有的接收碼字都落在2k個(gè)球內(nèi)，而球外沒有一個(gè)碼，這就是完備碼。6.2.6線性分組碼的譯碼

Here2023/2/516完備碼特性：圍繞2k個(gè)碼字，漢明距離為t=[(dmin－1)/2]的所有球都是不相交的，每一個(gè)接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為t，這時(shí)所有重量≤t的錯(cuò)誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t+1的錯(cuò)誤圖樣都不能糾正。6.2.6線性分組碼的譯碼2023/2/517舉例：對(duì)糾一個(gè)錯(cuò)誤的(7,4)漢明碼，可見，(7,4)漢明碼是一個(gè)完備碼。所有漢明碼都是完備碼（滿足2n－k=2m=n+1）。標(biāo)準(zhǔn)陣列譯碼=最小距離譯碼法=最佳譯碼法陪集首是可糾正的錯(cuò)誤圖樣，為了使譯碼錯(cuò)誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯(cuò)誤圖樣作陪集首；重量較輕的錯(cuò)誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)是選取重量最輕的n重作陪集首；這樣，當(dāng)錯(cuò)誤圖樣為陪集首時(shí)（可糾的錯(cuò)誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；6.2.6線性分組碼的譯碼2023/2/518因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼；所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。定理6.2.7：在標(biāo)準(zhǔn)陣列中，一個(gè)陪集的所有2k個(gè)n重有相同的伴隨式，不同的陪集伴隨式互不相同。[證明]：設(shè)H為給定(n,k)線性碼的監(jiān)督矩陣，在陪集首為El的陪集中的任意矢量R為R=El+Ci,i=1,2,…,2k其伴隨式為S=RHT=(El+Ci)HT=ElHT+CiHT=ElHT上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同所以伴隨式不同。6.2.6線性分組碼的譯碼2023/2/519③結(jié)論任意n重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對(duì)應(yīng)的，因而碼的可糾錯(cuò)誤圖樣和伴隨式是一一對(duì)應(yīng)的，應(yīng)用此對(duì)應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到(n,k)線性碼的一般譯碼步驟。(n,k)線性碼的一般譯碼步驟計(jì)算接收矢量R的伴隨式ST=HRT；根據(jù)伴隨式和錯(cuò)誤圖樣一一對(duì)應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出R的錯(cuò)誤圖樣E；將接收字減錯(cuò)誤圖樣，得發(fā)送碼矢的估值C’=R－E。6.2.6線性分組碼的譯碼2023/2/520上述譯碼法稱為伴隨式譯碼法或查表譯碼法。線性分組碼一般譯碼器譯碼器如圖6.2.9。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯(cuò)誤概率，原則上可用于任何(n,k)線性碼。6.2.6線性分組碼的譯碼2023/2/521在通信中檢糾錯(cuò)碼的實(shí)際性能是在統(tǒng)計(jì)上體現(xiàn)出來的。以下分析均以BSC信道為模型。(1)不可檢錯(cuò)誤概率(2)譯碼錯(cuò)誤概率(3)譯碼失敗概率(4)比特誤碼率6.2.7線性分組碼的性能2023/2/522(1)不可檢錯(cuò)誤概率pud由(n,k)線性碼的重量分布求pud令A(yù)i為碼的重量分布，表示重量為i的碼字個(gè)數(shù)，i=0,1,2,…,n；由于僅當(dāng)錯(cuò)誤圖樣與碼矢集合中的非0碼矢相同時(shí)，才不能檢出錯(cuò)誤，所以（p是BSC的誤碼率，且碼字等概發(fā)送）舉例：(7,3)碼的重量分布是A0=1,A1=A2=A3=0,A4=7，其不可檢錯(cuò)誤概率為pud＝7×p4(1－p)3，若p=0.01，則pud≈6.8×10－8。利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud設(shè)A0,A1,A2,…,An是(n,k)碼的重量分布；B0,B1,B2,…,Bn是它的對(duì)偶碼的重量分布；6.2.7線性分組碼的性能2023/2/523對(duì)偶碼的重量枚舉式：下面的多項(xiàng)式稱為(n,k)碼和它的對(duì)偶碼的重量枚舉式。MacWilliams恒等式：若已知線性碼的對(duì)偶碼的重量分布，就可確定該碼本身的重量分布。由式(6.2.23)得6.2.7線性分組碼的性能2023/2/524令將這個(gè)恒等式代入式(6.2.26)得將恒等式和(6.2.25)代入上式得.6.2.7線性分組碼的性能2023/2/525當(dāng)k<(n－k)時(shí)，用式(6.2.28)計(jì)算pud比較簡單；當(dāng)k>(n－k)時(shí)，用式(6.2.29)計(jì)算pud則更容易。舉例：已知(7,4)碼的監(jiān)督矩陣H(7,4)，它等于其對(duì)偶碼的生成矩陣G(7,3)，即由此生成矩陣的行的線性組合，可得到(7,3)碼的8個(gè)碼字由此得到(7,3)對(duì)偶碼的重量枚舉式為B(x)=1+7x4利用式(6.2.29)得出(7,4)碼的未檢出錯(cuò)誤概率為pud=2－3[1+7×(1－2p)4]－(1－p)7設(shè)p=0.01，則pud=6×10－6。6.2.7線性分組碼的性能2023/2/526(2)譯碼錯(cuò)誤概率pwe正確譯碼概率pwc：糾正小于等于t個(gè)差錯(cuò)的概率譯碼錯(cuò)誤概率pwe譯碼錯(cuò)誤發(fā)生在差錯(cuò)數(shù)目大于t，接收向量R與另一碼字C’的距離小于等于t的情況；Di是重量i并譯為錯(cuò)誤碼字的可能的接收向量R的數(shù)目，即譯碼錯(cuò)誤概率pwe為6.2.7線性分組碼的性能2023/2/527(3)譯碼失敗概率pwf由于仍存在不滿足式(6.2.30)的接收碼矢R，對(duì)于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即pwf=1－pwc－pwe圖6.2.30中RA—正確譯碼概率RB—譯碼錯(cuò)誤概率RC—譯碼失敗概率6.2.7線性分組碼的性能2023/2/528(4)比特誤碼率pbc：信道的比特差錯(cuò)概率，對(duì)于BSC信道，pbc等于信道轉(zhuǎn)移概率p。pbd：譯碼錯(cuò)誤導(dǎo)致的碼字之間的比特差錯(cuò)率。pbm：消息源與消息接收終端之間的比特差錯(cuò)概率。一般認(rèn)為消息和碼字之間的映射不改變碼字差錯(cuò)導(dǎo)致在整個(gè)碼長內(nèi)比特差錯(cuò)的均勻分布特性，在統(tǒng)計(jì)意義上有pbm≈pbd6.2.7線性分組碼的性能2023/2/529pbe譯碼錯(cuò)誤的誤碼率：設(shè)碼字是等概率發(fā)送，則是發(fā)送全0碼字并錯(cuò)接收為重量為j的碼字的概率；Pbe與pwe的關(guān)系碼字錯(cuò)必然有至少2t+1位碼字比特錯(cuò)；每個(gè)碼字平均有位消息比特錯(cuò)，所以pbe與pwe有如下漸進(jìn)關(guān)系6.2.7線性分組碼的性能2023/2/530pbf譯碼失敗造成的誤碼率pbd譯碼后總的誤碼率：pbd=pbe+pbf6.2.7線性分組碼的性能2023/2/531漢明碼是漢明于1950年提出的糾一個(gè)錯(cuò)誤的線性碼，也是第一個(gè)糾錯(cuò)碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。漢明碼的結(jié)構(gòu)參數(shù)：糾一個(gè)錯(cuò)誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無關(guān)/H的任兩列互不相同；沒有全0的列。監(jiān)督元個(gè)數(shù)n－k=r；H陣中每列有r個(gè)元素，至多可構(gòu)成2r－1種互不相同的非0列。對(duì)于任意正整數(shù)m≥3，漢明碼的結(jié)構(gòu)參數(shù)為碼長：n=2m－1信息位數(shù)：k=2m－m－1監(jiān)督位數(shù)：n－k=m碼的最小距離：dmin=3(t=1)6.2.8漢明碼2023/2/532漢明碼監(jiān)督矩陣構(gòu)成的兩種方式構(gòu)成H陣的標(biāo)準(zhǔn)形式，H=[QIm]，其中Im為m階單位子陣，子陣Q是構(gòu)造Im后剩下的列任意排列。用這種形式的H陣編出的漢明碼是系統(tǒng)碼。按m重（重量為m）表示的二進(jìn)制順序排列。按這種形式H陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為H陣中對(duì)應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值就是錯(cuò)誤位置號(hào)，有時(shí)這種碼譯碼比較方便。由于漢明碼可糾的錯(cuò)誤圖樣數(shù)為6.2.8漢明碼2023/2/533(1)擴(kuò)展/Extending和打孔/Puncturing(2)增廣/Augmenting和刪信/Expunging/Expurgating(3)延長/Lengthening和縮短/Shortening(4)乘積/Product(5)級(jí)聯(lián)/Concatenating(6)交織/Interleaving6.2.9由已知碼構(gòu)造新碼的方法2023/2/534(1)擴(kuò)展/Extending和打孔/Puncturing擴(kuò)展：保持碼字?jǐn)?shù)k不變，增加冗余位數(shù)以增加碼長。打孔：保持k不變，減小冗余位?？梢哉J(rèn)為是擴(kuò)展的逆過程。(2)增廣/Augmenting和刪信/Expunging/Expurgating增廣：保持n不變，增加碼字?jǐn)?shù)目k。刪信：保持n不變減小k。(3)延長/Lengthening和縮短/Shortening延長：同時(shí)增加k和n。縮短：同時(shí)減小k和n。6.2.9由已知碼構(gòu)造新碼的方法2023/2/535舉例：(7,4,3)漢明碼的各種修正關(guān)系如圖6.2.31所示。6.2.9由已知碼構(gòu)造新碼的方法2023/2/536(4)乘積/Product消息作為陣列，分別進(jìn)行行列編碼。(5)級(jí)聯(lián)/Concatenating對(duì)消息編碼后的碼字再進(jìn)行一次編碼。級(jí)聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內(nèi)碼。級(jí)聯(lián)編碼常用于既有隨機(jī)差錯(cuò)又有突發(fā)差錯(cuò)的信道編碼。(6)交織/Interleaving交織編碼分為分組交織和卷積交織兩種。如果交織編碼所用的(n,k)碼可以糾正t個(gè)隨機(jī)差錯(cuò)，那么交織深度為D的交織編碼可以糾正Dt長的突發(fā)錯(cuò)誤。6.2.9由已知碼構(gòu)造新碼的方法2023/2/537舉例：視盤存儲(chǔ)的糾錯(cuò)編碼采用對(duì)(31,21)糾雙錯(cuò)的BCH碼進(jìn)行256深度的交織，可以有效糾正因?yàn)榻橘|(zhì)損壞、磁（光）頭污染或者定時(shí)抖動(dòng)等引起的連續(xù)差錯(cuò)。6.2.9由