Turbo 譯碼SOVA 算法的研究與實現(xiàn)*

王丹飛，宋俊慷，夏慧寧

（1.北京航天馭星科技有限公司，河南 鄭州 450018；2.廣西民族師范學(xué)院，廣西 崇左 532200）

0 引言

低軌道通常指150 km～300 km 高度的軌道，相較于中高軌道具有空間鏈路損耗和時延小的特點。低軌道衛(wèi)星通常是小衛(wèi)星，依靠數(shù)量眾多的小衛(wèi)星可以很容易組成衛(wèi)星星座[1]，更適合軍事偵察、遙感應(yīng)用和實現(xiàn)個人衛(wèi)星通信等。

小衛(wèi)星重量輕[2]、結(jié)構(gòu)小，便于發(fā)射制造的同時對星載設(shè)備的集成化和數(shù)據(jù)可靠性傳輸又是一個挑戰(zhàn)。為此，CCSDS 空間數(shù)據(jù)鏈路業(yè)務(wù)標(biāo)準(zhǔn)規(guī)定了包括卷積碼、Turbo 碼在內(nèi)的一系列信道碼標(biāo)準(zhǔn)，用于近地和深空通信。Turbo 碼是以卷積碼為基礎(chǔ)的并行級聯(lián)碼[3-4]，在低信噪比條件下展現(xiàn)出優(yōu)越的譯碼性能，幾乎接近于香農(nóng)理論極限，因而廣泛應(yīng)用于衛(wèi)星通信中。

1 Turbo 碼網(wǎng)格圖

網(wǎng)格圖既可以用來說明編碼過程，也可以用來分析譯碼過程。當(dāng)Turbo 碼編碼器的結(jié)構(gòu)固定，網(wǎng)格圖也固定。CCSDS 標(biāo)準(zhǔn)推薦的Turbo 編碼器如圖1 所示，其分量編碼器的移位寄存器個數(shù)為4，因此是24=16 狀態(tài)（S0～S15）的Turbo 編碼器，再結(jié)合其反饋位置，得到網(wǎng)格圖如圖2 所示。

網(wǎng)格圖的橫軸是時間軸，縱軸是狀態(tài)值；網(wǎng)格圖既可以反映從當(dāng)前時刻某一狀態(tài)出發(fā)，輸入為0 或1 時，下一時刻的到達(dá)狀態(tài)和下一時刻的輸出；也可以反映從前一時刻的某一狀態(tài)出發(fā)，輸入為0 或1 時，當(dāng)前時刻能夠到達(dá)的狀態(tài)以及到達(dá)當(dāng)前時刻（的分支路徑上）的輸出。

編碼時，每輸入1 個比特的信息位mk，得到一個輸出碼字，共6 個比特，因此CCSDS Turbo碼的基本碼率是1/6，經(jīng)過打孔刪余可由基本碼率得到其他碼率。其中分量編碼器1 輸出3 個校驗位，同時分量編碼器2 輸出2 個校驗位，mk為未編碼位。對于特定的編碼輸入序列，由網(wǎng)格圖可以得到固定的編碼路徑，對應(yīng)唯一的編碼輸出序列。

圖3 是網(wǎng)格圖的圖表表示法，也是MATLAB 中trellis 函數(shù)的輸出，使用圖表表示方法更易于軟件實現(xiàn)。圖表法和圖2 的網(wǎng)格圖是一致的，例如，當(dāng)前時刻從狀態(tài)S5 出發(fā)，當(dāng)編碼輸入為0（或1），則下一時刻的到達(dá)狀態(tài)為next_state(0)=S10（或next_state(0)=S2），且對應(yīng)狀態(tài)轉(zhuǎn)移路徑上的輸出為 next_out(0:3)=0011(或next_out(4:7)=1100);再比如，前一時刻從狀態(tài)S5 出發(fā)，當(dāng)輸入為0 時，當(dāng)前時刻到達(dá)的狀態(tài)為S10 且轉(zhuǎn)移路徑上的輸出last_out(0:3)=0011，即虛線狀態(tài)轉(zhuǎn)移路徑上0/0111。

圖3 網(wǎng)格圖的圖表表示法

對于16 狀態(tài)網(wǎng)格圖在t=4 時刻之后達(dá)到全狀態(tài)，到達(dá)全狀態(tài)后，（對于二進制編碼）進入每個狀態(tài)的路徑有且僅有兩條，從每個狀態(tài)出發(fā)的路徑也是有且僅有兩條。

值得注意的是，圖2 狀態(tài)轉(zhuǎn)移路徑上的輸出“/xxxx”對應(yīng)，因此Turbo 碼網(wǎng)格圖也可以看作是分量編碼器的網(wǎng)格圖。但是由于Turbo 碼的分量編碼器是遞歸的卷積編碼器，存在著反饋輸入，因此網(wǎng)格圖的狀態(tài)路徑轉(zhuǎn)移路線與非遞歸卷積碼有所不同。

2 Turbo 碼通用譯碼器結(jié)構(gòu)

Turbo 碼通用的譯碼器結(jié)構(gòu)——軟輸入軟輸出迭代譯碼結(jié)構(gòu)(Soft Input Soft Output,SISO)如圖4 所示，主要由串并變換、（兩個）分量譯碼器、交織/解交織器和硬判決輸出組成。

圖4 通用的Turbo 碼迭代譯碼結(jié)構(gòu)圖

假定譯碼器的接收序列Y為：

式中，k=0,1,…,N-1，是過信道后的編碼信息位，分別對應(yīng)兩個分量編碼器輸出的過信道后的校驗序列。

經(jīng)過幾輪迭代譯碼后，交換的先驗信息值不再有大的變化，則對分量譯碼器2 輸出的外信息Λ2e(u)經(jīng)解交織后對符號位進行硬判決輸出，即為最終的譯碼輸出。

3 SOVA 譯碼實現(xiàn)

Turbo 編碼器中的分量編碼器是一個遞歸卷積編碼器，而卷積編碼的典型譯碼算法(也是最優(yōu)譯碼方法)是Viterbi 譯碼（等價于最大似然譯碼）。人們自然想到，是否能用Viterbi 譯碼的方法來實現(xiàn)對Turbo 碼的譯碼，答案是可以的，即軟輸出Viterbi 算法(Soft Output Viterbi Algorithm,SOVA)。

SOVA 基于圖4 結(jié)構(gòu)實現(xiàn)Turbo 迭代譯碼。其分量譯碼器的實現(xiàn)原理及過程和Viterbi 譯碼相比，主要有三個不同點：

(1) 使用修正的度量；

(2) 多了一個可靠性值更新的過程；

(3) 分量譯碼器的譯碼輸出不再是（二進制0，1 比特序列的）硬判決輸出，而是估計比特的外信息值Λ1e(u)(或Λ2e(u))。

3.1 SOVA 度量

SOVA 分量譯碼器使用修正的Viterbi 度量（也稱SOVA 度量），即：

式中，Mt是當(dāng)前時刻t的累積度量值，Mt-1是前一時刻的累積度量值；表示當(dāng)前時刻的分支度量值，ct,j是網(wǎng)格圖狀態(tài)轉(zhuǎn)移路徑上的輸出，yt,j是過信道后對應(yīng)位的解調(diào)軟輸出值（有符號數(shù)），分支度量值是轉(zhuǎn)移分支路徑上編碼碼字和接收碼字的點乘，計算的是歐氏距離，不再是漢明距離，這是因為解調(diào)軟輸出值是有符號數(shù)，而非0 或1 值。

分支度量值和先驗信息可以看作是SOVA 度量的加權(quán)值[6-7]，二者共同為t時刻對信息位比特的估計提供判決度量。其中分支度量值反映了信道條件的好壞，當(dāng)信道條件非常好時，應(yīng)當(dāng)主要以分支度量值為判決度量；當(dāng)信道條件很差時，應(yīng)當(dāng)主要以先驗信息值為判決度量；也就是說，二者的權(quán)重是相對的，而非相同。這就解釋了圖4 分量譯碼器輸出的外信息Λ1e(u)為什么需要與自身兩個輸入（先驗信息Λ1a(u)和系統(tǒng)信息序列YS）相加減，目的為了是保持兩個權(quán)重的相對獨立性，以兼顧不同信道條件的譯碼。

使用SOVA 度量進行“加比選”計算如圖5 所示，得到最大似然路徑（圖6 實線）和最大似然路徑上的估計比特（圖6 與實線相連的比特值，其他比特值為不同時刻下的不同狀態(tài)值所對應(yīng)的幸存路徑上的估計比特值）。由于每個時刻下到達(dá)不同狀態(tài)的路徑有且僅有兩條，且這兩條路徑互為幸存路徑和競爭路徑，而最大似然路徑是不同時刻下SOVA 度量值最大的幸存路徑的連線，因此最大似然路徑一定是幸存路徑，而幸存路徑不一定是最大似然路徑。

圖5 “加比選”單元

圖6 最大似然路徑（實線）和最大似然路徑上的估計比特值（橫軸為時間軸，縱軸為狀態(tài)值）

3.2 可靠性值更新過程

3.2.1 可靠性值的定義

可靠性值Lt定義為“當(dāng)前時刻競爭路徑上和幸存路徑上的累積度量值之差的絕對值”。

式中，i=0.1…15，si表示狀態(tài)值。

圖7 網(wǎng)格圖中競爭路徑與幸存路徑對比示意圖

通常來說幸存路徑累積度量總是優(yōu)于競爭路徑的累積度量，那么這個差值越大，幸存路徑是最大似然路徑的可能性就越大，輸出判決也越可靠。因此，可將最大似然路徑上的可靠性值作為先驗信息輔助另一個分量譯碼器進行譯碼判決，即相當(dāng)于MAP 類算法中的外部信息。

3.2.2 進行可靠性值更新的原因

SOVA 分量譯碼器進行可靠性值更新的原因是人們發(fā)現(xiàn)這樣一種情況，如圖7 在t=1 到t=6 這一時間段內(nèi)，幸存路徑（實線）與競爭路徑（虛線）先是在t=1 時刻的狀態(tài)節(jié)點S8 處開始分離，又在t=6 時刻的狀態(tài)節(jié)點S5 處重新匯合。又知最大似然路徑上t=2、t=5 和t=6 時刻的可靠性值分別是{10,25,0}，對于Viterbi 譯碼在t=6 時刻會因為幸存路徑和競爭路徑的累積度量值相同而任意選擇其中一條作為幸存路徑，這樣至少在t-4、t-2 和t這三個時刻的估計比特就存在著50%的誤判概率（但整體估計序列仍然是最大似然序列即序列最優(yōu)）。而Turbo 碼兩個分量譯碼器之間存在著迭代，如果沒有可靠值更新，迭代譯碼反而會放大這種錯誤，惡化譯碼性能。

3.2.3 可靠性值更新的策略和方法

由于信息和信道傳輸?shù)碾S機性，顯然無法避免圖7情況的出現(xiàn)，但是可以對其進行改善。分析如下：如果沒有可靠性值更新，當(dāng)前分量譯碼器會告訴下一個分量譯碼器t=2、t=5、t=6 時刻估計比特{0,0,1}的可信度值分別為{0,25,0}；在可靠性值更新后，當(dāng)前分量譯碼器會告訴下一個分量譯碼器在t=2、t=5、t=6 時刻估計比特{0,0,1}的可信度值分別為{0,0,0}，也就是說對t=2、t=5 時刻的可靠性值進行了更新改善，從而降低不可靠性值在迭代過程中惡性傳播的風(fēng)險。基于這樣的思路，本文給出一種工程中使用的滑窗回溯進行可靠性值更新的方法。

(1) 滑窗大小

為了兼顧譯碼時延和譯碼性能，工程上一般設(shè)置滑窗最大長度w=30，對于每個信息位，滑窗長度均是從1逐漸增大到30，滑窗的起始位置及滑窗大小變化過程如圖8 所示。圖中，{S0,S8,S4,S10,S5,S10,S13,……,S13,S14,S15,S7,S13,S6,S3,S1,S0,S0}為（某次某分量譯碼器輸出的）最大似然路徑。

圖8 滑窗起始位置及大小變化圖示

(2) 回溯

以圖6 分量譯碼器“加比選”單元計算得到的最大似然路徑為例，回溯過程如圖9 所示。

圖9 針對第一個信息位不同滑窗長度的可靠性值更新示意圖

對于第一個信息位，第一次回溯時滑窗長度w=1時，從t=2 時刻的狀態(tài)S4 處開始回溯如圖9(a)所示：首先，根據(jù)圖6 可知t=2 時刻到達(dá)狀態(tài)S4 的最大似然路徑上的估計比特值為0，那么與之相應(yīng)的競爭路徑上的估計比特值一定是1，這是因為到達(dá)某狀態(tài)的分支路徑有且僅有兩條。再根據(jù)圖3 網(wǎng)格圖表，可知輸入為1 且當(dāng)前時刻到達(dá)狀態(tài)S4 的前一狀態(tài)為S9，這一過程簡記為=1，表示t=2 時刻到達(dá)狀態(tài)S4 的競爭路徑上的估計比特值為1。接著從t=1 時刻的狀態(tài)S9向前回溯，根據(jù)圖6“加比選”計算結(jié)果可知t=1 時刻到達(dá)狀態(tài)S9 處的估計比特為1，再根據(jù)圖3 網(wǎng)格圖表，可得到輸入為1 且t=1 時刻到達(dá)狀態(tài)S9 的前一狀態(tài)為S3，記為=1，這樣就回溯得到連續(xù)的一條競爭路徑如圖9(a)虛線所示。

其次，比較t=1 時刻最大似然路徑上的估計比特值=1 和競爭路徑上的估計比特值=1 是否相同，相同則不更新可靠性值。

同樣的，增大滑窗長度w=2，從t=3 時刻的狀態(tài)S10 處開始回溯，回溯到t=1 時刻，并比較最大似然路徑上的估計比特值=1 和競爭路徑上的估計比特值=1 是否相同，相同則不更新。

當(dāng)滑窗長度w=3 時，從t=4 時刻的狀態(tài)S5 處開始回溯，比較=1 和=1 是否相同，相同則不更新。

當(dāng)滑窗長度w=4 時，從t=5 時刻的狀態(tài)S10 處開始回溯，比較=1 和=0 是否相同，不相同則更新。更新方法：比較t=1 時刻的可靠性值和t=5 時刻的可靠性值，選擇最小值賦值給t=1 時刻的可靠性值實現(xiàn)更新。

當(dāng)滑窗長度w=5 時，從t=6 狀態(tài)S5 處開始回溯，比較=1 和=1 是否相同，由于重合一定相同則不更新。

以此類推，逐步增大滑窗長度并回溯比較，從而實現(xiàn)對第一個信息位的可靠性值更新。

同理，對于第二個信息位，則從t=2 時刻開始逐次增大滑窗長度，并比較最大似然路徑上的估計值=0 和競爭路徑上的估計值是否相同，不相同則更新可靠性值（每次都取最小值）；

依次循環(huán)對最大似然路徑上每個信息位進行可靠性值更新后，將更新后的可靠性值與估計比特值（0 和1分別映射為-1 和1）相乘后作為分量譯碼器的軟信息輸出。

3.3 判決輸出和SOVA 分量譯碼器實現(xiàn)流程圖

根據(jù)迭代準(zhǔn)測（如設(shè)置固定的迭代次數(shù)），將分量譯碼器2 輸出的軟信息的符號位進行硬判決輸出即可。SOVA 分量譯碼器實現(xiàn)流程圖如圖10所示。

圖10 SOVA 分量譯碼器實現(xiàn)流程圖

4 仿真及設(shè)備驗證

SOVA 譯碼仿真參數(shù)設(shè)置如下：幀長8 160 bit，1/3碼率，CCSDS 交織方式，迭代3 次，滑窗長度w的最大值為30，仿真結(jié)果如圖11 所示，可以看出SOVA 與MAP 類算法性能相比僅有1 dB 的損失。

圖11 SOVA 算法與MAP 類算法（log-map 算法、max-log 算法）誤碼率性能對比

5 結(jié)論

本文以CCSDS 標(biāo)準(zhǔn)推薦的Turbo 碼為例，對SOVA譯碼的原理及實現(xiàn)進行了介紹，重點研究了網(wǎng)格圖的功能及在其譯碼過程中的應(yīng)用；同時詳細(xì)分析了可靠性更新過程，闡明了SOVA 譯碼與Viterbi 譯碼的區(qū)別和聯(lián)系，并給出了工程中一種實際的用法，最后對SOVA 譯碼進行了仿真驗證，并成功應(yīng)用于某數(shù)傳設(shè)備，經(jīng)過實際測試，該方式在不增加設(shè)備復(fù)雜度的同時獲得良好的信道編碼增益，實現(xiàn)簡單方便維護。