4×4天線分組排序K—Best MIMO檢測器設計

李明浩

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

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

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

1 引言

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

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

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

2 K-Best MIMO檢測算法

K-Best算法搜索規則是：首先確定樹中每層保留節點數K；然后從最頂層節點開始搜索，計算所有節點的累積歐氏距離度量，選擇K個具有最小累計歐氏距離度量的節點，刪減其余節點，逐層搜索至最底層節點結束。可見該搜索規則的特點是：同一層節點的搜索并行執行，每層保留的節點數目具有確定性，不隨信道條件的變化而變化。這些特性使得該搜索規則便于高速硬件實現，下面以具體的數學公式實現該搜索規則。

考慮發送天線數目與接收天線數目均為N的MIMO通信系統基帶信號等效模型：

y=Hx+n （1）

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

（2）

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

（3）

其中，是2N維向量，

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

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

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

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

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

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

3 分組排序K-Best MIMO檢測器架構設計

3.1 整體架構

基于上述分組排序K-Best算法，本文設計了可配置分組排序K-Best MIMO檢測器，具體如圖3揭示了一個典型的采用全并行流水線結構的分組排序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個累積歐氏距離及其對應的保留節點。

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

表1 4×4天線16QAM調制MIMO信號檢測器性能參數

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

K-Best算法 算法

保留節點數 K=4 K=4

天線數 4×4 4×4

調制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發器 15 505 18 198

4輸入查找表 21 938 23 951

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

參考文獻：

[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中的實現[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系統信號檢測技術研究及VLSI實現[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個累積歐氏距離及其對應的保留節點。

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

表1 4×4天線16QAM調制MIMO信號檢測器性能參數

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

K-Best算法 算法

保留節點數 K=4 K=4

天線數 4×4 4×4

調制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發器 15 505 18 198

4輸入查找表 21 938 23 951

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

參考文獻：

[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中的實現[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系統信號檢測技術研究及VLSI實現[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個累積歐氏距離及其對應的保留節點。

（6）

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

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

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

4 分組排序K-Best MIMO

檢測器性能分析

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

圖4 硬件仿真平臺示意圖

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

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

表1 4×4天線16QAM調制MIMO信號檢測器性能參數

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

K-Best算法 算法

保留節點數 K=4 K=4

天線數 4×4 4×4

調制方式 16QAM 16QAM

邏輯片 12 866 14 701

觸發器 15 505 18 198

4輸入查找表 21 938 23 951

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

參考文獻：

[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中的實現[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系統信號檢測技術研究及VLSI實現[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