卷積碼（電信技術）

卷積碼（電信技術）

卷積碼 （電信技術） 次瀏覽 | 2022.07.18 15:14:49 更新 來源 ：互聯網 精選百科 本文由作者推薦 卷積碼電信技術

卷積碼將k個信息比特編成n個比特，但k和n通常很小，特別適合以串行形式進行傳輸，時延小。與分組碼不同，卷積碼編碼后的n個碼元不僅與當前段的k個信息有關，還與前面的N-1段信息有關，編碼過程中互相關聯的碼元個數為nN。卷積碼的糾錯性能隨N的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優于分組碼。

中文名

卷積碼

外文名

convolutional code

所屬技術

電信技術

提出

1955年

概述一種卷積碼編碼器

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

同樣，在卷積碼譯碼過程中，不僅從此時刻收到的碼組中提取譯碼信息，而且還要利用以前或以后各時刻收到的碼組中提取有關信息。而且卷積碼的糾錯能力隨約束長度的增加而增強，差錯率則隨著約束長度增加而呈指數下降。卷積碼(n，k，m)主要用來糾隨機錯誤，它的碼元與前后碼元有一定的約束關系，編碼復雜度可用編碼約束長度m*n來表示。一般地，最小距離d表明了卷積碼在連續m段以內的距離特性，該碼可以在m個連續碼流內糾正(d-1)/2個錯誤。

卷積碼的糾錯能力不僅與約束長度有關，還與采用的譯碼方式有關。總之，由于n，k較小，且利用了各組之間的相關性，在同樣的碼率和設備的復雜性條件下，無論理論上還是實踐上都證明：卷積碼的性能至少不比分組碼差。

卷積碼是一種前向糾錯碼(Forward Correct Code)，通卷積碼是一種性能優越的信道編碼。它結構簡單、具有較強的糾錯能力和比較簡單的譯碼算法，在通訊、信息傳輸、存儲等方面獲得了十分廣泛的應用。若以(n，k，m)來描述卷積碼，其中k為每次輸入到卷積編碼器的bit數，n為每個k元組碼字對應的卷積碼輸出n元組碼字，m為編碼存儲度，也就是卷積編碼器的k元組的級數。卷積碼編碼后的n個碼元不僅與當前組的k個信息比特有關，而且與前N-1個輸入組的信息比特有關。編碼過程中相互關聯的碼元有N乘以n個。R/n是卷積碼的碼率，碼率和約束長度是衡量卷積碼的兩個重要參數。卷積碼的糾錯性能隨m的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優于分組碼。

編碼原理

以二元碼為例，編碼器如圖。輸入信息序列為

u

＝(

u

0

，

u

1

，…)，其多項式表示為

u

(

x

)＝

u

0

+

u

1

x

＋…＋

u

l

x

＋編碼器的連接可用多項式表示為

g

(

x

)＝1+

x

+

x

和

g

(

x

)＝1+

x

稱為碼的子生成多項式。它們的系數矢量

g

=(111)和

g

=(101)稱作碼的子生成元。以子生成多項式為陣元構成的多項式矩陣

G

(

x

)＝[

g

(

x

)，

g

(

x

)]，稱為碼的生成多項式矩陣。由生成元構成的半無限矩陣稱為碼的生成矩陣。其中(11，10，11)是由g和g交叉連接構成。編碼器輸出序列為c＝u·G，稱為碼序列，其多項式表示為c(x)，它可看作是兩個子碼序列c(x)和c(x)經過合路開關S合成的，其中c(x)＝u(x)g(x)和c(x)＝u(x)g(x)，它們分別是信息序列和相應子生成元的卷積，卷積碼由此得名。

在一般情況下，輸入信息序列經過一個時分開關被分成k0個子序列，分別以u

卷積碼

(x)表示，其中i=1，2，…k0，即u(x)＝[u

卷積碼

(x)，…，u

卷積碼

(x)]。編碼器的結構由k0×n0階生成多項式矩陣給定。輸出碼序列由n0個子序列組成，即c(x)＝[c

卷積碼

(x)，c

卷積碼

(x)，…，c

卷積碼

(x)]，且c(x)=u(x)·G(x)。若m是所有子生成多項式g

卷積碼

(x)中最高次式的次數，稱這種碼為(n0，k0，m)卷積碼。

表示方法

描述卷積碼編碼器過程的方法有很多，如矩陣法、多項式、碼樹和網格圖等，這里我們主要介紹和卷積碼編碼器結構密切相關的多項式法，以及與卷積碼譯碼密切相關的網格圖法。

1.多項式法

多項式法就是由卷積碼的生成多項式直接得出其編碼器的結構圖。如前面例子中的(2，1，2)卷積碼的生成多項式矩陣為：G(D)=[1DD2，1D2]

其中，D是延遲算子，生成多項式的第一項為1DD2，表示輸出編碼的第一個碼元等于輸入碼元x（n）與前兩個時刻輸入的碼元x（n-1）、x（n-2）的模2和，同理第二項類似。

2.狀態圖

卷積碼狀態圖

將編碼器寄存器中的內容組合（x（n-1）、x（n-2））定義為編碼器狀態。如仍以前面所舉的例子(2，1，2)為例，則該編碼器的狀態有四種：00，10，01和11，下面分別用a，b，c，d來代替。編碼器在每一個時鐘沿打入一個輸入信息x（n），因此圖示寄存器組合內容就變為（x（n），x（n-1））即狀態發生了轉移，并同時輸出G0（n）、G1（n）。由此我們可以將圖所示編碼過程用右圖所示的狀態圖表示。

由圖所示，隨著信息序列不斷輸入，編碼器就不斷從一個狀態轉移到另一個狀態并同時輸出相應的碼序列，所以圖3所示狀態圖可以簡單直觀的描述編碼器的編碼過程。因此通過狀態圖很容易給出輸入信息序列的編碼結果，假定輸入序列為110100，首先從零狀態開始即圖示a狀態，由于輸入信息為“1”，所以下一狀態為b并輸出“11”，繼續輸入信息“1”，由圖知下一狀態為d、輸出“01”……其它輸入信息依次類推，按照狀態轉移路徑a->b->d->c->b->c->a輸出其對應的編碼結果“110101001011”。

3.網格圖

狀態圖可以完整的描述編碼器的工作過程，但是其只能顯示狀態轉移的過程而不能顯示狀態轉移發生的時刻，由此引出用來表示卷積碼的另一種常用方法——網格圖。網格圖就是時間與對應狀態的轉移圖（如圖），在網格圖中每一個點表示該時刻的狀態，狀態之間的連線表示狀態轉移。通過觀察網格圖可以發現在網格圖中輸入信息x（n）并沒有標出，但如觀察到轉移后的狀態表示（x（n），x（n-1））就可以發現輸入信息已經隱含在轉移后的狀態中。在圖中還可以發現兩個網格圖不同主要集中在轉移后狀態位置不同。重新排序結構（即所謂蝶型結構）是為了優化運算而設計的，因為其中蝶型與蝶型之間是相互獨立的。

網格圖

下面就讓我們來看看網格圖是如何描述卷積編碼過程的：仍以(2，1，2)為例，假定輸入序列為1011010100，起始狀態（零時刻）為狀態a（零狀態）。第一個有效時鐘沿來臨后，編碼器接收到輸入信息“1”，根據圖所示網格圖知該時刻（即時刻1）狀態為b，并輸出其對應的編碼結果“11”，同樣在下一個時刻（時刻2）接收到輸入信息“0”，狀態變為c并輸出“10”，接下來的輸入數據依次類推……，由此我們可以用網格圖作出該例子的卷積編碼過程，如圖5所示，其中兩個狀態連線之間的信息為輸出結果。

譯碼方法

若信道干擾序列為

卷積碼

，其中

卷積碼

。接收序列為

卷積碼

其中

卷積碼

和

卷積碼卷積碼

。這里“+”為模2運算(q=p

卷積碼

元碼按模p運算)。譯碼就是根據編碼規則和信道干擾的統計特性，對信息序列u(x)作出估值的方法。常用的有三類譯碼方法，即代數譯碼、維特比譯碼和序貫譯碼。

1.代數譯碼

代數譯碼是將卷積碼的一個編碼約束長度的碼段看作是[n0(m+1)，k0(m+1)]線性分組碼，每次根據(m+1)分支長接收數字，對相應的最早的那個分支上的信息數字進行估計，然后向前推進一個分支。上例中信息序列

卷積碼

＝(10111)，相應的碼序列c＝(11100001100111)。若接收序列R＝(10100001110111)，先根據R的前三個分支（101000）和碼樹中前三個分支長的所有可能的8條路徑(000000…)、(000011…)、(001110…)、(001101…)、(111011…)、(111000…)、(110101…)和(110110…)進行比較，可知(111001)與接收序列(101000)的距離最小，于是判定第0分支的信息數字為0。然后以R的第1～3分支數字(100001)按同樣方法判決，依此類推下去，最后得到信息序列的估值為

卷積碼

=(10111)，遂實現了糾錯。這種譯碼法，譯碼時采用的接收數字長度或譯碼約束長度為(m+1)n0，所以只能糾正不多于(dmin-1)/2個錯誤(n長上的)。實用中多采用反饋擇多邏輯譯碼法實現。

2.維特比譯碼

維特比譯碼過程

維特比譯碼是根據接收序列在碼的格圖上找出一條與接收序列距離（或其他量度）為最小的一種算法。它和運籌學中求最短路徑的算法相類似。若接收序列為

R

=(10100101100111)，譯碼器從某個狀態，例如從狀態

ɑ

出發，每次向右延伸一個分支（對于

l

＜

L

，從每個節點出發都有2

卷積碼

=2種可能的延伸，其中

L

是信息序列段數，對

l

≥

L

，只有一種可能），并與接收數字相應分支進行比較，計算它們之間的距離，然后將計算所得距離加到被延伸路徑的累積距離值中。對到達每個狀態的各條路徑（有2

卷積碼

=2條）的距離累積值進行比較，保留距離值最小的一條路徑，稱為幸存路徑（當有兩條以上取最小值時，可任取其中之一），譯碼過程如圖。圖中標出到達各級節點的幸存路徑的距離累積值。對給定

R的估值序列為=(10111)。這種算法所保留的路徑與接收序列之間的似然概率為最大，所以又稱為最大似然譯碼。這種譯碼的譯碼約束長度常為編碼約束長度的數倍，因而可以糾正不多于(df/2)個錯誤。

維特比譯碼器的復雜性隨m呈指數增大。實用中m不大于10。它在衛星和深空通信中有廣泛的應用。在解決碼間串擾和數據壓縮中也可應用。

3.序貫譯碼

序貫譯碼是根據接收序列和編碼規則，在整個碼樹中搜索（既可以前進，也可以后退）出一條與接收序列距離（或其他量度）最小的一種算法。由于它的譯碼器的復雜性隨m值增大而線性增長，在實用中可以選用較大的m值（如20～40）以保證更高的可靠性。許多深空和海事通信系統都采用序貫譯碼。

Viterbi譯碼流程及實現優化Viterbi譯碼示例

卷積碼的Viterbi譯碼是根據接收碼字序列尋找編碼時通過網格圖最佳路徑的過程，找到最佳路徑即完成了譯碼過程，并可以糾正接收碼字中的錯誤比特。Viterbi譯碼算法步驟如下描述：

①根據接收碼符號R，計算出相應的分支量度值BM(R/Cj)，j=1、2；

②進入某一狀態的2條分支量度BM(R/Cj)與其前狀態路徑量度PM累加求和；

③比較到達當前狀態的2條新的路徑量度PM的大小，選擇最大者作為新的狀態路徑量度存儲起來，并保存與此路徑對應的碼字；

④對所有的256個狀態都實施上述加、比、選(ACS)運算；

⑤在每一譯碼時刻，滿足延時就從256條留存路徑中，選擇路徑量度最大的一條路徑作為譯碼數據輸出；

⑥進入下一譯碼時刻，重復以上步驟，直至譯碼結束。

由于卷積碼譯碼的復雜度隨著約束長度的增加以非線性方式迅速增加，在實際應用中，卷積碼的實際應用性能往往受限于存儲器容量和系統運算速度，尤其是對約束長度比較大的卷積碼。為了在有限的硬件或軟件資源條件下保證系統較高的譯碼性能，下面對算法進行優化。

1.留存路徑更新算法優化

傳統的實現留存路徑存儲器(SMU)更新的算法，有寄存器交換法RE和回溯法TB，其詳細內容請參考有關文獻。寄存器交換法利用數據在寄存器中不斷交換，來更新留存路徑，實現信息的譯碼，相對于TB法不斷讀寫存儲數據和需要延時回溯判決，其優點是存儲單元少、譯碼延時短。RE方法的缺點是內聯關系過于復雜，不適合約束長度比較大的卷積碼譯碼器的FPGA實現?；赗E提出了對留存路徑存儲及輸出優化的實現方法，具體描述如下：.

①逐狀態分配256個存儲器單元，單元位數由延時D(譯碼深度)決定，每單元存儲一個碼字；

②每一個狀態當前留存路徑存儲器的值由選定的前一狀態存儲器值和路徑對應的碼字決定(見上述Viterbi譯碼算法步驟描述③)；

③每一個譯碼時刻只向存儲單元中存人留存路徑的碼字，并把選定碼字寫入存儲單元中最低位；

④當譯碼時刻大于延時D時，判決出當前時刻的所有狀態中具有最大路徑量度的狀態，并將其對應的留存路徑存儲單元中的最高位作為譯碼結果輸出；

⑤在實現存儲單元的移位時，可采用循環移位的方式，避免重復讀寫，在軟件實現時如果采用指針的方式讀寫地址，也可以做到只用一套存儲器，這樣就能繼續在節省空間和提高運算速度上更進一步，在Matlab仿真中由于系統本身的特點，只須用簡單的命令完成以上操作。

由于留存路徑存儲器中存入的只是路徑信息，因而節省了存儲空間；當譯碼輸出時，只讀出具有最大路徑量度的狀態所對應的留存路徑存儲單元最高位即可，不須向前回溯，減少了讀RAM的次數(由D次減少至1次)提高了譯碼速度。

2.優化判決輸出

在輸出時需要做延時判斷，以確定延時足夠再輸出正確數據。但每一時刻做延時的后果是增加了運算量，導致系統效率較低，根據仿真實現的特點，可以做以下修改：為了避免重復做延時判斷，節省運算量，譯碼輸出時省略這一判斷，每一時刻都有判決輸出碼字，只是在接收譯碼數據時把開始D時刻的接收碼字丟棄，相當于譯碼單元從D時刻開始輸出，這是一種把部分系統功能從復雜模塊轉移分離到相對簡單模塊的思想。相對于在譯碼過程不斷重復做判斷，這種做法無論在軟件或者硬件實現中，都能一定程度上提高運算速度。

參考資料