概述
卷積碼是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所示，其中兩個狀态連線之間的信息為輸出結果。
譯碼方法
若信道幹擾序列為n
，其中n
。接收序列為
其中n
和n
。這裡“+”為模2運算(q=p
元碼按模p運算)。譯碼就是根據編碼規則和信道幹擾的統計特性，對信息序列u(x)作出估值的方法。常用的有三類譯碼方法，即代數譯碼、維特比譯碼和序貫譯碼。
1.代數譯碼
代數譯碼是将卷積碼的一個編碼約束長度的碼段看作是[n0(m+1)，k0(m+1)]線性分組碼，每次根據(m+1)分支長接收數字，對相應的最早的那個分支上的信息數字進行估計，然後向前推進一個分支。上例中信息序列n
＝(10111)，相應的碼序列c＝(11100001100111)。若接收序列R＝(10100001110111)，先根據R的前三個分支（101000）和碼樹中前三個分支長的所有可能的8條路徑(000000…)、(000011…)、(001110…)、(001101…)、(111011…)、(111000…)、(110101…)和(110110…)進行比較，可知(111001)與接收序列(101000)的距離最小，于是判定第0分支的信息數字為0。然後以R的第1～3分支數字(100001)按同樣方法判決，依此類推下去，最後得到信息序列的估值為n
=(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譯碼算法步驟如下描述：
①根據接收碼符号R，計算出相應的分支量度值BM(R/Cj)，j=1、2；
②進入某一狀态的2條分支量度BM(R/Cj)與其前狀态路徑量度PM累加求和；
③比較到達當前狀态的2條新的路徑量度PM的大小，選擇最大者作為新的狀态路徑量度存儲起來，并保存與此路徑對應的碼字；
④對所有的256個狀态都實施上述加、比、選(ACS)運算；
⑤在每一譯碼時刻，滿足延時就從256條留存路徑中，選擇路徑量度最大的一條路徑作為譯碼數據輸出；
⑥進入下一譯碼時刻，重複以上步驟，直至譯碼結束。
由于卷積碼譯碼的複雜度随着約束長度的增加以非線性方式迅速增加，在實際應用中，卷積碼的實際應用性能往往受限于存儲器容量和系統運算速度，尤其是對約束長度比較大的卷積碼。為了在有限的硬件或軟件資源條件下保證系統較高的譯碼性能，下面對算法進行優化。
1.留存路徑更新算法優化
傳統的實現留存路徑存儲器(SMU)更新的算法，有寄存器交換法RE和回溯法TB，其詳細内容請參考有關文獻。寄存器交換法利用數據在寄存器中不斷交換，來更新留存路徑，實現信息的譯碼，相對于TB法不斷讀寫存儲數據和需要延時回溯判決，其優點是存儲單元少、譯碼延時短。RE方法的缺點是内聯關系過于複雜，不适合約束長度比較大的卷積碼譯碼器的FPGA實現。基于RE提出了對留存路徑存儲及輸出優化的實現方法，具體描述如下：.
①逐狀态分配256個存儲器單元，單元位數由延時D(譯碼深度)決定，每單元存儲一個碼字；
②每一個狀态當前留存路徑存儲器的值由選定的前一狀态存儲器值和路徑對應的碼字決定(見上述Viterbi譯碼算法步驟描述③)；
③每一個譯碼時刻隻向存儲單元中存人留存路徑的碼字，并把選定碼字寫入存儲單元中最低位；
④當譯碼時刻大于延時D時，判決出當前時刻的所有狀态中具有最大路徑量度的狀态，并将其對應的留存路徑存儲單元中的最高位作為譯碼結果輸出；
⑤在實現存儲單元的移位時，可采用循環移位的方式，避免重複讀寫，在軟件實現時如果采用指針的方式讀寫地址，也可以做到隻用一套存儲器，這樣就能繼續在節省空間和提高運算速度上更進一步，在Matlab仿真中由于系統本身的特點，隻須用簡單的命令完成以上操作。
由于留存路徑存儲器中存入的隻是路徑信息，因而節省了存儲空間；當譯碼輸出時，隻讀出具有最大路徑量度的狀态所對應的留存路徑存儲單元最高位即可，不須向前回溯，減少了讀RAM的次數(由D次減少至1次)提高了譯碼速度。
2.優化判決輸出
在輸出時需要做延時判斷，以确定延時足夠再輸出正确數據。但每一時刻做延時的後果是增加了運算量，導緻系統效率較低，根據仿真實現的特點，可以做以下修改：為了避免重複做延時判斷，節省運算量，譯碼輸出時省略這一判斷，每一時刻都有判決輸出碼字，隻是在接收譯碼數據時把開始D時刻的接收碼字丢棄，相當于譯碼單元從D時刻開始輸出，這是一種把部分系統功能從複雜模塊轉移分離到相對簡單模塊的思想。相對于在譯碼過程不斷重複做判斷，這種做法無論在軟件或者硬件實現中，都能一定程度上提高運算速度。
