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

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

個n重中選取一個重量最輕的n重E2放在全0碼矢C1下面，再將E2分別和碼矢相加，放在對應碼矢下面構成陣列第二行；在第二次剩下的n重中，選取重量最輕的n重E3，放在E2下面，并將E3分別加到第一行各碼矢上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到表所示的給定(n,k)線性碼的標準陣列。6.2.6線性分組碼的譯碼第六頁，共四十五頁，2022年，8月28日2023/1/1876.2.6線性分組碼的譯碼第七頁，共四十五頁，2022年，8月28日2023/1/188標準陣列的特性定理：在標準陣列的同一行中沒有相同的矢量，而且2n個n重中任一個n重在陣列中出現一次且僅出現一次。

[證明]：因為陣列中任一行都是由所選出某一n重分別與2k個碼矢相加構成的，而2k個碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；在構造標準陣列時，是用完全部n重為止，因而每個n重必出現一次；每個n重只能出現一次。假定某一n重X出現在第l行第i列，那么X＝El+Ci，又假設X出現在第m行第j列，那么X＝Em+Cj，l<m，6.2.6線性分組碼的譯碼第八頁，共四十五頁，2022年，8月28日2023/1/189

因此El+Ci=Em+Cj，移項得Em=El+Ci+Cj

而Ci+Cj也是一個碼矢，設為Cs，于是Em=El+Cs，這意味著Em是第l行中的一個矢量，但Em是第m行(m>l)的第一個元素，而按陣列構造規(guī)則，后面行的第一個元素是前面行中未曾出現過的元素，這就和陣列構造規(guī)則相矛盾。6.2.6線性分組碼的譯碼第九頁，共四十五頁，2022年，8月28日2023/1/1810定理6.2.6(線性碼糾錯極限定理)：二元(n,k)線性碼能糾2n－k個錯誤圖樣。這2n－k個可糾的錯誤圖樣，包括0矢量在內，即把無錯的情況也看成一個可糾的錯誤圖樣。

[證明]：(n,k)線性碼的標準陣列有2k列（和碼矢矢量相等），2n/2k=2n－k行，且任何兩列和兩行都沒有相同的元素。陪集：標準陣列的每一行叫做碼的一個陪集。陪集首：每個陪集的第一個元素叫做陪集首。每一列包含2n－k個元素，最上面的是一個碼矢，其它元素是陪集首和該碼矢之和，例如第j列為6.2.6線性分組碼的譯碼第十頁，共四十五頁，2022年，8月28日2023/1/1811若發(fā)送碼矢為Cj，信道干擾的錯誤圖樣是陪集首，則接收矢量R必在Dj中；若錯誤圖樣不是陪集首，則接收矢量R不在Dj中，則譯成其它碼字，造成錯誤譯碼；當且僅當錯誤圖樣為陪集首時，譯碼才是正確的?？杉m正的錯誤圖樣：這2n－k個陪集首稱為可糾正的錯誤圖樣。6.2.6線性分組碼的譯碼第十一頁，共四十五頁，2022年，8月28日2023/1/1812線性碼糾錯能力與監(jiān)督元數目的關系：一個可糾t個錯誤的線性碼必須滿足

上式中等式成立時的線性碼稱為完備碼。即

[證明]：糾一個錯誤的(n,k)線性碼，必須能糾正個錯誤圖樣，因此6.2.6線性分組碼的譯碼第十二頁，共四十五頁，2022年，8月28日2023/1/1813對糾兩個錯誤的(n,k)線性碼，必須能糾個錯誤圖樣，所以依此類推，一個糾t個錯誤的(n,k)線性碼必須滿足對于完備碼，由碼的糾錯能力所確定的伴隨式數恰好等于可糾的錯誤圖樣數，所以完備碼的(n－k)個監(jiān)督碼元得到了充分的利用。6.2.6線性分組碼的譯碼第十三頁，共四十五頁，2022年，8月28日2023/1/1814定義：(n,k)線性碼的所有2n－k個伴隨式，在譯碼過程中若都用來糾正所有小于等于個隨機錯誤，以及部分大于t的錯誤圖樣，則這種譯碼方法稱為完備譯碼。限定距離譯碼：任一個(n,k)線性碼，能糾正個隨機錯誤，如果在譯碼時僅糾正t’<t個錯誤，而當錯誤個數大于t’時，譯碼器不進行糾錯而僅指出發(fā)生了錯誤，稱這種方法為限定距離譯碼。6.2.6線性分組碼的譯碼第十四頁，共四十五頁，2022年，8月28日2023/1/1815從多維矢量空間的角度看完備碼：假定圍繞每一個碼字Ci放置一個半徑為t

的球，每個球內包含了與該碼字漢明距離小于等于t的所有接收碼字R的集合；這樣，在半徑為t=[(dmin－1)/2]的球內的接收碼字數是因為有2k個可能發(fā)送的碼字，也就有2k個不相重疊的半徑為t的球。包含在2k個球中的碼字總數不會超過2n個可能的接收碼字。于是一個糾t個差錯的碼必然滿足不等式如果上式中等號成立，表示所有的接收碼字都落在2k個球內，而球外沒有一個碼，這就是完備碼。6.2.6線性分組碼的譯碼

Here第十五頁，共四十五頁，2022年，8月28日2023/1/1816完備碼特性：圍繞2k個碼字，漢明距離為t=[(dmin－1)/2]的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為t，這時所有重量≤t的錯誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t+1的錯誤圖樣都不能糾正。6.2.6線性分組碼的譯碼第十六頁，共四十五頁，2022年，8月28日2023/1/1817舉例：對糾一個錯誤的(7,4)漢明碼，可見，(7,4)漢明碼是一個完備碼。所有漢明碼都是完備碼（滿足2n－k=2m=n+1）。標準陣列譯碼=最小距離譯碼法=最佳譯碼法陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應選取出現概率最大的錯誤圖樣作陪集首；重量較輕的錯誤圖樣出現概率較大，所以在構造標準陣列時是選取重量最輕的n重作陪集首；這樣，當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；6.2.6線性分組碼的譯碼第十七頁，共四十五頁，2022年，8月28日2023/1/1818因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼；所以標準陣列譯碼法也是最佳譯碼法。定理：在標準陣列中，一個陪集的所有2k個n重有相同的伴隨式，不同的陪集伴隨式互不相同。

[證明]：設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線性分組碼的譯碼第十八頁，共四十五頁，2022年，8月28日2023/1/1819③結論任意n重的伴隨式決定于它在標準陣列中所在陪集的陪集首。標準陣列的陪集首和伴隨式是一一對應的，因而碼的可糾錯誤圖樣和伴隨式是一一對應的，應用此對應關系可以構成比標準陣列簡單得多的譯碼表，從而得到(n,k)線性碼的一般譯碼步驟。(n,k)線性碼的一般譯碼步驟計算接收矢量R的伴隨式ST=HRT

；根據伴隨式和錯誤圖樣一一對應的關系，利用伴隨式譯碼表，由伴隨式譯出R的錯誤圖樣E；將接收字減錯誤圖樣，得發(fā)送碼矢的估值C’=R－E

。6.2.6線性分組碼的譯碼第十九頁，共四十五頁，2022年，8月28日2023/1/1820

上述譯碼法稱為伴隨式譯碼法或查表譯碼法。線性分組碼一般譯碼器譯碼器如圖。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何(n,k)線性碼。6.2.6線性分組碼的譯碼第二十頁，共四十五頁，2022年，8月28日2023/1/1821

在通信中檢糾錯碼的實際性能是在統(tǒng)計上體現出來的。以下分析均以BSC信道為模型。(1)不可檢錯誤概率(2)譯碼錯誤概率(3)譯碼失敗概率(4)比特誤碼率6.2.7線性分組碼的性能第二十一頁，共四十五頁，2022年，8月28日2023/1/1822(1)不可檢錯誤概率pud由(n,k)線性碼的重量分布求pud令Ai為碼的重量分布，表示重量為i的碼字個數，i=0,1,2,…,n；由于僅當錯誤圖樣與碼矢集合中的非0碼矢相同時，才不能檢出錯誤，所以（p是BSC的誤碼率，且碼字等概發(fā)送）舉例：(7,3)碼的重量分布是A0=1,A1=A2=A3=0,A4=7，其不可檢錯誤概率為

pud＝7×p4(1－p)3，若p=0.01，則pud≈6.8×10－8。利用(n,k)碼重量分布與其對偶碼的重量分布關系求pud設A0,A1,A2,…,An是(n,k)碼的重量分布；B0,B1,B2,…,Bn是它的對偶碼的重量分布；6.2.7線性分組碼的性能第二十二頁，共四十五頁，2022年，8月28日2023/1/1823對偶碼的重量枚舉式：下面的多項式稱為(n,k)碼和它的對偶碼的重量枚舉式。MacWilliams恒等式：若已知線性碼的對偶碼的重量分布，就可確定該碼本身的重量分布。由式(6.2.23)得6.2.7線性分組碼的性能第二十三頁，共四十五頁，2022年，8月28日2023/1/1824令將這個恒等式代入式(6.2.26)得將恒等式和(6.2.25)代入上式得.6.2.7線性分組碼的性能第二十四頁，共四十五頁，2022年，8月28日2023/1/1825當k<(n－k)時，用式(6.2.28)計算pud比較簡單；當k>(n－k)時，用式(6.2.29)計算pud則更容易。舉例：已知(7,4)碼的監(jiān)督矩陣H(7,4)，它等于其對偶碼的生成矩陣G(7,3)，即由此生成矩陣的行的線性組合，可得到(7,3)碼的8個碼字由此得到(7,3)對偶碼的重量枚舉式為B(x)=1+7x4

利用式(6.2.29)得出(7,4)碼的未檢出錯誤概率為

pud=2－3[1+7×(1－2p)4]－(1－p)7

設p=0.01，則pud=6×10－6。6.2.7線性分組碼的性能第二十五頁，共四十五頁，2022年，8月28日2023/1/1826(2)譯碼錯誤概率pwe正確譯碼概率pwc：糾正小于等于t個差錯的概率譯碼錯誤概率pwe譯碼錯誤發(fā)生在差錯數目大于t，接收向量R與另一碼字C’的距離小于等于t的情況；Di是重量i并譯為錯誤碼字的可能的接收向量R的數目，即譯碼錯誤概率pwe為6.2.7線性分組碼的性能第二十六頁，共四十五頁，2022年，8月28日2023/1/1827(3)譯碼失敗概率pwf由于仍存在不滿足式(6.2.30)的接收碼矢R，對于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即

pwf=1－pwc

－pwe

圖中RA—正確譯碼概率RB—譯碼錯誤概率RC—譯碼失敗概率6.2.7線性分組碼的性能第二十七頁，共四十五頁，2022年，8月28日2023/1/1828(4)比特誤碼率pbc：信道的比特差錯概率，對于BSC信道，pbc等于信道轉移概率p。pbd：譯碼錯誤導致的碼字之間的比特差錯率。pbm：消息源與消息接收終端之間的比特差錯概率。一般認為消息和碼字之間的映射不改變碼字差錯導致在整個碼長內比特差錯的均勻分布特性，在統(tǒng)計意義上有pbm≈pbd6.2.7線性分組碼的性能第二十八頁，共四十五頁，2022年，8月28日2023/1/1829pbe譯碼錯誤的誤碼率：設碼字是等概率發(fā)送，則是發(fā)送全0碼字并錯接收為重量為j的碼字的概率；Pbe與pwe的關系碼字錯必然有至少2t+1位碼字比特錯；每個碼字平均有位消息比特錯，所以pbe與pwe有如下漸進關系6.2.7線性分組碼的性能第二十九頁，共四十五頁，2022年，8月28日2023/1/1830pbf譯碼失敗造成的誤碼率pbd譯碼后總的誤碼率：pbd=pbe+pbf6.2.7線性分組碼的性能第三十頁，共四十五頁，2022年，8月28日2023/1/1831漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數據存儲系統(tǒng)中得到廣泛應用的一類線性碼。漢明碼的結構參數：糾一個錯誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無關/H的任兩列互不相同；沒有全0的列。監(jiān)督元個數n－k=r；H陣中每列有r個元素，至多可構成2r－1種互不相同的非0列。對于任意正整數m≥3，漢明碼的結構參數為碼長：n=2m－1信息位數：k=2m－m－1監(jiān)督位數：n－k=m碼的最小距離：dmin=3(t=1)6.2.8漢明碼第三十一頁，共四十五頁，2022年，8月28日2023/1/1832漢明碼監(jiān)督矩陣構成的兩種方式構成H陣的標準形式，H=[QIm]，其中Im為m階單位子陣，子陣Q是構造Im后剩下的列任意排列。用這種形式的H陣編出的漢明碼是系統(tǒng)碼。按m重（重量為m

）表示的二進制順序排列。按這種形式H陣編出的碼是非系統(tǒng)碼。當發(fā)生可糾的單個錯誤時，伴隨式為H陣中對應的列，所以伴隨式的二進制數值就是錯誤位置號，有時這種碼譯碼比較方便。由于漢明碼可糾的錯誤圖樣數為6.2.8漢明碼第三十二頁，共四十五頁，2022年，8月28日2023/1/1833(1)擴展/Extending和打孔/Puncturing(2)增廣/Augmenting和刪信/Expunging/Expurgating(3)延長/Lengthening和縮短/Shortening(4)乘積/Product(5)級聯(lián)/Concatenating(6)交織/Interleaving6.2.9由已知碼構造新碼的方法第三十三頁，共四十五頁，2022年，8月28日2023/1/1834(1)擴展/Extending和打孔/Puncturing擴展：保持碼字數k不變，增加冗余位數以增加碼長。打孔：保持k不變，減小冗余位?？梢哉J為是擴展的逆過程。(2)增廣/Augmenting和刪信/Expunging/Expurgating增廣：保持n不變，增加碼字數目k。刪信：保持n不變減小k。(3)延長/Lengthening和縮短/Shortening延長：同時增加k和n?？s短：同時減小k和n。6.2.9由已知碼構造新碼的方法第三十四頁，共四十五頁，2022年，8月28日2023/1/1835舉例：(7,4,3)漢明碼的各種修正關系如圖所示。6.2.9由已知碼構造新碼的方法第三十五頁，共四十五頁，2022年，8月28日2023/1/1836(4)乘積/Product

消息作為陣列，分別進行行列編碼。(5)級聯(lián)/Concatenating對消息編碼后的碼字再進行一次編碼。級聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內碼。級聯(lián)編碼常用于既有隨機差錯又有突發(fā)差錯的信道編碼。(6)交織/Interleaving交織編碼分為分組交織和卷積交織兩種。如果交織編碼所用的(n,k)碼可以糾正t個隨機差錯，那么交織深度為D的交織編碼可以糾正Dt長的突發(fā)錯誤。6.2.9由已知碼構造新碼的方法第三十六頁，共四十五頁，2022年，8月28日2023/1/1837舉例：視盤存儲的糾錯編碼采用對(31,21)糾雙錯的BCH碼進行256深度的交織，可以有效糾正因為介質損壞、磁（光）頭污染或者定時抖動等引起的連續(xù)差錯。6.2.9由已知碼構造新碼的方法第三十七頁，共四十五頁，2022年，8