信道的糾錯(cuò)編碼幻燈片資料

第9章信道的糾錯(cuò)編碼

信道編碼的概念

線性分組碼

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

按信息碼元在編碼后是否保持原形式：系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持位置不變。非系統(tǒng)碼：信息位打亂，與編碼前位置不同。3錯(cuò)誤圖樣⑴當(dāng)系統(tǒng)無干擾時(shí)R=C⑵當(dāng)系統(tǒng)有干擾時(shí)R=C+E其中，E稱為信道的錯(cuò)誤圖樣，E=(e0,e1,…,en-1)；ei∈{0,1}；當(dāng)ei=1，則第i位上有錯(cuò)；反之，無錯(cuò)。例：C=00101101E=01001001R=01100100由信道的對(duì)稱性可知p(0/1)=p(1/0)=p(e=1)=p反之，若已知R，E則可求出C，這就是糾錯(cuò)碼的原理，如：E=01001001R=01100100

C=001011015檢錯(cuò)與糾錯(cuò)的原理⒈編碼效率設(shè)：信息碼長(zhǎng)度為k，經(jīng)信道編碼后長(zhǎng)度為n，則我們定義編碼效率R為：R=k/n⒉幾種簡(jiǎn)單的檢糾錯(cuò)碼奇/偶校驗(yàn)碼——檢錯(cuò)碼重復(fù)碼——糾錯(cuò)碼6檢錯(cuò)與糾錯(cuò)方式和能力⒈檢糾錯(cuò)方式FEC（前向糾錯(cuò)）——糾錯(cuò)ARQ（自動(dòng)請(qǐng)求重發(fā)）——檢錯(cuò)⒉幾個(gè)概念漢明距離/距離：在線性碼中，兩個(gè)碼字U、V

之間對(duì)應(yīng)碼元位上符號(hào)取值不同的個(gè)數(shù)，稱為碼字U、V

之間的漢明距離。例如：(7,3)碼的兩個(gè)碼字U=0011101,V=0100111，它們之間第2、3、4和6位不同。因此，碼字U和V的距離為4。線性分組碼的一個(gè)碼字對(duì)應(yīng)于n維線性空間中的一點(diǎn)，碼字間的距離即為空間中兩對(duì)應(yīng)點(diǎn)的距離。7檢錯(cuò)與糾錯(cuò)方式和能力最小碼距：在碼集合中，任兩個(gè)碼字間的距離為最小時(shí)，該碼距即為碼集合的最小碼距。碼字的重量：碼字中非0碼元符號(hào)的個(gè)數(shù)，稱為該碼字的重量，又稱為漢明重量。碼的最小重量：線性分組碼CI中，非0碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI

,V≠0}最小碼距與最小重量的關(guān)系：線性分組碼的最小碼距等于它的最小重量。8檢錯(cuò)與糾錯(cuò)能力--1最小碼距與糾錯(cuò)能力的關(guān)系：定理：(n,k)線性碼能糾t個(gè)錯(cuò)誤的充要條件是碼的最小距離為

dmin=2t

+1或t

=(dmin－1)/2V’9檢錯(cuò)與糾錯(cuò)能力--2最小碼距與檢錯(cuò)能力的關(guān)系：定理：(n,k)線性碼能夠發(fā)現(xiàn)e個(gè)錯(cuò)誤的充要條件是碼的最小距離為

dmin=e+1或e=dmin－1V’e10檢錯(cuò)與糾錯(cuò)能力--3最小碼距與檢、糾錯(cuò)能力的關(guān)系：定理：(n,k)線性碼能糾t個(gè)錯(cuò)誤，并能發(fā)現(xiàn)e個(gè)錯(cuò)誤

(e>t)的充要條件是碼的最小距離為

dmin=t+e+1或t+e=dmin－1eV’V’’11線性分組碼

一、線性分組碼的描述線性分組碼是同時(shí)具有分組特性和線性特性的糾錯(cuò)碼。定義：一個(gè)（n,k）線性分組碼C是稱為碼字c的n維向量的集合。式中：為消息矢量，是一個(gè)k行n列的秩為k（n﹥k)的矩陣，我們稱它為線性碼的生成矩陣。第一種編碼方法12線性分組碼例：（4,3）偶校驗(yàn)碼是一個(gè)（4,3）線性分組碼，其生成矩陣為

求消息碼010，110所對(duì)應(yīng)的線性碼。解：13線性分組碼將消息碼直接代入有：思考：此碼是否為系統(tǒng)碼？14線性分組碼二、線性分組碼的性質(zhì)及定理當(dāng)消息碼為零向量0…0，所得的碼字為零碼字0…0。

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

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

個(gè)碼字與它們一一對(duì)應(yīng)。在由(n,k)線性碼構(gòu)成的線性空間Vn

的k維子空間中，一定存在k個(gè)線性獨(dú)立的碼字：g0,g1,…,gk-1，碼Ci中其它任何碼字C都可以表為這k個(gè)碼字的一種線性組合，即15線性分組碼16線性分組碼三、線性分組碼的監(jiān)督陣⒈線性分組碼的監(jiān)督陣編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，以構(gòu)成碼字。在k個(gè)信息碼元之后附加r(r=n－k)

個(gè)監(jiān)督碼元，使每個(gè)監(jiān)督碼元是其中某些信息碼元的模2和。舉例：k=3,r=4，構(gòu)成(7,3)線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個(gè)碼元取“0”或“1”監(jiān)督元可按下面方程組計(jì)算17線性分組碼一致監(jiān)督方程/一致校驗(yàn)方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗(yàn)方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗(yàn)方程。由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運(yùn)算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。第二種編碼方法18線性分組碼信息碼組(101)，即C6=1,C5=0,C4=1代入監(jiān)督方程得：C3=0,C2=0,C1=1,C0=1由信息碼組(101)編出的碼字為(1010011)。其它7個(gè)碼字如下。表9.1

(7,3)分組碼編碼表

信息組

對(duì)應(yīng)碼字

000

0000000

001

0011101

010

0100111

011

0111010

100

1001110

101

101

0011

110

1101001

111

1110100

19線性分組碼為了運(yùn)算方便，將監(jiān)督方程寫成矩陣形式，得:20線性分組碼推廣到一般情況：對(duì)(n,k)線性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定

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

或

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

23四、(n,k)線性碼的對(duì)偶碼對(duì)偶碼：對(duì)一個(gè)(n,k)線性碼CI，由于Hr×nGTn×k=0Tr×k，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個(gè)碼CId，碼CId是一個(gè)(n,n－k)線性碼，稱碼CId為原碼的對(duì)偶碼。

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

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

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

若碼的最小距離為S+1，則該碼的監(jiān)督陣有任意S列線性無關(guān)，而必存在線性相關(guān)的S+1列。推理在二元線性碼的監(jiān)督陣H中，如果任一列都不為全零，且任二列都不相等，則該碼能糾一個(gè)錯(cuò)。例：33線性分組碼的譯碼

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

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

作出判決，此判決過程又稱為譯碼。譯碼器按任務(wù)可分為：檢錯(cuò)譯碼和糾錯(cuò)譯碼。檢錯(cuò)譯碼：輸出接收碼字，及差錯(cuò)標(biāo)志。糾錯(cuò)譯碼：輸出糾正的碼字（在糾錯(cuò)能力之內(nèi)）

輸出接收碼字及出錯(cuò)標(biāo)志。（超出糾錯(cuò)能力）

34線性分組碼的譯碼

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

根據(jù)上述原理，我們可知：⒊伴隨式檢錯(cuò)原理設(shè)：發(fā)送碼字C＝(cn－1,cn－2,…,c0)，信道的錯(cuò)誤圖樣為

E＝(en－1,en－2,…,e0)，式中：若ei＝0，表示第i位無錯(cuò)，若ei＝1，則表示第i位有錯(cuò)，i＝n－1，n－2，…，0。那么，接收碼字R=(rn－1,rn－2,…,r0)=C＋E

=(cn－1+en－1，cn－2+en－2，…，c0+e0)檢錯(cuò)譯碼基本原理判為無錯(cuò)（可能有錯(cuò)）一定出錯(cuò)36線性分組碼的譯碼

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

0T，則有：

ST＝HET

所以，37線性分組碼的譯碼

由上面分析得到如下結(jié)論：(1)伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定。(2)伴隨式是錯(cuò)誤的判別式：若S＝0，則判沒有出錯(cuò)，（或存在一個(gè)不可檢測(cè)的錯(cuò)誤，接收字是一個(gè)碼字），若S≠0，則判有錯(cuò)。(3)不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的，二元碼伴隨式是H陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和。38線性分組碼的譯碼

例：設(shè)(7,3)線性分組碼的校驗(yàn)矩陣為試確定以下三種情況時(shí)的譯碼器的輸出（1）接收碼字R=(1010011)，（2）接收碼字R=(1110011)，（3）接收碼字R=(0011011)，39線性分組碼的譯碼

解：對(duì)于⑴有：傳輸過程中沒有誤碼，40線性分組碼的譯碼

對(duì)于⑵有：，第2位出錯(cuò)，41線性分組碼的譯碼

對(duì)于⑶有：與中的任一列都不相同，不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。42線性分組碼的譯碼

定理：可糾t個(gè)錯(cuò)誤的二元線性分組碼與校驗(yàn)元個(gè)數(shù)的關(guān)系：三、采用伴隨式糾錯(cuò)譯碼的方法⒈查表法⒉標(biāo)準(zhǔn)陣列法幾個(gè)概念許用碼組：在(n,k)線性碼中，與2k個(gè)消息碼對(duì)應(yīng)的碼字稱為許用碼組。禁用碼組：在(n,k)線性碼中，除了消息碼外的2n-2k個(gè)碼字。標(biāo)準(zhǔn)陣列的構(gòu)造43線性分組碼的譯碼

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

個(gè)n重碼中選取一個(gè)重量最輕的n重E1放在全0碼字C0下面，再將E1分別和各碼字相加，放在對(duì)應(yīng)碼字下面構(gòu)成陣列第二行;在第二次剩下的n重碼中，選取重量最輕的n重E2，放在E1下面，并將E2分別加到第一行各碼字上，得到第三行；直到全部n重碼字用完為止。得到(n,k)線性碼的標(biāo)準(zhǔn)陣列。（注意：作為錯(cuò)誤圖樣的Ei不能與表內(nèi)的其它碼字相同！）44線性分組碼的譯碼

例：已知(6,3)線性分組碼的生成陣為求它的標(biāo)準(zhǔn)陣列。解：由生成陣可得該碼許用碼組的全部碼字：消息碼線性分組碼消息碼線性分組碼00000000010010011000100110110110101101001001111011010101101111011111100045線性分組碼的譯碼

則它的標(biāo)準(zhǔn)陣列為：00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000010000100001000010000010000100111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101010011101011110011000010100001100001100146線性分組碼的譯碼

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

0碼矢在內(nèi)，也就是說，把無錯(cuò)的情況也看成一個(gè)可糾的錯(cuò)誤圖樣。定理：(n,k)線性碼可糾2n-k個(gè)錯(cuò)誤圖樣。定理：在標(biāo)準(zhǔn)陣列中，一個(gè)陪集的所有2k個(gè)n重碼字有相同的伴隨式，不同陪集的伴隨式互不相同。譯碼原理：收到的n