摺積碼

卷積碼（英語：convolution code）是頻道編碼（channel coding）技術的一種，在電信領域中，屬於一種糾錯碼（error-correcting code）。相對於分組碼，卷積碼維持頻道的記憶效應（memory property）。卷積碼的由來，是因為輸入的原始訊息資料會和編碼器（encoder）的脈衝響應（impulse response）做卷積運算。卷積碼具有以下特性：

一段m字元的訊息(m字元的二進位元字串)會被編碼轉換成n字元的符號，m/n即是編位元速率(code rate，n ≥ m)

卷積碼的應用範圍[編輯]

　為了達成資料傳輸，卷積碼被廣泛使用在許多儀器或技術上，比如數碼視像、廣播、手機通訊、衛星通訊傳輸。資訊通常透過'硬性決策方式'（hard-decision code）來解碼，例如里德-所羅門碼。在渦輪碼（turbo codes）出現之前，這種架構可以算是非常高效率的編碼。

卷積碼編碼[編輯]

原始訊息資料依序由輸入端（input）進入編碼器的暫存器(register，圖內簡稱reg.)，每一個暫存器會儲存一個輸入字元，而它們的起始值都是0。依圖一而言，編碼器內有3個二模數加法器(modulo-2 adder，可等價於一個異或門（Boolean XOR gate），運算方式是0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0)對儲存的3位元原始資料，做各自的加法運算。接着，暫存器（register）內的字元會移往下一格，(reg1 moves to reg2, reg2 moves to reg3)；然後繼續將資訊傳至輸出端（output），如此便可以得到要傳輸的內容。

output1=reg.1+reg.3\,

output2=reg.1+reg.2+reg.3\,

運算後，輸出端（output）則輸出編碼後的卷積碼資料。

由於原始訊息資料是依序輸入至編碼器，所以3個暫存器（register）儲存的資料是不同時間點的輸入值；reg. 1 儲存目前訊息資料，reg. 2儲存前一週期的資料，reg. 3則是前前一週期的資料。因此，每筆卷積碼資料皆與過去的訊息資料有關係，因而保有記憶效應（memory property）。

G1 = (1,0,1), G2 = (1,1,1), 總輸出數量是2個，有3個暫存器（register）。

遞歸以及非遞歸編碼[編輯]

圖一是一個非遞歸編碼（non-recursive code）的類型，而圖二我們提供了一個遞歸編碼（recursive code）再處理的類型，其即將被進行編碼的輸入訊號同時也是輸出訊號(參見output 2)；此外，遞歸編碼幾乎都是系統性的（systematic），反之非遞歸編碼則是非系統性的（non-systematic）。

脈衝響應以及轉移函數[編輯]

卷積碼之所以得其名是因為其處理方法是將輸入端訊號以及編碼器中的脈衝響應進行摺積。

y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}

此處 $x$ 是輸入訊號， $y^{j}$ 是輸出訊號j，而 $h^{j}$ 則是輸出訊號j的脈衝響應。

卷積碼的編碼器是一個離散線性非時變系統，因此每個輸出端子的訊息都可以視為該編碼器的轉移函數；此外，脈衝響應可以透過Z轉換與轉移函數建立關聯性。

舉一個例子，圖三是一個非遞歸編碼器，它的轉移函數有三，如下：

$H_{1}(z)=1+z^{-1}+z^{-2},$
$H_{2}(z)=z^{-1}+z^{-2},$
$H_{3}(z)=1+z^{-2}.$

再者，圖二的編碼器轉移函數如下：

$H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},$
$H_{2}(z)=1.$

樹狀圖[編輯]

參見：Trellis modulation（英語：Trellis modulation）

樹狀圖（Trellis diagram）又稱籬笆圖，樹圖表。

卷積碼的編碼器（encoder）可以表示成有限狀態機(finite-state machine, FSM)，擁有 $n$ 組輸出端（output）的編碼器在FSM上會有 $2^{n}$ 個狀態（states）。

以圖三的非遞歸編碼器來說，假設現在 $m_{0}$ 存着'1'這一位元、'0'被存放在 $m_{-1}$ ( $m_{1}$ 不用列入考量因為它存放的是現在這個時刻的值)，那我們便定義現在位在"10"這個狀態。而在下一個時刻，新的輸入端訊號進入編碼器時可能產生'1'或者'0'，因此下一時刻編碼器可抵達的狀態是"01"或者"11"；整個樹狀圖如圖四所示，顯而易見的，並不是所有的狀態間都可以進行相連，比如"10"就不會連到"00"或者"10"這兩個狀態。

這個樹狀圖是卷積碼在解碼（decode）時的基礎，唯有能夠從頭連到尾的輸出端訊號（output sequences），才有可能是解碼出來的結果，否則便會產生錯誤。

卷積碼解碼[編輯]

現存有許多解碼卷積碼的方法。對於較小的輸出端組數，維特比演算法（Viterbi algorithm）是一種普遍被使用來解碼的演算法，其以最大似然估計（maximum likelihood）來尋找最有可能產生觀測事件序列的路徑。

參考資料[編輯]

This article incorporates public domain material （頁面存檔備份，存於互聯網檔案館） from the General Services Administration （頁面存檔備份，存於互聯網檔案館） document "Federal Standard 1037C"（頁面存檔備份，存於互聯網檔案館）