基于部分碼字譯碼的MPA檢測算法

摘" 要： 稀疏碼多址接入技術（SCMA）是一種新型非正交多址接入技術。針對 SCMA中消息傳遞算法進行多用戶檢測復雜度較高的問題，提出基于部分碼字球形譯碼多用戶檢測算法（PCSD?MPA）。該算法通過設置球型半徑減少參與迭代的用戶碼字，并根據SCMA的非正交特性引入信道質量這一新的判決機制，從而進一步降低MPA算法的計算復雜度。同時采用部分碼字初始概率均等分配策略，有效提升了算法的收斂速率。仿真結果表明，在球形半徑設定合理的條件下，PCSD?MPA在幾乎不改變系統誤比特率性能的情況下降低了MPA的復雜度，且該算法的計算復雜度隨著SNR的增大明顯降低。

關鍵詞： 稀疏碼多址接入; 非正交多址接入; 消息傳遞算法; 多用戶檢測; 球形譯碼; 信道質量

中圖分類號： TN929.5?34" " " " " " " " " " " " 文獻標識碼： A" " " " " " " " " " " " "文章編號： 1004?373X（2019）21?0018?05

Abstract： Sparse code multiple access （SCMA） technology is a new non?orthogonal multiple access technology. Since the message passing algorithm in SCMA has high complexity in multiuser detection， a partial code?word spherical decoding based multiuser detection algorithm （PCSD?MPA） is proposed in this paper， which reduces the number of user codes participating in the iteration by setting the spherical radius， and introduces a new decision mechanism， channel quality according to the non?orthogonal characteristics of SCMA to further reduce the computational complexity of MPA algorithm. A partial code?words initial probability equal allocation strategy is adopted to effectively improve the convergence rate of the algorithm. Simulation results show that the proposed PCSD?MPA can reduce the complexity of MPA almost without changing the bit error ratio under the condition of reasonable set?up of sphere radius. The computational complexity is obviously reduced with the increase of SNR.

Keywords： sparse code multiple access; non?orthogonal multiple access; message passing algorithm; multiuser detection; sphere decoding; channel quality

0" 引" 言

與第四代移動通信系統相比，第五代（5G）移動通信系統具有廣覆蓋、低延遲、高可靠、低功耗、高頻譜效率和海量連接等特點[1]。由于傳統正交多址技術中接入用戶數與頻譜資源數量成正比，無法滿足5G高頻譜效率和海量連接等需求，因此非正交多址接入技術被提出用于解決上述問題[2?4]。針對這一情況，華為提出基于碼域的非正交多址接入技術（SCMA），其主要思想是將高維調制和低密度簽名多址接入相結合，直接把比特流映射成預先設定碼本里的多維碼字，從而解決系統過載問題[5]。與正交多址技術相比，SCMA具有更高的頻譜效率和更多的用戶接入[6]。然而，將SCMA應用到5G系統中還需解決多用戶檢測復雜度過高的問題。文獻[7]提出基于因子圖迭代的消息傳遞算法（MPA）作為SCMA檢測的主流算法，其計算復雜度相比最大似然檢測明顯降低，但是其收斂速度過慢，計算復雜度仍然偏高，因此不適用于實際移動通信系統中。為了提高其收斂速度，文獻[8]提出一種串行MPA檢測算法。文獻[9]根據信道質量，提出一種減少用戶節點的MPA算法;另外，一種基于球形譯碼的MPA算法在文獻[10]中提出，但該算法只考慮了用戶碼字在單一資源節點上對檢測結果的影響，并未從用戶節點的角度考慮碼字在多個資源節點上對檢測結果的影響。

基于上述分析，本文針對收斂速度較快的串行MPA算法，提出一種新的基于部分碼字球形譯碼的MPA多用戶檢測算法（PCSD?MPA）。該算法綜合考慮資源節點和用戶間節點之間的映射關系，在原有球形譯碼算法基礎上引入信道質量這一新的判決標準，有效減少了參與迭代的碼字，并且由于只有部分碼字參與迭代，因此初始化時只對參與迭代的碼字進行等概率分配，增大剩余碼字的初始概率，加快迭代過程的收斂速率，從而降低檢測算法的計算復雜度。

1" 系統模型

1.1" 上行SCMA系統模型

在多用戶SCMA系統中，不同用戶將輸入的二進制比特流通過不同的SCMA碼本，直接映射到SCMA多維碼本的碼字上。假設用戶數和碼本數都是[J]，每個碼本長度為[K]，非零元素個數為[N（Nlt;K）]，其過載因子定義為[λ=JK]。在傳輸時，第[j]個用戶的[log2 M]比特流通過[K]維復數域碼字[xj]直接映射到[K]個共享的正交子載波上。其中，碼字[xj]是從碼本[Xj]中選出，且[M=Xj]為碼本尺寸。

SCMA資源塊和用戶間的映射關系可以用因子圖矩陣 [F=（f1， f2，…， fJ）]表示。當且僅當[Fkj=1]時，用戶節點[uj]與資源節點[rk]連接。[J=6]，[K=4]的SCMA因子圖及其矩陣[F]之間的對應關系如圖1所示。

假定一個上行多用戶SCMA通信系統，[J]個用戶共享[K]個正交時頻資源，并傳輸數據給同一個基站。若所有用戶時間同步，基站接收到的信號為所有用戶的疊加信號，則接收信號可以表示為：

式中：[xj]表示第[j]個用戶發送的碼字;[hj]表示第[j]個用戶的信道增益向量;[n]為高斯白噪聲，且[n～cN（0，σ2I）]。則資源節點[k]處接收到的信號為：

由于碼字[xj]是稀疏的，所以在資源節點[k]處僅有較少的碼字沖突。

1.2" MPA檢測算法

MPA是SCMA檢測的主流算法，其實現過程包括兩個階段：

階段1：所有資源節點以用戶節點傳遞過來的信息為先驗信息，同時更新因子圖中全部資源節點[rk]到用戶節點[uj]的消息[Mtrk→uj（xj）]。

階段2：所有用戶節點通過合成資源節點傳遞過來的消息進行更新，同時更新因子圖中所有用戶節點[uj]到資源節點[rk]的消息[7][Mtuj→rk（xj）]。則MPA可以用數學公式表示為：

式中：[t]為迭代次數;[εk]與[ζj]分別表示稀疏碼矩陣[F]第[k]行的非零位置集與第[j]列的非零位置集。其中，概率密度函數為：

式中：[xk（[mj]）]定義為資源塊[k]上所連接的所有用戶發送端可能發送的碼字元素組成集合，達到預先設定的最大迭代次數[tmax]后，用戶碼字輸出概率可以表示為：

為了有效提升MPA算法的收斂速度，文獻[10]提出了串行MPA算法，其表達式如下：

串行 MPA多用戶檢測算法在每輪迭代過程中，更新后的消息馬上傳遞給后續節點，而不必等到下一輪迭代過程，加快了MPA的收斂性。 串行MPA（3次迭代） 和MPA（6次迭代）達到收斂后的性能相當，但其計算復雜度依然偏高，仍有較大改進空間。

2" PCSD?MPA檢測算法

為了進一步降低MPA的復雜度，本文結合SCMA的非正交性，以球形譯碼理論為基礎，引入信道質量這一新的判決標準，對用戶碼字進行篩選，減少參與迭代的碼字從而降低MPA的計算復雜度。假定[J=6]，[K=4]，式（2）按因子圖矩陣[F]展開得：

當碼本尺寸[M=4]時，由式（8）可知，資源節點[rk]上所承載的用戶數[df=3]，則資源節點[k]上有43=64個合成星座點（Synthetic Constellation Points，SCP）參與MPA迭代運算，其分布如圖2所示。

由球形譯碼理論可知，合成星座點的歐氏距離越接近接收信號點，越有可能正確譯碼[10]。則可以通過設置球形半徑來減少參與迭代的用戶碼字，其表達式為：

式中：[Dk（[mj]）]為合成星座點與接收信號之間的歐氏距離;[β]是大于0的實數。當[Dk（[mj]）]大于半徑[R]時，舍棄對應的SCP，僅保留[Dk（[mj]）]小于半徑[R]的這一部分碼字參與MPA的計算。球形譯碼半徑[R]是由噪聲功率[σ2]決定的，通過調節[R]的大小可以在計算復雜度和誤碼率（Bit Error Ratio，BER）之間取得折中。其中，[β]=1，2，3時的置信區間和正確譯碼概率之間的對應關系如表1所示。

當[R=2σ]時，置信區間為[（-2σ，2σ）]，可以保證資源塊[k]上正確譯碼的概率值達到95.4%。

式中：半徑[R]值設定要合理，過小將會把一部分能夠正確譯碼的碼字篩選掉，從而影響檢測結果。該式即為文獻[10]提出的SD?MPA多用戶檢測算法，可以明顯降低算法復雜度。但該算法只考慮了用戶碼字對資源節點譯碼的影響，并未考慮對用戶節點的影響。從用戶節點考慮，假設第[j]個用戶的碼字[xj（mj）]中的[N]個非零元素[xnj（mj）（1≤n≤N）]同時映射到了[N]個資源節點上，那么在同一球形半徑[R]的條件下，第[n]個資源節點上滿足門限條件的合成星座點將會包含[j]用戶的碼字元素[xnj（mj）]。由于信道為獨立衰落信道，[du]個信道系數[hk，j（k∈ζj）] 都不相同，即一些資源節點的信道增益比其他資源節點大得多，信道質量越高，通過該信道的消息越可靠，因此可以將信道質量作為碼字篩選的一個評判標準。本文采用華為公布的4～6碼本，每個用戶占用兩個資源進行數據傳輸。讓[k1]和[k2]分別代表每個碼字中的兩個非零元素的位置，則碼字篩選公式定義如下：

式中[Mj]表示用戶[j]的候選碼字集合，只有信道質量最佳的資源節點用來篩選用戶[j]的碼字。將由式（11）得到的候選碼字代入式（7），則式（7）可以改寫為：

式（12）即為本文提出的PCSD?MPA多用戶檢測算法，該算法由于綜合考慮了資源節點和用戶節點之間的數據映射關系，不但減輕資源節點的負擔，還能減輕用戶節點的負擔，且該算法只有部分碼字參與多用戶檢測階段，對[M0uj→rk（xkj（mj））]初始化時，只對參與運算的碼字等概率分配，初始化公式定義為：

由式（13）可知，由于采用部分碼字初始概率均等分配策略，剩余碼字越少，每個碼字的初始概率越大，這樣可以加快迭代的收斂速度，有效降低了計算復雜度。

3" 仿真結果分析

本文基于典型的上行SCMA系統模型對提出的PCSD?MPA進行仿真，并與串行MPA和SD?MPA算法進行比較，具體仿真參數如表2所示。

3.1" 誤碼率性能對比

圖3為本文提出的PCSD?MPA與串行MPA以及SD?MPA在迭代3次的誤碼率性能隨信噪比（Signal to Noise Ratio，SNR）的對比圖。由圖3可以看出，判決半徑[R]越小，BER性能越差，原因是[R]過小將會過度篩選用戶碼字信息。當[R=2σ]時，本文所提到的三種算法的誤碼率性能相近，主要原因是基于歐氏距離的球形譯碼理論進行碼字篩選可以大概率的保證多用戶檢測的正確性。

3.2" 收斂性能對比

圖4為本文所提PCSD?MPA（[R=2σ]）與SD?MPA（[R=2σ]）以及串行MPA收斂性對比圖。由圖4可知，本文所提算法在高SNR條件下，迭代1次和2次的BER性能要好于SD?MPA和串行MPA算法。SD?MPA在迭代次數較小的情況下其誤碼率性能與串行MPA接近。值得注意的是，本文所提算法，迭代2次的BER性能與串行MPA迭代3次的BER性能接近，原因是高信噪比條件下篩選掉的碼字較多，這樣在初始化階段采用部分碼字概率均等策略可以加快其收斂速度。

3.3" 復雜度對比

圖5表示本文所提算法PCSD?MPA、SD?MPA以及串行MPA在[tmax=3]時算法復雜度對比。算法復雜度以任意資源節點[k]處平均合成星座點傳遞量進行衡量，串行MPA算法每個資源節點的平均合成星座傳遞量為64。由圖5可知，SD?MPA隨著[R]的減少復雜度越來越低。本文所提算法復雜度呈現快速下降趨勢，復雜度進一步降低，原因是根據SCMA的非正交特性，引入信道質量這一新的判決機制，進一步去掉了一些合成星座點，因此能有效降低復雜度。綜合來看，本文所提算法在誤碼率性能和復雜度之間能夠取得較好的平衡。

4" 結" 語

本文針對MPA具有復雜度較高的特點，根據球形譯碼理論，結合SCMA的非正交特性，提出一種基于部分碼字球形譯碼運算的PCSD?MPA多用戶檢測算法。由于每個用戶只有部分碼字參與檢測階段，在初始化階段，采用部分碼字初始概率均等分配策略，因此有助于提升其收斂性。仿真結果表明，相比串行MPA，在球形半徑設定合理的情況下，本文所提的PCSD?MPA可以在復雜度和誤碼率之間取得較好的平衡，且在SNR較高的條件下，收斂速度也有所提高，更適用于5G通信系統。

參考文獻

[1] SOLDANI D， MANZALINI A. Horizon 2020 and beyond： on the 5G operating system for a true digital society [J]. IEEE vehicular technology magazine， 2015， 10： 32?42.

[2] BENJEBBOUR A， SAITO Y， KISHIYAMA Y， etc. H Concept and practical considerations of non?orthogonal multiple access （NOMA） for future radio access [C]// Proceedings of International Symposium on Intelligent Signal Processing and Communications Systems （ISPACS）. [S. l.： s.n.]， 2013： 770?774.

[3] THOMPSON J， GE X， WU H C， et al. 5G wireless communication systems： prospects and challenges [J]. IEEE communications magazine， 2014， 52（2）： 62?64.

[4] DAI L L， WANG B C， YUAN Y F， et al. Non?orthogonal multiple access for 5G： solutions， challenges， opportunities， and future research trends [J]. IEEE communications magazine， 2015， 53（9）： 74?81.

[5] 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.

[6] DU Y， DONG B， CHEN Z. Joint sparse graph?detector design for downlink MIMO?SCMA system [J]. IEEE wireless communications letters ， 2017， 6（1）： 14?17.

[7] 杜洋，董彬虹，王顯俊，等.基于串行策略的SCMA多用戶檢測算法[J].電子與信息學報，2016，38（8）：1888?1893.

DU Y， DONG B H， WANG X J， et al. Multiuser detection scheme for SCMA systems based on serial strategy [J]. Journal of electronics amp; information technology， 2016， 38（8）： 1888?1893.

[8] DU Y， DONG B， CHEN Z， et al. A fast convergence multiuser detection scheme for uplink SCMA systems [J]. IEEE wireless communications letters， 2016， 5（4）： 388?391.

[9] DU Yang， DONG Binhong， CHEN Zhi， et al. Low complexity detector in sparse code multiple access systems [J]. IEEE communications letters， 2016， 20（9）： 1812?1815.

[10] YANG L， MA X， SIU Y. Low complexity MPA detector based on sphere decoding for SCMA [J]. IEEE communications letters， 2017， 21（8）： 1855?1858.

[11] LU L， CHEN Y， GUO W， et al. Prototype for 5G new air interface technology SCMA and performance evaluation [J]. China communications， 2015， 12（S1）： 38?48.