PAGEPAGE22摘要卷積碼是一種性能優越的信道編碼，它的編碼器和譯碼器都比較容易實現，同時它具有較強的糾錯能力，隨著糾錯編碼理論的研究不斷深入，卷積碼的實際應用越來越廣泛。本文不僅對卷積碼和卷積碼的編譯碼有一個簡單的介紹，而且對（212）卷積碼進行了編碼和譯碼，最后，通過MATLAB對（212）卷積碼進行編譯的仿真，對仿真結果進行了解釋。關鍵字：卷積碼、信道編碼、卷積碼編譯碼、MATLAB仿真

目錄摘要 1一、引言 31.1發展歷史及研究狀況 31.2設計目的和意義 31.3設計方法 4二、卷積碼編譯碼原理 52.1卷積碼編碼原理 52.2編碼器 62.3卷積碼譯碼原理 72.4VITEBI譯碼的關鍵步驟 82.4.1輸入與同步單元 82.4.2支路量度計算 82.4.3路徑量度的存儲與更新 82.4.4信息序列的存儲與更新 82.4.5判決與輸出單元 8三、卷積碼編碼實現 93.1編碼原理分析 93.2卷積碼編碼流程圖 10四、卷積碼譯碼實現 114.1譯碼編程思路 114.2卷積碼譯碼流程圖 11五、卷積碼編譯碼程序的編譯及仿真波形 125.1卷積碼編碼仿真 135.2卷積碼譯碼仿真 135.3卷積碼糾錯碼仿真 15六、總結 16七、參考文獻 17附錄 18一、引言1.1發展歷史及研究狀況1948年，Bell實驗室的C.E.Shannon發表的《通信的數學理論》，是關于現代信息理論的奠基性論文，它的發表標志著信息與編碼理論這一學科的創立。20世紀40年代，R.Hamming和M.Golay提出了第一個實用的差錯控制編碼方案，使編碼理論這個應用數學分支的發展得到了極大的推動。分組碼所存在的固有缺點可以通過采用其他的編碼方法來改善，這種編碼方法就是卷積碼。卷積碼是Elias等人在1955年提出的。卷積碼與分組碼的不同在于：它充分利用了各個信息塊之間的相關性。通常卷積碼記為(n，k，N)碼。卷積碼的編碼過程是連續進行的，依次連續將每k個信息元輸入編碼器，得到n個碼元，得到的碼元中的檢驗元不僅與本碼的信息元有關，還與以前時刻輸入到編碼器的信息元(反映在編碼寄存器的內容上)有關。同樣，在卷積碼的譯碼過程中，不僅要從本碼中提取譯碼信息，還要充分利用以前和以后時刻收到的碼組．從這些碼組中提取譯碼相關信息，而且譯碼也是可以連續進行的，這樣可以保證卷積碼的譯碼延時相對比較小。通常，在系統條件相同的條件下，在達到相同譯碼性能時，卷積碼的信息塊長度和碼字長度都要比分組碼的信息塊長度和碼字長度小，相應譯碼復雜性也小一些。卷積碼的譯碼通常有如下幾個比較流行的譯碼算法：由Wozencraft和Reiffen在1961年提出，Fano和Jelinek分別在1963年和1969年進行改進了的序貫譯碼算法。該算法是基于碼字樹圖結構的一種次最優概率譯碼算法。由Massey在1963年提出的門限譯碼算法。這個算法利用碼字的代數結構進行代數譯碼。由Viterbi在1967年提出的Viterbi算法是基于碼字格圖結構的一種最大似然譯碼算法，是一種最優譯碼算法。在Viterbi譯碼算法提出之后，卷積碼在通信系統中得到了極為廣泛的應用。如GSM、3G、商業衛星通信系統等。1.2設計目的和意義因為信道中信號不可避免會受到干擾而出錯。為實現可靠性通信，主要有兩種途徑:一種是增加發送信號的功率，提高接收端的信號噪聲比;另一種是采用編碼的方法對信道差錯進行控制。前者常常受條件限制，不是所有情況都能采用。而編碼理論可以解決這個問題，使得成本降低，實用性增強。隨著現代通信的發展，卷積碼以其高速性和可靠性在實際應用中越來越廣泛。1967年Viterbi譯碼算法的提出，使卷積碼成為信道編碼中最重要的編碼方式之一。在卷積碼中，因為Viterbi算法效率高，速度快，結構相對簡單等特點，被廣泛應用于各種數據傳輸系統。特別是深空通信、衛星通信系統中。因此采用Viterbi譯碼算法具有非常現實的意義。1.3設計方法本文在分析卷積碼編譯碼器原理的基礎上，通過基于MATLAB對卷積編碼，解碼進行仿真。通過仿真可以更清楚的認識到卷積碼的編碼，解碼的各個環節，并對仿真結果進行了分析。得出卷積碼Viterbi譯碼的誤比特性能和回溯長度，碼率，約束長度的關系。

二、卷積碼編譯碼原理2.1卷積碼編碼原理2.1.1卷積碼簡介積碼，又稱連環碼，是由伊萊亞斯于1955年提出來的一種非分組碼。若以（n,k,m）來描述卷積碼，其中k為每次輸入到卷積編碼器的bit數，n為每個k元組碼字對應的卷積碼輸出n元組碼字，m為編碼存儲度，也就是卷積編碼器的k元組的級數，稱m+1=K為編碼約束度m稱為約束長度。卷積碼將k元組輸入碼元編成n元組輸出碼元，但k和n通常很小，特別適合以串行形式進行傳輸，時延小。與分組碼不同，卷積碼編碼生成的n元組不僅與當前輸入的k元組有關，還與前面m-1個輸入的k元組有關，編碼過程中互相關聯的碼元個數為n*m。卷積碼的糾錯性能隨m的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優于分組碼。卷積碼編碼的當前輸出v(l)不僅與當前輸入消息u(l)相關，還與此去前輸入的m個消息u(l-1),…,u(l-m)相關，即v(l)=f(u(l),u(l-1),…,u(l-m)),l=0,1,2…卷積編碼電路中移位寄存器初態可設定為全0，電路為按段工作方式，即對每段k比特輸出入，產生一段n比特輸出。任意一輸入段u(l-h)與輸出v(l)的關系都是一個特殊的線性分組碼的編碼關系，即存在k*n的二元矩陣,使得,h=0,1,2,…,m因此對于消息段序列u=(u(0),u(1),…，u(m),u(m+1),…),相應的輸出端序列為v=(v(0),v(1),…,v(m)，v(m+1),…),并滿足卷積編碼電路在按段工作方式下只需存儲或者記憶m段的消息輸入，電路中輸入移位寄存器最多只有個有效的寄存器單元，而輸出移位寄存器僅起一個并串轉換作用。因此稱參量m為卷積碼的記憶長度（段）。二元（n，k，m）卷積碼共有個不同的狀態，記為當狀態為（或）時,輸入段（或u）產生編碼輸出端（或v）并使該狀態改變（或稱為轉移）到新的狀態(或)。到的轉移過程稱為一個轉移分支，記為（，）或（，）并標記轉移過程為或v/u。以狀態為結點，轉移分支為有向邊描述卷積碼的所有不同狀態轉移的有向圖，稱為卷積碼的狀態轉移圖。2.2編碼器2．2.1編碼器的一般結構卷積碼的編碼器一般都比較簡單。圖2-1是一般情況下的卷積碼編碼器框圖。它包括NK級的輸入移位器，一組n個模2和加法器和n級的輸出移位寄存器[6]。對應于每段k比特的輸入序列，輸出n個比特。由圖可知，n個輸出比特不但與當前的k個輸入比特有關，而且與以前的(N-1)k個輸入信息比特有關。整個編碼過程可以看成是輸入信息序列與由移位寄存器和模2加法器的連接方式所決定的另一個序列的卷積，卷積碼由此得名。本文采用的是沖擊響應描述法編碼思想。2.2．2編碼器的參數⑴有k個輸入信息端，n個輸出端（k<n）,K-1節移位寄存器（共需k(K-1)個寄存器單元），稱做（n,k,K）卷積碼。⑵通常稱K為約束長度（一般來說，約束長度越大，則碼字糾錯性能越好）。⑶碼的效率：k/n⑷編碼前，k(K-1)個寄存器單元全部復位清零。⑸由于一段消息不僅影響當前段的編碼輸出，還影響其后m段的編碼輸出，所以稱參量為卷積嗎的約束比特長度為注意進入卷積編碼器的最后m段消息仍是要編碼輸出的消息，對這最后m段消息的編碼處理，稱作卷積編碼的結尾處理。一種常見的結尾處理方法是額外輸入m段無效的0數據比特，一方面將存儲的m段消息編碼全部推出，另一方面保證編碼器回到全0的初態。2.3卷積碼譯碼原理維特比算法的基本思想是把接收到的矢量，和網格圖上諸種可能的路徑比較，刪去距離大的路徑，保留距離小的路徑，以距離最小路徑作為發碼的估值。它的原理是將接收到的信號序列,選擇其中漢明距離最小的序列作為現在的發送信號序列。為簡便,討論(n,k,N)卷積碼當k=1的情形,從全0。由卷積碼網格圖的前N-1,即最初的2N-r條路徑各不相同;當到達第N級時,每條路徑都有2N-1N級上;而第N級上的每2條支路又都匯聚在一個節點上。第N級以后的網格圖圖形完全是重復第N級的圖形。在維特比算法中,把匯聚在每個節點上的2條路徑的對數似然函數累加值進行比較;然后把具有較大對數似然函數累加值的路徑保存下來,稱此部分路徑為幸存路徑,而丟棄另一條路徑;經挑選后,第N級只留下2N-r條幸存路徑,選出的路徑連同它們的對數似然函數累加值一起被存儲起來。因每個節點引出2N-1條支路,因此以后各級中路徑的延伸都增大一倍;但比較它們的似然函數累加值后,丟棄一半,結果留存下來的路徑總數保持常數(等于其狀態數)。由此可見,上述譯碼過程中的基本操作是“加→比→選”。即每級求出對數似然函數累加值,然后兩兩比較并做出選擇。有時會出現2條路徑的對數似然函數累加值相等的情形,此時可任意選擇其中一條作為“幸存路徑”。每一級都有條幸存路徑,則當序列發送完畢后，為判斷其最后結果,通常要在網格圖的終結處加上一些結束信息。通常結束信息為N-1個已知信息,當然結束信息大于N-1也可以。在此信息到來時,因每一個狀態只有與已知發送信息相符的那條支路被延伸,因而在每級比較后,幸存路徑減少一半。因此,在接收到N-1個已知信息后,整個網格圖中只有惟一的一條幸存路徑保留下來。這就是譯碼所得到的路徑,這條譯碼路徑和發送序列是最相似的。從上述卷積碼的譯碼過程可以看出:約束長度為N時,需要存儲和計算條路徑的參量。由此可見,維特比算法的復雜度隨約束長度N按指數形式增長2N。故維特比算法適合約束長度較小(N≤10)的編碼。當編碼約束度不太大(≤10)或者誤碼率要求不太高(>)時,它的設備比較簡單,用硬件譯碼計算速度快。Viterbi譯碼的缺點是隨著約束長度的增加算法的復雜度增加很快。約束長度N為7時要比較的路徑就有64條，為8時路徑變為128條。(2<<(N-1))。所以Viterbi譯碼一般應用在約束長度小于10的場合中。2.4VITEBI譯碼的關鍵步驟2.4.1輸入與同步單元輸入同步單元為譯碼器提供正確的支路同步，每次正確地輸出屬于一條支路的n個比特。顯然，當支路定時失步時，譯碼過程中將會出現大量的差錯，只要能檢測出這種狀態，即能有效地調整支路同步。一種方法是監視路徑量度的增長率；另一種方法是檢查網格圖的路徑合并性質。當譯碼器出現失步時，網格圖中幸存路徑合并的速率比同步時慢得多[2]。2.4.2支路量度計算每當接收到一條新支路的一組n個量度值(硬判決時為n比特)，支路量度計算單元就對網格圖中每一條不同的支路確定一新的量度值。對R=k/n碼來說，每次將有2個不同的量度值。在軟判決Viterbi譯碼時，支路量度值不但隨支路不同而異，而且還與接收信號的量化值有關[2]。2.4.3路徑量度的存儲與更新在此單元中，支路量度與以前所存儲的路徑量度相加，然后對匯聚到同一節點處的支路進行路徑量度比較，選擇一條路徑量度最小的路徑保留下來。2.4.4信息序列的存儲與更新一種最佳的也是最常用的方法是基于最大似然譯碼。對于R=1/n卷積碼而言，每接收一組新的支路信息，在各個狀態的路徑存儲器中存入經“加一比一選”電路選出的一位假想信息比特，同時將最先存入路徑存儲器的一位比特輸出給判決單元。因此，每接收到一條新支路，路徑存儲器就更新一次它所存儲的假想信息序列。2.4.5判決與輸出單元在R=1/n卷積碼最佳譯碼時，應選擇具有最小路徑量度的假想信息序列中最早存入的一個比特做譯碼輸出。三、卷積碼編碼實現3.1編碼原理分析以(2，1，2)卷積碼為例，其生成多項式為：G=QUOTE(3-1)QUOTE狀態轉移方程為：(3-2)下面以圖3.1的編碼器所編出的碼為例，來說明卷積碼編碼的方法和過程。為了使過程更加清晰，這里給出該碼的狀態圖，如圖3.2所示。圖3.1（2,1,2）卷積碼編碼器圖3.2（2,1,2）卷積碼狀態轉移圖由上面狀態轉移圖得到狀態轉移的4個狀態，每一個狀態的轉移都與當前輸入消息的狀態有關。而每一個對應的輸出不僅與當前輸入的m個消息有關，還與此前輸入的相關，即根據該碼的狀態轉移圖可以列出其狀態轉移表，如表3.1所示。表3.1（2,1,2）卷積碼狀態轉移表u()()()()()()()()(00)(01)(10)(11)0(00)(00)(10)(11)(00)(10)(10)(01)1(01)(11)(11)(00)(01)(01)(11)(10)3.2卷積碼編碼原理卷積碼譯碼流程圖如下，首先輸入n位信息序列，然后根據前兩位的輸入信息及當前信息計算輸出序列，輸出2n位信息編碼。流程圖（3.3）開始開始輸入n位信息序列依據前兩位輸入信息及當前信息計算輸出序列輸出2n位信息編碼結束

四、卷積碼譯碼實現4.1譯碼編程思路譯碼總體上是先通過“加-比-選”來得到最優路徑，然后根據狀態轉移圖來得到解碼后的碼字。在整個過程中需要記錄的是到達各個狀態的累計最小漢明距離及路徑。用D(i)=hamming_distance(W(i,:),word(1:chip*2))實現與出錯碼字對比得到漢明距，用[val,index]=sort(D)來實現val中存漢明距從小到大排列，index中存對應val數據所在位置。首先初始化選前n時刻來比較漢明距，選出最小的4~8條路徑，而后每條被選出的路徑每次加一時刻進行迭代運算，選出新的漢明距最小的4~8條路徑，依次循環，直至迭代至碼組結束。最后選出4~8條路徑中最小的一條來進行譯碼。開始輸入2m位編碼序列計算到達各個狀態的累計最小漢明距離及路徑開始輸入2m位編碼序列計算到達各個狀態的累計最小漢明距離及路徑初始化前n時刻比較漢明距選出最小的6條路徑迭代至碼組結束？加一時刻迭代運算選出漢明距最小的一條路徑進行譯碼結束

上圖所示的是卷積碼的譯碼流程圖，卷積碼譯碼原理開始的時候,是首先輸入2m的編碼序列，然后計算到達各個狀態的累計最小漢明距離及其路徑，然后初始化前n時刻，計較漢明距離。選出最小的6條路徑，迭代至碼組結束，選出漢明距離最小的一條路徑進行譯碼，譯碼結束，若在迭代至碼組結束時判斷沒有結束，則加一時刻的迭代運算，在初始化前n時刻比較漢明距離之后繼續執行，知道迭代至碼組結束。

五、卷積碼編譯碼程序的編譯及仿真波形5.1卷積碼編碼仿真請輸入信息碼序列：[1011101]msg=1011101word=11110100100101圖5.1卷積碼編碼原理圖5.2卷積碼譯碼仿真請輸入收到的編碼：[11110100100101]word=11110100100101信息編碼無錯誤msg=1011101圖5.2卷積碼譯碼原理5.3卷積碼糾錯碼仿真請輸入收到的編碼：[11110100000101]word=11110100000101錯誤出現在第9位wordr=11110100100101msg=1011101圖5.3卷積碼糾錯原理圖

六、總結這次課程設計，對我的意義很大，讓我的學習能力和動手能力都有所增加，在這次的課程設計中，讓我對卷積碼的編碼和譯碼都有了一個比較深入的了解，對編譯碼用MATLAB進行仿真，讓我對MATLAB的應用能力有了一個更深入的掌握，我想這對我以后的工作會有一個很大幫助。總體對卷積碼的編碼與譯碼，以及譯碼之后的錯誤糾正，讓我對通信系統的總體原理也有一定的了解，也讓我對信道的傳輸明白了其中的道理，明白了信息在信道中傳輸的原理。通過課程設計，讓我知道了許多的生活道理，在剛剛收到老師發給我們的題目之后，感覺很是簡單，但在真正的著手開始做的時候，才發現問題很多，而最重要的問題是在程序編譯中，還有其中的原理有許多的地方不明白，對很多的名詞不知道什么意思，之后，通過在圖書館借書，上網查資料，在課堂上問老師，和團隊的同學進行討論等等，我的問題終于一點點的解決，程序也一點點的編譯了出來，仿真圖像也很好的顯示出來。這讓我明白了幾個道理，首先，我們不能小看一件小事情，所有的大事情都是在一件件的小事上建立起來的。其二，那些看是簡單的事情，當我們真正開始做的時候，就會發現不是輕而易舉就可以完成的，告訴我們更重要的是注重我們的動手能力。其三，我們都知道的是眾人拾柴火焰高的道理，這次，讓我更加的明白了它的含義，尤其是在這個競爭異常激烈的今天，我們更應該注重團隊的力量，一個人單槍匹馬，最終會被社會淘汰，而只有那些懂得團隊的人才能立足。總之，這次課程設計對我的意義很大，不僅讓我的知識增加了不少，同時也讓我懂得了許多的道理，可謂是受益匪淺。最后，非常感謝鄭玉峰老師的幫助，讓我順利的完成了這次課程設計。

七、參考文獻[1].李建新.現代通信系統分析與仿真-MATLAB通信工具箱.西安：西安電子科技大學出版社，2000.[2].樊昌信.通信原理.北京：國防工業出版社,2002.[3].劉敏.MATLAB通信仿真與應用.北京：國防工業出版社.[4].曹志剛等著.現代通信原理.北京：清華大學出版社，2001.[5].吳偉陵等著.移動通信原理.北京：電子工業出版社，2005.[6]RodgerE.Ziemer，RogerL.Peterson著.尹長川，郝建軍，羅濤等譯.數字通信基礎(IntroductiontoDigitalCommunication).原書第2版.北京：機械工業出版社，2005.1[7]鄧華.Matlab通信仿真及應用實例詳解.北京：人民郵電出版社，2003.9[8]陳國通.數字通信.哈爾濱：哈爾濱工業大學出版社，2002.4[9]孫祥Matlab7.0基礎教程.北京：清華大學出版社，2005.5附錄：decode.mclear;clc;word=input('請輸入收到的編碼：');wordmsg=decode_conv212(word);wordr=encode_conv212(msg);c=1;fori=1:1:length(word)ifword(i)~=wordr(i)c=0;s=i;endendifc==0fprintf('錯誤出現在第%1.0f位\n',s);wordrelsefprintf('信息編碼無錯誤');endmsga=length(msg);x=.01:.01:a;[m,n]=size([msg]'*ones(1,100));y=reshape(([msg]'*ones(1,100))',1,m*n);subplot(2,1,2)plot(x,y)title('信息碼序列')xlabel('t')ylabel('msg')axis([0length(msg)-0.51.5])b=length(word);x=.01:.01:b;[m,n]=size([word]'*ones(1,100));y=reshape(([word]'*ones(1,100))',1,m*n);subplot(2,1,1)plot(x,y)holdonifc==0z=reshape(([wordr]'*ones(1,100))',1,m*n);plot(x,z,'--r')endtitle('編碼序列')xlabel('t')ylabel('word')axis([0length(word)-0.51.5])decode_conv212.mfunctionmsg=decode_conv212(word)chip=5;fori=1:2^chipM(i,:)=de2bi(i-1,chip);W(i,:)=encode_conv212(M(i,:));D(i)=hamming_distance(W(i,:),word(1:chip*2));end[val,index]=sort(D);ret_msg=zeros(1,length(word)/2);fori=1:6ret_msg(i,1:chip)=M(index(i),:);ret_dis(i)=D(index(i));enditer=(length(word)-chip*2)/2;fori=1:iterforj=1:6msg_temp1=[ret_msg(j,1:chip+i-1)0];msg_temp2=[ret_msg(j,1:chip+i-1)1];word_temp1=encode_conv212(msg_temp1);word_temp2=encode_conv212(msg_temp2);dis_temp1=hamming_distance(word_temp1,word(1:chip*2+2*i));dis_temp2=hamming_distance(word_temp2,word(1:chip*2+2*i));if(dis_temp1<dis_temp2)ret_msg(j,1:chip+i)