第六章信道編碼1

信息論與編碼技術(shù)展愛云Zayscj@通信工程教研室CodingandInformationTheroy本課程的相關(guān)要求課程基礎(chǔ)（概率論）上課要求學(xué)習(xí)要求實(shí)驗(yàn)要求（C\C++)本課程的重點(diǎn)信息的基本概念信息量的計(jì)算典型的幾種信源編碼方法典型的幾種信道編碼方法無失真信源編碼定理-香農(nóng)第一定理信道編碼定理-香農(nóng)第二定理限失真信源編碼定理-香農(nóng)第三定理差錯控制系統(tǒng)分類可糾正錯誤的碼發(fā)收FEC能夠發(fā)現(xiàn)錯誤的碼發(fā)收ARQ應(yīng)答信號能夠發(fā)現(xiàn)和糾正錯誤的碼發(fā)收HEC應(yīng)答信號信道編碼一、引言思考：信道編碼的目的是什么？通信系統(tǒng)模型信道編碼：從消息到信道波形或矢量的映射從兩個方面引入信道編碼檢錯和糾錯：對付信道引入的差錯直觀的譯碼準(zhǔn)則：最小距離譯碼Shannon第二定理當(dāng)信息速率R小于信道容量C時，總存在一種編碼方式使差錯率低于任一給定值e接近信道容量信道編碼的作用信道編碼的作用：在資源、可靠性和傳信量之間選擇一個好的工作點(diǎn)（有時還要考慮延時）。資源指的提供信息傳輸所付出的代價包括頻率、時間、空間、功率等等。但不包括實(shí)現(xiàn)復(fù)雜度一個好的編碼就是要充分利用資源，傳遞盡可能多的信息三種情形：給定資源和可靠性要求，通過信道編碼盡量提高傳輸速率給定對信息傳輸?shù)乃俾屎涂煽啃砸?，通過信道編碼盡量減少資源開銷給定資源和傳輸速率，通過編碼提高可靠性編碼的實(shí)質(zhì)

——利用冗余降低差錯概率將所有可能的輸入信息（消息）映射到信道符號（波形）空間的點(diǎn)，而這個點(diǎn)的集合要小于（包含于）全信道空間中。幾種常用的離散信道編碼分組碼將一個有限(k)維輸入矢量映射到一個（n維）矢量的編碼，記為(n,k)分組碼卷積碼輸入為一個無限長序列，每個節(jié)拍有k個符號送入編碼器，同時有n個符號向輸出至信道，但每節(jié)拍的輸出不僅與本節(jié)拍的輸入有關(guān)，還與之前L-1個節(jié)拍的輸入有關(guān)，記為(n,k,L)卷積碼級聯(lián)碼兩個以上的編碼器按一定方式組合而成的編碼器信道編碼的分類編碼與譯碼對二進(jìn)制(n,k)碼，信息數(shù)量（或合法碼字?jǐn)?shù)）為2k，可用編碼空間的點(diǎn)數(shù)為2n個。任一種2k信息集合到二進(jìn)制序列集合(2n)的映射都是一種(n,k)碼。因此總共可能的編碼方案有種。如，共有1029種(100,50)碼。譯碼運(yùn)算量：如果直接用最大似然序列譯碼，對一般性的編碼而言，正比于n*2k，對(100,50)碼，則為1017。幾乎是不可能譯碼的。為什么要引入線性碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題編碼方案太多，以至全局搜索是不可能的現(xiàn)實(shí)的做法是對編碼方案加以一定的約束，在一個子集中尋找局部最優(yōu)這種約束即要能包含盡可能好的碼，又要便于分析，便于譯碼目前對線性系統(tǒng)的研究遠(yuǎn)比非線性系統(tǒng)充分線性碼的定義碼字集中的元之間的任意線性組合仍是合法碼字，即對線性組合運(yùn)算封閉的碼字集，稱為線性碼因此，為了構(gòu)成線性空間，必須首先定義運(yùn)算群——定義了一種運(yùn)算的集合群運(yùn)算封閉有恒等元有逆元滿足結(jié)合律交換群滿足交換律的群環(huán)——定義了兩種運(yùn)算的集合按第一種運(yùn)算（不妨稱為加法）構(gòu)成交換群第二種運(yùn)算（不妨稱為乘法）滿足以下條件封閉性結(jié)合律與加法間滿足分配律域——一種特殊的環(huán)乘法有恒等元（稱為1元），且除了加法的恒等元（稱為0元）以外有逆的環(huán)除0元外，對乘法構(gòu)成交換群無限域和有限域有理數(shù)、實(shí)數(shù)和復(fù)數(shù)都是無限域信道編碼中用到的是有限域，GF(q)兩者在空間意義上有很強(qiáng)的可類比性糾錯碼的發(fā)展概況通信的數(shù)學(xué)理論，Shannon(1948)漢明碼，Hamming(1950)級連碼，F(xiàn)orney(1966)卷積碼及有效譯碼,(60年代)RS碼及BCH碼的有效譯碼(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo碼，Berrou(1993)LDPC碼，Gallager(1963),Macky(1996)空時編碼,Tarokh(2000)重復(fù)碼00…0011…11若將每個比特重復(fù)n次，則構(gòu)成一個碼長為n，信息位長度為1的(n,1)重復(fù)碼,且編碼效率(碼率)R=1/n許用碼字0.9010BSC信道n=2時許用碼組：00，11禁用碼組：01，10能夠發(fā)現(xiàn)一個錯誤，但不能糾正錯誤n=3時許用碼組：000，111禁用碼組：001,010,100,011,101,110能夠糾正一個錯誤，發(fā)現(xiàn)兩個錯誤n=4時許用碼組：0000，1111禁用碼組：0001,0010,0100,1000,0011,0101,0110,1100,1001,1010,0111,1101,1110,1011能夠糾正一個錯誤同時發(fā)現(xiàn)兩個錯誤譯碼正確譯碼失敗譯碼錯誤發(fā)現(xiàn)三個錯誤糾錯碼如何糾正錯誤？在信息序列之后按照一定的規(guī)則添加一定長度的保護(hù)比特(校驗(yàn)比特或監(jiān)督比特)信道編碼二、基本概念(p193)1、漢明碼重(hammingweight)碼字中碼元“1”的個數(shù)。例如：100110的碼重是3w(1100110)=？信道編碼2、漢明碼距(hammingdistance)兩個碼字相對應(yīng)位不同的個數(shù)。例如：d(1011,0110)=3d(0011,1011)=?思考：碼距和碼重的關(guān)系？信道編碼結(jié)論：碼距是兩個碼字異或的結(jié)果的碼重例如：d(10101,01011)101010101111110信道編碼3、最小漢明碼距dmin在碼組中所有碼字相互之間距離的最小值。例如：碼組{10010，11010，01100}d(10010,11010)=1d(10010,01100)=4d(11010,01100)=3dmin(10010,11010,01100)=1

信道編碼三、檢糾錯能力(p194)結(jié)論：檢糾能力與最小碼距有關(guān)。任一(n,k)分組碼，若要在碼字內(nèi)：1、檢錯能力(e位)d>=e+1例如：碼組{1001，0110，0101}e=?

信道編碼2、糾錯能力（t)d>=2*t+1例如：碼組{100101，000101，100001}的糾錯能力？3、糾正t個隨機(jī)錯誤，同時檢測e(e>=t)個錯誤，則要求d>=e+t+1信道編碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確的恢復(fù)出原信息。作為譯碼器的輸入，譯碼算法的已知條件是：1）實(shí)際接收到的碼字序列2）發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集3）信道模型和信道參數(shù)如何譯碼呢？幾種基本的譯碼方法問題：M?C?R如何根據(jù)接收信號R估計(jì)發(fā)送序列C’,進(jìn)而估計(jì)信息序列M’？設(shè)計(jì)譯碼算法的原則：使譯碼錯誤概率最小最大后驗(yàn)概率譯碼

（MaximumAposteriorProbability）

在已知接受的碼字序列R條件下，找出可能性最大的發(fā)碼Ci作為譯碼估值C’,C’=maxp(Ci/R)信道編碼信道編碼收碼推測發(fā)碼.但在實(shí)際中,后驗(yàn)概率的定量確定是很困難的.最大似然譯碼

(MaximumLikelihoodDecode)在已知r的條件下,使先驗(yàn)概率最大的譯碼算法.c’=maxp(r/ci)信道編碼信道編碼譯碼失敗：譯碼器根據(jù)接收到的信號無法作出明確判斷譯碼錯誤：譯碼器根據(jù)接收到的信號作出錯誤判斷不完備譯碼(p199)完備譯碼：根據(jù)接收信號，譯碼器一定能作出是哪一組信息的判斷(p200)信道編碼信道編碼四、簡單的信道編碼方法1、奇偶校驗(yàn)（在消息序列后加上一位的冗余位，使整個序列的“1”的個數(shù)為奇數(shù)個或偶數(shù)個。）奇校驗(yàn)：數(shù)“1”的個數(shù)，在消息序列后加上一位的冗余位，使整個序列的“1”的個數(shù)為奇數(shù)個偶校驗(yàn)：數(shù)“1”的個數(shù)，在消息序列后加上一位的冗余位，使整個序列的“1”的個數(shù)為偶數(shù)個信道編碼例如：消息序列1000111010101奇校驗(yàn)：10001110101010偶校驗(yàn)：10001110101011思考：這種方法是否能夠糾錯？信道編碼2、定比碼在碼字中，“1”和“0”的比例為確定值。應(yīng)用于數(shù)據(jù)通信和工業(yè)控制中。在我國原來的電傳機(jī)上使用的就是五單位定比碼。國際ARQ電報(bào)通信系統(tǒng)中使用的是七單位定比碼。信道編碼3、群計(jì)數(shù)碼數(shù)碼字中“1”的個數(shù)，在碼字后加上用二進(jìn)制表示的“1”的個數(shù)。例如：1100101100思考：能不能加0100？信道編碼4、模p法在實(shí)際生活中，有時侯“1”和“I”很相似。p=37(符號的個數(shù)）數(shù)字“0”-“9”和字母“A”-“Z”和空格共37種符號?！?”0“1”1¨“A”10“B”11

設(shè)有某消息的符號序列為X=X1X2X3X4,用下表的方式來求它們的和及累加和，然后加上適當(dāng)?shù)谋O(jiān)督元，使累加和是模37的倍數(shù)。消息符號和累加和X1X1X1X2X1+X22*X1+X2X3X1+X2+X33*X1+2*X2+X3X4X1+X2+X3+X44*X1+3*X2+2*X3+X4ψX1+X2+X3+X4+ψ5*X1+4*X2+3*X3+2*X4+ψ信道編碼信道編碼例如：AS9R符號值和累加和A101010S283848994795R2774169監(jiān)督元ΨΨ+74Ψ+243（Ψ+243）/37=整數(shù)Ψ=16監(jiān)督元G

AS9RG信道編碼5、正反碼在某些電氣化鐵道運(yùn)動系統(tǒng)和電報(bào)系統(tǒng)中采用。監(jiān)督元與信息元相同或者相反。例：10110監(jiān)督元1011010100監(jiān)督元01011信道編碼的實(shí)質(zhì)就是在信息元后加上合適的監(jiān)督元,這樣起到檢錯和糾錯的作用簡單的信道編碼方法最小碼距和檢糾錯能力之間的關(guān)系介紹了線性碼的基本代數(shù)知識那么到底在線行碼的約束條件之下,如何能夠起到檢錯和糾錯的能力呢?信道編碼五、監(jiān)督矩陣與生成矩陣——從線性方程組的角度描述分組碼為了進(jìn)行差錯控制，我們按線性代數(shù)的關(guān)系來添加監(jiān)督元序列。這種就叫做線性碼。信道編碼n-k（r)個校驗(yàn)位可用k個已知的信息位表示出來1、監(jiān)督矩陣信道編碼Examples信道編碼信道編碼信道編碼校驗(yàn)矩陣H與任意一個碼字之積為零，因此有(P197/p176)信道編碼信道編碼例：一個（7，3）碼的信息元[x1x2x3]和監(jiān)督元[x4x5x6x7]間的監(jiān)督方程組為：

信道編碼信道編碼信息元監(jiān)督元編成碼字0000000000000000111010011101010011101001110111010011101010011101001110101001110100111101001110100111101001110100信道編碼結(jié)論(P196-198/p176-177)1)上表中的八個碼字是許用碼字.2)任意兩個碼字逐位模二相加，可以得到另外一個碼字。這種性質(zhì)叫做封閉性。3）由于封閉性，可知兩個碼字的碼距就是另外一個碼字的重量。一組碼字中碼的最小重量（除全0）就是該碼組的最小碼距。

4）監(jiān)督矩陣由兩部分組成其中A為r×k矩陣，In-k為r=n-k階單位方陣。

信道編碼信道編碼信道編碼5）每個碼字必須滿足監(jiān)督方程。例如：檢驗(yàn)0011101是否是碼字？信道編碼所以0011101是碼字所以0011001不是碼字信道編碼信道編碼6）在線性碼組中，如果有一個碼字的碼重為W，則，在H中必有與之相應(yīng)的W列相加為0，故稱W列線性相關(guān)。如果要求碼組的最小碼距為d，則表示H中至少有d列相加之和為0。這就要求在碼的監(jiān)督矩陣中，任意少于或等于d-1列相加之和均不應(yīng)等于0，即任意d-1列線性無關(guān)。（P198/p177)信道編碼2、生成矩陣

信道編碼或者信道編碼設(shè)有一個待編碼的消息序列為M=[m1m2….mk]將它表示為信息元序列[x1x2…xk]用矩陣關(guān)系可以表示兩者的關(guān)系：

信道編碼信道編碼信道編碼G為生成矩陣信道編碼例：一個（7，3）碼的信息元[x1x2x3]和監(jiān)督元[x4x5x6x7]間的監(jiān)督方程組為：信道編碼信道編碼設(shè)一信息元組為m1m2m3=101,則通過這種方法，能夠計(jì)算出所有的碼字信道編碼結(jié)論：生成矩陣的三行實(shí)際上均是碼字。這三個碼字組成的生成矩陣，能夠使得得出的碼字中，信息元在前，監(jiān)督元在后，即構(gòu)成系統(tǒng)碼。如選其他的碼字來構(gòu)成生成矩陣，得出的碼字中信息元與監(jiān)督元將是交錯排列，稱為非系統(tǒng)碼。信道編碼六：線性分組碼的譯碼（P199/p177)1、伴隨式發(fā)送的碼字是C,接受的碼字是RE=R-C成為錯誤圖樣或者差錯序列。當(dāng)用監(jiān)督矩陣來校驗(yàn)接收到的碼字，有

信道編碼由于C是一個碼字，所以S被稱為伴隨式或者校驗(yàn)子，用它來檢查接收碼字中的錯誤。S是校驗(yàn)矩陣H中某幾列數(shù)據(jù)的線性組合

線性分組碼的基本譯碼步驟

Step1:由接收到的序列R，計(jì)算伴隨式S=RHT；

Step2:若S=0，正確接收；若S不為零，尋找錯誤圖樣；

Step3:由錯誤圖樣解出碼字C=R-E。信道編碼2、標(biāo)準(zhǔn)矩陣（StandardArray)設(shè)有一個（n,k)線性碼，它共有2k個碼字c0,c1,c2…..c2k-1

將他們排列。根據(jù)許用碼字將禁用碼字進(jìn)行分類，分類的依據(jù)是錯誤圖樣。信道編碼C0C1C2C3……C2k-1伴隨式SE2C1+E2C2+E2C3+E2

C2k-1+E2S2E3C1+E3C2+E3C3+E3

C2k-1E3

S3………..……………………

E2n-kC1+E2n-kC2+E2n-kC3+E2n-k

C2k-1E2n-kS2r碼字錯誤圖樣陪集首信道編碼標(biāo)準(zhǔn)陣列的構(gòu)造方法：1）選擇所用的碼字構(gòu)成第0行。2）選擇差錯圖樣作為第0列。3）陣列中的I行J列元素為Cj+Ei

信道編碼例：信道編碼00000000011101010011101110101001110101001111010011110100S(0000)

00000010011100

0001

00000100011111

0010

0000011

0011

0000100

0100

0011000

0101

0000110

0110

0100000

0111

0001000

1000

0001001

1001

0001010

1010

0001011

1011

0001100

1100

0010000

1101

1000000

1110

1000001

1111

信道編碼應(yīng)當(dāng)指出，當(dāng)（n,k)碼的碼長n較大時，即使只存儲陪集首及伴隨式，譯碼器所需內(nèi)存仍然很大。兩個概念（p201)

完備譯碼限定距離譯碼譯碼失敗：譯碼器根據(jù)接收到的信號無法作出明確判斷譯碼錯誤：譯碼器根據(jù)接收到的信號作出錯誤判斷不完備譯碼完備譯碼：根據(jù)接收信號，譯碼器一定能作出是哪一組信息的判斷在糾錯編碼實(shí)現(xiàn)上總希望在盡可能小的n和r條件下獲得盡可能大的k，d或t對于一個(n,k,d)二元線性碼存在如下碼限。（p204)信道編碼

Singleton信道編碼七、漢明碼(p205)定義：能夠糾正一位錯誤的一組線性碼。二元（n,k,d)漢明碼是一種d=3的完備碼，滿足：校驗(yàn)矩陣有m行，2m-1列，取互不相同的m重構(gòu)成GF(2)上的[7,4,3]漢明碼，001,010,011,100,101,110,111,000。校驗(yàn)矩陣為：Examples:信道編碼八、由已知碼構(gòu)造新碼的方法（p210)擴(kuò)展碼刪余碼增廣碼(增信刪余碼)增余刪信碼延長碼1、擴(kuò)展碼[n+1,k,d]或[n+1,k,d+1]增加一個全校驗(yàn)位2、刪余碼(打孔)在原碼基礎(chǔ)上刪去一個校驗(yàn)元。[n-1,k]3、增廣碼在原碼基礎(chǔ)上，增加一個信息元，刪去一個校驗(yàn)元[n,k+1,d]d*=min{d,n-maxw(c)}4、增余刪信碼刪去一個信息元，增加一個校驗(yàn)元若[n,k,d]碼的最小漢明距離d為奇數(shù)，則挑選所有偶數(shù)重量的碼字，即可構(gòu)成[n,k-1,d+1]增余刪信碼5、延長碼對增廣碼再填加一個全校驗(yàn)位。[n+1,k+1]信道編碼九循環(huán)碼１、特點(diǎn):1)碼的結(jié)構(gòu)參數(shù)可以用有限域的代數(shù)方法來表示、分析和構(gòu)造。２）利用循環(huán)特性，可以用循環(huán)反饋移位寄存器來構(gòu)造較為簡單方便的編碼器和譯碼器。信道編碼２、定義（p215)定義1：設(shè)CH是一個[n.k]線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。信道編碼定義2：設(shè)是n維空間的一個k維子空間，若對任一恒有則稱Vn,k為循環(huán)子空間或循環(huán)碼信道編碼3、幾個概念１）多項(xiàng)式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，該多項(xiàng)式稱為域Fp上的多項(xiàng)式2)多項(xiàng)式次數(shù)degf(x)

系數(shù)不為零的x的最高次數(shù)稱為多項(xiàng)式f(x)的次數(shù)3)首一多項(xiàng)式最高次數(shù)的系數(shù)為1的多項(xiàng)式信道編碼4)既約多項(xiàng)式設(shè)f(x)是次數(shù)大于零的多項(xiàng)式，若除常數(shù)和常數(shù)與本身的乘積以外，再不能被域Fp上的其他多項(xiàng)式整除，則稱f(x)為域Fp上的既約多項(xiàng)式

多項(xiàng)式的因式分解問題、根的問題f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gnxn+gn-1xn-1+…+g1x+g0若對所有i,fi=gi,則f(x)=g(x)5)多項(xiàng)式加法（p213)f(x)+g(x)=(fn+

gn)xn+(fn-1

+

gn-1)xn-1+…+(f1

+

g1)x+(f0

+

g0)6)多項(xiàng)式乘法(p213)結(jié)論：按上述定義的加法和乘法運(yùn)算，F(xiàn)p[x]構(gòu)成一個具有單位元、無零因子的可換環(huán)信道編碼7)多項(xiàng)式同余（長除法）兩個多項(xiàng)式同余８）剩余類(Residue)：給定正整數(shù)m，可將全體整數(shù)按余數(shù)相同進(jìn)行分類，可獲得m個剩余類，分別用Examples1、GF(2)上的多項(xiàng)式f(x)=x2+1的剩余類全體為：信道編碼問題一

如何尋找k維循環(huán)子空間？

如何設(shè)計(jì)[n,k]循環(huán)碼？——利用多項(xiàng)式和有限域的概念信道編碼問題一轉(zhuǎn)化為

如何從模多項(xiàng)式xn-1的剩余類結(jié)合代數(shù)中尋找循環(huán)子空間？如何尋找生成多項(xiàng)式g(x)？循環(huán)碼模多項(xiàng)式xn-1剩余類線性結(jié)合代數(shù)中的理想生成多項(xiàng)式信道編碼９）生成多項(xiàng)式定理1(p215):GF(q)(q為素?cái)?shù)或素?cái)?shù)的冪)上的[n,k]循環(huán)碼中，存在唯一的n-k次首一多項(xiàng)式g(x)，每一個碼多項(xiàng)式C(x)必是g(x)的倍式，每一個小于等于(n-1)次的g(x)的倍式一定是碼多項(xiàng)式信道編碼定理2(p216):GF(q)(q為素?cái)?shù)或素?cái)?shù)的冪)上[n,k]循環(huán)碼的生成多項(xiàng)式g(x)一定是xn-1的n-k次因式：xn-1=g(x)h(x)。反之，若g(x)為n-k次多項(xiàng)式，且xn-1能被g(x)整除，則g(x)一定能生成一個[n,k]循環(huán)碼信道編碼兩個結(jié)論

結(jié)論1:找一個[n,k]循環(huán)碼，即是找一個n-k次首一多項(xiàng)式g(x)，且g(x)必是xn-1的因式。結(jié)論2:若C(x)是一個碼多項(xiàng)式，則反之，若則C(x)必是一個碼多項(xiàng)式信道編碼ExamplesGF(2)上，x7+1=(x+1)(x3+x+1)(x3+x2+1)試求一個[7,4]循環(huán)碼。g(x)、xg(x)、x2

g(x)、x3g(x)、g(x)決定生成矩陣，h(x)決定校驗(yàn)矩陣４、循環(huán)碼的生成矩陣和校驗(yàn)矩陣循環(huán)碼的編碼原理基本步驟([n,k])1、分解多項(xiàng)式xn-1=g(x)h(x)2、選擇其中的n-k次多項(xiàng)式g(x)為生成多項(xiàng)式3、由g(x)可得到k個多項(xiàng)式g(x),xg(x),…xk-1g(x)4、取上述k個多項(xiàng)式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣5、取h(x)的互反多項(xiàng)式h*(x),取h*(x),xh*(x),…xn-k-1h*(x)

的系數(shù)即可構(gòu)成相應(yīng)的校驗(yàn)矩陣信道編碼5系統(tǒng)循環(huán)碼——模g(x)的除法問題m(x)是消息多項(xiàng)式信道編碼循環(huán)碼的系統(tǒng)碼構(gòu)造的步驟為：1）消息多項(xiàng)式乘xn-k2)xn-km(x)/g(x)=q(x)+r(x)/g(x)其中：q(x)是商，r(x)是余數(shù)3）C(x)=xn-km(x)+r(x)信道編碼例：信息元m=1011g(x)=1+x+x3

xn-km(x)=x3(x3+x2+1)信道編碼r(x)=1C(x)=xn-km(x)+r(x)=x6+x5+x3+1所以，碼字是1001011b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak

乘B(x)運(yùn)算電路(利用校驗(yàn)多項(xiàng)式h(x)編碼時會用到)6、多項(xiàng)式的乘法電路（p222)b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運(yùn)算電路akb0akb1akbr-2akbr-16、多項(xiàng)式的乘法電路（p222)h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a1,…ak-g1gr-1輸出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)運(yùn)算電路7、多項(xiàng)式的除法電路（p225)縮減信源循環(huán)碼（n-I,k-I),循環(huán)碼編碼電路g0g1g2gn-k-2b1gn-k-1b1gn-k輸出C(x)輸入m(x)m0,m1,…mk乘g(x)運(yùn)算電路mk-1gn-k-1mk-1

gn-k輸入m(x)是信息序列，g(x)為生成多項(xiàng)式mk-1g0mk-1g1循環(huán)碼編碼電路（p225)信道編碼十、BCH碼(p230)能糾正多位錯誤的循環(huán)碼。碼長：n=2m-1監(jiān)督元位數(shù)：n-k<=mt最小碼距：dmin>=2t+1信道編碼十一：卷積碼（ConvolutionalCode）Encoding：1955，EliasDecoding：ThresholdDecoding——Massey(1963)ListDecoding——Wozencraft(1961)

ViterbiDecoding——Viterbi(1967)信道編碼編碼約束度N=m+1（m編碼的存儲級數(shù)）編碼約束比特長度NA=n*N編碼速率k/nk輸入的數(shù)據(jù)比特，n輸出比特?cái)?shù)。1、幾個基本概念(p234)信道編碼2、編碼電路mipi2pi1輸入D1D2(3,1,2)卷積編碼器信道編碼3、監(jiān)督矩陣監(jiān)督方程組：信道編碼輸入信息元：輸出碼字：Ci，Ci+1等稱為子碼。CiCi+1Ci+2