吳 軍，王紹偉

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

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

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

1 系統(tǒng)模型

在一個發(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ā)送信號空間為Ω，星座點數(shù)為NΩ。將系統(tǒng)復(fù)數(shù)形態(tài)轉(zhuǎn)換為實數(shù)形態(tài)y′=H′s′+n′，并實數(shù)分解為

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

2 算法分析

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

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

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

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

2.2 改進的K－Best算法

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

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

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

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

2.2.2 改進的K－Best檢測算法流程

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

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

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

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

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

2.3 算法性能仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

［1］張建忠，李宏偉，鄧冬虎.一種低復(fù)雜度的空時分組碼檢測算法［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é)報，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信號檢測器［J］.計算機工程，2009(24):236－238.