卷积码

维基百科,自由的百科全书
跳转至: 导航搜索

卷積碼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)出現之前,這種架構可以算是非常高效率的編碼。


卷積碼編碼(Encode)[编辑]

原始訊息資料依序由輸入端(input)進入編碼器的暫存器(register,圖內簡稱reg.),每一個暫存器會儲存一個輸入字元,而它們的起始值都是0。依圖一而言,編碼器內有3個'模數2加法器'(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),如此便可以得到要傳輸的內容。

output 1 = reg. 1 + reg. 3\,
output 2 = 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)。

圖二


脈衝響應以及轉移函數[编辑]

卷積碼之所以得其名是因為其處理方法是將輸入端(input)訊號以及編碼器(encoder)中的脈衝響應(impulse response)進行摺積(卷積、旋積,convolution)。

圖三

y^j_i = \sum_{k=0}^{\infty} h^j_k x_{i-k}

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

卷積碼的編碼器(encoder)是一個離散的(discrete)線性非時變系統(linear time-invariant system),因此每個輸出端子的訊息都可以視為該編碼器的轉移函數(transfer function);此外,脈衝響應可以透過Z轉換(Z-transform)與轉移函數建立關聯性。

舉一個例子,圖三是一個非遞迴(non-recursive)編碼器,它的轉移函數有三,如下:

  • H_1(z) = 1 + z^{-1} + z^{-2} ,
  • H_2(z) = z^{-1} + z^{-2} ,
  • H_3(z) = 1 + z^{-2} .

再者,圖二(recursive)的編碼器轉移函數如下:

  • H_1(z) = \frac{1 + z^{-1} + z^{-3}}{1 - z^{-1} - z^{-3}} ,
  • H_2(z) = 1 .


樹狀圖(Trellis diagram)[编辑]

參見: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"這兩個狀態。

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


卷積碼解碼(Decode)[编辑]

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


參考資料[编辑]