信道的糾錯編碼

信道的糾錯編碼1第一頁，共四十九頁，2022年，8月28日信道編碼的糾錯原理信道編碼的目的：提高系統(tǒng)的可靠性實現(xiàn)方法：增加冗余度信道編碼的糾錯原理根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關聯(lián)（約束）。在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤?！m錯碼2第二頁，共四十九頁，2022年，8月28日糾錯碼的分類按功能分：檢錯碼：僅能檢測誤碼。糾錯碼：可糾正誤碼。按信息碼元與監(jiān)督碼元之間的檢驗關系分：線性碼：滿足線性關系。非線性碼：不存在線性關系。

按信息碼元在編碼后是否保持原形式：系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內有確定位置，編碼后的信息碼元保持位置不變。非系統(tǒng)碼：信息位打亂，與編碼前位置不同。3第三頁，共四十九頁，2022年，8月28日糾錯碼的分類按信息碼元與監(jiān)督碼元之間的約束方式不同分：

分組碼：將信息碼元分為k位一組，每組相互獨立，再按編碼規(guī)則變成n位碼（n>k)，其中n-k=r位為監(jiān)督碼元，我們稱之為（n,k)分組碼。本碼組的監(jiān)督碼元僅和本碼組的信息碼元相關。

卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息碼元相關，而且與前面碼組的信息碼元有關。

4第四頁，共四十九頁，2022年，8月28日錯誤圖樣⑴當系統(tǒng)無干擾時R=C⑵當系統(tǒng)有干擾時R=C+E其中，E稱為信道的錯誤圖樣，E=(e0,e1,…,en-1)；ei∈{0,1}；當ei=1，則第i位上有錯；反之，無錯。例：C=00101101E=01001001R=01100100由信道的對稱性可知p(0/1)=p(1/0)=p(e=1)=p反之，若已知R，E則可求出C，這就是糾錯碼的原理，如：E=01001001R=01100100

C=001011015第五頁，共四十九頁，2022年，8月28日檢錯與糾錯的原理⒈編碼效率設：信息碼長度為k，經(jīng)信道編碼后長度為n，則我們定義編碼效率R為：R=k/n⒉幾種簡單的檢糾錯碼奇/偶校驗碼——檢錯碼重復碼——糾錯碼6第六頁，共四十九頁，2022年，8月28日檢錯與糾錯方式和能力⒈檢糾錯方式FEC（前向糾錯）——糾錯ARQ（自動請求重發(fā)）——檢錯⒉幾個概念漢明距離/距離：在線性碼中，兩個碼字U、V

之間對應碼元位上符號取值不同的個數(shù)，稱為碼字U、V

之間的漢明距離。例如：(7,3)碼的兩個碼字U=0011101,V=0100111，它們之間第2、3、4和6位不同。因此，碼字U和V的距離為4。線性分組碼的一個碼字對應于n維線性空間中的一點，碼字間的距離即為空間中兩對應點的距離。7第七頁，共四十九頁，2022年，8月28日檢錯與糾錯方式和能力最小碼距：在碼集合中，任兩個碼字間的距離為最小時，該碼距即為碼集合的最小碼距。碼字的重量：碼字中非0碼元符號的個數(shù)，稱為該碼字的重量，又稱為漢明重量。碼的最小重量：線性分組碼CI中，非0碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}最小碼距與最小重量的關系：線性分組碼的最小碼距等于它的最小重量。8第八頁，共四十九頁，2022年，8月28日檢錯與糾錯能力--1最小碼距與糾錯能力的關系：定理：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為dmin=2t

+1或t

=(dmin－1)/2V’9第九頁，共四十九頁，2022年，8月28日檢錯與糾錯能力--2最小碼距與檢錯能力的關系：定理：(n,k)線性碼能夠發(fā)現(xiàn)e個錯誤的充要條件是碼的最小距離為dmin=e+1或e=dmin－1V’e10第十頁，共四十九頁，2022年，8月28日檢錯與糾錯能力--3最小碼距與檢、糾錯能力的關系：定理：(n,k)線性碼能糾t個錯誤，并能發(fā)現(xiàn)e個錯誤(e>t)的充要條件是碼的最小距離為dmin=t+e+1或t+e=dmin－1eV’V’’11第十一頁，共四十九頁，2022年，8月28日線性分組碼

一、線性分組碼的描述線性分組碼是同時具有分組特性和線性特性的糾錯碼。定義：一個（n,k）線性分組碼C是稱為碼字c的n維向量的集合。式中：為消息矢量，是一個k行n列的秩為k（n﹥k)的矩陣，我們稱它為線性碼的生成矩陣。第一種編碼方法12第十二頁，共四十九頁，2022年，8月28日線性分組碼例：（4,3）偶校驗碼是一個（4,3）線性分組碼，其生成矩陣為

求消息碼010，110所對應的線性碼。解：13第十三頁，共四十九頁，2022年，8月28日線性分組碼將消息碼直接代入有：思考：此碼是否為系統(tǒng)碼？14第十四頁，共四十九頁，2022年，8月28日線性分組碼二、線性分組碼的性質及定理當消息碼為零向量0…0，所得的碼字為零碼字0…0。

線性分組碼的封閉性：線性分組碼中任意兩個碼字之和仍然是該碼的碼字。G中每一行gi=(gin-1,gin-2,…,gi0

)都是一個碼字；對每一個信息組m，由矩陣G都可以求得(n,k)線性碼對應的碼字。信息碼組長k位，有2k個不同的信息碼組，則有2k

個碼字與它們一一對應。在由(n,k)線性碼構成的線性空間Vn

的k維子空間中，一定存在k個線性獨立的碼字：g0,g1,…,gk-1，碼Ci中其它任何碼字C都可以表為這k個碼字的一種線性組合，即15第十五頁，共四十九頁，2022年，8月28日線性分組碼16第十六頁，共四十九頁，2022年，8月28日線性分組碼三、線性分組碼的監(jiān)督陣⒈線性分組碼的監(jiān)督陣編碼就是給已知信息碼組按預定規(guī)則添加監(jiān)督碼元，以構成碼字。在k個信息碼元之后附加r(r=n－k)個監(jiān)督碼元，使每個監(jiān)督碼元是其中某些信息碼元的模2和。舉例：k=3,r=4，構成(7,3)線性分組碼。設碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個碼元取“0”或“1”監(jiān)督元可按下面方程組計算17第十七頁，共四十九頁，2022年，8月28日線性分組碼一致監(jiān)督方程/一致校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運算關系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。第二種編碼方法18第十八頁，共四十九頁，2022年，8月28日線性分組碼信息碼組(101)，即C6=1,C5=0,C4=1代入監(jiān)督方程得：C3=0,C2=0,C1=1,C0=1由信息碼組(101)編出的碼字為(1010011)。其它7個碼字如下。表9.1

(7,3)分組碼編碼表

信息組

對應碼字

000

0000000

001

0011101

010

0100111

011

0111010

100

1001110

101

101

0011

110

1101001

111

1110100

19第十九頁，共四十九頁，2022年，8月28日線性分組碼為了運算方便，將監(jiān)督方程寫成矩陣形式，得:20第二十頁，共四十九頁，2022年，8月28日線性分組碼推廣到一般情況：對(n,k)線性分組碼，每個碼字中的r(r=n－k)個監(jiān)督元與信息元之間的關系可由下面的線性方程組確定

令上式的系數(shù)矩陣為H，碼字行陣列為C同樣有我們稱H為一致監(jiān)督陣/監(jiān)督陣。21第二十一頁，共四十九頁，2022年，8月28日線性分組碼一致監(jiān)督陣H22第二十二頁，共四十九頁，2022年，8月28日線性分組碼⒉監(jiān)督陣與生成陣的關系由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足Hr×nCTn×1=0Tr×1，則有Hr×nGTn×k=0Tr×k

或

Gk×nHTn×r=0k×r線性分組碼的監(jiān)督矩陣與生成矩陣正交。

23第二十三頁，共四十九頁，2022年，8月28日四、(n,k)線性碼的對偶碼對偶碼：對一個(n,k)線性碼CI，由于Hr×nGTn×k=0Tr×k，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構造另一個碼CId，碼CId是一個(n,n－k)線性碼，稱碼CId為原碼的對偶碼。

例如：(7,4)線性碼的對偶碼是(7,3)碼：(7,3)碼的監(jiān)督矩陣H(7,3)是(7,4)碼生成矩陣G(7,4)線性分組碼24第二十四頁，共四十九頁，2022年，8月28日線性分組碼五、生成陣和監(jiān)督陣的標準形式⒈生成陣的標準形式通過行初等變換，將G化為左邊k列是單位子陣的標準形式，我們稱之為生成陣的標準形式25第二十五頁，共四十九頁，2022年，8月28日線性分組碼⒉線性系統(tǒng)分組碼用生成陣的標準形式產(chǎn)生的碼集合稱為線性系統(tǒng)分組碼。設：則有：則有：依次排在碼的前面監(jiān)督元依次排在碼的后部26第二十六頁，共四十九頁，2022年，8月28日線性分組碼線性系統(tǒng)分組碼：用標準生成矩陣Gk×n

編成的碼字，前面k位為信息數(shù)字，后面r=n－k位為校驗數(shù)字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼。信息碼監(jiān)督碼Cn-1Cn-k

Cn-k-1C027第二十七頁，共四十九頁，2022年，8月28日線性分組碼例：(7,4)線性碼的生成矩陣為110100001101001110010101000174úúúú?ùêêêê?é=*G[])1010011(11010000110100111001010100010101)1010(74417141=úúúú?ùêêêê?é===****GmCm，則若28第二十八頁，共四十九頁，2022年，8月28日線性分組碼⒊監(jiān)督陣的標準形式同樣對監(jiān)督陣的各行進行初等變換，將右邊r列化為單位陣即可得到監(jiān)督陣的標準形式。29第二十九頁，共四十九頁，2022年，8月28日線性分組碼⒋監(jiān)督陣與生成陣的轉換關系由于系統(tǒng)碼的監(jiān)督陣與生成陣同樣彼此正交，所以有：所以，上述等式提供了監(jiān)督陣與生成陣的互求。即，30第三十頁，共四十九頁，2022年，8月28日線性分組碼例：31第三十一頁，共四十九頁，2022年，8月28日線性分組碼例：二元(7,3)碼，若生成矩陣已知，求生成矩陣和監(jiān)督矩陣的標準形式。解：得：②行和③行相加放入第②行①行和②行相加放入第③行32第三十二頁，共四十九頁，2022年，8月28日線性分組碼六、線性碼的最小距離與監(jiān)督陣的關系定理1設H為(n,k)線性碼的一致監(jiān)督陣，若H中任意S列線性無關，而存在S+1列線性相關，則碼的最小距離為S+1。即，dmin=S+1定理2

若碼的最小距離為S+1，則該碼的監(jiān)督陣有任意S列線性無關，而必存在線性相關的S+1列。推理在二元線性碼的監(jiān)督陣H中，如果任一列都不為全零，且任二列都不相等，則該碼能糾一個錯。例：33第三十三頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

一、譯碼器的任務設：發(fā)送的碼字C=(cn

-1，cn-2，…，c1，c0)，通過有擾信道傳輸，信道產(chǎn)生的錯誤圖樣E=(en-1,en-2，…,e1,e0)。接收端譯碼器收到的n重碼R=(rn-1,rn-2,…,r1,r0)，其中R=C+E。譯碼器的任務：根據(jù)編碼規(guī)則和信道特性，對接收碼字R

作出判決，此判決過程又稱為譯碼。譯碼器按任務可分為：檢錯譯碼和糾錯譯碼。檢錯譯碼：輸出接收碼字，及差錯標志。糾錯譯碼：輸出糾正的碼字（在糾錯能力之內）輸出接收碼字及出錯標志。（超出糾錯能力）

34第三十四頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

二、檢糾錯譯碼原理⒈伴隨式和錯誤檢測用監(jiān)督矩陣編碼，當然也用監(jiān)督矩陣譯碼。當收到一個接收碼字R后，可用監(jiān)督矩陣H來檢驗R是否滿足監(jiān)督方程，即HRT＝0T是否成立。若關系式成立，則認為R是一個碼字，否則判為碼字在傳輸中發(fā)生了錯誤。因此，HRT的值是否為0是檢驗碼字出錯與否的依據(jù)。把S＝RHT或ST＝HRT，稱為接收碼字R的伴隨式(或監(jiān)督子，或校驗子)。⒉不可檢測的錯誤圖樣與碼矢相同的錯誤圖樣是不可檢測的錯誤圖樣。它在數(shù)量上與非零碼矢一樣多2k-1個。（含零碼為2k個)35第三十五頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

根據(jù)上述原理，我們可知：⒊伴隨式檢錯原理設：發(fā)送碼字C＝(cn－1,cn－2,…,c0)，信道的錯誤圖樣為E＝(en－1,en－2,…,e0)，式中：若ei＝0，表示第i位無錯，若ei＝1，則表示第i位有錯，i＝n－1，n－2，…，0。那么，接收碼字R=(rn－1,rn－2,…,r0)=C＋E

=(cn－1+en－1，cn－2+en－2，…，c0+e0)檢錯譯碼基本原理判為無錯（可能有錯）一定出錯36第三十六頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

將接收字用監(jiān)督矩陣進行檢驗，即求接收碼字的伴隨式：其中H陣用列來表示，即，所以：ST＝HRT＝H(C＋E)T＝HCT＋HET由于HCT＝

0T，則有：ST＝HET

所以，37第三十七頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

由上面分析得到如下結論：(1)伴隨式僅與錯誤圖樣有關，而與發(fā)送的具體碼字無關，即伴隨式僅由錯誤圖樣決定。(2)伴隨式是錯誤的判別式：若S＝0，則判沒有出錯，（或存在一個不可檢測的錯誤，接收字是一個碼字），若S≠0，則判有錯。(3)不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的，二元碼伴隨式是H陣中與錯誤碼元對應列之和。38第三十八頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

例：設(7,3)線性分組碼的校驗矩陣為試確定以下三種情況時的譯碼器的輸出（1）接收碼字R=(1010011)，（2）接收碼字R=(1110011)，（3）接收碼字R=(0011011)，39第三十九頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

解：對于⑴有：傳輸過程中沒有誤碼，40第四十頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

對于⑵有：，第2位出錯，41第四十一頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

對于⑶有：與中的任一列都不相同，不能確定到底是哪兩位出錯，不能正確譯碼。42第四十二頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

定理：可糾t個錯誤的二元線性分組碼與校驗元個數(shù)的關系：三、采用伴隨式糾錯譯碼的方法⒈查表法⒉標準陣列法幾個概念許用碼組：在(n,k)線性碼中，與2k個消息碼對應的碼字稱為許用碼組。禁用碼組：在(n,k)線性碼中，除了消息碼外的2n-2k個碼字。標準陣列的構造43第四十三頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

先將2k個碼字排成一行，作為標準陣列的第一行，并將全0碼字C0=(00…0)放在第一行的最左邊的位置上；然后在剩下的(2n－2k)

個n重碼中選取一個重量最輕的n重E1放在全0碼字C0下面，再將E1分別和各碼字相加，放在對應碼字下面構成陣列第二行;在第二次剩下的n重碼中，選取重量最輕的n重E2，放在E1下面，并將E2分別加到第一行各碼字上，得到第三行；直到全部n重碼字用完為止。得到(n,k)線性碼的標準陣列。（注意：作為錯誤圖樣的Ei不能與表內的其它碼字相同?。?4第四十四頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

例：已知(6,3)線性分組碼的生成陣為求它的標準陣列。解：由生成陣可得該碼許用碼組的全部碼字：消息碼線性分組碼消息碼線性分組碼00000000010010011000100110110110101101001001111011010101101111011111100045第四十五頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

則它的標準陣列為：00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000010000100001000010000010000100111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101010011101011110011000010100001100001100146第四十六頁，共四十九頁，2022年，8月28日線性分組碼的譯碼

有關標準陣列的幾個概念：(n，k)線性碼的標準陣列有2k列(和碼矢數(shù)相等)，2n/2k＝2n－k行，且任何兩列和兩行都沒有相同的元素，即列和行都不相交。標準陣列的每一行叫做碼的一個陪集，每個陪集的第一個元素叫做陪集首，信道干擾的錯誤圖樣是陪集首。2n－k個陪集首稱為可糾正的錯誤圖樣。這2n－k個可糾的錯誤圖樣，包括

0碼矢在內，也就是說，把無錯的情況也看成一個可糾的錯誤圖樣。定理：(n,k)線性碼可糾2n-k個錯誤圖樣。定理：在標準陣列中，一個陪集的所