李揚(yáng) 金小萍 蘇春燕

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

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

中圖分類號(hào)：TN911 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2015）06（a）-0000-00

1、引言

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

2、樹形搜索思想

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

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

圖1樹形檢測(cè)過程模型圖

3、樹形檢測(cè)算法

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

3.1、搜索策略

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

3.2、樹枝的裁剪

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

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

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

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

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

4、總結(jié)

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

參考文獻(xiàn)

[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]李穎， 魏急波， 王欣等. 酉空時(shí)調(diào)制系統(tǒng)中基于球形譯碼的多符號(hào)差分檢測(cè)算法[J]. 中國(guó)科學(xué)（信息科學(xué)）， 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.