李明浩

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

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

中圖分類號：TN92 文獻標識碼：A 文章編號：1006-1010（2014）-06-0073-04

1 引言

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

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

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

2 K-Best MIMO檢測算法

K-Best算法搜索規(guī)則是：首先確定樹中每層保留節(jié)點數(shù)K；然后從最頂層節(jié)點開始搜索，計算所有節(jié)點的累積歐氏距離度量，選擇K個具有最小累計歐氏距離度量的節(jié)點，刪減其余節(jié)點，逐層搜索至最底層節(jié)點結(jié)束?？梢娫撍阉饕?guī)則的特點是：同一層節(jié)點的搜索并行執(zhí)行，每層保留的節(jié)點數(shù)目具有確定性，不隨信道條件的變化而變化。這些特性使得該搜索規(guī)則便于高速硬件實現(xiàn)，下面以具體的數(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）是復向量，計算復雜度較高，為了避免復數(shù)運算帶來額外硬件開銷，將系統(tǒng)模型實數(shù)化分解為：

（2）

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

（3）

其中，是2N維向量，

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

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

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

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

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

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

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

3.1 整體架構(gòu)

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

3.2 K-Best模塊設計

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

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

（4）

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

（5）

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

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

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

算法 本文分組排序 標準K-Best

K-Best算法 算法

保留節(jié)點數(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ù)對比可知：本設計的檢測器排序選擇運算明顯減小，并且可以看出檢測器復雜度的降低主要來自排序選擇運算的減少。

參考文獻：

[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中的實現(xiàn)[J]. 計算機工程與應用， 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實現(xiàn)[D]. 上海： 復旦大學， 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模塊設計

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

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

（4）

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

（5）

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

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

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

算法 本文分組排序 標準K-Best

K-Best算法 算法

保留節(jié)點數(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ù)對比可知：本設計的檢測器排序選擇運算明顯減小，并且可以看出檢測器復雜度的降低主要來自排序選擇運算的減少。

參考文獻：

[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中的實現(xiàn)[J]. 計算機工程與應用， 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實現(xiàn)[D]. 上海： 復旦大學， 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模塊設計

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

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

（4）

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

（5）

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

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

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

算法 本文分組排序 標準K-Best

K-Best算法 算法

保留節(jié)點數(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ù)對比可知：本設計的檢測器排序選擇運算明顯減小，并且可以看出檢測器復雜度的降低主要來自排序選擇運算的減少。

參考文獻：

[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中的實現(xiàn)[J]. 計算機工程與應用， 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實現(xiàn)[D]. 上海： 復旦大學， 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