一種基于消息傳遞的時域重疊復用譯碼算法*

胡峰華，王亞峰，金 婧

（1.北京郵電大學，北京 100876；2.中國移動研究院，北京 100032）

0 引言

隨著移動通信業務的迅速發展，無線頻譜資源越發的短缺[1]，這極大程度上限制了未來移動通信技術的發展。因此，如何實現高頻譜效率和提高信號的傳輸速率，是未來移動通信技術研究的重要方向。李道本教授通過多年的理論研究，提出了一種高頻譜效率的編碼方式，稱為重疊X 域復用編碼[2-4]，它包含時域重疊復用（Overlapped Time Division Multiplexing，OvTDM）、頻域重疊復用（Overlapped Frequency Division Multiplexing，OvFDM）以及碼域重疊復用（Overlapped Code Division Multiplexing，OvCDM）。盡管這種編碼方式很大程度上提升了系統的傳輸速率，但是由于引入了符號間的干擾，因此這種編碼方式在譯碼時運算復雜度很高，很難應用于實際。目前OvTDM 系統常用的譯碼算法有維特比算法[5]、Fano 算法[6]、stack 算法[7]等。其中，維特比算法具有最佳的譯碼性能，但是譯碼復雜度隨重疊復用系數的增大呈指數增加，在高重疊復用系數的情況下是難以接受的；Fano 算法和stack 算法雖然在運算復雜度方面相比于維特比算法有所降低，但是它們的譯碼性能相比維特比算法有著很大的差距。在這樣的背景下，如果能研究出一種低運算復雜度高性能的OvTDM 系統譯碼算法，就能推動OvTDM 編碼方式在實際生產中的應用。因此本文研究了OvTDM 系統的卷積編碼方式，發現該系統在發送序列和接收信號之間存在特殊的對應關系，以此為基礎能構建出關聯程度很大的因子圖結構。在此基礎上，本文將消息傳遞的思路應用到OvTDM 系統的譯碼過程中提出了一種新型的OvTDM 系統譯碼算法[8-11]，在實現低運算復雜度的同時有著較好的譯碼性能。

1 系統模型

相比于無符號間干擾的正交奈奎斯特系統，OvTDM 系統中存在波形的重疊，人為引入了符號間干擾，而重疊復用原理指出這種干擾是一種編碼約束關系，波形重疊得越嚴重，系統獲得的增益反而越高。OvTDM 系統本質上是復用波形在時域上的移位疊加，圖1 給出了OvTDM信號的編碼過程。

圖1 重疊復用系數為3的OvTDM 系統信號編碼過程

如圖1 所示為一個重疊復用系數為3的OvTDM系統信號的編碼過程，可以看出OvTDM信號的產生是通過時域復用波形的移位和疊加所產生的。這里g(t)代表周期為T的時域復用波形，K表示重疊復用系數，則每次移位的間隔為T/K。從圖1 中不難看出相鄰的K個符號之間是存在干擾的，這種干擾是人為引入的，但是這種干擾與信道噪聲不同，它是符號之間的一種編碼約束關系。當重疊復用系數越大時，波形重疊得越緊密，系統單位時間攜帶的符號信息也越多，OvTDM 系統以此來實現高編碼增益。雖然這種方式實現了高編碼增益，但是因為人為引入了符號間干擾，接收端信號的譯碼過程變得更加的困難，極大地增加了運算復雜度。

圖2 給出了加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道環境下OvTDM 系統從信號產生到接收端譯碼的總流程。

圖2 AWGN信道下OvTDM 系統流程

如圖2 所示，假定發送序列是等概率發送的無記憶信源，待發送的0、1 序列經過串并變換和調制后映射為調制序列x。調制序列進入OvTDM 成型濾波器后，經過復用波形的移位與疊加之后產生了OvTDM信號，該信號經過AWGN信道進行信號的傳輸。信號到達接收端后，與傳統的傳輸系統不同，它無需進行匹配濾波，而是直接進行采樣和譯碼，最終得到譯碼輸出的序列，這就是OvTDM信號從產生到譯碼的總過程。這里假設長度為N的待發送的調制符號序列為x，設定OvTDM 系統采用的復用波形為g(t)(t∈[0,T])，g(t)表示周期為T且能量歸一化的脈沖成型波形?；鶐vTDM信號s(t)可以表示為：

式中：xn表示第n個待發送的調制符號。

基帶信號經過AWGN信道之后到達接收端，獲得的接收端信號為：

式中：n(t)表示信道噪聲。

然后接收信號y(t)不經過匹配濾波器，直接進行采樣和譯碼，得到譯碼序列，至此流程結束。

2 算法原理

如果一個多變量的全局函數可以分解成多個局部函數乘積的形式，則可以使用因子圖來描述變量與局部函數之間的關系。消息傳遞往往是在因子圖模型的基礎上進行的，用來表征因子圖上各個節點之間消息進行傳遞更新的過程。在OvTDM 系統的接收端，每T/K周期內的接收信號都與多個發送符號有關。由于OvTDM 系統的卷積編碼結構引入了數據符號間的干擾，OvTDM 系統在接收信號和發送符號之間能構建易于進行信息傳遞的因子圖模型。在這樣的情況下，本文將消息傳遞的思想應用于OvTDM系統的譯碼過程中，提出了一種基于消息傳遞的OvTDM 譯碼算法。算法的原理步驟如下文所述。

假設調制序列為：

式中：(x-K+2,x-K+3,…,x0)為序列頭部；(xN+1,…,xN+K-1)為序列尾部；(x1,x2,…,xN)為實際發送的符號。序列頭部和序列尾部兩部分為已知序列，(x1,x2,…,xN)為待檢測序列。式（3）中N為發送符號數目，K為重疊復用系數，本論文采用二進制相移鍵控（Binary Phase Shift Keying，BPSK）調制。

假設OvTDM 系統的復用波形為：

式中：gi(t)(i=1,2,…,K)為第i個子復用波形。

設定g=(g1,g2,…,gK)是子復用波形在對應周期內的采樣值。

這里假設接收序列為：

式中：yl(l=1,2,…,N+K-1)為接收信號在第周期內的采樣值。

根據OvTDM 系統的卷積編碼方式可知：

式中：nl為接收端噪聲信號在第周期內的采樣值。

進一步推導可以得出：

根據式（7）中發送符號和接收序列的關系，本文提出了一種基于消息傳遞的OvTDM譯碼算法，算法流程如下：

步驟一：式（7）取i=l有：

若xl的前K-1 個發送符號的估計值已知，則根據式（8）可以求出xl的估計值，即(xl-K+1,xl-K+2,…,xl-1)已知，則可以估計xl，又(x-K+2,x-K+3,…,x0)為已知符號序列。因此，根據已知的符號序列可以估計x1的值，這里記x1的估計值為E(x1)。由于本文采用BPSK 調制，則利用：

將式（9）、式（10）歸一化得到：

取l=1，則可以求出x1的估計值：

計算出x1的估計值E(x1)后，這就可以作為已知條件進一步求出x2的估計值，以此類推直到求出xN的估計值E(xN)，最后將本步驟求出的所有估計值作為初始估計序列傳入后續的步驟。

步驟二：本文以發送符號為變量節點，以接收序列為函數節點，依據OvTDM 系統的卷積編碼結構構建了OvTDM 系統的因子圖模型。重疊復用系數為3的OvTDM 系統因子圖模型如圖3 所示。

圖3 K=2 時OvTDM 系統的因子圖模型

若只看某個函數節點yl(l=1,2,…,N+K-1)，則該部分的因子圖模型如圖4 所示。

圖4 函數節點部分的因子圖模型

若只看x1到xN的某個變量節點xi(i=1,2,…,N)，則該部分的因子圖模型如圖5 所示。

圖5 變量節點部分的因子圖模型

根據消息傳遞的原理，每一個函數節點傳遞給與之相連的變量節點的信息其計算公式為：

式中：n(yl)為所有與yl相關聯的變量節點；z為除xi以外與yl相關聯的變量節點。這里假設μyl→xi(xi)=E'(xi|yl)。因為OvTDM 系統的相鄰符號之間存在干擾，所以系統接收端的噪聲信號之間是存在相關性的，本文為了簡便處理將接收端噪聲信號假定為均值為0，方差為σ2的高斯隨機變量。又因為發送序列是等概率的無記憶信源，所以調制序列x是獨立同分布的0 均值高斯隨機變量，基于此，本算法將式（7）中的部分進行高斯近似，這里假設近似后該部分為，則有：

由于采用的是高斯近似，所以的均值為：

的方差的計算方式為：

則xi是滿足均值為E(xi)，方差為D(xi)的高斯隨機變量，其中：

據此可以求出：

可以求出由yl傳遞給xi的信息為：

根據上述的計算方式，利用第一步中獲取的傳輸序列的初始估計值，可以按照從y1到yN+K-1的順序，計算每一個函數節點yl(l=1,2,…,N+K-1)向與之關聯的變量節點xi(i=l-K+1,l-K+2,…,l)所傳遞的信息。

步驟三：根據變量節點部分的因子圖結構，變量節點向與之關聯的函數節點傳遞的信息μxi→yl由除yl外所有與xi相連的函數節點傳遞過來的信息決定?；诖?，本文設定：

本步驟按照式（25）分別計算從x1到xN的變量節點向與之相關聯的所有函數節點傳遞的信息，這些信息將作為新的序列估計值用于下一次迭代過程中。步驟二和步驟三，整體上為一次迭代的過程，每次迭代重復上述的過程，直到達到預設的迭代次數。

步驟四：迭代結束后按照消息傳遞的原理可以計算xi(i=1,2,…,N)的最終估計值為：

最后按照上述估計值進行判決，得出判決序列作為譯碼結果，至此譯碼結束。

3 算法復雜度分析

本算法的運算復雜度，主要由以下4 個部分構成。

（1）步驟一的運算復雜度，這部分與迭代次數無關，在計算初始估計值的過程中，分別計算了每個發送序列符號的兩個狀態的概率，因此本部分的運算復雜度為O(2N)。

（2）步驟二的運算復雜度，這部分對于每一個函數節點都計算了該函數節點向與之關聯的發送符號傳遞的信息，每份信息都由對應發送符號的兩個狀態的概率組成。這部分與迭代次數有關，假設迭代次數為M，則運算復雜度為O(2NMK)。

（3）步驟三的運算復雜度，這部分對于每一個發送符號都計算了該符號向與之關聯的函數節點傳遞的信息，這部分也與迭代次數有關，所以本部分的運算復雜度為O(NMK)。

（4）步驟四的運算復雜度，這部分與迭代次數無關，運算復雜度為O(N)。

因此本算法的總運算復雜度為O(3NMK+3N)。

表1 給出了本算法和維特比算法、Fano 算法的譯碼復雜度對比。

表1 算法譯碼復雜度對比

如表1 所示，維特比算法的譯碼復雜度隨重疊復用系數的增大呈指數增加，因此在高重疊復用系數的條件下該算法的譯碼復雜度是難以接受的。而對于Fano 算法和本文所提的算法，它們的譯碼復雜度隨著重疊復用系數的增大都是呈現線性的關系，因此在高重疊復用系數的條件下能很好地降低譯碼復雜度。

4 仿真結果與分析

本文按照表2 所示的仿真參數分別對維特比算法、Fano 算法和本文提出的算法進行了譯碼仿真。

表2 仿真參數

經過多次仿真發現，隨著重疊復用系數的增加，本文提出的算法性能減少收斂所需的迭代次數。當K=2 時，本算法經過4 次迭代譯碼的性能基本就收斂了，所以在后面的仿真中本算法以4 次迭代為例進行仿真，仿真結果如圖6、圖7、圖8、圖9所示。

圖6 K=2 時3 種譯碼算法性能對比

圖7 K=3 時3 種譯碼算法性能對比

圖8 K=4 時3 種譯碼算法性能對比

圖9 K=5 時3 種譯碼算法性能對比

如圖6、圖7、圖8、圖9 所示，可以看出在重疊復用系數K=2,3的條件下，本文提出的算法具有良好的譯碼性能，其譯碼性能超過了Fano 算法，與維特比算法的性能接近。同時也可以發現，本算法在高信噪比的情況下其性能要好于Fano 算法，而在高重疊復用系數和低信噪比的條件下，本算法的性能不如Fano 算法。本文推測其原因是在該條件下由于噪聲干擾和疊加影響導致譯碼狀態數目多，本算法的譯碼檢測過程只能約束在長度為K的路徑內，而Fano 算法譯碼過程是在整個譯碼路徑中進行的。在高信噪比情況下，噪聲的干擾影響遠小于疊加影響，本算法在消息傳遞的過程中，由于噪聲干擾的減小，在計算發送序列估計值的時候能夠更加地接近實際的發送序列，使得本算法的譯碼性能優于Fano 算法。

5 結束語

本文針對OvTDM 系統的檢測問題提出了一種基于消息傳遞的OvTDM 系統的譯碼算法。在結合OvTDM信號的卷積編碼方式的基礎上，本算法構建了關聯發送符號和接收信號的因子圖模型，并在因子圖的變量節點和函數節點之間實現了消息的傳遞更新，最終經過迭代之后進行判決譯碼。仿真結果表明本文提出的算法與傳統的檢測算法相比能實現較好的譯碼性能，同時具有較低的運算復雜度。因此，本文提出的基于消息傳遞的OvTDM 系統譯碼算法在OvTDM 領域是很有應用前景的。

致 謝

本研究由北京郵電大學-中國移動研究院聯合創新中心資助，在此表示感謝。