基于變量節點穩定性的SCMA 多用戶檢測算法

范鵬，李旭東

（西華大學理學院，成都610039）

0 引言

隨著第四代移動通信系統（The Fourth Generation Mobile Communication Systems，4G）的大規模商業化及其技術的不斷成熟，第五代移動通信系統（The Fifth Generation Mobile Communication Systems，5G）已成為全球研發的焦點[1-2]。目前，我國工信部已正式發放5G 商用牌照，與4G 相比，5G 在頻譜資源利用率和終端設備接入量均有很大的提高。非正交多址接入技術[3]（Non-Orthogonal Multiple-Access，NOMA）擁有頻譜效率較高的特點，在5G 通信中有著廣泛的應用。作為NOMA技術的一種，SCMA[4-5]利用碼本的稀疏性能夠連接大量不同的終端用戶，并同時為終端用戶服務。在發送端，每個用戶將數據比特直接映射為SCMA 碼本中的多維碼字，多個用戶的碼字進行疊加，使得同一頻譜資源上可以承載多個用戶，大幅度地提高了系統容量。在接收端，接收信號是多個用戶碼字和噪聲的疊加，需要對接收信號通過多用戶檢測（Multi-user Detection，MUD）技術來實現用戶譯碼。

利用SCMA 碼序列的稀疏性，在接收端使用復雜度相對較低的消息傳遞算法（Message Passing Algorithm，MPA）[6]進行譯碼。該系統中多個用戶共享頻率資源，來成倍提高系統容量和頻譜利用率，同時，基于MPA 的MUD 極大地降低了聯合最優最大后驗概率（Maximum-A-Posteriori，MAP）的復雜度。但原始的MPA 算法復雜度依然很高，特別是用戶碼本大小增加以及同一資源的用戶數增多時，其計算復雜度呈指數增長。為了降低原始MPA 算法復雜度，文獻[7]通過每次迭代計算未判決用戶的碼字可信度，將碼字可信度滿足門限條件的用戶提前譯碼來降低算法復雜度；文獻[8]提出函數節點在每次迭代中以串行方式，將已更新的消息立即傳遞到當前迭代中，從而降低算法復雜度；文獻[9]引入權重因子改變每個疊加星座點的初始概率，加快了迭代過程的收斂速度，降低了算法復雜度。此外文獻[10-12]通過不同的方法來降低算法的復雜度。

為了降低原始MPA 算法的復雜度，本文提出了一種變量節點穩定性判斷的方法。在每一輪迭代更新中，找出未譯碼用戶變量節點最大可信度的位置，若用戶所有變量節點最大可信度的位置相同，且在當前迭代和上次迭代中各變量節點最大可信度的位置也相同，則對用戶提前譯碼。仿真結果表明，本文所提算法在收斂速度和BER 性能上，優于門限MPA 算法和原始MPA 算法。在算法復雜度上優于原始MPA 算法。

1 系統模型

1.1 SCMA系統模型

假定一個上行多用戶SCMA 通信系統共有K 個資源塊，每個用戶占用資源數為N(NK)，其過載率為λ=J/K。SCMA系統中，每個用戶碼本有M 個不同的碼字，每個碼字由個比特映射而來，接收信號由J 個用戶的碼字和噪聲疊加而成。圖1 為用戶數為6 資源數為4 的上行SCMA 多用戶通信系統模型。

圖1 上行SCMA多用戶通信系統模型（J=6，K=4）

SCMA 碼的總結構可以由對應的因子圖及因子圖矩陣F=(f1，f2，…，fJ)來表示。當且僅當Fk，j=1 時，用戶j 占用資源塊k。稀疏矩陣的SCMA 因子圖及其矩陣如圖2 所示。

當J 個用戶同時接入時，接收信號可表示為：

其中，xj=(x1，j，x2，j，…，xK，j)T表示第j 個用戶發送的碼字，hj=(h1，j，h2，j，…，hK，j)T表示第j 個用戶的信道有效向量，n=(n1，n2，…，nK)表示信道噪聲且n ～cN(0，σ2I)。第k 個資源塊接收信號為：

圖2 SCMA碼本因子圖及其矩陣

1.2 原始MPA算法[5]

假定已知接收信號y 和信道矩陣H=(h1，h2，…，hJ)，用MAP 算法來檢測用戶數據X=(x1，x2，…，xJ)，如式：

MPA 算法是利用因子圖求邊緣概率分布的一種迭代算法，在算法迭代過程中，因子圖的變量節點和函數節點之間通過邊傳遞消息，每次消息傳遞后，根據一定的計算準則更新每個節點存儲的可信度值，以便計算下一次傳遞的外部信息。在多次消息迭代更新后，獲得一個關于所有用戶碼字的邊緣概率分布，以此概率分布作為判決量判決輸出結果，從而判斷出每個用戶發送的碼字。MPA 算法利用了碼本稀疏性的特征，其算法復雜度為O(Mf)（f 表示每個資源上疊加的用戶數，f

第一步，初始化，即SCMA 接收機在迭代開始時，假設每個用戶發送各碼字的概率相同，即：

第二步，由式（5）和式（6）分別更新函數節點和變量節點的消息，即：

其中，εk表示占用資源k 的用戶集合，l ∈εk/j 表示從集合εk中除去用戶j，目的是獲得用戶j 的外信息，normalize()· 表示歸一化。式（7）涉及信道傳遞函數，即：

第三步，迭代步數加1，重復第二步的操作，直到迭代次數達到最大迭代次數Tmax，對用戶碼字進行譯碼。

2 本文算法

2.1 變量節點穩定性的多用戶檢測算法

雖然MPA 算法極大地降低了MAP 的復雜度，使其硬件實現成為可能，但是當系統用戶數過多、用戶碼本尺寸過大或信號經歷快衰落時，MPA 復雜度依舊很高，不能滿足高質量的通信需求。

為了降低SCMA 多用戶檢測的復雜度，本文提出了基于變量節點穩定性的多用戶檢測算法。在每一輪迭代更新中，找出未譯碼用戶變量節點最大可信度的位置，若用戶所有變量節點最大可信度的位置相同，且在當前迭代和上次迭代中各變量節點最大可信度的位置也相同，則對用戶提前譯碼。這使得在保證降低算法復雜度的同時，提高了用戶譯碼的可靠性。

首先我們根據用戶是否已經提前譯碼，將用戶分為兩個集合，譯碼集φ 和非譯碼集ψ。在算法初始化階段，所有用戶都未譯碼，即所有用戶都在非譯碼集ψ之中。在每次消息迭代更新后，由式（9）找出第t 次迭代時用戶j 在資源塊k 上碼字可信度最大的位置，即：

根據式（8）可知，用戶發送碼字的可信度等于該用戶所有資源上變量節點的乘積。當檢測到任意用戶j的變量節點碼字最大可信度位置有不同時，這說明用戶j 的變量節點還未完全收斂，若此時直接將用戶j 進行譯碼，多用戶檢測的誤碼概率將會大大增加。因此當用戶j 的變量節點碼字最大可信度位置相同時，即，用戶j 譯碼的準確性將有所提高。為了進一步提高用戶譯碼的準確性，這里給出變量節點穩定性判斷定義：在算法迭代過程，若用戶j 的某一變量節點在當前迭代和上一次迭代中，檢測到最大碼字可信度的位置為同一位置，即，則用戶j 的這一變量節點趨于穩定。只有當用戶j 的所有變量節點碼字可信度均最大且滿足穩定性條件時，才將用戶j 提前譯碼，并將該用戶從非譯碼集ψ 移出放入譯碼集φ。若運行到最大迭代次數后若非譯碼集ψ 中仍有用戶存在，由式（10）繼續對剩余非譯碼集ψ 中用戶進行譯碼，即：

從而確定所有用戶的碼字。

2.2 復雜度分析

MPA 算法過程主要分為消息更新和碼字檢驗兩個階段，其算法復雜度主要體現在消息更新上。本文算法僅僅在每次消息更新迭代結束后，判斷用戶在后續迭代中是否繼續消息迭代更新，這個過程并沒有破壞用戶消息更新環節。比較原始MPA 算法[6]、門限MPA算法[7]和本文所提到的算法復雜度，只需要比較不同算法在迭代過程中需要的乘法運算數目即可。原始的MPA 算法所需的乘法個數為[13]：

其中dr和dc分別表示每個資源塊上的用戶數和每個用戶占用的資源塊數。由式（11）可知，在用戶碼本不變的情況下，影響本文算法復雜度的參數為用戶數和迭代次數。在本文算法中，因噪聲存在隨機性，不能給出具體算法復雜度的公式表達。在每次迭代過程中，用戶數隨著部分用戶提前譯碼而逐步減少，特別是當信噪比越高時，所有用戶未達到最大迭代次數就能被全部譯碼，故所提算法復雜度低于原始MPA 算法的復雜度。本文算法與門限MPA 算法相比，將用戶碼字提前判決條件從用戶碼字可信度降低到變量節點碼字可信度，減少了提前判斷用戶碼字時各變量節點的軟信息損失，從而提高了BER 性能。

3 仿真分析

通過仿真對比原始MPA 算法[6]、門限MPA 算法[7]以及本文提出的算法，驗證本文算法BER 性能，收斂速度和算法復雜度。由于門限MPA 算法在門限較高時近似原始MPA 算法，仿真只選擇門限為Th=20 來進行對比。在仿真中，用戶數為6，資源塊數為4，最大迭代次數為6，信道模型為AWGN。

3.1 BER性能比較

圖3 中可以看出，在迭代次數為2 時，本文提出的算法性能優于門限MPA（Th=20）和原始MPA 算法。在Eb/N0=11 時，迭代次數為2 的門限MPA（Th=20）和原始MPA 算法的EBR 值分別為0.0039 和0.0036，而本文算法的BER 值為0.0012，特別是Eb/N0>11 時，可以看到本文迭代2 次的EBR 性能明顯優于門限MPA（Th=20）的迭代4 次的EBR 性能。圖3 中還可以看出，本文算法迭代4 次的BER 性能幾乎和原始MPA算法迭代4 次的BER 性能相當，在Eb/N0=13 時，這兩種算法的BER 值相差僅為0.2×10-4。由于本文算法每次迭代后，已被譯碼的用戶不再繼續參與到后續迭代的消息更新中，故本文算法和原始MPA 算法相比不僅能保證BER 性能，同時也能大幅度的降低算法的復雜度。

3.2 收斂速度分析

從圖3 可以看出，在迭代次數為2 時，本文提出的算法的碼字收斂速度優于門限MPA（Th=20）和原始MPA 算法。從圖4 可以看出，在為11 和13 時，本文算法迭代3 次就趨于收斂，而門限MPA 算法和原始MPA 算法至少要迭代5 次才趨于收斂。本文所提算法的收斂速度明顯優于門限算法和原始MPA 算法。

圖3 不同算法不同迭代次數的BER對比

圖4 各算法收斂速度對比

3.3 復雜度對比

為了對比各算法之間的復雜度，在仿真過程中統計出各算法在不同、不同迭代次數下的平均乘法次數。在Eb/N0=13，迭代次數為4 時，本文所提算法、門限MPA 算法（Th=20）和原始MPA 算法的平均乘法次數為9974、6171 和18456，本文算法和門限MPA算法（Th=20）相比復雜度高61.6%，但BER 性能高68.7%，和原始MPA 算法相比復雜度只有原始MPA 算法的54%，BER 性能降低13.8%。

4 結語

為了降低SCMA 系通信統中多用戶檢測算法的復雜度，本文提出了基于變量節點穩定性的多用戶檢測算法。該算法在收斂速度和BER 性能方面明顯優于門限MPA 算法，與原始MPA 算法相比，在BER 性能幾乎不變的前提下，大大降低了算法的復雜性。因此，本文所提算法具有較高的實用性。