王 奔, 張文彬, 趙洪林

(哈爾濱工業(yè)大學(xué) 通信技術(shù)研究所，哈爾濱 150080)

空間調(diào)制信號(hào)的低復(fù)雜度球形譯碼算法

王 奔, 張文彬, 趙洪林

(哈爾濱工業(yè)大學(xué) 通信技術(shù)研究所，哈爾濱 150080)

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

空間調(diào)制；球形譯碼算法；SM-SD算法；最大似然檢測；多輸入多輸出系統(tǒng)

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

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

1 系統(tǒng)模型

1.1 空間調(diào)制系統(tǒng)模型

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

圖1 空間調(diào)制系統(tǒng)的模型

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

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

(1)

式中hlt位H的第lt列.

1.2 球形譯碼算法

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

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

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

2.1 Rx-SD算法

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

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

2.2 C-SD算法

C-SD算法同時(shí)減小“發(fā)射搜索空間”和“接收搜索空間”，它只計(jì)算位于球體內(nèi)的格點(diǎn)的歐氏距離，并不斷更新搜索半徑，節(jié)省了層距的計(jì)算次數(shù). 設(shè)ΘR是位于球體內(nèi)部的發(fā)射向量的集合，C-SD可以寫成

}.

(2)

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

(3)

3 新SM-SD算法

3.1 新型實(shí)數(shù)化方式

(4)

第2Nt維

.

3.2 新SM-SD算法原理

式(3)中的各向量已經(jīng)分別轉(zhuǎn)化為實(shí)向量

(5)

圖2 采用4QAM的4×4SM系統(tǒng)的碼搜索樹

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

3.3 新SM-SD算法的步驟

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

(6)

遍歷集合φ1中的發(fā)射向量之后:

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

b)如果集合φ2為非空集，則算法結(jié)束，φ2中唯一發(fā)射向量即是發(fā)射信號(hào).

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

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

(7)

(8)

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

(9)

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

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

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

4 SM-SD算法運(yùn)算復(fù)雜度分析

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

4.1 SM-ML算法

4.2 Rx-SD算法

4.3 C-SD算法

C-SD的運(yùn)算復(fù)雜度就是計(jì)算球內(nèi)點(diǎn)集ΘR的復(fù)雜度，運(yùn)算復(fù)雜度為CC-SD=Cpre-com+Cinterval+Ccheck.

2)C-SD的計(jì)算取值區(qū)間以及檢驗(yàn)過程的運(yùn)算復(fù)雜度為

4.4 新SM-SD算法

新SM-SD算法的運(yùn)算復(fù)雜度包括：預(yù)先復(fù)雜度Cpre-com，求取值區(qū)間的復(fù)雜度Cinterval和檢驗(yàn)Θinterval內(nèi)格點(diǎn)的歐幾里得總距離的運(yùn)算復(fù)雜度Ccheck.

2) 計(jì)算取值區(qū)間和檢驗(yàn)Θinterval內(nèi)格點(diǎn)歐幾里得總距離的運(yùn)算復(fù)雜度為

解釋：

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

5 仿真結(jié)果分析

5.1 仿真設(shè)置及說明

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

5.2 誤比特率仿真

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

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

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

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

(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 發(fā)射天線數(shù)與接收天線數(shù)不相等的情況(Nt≠Nr)

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

1)若“發(fā)射搜索空間”不變，當(dāng)Nr=6和Nr=8時(shí)，新SM-SD均優(yōu)于C-SD，隨著Nr增大，Rx-SD的優(yōu)勢逐漸顯現(xiàn)，而新SM-SD相對于C-SD的優(yōu)勢減小，這是由于新SM-SD中QR分解的運(yùn)算復(fù)雜度受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)若“接收搜索空間”不變，當(dāng)m增加，即頻譜效率增加時(shí)，新SM-SD和C-SD的運(yùn)算復(fù)雜度會(huì)降低，且新SM-SD始終優(yōu)于C-SD，并在m=6時(shí)優(yōu)于Rx-SD. 相比于SM-ML，m=6時(shí)的運(yùn)算復(fù)雜度減少效果比m=4時(shí)提升了將近20%. 因此，新SM-SD算法更加適合于檢測空間調(diào)制信號(hào).

6 結(jié) 語

本文提出一種具有新型實(shí)數(shù)化變換方式的新SM-SD算法，實(shí)發(fā)射向量中的兩維非零元素的位置相鄰，且檢測時(shí)相鄰的兩層互不影響，降低了運(yùn)算復(fù)雜度. 理論上分析了新SM-SD算法的運(yùn)算復(fù)雜度，在不同的SM系統(tǒng)中對新SM-SD算法的誤比特性能和運(yùn)算復(fù)雜度進(jìn)行仿真，并與已有的SM-SD算法相比較. 理論分析和仿真結(jié)果表明：新SM-SD算法在一定條件下可以降低運(yùn)算復(fù)雜度，同時(shí)保持了與ML相同的誤比特性能，尤其在多數(shù)情況下優(yōu)于C-SD. 在“發(fā)射搜索空間”較大，Nr不是很大的情況下，新SM-SD算法降低運(yùn)算復(fù)雜度的效果十分理想，明顯優(yōu)于C-SD和Rx-SD；在某些“接收搜索空間”較大的情況下，高信噪比時(shí)新SM-SD也會(huì)優(yōu)于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] 張文彬, 王孝, 陶晨嵩,等. 采用格基規(guī)約算法的空間調(diào)制檢測方案[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 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期論文“纖維素/氧化硅有機(jī)-無機(jī)雜化復(fù)合氣凝膠的研究進(jìn)展”，是哈爾濱工業(yè)大學(xué)特種環(huán)境復(fù)合材料技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室何飛副教授制作完成的纖維素/氧化硅有機(jī)-無機(jī)雜化復(fù)合氣凝膠的溶液浸漬法流程示意圖展示. 將具有生物材料特征的有機(jī)纖維素材料作為多孔模板或增強(qiáng)，采用原位溶液浸漬法，經(jīng)溶膠-凝膠和干燥過程，可獲得具有高比表面積和納米孔結(jié)構(gòu)特征的纖維素/氧化硅復(fù)合氣凝膠. 在研究中，通過選用不同類型的纖維素和氧化硅先驅(qū)體，借助于先驅(qū)體提供的不同官能團(tuán)作用，可賦予纖維素/氧化硅有機(jī)-無機(jī)雜化復(fù)合氣凝膠多種特殊性質(zhì)，使該類材料在保持氣凝膠獨(dú)特的低密度、高孔隙率、高比表面積和低熱導(dǎo)率等結(jié)構(gòu)與性能特點(diǎn)的同時(shí)，還在一定程度上改變和提高材料在力學(xué)、疏水、光學(xué)以及耐熱性等方面的性能，因而，在隔熱、生物、醫(yī)學(xué)、吸附、包裝、光學(xué)等多種領(lǐng)域具有廣泛的應(yīng)用前景和研究價(jià)值.

(圖文提供：何飛，駱金，李亞，方旻翰，赫曉東. 哈爾濱工業(yè)大學(xué)特種環(huán)境復(fù)合材料技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室)

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

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助(HIT.MKSTISP.201613)

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

張文彬，zwbgxy1973@hit.edu.cn

TN911.3

A

0367-6234(2017)05-0022-09