2.6 卷積碼

2.6.1 卷積碼的概念與網(wǎng)格圖表示

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

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

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

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

和

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

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

其中“*”表示卷積運(yùn)算。

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

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

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

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

描述卷積碼的方法有很多，除了上面從生成矩陣方面描述，也可以從卷積碼的多項(xiàng)式、狀態(tài)圖和網(wǎng)格圖等方面描述。

（1）卷積碼的多項(xiàng)式表示：在線性系統(tǒng)中，卷積的時(shí)域運(yùn)算可以以一種更方便的形式表示，即多項(xiàng)式乘法的變換域運(yùn)算。編碼輸出的每個(gè)序列可以用多項(xiàng)式表示，相應(yīng)的編碼方程為

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

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

其中信息序列為

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

編碼序列為

碼的生成多項(xiàng)式為

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

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

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

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

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

考慮一個(gè)卷積編碼的數(shù)字通信系統(tǒng)，如圖2.10所示。

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

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

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

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

對(duì)于無記憶信道，有

在對(duì)數(shù)域上，用對(duì)數(shù)似然函數(shù)表示為

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

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

因此，對(duì)于軟判決譯碼器，網(wǎng)格圖上的狀態(tài)轉(zhuǎn)移分支度量定義為

對(duì)于硬判決譯碼器，網(wǎng)格分支度量定義為

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

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

（1）對(duì)狀態(tài)轉(zhuǎn)移Sk-1→Sk，計(jì)算該轉(zhuǎn)移分支的度量M(rk|ck)，并與k-1時(shí)刻的幸存路徑度量Γ(Sk-1)相加，得到k時(shí)刻的一個(gè)候選路徑度量。

（2）對(duì)k時(shí)刻的每一個(gè)狀態(tài)，比較到達(dá)該狀態(tài)的候選路徑度量，選擇最小距離（或最大似然）度量所對(duì)應(yīng)的路徑作為幸存路徑，并存儲(chǔ)它的轉(zhuǎn)移路徑歷史（從時(shí)刻k=1開始）及其度量Γ(Sk)。

在最后時(shí)刻(L+m)，有一個(gè)唯一狀態(tài)，它的幸存路徑一定是結(jié)尾網(wǎng)格圖上的最短路徑。

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

2.6.3 卷積碼的逐符號(hào)MAP譯碼：BCJR算法

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

在本節(jié)中，我們經(jīng)常使用貝葉斯（Bayes）規(guī)則，它簡(jiǎn)述為

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

貝葉斯規(guī)則的一個(gè)直接結(jié)果是

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

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

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

由N個(gè)符號(hào)對(duì)組成，其中

式中，Es為每發(fā)送符號(hào)的平均能量；和為信道衰落因子，對(duì)于AWGN信道，；對(duì)于Rayleigh衰落信道，和為兩個(gè)Reyleigh隨機(jī)變量。和為兩個(gè)獨(dú)立同分布的高斯噪聲樣值，它們的均值為0，方差。

根據(jù)逐比特最大后驗(yàn)概率準(zhǔn)則，譯碼器輸出由下式得到：

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

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

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

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

下面利用BCJR算法對(duì)式(2.44)的計(jì)算方法進(jìn)行推導(dǎo)。

假定卷積編碼器有m個(gè)記憶單元（存儲(chǔ)級(jí)數(shù)為m），約束長(zhǎng)度ν=m+1。令Sk=(ak, ak-1, · · ·, ak-m+1)是k時(shí)刻編碼器的狀態(tài)。編碼器的狀態(tài)集合用S表示，狀態(tài)數(shù)為M=|S|=2m。

在網(wǎng)格圖上第k時(shí)刻的狀態(tài)轉(zhuǎn)移分支可以表示為bk?(Sk-1, uk, ck, Sk)，其中uk和ck分別是對(duì)應(yīng)狀態(tài)轉(zhuǎn)移Sk-1→ Sk的信息符號(hào)和編碼符號(hào)。連接狀態(tài)Sk-1=s′∈S和Sk=s∈S的所有平行分支組成的集合記為Bk(s′, s)。根據(jù)貝葉斯準(zhǔn)則，后驗(yàn)概率可以表示為

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

概率中的序列y可寫為

其中，表示接收序列y在t到?時(shí)刻內(nèi)的子序列。

應(yīng)用貝葉斯準(zhǔn)則，對(duì)進(jìn)行分解，可得

其中

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

② 是后向狀態(tài)度量。

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

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

定義

為從Sk-1=s′到Sk=s的狀態(tài)轉(zhuǎn)移概率。如果在網(wǎng)格圖中存在從Sk-1=s′到Sk=s的平行轉(zhuǎn)移分支，則γk(s′, s)的數(shù)值為所有對(duì)應(yīng)平行分支度量的總和。將式(2.48)代入式(2.46)，得到

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

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

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

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

分支度量可進(jìn)一步分解為

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

其中Ak是獨(dú)立于編碼比特的常數(shù)。如前所述，令

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

因此

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

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

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

因?yàn)?img alt="" class="h-pic" src="https://epubservercos.yuewen.com/B97B47/16992237205825406/epubprivate/OEBPS/Images/figure_0082_0006.png?sign=1753662696-W15MT8AgxHYOaeCMEXG3nbOyDJjnaTb7-0-fa84fd0dae159bba4bc1195e54bbd8d9">，所以

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

對(duì)于，考慮到，于是有

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

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

這樣就完成了分量碼的MAP譯碼算法的推導(dǎo)。和的遞推運(yùn)算示意圖如圖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編碼器的初始狀態(tài)為零狀態(tài)）

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

否則，應(yīng)設(shè)定為

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

MAP算法可歸結(jié)如下。

（1）初始化：

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

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

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

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

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

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

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

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

2.6.4 Max-Log-MAP譯碼算法

1．對(duì)數(shù)域上的簡(jiǎn)化運(yùn)算

如果譯碼器運(yùn)行在對(duì)數(shù)域上，則上述最大后驗(yàn)概率（MAP）算法中涉及的計(jì)算將會(huì)得到簡(jiǎn)化。定義

如果x＞y，可將其寫為

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

考慮一般情況，有

其中，fc(|x-y|)=ln(1+e-|x-y|)是一個(gè)修正函數(shù)。實(shí)際應(yīng)用時(shí)，可以通過查表實(shí)現(xiàn)。

這可以推廣到多個(gè)變量的情況。例如，對(duì)于一個(gè)實(shí)數(shù)集合{δ1, δ2, · · ·, δq}，有

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

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

2．Max-Log-MAP算法

Max-Log-MAP算法是基于前文所述MAP算法的次優(yōu)簡(jiǎn)化算法，旨在誤碼率和譯碼計(jì)算復(fù)雜度上取得有效的折中。

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

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

這里

以及

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

或者

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

等效地

顯然，該前后向狀態(tài)度量可以通過遞歸計(jì)算得到，初始條件為

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

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

類似地，式(2.63)的最終對(duì)數(shù)后驗(yàn)概率比可以近似為

這意味著通過執(zhí)行“加―比（較）―選（擇）―減”操作便可實(shí)現(xiàn)譯碼功能。

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