空間調制信號的低復雜度球形譯碼算法

王 奔, 張文彬, 趙洪林

(哈爾濱工業大學 通信技術研究所，哈爾濱 150080)

空間調制信號的低復雜度球形譯碼算法

王 奔, 張文彬, 趙洪林

(哈爾濱工業大學 通信技術研究所，哈爾濱 150080)

為進一步降低球型譯碼算法(SM-SD)的復雜度，同時不影響算法的誤比特性能，提出一種SM-SD算法，采用了不同于目前存在的SM-SD算法的復變量實數化方式，具有獨特的搜索樹結構，搜索樹的相鄰兩層相互獨立. 分析了新算法的原理及搜索過程，通過矩陣運算理論分析了幾種SM-SD算法的運算復雜度，然后在不同的空間調制系統中對SM-SD算法的誤比特性能和運算復雜度進行仿真. 理論分析和仿真結果表明：新算法的性能接近于最大似然算法，運算復雜度低于已有的各種類型的球型譯碼算法，因此更加適合于檢測空間調制信號.

空間調制；球形譯碼算法；SM-SD算法；最大似然檢測；多輸入多輸出系統

大規模多輸入多輸出(Massive Multi-input Multi-output，Massive MIMO)系統需要復雜的天線間同步技術及多條射頻鏈路[1]，導致系統的運算復雜度較高、能量消耗和硬件實現難度較大[2]. 空間調制(Spatial Modulation，SM)技術是一種利用激活發射天線的序號和調制符號共同表示發射信息的新型傳輸方案，可完全消除空間多路MIMO系統中接收信號間的相互干擾，具有較高的傳輸速率. 空間調制系統采用最大似然(Maximum Likelihood，ML)檢測算法可獲得最佳的誤比特性能，但運算復雜度較高[3]. 迫零算法(ZF)、最小均方誤差算法(MMSE)等次優算法雖然降低了運算復雜度，但誤碼性能較差[4]，球形譯碼(Sphere Decoding，SD)算法可平衡系統運算復雜度和誤比特兩方面的性能[5]. 文獻[5-6]提出3種不同的空間調制下的球型譯碼算法，分別是：以接收端為中心的Rx-SD、以發射端為中心的Tx-SD和聯合方案C-SD. 在運算復雜度和誤比特性能方面，C-SD始終優于Tx-SD，Rx-SD和C-SD在不同的情況下各有優劣，3種算法的運算復雜度都低于ML，誤比特性能接近于ML.

在不影響空間調制系統誤比特性能的前提下，為了進一步降低球型譯碼算法的運算復雜度，本文提出一種新的SM-SD算法，通過理論分析和仿真比較這種新算法與已有的Rx-SD、C-SD算法的運算復雜度和誤比特性能.

1 系統模型

1.1 空間調制系統模型

SM的基本思想是將待發送的信息分為兩部分，一部分用于選擇激活發射天線的序號，另一部分用于選擇調制符號. 假設SM系統發射天線數量為Nt，接收天線數量為Nr，調制符號集合中元素總數為M，發射機每次發送m=log2(Nt)+log2(M)個二進制比特信息. log2(Nt)個比特信息由激活發射天線序號攜帶；log2(M)個比特信息由調制符號攜帶. 為了不失一般性，這里的調制符號選取正交幅度調制(QuadratureAmplitudeModulation，QAM). 本文中，激活發射天線的序號用lt表示，lt∈{1,2,…,Nt}，發射的調制符號用st表示，st∈{s1,s2,…,sM}. 圖1是一個具有4根發射天線的SM系統模型，調制方式為BPSK.q是待發送的二進制序列，根據表格將q分組后產生含有4個元素的發射向量x，其中唯一的非零元素的位置表示被激活的發射天線的序號[5].

圖1 空間調制系統的模型

在平坦慢衰落情況下，假設Nr×Nt維信道矩陣H中的每個元素相互獨立，即各子信道相互獨立，且服從均值為零與方差為1的復高斯分布，包絡服從瑞利分布. 假設每根接收天線上的噪聲n為理想加性復高斯白噪聲，噪聲功率譜密度是已知的，符號能量為1，Nt維發射向量xlt,st=[01×(lt-1),st,01×(Nt-lt)]T，Nr維的接收向量y為

y=Hxlt,st+n=hltst+n，

(1)

式中hlt位H的第lt列.

1.2 球形譯碼算法

在不考慮噪聲情況下，每一個發射向量xl,s經過無線信道H之后對應著一個格點Hxl,s，球型譯碼算法的思想是僅在以接收信號y為中心、以R為半徑的球體中進行搜索，球體內與y之間歐幾里得距離(簡稱歐氏距離)最小的格點對應于檢測到的發射向量.SD算法的檢測性能可以逼近ML，但不需要遍歷搜索所有的格點，在半徑R選擇恰當的情況下，運算復雜度相對于ML會大大降低[7].

SD算法實際上構造了一棵Nt層的搜索樹，樹中每一條路徑{l,s}表示一個格點，對應著一個可能的發射向量，l為工作的發射天線序號且l∈{1,2,…Nt}，s為發射符號且s∈{s1,s2,…,sM}.路徑的第一層對應發射向量的第Nt維，最后一層對應發射向量的第1維. 本文將某一層的歐氏距離稱為該層的“層歐氏距離”(下簡稱為層距)，而該層與它之前各層的層歐氏距離之和稱為“部分歐氏距離”.

2 空間調制—球形譯碼算法(SM-SD)

2.1 Rx-SD算法

Rx-SD遍歷搜索“發射搜索空間”中所有的NtM條路徑，對每條路徑從最高維開始不斷地累加各維的層距，只要其仍然在球體之內，就繼續在此路徑上搜索，否則舍棄該條路徑. 每當發現一條球內的完整路徑，就更新半徑為此路徑的歐氏距離.

式中yr和hl,r分別表示y和hl的第r維元素. 根據文獻[2]，Rx-SD算法減小了“接收搜索空間”，非常適用于Nr非常大的情況.

2.2 C-SD算法

C-SD算法同時減小“發射搜索空間”和“接收搜索空間”，它只計算位于球體內的格點的歐氏距離，并不斷更新搜索半徑，節省了層距的計算次數. 設ΘR是位于球體內部的發射向量的集合，C-SD可以寫成

}.

(2)

C-SD首先計算兩個非零元素所在各自維度上的取值區間，然后從“發射搜索空間”中尋找滿足取值區間的發射向量組成集合Θinterval，取值區間為

(3)

3 新SM-SD算法

3.1 新型實數化方式

(4)

第2Nt維

.

3.2 新SM-SD算法原理

式(3)中的各向量已經分別轉化為實向量

(5)

圖2 采用4QAM的4×4SM系統的碼搜索樹

Fig.2 Search tree structure of 4×4 SM system with 4QAM modulation

3.3 新SM-SD算法的步驟

此算法從搜索樹第1層(i=1)開始執行以下步驟. 初始條件下，假設所有發射向量構成一個集合φ1，再定義一個φ2為空集，將來用于保存與接收向量之間具有最小歐式距離的發射向量.

(6)

遍歷集合φ1中的發射向量之后:

a)如果集合φ2為空集，則增大半徑R，令i=1，φ1存入全部發射向量，重新回到Step1；

b)如果集合φ2為非空集，則算法結束，φ2中唯一發射向量即是發射信號.

a) 若i≤2Nt，說明還沒有搜索到搜索樹最后兩層，則返回到Step1.

b) 若i>2Nt，所有情況均已考慮完畢，集合φ1顯然已為空，對集合φ2進行判斷. 若φ2非空，則算法結束，若φ2仍為空，則增大半徑R，令i=1，φ1裝入全部發射向量.

(7)

(8)

如果此時集合φ2為空，則令檢驗門限M=R2. 如果wi+1>M，則從集合φ1中去除此發射向量，返回Step2；如果wi+1

(9)

新SM-SD算法執行過程可以由圖3和圖4中的流程圖來表示.

圖3 新SM-SD算法的流程圖

圖4 新SM-SD算法中Step3的流程圖

4 SM-SD算法運算復雜度分析

運算復雜度可以用算法過程中實數乘法運算的數量來衡量(本文中，除法也看作乘法)，下面對各算法(SM-ML、Rx-SD、C-SD、新SM-SD算法)的實乘運算次數進行分析.

4.1 SM-ML算法

4.2 Rx-SD算法

4.3 C-SD算法

C-SD的運算復雜度就是計算球內點集ΘR的復雜度，運算復雜度為CC-SD=Cpre-com+Cinterval+Ccheck.

2)C-SD的計算取值區間以及檢驗過程的運算復雜度為

4.4 新SM-SD算法

新SM-SD算法的運算復雜度包括：預先復雜度Cpre-com，求取值區間的復雜度Cinterval和檢驗Θinterval內格點的歐幾里得總距離的運算復雜度Ccheck.

2) 計算取值區間和檢驗Θinterval內格點歐幾里得總距離的運算復雜度為

解釋：

1)假設在搜索過程中，在碼搜索樹的第i∈(1,3,…2Nt-1)層，具有N(i)個非零可取值.

5 仿真結果分析

5.1 仿真設置及說明

在仿真實驗中，選取了多個發射天線數Nt、接收天線數Nr和調制尺寸M不同的SM系統，接收端采用新SM-SD、Rx-SD、C-SD和SM-ML算法，信道矩陣元素服從(0，1)復高斯分布，噪聲為加性高斯白噪聲，符號能量為1，通過改變噪聲的功率譜密度來設置信噪比在0至20dB的范圍內.SD的初始搜索半徑是在ε=10-6這一條件下根據R2=2αNrσn2來選取. 這里用“信道接入速率”表示單位時間內發射端發送的二進制比特數，用m表示，單位為“bit/信道接入”.

5.2 誤比特率仿真

圖5是Nt=Nr=4，采用16QAM的SM系統和Nt≠Nr，m=6的SM系統的BER. 仿真結果表明：新SM-SD和Rx-SD算法的誤比特性能與SM-ML幾乎完全相同，在相同的誤比特率條件下(例如取10-4)，C-SD算法所需要的信噪高于新SM-SD約1dB. 5.3 運算復雜度仿真

在比較運算復雜度時，將新SM-SD、Rx-SD和C-SD算法的運算復雜度用相對于SM-ML算法的減少量Crel來表示，Crel越大表示運算復雜度越低.

5.3.1 發射天線數與接收天線數相等的情況(Nt=Nr).

圖6和圖7是在Nt=Nr時幾種算法的運算復雜度仿真結果. 已知Rx-SD適用于Nr較大的情況，而C-SD適用于發射搜索空間較大的系統，這從圖6中也可以看出. 圖6和圖7表明：新SM-SD同樣適用于發射搜索空間大的系統，且優于C-SD，運算復雜度可達到SM-ML的10%以下. 不過，隨著M的增大，新SM-SD和C-SD的運算復雜度都不斷降低，新SM-SD的優勢逐漸減小，當M=64時，只有在高信噪比時新SM-SD才優于C-SD. 這是因為當M足夠大時，預先復雜度處于主導位置，而新SM-SD在實數化預處理時的預先復雜度高于C-SD. 此外，圖6也表明：在某些Rx-SD占優的情況下，信噪比較高時，新SM-SD也可以是最優的.

(a)Nr=4

(b)Nr=8

(a)M=4

(b)M=16

(c)M=64

Fig.6ComputationalcomplexityversusRSNforNt=Nr=4

(a)M=16

(b)M=64

Fig.7ComputationalcomplexityversusRSNforNt=Nr=8

5.3.2 發射天線數與接收天線數不相等的情況(Nt≠Nr)

這里只考慮超定系統(Nr>Nt)的情況. 圖8和圖9是在Nt≠Nr時幾種算法的運算復雜度仿真結果，從兩個方面來分析新SM-SD的運算復雜度，圖8和圖9表明：

1)若“發射搜索空間”不變，當Nr=6和Nr=8時，新SM-SD均優于C-SD，隨著Nr增大，Rx-SD的優勢逐漸顯現，而新SM-SD相對于C-SD的優勢減小，這是由于新SM-SD中QR分解的運算復雜度受Nr的影響大.

(a)Nr=6

(b)Nr=8

(c)Nr=10

Fig.8ComputationalcomplexityversusRSNform=6,Nt=4,M=16

(a)Nr=6

(b)Nr=8

Fig.9ComputationalcomplexityversusRSNform=4,Nt=4,M=4

2)若“接收搜索空間”不變，當m增加，即頻譜效率增加時，新SM-SD和C-SD的運算復雜度會降低，且新SM-SD始終優于C-SD，并在m=6時優于Rx-SD. 相比于SM-ML，m=6時的運算復雜度減少效果比m=4時提升了將近20%. 因此，新SM-SD算法更加適合于檢測空間調制信號.

6 結 語

本文提出一種具有新型實數化變換方式的新SM-SD算法，實發射向量中的兩維非零元素的位置相鄰，且檢測時相鄰的兩層互不影響，降低了運算復雜度. 理論上分析了新SM-SD算法的運算復雜度，在不同的SM系統中對新SM-SD算法的誤比特性能和運算復雜度進行仿真，并與已有的SM-SD算法相比較. 理論分析和仿真結果表明：新SM-SD算法在一定條件下可以降低運算復雜度，同時保持了與ML相同的誤比特性能，尤其在多數情況下優于C-SD. 在“發射搜索空間”較大，Nr不是很大的情況下，新SM-SD算法降低運算復雜度的效果十分理想，明顯優于C-SD和Rx-SD；在某些“接收搜索空間”較大的情況下，高信噪比時新SM-SD也會優于Rx-SD成為最佳選擇.

[1] GOLDSMITH A, JAFAR S A, JINDAL N, et al. Capacity limits of MIMO channels [J]. IEEE Journal on Selected Areas in Communications, 2003, 21(5):684-702. DOI: 10.1109/jsac.2003.810294.

[2] YOUNIS A, SINANOVI S, DI RENZO M. Generalized sphere decoding for spatial modulation [J]. IEEE Transactions on Communications, 2013, 61(7):2805-2815. DOI: 10.1109/tcomm.2013.061013.120547.

[3] RAJASHEKAR R, HARI K V S, HANZO L. Reduced-complexity ML detection and capacity-optimized training for spatial modulation systems [J]. IEEE Transactions on Communications, 2014, 62(1):112-124. DOI: 10.1109/tcomm.2013.120213.120850.

[4] 張文彬, 王孝, 陶晨嵩,等. 采用格基規約算法的空間調制檢測方案[J]. 哈爾濱工業大學學報, 2015, 47(11):63-68. DOI: 10.11918/j.issn.0367-6234.2015.11.011.

ZHANG W, WANG X, TAO C, et al. Spatial modulation detection schemes based on lattice reduction algorithm[J]. Journal of Harbin Institute of Technology, 2015, 47(11): 63-68. DOI:10.11918/j.issn.0367-6234. 2015. 11.011.

[5] YOUNIS A, MESLEH R, HAAS H, et al. Reduced complexity sphere decoder for spatial modulation detection receivers [C]//2010 IEEE Global Telecommunications Conference. Miami: IEEE Press, 2010:1-5. DOI: 10.1109/ glocom.2010.5683993.

[6] YOUNIS A, DI RENZO M, MESLEH R, et al. Sphere decoding for spatial modulation[C]//2011 IEEE International Conference on Communications. Kyoto: IEEE, 2011, 41(4):1-6. DOI: 10.1109/icc.2011.5963484.

[7] MAURER J, JALDEN D, SEETHALER D. Achieving a continuous diversity-complexity tradeoff in wireless MIMO systems via pre-equalized sphere decoding [J]. IEEE Journal of Selected Topics in Signal Processing, 2009, 3(6):986-999. DOI: 10.1109/jstsp.2009.2038210.

[8] XIA Xiaomei, HU Honglin, WANG Haifeng. Reduced initial searching radius for sphere decoder [C]//2007 IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications. Athens: IEEE, Press, 2007:1-4. DOI: 10.1109/pimrc.2007.4394469.

[9] LCSKEI H，GESBERT D，PAPADIAS C, et al. Space-time wireless systems: from array processing to MIMO communications [M]. Cambridge: Cambridge University Press, 2006:302-320.

[10]AZZAM L. Reduction of decoding complexity for MIMO sphere decoding, QOSTBC, and OSTBC systems[D]. Irvine: University of California, 2008. DOI: 10.1109/ita.2008.4601014.

[11]HASSIBI B, VIKALO H. On the sphere decoding algorithm I. expected complexity [J]. IEEE Transactions on Signal Processing, 2005, 53(8):2806-2818. DOI: 10.1109/tsp.2005.850352.

[12]MEN Hongzhi, JIN Minglu. A low-complexity ML detection algorithm for spatial modulation systems with MPSK constellation [J]. IEEE Communications Letters, 2014, 18(8):1375-1378. DOI: 10.1109/lcomm.2014. 2331283.

[13]AUBERT S, NOUVEL F, NAFKHA A. Complexity gain of QR decomposition based sphere decoder in LTE receivers[C]//2009 IEEE 70th Vehicular Technology Conference Fall. Anchorage: IEEE Press, 2009:1-5. DOI: 10. 1109/vetecf.2009.5378998.

(編輯 王小唯， 苗秀芝)

封面圖片說明

封面圖片來自第5期論文“纖維素/氧化硅有機-無機雜化復合氣凝膠的研究進展”，是哈爾濱工業大學特種環境復合材料技術國家級重點實驗室何飛副教授制作完成的纖維素/氧化硅有機-無機雜化復合氣凝膠的溶液浸漬法流程示意圖展示. 將具有生物材料特征的有機纖維素材料作為多孔模板或增強，采用原位溶液浸漬法，經溶膠-凝膠和干燥過程，可獲得具有高比表面積和納米孔結構特征的纖維素/氧化硅復合氣凝膠. 在研究中，通過選用不同類型的纖維素和氧化硅先驅體，借助于先驅體提供的不同官能團作用，可賦予纖維素/氧化硅有機-無機雜化復合氣凝膠多種特殊性質，使該類材料在保持氣凝膠獨特的低密度、高孔隙率、高比表面積和低熱導率等結構與性能特點的同時，還在一定程度上改變和提高材料在力學、疏水、光學以及耐熱性等方面的性能，因而，在隔熱、生物、醫學、吸附、包裝、光學等多種領域具有廣泛的應用前景和研究價值.

(圖文提供：何飛，駱金，李亞，方旻翰，赫曉東. 哈爾濱工業大學特種環境復合材料技術國家級重點實驗室)

Low complexity sphere decoding algorithm for spatial modulation signals

WANG Ben, ZHANG Wenbin, ZHAO Honglin

(Communication Research Center, Harbin Institute of Technology, Harbin 150080, China)

In order to reduce more complexity while maintaining a good bit error rate performance, a new SM-SD algorithm is proposed. The new SM-SD algorithm employs a different real-valued equivalent transformation from existing sphere decoding algorithms, and it has a unique search tree structure, the adjacent two layers of the search tree are independent of each other. The principle and process of the new algorithm are analyzed, and the computation complexity of SM-SD algorithms is compared by the matrix analysis. Then, the bit error rate and computational complexity of SM-SD algorithms are compared by simulation in different SM systems. Theoretical analysis and simulation results show that the new SM-SD algorithm has a very close performance to Maximum-Likelihood optimum detection, with lower computational complexity than other existing SM-SD algorithms. Thus, the new SM-SD algorithm is more suitable for SM signals detection.

spatial modulation; sphere decoding algorithm; SM-SD algorithm; ML detection；MIMO system

10.11918/j.issn.0367-6234.201607101

2016-07-25

中央高校基本科研業務費專項資金資助(HIT.MKSTISP.201613)

王 奔(1994—)，男，碩士研究生； 趙洪林(1969—)，男，教授，博士生導師

張文彬，zwbgxy1973@hit.edu.cn

TN911.3

A

0367-6234(2017)05-0022-09