卷積碼

　　對資訊序列不分組的改錯碼，它的校驗元不僅與當前的資訊元有關，而且與以前有限時間段上的資訊元有關。1955年由P.伊萊亞斯提出，雖經多年努力，在編碼方法上還沒有找到象分組碼那樣有效的數學工具和系統的理論。不過，卷積碼在解碼方面，不論在理論上還是在實用上都超過瞭分組碼，因而在差錯控制和資料壓縮系統中得到廣泛應用。

　　編碼　以二元碼為例，編碼器如圖1。輸入信息序列為u＝(u₀，u₁，…)，其多項式表示為u(x)＝u₀+u₁x＋…＋u

x ＋…。編碼器的連接可用多項式表示為 ( x)＝1+ x+ x ²和 ( x)＝1+ x ²，稱為碼的子生成多項式。它們的系數矢量 =(111)和 =(101)稱作碼的子生成元。以子生成多項式為陣元構成的多項式矩陣 G( x)＝[ ( x) ( x)]稱為碼的生成多項式矩陣。由生成元構成的半無限矩陣

稱為碼的生成矩陣。其中(11，10，11)是由

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

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

( x)表示，其中 i=1，2，… k ₀，即 u( x)＝[ u ( x)，…， u ( x)]。編碼器的結構由 k ₀× n ₀階生成多項式矩陣

給定。輸出碼序列由n₀個子序列組成，即

　　c(x)＝[c

( x)， c ( x)，…， c ( x)]，且 c( x)= u( x)· G( x)。

　　若m是所有子生成多項式g

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

　　輸出子序列中的每個數字都與存儲在移位寄存器中的各輸入子序列的(m+1)位數字有關，總共與n

＝( m＋1) k ₀個信息數字有關， n 稱為編碼約束長度。

　　編碼器可看作是有限狀態線性網絡，移位寄存器中的存數可看作是狀態。如(2，1，2)碼有四個狀態：ɑ=00，b=01，c=10和d=11。可用有向圖表示輸出、輸入和狀態的關系(圖2)。要展示輸入和輸出的所有可能情況，可將狀態圖展示成樹圖(圖3)。圖中的粗體線表示輸入序列 u=(1011100…)時編碼器沿樹圖走過的路徑，相應的輸出序列c=(111000011001111)。在q無編碼時，每個節點的分支數為q

個。卷積碼各分支間具有線性關系，它是一般樹碼的一個子類。

　　若將樹圖中同一級節點上所有相同狀態的各分支合並，便構成圖4中的格圖。它能更簡潔地描述卷積碼，因此卷積碼又稱格碼。

　　用c_L表示碼樹中L分支長的路徑或碼段，d(c_L，c'_L)表示同段上兩個不同路徑c_L和c'_L之間的漢明距離。稱

為L長碼段上的最小距離；稱d_min(n_A)為碼的最小距離，以d_min表示，它和分組碼的最小距離相當。稱d_min(∞)為碼的自由距離，以d_f表示。一般d_f≥d_min，上例的d_f=5，d_min=3。自由距離在卷積碼的研究中有重要作用。但尚無系統的代數方法，在給定n₀、k₀和m下構造d_min和d_f盡可能大的碼，實用中常用計算機搜索。

　　分類　類似於分組碼，卷積碼可分為系統碼和非系統碼、糾正獨立錯誤和糾突發錯誤碼以及擇多邏輯可譯卷積碼。

　　譯碼　若信道幹擾序列為

，其中 。接收序列為 ，其中 和

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

　　代數譯碼是將卷積碼的一個編碼約束長度的碼段看作是[n₀(m+1)，k₀(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) n ₀，所以隻能糾正不多於( d _min-1)/2個錯誤( n 長上的)。實用中多采用反饋擇多邏輯譯碼法實現。

　　維特比譯碼是根據接收序列在碼的格圖上找出一條與接收序列距離（或其他量度）為最小的一種算法。它和運籌學中求最短路徑的算法相類似。若接收序列為R=(10100101100111)，譯碼器從某個狀態，例如從狀態ɑ出發，每次向右延伸一個分支（對於l＜L，從每個節點出發都有2

=2種可能的延伸，其中 L是信息序列段數，對 l≥ L，隻有一種可能），並與接收數字相應分支進行比較，計算它們之間的距離，然後將計算所得距離加到被延伸路徑的累積距離值中。對到達每個狀態的各條路徑（有 2 =2條）的距離累積值進行比較，保留距離值最小的一條路徑，稱為幸存路徑（當有兩條以上取最小值時，可任取其中之一），譯碼過程如圖5。圖中標出到達各級節點的幸存路徑的距離累積值。對給定 R的估值序列為 =(10111)。這種算法所保留的路徑與接收序列之間的似然概率為最大，所以又稱為最大似然譯碼。這種譯碼的譯碼約束長度常為編碼約束長度的數倍，因而可以糾正不多於( d _f/2)個錯誤。

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

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

　　

參考書目

　S.Lin and D.J.Costello， Error Control Coding:Fundamentals and Applications， Prentice Hall，Englewood Cliffs，New Jersey，1982.