李揚 金小萍 蘇春燕

摘 要：如今移動通信業(yè)務(wù)對高速度高精度的通信數(shù)據(jù)傳輸?shù)囊?，促進了學者們對各類通信數(shù)據(jù)信息檢測算法的研究。本文從整體上介紹了各類樹形搜索策略的檢測思想及其代表算法，按照樹形搜索策略的不同分成窮搜索，深度優(yōu)先搜索，寬度優(yōu)先搜索和度量值優(yōu)先搜索四類，列舉了各類搜索策略的典型算法，分析了它們的優(yōu)勢和缺點，列舉出針對這些缺點拓展出的研究現(xiàn)狀，并對現(xiàn)狀和問題進行總結(jié)，提出了在后續(xù)針對樹形檢測算法進一步優(yōu)化的研究方向。

關(guān)鍵詞：低復(fù)雜度，樹形搜索策略，樹形檢測算法

中圖分類號：TN911 文獻標識碼：A 文章編號：1672-3791（2015）06（a）-0000-00

1、引言

現(xiàn)如今，消費者們對移動通信業(yè)務(wù)的使用已經(jīng)不僅僅滿足于對語音業(yè)務(wù)的需求，對互聯(lián)網(wǎng)，多媒體以及視屏通話等業(yè)務(wù)的需求變得與日俱增?；诖四壳罢谘芯慨斍昂拖乱淮囊苿油ㄐ?，即B3G、4G、5G等系統(tǒng)的關(guān)鍵技術(shù)。其中MIMO（多輸入多輸出）是提高系統(tǒng)傳輸效率的關(guān)鍵技術(shù)之一，已被廣泛應(yīng)用于各個系統(tǒng)當中。而低復(fù)雜度的檢測技術(shù)是MIMO系統(tǒng)核心技術(shù)之一，成為近幾年學者們研究的一個重點。本文就針對這些研究，將諸多的檢測算法進行分類和介紹，并主要針對樹形檢測算法思想進行闡述，分析其優(yōu)劣勢，在各類算法之間進行多維度的對比，提出未來針對樹形檢測算法的研究方向。

2、樹形搜索思想

在各類的檢測算法中，通常按照處理方式的不同將檢測方式分為線性和非線性，其中線性檢測算法計算原理簡單，但是檢測譯碼性能較差。而非線性檢測算法中，最大似然算法（ML）屬于性能最優(yōu)的算法，但是過高的計算復(fù)雜度問題使得該算法很難在實際中應(yīng)用，進而提出了諸如深度優(yōu)先，寬度優(yōu)先，度量值優(yōu)先等一系列擁有較低復(fù)雜度的性能次優(yōu)的檢測算法。

經(jīng)研究發(fā)現(xiàn)，在這些非線性檢測算法中有一個共性，就是可以用樹的模型來詮釋它們的思想，如圖1所示，圖中M表示采取的調(diào)制階數(shù)，根節(jié)點表示搜索起始節(jié)點，各分支節(jié)點表示調(diào)制星座點。多天線信道模型通過QR分解等數(shù)學推導，可以將接收端檢測判決公式的抽象表達式轉(zhuǎn)化成上三角矩陣的形式，然后通過樹枝長短來表示度量值的大小，樹的層數(shù)表示搜索的順序，樹的節(jié)點數(shù)表示復(fù)雜度等，從而將上述各種檢測算法問題提煉成樹形檢測算法的問題來研究。因此將多天線系統(tǒng)各種檢測算法的研究，統(tǒng)一到樹形檢測算法的研究上來，能更好的改進或者設(shè)計新的低復(fù)雜度檢測算法；也為多天線系統(tǒng)在未來先進通信系統(tǒng)的使用，以及硬件實現(xiàn)等方面提供一個更易實現(xiàn)的途徑。因此研究低復(fù)雜度樹形檢測算法具有重要的理論意義和工程應(yīng)用價值。

圖1樹形檢測過程模型圖

3、樹形檢測算法

出于對現(xiàn)有檢測算法轉(zhuǎn)化成樹形檢測算法思想的考慮，將現(xiàn)有算法根據(jù)節(jié)點選擇方式的不同，歸類搜索順序和樹枝裁剪兩大類，不同的搜索順序和裁剪方法都會造成不同的性能和復(fù)雜度。因此對樹形檢測算法的研究，能很好實現(xiàn)兩方面的平衡。

3.1、搜索策略

根據(jù)目前對于樹形檢測算法的研究結(jié)果，可以將它們按照不同的樹形搜索策略，分為以下四類：第一類是窮搜索策略，典型的代表為ML檢測算法，該算法搜索對比所有的分支，所以在譯碼性能上是最好的，但是窮搜索也意味著大量的計算量，使其很難在實際中應(yīng)用；第二類是深度優(yōu)先的樹形檢測策略[1-2]，此類算法首先沿著樹檢測層的深度方向進行搜索，一直到找到一條完整的分支路徑，然后再返回訪問之前一層的樹檢測層中的其他分支節(jié)點，完成其它分支路徑的檢測。該算法的譯碼性能接近ML算法，但是不斷進行的返溯運算使其在復(fù)雜度上并沒有太多的優(yōu)勢；第三類是度量值優(yōu)先的樹形檢測策略[3-5]，優(yōu)先對各分支節(jié)點中度量值最小的節(jié)點進行搜索訪問，在復(fù)雜度的降低方面有著較為明顯的優(yōu)勢，但是依然需要在各樹層之間進行多次的返溯運算；第四類是寬度優(yōu)先的樹形檢測策略[5-8]，如寬度優(yōu)先球形譯碼算法，K-best算法[5]，BID算法[6-7]，M-BID算法[8]等，此類算法通過固定的半徑寬度來限制每層被搜索到的分支節(jié)點數(shù)目，該算法具有較為穩(wěn)定的吞吐量，但也可能會帶來最佳分支路徑的分支節(jié)點被刪除的情況，造成譯碼錯誤。

3.2、樹枝的裁剪

關(guān)于樹枝的裁剪，通常采用的方法是利用半徑和概率的限制來進行裁剪。這類樹枝裁減思想在球形譯碼中較為常見，目前存在兩個著名的策略：基于噪聲統(tǒng)計的半徑選擇[7-8]，這是個固定半徑選擇方法，不夠靈活；在任意大的初始半徑的基礎(chǔ)上動態(tài)調(diào)整半徑，這種方法目前使用的比較多，但缺點是半徑過于松散，特別在低信噪比下網(wǎng)格點很密集的場合。對此W. Zhao[9]進行了改進，通過在搜索失敗時重復(fù)計算不完全樹的平均路徑度量值信息，來找到最有可能的路徑。文獻[10]中提出了IRA算法，在樹的每一層增加了一個概率的限制。然而這種刪除會使得在低層的半徑限制下出現(xiàn)無解的情況。對此文獻[11]提出了基于概率樹形裁剪的球形譯碼，它通過在球形限制的基礎(chǔ)上再增加了噪聲概率的限制，并結(jié)合動態(tài)半徑調(diào)整，以便進一步減少計算復(fù)雜度[12]。文獻[13]中提出一種基于概率分布的裁剪算法（SPSD），能在不同的網(wǎng)絡(luò)結(jié)構(gòu)中得到普遍應(yīng)用，并且引申出的五種裁剪算法均能在復(fù)雜度與性能相較傳統(tǒng)算法得到明顯的改善。

通過對研究現(xiàn)狀的分析得知，目前針對樹形檢測的研究主要集中在復(fù)雜度、性能、搜索速度等方面的優(yōu)化上，不同的搜索和裁減策略通過節(jié)點的搜索順序、半徑和概率的限制等多種方式來達到降低算法復(fù)雜度，提升譯碼性能的目的，而且也獲得了很多研究成果，但是還存在著以下問題：

1）結(jié)合概率思想的算法不夠豐富。由現(xiàn)狀分析得出，結(jié)合概率思想的多為球形譯碼算法，體現(xiàn)在對半徑的設(shè)定和半徑內(nèi)節(jié)點的篩選上，與其他搜索策略的結(jié)合略少。因此，將概率思想引入到更多的樹形搜索策略中可以作為未來研究的重要方向之一。

2）在樹形的裁剪算法中，主要針對的是深度優(yōu)先的檢測方法，而如何將這種思想運用于寬度優(yōu)先和度量值優(yōu)先的檢測算法中，并且把算法進行一般化，還沒有很好的研究。

3）當前大多性能優(yōu)良的算法都是基于已知信道信息基礎(chǔ)上的，如何把這種思想進行提煉，運用到未知信道信息的多天線系統(tǒng)中，進一步加深和拓展樹形檢測算法的研究。

4、總結(jié)

本文從檢測背景，策略，算法以及存在問題等多個方面詳細的介紹了樹形檢測算法，羅列了多種先進的低復(fù)雜度樹形檢測算的優(yōu)缺點，并針對研究中還存在的問題提出了3點需要進一步進行研究的方向，為低復(fù)雜度樹形檢測算法的研究提供了必要的資料。

參考文獻

[1]Jaeseok Lee， Byonghyo Shim. Soft Output list sphere detection with a probabilistic radius tightening[J]. IEEE Transactions on Wireless Commun.， 2008， 11（8）： 2848-2857.

[2]Volker Pauli， Lutz Lampe. Multiple Symbol differential sphere decoding for unitary space-time modulation[J]. IEEE Globecom， 2005， 3： 1630-1635.

[3]李穎， 魏急波， 王欣等. 酉空時調(diào)制系統(tǒng)中基于球形譯碼的多符號差分檢測算法[J]. 中國科學（信息科學）， 2009， 39（5）： 569-578.

[4]Peng Li. Adaptive decision-feedback detection with constellation constraints for MIMO systems[J]. IEEE Transactions on Vehicular Technology， 2012， 61（2）： 853-859.

[5]Ran Xu， Kocak T. High throughput parallel Fano decoding[J]. IEEE Transactions on Communications， 2011， 59（9）： 2394-2405.

[6]Tae-Hwan Kim， In-Cheol Park. Small-area and low-energy K-Best MIMO detector using relaxed tree expansion and early forwarding[J]. IEEE Transactions on Circuits and Systems I： Regular Papers， 2010， 57（10）： 2753-2761.

[7]Tao Cui， Chinthananda Tellambura. Bound-intersection detection for multiple symbol differential unitary space time modulation[J]. IEEE TRANSACTIONS COMMUN， 2005， 53（12）： 2114-2123.

[8]N Jin， X P Jin， Y G Ying. Multiple-symbol M-bound intersection detector for differential unitary space-time modulation[J]. IET Communications， 2010， 4（16）： 1987-1997.

[9]W Zhao， G B Giannakis. Sphere decoding algorithms with improved radius search[J]. IEEE Trans. Communications， 2005， 53（7）： 1104-1109.

[10]R Gowaikar， B Hassibi. Statistical pruning for near-maximum likelihood decoding[J]. IEEE Trans. Signal Process， 2007， 55（6）： 2661-2675.

[11]B Shim， I Kang. Sphere decoding with a probabilistic tree pruning[J]. IEEE Trans. Signal Process， 2008， 56（10）： 4867-4878.

[12]B Shim， I Kang. On further reduction of complexity in tree pruning based sphere search[J]. IEEE Trans. Communications， 2010， 58（2）： 417-422.

[13]Tao Cui， Shuangshuang Han， Chintha Tellambura. Probability- distribution based node pruning for sphere decoding[J]. IEEE Transactions on Vehicular Technology， 2013， 62（4）： 1586-1596.