第8章 信道編碼

第8章信道編碼8.1信道編碼的基本概念8.2譯碼規(guī)則8.3

信道編碼定理8.4

線性分組碼8.5

循環(huán)碼8.6卷積碼8.7突發(fā)錯(cuò)誤的糾正

本章小結(jié)8.1信道編碼的基本概念8.1.1編譯碼規(guī)則、檢糾錯(cuò)能力8.1.2平均錯(cuò)誤譯碼概率信源編碼信道編碼目的壓縮，通過(guò)去除信源冗余實(shí)現(xiàn)糾錯(cuò)，通過(guò)引入冗余實(shí)現(xiàn)主要指標(biāo)平均碼長(zhǎng)平均錯(cuò)誤譯碼概率影響主要指標(biāo)的因素編碼方法編碼方法、譯碼方法編譯碼之間的關(guān)系一個(gè)編碼方法對(duì)應(yīng)一個(gè)譯碼方法，譯碼是編碼的逆過(guò)程一個(gè)編碼方法可能對(duì)應(yīng)多個(gè)譯碼方法，在這多個(gè)譯碼方法中有一個(gè)能使平均錯(cuò)誤譯碼概率最小8.1.1編譯碼規(guī)則、檢糾錯(cuò)能力例子1【例8-1，P130】奇偶校驗(yàn)碼是一種簡(jiǎn)單而又常用的編碼方法。分為奇校驗(yàn)和偶校驗(yàn)。加入奇偶校驗(yàn)位（冗余位），使奇偶校驗(yàn)碼具有檢錯(cuò)能力；不具有糾錯(cuò)能力；奇偶校驗(yàn)碼能錯(cuò)出一位錯(cuò)誤，即檢錯(cuò)能力為1位。例子2【例8-2，P131】重復(fù)碼也是一種常見(jiàn)的信道編碼方式。試分析一次、二次和重復(fù)編碼。設(shè)要傳送A和B兩個(gè)消息一次重復(fù)編碼：A→0，B→1此時(shí)沒(méi)有冗余，無(wú)檢、糾錯(cuò)能力；當(dāng)接收到010011時(shí)，譯碼為ABAABB無(wú)法發(fā)現(xiàn)接收到的字符串中是否有錯(cuò)誤；二次重復(fù)編碼：Ａ→00、B→11此時(shí)有1位冗余，稱為監(jiān)督位（監(jiān)督元、校驗(yàn)元）當(dāng)接收到010011時(shí)會(huì)發(fā)現(xiàn)無(wú)法譯碼（01）具有檢測(cè)1位錯(cuò)誤能力；無(wú)糾錯(cuò)能力；“01”和“10”稱為禁用碼字，而“00”和“11”稱為許用碼字。三次重復(fù)編碼：A→000，B→111有2位冗余；能檢測(cè)1位或2位錯(cuò)誤，即檢錯(cuò)能力為2位；當(dāng)接收到010011時(shí)，會(huì)發(fā)現(xiàn)出現(xiàn)了禁用碼字（010、011）無(wú)論000010，還是111010，均可判斷出現(xiàn)錯(cuò)誤因此可以檢2位錯(cuò)如果按照“大數(shù)法則”譯碼則譯碼結(jié)果為AB具有糾錯(cuò)能力；如果000010，可正確譯碼為A；如果111010，不能正確譯碼，即該錯(cuò)誤不能被正確糾正過(guò)來(lái)因此只能糾1位錯(cuò)8.1.2平均錯(cuò)誤譯碼概率1、平均錯(cuò)誤譯碼概率的計(jì)算方法平均錯(cuò)誤譯碼概率Pe為錯(cuò)誤譯碼概率的均值其中p(xi)是信源符號(hào)xi的概率，pei是信源符號(hào)xi被錯(cuò)誤譯碼的概率。Pe是衡量譯碼方法好壞的一個(gè)重要指標(biāo)，所選擇的譯碼規(guī)則應(yīng)該使Pe盡可能小?！纠?-3，P131】對(duì)于三次重復(fù)碼，假設(shè)信源輸出的兩個(gè)符號(hào)為等概分布，即信源符號(hào)經(jīng)過(guò)三次重復(fù)編碼后在信道上傳輸，信道矩陣為試計(jì)算此時(shí)的平均錯(cuò)誤譯碼概率。平均錯(cuò)誤譯碼概率例子解：2、平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)【例8-4，P132】對(duì)于例8-3中的信源和信道，如果進(jìn)行一次重復(fù)編碼，平均錯(cuò)誤譯碼概率是多少？并與例8-3的結(jié)果進(jìn)行比較。解：說(shuō)明：與例8-3的結(jié)果不一樣；平均錯(cuò)誤譯碼概率與編碼規(guī)則有關(guān)?！纠?-5，P132】對(duì)于二進(jìn)制對(duì)稱信道，信道矩陣和信源分布分別為：信源符號(hào)不經(jīng)過(guò)任何編碼，直接在信道上傳輸，采用兩種不同的譯碼規(guī)則：譯碼規(guī)則1：0→0、1→1

譯碼規(guī)則2：0→1、1→0試分別計(jì)算這兩種不同譯碼規(guī)則的平均錯(cuò)誤譯碼概率。3、平均錯(cuò)誤譯碼概率與譯碼規(guī)則也有關(guān)解：譯碼規(guī)則1譯碼規(guī)則2說(shuō)明：在同樣的編碼規(guī)則下，不同譯碼規(guī)則的平均錯(cuò)誤譯碼概率是不一樣的；平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。8.2譯碼規(guī)則【定義8-1】

設(shè)信道輸入符號(hào)集為，輸出符號(hào)集為，若對(duì)每一個(gè)輸出符號(hào)yj都有一個(gè)確定的函數(shù)F(yj)，使yj對(duì)應(yīng)于唯一的一個(gè)輸入符號(hào)xi，則稱這樣的函數(shù)為譯碼規(guī)則，記為問(wèn)題的引出：平均錯(cuò)誤譯碼概率與譯碼規(guī)則有關(guān)。有沒(méi)有一種譯碼規(guī)則能使平均錯(cuò)誤譯碼概率Pe達(dá)到最小？在不考慮編碼規(guī)則的前提下，極大似然譯碼能使平均錯(cuò)誤譯碼概率Pe達(dá)到最小?！径x8-2】

選擇譯碼函數(shù)F(yj)=x*，使之滿足

則稱為極大似然譯碼規(guī)則。

極大似然譯碼能使平均錯(cuò)誤譯碼概率最小。上述條件可改為平均錯(cuò)誤譯碼概率可用下式計(jì)算：證明【例8-6，P133】

對(duì)例8-5給出的信源和信道，試設(shè)計(jì)極大似然譯碼規(guī)則，并求平均錯(cuò)誤譯碼概率。譯碼規(guī)則例子11、當(dāng)時(shí)，有因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為解：聯(lián)合概率分布為

2、當(dāng)時(shí)，有因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為3、當(dāng)時(shí)，有因此極大似然譯碼規(guī)則為此時(shí)，平均錯(cuò)誤譯碼概率為設(shè)信道矩陣：1、當(dāng)輸入等概時(shí)，給出極大似然譯碼規(guī)則，并計(jì)算平均錯(cuò)誤譯碼概率。2、若給出極大似然譯碼規(guī)則；計(jì)算平均錯(cuò)誤概率。解：1、（1）當(dāng)輸入等概時(shí)，極大似然譯碼規(guī)則：（2）計(jì)算錯(cuò)誤譯碼概率【例，增】譯碼規(guī)則例子2（1）極大似然譯碼規(guī)則（2）計(jì)算錯(cuò)誤譯碼概率2、當(dāng)輸入不等概時(shí)，8.3信道編碼定理【定理8-1】

有噪信道編碼定理（香農(nóng)第二定理）對(duì)于一個(gè)給定的離散無(wú)記憶信道，信道容量為C，如果信息傳輸率R<C，只要碼長(zhǎng)足夠長(zhǎng)，則一定存在一種編碼方法，使譯碼的錯(cuò)誤概率隨著碼長(zhǎng)的增加，按指數(shù)下降到任意小。說(shuō)明這就是說(shuō)，可以通過(guò)編碼（增加碼長(zhǎng)，即引入更多的冗余），使通信過(guò)程實(shí)際上不發(fā)生錯(cuò)誤，或者使錯(cuò)誤控制在允許范圍之內(nèi)這一定理為通信差錯(cuò)控制奠定了理論基礎(chǔ)。8.4線性分組碼8.4.1基本概念8.4.2線性分組碼的性質(zhì)8.4.3兩個(gè)重要參數(shù)8.4.4生成矩陣和監(jiān)督矩陣8.4.5對(duì)偶碼8.4.6伴隨式及錯(cuò)誤檢測(cè)8.4.7

漢明碼分組線性：校驗(yàn)元與信息元之間是線性關(guān)系稱為(n,k)線性分組碼(n,k)線性碼的每個(gè)碼字C可以表示為C=(cn-1,cn-2,…,c1,c0)，其中前k位是信息位8.4.1基本概念線性分組碼的例子解：(7,3)線性分組碼，n=7，k=3。共有23=8種信息碼元。碼字C=(c6,c5,c4,c3,c2,c1,c0)，其中c6、c5、c4為信息元，c3、c2、c1、c0為監(jiān)督元，每個(gè)碼元取值為“0”或“1”。【例8-7，P135】（7，3）線性分組碼的編碼規(guī)則為：（監(jiān)督方程、校驗(yàn)方程）c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

試給出編碼表。8.4.2線性分組碼的性質(zhì)【定理8-2】線性分組碼滿足封閉性：設(shè)二元線性分組碼CI

，若X和Y為其中的任意兩個(gè)碼字，則X+Y也是CI中的一個(gè)碼字。1、封閉性證明2、線性分組碼一定包含全0碼字證明全0信息元對(duì)應(yīng)的碼字就是全0碼字。8.4.3兩個(gè)重要參數(shù)編碼效率R：簡(jiǎn)稱碼率。編碼效率定義：R=k/n；碼元中信息元所占的比例；是衡量線性分組碼有效性的重要指標(biāo)；在糾錯(cuò)能力相同時(shí)，編碼效率大的碼優(yōu)于編碼效率小的碼。1、編碼效率最小漢明距離：最小漢明距離，衡量抗干擾能力；用(n,k,d)表示距離為d，碼率為R=k/n的線性分組碼糾錯(cuò)碼的基本任務(wù)之一就是構(gòu)造出R一定且dmin盡可能大的碼，或dmin一定且R盡可能大的碼2、最小漢明距離碼的重量漢明重量：在信道編碼中，定義碼字中非零碼元的數(shù)目為碼字的漢明（Hamming）重量，簡(jiǎn)稱碼重；如：“010”碼字的碼重為1“011”碼字的碼重為2最小漢明重量：在非零碼字中，重量最小者稱為最小漢明重量【例8-8，P136】接例8-7，試計(jì)算（7，3）線性分組碼的最小漢明重量。解：除全0碼字之外，其他碼字重量都為4，故最小漢明重量為4。漢明距離及最小漢明距離漢明距離：碼字x和y之間，對(duì)應(yīng)位取值不同的個(gè)數(shù)，簡(jiǎn)稱碼距，用d(x,y)表示。例如：x=(101)，y=(111)則d(x,y)=1漢明距離有以下三個(gè)性質(zhì)：(1)對(duì)稱性：d(C1,C2)＝d(C2,C1)(2)非負(fù)性：d(C1,C2)≥0(3)三角不等式：d(C1,C2)≤d(C1,C3)＋d(C3,C2)最小漢明距離：(n,k)分組碼中任意兩個(gè)碼字之間漢明距離的最小值，用dmin表示最小漢明距離的例子【例8-9，P136】接例8-7，試計(jì)算（7，3）線性分組碼的最小漢明距離。解：經(jīng)過(guò)兩兩計(jì)算漢明距離，得到最小漢明距離為4。最小漢明距離與最小漢明重量的關(guān)系【定理8-3】線性分組碼的最小距離等于碼中碼字的最小重量。證明碼的檢錯(cuò)及糾錯(cuò)能力檢測(cè)e個(gè)錯(cuò)碼，則要求最小碼距：dmin≥e+1糾正t個(gè)錯(cuò)碼，則要求最小碼距為：dmin≥2t+1糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e(e>t)個(gè)錯(cuò)碼，則要求最小碼距為dmin≥e+t+1【例8-10，P138】接例8-7，試分析（7，3）線性分組碼的檢錯(cuò)和糾錯(cuò)能力。解：例8-9得到dmin=4。碼的檢錯(cuò)和糾錯(cuò)的例子最多能檢測(cè)dmin-1=3個(gè)錯(cuò)誤；最多能糾正個(gè)錯(cuò)誤；當(dāng)它同時(shí)用于檢錯(cuò)和糾錯(cuò)時(shí)，要求即能糾正1位錯(cuò)誤，同時(shí)檢2位錯(cuò)誤。8.4.4生成矩陣和監(jiān)督矩陣1、生成矩陣【例8-11，P138】接例8-7，（7，3）線性分組碼的編碼規(guī)則如右，試給出生成矩陣。解：設(shè)分組碼是C=(c6,c5,c4,c3,c2,c1,c0)，信息元是M=(c6,c5,c4)，即C是碼字，M是信息，則編碼規(guī)則可以表示為即C=MG，其中稱為生成矩陣c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

c6=c6c5=c5c4=c4c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

生成矩陣在(n,k)線性分組碼中,每個(gè)碼字C都可以表示為C＝MG則G是該(n,k)線性分組碼的生成矩陣，即生成矩陣G建立了消息與碼矢間的一一對(duì)應(yīng)關(guān)系，它起著編碼器的變換作用；生成矩陣的每一行都是一個(gè)碼字。（后面定理8-4給出）生成矩陣不是唯一的例子【例8-12，P139】給出兩個(gè)生成矩陣。分別求出碼字空間，并進(jìn)行分析。解：

C＝MG結(jié)果如右討論這兩個(gè)碼的檢錯(cuò)和糾錯(cuò)能力一樣但是G2是系統(tǒng)碼，G1是非系統(tǒng)碼系統(tǒng)碼的編譯比較簡(jiǎn)單，而性能與非系統(tǒng)碼一樣，因此系統(tǒng)碼得到了廣泛的應(yīng)用和研究系統(tǒng)碼的生成矩陣可以表示為G＝[IkP]Ik---k×k階單位方陣不同的生成矩陣可能生成相同的碼字空間生成矩陣的初等變換變換非系統(tǒng)碼生成矩陣變?yōu)榕c它等價(jià)的系統(tǒng)碼生成矩陣的方法交換行的位置；將一行加到另一行上；交換列的位置。

如例8-12生成矩陣的每一行都是一個(gè)碼字【定理8-4】生成矩陣的每一行都是一個(gè)碼字。證明在線性分組碼(n,k)中，如果矩陣H使得對(duì)任意碼字C都有下式成立則H稱為(n,k)線性碼的一致監(jiān)督矩陣(或校驗(yàn)矩陣)其中2、監(jiān)督矩陣監(jiān)督矩陣的標(biāo)準(zhǔn)形式對(duì)H各行實(shí)行初等變換，將后r列化為單位子陣:H＝[QIr]這種形式的H稱為監(jiān)督矩陣H的標(biāo)準(zhǔn)形式如例8-11：(7,3)分組碼，監(jiān)督矩陣是標(biāo)準(zhǔn)形式為c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

c6+c4+c3=0c6+c5+c4+c2=0c6+c5+c1=0c5+c4+c0=0一般關(guān)系：HGT＝0T

或GHT＝0如例8-11系統(tǒng)碼的生成矩陣與監(jiān)督矩陣標(biāo)準(zhǔn)形之間的關(guān)系（G=[Ik

P]、H=[QIr]）：

其中：P＝QT

或Q=PT

3、生成矩陣和監(jiān)督矩陣關(guān)系【例8-13，P141】接例8-11，已知（7，3）線性分組碼的生成矩陣為求監(jiān)督矩陣。解：（G=[Ik

P]、H=[QIr]）：

其中：P＝QT

或Q=PT

生成矩陣與監(jiān)督矩陣關(guān)系的例子8.4.5對(duì)偶碼對(duì)一個(gè)(n,k)線性碼CI，由于HGT＝0T，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個(gè)碼CJCJ是一個(gè)(n,n-k)線性碼，稱為CI的對(duì)偶碼(7,3)碼的生成矩陣和監(jiān)督矩陣為則將兩個(gè)矩陣的作用對(duì)換，得到對(duì)偶碼(7,4)碼的生成矩陣和監(jiān)督矩陣為變換后為標(biāo)準(zhǔn)形式對(duì)偶碼的例子【例8-14，P141】求（7，3）線性分組碼的對(duì)偶碼。解：

得到的：(7,3)碼和(7,4)碼8.4.6伴隨式及錯(cuò)誤檢測(cè)伴隨式（監(jiān)督子，校驗(yàn)子）對(duì)接收碼字R，用監(jiān)督矩陣H來(lái)檢驗(yàn)R是否滿足監(jiān)督方程，即HRT＝0T是否成立若HRT＝0T成立，則認(rèn)為R是一個(gè)碼字，否則判為碼字在傳輸中發(fā)生了錯(cuò)誤把S＝RHT或ST＝HRT，稱為接收碼字R的伴隨式(或監(jiān)督子，或校驗(yàn)子)1、伴隨式錯(cuò)誤圖樣錯(cuò)誤圖樣：設(shè)發(fā)送碼字C＝(cn-1，cn-2，…，c0)，而接收到的碼字為R＝(rn-1,rn-2,…,r0)，則定義E＝(en－1，en－2，…，e0)=R-C，為信道的錯(cuò)誤圖樣

錯(cuò)誤圖樣含義：若ei＝0，表示第i位無(wú)錯(cuò)，若ei＝1，則表示第i位有錯(cuò)2、伴隨式的錯(cuò)誤圖樣表示伴隨式的錯(cuò)誤圖樣表示則此時(shí)伴隨式為ST＝HRT＝H(C＋E)T＝HCT+HET＝HET若將監(jiān)督矩陣H表示為H=[h1

h2…h(huán)n]

式中，hi為H的第i列即則此時(shí)伴隨式可表示為ST＝HET＝h1en－1＋h2en－2＋…+hne0，這叫做伴隨式的錯(cuò)誤圖樣表示基本結(jié)論伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無(wú)關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定伴隨式是錯(cuò)誤的判別式：若S＝0，則判沒(méi)有出錯(cuò)，接收字是一個(gè)碼字，若S≠0，則判有錯(cuò)二元碼伴隨式是H陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和

如E=[00101]，則伴隨式是監(jiān)督矩陣中第3和第5列的和。利用這點(diǎn)可以用來(lái)糾錯(cuò)（譯碼）。ST＝HET＝h1en－1＋h2en－2＋…+hne0，這叫做伴隨式的錯(cuò)誤圖樣表示伴隨式譯碼的基本過(guò)程3、根據(jù)伴隨式譯碼結(jié)束【例8-15，P143】接例8-13，二元（7，3）線性分組碼的監(jiān)督矩陣為設(shè)發(fā)送碼字C＝(1010011)試分別對(duì)三個(gè)接收碼字R1=[1010011]、R2=[1110011]、R3=[0011011]譯碼。解：

伴隨式的例子11、接收到的碼字R＝(1010011)接收碼字R的伴隨式為譯碼器判接收字無(wú)錯(cuò)，即傳輸中沒(méi)有發(fā)生錯(cuò)誤2、接收到的碼字R＝(1110011)接收碼字R的伴隨式為ST≠0，譯碼器判為有錯(cuò)(7，3)碼是糾單個(gè)錯(cuò)誤的碼，且ST等于H的第二列，因此判定接收碼字R的第二位是錯(cuò)的，因此譯碼為(1010011)由于接收字中錯(cuò)誤碼元數(shù)與碼的糾錯(cuò)能力相符，所以譯碼正確發(fā)送碼字C＝(1010011)伴隨式例1（續(xù)）伴隨式例1（續(xù)）發(fā)送碼字C＝(1010011)3、接收碼字R＝(0011011)碼元錯(cuò)誤多于1個(gè)其伴隨式為ST不等于0，但與H陣的任何一列都不相同；至少是監(jiān)督矩陣兩列的和（如第1、4列的和或第2、7列的和）無(wú)法判定錯(cuò)誤出在哪些位上，即此時(shí)只能發(fā)現(xiàn)有錯(cuò)伴隨式例2【例，增】(15,7)碼的生成矩陣和監(jiān)督矩陣分別為該碼可以糾正2位錯(cuò)發(fā)送碼字C＝(101001100101110)如：接收碼字R=(111101100101110)ST不等于0，H陣的第2、4列的和相同，因此錯(cuò)誤出現(xiàn)在第2、4位上，碼字可以糾正為(101001100101110)8.4.7漢明碼漢明碼是1950年由漢明提出的能夠糾正1位錯(cuò)碼且編碼效率較高的一種線性分組碼。它不僅性能好而且編譯碼電路非常簡(jiǎn)單，易于工程實(shí)現(xiàn)，因此是工程中常用的一種糾錯(cuò)碼二元漢明碼的參數(shù)n，k和d分別為碼長(zhǎng)：n=2r-1信息位數(shù)：k=2r-r-1監(jiān)督位數(shù)：r=n-k最小碼距：dmin=3由于dmin=3，因此能糾正1個(gè)隨機(jī)錯(cuò)誤或檢測(cè)2個(gè)錯(cuò)誤漢明碼的構(gòu)造漢明碼的監(jiān)督矩陣H的列為所有非零的r維向量組成，所以一旦r給定，就可構(gòu)造出具體的(n，k)漢明碼。漢明碼的構(gòu)造例子【例8-16，P145】試構(gòu)造一個(gè)二元的（7,4,3）漢明碼。解：由于r=7-4=3因此H中共有23-1=7列將該監(jiān)督矩陣進(jìn)行行列交換，得到監(jiān)督矩陣的標(biāo)準(zhǔn)形式H＝[QIr]這種行列交換，對(duì)碼的性能沒(méi)有影響。此時(shí)得到的漢明碼為系統(tǒng)漢明碼。列為所有非零的7維向量根據(jù)監(jiān)督矩陣可得到系統(tǒng)漢明碼的生成矩陣，即（G=[Ik

P]、H=[QIr]）：

其中：P＝QT

或Q=PT得到二元的（7,4,3）漢明碼為漢明碼的構(gòu)造例子（續(xù)）信息元碼字信息元碼字000000000001000100001100010001111100110011000010001011010101010101001100110011011101101001000100101110011001100101010101011011101001011001100111110111000001110111100111111111118.5循環(huán)碼循環(huán)碼是一類最主要、最有用的線性分組碼；1957年普朗格(Prange)首先開(kāi)始研究循環(huán)碼；循環(huán)碼具有許多優(yōu)良的性質(zhì)，在理論和實(shí)踐中都是十分重要的。8.5.1循環(huán)碼的基本概念8.5.2循環(huán)碼的生成多項(xiàng)式和監(jiān)督多項(xiàng)式8.5.3循環(huán)碼的譯碼8.5.4BCH碼8.5.5RS碼8.5.1循環(huán)碼的基本概念設(shè)C是一個(gè)(n,k)線性碼；如果C中的任意一個(gè)碼字經(jīng)任意循環(huán)移位之后仍然是C中的一個(gè)碼字，那么就稱此碼是一個(gè)循環(huán)碼；循環(huán)左移與循環(huán)右移是等價(jià)的循環(huán)左移i位等于循環(huán)右移n-i位因此可以默認(rèn)循環(huán)移位為循環(huán)左移碼字C=(cn-1,cn-2,…,c1,c0)循環(huán)移位i位之后為C(i)＝(cn-i-1,cn-i-2,…,c0,cn-1,…,cn-i+1,cn-i)循環(huán)碼舉例如：例8-7給出的（7，3）線性分組碼是一個(gè)循環(huán)碼：碼字的多項(xiàng)式設(shè)碼字C=(cn-1,cn-2,…,c1,c0)，用各個(gè)分量作為系數(shù)，可以寫(xiě)出一個(gè)多項(xiàng)式C(x)=cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0則C(x)就是相應(yīng)碼字的多項(xiàng)式；碼字C與多項(xiàng)式C(x)是一一對(duì)應(yīng)的。循環(huán)碼的碼字多項(xiàng)式碼字循環(huán)移位之后，碼字多項(xiàng)式的變化(選3個(gè)編碼為例)：C1(0111010)的多項(xiàng)式C1(x)=x5+x4+x3+xC2(1110100)的多項(xiàng)式C2(x)=x6+x5+x4+x2C3(1101001)的多項(xiàng)式C3(x)=x6+x5+x3+1三者的關(guān)系為C2(x)=xC1(x)=C1(1)(x)，C3(x)=x2C1(x)mod(x7+1)=C1(2)(x)這表明C(i)(x)≡xiC(x)mod(xn＋1)C(x)乘以xi的目的是左移i位，對(duì)xn+1取余式的目的是循環(huán)左移循環(huán)循環(huán)碼的多項(xiàng)式舉例【例，增】(7，3)循環(huán)碼可由任一個(gè)碼字，比如0011101經(jīng)過(guò)循環(huán)移位，得到其他6個(gè)非0碼字(7，3)循環(huán)碼也可由碼多項(xiàng)式x4+x3＋x2＋1，乘以xi，再模x7＋1得到其他6個(gè)非0碼多項(xiàng)式8.5.2循環(huán)碼的生成多項(xiàng)式和監(jiān)督多項(xiàng)式1、生成多項(xiàng)式循環(huán)碼可由一個(gè)非零碼字經(jīng)過(guò)循環(huán)移位得到其他非0碼字；因此在(n，k)循環(huán)碼的2k個(gè)碼多項(xiàng)式中，只要給出一個(gè)就可以推得其它選擇其中前k-1位皆為0的碼多項(xiàng)式g(x)(次數(shù)r＝n-k)，這個(gè)多項(xiàng)式叫做(n，k)循環(huán)碼的生成多項(xiàng)式g(x)＝gn-k

xn-k＋gn-k-1xn-k-1＋…＋g1x＋g0生成多項(xiàng)式的性質(zhì)g(x)＝gn-k

xn-k＋gn-k-1xn-k-1＋…＋g1x＋g0生成多項(xiàng)式的次數(shù)為n-k；生成多項(xiàng)式是(n,k)線性分組碼的所有非零碼多項(xiàng)式中，次數(shù)最低的多項(xiàng)式；在(n,k)循環(huán)碼中，g(x)是唯一的n-k次多項(xiàng)式；生成多項(xiàng)式g(x)一定是xn+1的因式。因此，分解xn+1，其中次數(shù)為n-k的因式就是生成多項(xiàng)式說(shuō)明說(shuō)明生成多項(xiàng)式的構(gòu)造分解多項(xiàng)式x7+1=(x+1)(x3+x2+1)(x3+x+1)因此生成多項(xiàng)式為：g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1或者g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1【例8-17，P147】求(7,3)循環(huán)碼的生成多項(xiàng)式。解：00000000111001001011111100100101110110010110111001001011由g1(x)生成的循環(huán)碼00000001101001001110110100110111010010011111101001001110由g2(x)生成的循環(huán)碼如果g(x)為(n，k)循環(huán)碼的生成多項(xiàng)式，則必為xn＋1的因式，因此xn＋1＝h(x)·g(x)如果多項(xiàng)式h(x)滿足xn＋1＝h(x)·g(x)，且hk＝1,h0＝１，則稱h(x)為(n，k)循環(huán)碼的監(jiān)督多項(xiàng)式h(x)＝hkxk＋hk-１xk-１＋…＋h1x＋h0對(duì)偶碼以n-k次多項(xiàng)式g(x)為生成多項(xiàng)式，則生成一個(gè)(n，k)循環(huán)碼以h(x)為生成多項(xiàng)式，則生成(n，n-k)循環(huán)碼這兩個(gè)循環(huán)碼互為對(duì)偶碼2、監(jiān)督多項(xiàng)式生成矩陣(n,k)循環(huán)碼的生成多項(xiàng)式g(x)經(jīng)k-1次循環(huán)移位，共得到k個(gè)碼多項(xiàng)式：

g(x)，xg(x)，…，xk-1g(x)這k個(gè)碼多項(xiàng)式的系數(shù)可作為生成矩陣G(x)的k行，即3、生成矩陣和監(jiān)督矩陣生成矩陣舉例解：【例，增】設(shè)(7,4)循環(huán)碼的生成多項(xiàng)式g(x)＝x3＋x＋1，求其生成矩陣G。監(jiān)督矩陣(n，k)循環(huán)碼的監(jiān)督多項(xiàng)式為h(x)＝hkxk＋hk-１xk-１＋…＋h1x＋h0則(n，k)循環(huán)碼的監(jiān)督矩陣為循環(huán)碼的生成矩陣、監(jiān)督矩陣舉例(7，3)碼：x7＋1＝(x3＋x＋1)(x4＋x2＋x＋1)4次多項(xiàng)式為生成多項(xiàng)式：

g(x)＝x4＋x2＋x＋1＝g4x4＋g3x3＋g2x2＋g1x＋g03次多項(xiàng)式則是監(jiān)督多項(xiàng)式：

h(x)＝x3＋x＋1＝h3x3＋h2x2＋h1x＋h0則生成矩陣和監(jiān)督矩陣分別為【例8-18，P148】求(7,3)循環(huán)碼的生成多項(xiàng)式、監(jiān)督多項(xiàng)式、生成矩陣、監(jiān)督矩陣。解：8.5.3循環(huán)碼的譯碼循環(huán)碼的譯碼包括三個(gè)步驟計(jì)算伴隨式求伴隨式對(duì)應(yīng)的錯(cuò)誤圖樣用錯(cuò)誤圖樣糾錯(cuò)（譯碼）相比于一般線性分組碼，循環(huán)碼的譯碼更加簡(jiǎn)單易行伴隨式一般線性分組碼的伴隨式（矩陣形式）：S=RHT或ST=HRT，這對(duì)循環(huán)碼也是適用的；循環(huán)碼伴隨式的特殊求法（多項(xiàng)式形式）S(x)≡R(x)modg(x)即循環(huán)碼的伴隨式是接收多項(xiàng)式R(x)除以g(x)的余式循環(huán)碼譯碼例接收到碼字：R(x)=x6+x3+x+1S(x)≡R(x)modg(x)=x2+1，即S=[101]T而h(x)=x7+1/g(x)=x4+x2+x+1，即伴隨式是監(jiān)督矩陣的第一列，因此碼字的第1位出錯(cuò)，譯碼為0001011，正確譯碼【例8-19，P148】一個(gè)(7,4)循環(huán)碼的生成多項(xiàng)式g(x)＝x3+x+1，一個(gè)碼字為0001011，若該碼字在傳輸過(guò)程中發(fā)生錯(cuò)誤，接收到的碼字變?yōu)?001011，試對(duì)其譯碼。解：8.5.4BCH碼是一種獲得廣泛應(yīng)用的能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼，是迄今為止所發(fā)現(xiàn)的一類性能較優(yōu)的碼；BCH碼的重要性在于它解決了生成多項(xiàng)式與糾錯(cuò)能力的關(guān)系問(wèn)題BCH的歷史（是以3位發(fā)明這種碼的人名(Bose-Chaudhuri-Hocguenghem)命名的）1959年霍昆格姆(Hocgenghem)和1960年博斯(Bose)及查德胡里(Chaudhuri)分別提出的糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，稱為BCH碼1960年彼得森(Pelerson)找到了二元BCH碼的第一個(gè)有效算法，后經(jīng)多人的推廣和改進(jìn)1967年由伯利坎普(Berlekamp)提出了BCH碼譯碼的迭代算法，從而將BCH碼由理論研究推向?qū)嶋H應(yīng)用階段，使它成為應(yīng)用廣泛而有效的一類線性碼BCH碼的基本參數(shù)對(duì)任何正整數(shù)m(3)和t(<2m-1)，存在一個(gè)二元BCH碼，具有下面的參數(shù)碼長(zhǎng)：n=2m-1一致校驗(yàn)位的數(shù)目：n-k

mt最小碼距：dmin2t+1能糾正n=2m-1個(gè)碼元中任意不超過(guò)t個(gè)錯(cuò)誤即給定符合條件m3、t<2m-1的m和t之后，總能設(shè)計(jì)出一個(gè)二元BCH，滿足碼長(zhǎng)為2m-1，并能糾正t個(gè)隨機(jī)錯(cuò)誤。1、BCH碼的生成多項(xiàng)式和參數(shù)BCH碼的定義g(x)是一個(gè)循環(huán)碼的生成多項(xiàng)式，如果g(x)=0的根中包括2t個(gè)連續(xù)根

,

2,

3,…,

2t，則由g(x)生成的循環(huán)碼叫做BCH碼。此時(shí)g(x)=(x-

)(x-

2)…(x-

2t)=0如何構(gòu)造出滿足該條件的生成多項(xiàng)式g(x)是比較困難的，有興趣的同學(xué)可以自學(xué)nktg(x)（八進(jìn)制）74113151112315727211553246731261453121235513116310765731115542332531673133650473126175635711032、部分常用BCH碼的生成多項(xiàng)式說(shuō)明：(721)8=111010001【例8-20，P150】對(duì)(7,4)BCH碼，一個(gè)碼字為1101001，若該碼字在傳輸過(guò)程中發(fā)生錯(cuò)誤，接收到的碼字變?yōu)?101000，試對(duì)其譯碼。解：(13)8=001011BCH碼舉例nktg(x)（八進(jìn)制）74113（001011）1511123157272115532467312614531212355131163107657311155423325則生成矩陣為初等變換為系統(tǒng)碼生成矩陣為如果信息元為1101，則對(duì)應(yīng)的碼字為1101001如果接收到的碼字為1101000，則伴隨式為001，是監(jiān)督矩陣的最后一列，則譯碼結(jié)果為1101001BCH碼舉例（續(xù)）監(jiān)督矩陣H為（G=[IkP]、H=[QIr]）：

其中：P＝QT

或Q=PT因此伴隨式為8.5.5RS碼里德-索羅蒙（Reed-Solomon）碼，簡(jiǎn)稱RS碼RS碼是q元BCH碼編碼方式類似RS碼是以數(shù)據(jù)塊進(jìn)行編碼例如如果q=4，數(shù)據(jù)塊的長(zhǎng)度就是2如果q=8，數(shù)據(jù)塊的長(zhǎng)度就是3RS碼即可以糾隨機(jī)錯(cuò)誤，又可以糾突發(fā)錯(cuò)誤。8.6卷積碼8.6.1卷積碼的基本概念和基本原理8.6.2卷積碼的編碼8.6.3卷積碼的矩陣表述1955年埃里亞斯(Elias)最早提出卷積碼的概念卷積碼(又稱連環(huán)碼)指的是在任意給定時(shí)刻，編碼器輸出的n0個(gè)碼元中，每一個(gè)碼元不僅和此時(shí)刻輸入的k0個(gè)信息元有關(guān)，還與前面連續(xù)m0個(gè)時(shí)刻輸入的信息元有關(guān)，可以用（n0,k0,m0）表示；8.6.1卷積碼的基本概念和基本原理幾點(diǎn)說(shuō)明：典型的卷積碼一般選較小的n0和k0(k0<n0)，但存儲(chǔ)器數(shù)m0則取較大的值(m0<10)卷積碼的編碼效率為R＝k0/n0在同樣的編碼效率R下，卷積碼的性能優(yōu)于分組碼，至少不低于分組碼但是卷積碼不像分組碼有嚴(yán)格的代數(shù)結(jié)構(gòu)，至今沒(méi)有嚴(yán)密的數(shù)學(xué)手段將糾錯(cuò)能力與碼的結(jié)構(gòu)十分有規(guī)律的聯(lián)系起來(lái)。8.6.2卷積碼的編碼設(shè)卷積碼編碼器輸入碼序列為U=[us-m0(1)us-m0(2)…us-m0(k0)…

us-1(1)us-1(2)…us-1(k0)

us(1)us(2)…us(k0)…]編碼器的輸出，即碼字為C=[cs(1)cs(2)…cs(k0)

cs(k0+1)…cs(n0)]則非系統(tǒng)碼的編碼為系統(tǒng)碼的編碼為

其中g(shù)t(i,j)的值是0或1；定義：g(i,j)=[g0(i,j)g1(i,j)…gm0(i,j)]是卷積碼的生成序列，共有k0*n0個(gè)生成序列，每個(gè)序列的長(zhǎng)度為m0+1比特，它的作用與線性分組碼中的生成矩陣類似，表明如何由信息元得到碼字。卷積碼編碼例1對(duì)于(3,1,2)系統(tǒng)卷積碼則n0=3，k0=1，m0=2U=[us-2(1)us-1(1)us(1)]因此它有3個(gè)生成序列g(shù)(1,1)、g(1,2)、g(1,3)則編碼方法為【例8-21，P151】(3,1,2)系統(tǒng)卷積碼的3個(gè)生成序列為

g(1,1)=[100]g(1,2)=[110]g(1,3)=[101]試構(gòu)造它的編碼規(guī)則。解：卷積碼編碼例2(3,2,2)系統(tǒng)卷積碼則n0=3，k0=2，m0=2U=[us-2(1)us-2(2)us-1(1)us-1(2)us(1)us(2)]因此它有6個(gè)生成序列：g(1,1)、g(1,2)、g(1,3)、g(2,1)、g(2,2)、g(2,3)，【例8-22，P151】(3,2,2)系統(tǒng)卷積碼的生成序列為

g(1,1)=[100]，g(1,2)=[000]，g(1,3)=[101]g(2,1)=[000]，g(2,2)=[100]，g(2,3)=[110]試構(gòu)造它的編碼規(guī)則。解：卷積碼編碼例2（續(xù)）6個(gè)生成序列的值分別為g(1,1)=[100]，g(2,2)=[100]g(1,2)=[000]，g(2,1)＝[000]g(1,3)=[g0(1,3)g1(1,3)g2(1,3)]=[101]g(2,3)=[g0(2,3)g1(2,3)g2(2,3)]=[110]該碼的任一子碼Cs為8.6.3卷積碼的矩陣表述生成矩陣其中叫做基本生成矩陣稱為生成子矩陣。生成子矩陣gt與生成序列g(shù)(i,j)的關(guān)系而因?yàn)間(1,1)=[100]，g(1,2)=[110]，g(1,3)=[101]即生成子矩陣為g0=[111]，g1=[010]，g2=[001]所以生成矩陣為【例8-23，P152】接例8-21。試構(gòu)造(3,1,2)系統(tǒng)卷積碼的生成矩陣，并計(jì)算當(dāng)輸入序列（即信息序列）為U=[1011010100…]時(shí)，卷積碼的輸出序列（即碼字序列）。解：卷積碼生成例1若信息序列為U=[1011010100…]則輸出碼字序列為即輸出序列為[111010110101011…]卷積碼生成例1（續(xù)）【例8-24，P153】

(3,2,1)卷積碼的生成子矩陣分別為求卷積碼的生