2.6 卷積碼

2.6.1 卷積碼的概念與網格圖表示

卷積碼的編碼器是有記憶的，在一定的時間內，編碼器的輸出不僅取決于該時刻的輸入，也與一定數量以前的輸入相關。考慮一個碼率為R=k/n的卷積編碼器。在卷積編碼中，信息序列u被劃分為長度為k的數據幀，在每一個時刻，一個k比特長的數據幀被作為信息序列送入卷積編碼器，相應的輸出是n比特的編碼序列，k和n通常是比較小的整數并且k ＜n。每n-比特的編碼輸出塊不僅依賴于當前時刻的k-比特輸入序列，也依賴于m個以前輸入的k-比特序列。參數m稱為存儲級數，ν=m+1稱為卷積碼的約束長度。該卷積碼通常記為(n, k, ν)或(n, k, m)卷積碼。

圖2.7給出了一個存儲級數m=2、碼率R=1/2的卷積碼編碼器。這個編碼器有k=1路輸入，n=2路輸出，稱為(2,1,2)卷積碼。由于模2和是線性運算，因此編碼器是線性系統。它由下面兩個生成序列所定義

g(1)=(101), g(2)=(111)

根據圖2.7所示，信息序列表示為u=(u0, u1, · · ·)。編碼器的兩個輸出序列表示為

和

由于編碼器可以看作線性系統，輸出序列可以由輸入序列和編碼器的兩個沖擊響應卷積得到，并且g(1)、g(2)就是編碼器的兩個沖激響應，由u=δ=(100 · · ·)得到。沖激響應至多持續m+1個時間單位，且可寫為

g(1)、g(2)被稱為編碼器的生成序列，它描述了編碼器中移位寄存器的連接關系。令u=(u0, u1, · · ·)是編碼器輸入信息序列，則兩個編碼輸出序列為

其中“*”表示卷積運算。

在t時刻，輸入是單個比特ut，相應的輸出是兩比特組成的一個碼組（block）(, )，其中

輸出碼字是。例如，對于輸入u=(1011100 · · ·)，碼字c=(11,01,00,10,01,10,11, · · ·)。

將生成序列交織，重新排列可得到如下時域生成矩陣。

編碼方程可以重寫成矩陣的形式：c=uG。

描述卷積碼的方法有很多，除了上面從生成矩陣方面描述，也可以從卷積碼的多項式、狀態圖和網格圖等方面描述。

（1）卷積碼的多項式表示：在線性系統中，卷積的時域運算可以以一種更方便的形式表示，即多項式乘法的變換域運算。編碼輸出的每個序列可以用多項式表示，相應的編碼方程為

c(1)(D)=u(D)g(1)(D)

c(2)(D)=u(D)g(2)(D)

其中信息序列為

u(D)=u0+u1D+u2D2· · ·

編碼序列為

碼的生成多項式為

對于圖2.7所示的卷積碼，生成矩陣表示為

（2）狀態圖：因為編碼器是一個線性時序電路，所以可以用狀態轉移圖來描述其行為。我們用t時刻記憶單元中存儲的消息比特來表示t時刻的編碼器狀態。上述例子中(2,1,2)卷積編碼器有兩個記憶單元，因此共有4種可能的狀態，其狀態轉移圖如圖2.8所示。圖中的狀態被定義為編碼器電路中兩個記憶單元的值（從左至右讀取），邊上的標記為“輸入/輸出”。

（3）網格圖：將狀態圖在時間軸上展開，就會清晰看到卷積編碼器隨時間的狀態轉移，這個在時間上擴展開的狀態圖就稱為網格圖（trellis diagram）。具體在圖示中，網格圖是在水平方向上加上離散時間維度的狀態圖。上述(2,1,2)卷積碼的網格圖如圖2.9所示。

編碼器從00狀態開始，在t≥2時的網格，本質上是狀態圖的復制?？梢钥吹骄W格圖給出了所有可能的編碼路徑，消息序列u的編碼等價于在網格圖上追蹤一條路徑。網格圖是描述卷積碼編碼器的一種重要方法，它對于描述卷積碼的譯碼算法也是非常方便的。

2.6.2 卷積碼的最大似然譯碼：Viterbi算法

考慮一個卷積編碼的數字通信系統，如圖2.10所示。

假定使用(n0, k0, m)卷積碼C, m為編碼器的存儲單元個數（存儲級數）。輸入信息序列長度為L段（K=k0L個比特）:。

編完信息比特并添加尾比特后，輸出碼字c的長度為N=n0(L+m)比特：c=(c1, c2, · · ·, cL+m), 。在網格圖上，每個碼字是從全0狀態出發經過不同分支，最后回到全0狀態的一條網格路徑，稱為編碼路徑。作為一個例子，圖2.11所示卷積編碼器的網格圖及編碼路徑如圖2.12所示。

假定經過編碼信道傳輸，與發送碼字c對應的接收序列是r=(r1, r2, · · ·, rL+m)。對于BSC信道，。對于AWGN信道，假定采用BPSK調制，每一編碼符號被映射為發送信號，接收信號，其中是獨立同分布的高斯噪聲序列。這樣，軟判決譯碼器的輸入序列r=x+n，其中x=M(c)=(-1)c。

ML譯碼器選擇使P(r|c)最大的c作為譯碼輸出：

對于無記憶信道，有

在對數域上，用對數似然函數表示為

令M(rk|ck)=log P(rk|ck)表示分支度量。一條網格路徑的前t個分支的累積度量（或稱為部分路徑度量）定義為

對于AWGN信道（或BSC），最大似然度量P(r|c)等價于最小Euclidean距離度量||r-M(c)||2（或Hamming距離度量dH(r, c)）。因此，AWGN信道下的最佳譯碼準則簡化為

因此，對于軟判決譯碼器，網格圖上的狀態轉移分支度量定義為

對于硬判決譯碼器，網格分支度量定義為

Viterbi譯碼算法在網格圖上通過遞歸處理方式尋找最大似然路徑。它首先計算k時刻的接收信號rk與進入狀態Sk的所有網格分支之間的Hamming（或Euclidean）距離，并將它作為分支度量；然后計算進入狀態Sk的所有網格路徑的度量并進行比較，存儲有最佳度量的那條網格路徑及其度量，剪掉其余的（不可能成為ML選擇的那些）網格路徑。譯碼器對k時刻的所有狀態進行這種選擇。這樣，在時刻k，對每一狀態Sk，確定了一條從時刻0的全0狀態出發而到達Sk的最佳路徑，稱為幸存路徑。如圖2.13所示，其中Γ(Sk=s)表示k時刻到達狀態Sk=s的幸存路徑的累積度量（或稱為狀態度量）。

具體地說，k時刻的幸存者按照下列“加―比（較）―選（擇）”運算從k-1時刻的幸存者中確定。

（1）對狀態轉移Sk-1→Sk，計算該轉移分支的度量M(rk|ck)，并與k-1時刻的幸存路徑度量Γ(Sk-1)相加，得到k時刻的一個候選路徑度量。

（2）對k時刻的每一個狀態，比較到達該狀態的候選路徑度量，選擇最小距離（或最大似然）度量所對應的路徑作為幸存路徑，并存儲它的轉移路徑歷史（從時刻k=1開始）及其度量Γ(Sk)。

在最后時刻(L+m)，有一個唯一狀態，它的幸存路徑一定是結尾網格圖上的最短路徑。

例2.3 考慮圖2.11中的(2,1,2)卷積碼。發送序列為c=(11,01,01,00,10,11)，接收序列為r=(11,11,00,00,10,11)。Viterbi譯碼器選擇幸存路徑的過程如圖2.14 ～圖2.17所示，圖中狀態轉移分支邊上的標號為Hamming距離，狀態度量Γi等于該狀態的幸存路徑累積度量。

2.6.3 卷積碼的逐符號MAP譯碼：BCJR算法

1974年，Bahl、Cocke、Jelinek和Raviv提出了一種最大后驗概率（MAP）算法[28]，用于估計噪聲中一個Markov源的狀態轉移的后驗概率，這個算法后來就被稱為BCJR算法。論文中也展示了該算法如何用來譯分組碼和卷積碼。用于譯卷積碼時，BCJR算法能夠最小化誤比特率，即BCJR算法在最小化BER意義下是最佳的；而Viterbi算法是最小化碼字錯誤概率（在網格圖上譯碼器選擇不正確路徑的概率）。另外，BCJR算法不僅能提供比特序列估計值，而且能夠給出每個比特被正確譯碼的概率，這也是Turbo迭代譯碼的基礎。因此，BCJR算法經常用于需要軟信息輸出的譯碼器/檢測器，如Turbo譯碼器和Turbo均衡器等。

在本節中，我們經常使用貝葉斯（Bayes）規則，它簡述為

P(u, v)=P(u|v)P(v)

貝葉斯規則的一個直接結果是

P(u, v|w)=P(u|v, w)P(v|w)

下面具體介紹卷積碼的逐符號MAP譯碼算法?？紤]圖2.18所示的系統模型。令u=(u1, u2, · · ·, uK), uk∈{0,1}，是輸入信息序列，它用碼率為1/2的（系統或非系統）卷積編碼器進行編碼，生成編碼符號序列c=(c1, c2, · · ·, cN)，其中,1≤k≤N。這里N表示網格圖長度，如果沒有結尾（termination）處理，則有N=K。然后編碼符號和用BPSK調制，得到在信道上傳輸的發送符號xs和xp。

對于圖2.18所示的信道模型，接收序列

由N個符號對組成，其中

式中，Es為每發送符號的平均能量；和為信道衰落因子，對于AWGN信道，；對于Rayleigh衰落信道，和為兩個Reyleigh隨機變量。和為兩個獨立同分布的高斯噪聲樣值，它們的均值為0，方差。

根據逐比特最大后驗概率準則，譯碼器輸出由下式得到：

這里P(uk|y)是信息比特uk在接收到序列y的情況下的后驗概率。

BCJR算法就是工作在網格圖上的一種高效MAP算法。為后面使用算法方便起見，考慮圖2.19所示的軟輸入軟輸出（SISO）MAP譯碼器，它能為每一個譯碼比特提供對數似然比輸出。

圖2.19中MAP譯碼器的輸入La(uk)是關于uk的先驗信息，L(uk)是關于uk的對數后驗概率（APP）比。它們的定義為

MAP譯碼器的任務就是求解式(2.44)，然后按照下列規則進行判決。

下面利用BCJR算法對式(2.44)的計算方法進行推導。

假定卷積編碼器有m個記憶單元（存儲級數為m），約束長度ν=m+1。令Sk=(ak, ak-1, · · ·, ak-m+1)是k時刻編碼器的狀態。編碼器的狀態集合用S表示，狀態數為M=|S|=2m。

在網格圖上第k時刻的狀態轉移分支可以表示為bk?(Sk-1, uk, ck, Sk)，其中uk和ck分別是對應狀態轉移Sk-1→ Sk的信息符號和編碼符號。連接狀態Sk-1=s′∈S和Sk=s∈S的所有平行分支組成的集合記為Bk(s′, s)。根據貝葉斯準則，后驗概率可以表示為

其中，是由輸入uk=i引起的狀態轉移Sk-1→Sk的集合。故式(2.44)可表示為

概率中的序列y可寫為

其中，表示接收序列y在t到?時刻內的子序列。

應用貝葉斯準則，對進行分解，可得

其中

① 稱為前向狀態度量，由k時刻譯碼器狀態Sk=s和接收序列共同決定。

② 是后向狀態度量。

③ 是輸入為uk=i時連接狀態Sk-1=s′到Sk=s的分支度量。

式(2.47)遵循譯碼器的Markov性，即如果已知Sk=s，則時刻k之后發生的事件獨立于到達Sk之前的序列。

定義

為從Sk-1=s′到Sk=s的狀態轉移概率。如果在網格圖中存在從Sk-1=s′到Sk=s的平行轉移分支，則γk(s′, s)的數值為所有對應平行分支度量的總和。將式(2.48)代入式(2.46)，得到

下面來求αk(s)、βk(s)和γk(s′, s)。根據定義，αk(s)項可通過遞歸計算。

其中初始值為α0(s)=P(S0=s)。

類似地，βk(s)可以通過如下的后向遞歸計算。

邊界條件為βN(s)=P(SN=s)。

分支度量可進一步分解為

其中，P(uk=i)是uk的先驗概率，P(Sk=s|Sk-1=s′, uk=i)是在輸入為uk=i的條件下，狀態轉移Sk-1→ Sk發生的概率，該數值為1或0。p(yk|ck) ?p(yk|Sk=s, Sk-1=s′, uk=i)是在給定特定分支的情況下，接收到yk的概率，由信道轉移概率確定。對于無記憶AWGN信道，可由下式計算得到

其中Ak是獨立于編碼比特的常數。如前所述，令

為信道的可靠性度量。則式(2.54)可寫為

因此

至此，如果將式(2.50)分子、分母中的約掉，L(uk)的求解已基本完成。然而，由于式(2.56)是從連續隨機變量的概率密度計算得到，γk(s′, s)的值可能大于1，這會使得式(2.51)、式(2.52)產生上溢出，導致整個算法不穩定。另外，由于下列原因，也可能導致下溢出：隨著k的增加，某些狀態度量的數值將小到幾乎可以忽略不計，這將由于精確性的限制造成錯誤。考慮如下的求和算式時，該現象就顯而易見。

接收到特定序列的概率，將隨著時刻k的增加而變得非常小。

因此，有必要對αk(s)和βk(s)進行歸一化處理。令

因為，所以

將式(2.51)代入式(2.60)，并且分子分母同除以，得到

對于，考慮到，于是有

合并式(2.48)和式(2.59)得

將上式代入式(2.46)，并且分子分母同乘以因子，便得最終計算公式為

這樣就完成了分量碼的MAP譯碼算法的推導。和的遞推運算示意圖如圖2.21所示，其中αk(0)=αk-1(0)γk(0,0)+αk-1(1)γk(1,0), βk(0)=βk+1(0)γk+1(0,0)+βk+1(2)γk+1(0,2)。的初始條件為（假定RSC編碼器的初始狀態為零狀態）

如果編碼器在每幀編碼完成之后通過結尾（termination）處理也回到零狀態，那么遞推的初始條件為

否則，應設定為

注意：MAP算法也通常被稱為BCJR算法或前后向遞歸算法，與隱馬爾可夫模型（hidden Markov models）中的Baum-Welch算法等價。

MAP算法可歸結如下。

（1）初始化：

α0(0)=1, α0(?s=0)=0；

βN(0)=1, βN(?s=0)=0。

（2）前向遞歸：對于k=1到N，做如下操作。

①對i=0、1，參照式(2.57)計算并存儲分支度量。

②對s∈S，參照式(2.61)計算并存儲前向度量αk(s)。

（3）后向遞歸：對于k=N-1到0，做如下操作。

參照式(2.62)，使用前向遞歸中計算得到的分支度量值，計算并存儲后向度量βk(s), ?s∈S。

（4）輸出：對于k=1到K，參照式(2.63)計算并輸出軟信息L(uk)。

2.6.4 Max-Log-MAP譯碼算法

1．對數域上的簡化運算

如果譯碼器運行在對數域上，則上述最大后驗概率（MAP）算法中涉及的計算將會得到簡化。定義

如果x＞y，可將其寫為

max*(x, y)=ln[ex(1+ey-x)]=x+ln(1+ey-x)

考慮一般情況，有

其中，fc(|x-y|)=ln(1+e-|x-y|)是一個修正函數。實際應用時，可以通過查表實現。

這可以推廣到多個變量的情況。例如，對于一個實數集合{δ1, δ2, · · ·, δq}，有

這表明ln(eδ1+eδ2+· · ·+eδq)可以通過遞歸計算得到，記為

max*(δ1, δ2, · · ·, δq)=max*(max*((max*(max*(δ1, δ2), δ3), · · ·), δq-1), δq)

2．Max-Log-MAP算法

Max-Log-MAP算法是基于前文所述MAP算法的次優簡化算法，旨在誤碼率和譯碼計算復雜度上取得有效的折中。

Max-Log-MAP算法使用了以下的Max-Log近似。

在該近似下，有下面的推導。對于式(2.61)，可得

這里

以及

由此，式(2.61)的前向遞歸在對數域可以表示為

或者

類似地，式(2.62)后向狀態度量可以表示為

等效地

顯然，該前后向狀態度量可以通過遞歸計算得到，初始條件為

A0(0)=0, A0(s)=-∞, ?s=0

BN(0)=0, BN(s)=-∞, ?s=0

類似地，式(2.63)的最終對數后驗概率比可以近似為

這意味著通過執行“加―比（較）―選（擇）―減”操作便可實現譯碼功能。

從上述討論可以看出，Max-Log-MAP算法與雙向Viterbi算法等價。如果將max函數用max*代替，就可得到Log-MAP算法。