【文章內(nèi)容簡介】 列合并為一個碼字序列為C=(ca0cb0ca1cb1ca2cb2……)。若輸入信息序列為[1 1 0 1]。則P1=[1 0 0 1 0 1 0 1 0 1]，P2=[1 1 1 1 1 0 1 1 1 1],C=[1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1]。如圖32所示為(2,1,3)卷積碼的編碼器，也是本次課程設(shè)計所研究的卷積碼編碼器，由于其生成沖激響應(yīng)分別為[1 1 1]和[1 0 1]，故被稱為(7,5) 碼[17]。 Z1Z1++ 圖32 （2,1,3）卷積碼編碼器 卷積碼圖形表示法除了用解析法描述卷積碼的編碼外，還可以使用比較形象的圖形法來表示卷積碼。比較常用的有狀態(tài)圖法，樹圖法和網(wǎng)格圖法。狀態(tài)圖法：由于卷積碼編碼器在下一時刻的輸出取決于編碼器的當(dāng)前狀態(tài)和下一時刻的輸入，而編碼器當(dāng)前狀態(tài)取決于編碼器當(dāng)前各移位寄存器的存儲內(nèi)容。稱編碼器當(dāng)前各移位寄存器存儲內(nèi)容(0或1)為編碼器在該時刻的狀態(tài)(此狀態(tài)代表記憶以前的輸入信息)。隨著信息序列的不斷輸入，編碼器不斷從一個狀態(tài)轉(zhuǎn)移到另外一個狀態(tài)，并且輸出相應(yīng)的編碼序列。編碼器的總可能狀態(tài)數(shù)為2mk個。對(7,5)碼的編碼器來說，n=2，k=1，N=3，m=2。共有四個可能狀態(tài)，其狀態(tài)圖如圖33所示：0/00001001111/101/011/000/100/010/111/11圖33 卷積碼狀態(tài)圖圖中四個方塊表示狀態(tài)，狀態(tài)間的連線與箭頭表示轉(zhuǎn)移方向，連線上的數(shù)字表示是狀態(tài)發(fā)生轉(zhuǎn)移的到來比特，斜杠后的數(shù)字由一個狀態(tài)到另一個狀態(tài)轉(zhuǎn)移時的輸出碼字。如當(dāng)前狀態(tài)為11，輸入信息為0，則轉(zhuǎn)移到01狀態(tài)并輸出01碼字，若輸入信息為1，則依然為11狀態(tài)，并輸出10碼字。 樹圖法描述卷積碼的編碼過程除了用它的生成矩陣外，還可以用半無限碼樹圖。卷積碼的樹圖表示是一種形象的表示卷積碼編碼過程的方法。卷積碼的各種距離度量與樹圖有密切關(guān)系。以(2,1,3)卷積碼為例，它的生成多項式矩陣和生成矩陣分別為：GD==1+D+D2,1+D2 (31)G∞=1110111110111110…11…＝g0g1g0g2g1g0g2g1… g2…　　 (32)若輸入編碼器的信息序列M(D)=(m0,m1,m2…..)=(1 1 0 1 1 …..),則由編碼器輸出碼序列C為C = MG∞ =(11，01，01，00，01，01， )=( C0,Cl,C2, C3,…) (33)可以把這個編碼過程用如圖34所示的半無限碼樹圖來說明。設(shè)編碼器的初始狀態(tài)為0，碼樹中每個節(jié)點的下一級的上面的分支表示輸入為0，下面的分支表示輸入為l。每個分支上面的數(shù)字表示對應(yīng)次分支的輸出。因此輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。按照上面的例子，則編碼過程對應(yīng)碼樹中粗線表示的一條路徑。對該碼序列來說，樹圖上的這條路徑就是它的正確路徑。對于一般的二進制(n,k,N)編碼器來說，每次輸入的是k個信息元，有2k個可能的信息組，這對應(yīng)于從碼樹每一個節(jié)點上分出的分支樹有2k條，相應(yīng)于2k個不同信息組的輸入，并且每條都有n個碼元，作為與此相應(yīng)的輸出子碼。00由以上討論可知，卷積碼編碼過程的實質(zhì)，是在輸入信息序列的控制下，編碼器沿碼樹通過某一特定路徑的過程。顯然，譯碼過程就是根據(jù)接收序列和信道干擾的統(tǒng)計特性，譯碼器在原碼樹上力圖恢復(fù)原來編碼器所走的路徑，即尋找正確路徑的過程。其過程如圖34所示。0000S01100S010S2011101 S000101100110101100S2S2S301S000S011101S2S2110111S100 000 01S3S310圖34 ( 2,1,3)卷積碼的樹圖網(wǎng)格圖法：網(wǎng)格圖可以描述卷積碼的狀態(tài)隨時間推移而轉(zhuǎn)移的情況。該圖縱坐標(biāo)表示所有狀態(tài)，橫坐標(biāo)表示時間。網(wǎng)格圖在卷積碼的概率譯碼，特別是Viterbi譯碼中非常重要，它綜合了狀態(tài)圖法直觀簡單和樹圖法時序關(guān)系清晰的特點[18]。如圖34所示狀態(tài) t1 t2 t3 t4 t5 t6 211111111111022020020202111020 1000 01 11圖35 譯碼器網(wǎng)格圖圖中實線表示輸入0時所走分支，虛線表示輸入1時所走分支，編碼時只需從起始狀態(tài)開始依次選擇路線并讀出輸出即可。假設(shè)從a狀態(tài)開始，輸入為[1 0 1 1]，則可由圖中讀出輸出為[11 10 10 01]。 卷積碼譯碼原理 卷積碼三種譯碼方式(1)代數(shù)譯碼 代數(shù)譯碼是將卷積碼的一個編碼約束長度的碼段看作是[n0(m+1)，k0(m+1)]線性分組碼，每次根據(jù)(m+1)分支長接收數(shù)字，對相應(yīng)的最早的那個分支上的信息數(shù)字進行估計，然后向前推進一個分支。如果假設(shè)輸入的信息序列為＝(10111)，相應(yīng)的編碼輸出序列為 c＝(11100001100111)。在未超出編碼約束長度的情況下，可以通過譯碼時將接受序列與所有可能的輸出編碼序列進行比較，通過比較可以得到最小距離，進而可以得到可能的最大概率。按同樣方法判決，將每一位進行比較，進行糾錯。若此時接收序列R＝(10100001110111),先根據(jù)R的前三個分支（101000）和碼樹中前三個分支長的所有可能的 8條路徑(000000…)、(000011…)、(001110…)、(001101…)、(111011…)、(111000…)、(110101…)和(110110…)進行比較，可知(111001)與接收序列(101000)的距離最小，于是判定第 0分支的信息數(shù)字為 0。然后以R的第 1～3分支數(shù)字(100001)按同樣方法判決,依此類推下去,最后得到信息序列的估值為=(10111)，遂實現(xiàn)了糾錯。這種譯碼法，譯碼時采用的接收數(shù)字長度或譯碼約束長度為(m+1)n0，所以只能糾正不多于(dmin1)/2個錯誤(n長上的)。實用中多采用反饋擇多邏輯譯碼法實現(xiàn)。 (2)維特比譯碼維特比譯碼是根據(jù)接收序列在碼的格圖上找出一條與接收序列距離（或其他量度）為最小的一種算法。它和運籌學(xué)中求最短路徑的算法相類似。若接收序列為R=(10100101100111)，譯碼器從某個狀態(tài),例如從狀態(tài)ɑ出發(fā),每次向右延伸一個分支（對于l＜L,從每個節(jié)點出發(fā)都有2種可能的延伸,其中L是信息序列段數(shù),對l≥L，只有一種可能）,并與接收數(shù)字相應(yīng)分支進行比較,計算它們之間的距離，然后將計算所得距離加到被延伸路徑的累積距離值中。對到達(dá)每個狀態(tài)的各條路徑（有2條）的距離累積值進行比較，保留距離值最小的一條路徑，稱為幸存路徑（當(dāng)有兩條以上取最小值時，可任取其中之一）,譯碼過程如圖。圖中標(biāo)出到達(dá)各級節(jié)點的幸存路徑的距離累積值。對給定 R的估值序列為=(10111)。這種算法所保留的路徑與接收序列之間的似然概率為最大，所以又稱為最大似然譯碼。這種譯碼的譯碼約束長度常為編碼約束長度的數(shù)倍，因而可以糾正不多于(df/2)個錯誤[19]。 維特比譯碼器的復(fù)雜性隨m呈指數(shù)增大。實用中m不大于10。它在衛(wèi)星和深空通信中有廣泛的應(yīng)用。在解決碼間串?dāng)_和數(shù)據(jù)壓縮中也可應(yīng)用。 （3）序貫譯碼序貫譯碼是根據(jù)接收序列和編碼規(guī)則，在整個碼樹中搜索（既可以前進，也可以后退）出一條與接收序列距離（或其他量度）最小的一種算法。由于它的譯碼器的復(fù)雜性隨m值增大而線性增長,在實用中可以選用較大的m值（如20～40）以保證更高的可靠性。許多深空和海事通信系統(tǒng)都采用序貫譯碼。 Viterbi譯碼原理卷積碼概率譯碼的基本思路是:以接收碼流為基礎(chǔ)，逐個計算它與其他所有可能出現(xiàn)的、連續(xù)的網(wǎng)格圖路徑的距離，選出其中可能性最大的一條作為譯碼估值輸出。概率最大在大多數(shù)場合可解釋為距離最小，這種最小距離譯碼體現(xiàn)的正是最大似然的準(zhǔn)則。卷積碼的最大似然譯碼與分組碼的最大似然譯碼在原理上是一樣的，但實現(xiàn)方法上略有不同。主要區(qū)別在于:分組碼是孤立地求解單個碼組的相似度，而卷積碼是求碼字序列之間的相似度?；诰W(wǎng)格圖搜索的譯碼是實現(xiàn)最大似然判決的重要方法和途徑。用格圖描述時，由于路徑的匯聚消除了樹狀圖中的多余度，譯碼過程中只需考慮整個路徑集合中那些使似然函數(shù)最大的路徑。如果在某一點上發(fā)現(xiàn)某條路徑已不可能獲得最大對數(shù)似然函數(shù)，就放棄這條路徑，然后在剩下的“幸存”路徑中重新選擇路徑。這樣一直進行到最后第L級(L為發(fā)送序列的長度)。由于這種方法較早地丟棄了那些不可能的路徑，從而減輕了譯碼的工作量，Viterbi譯碼正是基于這種想法[20]。 對于(n, k, N)卷積碼，其網(wǎng)格圖中共2kL種狀態(tài)。由網(wǎng)格圖的前N1條連續(xù)支路構(gòu)成的路徑互不相交，即最初2k_1條路徑各不相同，當(dāng)接收到第N條支路時，每條路徑都有2條支路延伸到第N級上，而第N級上的每兩條支路又都匯聚在一個節(jié)點上。在Viterbi譯碼算法中，把匯聚在每個節(jié)點上的兩條路徑的對數(shù)似然函數(shù)累加值進行比較，然后把具有較大對數(shù)似然函數(shù)累加值的路徑保存下來，而丟棄另一條路徑，經(jīng)挑選后第N級只留下2N條幸存路徑。選出的路徑同它們的對數(shù)似然函數(shù)的累加值將一起被存儲起來。由于每個節(jié)點引出兩條支路，因此以后各級中路徑的延伸都增大一倍，但比較它們的似然函數(shù)累加值后，丟棄一半，結(jié)果留存下來的路徑總數(shù)保持常數(shù)。由此可見，上述譯碼過程中的基本操作是，“加比選”，即每級求出對數(shù)似然函數(shù)的累加值，然后兩兩比較后作出選擇。有時會出現(xiàn)兩條路徑的對數(shù)似然函數(shù)累加值相等的情形，在這種情況下可以任意選擇其中一條作為“幸存”路徑。卷積碼的編碼器從全零狀態(tài)出發(fā)，最后又回到全零狀態(tài)時所輸出的碼序列，稱為結(jié)尾卷積碼。因此，當(dāng)序列發(fā)送完畢后，要在網(wǎng)格圖的終結(jié)處加上（N1）個己知的信息作為結(jié)束信息。在結(jié)束信息到來時，由于每一狀態(tài)中只有與已知發(fā)送信息相符的那條支路被延伸，因而在每級比較后，幸存路徑減少一半。因此，在接收到（N1）個己知信息后，在整個網(wǎng)格圖中就只有唯一的一條幸存路徑保留下來，這就是譯碼所得的路徑。也就是說，在己知接收到的序列的情況下，這條譯碼路徑和發(fā)送序列是最相似的。 維特比譯碼算法性能對于(n，k，N)卷積碼，其編碼存儲度(移位寄存器單元的數(shù)量)為N，幸存路徑有2N條。每條幸存路徑(或信息序列)存儲器單元數(shù)是n*D，其中，n是卷積碼碼組寬度，D是需要存儲的碼組的個數(shù)。D的取值一般考慮取m的整倍數(shù)，稱D為幸存路徑長度。編碼存儲度和幸存路徑長度的取值問題關(guān)系到芯片規(guī)格、傳輸時延等問題。若D很大，則譯碼器的存儲量太大而難以實用。一般情況下，當(dāng)譯碼進行到第5級(每級包括m個時刻)以后，每個狀態(tài)幸存路徑的前幾個分支已基本重合在一起，這就是說每個路徑存儲器不必存儲D個很大的碼序列。譯碼時，當(dāng)譯碼器接收并處理完第D個碼組后，譯碼器中的幸存路徑存儲器已全部存滿，當(dāng)譯碼器開始處理第D+1個碼組時，他就對幸存路徑存儲器中的最頂端的碼組做出判決并輸出。1) 適當(dāng)增加幸存路徑的長度可以提高譯碼器的糾錯能力。2) 幸存路徑的長度在增加到一定值時，譯碼器糾錯能力趨于穩(wěn)定。當(dāng)N值增加到6以上，誤比特率降低幅度大為減小，曲線有合二為一的趨勢。因此，可以認(rèn)為幸存路徑長度D取編碼存儲度的6倍以上就可以取得比較好的譯碼性能。3) 選擇合適的延時。路徑量度(似然度)的累加選取和碼字延時判決輸出提高了譯碼的準(zhǔn)確性，D 越大越有利于判決的正確性，但是這又和通信的實時性背道而馳，一般D 為卷積碼約束長度N的5~10 倍即可，本文算法D取50。4) 留存路徑的更新的描述。每個狀態(tài)的留存路徑選擇實際上是從當(dāng)前時刻往前推的，例如，在時刻t，又假設(shè)到達(dá)狀態(tài)s2的路徑有兩個，分別為s4 和s5，對應(yīng)的輸出碼字分別是00 和11，我們分別計算出兩條路經(jīng)的分支量度BM，并累加它們對應(yīng)的前狀態(tài)路徑量度PM_l，發(fā)現(xiàn)累加后s5 s2的PM值比s4 s2 的大，所以保留s5 所對應(yīng)的留存路徑，并更新狀態(tài)s2 所對應(yīng)的留存路徑存儲器。對每一狀態(tài)都做如此比較，保存大的分支量度BM，然后再累加前一狀態(tài)路徑量度PM_l，最后完成所有狀態(tài)的選擇，比較當(dāng)前所有狀態(tài)的路經(jīng)量度PM,選擇最大路徑，如果延時超過D 就判決輸出碼字。顯然此處判決的碼字要延時D 時刻才能移位輸出。4 卷積碼編譯碼及MATLAB仿真在本次課題研究中，我們對整個通信過程進行了仿真，其過程如下圖：序列產(chǎn)生信道編碼BPSK調(diào)制AWGN信道傳輸BPSK解調(diào)Viterbi譯碼信息輸出圖41 卷積碼編譯碼流程圖 Matlab概述計算機對科學(xué)技術(shù)的幾乎一切領(lǐng)域產(chǎn)成了極其深遠(yuǎn)的影響。熟練掌握并利用計算機進行科學(xué)計算研究及工程應(yīng)用已是廣大科研設(shè)計人員所必備的基本技能之一。從事科學(xué)研究和工程應(yīng)用時候所遇到的最大的困擾大抵是我們在計算涉及矩陣運算或畫圖時，采用Fortran、C及C++等計算機語言進行程序設(shè)計是一項十分麻煩的工作，不僅需要對所利用的有關(guān)算法有深刻的了解，還需要掌握所用語言的語法及編程技巧。Matlab軟件由美國Math Works 公司于1984 年推出,歷經(jīng)十幾年的發(fā)展和競爭，現(xiàn)已成為通用科技計算和圖視交互