吉明明，鄭建宏

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

基于變量節(jié)點串行策略的SCMA低復(fù)雜度譯碼研究

吉明明，鄭建宏

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

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

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

1 引言

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

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

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

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

2 系統(tǒng)模型

2.1 上行SCMA系統(tǒng)概述

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

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

SCMA編碼器將用戶比特根據(jù)用戶的碼本直接映射對應(yīng)復(fù)數(shù)域碼字，即：

圖1 上行SCMA系統(tǒng)模型

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

SCMA編碼器的編碼函數(shù)可定義如下：

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

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

圖2 SCMA的因子圖與矩陣的關(guān)系

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

2.2 原始MPA

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

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

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

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

在因子圖中，變量節(jié)點可以通過如下規(guī)則進行更新：

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

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

3 串行譯碼算法

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

3.1 基于變量節(jié)點串行譯碼算法

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

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

根據(jù)式（7）與式（8），可得：

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

3.2 復(fù)雜度分析

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

表1 不同MPA所需乘法器數(shù)目

4 仿真結(jié)果與分析

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

4.1 收斂速度

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

4.2 BER性能

圖5給出了本文算法S-MPA、原始MPA與PM-based MPA在不同信噪比條件下BER性能與迭代次數(shù)的關(guān)系曲線，可以看到，隨著信噪比的增大，BER性能有了明顯的改善。從圖 5可以得到，對于相同的迭代次數(shù)，本文算法的譯碼性能都優(yōu)于原始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性能優(yōu)于 6次迭代的 PM-based MPA，并且伴有0.65 dB的增益。

圖4 各種算法的收斂速度

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

4.3 復(fù)雜度對比

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

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

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

5 結(jié)束語

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

[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 的非正交多址接入技術(shù)[J].電信科學(xué), 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過載零星傳輸系統(tǒng)中的多用戶檢測技術(shù)性能分析[J]. 電信科學(xué), 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-），男，重慶郵電大學(xué)通信與信息工程學(xué)院碩士生，主要研究方向為5G關(guān)鍵技術(shù)——新型多址技術(shù)SCMA。

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

2017-03-15；

：2017-07-16

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