卷積碼中的維特比譯碼和序貫譯碼算法

1、 卷積碼是1955年由Elias等人提出的,是一種非常有前途的編碼方法。我們在一些資料上可以找到關(guān)于分組碼的一些介紹,分組碼的實現(xiàn)是將編碼信息分組單獨(dú)進(jìn)行編碼,因此無論是在編碼還是譯碼的過程中不同碼組之間的碼元無關(guān)。卷積碼和分組碼的根本區(qū)別在于,它不是把信息序列分組后再進(jìn)行單獨(dú)編碼,而是由連續(xù)輸入的信息序列得到連續(xù)輸出的已編碼序列。即進(jìn)行分組編碼時,其本組中的n-k個校驗元僅與本組的k個信息元有關(guān),而與其它各組信息無關(guān);但在卷積碼中,其編碼器將k個信息碼元編為n個碼元時,這n個碼元不僅與當(dāng)前段的k個信息有關(guān),而且與前面的(m-1段信息有關(guān)(m為編碼的約束長度。同樣,在卷積碼譯碼過程中,不僅從此

2、時刻收到的碼組中提取譯碼信息,而且還要利用以前或以后各時刻收到的碼組中提取有關(guān)信息。而且卷積碼的糾錯能力隨約束長度的增加而增強(qiáng),差錯率則隨著約束長度增加而呈指數(shù)下降 。卷積碼(n,k,m 主要用來糾隨機(jī)錯誤,它的碼元與前后碼元有一定的約束關(guān)系,編碼復(fù)雜度可用編碼約束長度m*n來表示。一般地,最小距離d表明了卷積碼在連續(xù)m段以內(nèi)的距離特性,該碼可以在m個連續(xù)碼流內(nèi)糾正(d-1/2個錯誤。卷積碼的糾錯能力不僅與約束長度有關(guān),還與采用的譯碼方式有關(guān)?？傊?由于n,k較小,且利用了各組之間的相關(guān)性,在同樣的碼率和設(shè)備的復(fù)雜性條件下,無論理論上還是實踐上都證明:卷積碼的性能至少不比分組碼差。編碼原理回目

3、錄以二元碼為例,編碼器如圖。輸入信息序列為u =(u 0,u 1,其多項式表示為u (x =u 0+u 1x +u l x l +。 編碼器的連接可用多項式表示為g (1,1(x =1+x +x 2和g (1,2(x =1+x 2,稱為碼的子生成多項式。它們的系數(shù)矢量g (1,1=(111和g (1,2=(101稱作碼的子生成元。以子生成多項式為陣元構(gòu)成的多項式矩陣G (x =g (1,1(x ,g (1,2(x ,稱為碼的生成多項式矩陣。由生成元構(gòu)成的半無限矩陣 稱為碼的生成矩陣。其中(11,10,11是由g (1,1和g (1,2交叉連接構(gòu)成。編碼器輸出序列為c =u ·G ,稱

4、為碼序列,其多項式表示為c (x ,它可看作是兩個子碼序列c (1(x 和c (2(x 經(jīng)過合路開關(guān)S 合成的,其中c (1(x =u (x g (1,1(x 和c (2(x =u (x g (1,2(x ,它們分別是信息序列和相應(yīng)子生成元的卷積,卷積碼由此得名。卷積碼編碼器在一般情況下,輸入信息序列經(jīng)過一個時分開關(guān)被分成k 0個子序列,分別以u (x 表示,其中i =1,2,k 0,即u (x =u (x ,u (x 。編碼器的結(jié)構(gòu)由k 0×n 0階生成多項式矩陣給定。輸出碼序列由n 0個子序列組成,即c (x =c (x ,c (x ,c (x ,且c (x =u (x 

5、3;G (x 。若m 是所有子生成多項式g (x 中最高次式的次數(shù),稱這種碼為(n 0,k 0,m 卷積碼。表示方法回目錄描述卷積碼編碼器過程的方法有很多,如矩陣法、多項式、碼樹和網(wǎng)格圖等,這里我們主要介紹和卷積碼編碼器結(jié)構(gòu)密切相關(guān)的多項式法,以及與卷積碼譯碼密切相關(guān)的網(wǎng)格圖法。多項式法就是由卷積碼的生成多項式直接得出其編碼器的結(jié)構(gòu)圖。如前面例子中的(2,1,2卷積碼的生成多項式矩陣為:G(D=1 D D2,1 D2其中,D是延遲算子,生成多項式的第一項為1 D D2,表示輸出編碼的第一個碼元等于輸入碼元x(n與前兩個時刻輸入的碼元x(n-1、x(n-2的模2和,同理第二項類似。 2. 狀態(tài)圖

6、卷積碼狀態(tài)圖將編碼器寄存器中的內(nèi)容組合(x(n-1、x(n-2定義為編碼器狀態(tài)。如仍以前面所舉的例子(2,1,2為例,則該編碼器的狀態(tài)有四種:00,10,01和11,下面分別用a,b,c,d來代替。編碼器在每一個時鐘沿打入一個輸入信息x(n,因此圖示寄存器組合內(nèi)容就變?yōu)?x(n,x(n-1即狀態(tài)發(fā)生了轉(zhuǎn)移,并同時輸出G0(n、G1(n。由此我們可以將圖所示編碼過程用右圖所示的狀態(tài)圖表示。由圖所示,隨著信息序列不斷輸入,編碼器就不斷從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)并同時輸出相應(yīng)的碼序列,所以狀態(tài)圖可以完整的描述編碼器的工作過程,但是其只能顯示狀態(tài)轉(zhuǎn)移的過程而不能顯示狀態(tài)轉(zhuǎn)移發(fā)生的時刻,由此引出用來表示

7、卷積碼的另一種常用方法網(wǎng)格圖。網(wǎng)格圖就是時間與對應(yīng)狀態(tài)的轉(zhuǎn)移圖(如圖,在網(wǎng)格圖中每一個點表示該時刻的狀態(tài),狀態(tài)之間的連線表示狀態(tài)轉(zhuǎn)移。通過觀察網(wǎng)格圖可以發(fā)現(xiàn)在網(wǎng)格圖中輸入信息x(n并沒有標(biāo)出,但如觀察到轉(zhuǎn)移后的狀態(tài)表示(x(n,x(n-1就可以發(fā)現(xiàn)輸入信息已經(jīng)隱含在轉(zhuǎn)移后的狀態(tài)中。在圖中還可以發(fā)現(xiàn)兩個網(wǎng)格圖不同主要集中在轉(zhuǎn)移后狀態(tài)位置不同。重新排序結(jié)構(gòu)(即所謂蝶型結(jié)構(gòu)是為了優(yōu)化運(yùn)算而設(shè)計的,因為其中蝶型與蝶型之間是相互獨(dú)立的。 網(wǎng)格圖下面就讓我們來看看網(wǎng)格圖是如何描述卷積編碼過程的:仍以(2,1,2為例,假定輸入序列為1011010100,起始狀態(tài)(零時刻為狀態(tài)a(零狀態(tài)。第一個有效時鐘沿來臨

8、后,編碼器接收到輸入信息“1”,根據(jù)圖所示網(wǎng)格圖知該時刻(即時刻1狀態(tài)為b,并輸出其對應(yīng)的編碼結(jié)果“11”,同樣在下一個時刻(時刻2接收到輸入信息“0”,狀態(tài)變?yōu)閏 并輸出“10”,接下來的輸入數(shù)據(jù)依次類推,由此我們可以用網(wǎng)格圖作出該例子的卷積編碼過程,如圖5所示,其中兩個狀態(tài)連線之間的信息為輸出結(jié)果。譯碼方法回目錄若信道干擾序列為,其中。接收序列為其中和。這里“+”為模 2 運(yùn)算(q =p 元碼按模p 運(yùn)算。譯碼就是根據(jù)編碼規(guī)則和信道干擾的統(tǒng)計特性,對信息序列u (x 作出估值的方法。常用的有三類譯碼方法,即代數(shù)譯碼、維特比譯碼和序貫譯碼。 1. 代數(shù)譯碼樣方法判決,依此類推下去,最后得到信

9、息序列的估值為=(10111,遂實現(xiàn)了糾錯。這種譯碼法,譯碼時采用的接收數(shù)字長度或譯碼約束長度為(m +1n 0,所以只能糾正不多于(d min -1/2個錯誤(n 長上的。實用中多采用反饋擇多邏輯譯碼法實現(xiàn)。2. 維特比譯碼 維特比譯碼過程維特比譯碼是根據(jù)接收序列在碼的格圖上找出一條與接收序列距離(或其他量度為最小的一種算法。它和運(yùn)籌學(xué)中求最短路徑的算法相類似。若接收序列為出發(fā),每次向右延伸一個分支(對于l <L ,從每個節(jié)點出發(fā)都有2=2種可能的延伸,其中L 是信息序列段數(shù),對l L ,只有一種可能,并與接收數(shù)字相應(yīng)分支進(jìn)行比較,計算它們之間的距離,然后將計算所得距離加到被延伸路徑的

10、累積距離值中。對到達(dá)每個狀態(tài)的各條路徑(有2=2條的距離累積值進(jìn)行比較,保留距離值最小的一條路徑,稱為幸存路徑(當(dāng)有兩條以上取最小值時,可任取其中 之一,譯碼過程如圖。圖中標(biāo)出到達(dá)各級節(jié)點的幸存路徑的距離累積值。對給定 R 的估值序列為=(0111。這種算法所保留的路徑與接收序列之間的似然概率為最大,所以又稱為1最大似然譯碼。這種譯碼的譯碼約束長度常為編碼約束長度的數(shù)倍,因而可以糾正不多于(d f /2個錯誤。維特比譯碼器的復(fù)雜性隨m 呈指數(shù)增大。實用中m 不大于10。它在衛(wèi)星和深空通信中有廣泛的應(yīng)用。在解決碼間串?dāng)_和數(shù)據(jù)壓縮中也可應(yīng)用。 3. 序貫譯碼序貫譯碼是根據(jù)接收序列和編碼規(guī)則,在整個

11、碼樹中搜索(既可以前進(jìn),也可以后退出一條與接收序列距離(或其他量度最小的一種算法。由于它的譯碼器的復(fù)雜性隨m 值增大而線性增長,在實用中可以選用較大的m 值(如2040以保證更高的可靠性。許多深空和海事通信系統(tǒng)都采用序貫譯碼。Viterbi 譯碼流程及實現(xiàn)優(yōu)化回目錄 Viterbi 譯碼示例卷積碼的Viterbi 譯碼是根據(jù)接收碼字序列尋找編碼時通過網(wǎng)格圖最佳路徑的過程,找到最佳路徑即完成了譯碼過程,并可以糾正接收碼字中的錯誤比特。Viterbi 譯碼算法步驟如下描述:根據(jù)接收碼符號R ,計算出相應(yīng)的分支量度值BM( R/ Cj , j = 1 、2 ;進(jìn)入某一狀態(tài)的2 條分支量度BM ( R

12、/ Cj與其前狀態(tài)路徑量度PM累加求和;比較到達(dá)當(dāng)前狀態(tài)的2 條新的路徑量度PM 的大小,選擇最大者作為新的狀態(tài)路徑量度存儲起來,并保存與此路徑對應(yīng)的碼字;對所有的256 個狀態(tài)都實施上述加、比、選(ACS 運(yùn)算;在每一譯碼時刻,滿足延時就從256 條留存路徑中,選擇路徑量度最大的一條路徑作為譯碼數(shù)據(jù)輸出; 進(jìn)入下一譯碼時刻,重復(fù)以上步驟,直至譯碼結(jié)束。由于卷積碼譯碼的復(fù)雜度隨著約束長度的增加以非線性方式迅速增加,在實際應(yīng)用中,卷積碼的實際應(yīng)用性能往往受限于存儲器容量和系統(tǒng)運(yùn)算速度,尤其是對約束長度比較大的卷積碼。為了在有限的硬件或軟件資源條件下保證系統(tǒng)較高的譯碼性能,下面對算法進(jìn)行優(yōu)化。 1

13、. 留存路徑更新算法優(yōu)化傳統(tǒng)的實現(xiàn)留存路徑存儲器(SMU 更新的算法,有寄存器交換法RE 和回溯法TB ,其詳細(xì)內(nèi)容請參考有關(guān)文獻(xiàn)。寄存器交換法利用數(shù)據(jù)在寄存器中不斷交換,來更新留存路徑,實現(xiàn)信息的譯碼,相對于TB 法不斷讀寫存儲數(shù)據(jù)和需要延時回溯判決,其優(yōu)點是存儲單元少、譯碼延時短。RE 方法的缺點是內(nèi)聯(lián)關(guān)系過于復(fù)雜,不適合約束長度比較大的卷積碼譯碼器的FPGA 實現(xiàn)?；赗E 提出了對留存路徑存儲及輸出優(yōu)化的實現(xiàn)方法,具體描述如下:.逐狀態(tài)分配256 個存儲器單元,單元位數(shù)由延時D (譯碼深度 決定,每單元存儲一個碼字;每一個狀態(tài)當(dāng)前留存路徑存儲器的值由選定的前一狀態(tài)存儲器值和路徑對應(yīng)的碼

14、字決定(見上述Viterbi 譯碼算法步驟描述 ;每一個譯碼時刻只向存儲單元中存人留存路徑的碼字,并把選定碼字寫入存儲單元中最低位;當(dāng)譯碼時刻大于延時D 時,判決出當(dāng)前時刻的所有狀態(tài)中具有最大路徑量度的狀態(tài),并將其對應(yīng)的留存路徑存儲單元中的最高位作為譯碼結(jié)果輸出;在實現(xiàn)存儲單元的移位時,可采用循環(huán)移位的方式,避免重復(fù)讀寫,在軟件實現(xiàn)時如果采用指針的方式讀寫地址,也可以做到只用一套存儲器,這樣就能繼續(xù)在節(jié)省空間和提高運(yùn)算速度上更進(jìn)一步,在Matlab 仿真中由于系統(tǒng)本身的特點,只須用簡單的命令完成以上操作。由于留存路徑存儲器中存入的只是路徑信息,因而節(jié)省了存儲空間;當(dāng)譯碼輸出時,只讀出具有最大路徑量度的狀態(tài)所對應(yīng)的留存路徑存儲單元最高位即可,不須向前回溯,減少了讀RAM 的次數(shù)(由D次減少至1 次 提高了譯碼速度。 2. 優(yōu)化判決輸出在輸出時需要做延時判