李明浩

目前K-Best MIMO檢測器采用的排序選擇運(yùn)算占用了大量硬件資源，使得硬件設(shè)計復(fù)雜度極高。為了在保證良好的算法性能的同時還能夠降低硬件設(shè)計復(fù)雜度，采用分組排序方式對排序選擇運(yùn)算進(jìn)行了優(yōu)化，并在現(xiàn)場可編程門陣列平臺上對4×4天線、16QAM調(diào)制方式的分組排序K-Best MIMO檢測器進(jìn)行了仿真分析。

K-Best MIMO檢測器 分組排序 FPGA

中圖分類號：TN92 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-1010（2014）-06-0073-04

1 引言

實(shí)現(xiàn)MIMO（Multiple-Input Multiple-Output，多入多出）技術(shù)的關(guān)鍵部分在于設(shè)計出低復(fù)雜度、高性能的檢測器。由于MIMO系統(tǒng)中常采用最大似然算法作為最佳硬判決檢測方法，該算法實(shí)施復(fù)雜度隨著天線數(shù)目和調(diào)制階數(shù)的增加呈指數(shù)級增大，ASIC（Application Specific Integrated Circuit，專用集成電路）或FPGA（Field-Programmable Gate Array，現(xiàn)場可編程門陣列）都只能實(shí)現(xiàn)少數(shù)目天線的低階調(diào)制方案。為了滿足MIMO系統(tǒng)逐漸增長的性能需求，又提出了一種既能夠保證BER（Bit Error Rate，誤碼率）性能又能夠降低計算復(fù)雜度的檢測算法——SD（Sphere Decoding，球形檢測）算法，該算法能夠保持與最大似然算法相媲美的BER性能，且可大幅降低計算復(fù)雜度。

SD算法主要原理是：對于一個以接收信號Y為圓心、以C為檢測半徑的多維搜索格點(diǎn)，該格點(diǎn)的度量就作為新的搜索半徑替換之前設(shè)定的半徑，通過限制搜索半徑，使得計算次數(shù)控制在一定的范圍內(nèi)，能夠有效降低運(yùn)算復(fù)雜度。根據(jù)樹形搜索方式的不同，SD算法可分為兩種不同算法：DFS（Depth First Search，深度優(yōu)先算法）與BFS（Breadth First Search，廣度優(yōu)先算法），目前常用的廣度優(yōu)先算法為K-Best搜索算法，即K-Best算法。深度優(yōu)先算法進(jìn)行單向搜索，存在反饋路徑，不利于高速硬件實(shí)現(xiàn)；K-Best算法通過對樹中每層搜索節(jié)點(diǎn)數(shù)的約束進(jìn)行并行搜索，可以利用流水線結(jié)構(gòu)提高吞吐量，便于高速硬件實(shí)現(xiàn)。

本文主要是對標(biāo)準(zhǔn)K-Best算法與分組排序K-Best算法性能進(jìn)行仿真對比，并在現(xiàn)場可編程門陣列（FPGA）Xilinx Virtex-4（XC4VLX200）平臺上實(shí)現(xiàn)了4×4天線、16QAM（Quadrature Amplitude Modulation，正交幅度調(diào)制）調(diào)制方式的分組排序K-Best檢測器的設(shè)計。

2 K-Best MIMO檢測算法

K-Best算法搜索規(guī)則是：首先確定樹中每層保留節(jié)點(diǎn)數(shù)K；然后從最頂層節(jié)點(diǎn)開始搜索，計算所有節(jié)點(diǎn)的累積歐氏距離度量，選擇K個具有最小累計歐氏距離度量的節(jié)點(diǎn)，刪減其余節(jié)點(diǎn)，逐層搜索至最底層節(jié)點(diǎn)結(jié)束?？梢娫撍阉饕?guī)則的特點(diǎn)是：同一層節(jié)點(diǎn)的搜索并行執(zhí)行，每層保留的節(jié)點(diǎn)數(shù)目具有確定性，不隨信道條件的變化而變化。這些特性使得該搜索規(guī)則便于高速硬件實(shí)現(xiàn)，下面以具體的數(shù)學(xué)公式實(shí)現(xiàn)該搜索規(guī)則。

考慮發(fā)送天線數(shù)目與接收天線數(shù)目均為N的MIMO通信系統(tǒng)基帶信號等效模型：

y=Hx+n （1）

其中，H表示MIMO通信系統(tǒng)信道的N×N信道矩陣；x=[x1，x2，…，xN]表示N維發(fā)送信號；y=[y1，y2，…，yN]表示N維接收信號；n表示N維加性高斯白噪聲。由于公式（1）是復(fù)向量，計算復(fù)雜度較高，為了避免復(fù)數(shù)運(yùn)算帶來額外硬件開銷，將系統(tǒng)模型實(shí)數(shù)化分解為：

（2）

其中，Re（*）、Im（*）分別表示復(fù)數(shù)（*）的實(shí)數(shù)部分和虛數(shù)部分；實(shí)數(shù)化的信道矩陣H～經(jīng)過QR分解得到H～=QR，采用最大似然準(zhǔn)則求解公式（1）可得：

（3）

其中，是2N維向量，

表示接收信號的實(shí)數(shù)部分；Q表示2N×2N維的正交矩陣；R表示2N×2N維的上三角矩陣。

樹形搜索過程具體是：每次計算從最高層開始，需要計算每層歐氏距離增量（INC），將每層的歐氏距離增量與上層保留的K個累積歐氏距離（PED）相加得到本層的累積歐氏距離，再通過排序操作選出本層保留的K個最小累積歐氏距離及其對應(yīng)節(jié)點(diǎn)（也稱幸存節(jié)點(diǎn)）。對于調(diào)制階數(shù)為M的K-Best檢測器樹搜索結(jié)構(gòu)，每層需計算、排序的PED的數(shù)量為，隨著K與M的增大，整個搜索過程的計算復(fù)雜度呈指數(shù)增長，導(dǎo)致硬件難以實(shí)現(xiàn)。

在標(biāo)準(zhǔn)的K-Best算法中取平方作為歐氏距離增量度量，在本文設(shè)計中取絕對值作為歐氏距離增量度量，以絕對值代替平方運(yùn)算，不僅僅能夠減少平方運(yùn)算，而且歐氏距離增量的最大值大大減少，硬件實(shí)現(xiàn)處理的數(shù)據(jù)位寬將減小，硬件資源消耗也會大大減少。

為了降低硬件實(shí)現(xiàn)復(fù)雜度，本文采用分組排序的K-Best算法，并在平坦衰落信道模型下對4×4天線、16QAM調(diào)制、無線信道編碼的點(diǎn)對點(diǎn)MIMO鏈路進(jìn)行了仿真，其仿真結(jié)果如圖1揭示的4×4天線16QAM調(diào)制方式分組排序K-Best算法BER性能所示。

本文設(shè)計中FPGA采用定點(diǎn)計算，具體結(jié)果如圖2揭示的16QAM調(diào)制分組排序K-Best算法定點(diǎn)BER性能所示。

從圖2可以看出，接收數(shù)據(jù)采取8位小數(shù)量化、歐氏距離采取6位小數(shù)量化，即達(dá)到與浮點(diǎn)算法性能相近的BER性能。

3 分組排序K-Best MIMO檢測器架構(gòu)設(shè)計

3.1 整體架構(gòu)

基于上述分組排序K-Best算法，本文設(shè)計了可配置分組排序K-Best MIMO檢測器，具體如圖3揭示了一個典型的采用全并行流水線結(jié)構(gòu)的分組排序K-Best MIMO檢測器所示，包括：QR分解模塊、均衡模塊、待選生成模塊、8層K-Best模塊和最終判決模塊。endprint

3.2 K-Best模塊設(shè)計

K-Best模塊是K-Best檢測器的核心模塊，該模塊的處理原理具體包括以下步驟：

步驟1：按照公式（4）計算第l層K×4個歐氏距離增量incl（xl）。

（4）

步驟2：按照公式（5）計算第l層K×4個累積歐氏距離PEDl（xl）。

（5）

步驟3：對步驟2計算得到的所有累積歐氏距離進(jìn)行排序，選擇出第l層最小的K個累積歐氏距離及其對應(yīng)的保留節(jié)點(diǎn)。

（6）

步驟4：l從最高層開始逐次遞減1，回到步驟1重新開始計算直至l=1。

步驟5：從第1層的K個選出最小PED及其對應(yīng)節(jié)點(diǎn)作為檢測結(jié)果輸出。

K-Best算法中各檢測層均需多次計算R×Z。其中，R表示信道矩陣H經(jīng)QR分解得到的上三角矩陣；Z表示樹形搜索圖節(jié)點(diǎn)集合，本文設(shè)計中的待選生成模塊采用文獻(xiàn)[3]中提出的待選生成方法，在各節(jié)點(diǎn)歐氏距離增量計算之前生成R×Z集合，避免了R×Z的反復(fù)計算，減少了硬件資源消耗。其中，第7層和第8層的K-Best計算均采用標(biāo)準(zhǔn)冒泡排序，第6層至第l層的K-Best計算均采用分組排序以降低硬件資源消耗。本文采用的分組排序首先將擴(kuò)展后16個子節(jié)點(diǎn)分為4組，每組排序選擇最小的2個，然后再對得到的8個節(jié)點(diǎn)排序選出最小的4個。

4 分組排序K-Best MIMO

檢測器性能分析

為了驗證設(shè)計的分組排序K-Best檢測器具有較低的硬件實(shí)現(xiàn)復(fù)雜度，筆者利用Xilinx Virtex-4（XC4VLX200）平臺對提出的結(jié)構(gòu)進(jìn)行了驗證仿真。該檢測器的驗證仿真平臺主要由一塊Xilinx Virtex-4（XC4VLX200）FPGA芯片和一臺PC機(jī)組成，硬件仿真平臺的結(jié)構(gòu)如圖4所示，該平臺采用的系統(tǒng)頻率是50MHz。

圖4 硬件仿真平臺示意圖

整個測試過程具體是：首先在PC機(jī)上由Matlab產(chǎn)生消息序列，經(jīng)過數(shù)字調(diào)制過信道加噪聲后量化為定點(diǎn)數(shù)據(jù)；然后采用定點(diǎn)數(shù)據(jù)（包括消息序列和過信道加噪聲數(shù)據(jù)）初始化RAM；最后進(jìn)行FPGA在線編程并將FPGA仿真結(jié)果與輸入消息序列進(jìn)行對比，通過在線調(diào)試軟件Chipscope將結(jié)果輸出給PC機(jī)顯示。測試結(jié)果表明，檢測器具有與Matlab定點(diǎn)仿真相同的BER性能。

采用本文設(shè)計的4×4天線、16QAM調(diào)制方式MIMO檢測器與采用標(biāo)準(zhǔn)K-Best算法設(shè)計的檢測器的主要性能參數(shù)如表1所示：

表1 4×4天線16QAM調(diào)制MIMO信號檢測器性能參數(shù)

算法 本文分組排序 標(biāo)準(zhǔn)K-Best

K-Best算法 算法

保留節(jié)點(diǎn)數(shù) K=4 K=4

天線數(shù) 4×4 4×4

調(diào)制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發(fā)器 15 505 18 198

4輸入查找表 21 938 23 951

這兩種檢測器除了排序選擇方式不同，優(yōu)化策略以及量化精度均采用相同方式，通過表1中的邏輯片、觸發(fā)器、4輸入查找表中的參數(shù)對比可知：本設(shè)計的檢測器排序選擇運(yùn)算明顯減小，并且可以看出檢測器復(fù)雜度的降低主要來自排序選擇運(yùn)算的減少。

參考文獻(xiàn)：

[1] Damen O， Chkeif A， Belfiore J-C. Lattice Code Decoder for Space-Time Codes[J]. IEEE Communications Letters， 2000，4（5）： 161-163.

[2] U Finke， M Pohst. Improved Methods for Calculating Vectors of Short Length in a Lattice， Including a Complexity Analysis[J]. Mathematics of Compuation， 1985，44： 463-471.

[3] 馬計，王海紅，王欣. 排序QR分解MIMO檢測器在FPGA中的實(shí)現(xiàn)[J]. 計算機(jī)工程與應(yīng)用， 2011，47（32）： 75-77.

[4] Burg A， Borgmann M， Wenk M， et al. VLSI Implementation of MIMO Detection Using the Sphere Decoding Algorithm[J]. IEEE Journal of Solid-State Circuits， 2005，40（7）： 1566-1577.

[5] 馬小晶. MIMO-OFDM系統(tǒng)信號檢測技術(shù)研究及VLSI實(shí)現(xiàn)[D]. 上海： 復(fù)旦大學(xué)， 2009.

[6] Raghu Mysore Rao， Helen Tarn， Raied Mazahreh， et al. A Low Complexity Square Root MMSE MIMO Decoder[C]. IEEE Transactions on ASILOMAR， 2010： 1463-1467.★endprint

3.2 K-Best模塊設(shè)計

K-Best模塊是K-Best檢測器的核心模塊，該模塊的處理原理具體包括以下步驟：

步驟1：按照公式（4）計算第l層K×4個歐氏距離增量incl（xl）。

（4）

步驟2：按照公式（5）計算第l層K×4個累積歐氏距離PEDl（xl）。

（5）

步驟3：對步驟2計算得到的所有累積歐氏距離進(jìn)行排序，選擇出第l層最小的K個累積歐氏距離及其對應(yīng)的保留節(jié)點(diǎn)。

（6）

步驟4：l從最高層開始逐次遞減1，回到步驟1重新開始計算直至l=1。

步驟5：從第1層的K個選出最小PED及其對應(yīng)節(jié)點(diǎn)作為檢測結(jié)果輸出。

K-Best算法中各檢測層均需多次計算R×Z。其中，R表示信道矩陣H經(jīng)QR分解得到的上三角矩陣；Z表示樹形搜索圖節(jié)點(diǎn)集合，本文設(shè)計中的待選生成模塊采用文獻(xiàn)[3]中提出的待選生成方法，在各節(jié)點(diǎn)歐氏距離增量計算之前生成R×Z集合，避免了R×Z的反復(fù)計算，減少了硬件資源消耗。其中，第7層和第8層的K-Best計算均采用標(biāo)準(zhǔn)冒泡排序，第6層至第l層的K-Best計算均采用分組排序以降低硬件資源消耗。本文采用的分組排序首先將擴(kuò)展后16個子節(jié)點(diǎn)分為4組，每組排序選擇最小的2個，然后再對得到的8個節(jié)點(diǎn)排序選出最小的4個。

4 分組排序K-Best MIMO

檢測器性能分析

為了驗證設(shè)計的分組排序K-Best檢測器具有較低的硬件實(shí)現(xiàn)復(fù)雜度，筆者利用Xilinx Virtex-4（XC4VLX200）平臺對提出的結(jié)構(gòu)進(jìn)行了驗證仿真。該檢測器的驗證仿真平臺主要由一塊Xilinx Virtex-4（XC4VLX200）FPGA芯片和一臺PC機(jī)組成，硬件仿真平臺的結(jié)構(gòu)如圖4所示，該平臺采用的系統(tǒng)頻率是50MHz。

圖4 硬件仿真平臺示意圖

整個測試過程具體是：首先在PC機(jī)上由Matlab產(chǎn)生消息序列，經(jīng)過數(shù)字調(diào)制過信道加噪聲后量化為定點(diǎn)數(shù)據(jù)；然后采用定點(diǎn)數(shù)據(jù)（包括消息序列和過信道加噪聲數(shù)據(jù)）初始化RAM；最后進(jìn)行FPGA在線編程并將FPGA仿真結(jié)果與輸入消息序列進(jìn)行對比，通過在線調(diào)試軟件Chipscope將結(jié)果輸出給PC機(jī)顯示。測試結(jié)果表明，檢測器具有與Matlab定點(diǎn)仿真相同的BER性能。

采用本文設(shè)計的4×4天線、16QAM調(diào)制方式MIMO檢測器與采用標(biāo)準(zhǔn)K-Best算法設(shè)計的檢測器的主要性能參數(shù)如表1所示：

表1 4×4天線16QAM調(diào)制MIMO信號檢測器性能參數(shù)

算法 本文分組排序 標(biāo)準(zhǔn)K-Best

K-Best算法 算法

保留節(jié)點(diǎn)數(shù) K=4 K=4

天線數(shù) 4×4 4×4

調(diào)制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發(fā)器 15 505 18 198

4輸入查找表 21 938 23 951

這兩種檢測器除了排序選擇方式不同，優(yōu)化策略以及量化精度均采用相同方式，通過表1中的邏輯片、觸發(fā)器、4輸入查找表中的參數(shù)對比可知：本設(shè)計的檢測器排序選擇運(yùn)算明顯減小，并且可以看出檢測器復(fù)雜度的降低主要來自排序選擇運(yùn)算的減少。

參考文獻(xiàn)：

[1] Damen O， Chkeif A， Belfiore J-C. Lattice Code Decoder for Space-Time Codes[J]. IEEE Communications Letters， 2000，4（5）： 161-163.

[2] U Finke， M Pohst. Improved Methods for Calculating Vectors of Short Length in a Lattice， Including a Complexity Analysis[J]. Mathematics of Compuation， 1985，44： 463-471.

[3] 馬計，王海紅，王欣. 排序QR分解MIMO檢測器在FPGA中的實(shí)現(xiàn)[J]. 計算機(jī)工程與應(yīng)用， 2011，47（32）： 75-77.

[4] Burg A， Borgmann M， Wenk M， et al. VLSI Implementation of MIMO Detection Using the Sphere Decoding Algorithm[J]. IEEE Journal of Solid-State Circuits， 2005，40（7）： 1566-1577.

[5] 馬小晶. MIMO-OFDM系統(tǒng)信號檢測技術(shù)研究及VLSI實(shí)現(xiàn)[D]. 上海： 復(fù)旦大學(xué)， 2009.

[6] Raghu Mysore Rao， Helen Tarn， Raied Mazahreh， et al. A Low Complexity Square Root MMSE MIMO Decoder[C]. IEEE Transactions on ASILOMAR， 2010： 1463-1467.★endprint

3.2 K-Best模塊設(shè)計

K-Best模塊是K-Best檢測器的核心模塊，該模塊的處理原理具體包括以下步驟：

步驟1：按照公式（4）計算第l層K×4個歐氏距離增量incl（xl）。

（4）

步驟2：按照公式（5）計算第l層K×4個累積歐氏距離PEDl（xl）。

（5）

步驟3：對步驟2計算得到的所有累積歐氏距離進(jìn)行排序，選擇出第l層最小的K個累積歐氏距離及其對應(yīng)的保留節(jié)點(diǎn)。

（6）

步驟4：l從最高層開始逐次遞減1，回到步驟1重新開始計算直至l=1。

步驟5：從第1層的K個選出最小PED及其對應(yīng)節(jié)點(diǎn)作為檢測結(jié)果輸出。

K-Best算法中各檢測層均需多次計算R×Z。其中，R表示信道矩陣H經(jīng)QR分解得到的上三角矩陣；Z表示樹形搜索圖節(jié)點(diǎn)集合，本文設(shè)計中的待選生成模塊采用文獻(xiàn)[3]中提出的待選生成方法，在各節(jié)點(diǎn)歐氏距離增量計算之前生成R×Z集合，避免了R×Z的反復(fù)計算，減少了硬件資源消耗。其中，第7層和第8層的K-Best計算均采用標(biāo)準(zhǔn)冒泡排序，第6層至第l層的K-Best計算均采用分組排序以降低硬件資源消耗。本文采用的分組排序首先將擴(kuò)展后16個子節(jié)點(diǎn)分為4組，每組排序選擇最小的2個，然后再對得到的8個節(jié)點(diǎn)排序選出最小的4個。

4 分組排序K-Best MIMO

檢測器性能分析

為了驗證設(shè)計的分組排序K-Best檢測器具有較低的硬件實(shí)現(xiàn)復(fù)雜度，筆者利用Xilinx Virtex-4（XC4VLX200）平臺對提出的結(jié)構(gòu)進(jìn)行了驗證仿真。該檢測器的驗證仿真平臺主要由一塊Xilinx Virtex-4（XC4VLX200）FPGA芯片和一臺PC機(jī)組成，硬件仿真平臺的結(jié)構(gòu)如圖4所示，該平臺采用的系統(tǒng)頻率是50MHz。

圖4 硬件仿真平臺示意圖

整個測試過程具體是：首先在PC機(jī)上由Matlab產(chǎn)生消息序列，經(jīng)過數(shù)字調(diào)制過信道加噪聲后量化為定點(diǎn)數(shù)據(jù)；然后采用定點(diǎn)數(shù)據(jù)（包括消息序列和過信道加噪聲數(shù)據(jù)）初始化RAM；最后進(jìn)行FPGA在線編程并將FPGA仿真結(jié)果與輸入消息序列進(jìn)行對比，通過在線調(diào)試軟件Chipscope將結(jié)果輸出給PC機(jī)顯示。測試結(jié)果表明，檢測器具有與Matlab定點(diǎn)仿真相同的BER性能。

采用本文設(shè)計的4×4天線、16QAM調(diào)制方式MIMO檢測器與采用標(biāo)準(zhǔn)K-Best算法設(shè)計的檢測器的主要性能參數(shù)如表1所示：

表1 4×4天線16QAM調(diào)制MIMO信號檢測器性能參數(shù)

算法 本文分組排序 標(biāo)準(zhǔn)K-Best

K-Best算法 算法

保留節(jié)點(diǎn)數(shù) K=4 K=4

天線數(shù) 4×4 4×4

調(diào)制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發(fā)器 15 505 18 198

4輸入查找表 21 938 23 951

這兩種檢測器除了排序選擇方式不同，優(yōu)化策略以及量化精度均采用相同方式，通過表1中的邏輯片、觸發(fā)器、4輸入查找表中的參數(shù)對比可知：本設(shè)計的檢測器排序選擇運(yùn)算明顯減小，并且可以看出檢測器復(fù)雜度的降低主要來自排序選擇運(yùn)算的減少。

參考文獻(xiàn)：

[1] Damen O， Chkeif A， Belfiore J-C. Lattice Code Decoder for Space-Time Codes[J]. IEEE Communications Letters， 2000，4（5）： 161-163.

[2] U Finke， M Pohst. Improved Methods for Calculating Vectors of Short Length in a Lattice， Including a Complexity Analysis[J]. Mathematics of Compuation， 1985，44： 463-471.

[3] 馬計，王海紅，王欣. 排序QR分解MIMO檢測器在FPGA中的實(shí)現(xiàn)[J]. 計算機(jī)工程與應(yīng)用， 2011，47（32）： 75-77.

[4] Burg A， Borgmann M， Wenk M， et al. VLSI Implementation of MIMO Detection Using the Sphere Decoding Algorithm[J]. IEEE Journal of Solid-State Circuits， 2005，40（7）： 1566-1577.

[5] 馬小晶. MIMO-OFDM系統(tǒng)信號檢測技術(shù)研究及VLSI實(shí)現(xiàn)[D]. 上海： 復(fù)旦大學(xué)， 2009.

[6] Raghu Mysore Rao， Helen Tarn， Raied Mazahreh， et al. A Low Complexity Square Root MMSE MIMO Decoder[C]. IEEE Transactions on ASILOMAR， 2010： 1463-1467.★endprint