第十二章卷積碼第十二章卷積碼1主要內(nèi)容和重點(diǎn)基本概念卷積碼的圖解表示樹狀圖網(wǎng)格圖狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖卷積碼的解析表示延時(shí)算子多項(xiàng)式表示半無限矩陣表示主要內(nèi)容和重點(diǎn)基本概念212.1基本概念

按照信息碼元和監(jiān)督碼元之間的約束方式不同分為(n,k)分組碼：每個(gè)碼組的(n-k)個(gè)校驗(yàn)位僅與本碼組的k個(gè)信息位有關(guān)，而與其他碼組無關(guān)為了達(dá)到一定的糾錯(cuò)能力和編碼效率（Rc=k/n），n通常較大，編譯碼時(shí)存儲(chǔ)信息碼產(chǎn)生的時(shí)延隨n增大而線性增加(n,k,N)卷積碼：在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的n個(gè)碼元，不僅取決于這段時(shí)間中的k個(gè)信息位，而且取決于前(N-1)段時(shí)間內(nèi)的信息位也是把k個(gè)信息比特編成n個(gè)比特，但k和n很小，延時(shí)小編碼過程中相互關(guān)聯(lián)的碼元為Nn個(gè)糾錯(cuò)能力隨N的增加而增大。在編碼器復(fù)雜性相同的情況下，卷積碼的性能優(yōu)于分組碼未有嚴(yán)格的數(shù)學(xué)手段有規(guī)律地聯(lián)系糾錯(cuò)性能和碼的構(gòu)成，采用計(jì)算機(jī)搜索好碼N（或Nn）定義為卷積碼的約束長度編碼效率Rc=k/n12.1基本概念按照信息碼元和監(jiān)督碼元之間的約束方式不312.1基本概念

表示方法：解析法：延時(shí)算子多項(xiàng)式表示、半無限矩陣表示圖解法：樹狀圖、網(wǎng)格圖、狀態(tài)圖譯碼方法：門限譯碼：即大數(shù)邏輯譯碼性能最差，但硬件簡單Viterbi（維特比）譯碼：屬最大似然譯碼具最佳性能，但硬件實(shí)現(xiàn)復(fù)雜序列（序貫）譯碼：屬最大似然譯碼在性能和硬件方面介于兩者之間12.1基本概念表示方法：412.1基本概念

卷積碼編碼器的一般形式N段組成的輸入移位寄存器，每段k級(jí)，共Nk位寄存器n個(gè)模2和相加器n級(jí)組成的輸出移位寄存器12.1基本概念卷積碼編碼器的一般形式512.1基本概念

卷積碼編碼器的一般形式（續(xù)）由圖可知：n個(gè)輸出比特不但與當(dāng)前k個(gè)輸入比特有關(guān)，而且與以前的(N-1)k個(gè)輸入信息比特有關(guān)整個(gè)編碼過程可看成：輸入信息序列與移位寄存器和模2和連接方式所決定的另一個(gè)序列的卷積12.1基本概念卷積碼編碼器的一般形式（續(xù)）612.2卷積碼的圖解表示主要內(nèi)容樹狀圖網(wǎng)格圖狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖12.2卷積碼的圖解表示主要內(nèi)容712.2卷積碼的圖解表示樹狀圖(2,1,3)卷積編碼器：輸出移位寄存器用轉(zhuǎn)換開關(guān)代替，每輸入1個(gè)信息比特經(jīng)編碼產(chǎn)生2個(gè)輸出比特設(shè)移位寄存器初始狀態(tài)為全0第1個(gè)輸入比特：為0，輸出比特=00；為1，輸出比特=11第2個(gè)比特輸入，第1個(gè)比特右移1位，輸出比特同時(shí)受當(dāng)前輸入比特和前一個(gè)輸入比特的影響第3個(gè)比特輸入，第1、2個(gè)比特各右移1位，輸出比特同時(shí)由這3位移位寄存器存儲(chǔ)的比特共同決定第4個(gè)比特輸入，第1個(gè)比特移出移位寄存器，不對(duì)后續(xù)編碼產(chǎn)生影響12.2卷積碼的圖解表示樹狀圖812.2卷積碼的圖解表示樹狀圖（續(xù)）：(2,1,3)卷積編碼器移位過程可用樹狀圖表示用a、b、c、d表示移位寄存器mj-2mj-1的4種可能狀態(tài)：00、01、10和11樹狀圖用mj=0和mj-2mj-1=00作起點(diǎn)，即從a點(diǎn)出發(fā)隨著移位寄存器和輸入比特的不同，樹狀圖陸續(xù)分成4條支路，2上、2下。上支路對(duì)應(yīng)于輸入比特為0，下支路對(duì)應(yīng)于輸入比特為1每條支路（樹叉）上標(biāo)注的碼元為輸出比特，每個(gè)節(jié)點(diǎn)上標(biāo)注的a、b、c、d為移位寄存器的狀態(tài)對(duì)j個(gè)輸入信息比特，有2j條支路，但在j=N≥3時(shí)，樹狀圖的節(jié)點(diǎn)自上而下開始重復(fù)出現(xiàn)4種狀態(tài)（相當(dāng)于移位超過移位寄存器長度，狀態(tài)已重復(fù)出現(xiàn)）12.2卷積碼的圖解表示樹狀圖（續(xù)）：(2,1,912.2卷積碼的圖解表示樹狀圖（續(xù)）——樹狀圖分析：第1個(gè)輸入比特m1=0時(shí)，輸出比特x1,1x2,1=00；m1=1時(shí)x1,1x2,1=11。即從a點(diǎn)出發(fā)有2條支路（樹叉）可選：m1=0取上支路，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1取下支路，下一節(jié)點(diǎn)mj-2mj-1=01（即b）12.2卷積碼的圖解表示樹狀圖（續(xù)）——樹狀圖分析：1012.2卷積碼的圖解表示樹狀圖（續(xù)）——(2,1,3)卷積編碼器樹狀圖分析：輸入第2個(gè)比特，移位寄存器右移1位后，上支路情況下移位寄存器狀態(tài)mj-2mj-1仍為00，即a，下支路mj-2mj-1=01，即b對(duì)a，mj-2mj-1=00。若m1=0時(shí)，x1,1x2,1=00，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1時(shí)x1,1x2,1=11，下一節(jié)點(diǎn)mj-2mj-1=01（為b）對(duì)b，mj-2mj-1=01。若m1=0時(shí)，x1,1x2,1=10，下一節(jié)點(diǎn)mj-2mj-1=10（為c）；m1=1時(shí)x1,1x2,1=01，下一節(jié)點(diǎn)mj-2mj-1=11（為d）輸入第3個(gè)比特（a、b的情況重復(fù)，故可不考慮）對(duì)c，mj-2mj-1=10。若m1=0時(shí)，x1,1x2,1=11，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1時(shí)x1,1x2,1=00，下一節(jié)點(diǎn)mj-2mj-1=01（為b）對(duì)d，mj-2mj-1=11。若m1=0時(shí)，x1,1x2,1=01，下一節(jié)點(diǎn)mj-2mj-1=10（為c）；m1=1時(shí)x1,1x2,1=10，下一節(jié)點(diǎn)mj-2mj-1=11（為d）12.2卷積碼的圖解表示樹狀圖（續(xù)）——(2,1,1112.2卷積碼的圖解表示網(wǎng)格圖按照碼樹中的重復(fù)性，可得一種更為緊湊的圖形表示把碼樹中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起12.2卷積碼的圖解表示網(wǎng)格圖1212.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）碼樹中的上支路（對(duì)應(yīng)輸入比特0）用實(shí)線表示，下支路（對(duì)應(yīng)輸入比特1）用虛線表示12.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）1312.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）支路上標(biāo)注的碼元為輸出比特，自上而下4行節(jié)點(diǎn)分別表示a、b、c、d四種狀態(tài)。通常有2N-1種狀態(tài)，從第N節(jié)開始，圖形開始重復(fù)而完全相同12.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）1412.2卷積碼的圖解表示狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖取出已達(dá)到穩(wěn)定狀態(tài)的一節(jié)網(wǎng)格，可得到狀態(tài)圖再把目前狀態(tài)與下一行狀態(tài)重疊起來，可得到反映狀態(tài)轉(zhuǎn)移的狀態(tài)轉(zhuǎn)移圖12.2卷積碼的圖解表示狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖1512.2卷積碼的圖解表示例：對(duì)上述(2,1,3)卷積編碼器，若起始狀態(tài)為a，輸入序列為110111001000，求輸出序列和狀態(tài)變化路徑解：由該卷積碼的網(wǎng)格圖表示，找出編碼時(shí)網(wǎng)格圖中的路徑如圖所示，由此可得到輸出序列和狀態(tài)變化路徑，畫在同一圖中12.2卷積碼的圖解表示例：對(duì)上述(2,1,3)1612.2卷積碼的圖解表示對(duì)于(n,k,N)卷積碼的一般情況，有如下結(jié)論對(duì)應(yīng)于每組k個(gè)輸入比特，編碼后產(chǎn)生n個(gè)輸出比特樹狀圖中每個(gè)節(jié)點(diǎn)引出2k條支路網(wǎng)格圖和狀態(tài)圖（狀態(tài)轉(zhuǎn)移圖）都有2k(N-1)種可能的狀態(tài)。每個(gè)狀態(tài)引出2k條支路，同時(shí)也有2k條支路從其它狀態(tài)或本狀態(tài)引入12.2卷積碼的圖解表示對(duì)于(n,k,N)卷積碼1712.3卷積碼的解析表示主要內(nèi)容延時(shí)算子多項(xiàng)式表示半無限矩陣表示12.3卷積碼的解析表示主要內(nèi)容1812.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示將編碼器中移位寄存與模2和的連接關(guān)系以及輸入、輸出序列都表示為延時(shí)算子D的多項(xiàng)式如輸入序列1101110…表示為M(D)=1+D+D3+D4+D5+…啞變量D的冪次等于相對(duì)于時(shí)間起點(diǎn)的單位延時(shí)數(shù)目，時(shí)間起點(diǎn)通常選在第1個(gè)輸出比特通常，輸入序列可表示為M(D)=m1+m2D+m3D2+m4D3+…其中，m1、m2、m3、m4…為輸入比特的二進(jìn)制表示（1或0）12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示1912.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示用D算子多項(xiàng)式表示移位寄存器各級(jí)與各模2和連接關(guān)系時(shí)，若某級(jí)寄存器與某模2和相連，則多項(xiàng)式中相應(yīng)項(xiàng)的系數(shù)為1，否則為0（表示無連接線）(2,1,3)卷積碼編碼器中，左、右兩個(gè)模2和與寄存器各級(jí)的連接關(guān)系可表示為G1(D)=1+D+D2G2(D)=1+D212.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示2012.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）把表示移位寄存器與模2和連接關(guān)系的多項(xiàng)式稱為生成多項(xiàng)式由生成多項(xiàng)式用多項(xiàng)式相乘可計(jì)算出輸出序列以輸入序列1101110…為例，可得x1(D)=G1(D)×M(D)=(1+D+D2)(1+D+D3+D4+D5+…)=1+D5+D7+…x2(D)=G2(D)M(D)=(1+D2)(1+D+D3+D4+D5+…)=1+D+D2+D4+D6+D7+…)由此，輸出序列x1=(x1,1,x1,2,x1,3,…)=10000101…x2=(x2,1,x2,2,x2,3,…)=11101011…x==(x1,1,x2,1,x1,2,x2,2,x1,3,x2,3,…)=1101010001100111…結(jié)果與前面圖解法所得結(jié)果相同12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）2112.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）常用二進(jìn)制或八進(jìn)制序列表示生成多項(xiàng)式。如上例：G1(D)=1+D+D2g1=(111)=(7)8G2(D)=1+D2g2=(101)=(5)8這種表示主要是為了方便12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）2212.3卷積碼的解析表示半無限矩陣表示輸入信息序列和輸出序列都用半無限矢量表示以(2,1,3)卷積碼為例，有M=[m1m2m3…]X=[x1,1x2,1x1,2x2,2x1,3x2,3…]當(dāng)?shù)?個(gè)信息比特輸入時(shí)，若移位寄存器起始狀態(tài)為全0，兩個(gè)輸出比特為x1,1=m1x2,1=m1當(dāng)?shù)?個(gè)信息比特輸入時(shí)，移位寄存器右移1位，輸出為x1,2=m2+m1x2,2=m2當(dāng)?shù)?個(gè)信息比特輸入時(shí)，有x1,3=m3+m2+m1x2,3=m3+m112.3卷積碼的解析表示半無限矩陣表示2312.3卷積碼的解析表示半無限矩陣表示當(dāng)?shù)趈個(gè)信息比特輸入時(shí)，輸出為x1,j=mj+mj-1+mj-2x2,j=mj+mj-2上式寫成矩陣形式，即[mjmj-1mj-2]A=[x1,jx2,j]其中12.3卷積碼的解析表示半無限矩陣表示2412.3卷積碼的解析表示半無限矩陣表示當(dāng)?shù)?、2信息比特輸入時(shí)存在過渡過程[m100]T1=[x1,1x2,1][m1m20]T2=[x1,2x2,2]其中，12.3卷積碼的解析表示半無限矩陣表示2512.3卷積碼的解析表示半無限矩陣表示把上述編碼過程綜合起來，可得矩陣表示如下X=MG其中，G為生成矩陣（半無限，矩陣的空白區(qū)元素均為0）12.3卷積碼的解析表示半無限矩陣表示2612.3卷積碼的解析表示半無限矩陣表示生成矩陣和生成多項(xiàng)式之間存在確定關(guān)系已知(2,1,3)卷積碼的生成序列為g1=(111)=(g11g12g13)g2=(101)=(g21g22g23)把生成序列g(shù)1、g2按如下方法交錯(cuò)排列，即可得生成矩陣12.3卷積碼的解析表示半無限矩陣表示2712.3卷積碼的解析表示半無限矩陣表示生成矩陣和生成多項(xiàng)式之間存在確定關(guān)系（續(xù)）結(jié)果與前面表示的生成矩陣相同，上式可表示為其中，每個(gè)子矩陣Gi（i=1,2,3）由一行二列組成：G1=(g11g21)G2=(g12g22)G3=(g13g23)12.3卷積碼的解析表示半無限矩陣表示2812.3卷積碼的解析表示半無限矩陣表示推廣：對(duì)于(n,k,N)碼，有X=MG其中，M=[m1,1m2,1m3,1…mk,1m1,2m2,2m3,2…mk,2…]X=[x1,1x2,1x3,1…xn,1x1,2x2,2x3,2…xn,2…]已知該碼的生成序列一般表達(dá)式為

gi,j=(gi,j1gi,j2…gi,jl…gi,jN)i=1,2,…,k;j=1,2,…,n;l=1,2,…,N其中g(shù)i,jl表示了每組k個(gè)輸入比特中第i個(gè)比特經(jīng)l-1組延遲后的輸出與每組n個(gè)輸出比特中第j個(gè)模2和的輸入端的連接關(guān)系，gi,jl=1表示有連線，gi,jl=0表示無連線則生成矩陣的一般形式為

12.3卷積碼的解析表示半無限矩陣表示2912.3卷積碼的解析表示半無限矩陣表示式中，Gl（l=1,2,…,N）是k行n列子矩陣，有12.3卷積碼的解析表示半無限矩陣表示30差錯(cuò)控制編碼復(fù)習(xí)－思考題在通信系統(tǒng)中采用差錯(cuò)控制的目的是什么？什么是隨機(jī)信道？什么是突發(fā)信道？什么是混合信道？常用的差錯(cuò)控制方法有哪些？試比較其優(yōu)缺點(diǎn)。什么試分組碼？其構(gòu)成有何特點(diǎn)？試述碼重、碼距、編碼效率的定義、一種編碼的最小碼距與其檢錯(cuò)和糾錯(cuò)能力有什么關(guān)系？什么是奇偶監(jiān)督碼？其檢錯(cuò)能力如何？什么是線性碼？它具有哪些重要性質(zhì)？什么是循環(huán)碼？循環(huán)碼的生成多項(xiàng)式如何確定？卷積碼和分組碼之間有何異同點(diǎn)？卷積碼是否為線性碼？什么是卷積碼的樹狀圖、網(wǎng)格圖和狀態(tài)圖？差錯(cuò)控制編碼復(fù)習(xí)－思考題在通信系統(tǒng)中采用差錯(cuò)控制的目的是什么31差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)基本計(jì)算（1）抗干擾能力e，t與dmin之間的關(guān)系（2）對(duì)線性分組碼，dmin=Wmin（3）奇偶監(jiān)督碼編碼（4）漢明碼參數(shù)（n=2r-1，r>=3）（5）編碼效率R＝k/n線性分組碼（1）編碼A=MG，典型陣G=IkQ（2）監(jiān)督AHT=O，典型陣H=PIr（3）糾錯(cuò)S=BHT=EHTQ=PT，GHT=O差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)基本計(jì)算Q=PT，GHT=32差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)循環(huán)碼（1）生成多項(xiàng)式g(D)（2）g(D)→G→典型G→典型Ｈ（同線性分組碼）（3）編碼：A(D)=Dn-kM(D)+r(D)（4）譯碼：卷積碼(n,k,N)（1）約束長度N的含義：相互關(guān)聯(lián)的碼段總數(shù)（2）根據(jù)編碼器原理圖寫出yi~mi關(guān)系式（3）根據(jù)輸入信碼求出卷積碼，有如下多種方法：根據(jù)輸出、輸入關(guān)系式：yi~mi根據(jù)生成多項(xiàng)式gi根據(jù)各種圖形：樹狀圖、網(wǎng)格圖、狀態(tài)圖（4）狀態(tài)圖畫法差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)循環(huán)碼33練習(xí)題1、已知三個(gè)碼組為(001010),(101101),(010001)。若用于檢錯(cuò)，能檢出幾位錯(cuò)碼？若用于糾錯(cuò)，能糾正幾位錯(cuò)碼？若同時(shí)用于檢錯(cuò)和糾錯(cuò)，各能糾、檢幾位錯(cuò)碼？根據(jù)三個(gè)碼組可知該碼的最小碼距dmin＝4。當(dāng)用于檢錯(cuò)時(shí)，由dmin≥e+1可得e=3，即能檢出3位錯(cuò)碼；當(dāng)用于糾錯(cuò)時(shí)，由dmin≥2t+1可得t=1，即能糾正1位錯(cuò)碼；當(dāng)同時(shí)用于檢錯(cuò)和糾錯(cuò)時(shí)，由dmin≥e+t+1（e≥t）可得t=1,e=2，即能糾正1位錯(cuò)碼，同時(shí)檢測2位錯(cuò)碼。練習(xí)題1、已知三個(gè)碼組為(001010),(101101),34練習(xí)題2、設(shè)一線性分組碼的錯(cuò)碼圖樣如表所示。試：（1）確定(n,k)中的n,k值（2）求監(jiān)督矩陣H；（3）求生成矩陣G；（4）寫出全部碼組；（5）求dmin；（6）若接收碼組B=(0111111)，試糾正之。（7）若編碼器輸出碼元速率為350Bd，求其輸入碼元速率。錯(cuò)碼位置S1S2S3a6110a5101a4011a3111a2100a1010a0001無錯(cuò)000練習(xí)題2、設(shè)一線性分組碼的錯(cuò)碼圖樣如表所示。試：錯(cuò)碼位置S135解：1、由表可知{a}為a6~a0，故n=7。又S為rbit，得r=3，于是k=4，此為（7，4）碼。2、表中內(nèi)容為HT（除全0外），故有：3、解：1、由表可知{a}為a6~a0，故n=7。又S為rbit36解：4、有兩個(gè)方法：a：A=MG，然后從0000~1111排列出16種信息碼，分別與G相乘。 b:在生成矩陣中取一行，兩行之和，三行之和，四行之和，以及取零行（全0碼），組成全部碼組，共有C40＋C41＋C42＋C43＋C44＝16種。5、dmin=Wmin=36、

解：4、有兩個(gè)方法：a：A=MG，然后從0000~1111排377、編碼效率R＝k/n=4/7輸入碼元速率＝R×輸出碼元速率 ＝（4/7）×350＝200Bd7、編碼效率R＝k/n=4/738練習(xí)題3、已知(7,3)循環(huán)碼的全部碼組為(0000000),(0011101),(0111010),(1110100),(1101001),(1010011),(0100111),(1001110)。試求：（1）生成多項(xiàng)式g(D)；（2）典型生成矩陣G；（3）典型監(jiān)督矩陣H；（4）列出錯(cuò)碼圖樣表；（5）是否為漢明碼？練習(xí)題3、已知(7,3)循環(huán)碼的全部碼組為(0000000)39解：1、根據(jù)生成多項(xiàng)式含義找到題中的第二碼組（0011101），對(duì)應(yīng)有：g(D)=D4+D3+D2+12、3、解：1、根據(jù)生成多項(xiàng)式含義找到題中的第二碼組（001110140解：4、dmin=Wmin=4，所以t=1。列出錯(cuò)碼圖樣如下圖：5、由于不滿足n=2r-1，因而它不是漢明碼。錯(cuò)碼位置S1S2S3S4a61110a50111a41101a31000a20100a10010a00001無錯(cuò)0000解：4、dmin=Wmin=4，所以t=1。列出錯(cuò)碼圖樣如下41練習(xí)題4、已知D7+1=(D3+D2+1)(D3+D+1)(D+1)。另g1(D)=D3+D2+1, g2(D)=D3+D+1, g3(D)=D+1。分別討論：（1）g(D)=g1(D)g2(D)（2）g(D)=g2(D)g3(D)兩種情況下，由g(D)生成的7位循環(huán)碼的檢錯(cuò)與糾錯(cuò)能力。練習(xí)題4、已知D7+1=(D3+D2+1)(D3+D+1)(42練習(xí)題5、設(shè)有一（3,1,4）卷積碼，其編碼器輸出y與m1,m2,m3,m4之間的關(guān)系為：Y1=m4;Y2=m1+m2+m3;Y3=m2+m3+m4并給定輸入信碼為110100，試：（1）畫出編碼器原理圖（2）根據(jù)題目給定的關(guān)系式求輸出序列（3）采用生成多項(xiàng)式計(jì)算輸出序列；（4）畫出該卷積碼編碼器的狀態(tài)圖；（5）根據(jù)狀態(tài)圖求輸出序列。練習(xí)題5、設(shè)有一（3,1,4）卷積碼，其編碼器輸出y與m1,431、2、假設(shè)零初始條件，即m1=m2=m3=m4=0。當(dāng)?shù)?個(gè)信碼進(jìn)入時(shí)，m4=1，y1=m4=1,y2=m1+m2+m3=0,y3=m2+m3+m4=1。當(dāng)?shù)?個(gè)信碼進(jìn)入時(shí)，有m4=1,m3=1,m2=m1=0。于是有：y1=1,y2=1,y3=0。以此類推?？傻茫狠斎胄畔⒋a：110100輸出卷積碼：101110000100001011為系統(tǒng)碼。1、443、生成多項(xiàng)式為：g1(D)=1,g2(D)=D3+D2+D,g3(D)=D2+D+1又知信息碼多項(xiàng)式m(D)=D3+D+1,因此，Y1(D)=m(D)g1(D)=D3+D+1(110100)Y2(D)=m(D)g2(D)=D6+D5+D(0100011)Y3(D)=m(D)g3(D)=D5+D4+1(1000110)3、生成多項(xiàng)式為：g1(D)=1,g2(D)=D3+D2+D45第十二章卷積碼第十二章卷積碼46主要內(nèi)容和重點(diǎn)基本概念卷積碼的圖解表示樹狀圖網(wǎng)格圖狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖卷積碼的解析表示延時(shí)算子多項(xiàng)式表示半無限矩陣表示主要內(nèi)容和重點(diǎn)基本概念4712.1基本概念

按照信息碼元和監(jiān)督碼元之間的約束方式不同分為(n,k)分組碼：每個(gè)碼組的(n-k)個(gè)校驗(yàn)位僅與本碼組的k個(gè)信息位有關(guān)，而與其他碼組無關(guān)為了達(dá)到一定的糾錯(cuò)能力和編碼效率（Rc=k/n），n通常較大，編譯碼時(shí)存儲(chǔ)信息碼產(chǎn)生的時(shí)延隨n增大而線性增加(n,k,N)卷積碼：在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的n個(gè)碼元，不僅取決于這段時(shí)間中的k個(gè)信息位，而且取決于前(N-1)段時(shí)間內(nèi)的信息位也是把k個(gè)信息比特編成n個(gè)比特，但k和n很小，延時(shí)小編碼過程中相互關(guān)聯(lián)的碼元為Nn個(gè)糾錯(cuò)能力隨N的增加而增大。在編碼器復(fù)雜性相同的情況下，卷積碼的性能優(yōu)于分組碼未有嚴(yán)格的數(shù)學(xué)手段有規(guī)律地聯(lián)系糾錯(cuò)性能和碼的構(gòu)成，采用計(jì)算機(jī)搜索好碼N（或Nn）定義為卷積碼的約束長度編碼效率Rc=k/n12.1基本概念按照信息碼元和監(jiān)督碼元之間的約束方式不4812.1基本概念

表示方法：解析法：延時(shí)算子多項(xiàng)式表示、半無限矩陣表示圖解法：樹狀圖、網(wǎng)格圖、狀態(tài)圖譯碼方法：門限譯碼：即大數(shù)邏輯譯碼性能最差，但硬件簡單Viterbi（維特比）譯碼：屬最大似然譯碼具最佳性能，但硬件實(shí)現(xiàn)復(fù)雜序列（序貫）譯碼：屬最大似然譯碼在性能和硬件方面介于兩者之間12.1基本概念表示方法：4912.1基本概念

卷積碼編碼器的一般形式N段組成的輸入移位寄存器，每段k級(jí)，共Nk位寄存器n個(gè)模2和相加器n級(jí)組成的輸出移位寄存器12.1基本概念卷積碼編碼器的一般形式5012.1基本概念

卷積碼編碼器的一般形式（續(xù)）由圖可知：n個(gè)輸出比特不但與當(dāng)前k個(gè)輸入比特有關(guān)，而且與以前的(N-1)k個(gè)輸入信息比特有關(guān)整個(gè)編碼過程可看成：輸入信息序列與移位寄存器和模2和連接方式所決定的另一個(gè)序列的卷積12.1基本概念卷積碼編碼器的一般形式（續(xù)）5112.2卷積碼的圖解表示主要內(nèi)容樹狀圖網(wǎng)格圖狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖12.2卷積碼的圖解表示主要內(nèi)容5212.2卷積碼的圖解表示樹狀圖(2,1,3)卷積編碼器：輸出移位寄存器用轉(zhuǎn)換開關(guān)代替，每輸入1個(gè)信息比特經(jīng)編碼產(chǎn)生2個(gè)輸出比特設(shè)移位寄存器初始狀態(tài)為全0第1個(gè)輸入比特：為0，輸出比特=00；為1，輸出比特=11第2個(gè)比特輸入，第1個(gè)比特右移1位，輸出比特同時(shí)受當(dāng)前輸入比特和前一個(gè)輸入比特的影響第3個(gè)比特輸入，第1、2個(gè)比特各右移1位，輸出比特同時(shí)由這3位移位寄存器存儲(chǔ)的比特共同決定第4個(gè)比特輸入，第1個(gè)比特移出移位寄存器，不對(duì)后續(xù)編碼產(chǎn)生影響12.2卷積碼的圖解表示樹狀圖5312.2卷積碼的圖解表示樹狀圖（續(xù)）：(2,1,3)卷積編碼器移位過程可用樹狀圖表示用a、b、c、d表示移位寄存器mj-2mj-1的4種可能狀態(tài)：00、01、10和11樹狀圖用mj=0和mj-2mj-1=00作起點(diǎn)，即從a點(diǎn)出發(fā)隨著移位寄存器和輸入比特的不同，樹狀圖陸續(xù)分成4條支路，2上、2下。上支路對(duì)應(yīng)于輸入比特為0，下支路對(duì)應(yīng)于輸入比特為1每條支路（樹叉）上標(biāo)注的碼元為輸出比特，每個(gè)節(jié)點(diǎn)上標(biāo)注的a、b、c、d為移位寄存器的狀態(tài)對(duì)j個(gè)輸入信息比特，有2j條支路，但在j=N≥3時(shí)，樹狀圖的節(jié)點(diǎn)自上而下開始重復(fù)出現(xiàn)4種狀態(tài)（相當(dāng)于移位超過移位寄存器長度，狀態(tài)已重復(fù)出現(xiàn)）12.2卷積碼的圖解表示樹狀圖（續(xù)）：(2,1,5412.2卷積碼的圖解表示樹狀圖（續(xù)）——樹狀圖分析：第1個(gè)輸入比特m1=0時(shí)，輸出比特x1,1x2,1=00；m1=1時(shí)x1,1x2,1=11。即從a點(diǎn)出發(fā)有2條支路（樹叉）可選：m1=0取上支路，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1取下支路，下一節(jié)點(diǎn)mj-2mj-1=01（即b）12.2卷積碼的圖解表示樹狀圖（續(xù)）——樹狀圖分析：5512.2卷積碼的圖解表示樹狀圖（續(xù)）——(2,1,3)卷積編碼器樹狀圖分析：輸入第2個(gè)比特，移位寄存器右移1位后，上支路情況下移位寄存器狀態(tài)mj-2mj-1仍為00，即a，下支路mj-2mj-1=01，即b對(duì)a，mj-2mj-1=00。若m1=0時(shí)，x1,1x2,1=00，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1時(shí)x1,1x2,1=11，下一節(jié)點(diǎn)mj-2mj-1=01（為b）對(duì)b，mj-2mj-1=01。若m1=0時(shí)，x1,1x2,1=10，下一節(jié)點(diǎn)mj-2mj-1=10（為c）；m1=1時(shí)x1,1x2,1=01，下一節(jié)點(diǎn)mj-2mj-1=11（為d）輸入第3個(gè)比特（a、b的情況重復(fù)，故可不考慮）對(duì)c，mj-2mj-1=10。若m1=0時(shí)，x1,1x2,1=11，下一節(jié)點(diǎn)mj-2mj-1=00（為a）；m1=1時(shí)x1,1x2,1=00，下一節(jié)點(diǎn)mj-2mj-1=01（為b）對(duì)d，mj-2mj-1=11。若m1=0時(shí)，x1,1x2,1=01，下一節(jié)點(diǎn)mj-2mj-1=10（為c）；m1=1時(shí)x1,1x2,1=10，下一節(jié)點(diǎn)mj-2mj-1=11（為d）12.2卷積碼的圖解表示樹狀圖（續(xù)）——(2,1,5612.2卷積碼的圖解表示網(wǎng)格圖按照碼樹中的重復(fù)性，可得一種更為緊湊的圖形表示把碼樹中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起12.2卷積碼的圖解表示網(wǎng)格圖5712.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）碼樹中的上支路（對(duì)應(yīng)輸入比特0）用實(shí)線表示，下支路（對(duì)應(yīng)輸入比特1）用虛線表示12.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）5812.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）支路上標(biāo)注的碼元為輸出比特，自上而下4行節(jié)點(diǎn)分別表示a、b、c、d四種狀態(tài)。通常有2N-1種狀態(tài)，從第N節(jié)開始，圖形開始重復(fù)而完全相同12.2卷積碼的圖解表示網(wǎng)格圖（續(xù)）5912.2卷積碼的圖解表示狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖取出已達(dá)到穩(wěn)定狀態(tài)的一節(jié)網(wǎng)格，可得到狀態(tài)圖再把目前狀態(tài)與下一行狀態(tài)重疊起來，可得到反映狀態(tài)轉(zhuǎn)移的狀態(tài)轉(zhuǎn)移圖12.2卷積碼的圖解表示狀態(tài)圖和狀態(tài)轉(zhuǎn)移圖6012.2卷積碼的圖解表示例：對(duì)上述(2,1,3)卷積編碼器，若起始狀態(tài)為a，輸入序列為110111001000，求輸出序列和狀態(tài)變化路徑解：由該卷積碼的網(wǎng)格圖表示，找出編碼時(shí)網(wǎng)格圖中的路徑如圖所示，由此可得到輸出序列和狀態(tài)變化路徑，畫在同一圖中12.2卷積碼的圖解表示例：對(duì)上述(2,1,3)6112.2卷積碼的圖解表示對(duì)于(n,k,N)卷積碼的一般情況，有如下結(jié)論對(duì)應(yīng)于每組k個(gè)輸入比特，編碼后產(chǎn)生n個(gè)輸出比特樹狀圖中每個(gè)節(jié)點(diǎn)引出2k條支路網(wǎng)格圖和狀態(tài)圖（狀態(tài)轉(zhuǎn)移圖）都有2k(N-1)種可能的狀態(tài)。每個(gè)狀態(tài)引出2k條支路，同時(shí)也有2k條支路從其它狀態(tài)或本狀態(tài)引入12.2卷積碼的圖解表示對(duì)于(n,k,N)卷積碼6212.3卷積碼的解析表示主要內(nèi)容延時(shí)算子多項(xiàng)式表示半無限矩陣表示12.3卷積碼的解析表示主要內(nèi)容6312.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示將編碼器中移位寄存與模2和的連接關(guān)系以及輸入、輸出序列都表示為延時(shí)算子D的多項(xiàng)式如輸入序列1101110…表示為M(D)=1+D+D3+D4+D5+…啞變量D的冪次等于相對(duì)于時(shí)間起點(diǎn)的單位延時(shí)數(shù)目，時(shí)間起點(diǎn)通常選在第1個(gè)輸出比特通常，輸入序列可表示為M(D)=m1+m2D+m3D2+m4D3+…其中，m1、m2、m3、m4…為輸入比特的二進(jìn)制表示（1或0）12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示6412.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示用D算子多項(xiàng)式表示移位寄存器各級(jí)與各模2和連接關(guān)系時(shí)，若某級(jí)寄存器與某模2和相連，則多項(xiàng)式中相應(yīng)項(xiàng)的系數(shù)為1，否則為0（表示無連接線）(2,1,3)卷積碼編碼器中，左、右兩個(gè)模2和與寄存器各級(jí)的連接關(guān)系可表示為G1(D)=1+D+D2G2(D)=1+D212.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示6512.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）把表示移位寄存器與模2和連接關(guān)系的多項(xiàng)式稱為生成多項(xiàng)式由生成多項(xiàng)式用多項(xiàng)式相乘可計(jì)算出輸出序列以輸入序列1101110…為例，可得x1(D)=G1(D)×M(D)=(1+D+D2)(1+D+D3+D4+D5+…)=1+D5+D7+…x2(D)=G2(D)M(D)=(1+D2)(1+D+D3+D4+D5+…)=1+D+D2+D4+D6+D7+…)由此，輸出序列x1=(x1,1,x1,2,x1,3,…)=10000101…x2=(x2,1,x2,2,x2,3,…)=11101011…x==(x1,1,x2,1,x1,2,x2,2,x1,3,x2,3,…)=1101010001100111…結(jié)果與前面圖解法所得結(jié)果相同12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）6612.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）常用二進(jìn)制或八進(jìn)制序列表示生成多項(xiàng)式。如上例：G1(D)=1+D+D2g1=(111)=(7)8G2(D)=1+D2g2=(101)=(5)8這種表示主要是為了方便12.3卷積碼的解析表示延時(shí)算子多項(xiàng)式表示（續(xù)）6712.3卷積碼的解析表示半無限矩陣表示輸入信息序列和輸出序列都用半無限矢量表示以(2,1,3)卷積碼為例，有M=[m1m2m3…]X=[x1,1x2,1x1,2x2,2x1,3x2,3…]當(dāng)?shù)?個(gè)信息比特輸入時(shí)，若移位寄存器起始狀態(tài)為全0，兩個(gè)輸出比特為x1,1=m1x2,1=m1當(dāng)?shù)?個(gè)信息比特輸入時(shí)，移位寄存器右移1位，輸出為x1,2=m2+m1x2,2=m2當(dāng)?shù)?個(gè)信息比特輸入時(shí)，有x1,3=m3+m2+m1x2,3=m3+m112.3卷積碼的解析表示半無限矩陣表示6812.3卷積碼的解析表示半無限矩陣表示當(dāng)?shù)趈個(gè)信息比特輸入時(shí)，輸出為x1,j=mj+mj-1+mj-2x2,j=mj+mj-2上式寫成矩陣形式，即[mjmj-1mj-2]A=[x1,jx2,j]其中12.3卷積碼的解析表示半無限矩陣表示6912.3卷積碼的解析表示半無限矩陣表示當(dāng)?shù)?、2信息比特輸入時(shí)存在過渡過程[m100]T1=[x1,1x2,1][m1m20]T2=[x1,2x2,2]其中，12.3卷積碼的解析表示半無限矩陣表示7012.3卷積碼的解析表示半無限矩陣表示把上述編碼過程綜合起來，可得矩陣表示如下X=MG其中，G為生成矩陣（半無限，矩陣的空白區(qū)元素均為0）12.3卷積碼的解析表示半無限矩陣表示7112.3卷積碼的解析表示半無限矩陣表示生成矩陣和生成多項(xiàng)式之間存在確定關(guān)系已知(2,1,3)卷積碼的生成序列為g1=(111)=(g11g12g13)g2=(101)=(g21g22g23)把生成序列g(shù)1、g2按如下方法交錯(cuò)排列，即可得生成矩陣12.3卷積碼的解析表示半無限矩陣表示7212.3卷積碼的解析表示半無限矩陣表示生成矩陣和生成多項(xiàng)式之間存在確定關(guān)系（續(xù)）結(jié)果與前面表示的生成矩陣相同，上式可表示為其中，每個(gè)子矩陣Gi（i=1,2,3）由一行二列組成：G1=(g11g21)G2=(g12g22)G3=(g13g23)12.3卷積碼的解析表示半無限矩陣表示7312.3卷積碼的解析表示半無限矩陣表示推廣：對(duì)于(n,k,N)碼，有X=MG其中，M=[m1,1m2,1m3,1…mk,1m1,2m2,2m3,2…mk,2…]X=[x1,1x2,1x3,1…xn,1x1,2x2,2x3,2…xn,2…]已知該碼的生成序列一般表達(dá)式為

gi,j=(gi,j1gi,j2…gi,jl…gi,jN)i=1,2,…,k;j=1,2,…,n;l=1,2,…,N其中g(shù)i,jl表示了每組k個(gè)輸入比特中第i個(gè)比特經(jīng)l-1組延遲后的輸出與每組n個(gè)輸出比特中第j個(gè)模2和的輸入端的連接關(guān)系，gi,jl=1表示有連線，gi,jl=0表示無連線則生成矩陣的一般形式為

12.3卷積碼的解析表示半無限矩陣表示7412.3卷積碼的解析表示半無限矩陣表示式中，Gl（l=1,2,…,N）是k行n列子矩陣，有12.3卷積碼的解析表示半無限矩陣表示75差錯(cuò)控制編碼復(fù)習(xí)－思考題在通信系統(tǒng)中采用差錯(cuò)控制的目的是什么？什么是隨機(jī)信道？什么是突發(fā)信道？什么是混合信道？常用的差錯(cuò)控制方法有哪些？試比較其優(yōu)缺點(diǎn)。什么試分組碼？其構(gòu)成有何特點(diǎn)？試述碼重、碼距、編碼效率的定義、一種編碼的最小碼距與其檢錯(cuò)和糾錯(cuò)能力有什么關(guān)系？什么是奇偶監(jiān)督碼？其檢錯(cuò)能力如何？什么是線性碼？它具有哪些重要性質(zhì)？什么是循環(huán)碼？循環(huán)碼的生成多項(xiàng)式如何確定？卷積碼和分組碼之間有何異同點(diǎn)？卷積碼是否為線性碼？什么是卷積碼的樹狀圖、網(wǎng)格圖和狀態(tài)圖？差錯(cuò)控制編碼復(fù)習(xí)－思考題在通信系統(tǒng)中采用差錯(cuò)控制的目的是什么76差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)基本計(jì)算（1）抗干擾能力e，t與dmin之間的關(guān)系（2）對(duì)線性分組碼，dmin=Wmin（3）奇偶監(jiān)督碼編碼（4）漢明碼參數(shù)（n=2r-1，r>=3）（5）編碼效率R＝k/n線性分組碼（1）編碼A=MG，典型陣G=IkQ（2）監(jiān)督AHT=O，典型陣H=PIr（3）糾錯(cuò)S=BHT=EHTQ=PT，GHT=O差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)基本計(jì)算Q=PT，GHT=77差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)循環(huán)碼（1）生成多項(xiàng)式g(D)（2）g(D)→G→典型G→典型Ｈ（同線性分組碼）（3）編碼：A(D)=Dn-kM(D)+r(D)（4）譯碼：卷積碼(n,k,N)（1）約束長度N的含義：相互關(guān)聯(lián)的碼段總數(shù)（2）根據(jù)編碼器原理圖寫出yi~mi關(guān)系式（3）根據(jù)輸入信碼求出卷積碼，有如下多種方法：根據(jù)輸出、輸入關(guān)系式：yi~mi根據(jù)生成多項(xiàng)式gi根據(jù)各種圖形：樹狀圖、網(wǎng)格圖、狀態(tài)圖（4）狀態(tài)圖畫法差錯(cuò)控制編碼復(fù)習(xí)——計(jì)算方面的考點(diǎn)循環(huán)碼78練習(xí)題1、已知三個(gè)碼組為(001010),(101101),(010001)。若用于檢錯(cuò)，能檢出幾位錯(cuò)碼？若用于糾錯(cuò)，能糾正幾位錯(cuò)碼？若同時(shí)用于檢錯(cuò)和糾錯(cuò)，各能糾、檢幾位錯(cuò)碼？根據(jù)三個(gè)碼組可知該碼的最小碼距dmin＝4。當(dāng)用于檢錯(cuò)時(shí)，由dmin≥e+1可得e=3，即能檢出3位錯(cuò)碼；當(dāng)用于糾錯(cuò)時(shí)，由dmin≥2t+1可得t=1，即能糾正1位錯(cuò)碼；當(dāng)同時(shí)用于檢錯(cuò)和糾錯(cuò)時(shí)，由dmin≥e+t+1（e≥t）可得t=1,e=2，即能糾正1位錯(cuò)碼，同時(shí)檢測2位錯(cuò)碼。練習(xí)題1、已知三個(gè)碼組為(001010),(101101),79練習(xí)題2、設(shè)一線性分組碼的錯(cuò)碼圖樣如表所示。試：（1）確定(n,k)中的n,k值（2）求監(jiān)督矩陣H；（3）求生成矩陣G；（4）寫出全部碼組；（5）求dmin；（6）若接收碼組B=(0111111)，試糾正之。（7）若編碼器輸出碼元速率為350Bd，求其輸入碼元速率。錯(cuò)碼位置S1S2S3a6110a5101a4011a3111a2100a1010a0001無錯(cuò)000練習(xí)題2、設(shè)一線性分組碼的錯(cuò)碼圖樣如表