卷積碼/Viterbi譯碼,卷積碼/Viterbi譯碼是什么意思

卷積碼在一個二進制分組碼（n,k）當中，包含k個信息位，碼組長度為n，每個碼組的（n-k）個校驗位僅與本碼組的k個信息位有關，而與其它碼組無關。為了達到一定的糾錯能力和編碼效率（＝k/n），分組碼的碼組長度n通常都比較大。編譯碼時必須把整個信息碼組存儲起來，由此產生的延時隨著n的增加而線性增加。

為了減少這個延遲，人們提出了各種解決方案，其中卷積碼就是一種較好的信道編碼方式。這種編碼方式同樣是把k個信息比特編成n個比特，但k和n通常很小，特別適宜于以串行形式傳輸信息，減小了編碼延時。

與分組碼不同，卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關，而且也與前面（N-1）段的信息有關，編碼過程中相互關聯的碼元為nN個。因此，這N時間內的碼元數目nN通常被稱為這種碼的約束長度。卷積碼的糾錯能力隨著N的增加而增大，在編碼器復雜程度相同的情況下，卷段積碼的性能優于分組碼。另一點不同的是：分組碼有嚴格的代數結構，但卷積碼至今尚未找到如此嚴密的數學手段，把糾錯性能與碼的結構十分有規律地聯系起來，目前大都采用計算機來搜索好碼。

下面通過一個例子來簡要說明卷積碼的編碼工作原理。正如前面已經指出的那樣，卷積碼編碼器在一段時間內輸出的n位碼，不僅與本段時間內的k位信息位有關，而且還與前面m段規定時間內的信息位有關，這里的m＝N-1通常用（n，k，m）表示卷積碼（注意：有些文獻中也用（n，k，N）來表示卷積碼）。圖1就是一個卷積碼的編碼器，該卷積碼的n = 2，k = 1，m = 2，因此，它的約束長度nN = n×(m+1) = 2×3 = 6。

圖1 （2，1，2）卷集碼編碼器

在圖1中，與 為移位寄存器，它們的起始狀態均為零。、與、、之間的關系如下：

?（1）

假如輸入的信息為D = [11010]，為了使信息D全部通過移位寄存器，還必須在信息位后面加3個零。表1列出了對信息D進行卷積編碼時的狀態。

表1 信息D進行卷積編碼時的狀態

輸入信息D 1 1 0 1 0 0 0 0?
b3b2 00 0 1 1 1 1 0 0 1 1 0 0 0 0 0?
輸出C1C2 1 1 0 1 0 1 0 0 1 0 1 1 0 0 0 0?

描述卷積碼的方法有兩類，也就是圖解表示和解析表示。解析表示較為抽象難懂，而用圖解表示法來描述卷積碼簡單明了。常用的圖解描述法包括樹狀圖、網格圖和狀態圖等?；谄蜻@里就不詳細介紹了。

卷積碼的譯碼方法可分為代數譯碼和概率譯碼兩大類。代數譯碼方法完全基于它的代數結構，也就是利用生成矩陣和監督矩陣來譯碼，在代數譯碼中最主要的方法就是大數邏輯譯碼。概率譯碼比較常用的有兩種，一種叫序列譯碼，另一種叫維特比譯碼法。雖然代數譯碼所要求的設備簡單，運算量小，但其譯碼性能（誤碼）要比概率譯碼方法差許多。因此，目前在數字通信的前向糾錯中廣泛使用的是概率譯碼方法。

維特比譯碼法簡介

viterbi譯碼算法是一種卷積碼的解碼算法。缺點是隨著約束長度的增加算法的復雜度增加很快。約束長度N為7時要比較的路徑就有64條，為8時路徑變為128條。 (2<<(N-1))。所以viterbi譯碼一般應用在約束長度小于10的場合中。

編碼（舉例約束長度為7）：編碼器7個延遲器的狀態（0，1）組成了整個編碼器的64個狀態。每個狀態在編碼器輸入0或1時，會跳轉到另一個之中。比如110100輸入1時，變成101001（其實就是移位寄存器）。并且輸出也是隨之而改變的。

解碼的過程就是逆過程。算法規定t時刻收到的數據都要進行64次比較，就是64個狀態每條路有兩條分支（因為輸入0或1），同時，跳傳到不同的兩個狀態中去，將兩條相應的輸出和實際接收到的輸出比較，量度值大的拋棄（也就是比較結果相差大的），留下來的就叫做幸存路徑，將幸存路徑加上上一時刻幸存路徑的量度然后保存，這樣64條幸存路徑就增加了一步。在譯碼結束的時候，從64條幸存路徑中選出一條量度最小的，反推出這條幸存路徑（叫做回溯），得出相應的譯碼輸出。

這樣的算法在TI的C54x的dsp上使用100M的速率運行，都無法達到數傳速度的要求，主要的時間消耗在每條路徑的兩次比較上，兩次比較的時候一共需要從內存中取3個數（上一時刻幸存路徑的量度，兩個狀態跳轉相應的輸出值），比較結束以后，還需要對內存寫入2個數（幸存路徑新的總量度，下一個跳轉的狀態），這樣，每個時鐘節拍需要比較的次數就是64*2次，每次存取數就要5次。一個數據包是256byte，知道解碼一包所大概需要的時間。加上其他的開銷，最后實驗出來的結果是大概0.06m，但是用64k速率傳輸的時候只要0.03m即可傳完。