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

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

關(guān)鍵詞：低復(fù)雜度，樹(shù)形搜索策略，樹(shù)形檢測(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ǔ)音業(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ì)樹(shù)形檢測(cè)算法思想進(jìn)行闡述，分析其優(yōu)劣勢(shì)，在各類算法之間進(jìn)行多維度的對(duì)比，提出未來(lái)針對(duì)樹(shù)形檢測(cè)算法的研究方向。

2、樹(shù)形搜索思想

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

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

圖1樹(shù)形檢測(cè)過(guò)程模型圖

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

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

3.1、搜索策略

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

3.2、樹(shù)枝的裁剪

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

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

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

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

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

4、總結(jié)

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