基于變量節點串行策略的SCMA低復雜度譯碼研究

吉明明，鄭建宏

（重慶郵電大學通信與信息工程學院，重慶 400065）

基于變量節點串行策略的SCMA低復雜度譯碼研究

吉明明，鄭建宏

（重慶郵電大學通信與信息工程學院，重慶 400065）

稀疏碼多址接入（SCMA）技術作為5G無線通信網絡的一個競爭性的非正交多址方案，具有廣闊的應用前景。但目前基于SCMA的上行鏈路均采用泛洪方案的消息傳遞算法（MPA）進行譯碼，無論是檢測的復雜度還是收斂速度都不甚理想。提出一種改變信息更新策略的串行消息傳遞算法——S-MPA（serial MPA），按照變量節點的次序進行消息處理和傳遞，每一個變量節點同時進行校驗消息的接收和變量消息的發送。理論和仿真結果表明，該算法不僅能保持良好的性能，而且也有較低的解碼復雜度。

稀疏碼多址接入；多用戶檢測；變量節點；串行消息傳遞

1 引言

伴隨移動設備與物聯網的迅速發展，無線通信網絡的數據流也將成倍增長，5G移動通信需要有效地支持更加多樣化的設備。所以，5G網絡希望在業務和鏈接密度及高移動性等要求很高的場景中，能夠支持更多的數據業務類型，提供更高的數據速率和超低的時延、海量鏈接以及更好的服務質量（quality of service，QoS）、更高的頻譜效率（spectral efficiency，SE）或能量效率（energy efficiency，EE）等[1,2]。這必定給5G空中接口技術帶來很多新的挑戰，特別是多址接入領域，將遇到極大的挑戰。

在過去的十幾年中，很多學者已經對碼分多址接入（code division multiple access，CDMA）的非正交技術進行了深入的研究，近年來低密度信號（low density signature，LDS）作為一種特別的CDMA技術被提出，用以解決5G標準海量連接的情況。隨著LDS-CDMA多址技術發展，演變為性能更優的稀疏碼多址接入（sparse code multiple access，SCMA）[3-9]，在 SCMA系統中，QAM（quadrature amplitude modulation）映射和LDS聯合在一起，比特流直接映射到復數域的多維碼本的碼字，因此，LDS思想的提出可以更好地滿足5G大量的連接需求[6,9]。然而，為了使SCMA成為5G空中接口中有競爭力的候選非正交接入方法[10,11]，有兩個至關重要的問題，即設計優良的SCMA碼本和高效的譯碼算法。在參考文獻[9]中，提出了系統的碼書設計方法和評估方法。所以本文專注于高效的多用戶檢測的譯碼算法。

基于LDS思想，SCMA系統將每一個用戶的比特流映射到有限的子載波上，同時保證每一個資源塊上的疊加用戶數在一定范圍內，這為上行鏈路實現低復雜度譯碼算法提供了可能。參考文獻[12,13]針對SCMA擴頻矩陣設計稀疏性的特點，最先提出了一種上行 SCMA系統用戶檢測算法——MPA（message passing algorithm）[4,14]，MPA算法具有接近最大后驗概率的性能，但譯碼復雜度較高。參考文獻[15]提出了一種MPA的改進算法——PM-based MPA（partial marginalization based MPA），在保證譯碼性能的條件下，降低譯碼算法的復雜度。綜上所述，現有SCMA上行鏈路譯碼算法大都采用泛洪消息傳遞機制進行譯碼，即在每輪迭代過程中，首先所有的校驗節點進行消息更新，并把更新的消息傳回與之相連的變量節點，緊接著變量節點進行消息更新，并把更新的消息傳給與之相連的校驗節點，而對于碼字的判決只能等到每輪迭代完成之后才能進行，譯碼的效率并非最佳。

針對上述譯碼算法的不足，本文基于變量節點的串行策略提出了一種低復雜度的上行SCMA系統的多用戶算法，本文算法改變了傳統MPA的信息更新策略，可以把已更新的消息用于當前的迭代計算中。

2 系統模型

2.1 上行SCMA系統概述

SCMA是一種碼域的非正交多址接入技術。在SCMA系統中，調制和編碼是聯合在一起進行的，即SCMA編碼器將經過信道編碼的用戶比特根據用戶的碼本（CodeBook）直接映射對應復數域碼字（CodeWord），對于一個上行鏈路的SCMA通信系統，假定有J個用戶，K個正交時頻資源（J＞K），J個用戶稀疏擴頻到K個子載波，定義λ=J/K為其過載因子。例如，過載因子為1.5的6個用戶、4個正交資源塊的上行SCMA系統模型如圖1所示。

4資源塊代表4子載波，6路消息流擴展到這4個資源塊，經過信道編碼后的信息流經 SCMA編碼器，并擴展到多個正交資源上。這6條消息流可以屬于一個用戶或幾個用戶。為簡單起見，假設這6個消息屬于6個用戶。擴展疊加法是上面提到的非正交，在SC1資源塊，覆蓋UE1、UE3和UE5這3個用戶。這樣的疊加可使系統容納海量用戶。隨著資源塊數的增加，系統可以容納更多的數據流和更高的系統過載。例如，在8個資源塊中可能有24個用戶的數據流，可以達到300%過載。

SCMA編碼器將用戶比特根據用戶的碼本直接映射對應復數域碼字，即：

圖1 上行SCMA系統模型

其中，χ是具有稀疏性復數向量，代表一個K維碼字，且碼字中只含有L（L＜K）個非零元；M是輸入信號的種類，即碼本的尺寸。若用C來代表一個L維的星座點向量，則輸入信號比特到相應L維的星座點集C的關系可以由式（2）來確定：

SCMA編碼器的編碼函數可定義如下：

。例如，6個用戶、4個正交資源塊的上行SCMA系統模型因子圖和映射矩陣的關系如圖2所示。

為簡單起見，假定所有用戶的本地時間是同步的，則在SCMA上行鏈路終端收到的信號為所有用戶發送信號的疊加，具體如式（4）所示：

圖2 SCMA的因子圖與矩陣的關系

由于碼字是稀疏的，因此在時頻資源 k處有較少的碼字沖突。

2.2 原始MPA

消息傳遞算法是利用因子圖模型解決概率推理問題的有效方法，特別適合應用在低密度的因子圖中。由于SCMA傳播稀疏性，復雜性接收器可以被限制在較低的范圍內，以確保接收機使用消息傳遞算法（MPA）來檢測消息，MPA用多個相對簡單的迭代步驟來等效復雜的信號處理，各個步驟之間的運算以信息概率為基礎，使軟信息在因子圖上盡可能無損失地進行傳遞，每一輪迭代過程分解為如下兩個步驟。

步驟 1 更新所有校驗節點 ck到變量節點uj傳遞的概率消息

步驟 2 更新所有變量節點uj到校驗節點 ck傳遞的概率消息

第1次進行消息迭代更新時，因為沒有先驗的任何信息，因此所有信息均被等概率初始化為，其中M為碼本尺寸。

在因子圖中，變量節點可以通過如下規則進行更新：

其中，t表示迭代進行的次數，當迭代過程收斂或者達到預設的最大迭代次數后，每一個用戶發送碼字的的輸出概率即發送符號的后驗概率可以通過式（8）進行計算：

于是，發送信號的第 i個比特的軟判決信息可以表示為：

3 串行譯碼算法

傳統 MPA在每輪迭代中消息的更新處理都是并行的：首先校驗節點同時處理和傳送校驗消息，緊接著變量節點同時處理和傳送變量消息。在每次迭代中，無論是校驗節點信息還是變量節點的信息計算都是利用上一輪迭代更新的結果，即本輪更新的信息會延遲傳遞。對于實際工程應用，這樣的處理過程不僅會占用大量的硬件資源而且收斂性也并非最佳，為了加快MPA的收斂速度，本文將在同一次迭代更新中充分利用這些已更新的消息。

3.1 基于變量節點串行譯碼算法

針對上述譯碼算法的不足，本節提出一種基于變量節點串行消息傳遞的MPA，它能夠在譯碼性能和復雜度保持良好的平衡。本算法依照串行策略對變量節點更新信息，一次迭代過程如圖 3所示。該方法確保更新的消息在同一輪迭代中傳輸，提高了消息的收斂速度。

圖3 本文算法的一次迭代過程

根據式（7）與式（8），可得：

基于變量節點串行策略的 MPA低復雜度譯碼算法的詳細流程如下所示，這種串行策略按照變量節點的預定次序進行消息的更新和傳遞，確保已經更新的消息在本輪中馬上得到傳遞，不同于原始 MPA并行策略，更新的消息在下一輪迭代中才能傳輸。這樣的消息更新策略加快了消息的收斂速度，在較少迭代次數時，本文算法譯碼性能就能達到較好的效果。然而，由于串行更新策略，每次迭代所需的時間增加，將有一定程度的時延。

3.2 復雜度分析

SCMA多用戶檢測算法的復雜度主要花費在迭代過程信息更新與迭代次數上，為了統一比較算法效率，本文中所有算法的復雜度將以算法中所用到的乘法器的個數進行對比分析，見表1，其中 df代表作用在資源節點的用戶數目，dv代表作用在用戶節點的資源節點數量，m 與Rs代表PM-based MPA相關的參數。

表1 不同MPA所需乘法器數目

4 仿真結果與分析

為了驗證本文算法性能，對原始 MPA和PM-based MPA與本文算法在相同條件下進行了仿真比較，同時在信道中引入加性高斯白噪聲，仿真時SCMA系統的參數為K=4，J=6，M=4，

4.1 收斂速度

圖4顯示了本文算法S-MPA、原始MPA和PM-based MPA的BER性能與迭代次數的關系。由圖4可知，對于同一迭代次數，PM-based MPA的BER性能遠差于本文算法和原始MPA，并且本文算法S-MPA經過少數次的迭代，BER性能幾乎達到其譯碼的最佳水平。可見，基于變量節點的串行消息傳遞機制，使得節點消息的更新與傳遞結合起來，加快了譯碼的收斂速度，即使經過少數幾次迭代便能取得在并行策略下多次迭代才能達到的誤碼性能。迭代次數達到一定條件后，本文算法與原始MPA在BER性能上的差距越來越小，最終譯碼性能達到穩定，但在實際的應用中兼顧硬件資源開銷，使得這種以消息傳遞為基礎的譯碼的迭代次數不能取得很大，更能體現本文串行策略的優勢。

4.2 BER性能

圖5給出了本文算法S-MPA、原始MPA與PM-based MPA在不同信噪比條件下BER性能與迭代次數的關系曲線，可以看到，隨著信噪比的增大，BER性能有了明顯的改善。從圖 5可以得到，對于相同的迭代次數，本文算法的譯碼性能都優于原始MPA，在Eb/N0=10 dB時，2次迭代原始MPA的BER值為6.1× 10-3，而本文算法 2次迭代的 BER 值為2.4× 10-3。在BER=1.0× 10-3時，本文算法2次迭代的BER性能優于 6次迭代的 PM-based MPA，并且伴有0.65 dB的增益。

圖4 各種算法的收斂速度

圖5 各種算法的BER性能對比

4.3 復雜度對比

為分析算法效率，對幾種算法收斂時使用的乘法器的數目進行了比較，結合第 4.2節分析，在時本文算法S-MPA 2次迭代的性能和原始MPA和PM-based MPA6次迭代的性能幾乎等效，涉及的乘法器個數分別為 10 944、32 256、26 208。與原始MPA相比，本文算法節省了66.1%的乘法器。并且，相對于 PM-based MPA算法，不僅節約了58.3%的乘法器，而且在譯碼性能方面也有不錯的增益。因此，該算法可以提供一個良好的BER性能和復雜性之間的平衡。

為分析譯碼時間，對原始MPA與本文算法在相同條件下的譯碼時間進行了對比，如圖6所示，由于本文算法采用串行更新策略，每次迭代所需的時間增加，但相對于性能的提升，這點時延在接受范圍之內。

圖6 本文算法與原始MPA譯碼時間對比

5 結束語

本文基于上行SCMA通信鏈路系統，以因子圖中的變量節點消息串行更新為基礎，提出了一種加快譯碼收斂速度的多用戶檢測算法。相對于原始MPA與PM-based MPA，本文算法在不增加譯碼復雜度的基礎上，改善了譯碼的性能。因此，本文算法是一種具有很高的實用價值的SCMA多用戶檢測算法。本文對MPA信號檢測技術的研究只局限于信道條件已知的高斯信道以及終端處于靜止狀態的情況，但在實際應用場景中，多變的信道環境和運動的終端都會對系統性能產生較大的影響。因此，針對不同應用場景和不同狀態的終端，研究切合實際的SCMA技術解決方案，將是非常有價值的研究方向。

[1] BHUSHAN N, LI J, MALLADI D, et al. Network densification: the dominant theme for wireless evolution into 5G[J]. IEEE Communications Magazine, 2014, 52(2): 82-89.

[2] ROWELL C, HAN S. Toward green and soft: a 5G perspective[J]. IEEE Communications Magazine, 2014, 52(2): 66-73.

[3] DAI L, WANG B, YUAN Y, et al. Non-orthogonal multiple access for 5G: solutions, challenges, opportunities, and future research trends[J]. IEEE Communications Magazine, 2015, 53(9): 74-81.

[4] HOSHYAR R, WATHAN F P, TAFAZOLLI R. Novel low-density signature for synchronous CDMA systems over AWGN channel[J]. IEEE Transactions on Signal Processing, 2008, 56(4): 1616-1626.

[5] BEEK J V D, POPOVIC B M. Multiple access with low-density signatures[C]//IEEE Global Telecommunications Conference, January 26-28, 2009, London, UK. New Jersey: IEEE Press, 2009: 1-6.

[6] NIKOPOUR H, BALIGH H. Sparse code multiple access[C]// IEEE International Symposium on Personal Indoor and Mobile Radio Communications, September 8-11, 2013, London, UK. New Jersey: IEEE Press, 2013: 332-336.

[7] AU K, ZHANG L, NIKOPOUR H, et al. Uplink contention based SCMA for 5G radio access[C]//IEEE GLOBECOM Workshops, December 8-12, 2014, Austin, TX, USA. New Jersey: IEEE Press, 2014: 900-905.

[8] ZHANG S, XU X, LU L, et al. Sparse code multiple access: an energy efficient uplink approach for 5G wireless systems[C]//IEEE Global Communications Conference, December 8-12, Austin, TX, USA. New Jersey: IEEE Press, 2014: 4782-4787.

[9] TAHERZADEH M, NIKOPOUR H, BAYESTEH A, et al. SCMA codebook design[C]//IEEE Vehicular Technology Conference, September 14-17, 2014, Vancouver, Canada. New Jer-sey: IEEE Press, 2014: 1-5.

[10] 畢奇, 梁林, 楊姍, 等. 面向 5G 的非正交多址接入技術[J].電信科學, 2015, 31(5): 14-21. BI Q, LIANG L, YANG S, et al. Non-orthogonal multiple access technology for 5G systems[J]. Telecommunications Science, 2015, 31(5): 14-21.

[11] 馬國玉, 艾渤, 胡顯安, 等. 5G過載零星傳輸系統中的多用戶檢測技術性能分析[J]. 電信科學, 2016, 32(8): 39-45. MA G Y, AI B, HU X A, et al. Performance analysis of multi-user detection of 5G overloaded sporadic system[J]. Telecommunications Science, 2016, 32(8): 39-45.

[12] WANG B, WANG K, LU Z, et al. Comparison study of non-orthogonal multiple access schemes for 5G[C]// IEEE International Symposium on Broadband Multimedia Systems and Broadcasting, June 17-19, 2015, Ghent, Belgium. New Jersey: IEEE Press, 2015: 1-5.

[13] WU Y, ZHANG S, CHEN Y. Iterative multiuser receiver in sparse code multiple access systems[C]//ICC IEEE International Conference on Communications, June 8-12, 2015, London, UK. New Jersey: IEEE Press, 2015: 2918-2923.

[14] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2): 498-519.

[15] MU H, MA Z, ALHAJI M, et al. A fixed low complexity message pass detector for up-link SCMA system[J]. IEEE Wireless Communications Letters, 2015, 4(6): 585-588.

Research on low complexity decoding for SCMA based on serial strategies of variable node

JI Mingming, ZHENG Jianhong
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Sparse code multiple access technology, as a competitive non orthogonal multiple access scheme for the fifth generation wireless communication network, has a broad application prospect. However, current SCMA uplink use the flooding scheme of message passing algorithm for decoding, both the detection complexity and convergence properties are not ideal. A serial message passing algorithm which changed the information updating strategy was proposed, which performed message processing and deliveried according to the order of the variable nodes. Each of variable node simultaneously performed the reception of the verification message and the transmission of the variable message. The theoretical and simulation results show that the proposed algorithm not only maintains good performance, but also has low decoding complexity.

sparse code multiple access, multiuser detection, variable node, serial message passing

The National Science and Technology Major Project of China (No.2016ZX03002010-003)

TN929

：A

10.11959/j.issn.1000-0801.2017226

吉明明（1992-），男，重慶郵電大學通信與信息工程學院碩士生，主要研究方向為5G關鍵技術——新型多址技術SCMA。

鄭建宏（1961-），男，重慶郵電大學通信與信息工程學院教授，主要研究方向為新一代寬帶移動通信協議及系統應用。

2017-03-15；

：2017-07-16

國家科技重大專項基金資助項目（No.2016ZX03002010-003）