改進(jìn)的K－Best檢測(cè)算法研究及實(shí)現(xiàn)

吳 軍，王紹偉

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

多輸入多輸出(MIMO)系統(tǒng)是一個(gè)具有挑戰(zhàn)意義的研究熱點(diǎn)［1］，它可以有效地解決未來(lái)通信中信道容量緊缺的問(wèn)題。MIMO通信系統(tǒng)有很高的頻譜利用率，在一定的頻段上可以獲得很高的傳輸速率，而且理論上與MIMO的天線數(shù)成正比，在相同發(fā)射功率和傳輸帶寬下，多天線系統(tǒng)比單天線系統(tǒng)的信道容量高40多倍［2］。在MIMO系統(tǒng)中接收端的信號(hào)檢測(cè)部分是整個(gè)MIMO系統(tǒng)最重要的一部分，因?yàn)樾盘?hào)檢測(cè)部分如果可以準(zhǔn)確地檢測(cè)，那么系統(tǒng)的性能便可以大大提升，系統(tǒng)可靠度及頻譜效率也都可以獲得改善。

在MIMO檢測(cè)中，球形檢測(cè)算法是一種比特誤碼率性能接近最佳ML檢測(cè)，又能大幅降低復(fù)雜度的有效方法。目前，對(duì)MIMO系統(tǒng)的球形檢測(cè)算法研究，主要有兩種類(lèi)型，一類(lèi)是深度優(yōu)先算法，該算法可以達(dá)到與ML相同的性能，缺點(diǎn)是搜索過(guò)程中迭代次數(shù)較多，吞吐率不高且復(fù)雜度不固定，如SESD(Schnorr－Euchner SD)算法、列表球算法(LSD)。另一類(lèi)是廣度優(yōu)先算法，算法性能相對(duì)于ML有一定損失，但采用了備受歡迎的前饋結(jié)構(gòu)，具有硬件友好的特征，在檢測(cè)信號(hào)的每一層，只保留最小的K個(gè)度量值對(duì)應(yīng)的路徑來(lái)確定擴(kuò)展情況，如K－Best算法［3］。本文在深入研究球形檢測(cè)算法的基礎(chǔ)上，針對(duì)K－Best算法采用預(yù)測(cè)技術(shù)和并行排序結(jié)合的方法，在不損失性能的情況下，降低了算法的計(jì)算復(fù)雜度。提出了改進(jìn)的KBest檢測(cè)算法的流水線結(jié)構(gòu)實(shí)現(xiàn)方案，給出了QR分解的實(shí)現(xiàn)結(jié)構(gòu)。

1 系統(tǒng)模型

在一個(gè)發(fā)射天線與接收天線均為N的MIMO系統(tǒng)，信道為準(zhǔn)靜態(tài)平坦衰落，MIMO系統(tǒng)數(shù)學(xué)模型可以表示為

式中:y為N維的接收數(shù)據(jù)列向量;s為發(fā)送數(shù)據(jù)列向量;H為等效基帶信道傳輸矩陣，是N×N維的復(fù)矩陣;n為N維的理想加性復(fù)高斯白噪聲矢量，發(fā)送信號(hào)空間為Ω，星座點(diǎn)數(shù)為NΩ。將系統(tǒng)復(fù)數(shù)形態(tài)轉(zhuǎn)換為實(shí)數(shù)形態(tài)y′=H′s′+n′，并實(shí)數(shù)分解為

經(jīng)過(guò)實(shí)數(shù)分解后，復(fù)數(shù)向量和矩陣轉(zhuǎn)化為實(shí)數(shù)向量和矩陣，并且維數(shù)將是對(duì)應(yīng)復(fù)數(shù)向量和矩陣的2倍。其中，向量和矩陣的維數(shù)雖然增加了，但減少了處理單元的實(shí)現(xiàn)復(fù)雜度，從而降低了總的計(jì)算量，減少了檢測(cè)方案的硬件資源消耗。

2 算法分析

2.1 傳統(tǒng) K－Best算法

基于上述系統(tǒng)模型對(duì)信道矩陣H′進(jìn)行QR分解，則H′=QR，其中Q為2 N×2 N維正交矩陣，R為2 N×2 N維上三角陣，=QTy為2 N維向量。由式(1)，可得

則最大似然(ML)檢測(cè)公式為

傳統(tǒng)K－Best算法是由信道矩陣H′經(jīng)過(guò)QR分解后，根據(jù)最大似然檢測(cè)算法，將式(4)展開(kāi)得到

2.2 改進(jìn)的K－Best算法

傳統(tǒng)K－Best檢測(cè)算法相比于其他球形檢測(cè)算法的優(yōu)點(diǎn)是其只有正向搜索的過(guò)程，縮小了搜索空間，并且具有固定的復(fù)雜度和吞吐率，適于硬件實(shí)現(xiàn)。同時(shí)，由于傳統(tǒng)的K－Best算法的復(fù)雜度主要集中在路徑成本計(jì)算和每一層的排序操作，為了進(jìn)一步降低檢測(cè)算法的計(jì)算復(fù)雜度，本文在深入研究K－Best算法的基礎(chǔ)上，提出了預(yù)測(cè)技術(shù)和并行排序結(jié)合的改進(jìn)算法，以降低檢測(cè)算法的復(fù)雜度，使之適合硬件實(shí)現(xiàn)。

2.2.1 預(yù)測(cè)技術(shù)

預(yù)測(cè)技術(shù)其核心算法思想是改進(jìn)了SE策略［4］的實(shí)現(xiàn)方法，即在確定每層節(jié)點(diǎn)的擴(kuò)展子節(jié)點(diǎn)時(shí)，無(wú)須計(jì)算出此節(jié)點(diǎn)所有擴(kuò)展子節(jié)點(diǎn)的歐氏距離，只需要通過(guò)式(6)計(jì)算此層使PED為零的浮點(diǎn)數(shù)^si，然后確定和此^si距離最近的星座點(diǎn)來(lái)得到每層節(jié)點(diǎn)的擴(kuò)展子節(jié)點(diǎn)。

式中:NR為接收天線數(shù)目。于是將本來(lái)需要Mc個(gè)點(diǎn)的PED計(jì)算減少成1次PED計(jì)算與幾次比較選擇，因此較好地降低了檢測(cè)算法的計(jì)算復(fù)雜度［5］，從而節(jié)省了硬件實(shí)現(xiàn)的資源消耗。

2.2.2 改進(jìn)的K－Best檢測(cè)算法流程

改進(jìn)的K－Best算法的關(guān)鍵在于預(yù)測(cè)技術(shù)和并行排序的結(jié)合，首先在確定每層節(jié)點(diǎn)擴(kuò)展子節(jié)點(diǎn)的順序時(shí)采用上述預(yù)測(cè)技術(shù)大大減少了計(jì)算子節(jié)點(diǎn)PED的次數(shù)，簡(jiǎn)化了擴(kuò)展子節(jié)點(diǎn)的排序過(guò)程，從而降低了檢測(cè)算法的計(jì)算復(fù)雜度。然后再采用并行排序替代冒泡排序的方法從K個(gè)擴(kuò)展分組中選出具有K個(gè)最小PED的擴(kuò)展子節(jié)點(diǎn)作為一個(gè)子組，進(jìn)一步降低了算法的復(fù)雜度。改進(jìn)K－Best算法主要過(guò)程如下:

1)將系統(tǒng)模型轉(zhuǎn)化成實(shí)數(shù)模型，并對(duì)信道矩陣H進(jìn)行實(shí)數(shù)QR分解。

2)初始化根節(jié)點(diǎn)，由i+1層保留K個(gè)擴(kuò)展子節(jié)點(diǎn)得到第i層節(jié)點(diǎn)，從第2NT層開(kāi)始進(jìn)行檢測(cè);當(dāng)i=2NT時(shí)，該層每個(gè)節(jié)點(diǎn)擴(kuò)展得到Mc個(gè)擴(kuò)展子節(jié)點(diǎn)，采用預(yù)測(cè)技術(shù)確定第i層每個(gè)節(jié)點(diǎn)的擴(kuò)展子節(jié)點(diǎn)的順序，即保留每個(gè)節(jié)點(diǎn)的前K個(gè)擴(kuò)展子節(jié)點(diǎn)并按升序排列;在基于預(yù)測(cè)技術(shù)的方法確定K個(gè)擴(kuò)展子節(jié)點(diǎn)序列后，每一層得到K個(gè)按升序排列的節(jié)點(diǎn)分組，每個(gè)分組有K個(gè)按升序排列的擴(kuò)展子節(jié)點(diǎn)。

3)對(duì)K個(gè)按升序排列的節(jié)點(diǎn)分組，采用并行排序方法從上述K個(gè)擴(kuò)展節(jié)點(diǎn)分組中選出具有K個(gè)最小PED的擴(kuò)展子節(jié)點(diǎn)作為一個(gè)子組輸出到下一層。

4)逐層檢測(cè)，重復(fù)步驟2)和3)，直至i=1時(shí)，將具有最小PED所對(duì)應(yīng)的子組，即候選矢量^s作為最終的檢測(cè)結(jié)果。

2.3 算法性能仿真

基于上述球形檢測(cè)算法的分析、提出的預(yù)測(cè)技術(shù)以及并行排序結(jié)合的K－Best算法，本文對(duì)該檢測(cè)算法進(jìn)行了MATLAB性能仿真。圖1采用4發(fā)4收的MIMO通信系統(tǒng)，調(diào)制方式為16QAM，K=4，信道為準(zhǔn)靜態(tài)瑞利平坦衰落信道，對(duì)檢測(cè)算法進(jìn)行MATLAB仿真，比較了兩種檢測(cè)算法之間的誤碼率性能。

圖1 傳統(tǒng)K－Best算法和改進(jìn)K－Best算法性能比較

從圖1可以看出，改進(jìn)的K－Best檢測(cè)算法在降低計(jì)算復(fù)雜度的情況下與傳統(tǒng)K－Best算法性能基本一致，這說(shuō)明在保證降低算法復(fù)雜度的前提下改進(jìn)的K－Best檢測(cè)算法仍然具有較高的分集增益，滿足MIMO通信系統(tǒng)低誤碼率的設(shè)計(jì)要求。

3 算法的FPGA實(shí)現(xiàn)設(shè)計(jì)

根據(jù)算法的特點(diǎn)，由于該算法較為復(fù)雜，運(yùn)算較多，為達(dá)到速度的要求，在設(shè)計(jì)中采用流水線操作并進(jìn)行并行處理，節(jié)省了處理時(shí)間。該流水線架構(gòu)可允許在每個(gè)時(shí)鐘周期中進(jìn)行數(shù)據(jù)處理，在檢測(cè)信號(hào)的每一層，只保留最小的K個(gè)度量值對(duì)應(yīng)的路徑來(lái)確定擴(kuò)展情況。因此，檢測(cè)結(jié)構(gòu)的每級(jí)只需要一個(gè)PE單元，對(duì)該系統(tǒng)而言，PE單元的總數(shù)為8。圖2給出了該檢測(cè)算法流水線操作并行處理結(jié)構(gòu)實(shí)現(xiàn)框圖。

圖2 檢測(cè)算法流水線結(jié)構(gòu)實(shí)現(xiàn)框圖

圖2中，PE單元表示該層節(jié)點(diǎn)擴(kuò)展和子節(jié)點(diǎn)排序操作，預(yù)計(jì)算Γ是星座點(diǎn)和上三角矩陣R相乘的結(jié)果。在檢測(cè)發(fā)送信號(hào)時(shí)基于廣度優(yōu)先的準(zhǔn)則，在檢測(cè)信號(hào)的每一層，只保留最小的K個(gè)度量值對(duì)應(yīng)的路徑，搜索結(jié)束后把具有最小PED所對(duì)應(yīng)的候選矢量^s作為最終的檢測(cè)結(jié)果。在進(jìn)行PED排序并選出最小的K個(gè)路徑進(jìn)行下一次搜索時(shí)，若使用冒泡法排序，所需的比較選擇單元雖然較少，但需要消耗很多個(gè)時(shí)鐘周期，例如對(duì)于16QAM調(diào)制，K取10時(shí)，完成一次排序至少需要40個(gè)時(shí)鐘周期［6］，下一環(huán)節(jié)的PED計(jì)算單元需要等待較長(zhǎng)的時(shí)間，這意味著算法的吞吐率很低。因此，本文檢測(cè)算法采用預(yù)測(cè)技術(shù)和并行排序結(jié)合的方法，降低了計(jì)算復(fù)雜度，并采用并行流水結(jié)構(gòu)實(shí)現(xiàn)，節(jié)省了處理時(shí)間，實(shí)現(xiàn)了較高的數(shù)據(jù)吞吐量。

信道矩陣預(yù)處理單元負(fù)責(zé)對(duì)矩陣H進(jìn)行QR分解以便于檢測(cè)單元進(jìn)行排序篩選操作，下面給出了QR分解的實(shí)現(xiàn)電路結(jié)構(gòu)。

3.1 QR分解的Givens旋轉(zhuǎn)實(shí)現(xiàn)

在信道矩陣預(yù)處理過(guò)程中，主要負(fù)責(zé)對(duì)信道矩陣H進(jìn)行QR分解，本文中QR分解基于吉文斯旋轉(zhuǎn)使用一陣列電路實(shí)現(xiàn)［7］。QR分解通過(guò)一系列Givens旋轉(zhuǎn)變換得到，即Q矩陣是一系列二維旋轉(zhuǎn)矩陣的乘積。每一次旋轉(zhuǎn)將信道矩陣H的某一列中的一個(gè)非零元素變換為零，這樣反復(fù)旋轉(zhuǎn)直到信道矩陣H中剩下的非零元素全部在上三角部分，就得到了上三角矩陣R。如圖3所示，其中的六邊形和正方形模塊都表示Givens旋轉(zhuǎn)單元。六邊形單元處在第一行的最左邊位置稱為邊界單元(boundary cell)，用于產(chǎn)生Givens旋轉(zhuǎn)的半徑、正弦和余弦并存儲(chǔ)結(jié)果。正邊形單元又稱為內(nèi)部單元(interior cell)用于生成Givens變換后的向量。

圖3 QR分解電路實(shí)現(xiàn)

開(kāi)始時(shí)，所有運(yùn)算單元中的寄存器值都置零。隨著矩陣H不斷進(jìn)入寄存器中，分別由邊界單元和內(nèi)部單元計(jì)算Givens變換，并將計(jì)算結(jié)果存放于計(jì)算單元的寄存器中。

圖4a所示為邊界單元的電路結(jié)構(gòu)。設(shè)寄存器的初始值為x，輸入值為y，邊界單元設(shè)計(jì)生成吉文斯旋轉(zhuǎn)的3個(gè)值:x′=，cosθ=x/x′，sinθ=y/y′。其中x′存入x所在的寄存器，寄存器置零。邊界單元的輸出值cosθ和sinθ被放在同一行的內(nèi)部單元，用于計(jì)算Givens變換后的2維向量。內(nèi)部單元的電路如圖4b所示。內(nèi)部單元計(jì)算后將寄存器x與y中的值替換為新得到的x′和y′，其中x′作為QR分解中R矩陣的元素保留，y′將在計(jì)算下一行的Givens變換時(shí)被利用。

圖4 單元電路實(shí)現(xiàn)

3.2 硬件仿真實(shí)現(xiàn)

基于上述球形檢測(cè)算法的分析和提出的FPGA實(shí)現(xiàn)設(shè)計(jì)方案，本文對(duì)改進(jìn)的K－Best檢測(cè)算法進(jìn)行了硬件編程實(shí)現(xiàn)。該球形檢測(cè)算法采用Verilog語(yǔ)言編寫(xiě)代碼，使用ISE10.1軟件等進(jìn)行綜合、布線，并在Xilinx公司的Virtex－5系列的XC5VLX330 FPGA上完成了板級(jí)驗(yàn)證。

通過(guò)試驗(yàn)，在Virtex－5系列FPGA芯片中，按方案實(shí)現(xiàn)了4發(fā)4收16QAM系統(tǒng)的K－Best檢測(cè)算法，該算法實(shí)現(xiàn)資源消耗為使用Slice 10860個(gè)，占資源21%，使用塊RAM為102個(gè)，占總資源的25%，設(shè)計(jì)工作時(shí)鐘頻率為135 MHz。與文獻(xiàn)［8］相比，本文檢測(cè)算法實(shí)現(xiàn)資源消耗得到了有效降低，在資源開(kāi)銷(xiāo)不大的情況下，達(dá)到了較高的吞吐率。表1列舉了此MIMO球形檢測(cè)算法FPGA實(shí)現(xiàn)的資源耗用情況。

表1 K－Best檢測(cè)算法實(shí)現(xiàn)資源耗用

4 結(jié)論

本文在研究MIMO系統(tǒng)球形檢測(cè)算法的基礎(chǔ)上，針對(duì)傳統(tǒng)K－Best算法做出了改進(jìn)，給出了該檢測(cè)算法流水線操作并行處理結(jié)構(gòu)實(shí)現(xiàn)方案。改進(jìn)算法采用預(yù)測(cè)技術(shù)和并行排序相結(jié)合的方法，降低了算法復(fù)雜度，并采用并行流水線結(jié)構(gòu)實(shí)現(xiàn)，節(jié)省了處理時(shí)間。經(jīng)軟件仿真和硬件實(shí)現(xiàn)表明，該檢測(cè)算法在性能損失不大的情況下降低了算法的計(jì)算復(fù)雜度，減少了硬件資源消耗，硬件實(shí)現(xiàn)的性能與理論性能接近，驗(yàn)證了實(shí)現(xiàn)方案的正確性和有效性。

［1］張建忠，李宏偉，鄧冬虎.一種低復(fù)雜度的空時(shí)分組碼檢測(cè)算法［J］.電視技術(shù)，2011，35(2):67－68.

［2］FOSCHINI G J.Layered space－time architecture for wireless communication in fading environment when using multiple antennas［J］.Bell Labs Technical Journal，1996，1(2):41－59.

［3］LI Qingwei，WANG Zhongfeng.Improved K－Best sphere decoding algorithms for MIMO system［C］//Proc.2006 IEEE International Symposium on Circuits and Systems.［S.l.］:IEEE Press，2006:110－113.

［4］林云，王宇.MIMO系統(tǒng)K－Best球形譯碼算法研究［J］.電波科學(xué)學(xué)報(bào)，2009(1):141－145.

［5］BURG A，BORGMANN M，SIMON C.Performance tradeoffs in the VLSI implementation of the sphere decoding algorithm［C］//Proc.IEEE 3G Mobile Communication Conf.［S.l.］:IEEE Press，2004:93－97.

［6］GENTLEMAN W M，KUNG H T.Matrix triangularization by systolic arrays［J］.Real－time signal processing，1981，298(5):19－26.

［7］DICK C，AMIRI K，CAVALLARO J R.Design and architecture of spatial multiplexing MIMO decoders for FPGAs［C］//Proc.42nd Asilomar Conference on Signals，Systems and Computers.［S.l.］:IEEE Press，2008:160－164.

［8］馬小晶，劉亮，葉凡，等.基于可配置型K－Best的MIMO信號(hào)檢測(cè)器［J］.計(jì)算機(jī)工程，2009(24):236－238.