基于Systolic陣的IQRD-SMI算法的研究與FPGA優(yōu)化實(shí)現(xiàn)

劉禹韜，包志強(qiáng)，李龍龍，蘇子昊

(西安郵電大學(xué)，西安　710061)

?

基于Systolic陣的IQRD-SMI算法的研究與FPGA優(yōu)化實(shí)現(xiàn)

劉禹韜，包志強(qiáng)，李龍龍，蘇子昊

(西安郵電大學(xué)，西安710061)

摘要：針對自適應(yīng)波束形成系統(tǒng)中權(quán)值求解計算量大的問題，研究了基于LCMV的逆QR分解算法(IQRD-SMI算法) 及其傳統(tǒng)脈動流水的GR-TSA實(shí)現(xiàn)結(jié)構(gòu)，在Matlab中對算法以脈動陣搭建并進(jìn)行算法仿真；分析了CORDIC技術(shù)的原理以及如何利用它在FPGA上實(shí)現(xiàn)Systolic陣中的處理單元；在此基礎(chǔ)上，給出一種基于Systolic陣列的復(fù)用IQRD-SMI算法實(shí)現(xiàn)結(jié)構(gòu)GR-ITSA，比較了它與已有文獻(xiàn)中結(jié)構(gòu)的異同；基于ISE軟件，在Xilinx的xc7k325t型FPGA上實(shí)現(xiàn)了基于脈動陣列的IQRD-SMI算法的底層設(shè)計和硬件仿真，并將FPGA定點(diǎn)仿真數(shù)據(jù)回傳Matlab與計算機(jī)浮點(diǎn)仿真數(shù)據(jù)對比，進(jìn)而進(jìn)行系統(tǒng)的性能與誤差分析。

關(guān)鍵詞:自適應(yīng)波束形成算法；FPGA；Matlab；脈動陣；CORDIC技術(shù)；GR-ITSA

0引言

自適應(yīng)數(shù)字波束形成(ADBF)系統(tǒng)中，為了改善波束性能、增強(qiáng)期望信號的信噪比，應(yīng)使用高效的自適應(yīng)算法對即時采樣數(shù)據(jù)進(jìn)行處理[1-3]。但自適應(yīng)算法運(yùn)算量龐大、并行與實(shí)時性能差、硬件實(shí)現(xiàn)資源消耗大的問題在實(shí)際應(yīng)用中比較突出[4-6]。

為應(yīng)對以上問題，Teitelbaum[7]提出了對采樣協(xié)方差矩陣直接進(jìn)行QR分解的 (QRD-SMI)算法，該算法具有高度并行性結(jié)構(gòu)，易于使用Systolic脈動陣列搭建，在實(shí)際應(yīng)用中能夠與高性能的FPGA結(jié)合實(shí)現(xiàn)[8-9]。但是傳統(tǒng)的QRD-SMI算法存在需要通過求解兩個三角矩陣才能得到加權(quán)矢量w的缺點(diǎn)，并且后向帶入需用到資源消耗很高的硬件除法器，這對于系統(tǒng)的實(shí)現(xiàn)和權(quán)矢量w的實(shí)時并行獲取增加了復(fù)雜度。文獻(xiàn)[10]中對此算法進(jìn)行了詳細(xì)的介紹。

文獻(xiàn)[11]提出了一種逆QR分解算法(IQRD-SMI)，該算法避免了通過前向帶入和后向帶入的方式求解方程，在脈動陣結(jié)構(gòu)上的優(yōu)化達(dá)到了可以實(shí)時、并行地進(jìn)行權(quán)值獲取，更易于硬件實(shí)現(xiàn)。但是并沒有實(shí)際的工程實(shí)現(xiàn)，并且其結(jié)構(gòu)在具體實(shí)現(xiàn)中存在軟件編程復(fù)雜和硬件資源消耗高的問題。

本文研究了數(shù)字逆QR分解SMI波束形成算法，結(jié)合Systolic陣在Matlab中搭建仿真實(shí)驗(yàn)，介紹了CORDIC算法與使用方法，并用Verilog語言在ISE中進(jìn)行了硬件實(shí)現(xiàn)，進(jìn)一步提出了一種復(fù)用的硬件實(shí)現(xiàn)結(jié)構(gòu)GR-ITSA，簡化了軟件編程，節(jié)約了硬件資源成本。并將硬件定點(diǎn)處理數(shù)據(jù)與軟件浮點(diǎn)仿真數(shù)據(jù)同時回饋到Matlab中比對，進(jìn)行誤差分析。

1基于逆QR分解的SMI波束形成算法

IQRD-SMI(逆QR分解SMI)算法，是在QR分解算法上的進(jìn)一步改進(jìn)，它能夠回避QRD-SMI算法中的前后向回代問題，而且該算法仍能使用簡單的Systolic陣列結(jié)構(gòu)搭建，使權(quán)抽取操作得以全速并行實(shí)現(xiàn)，在軟件編程與硬件實(shí)現(xiàn)中的便捷性大大提升。

設(shè)采樣數(shù)據(jù)矩陣X為n次快拍得到的M*n維陣，即

(1)

傳統(tǒng)采用QR分解SMI算法首先通過對協(xié)方差矩陣Rxx的估計，避免了直接使用Rxx矩陣去求解線性方程。然后使用酉矩陣Q通過Givens旋轉(zhuǎn)對采樣矩陣QR分解，最終化簡為通過求解如(2)式所示的線性方程組來取得自適應(yīng)權(quán)值w：

(2)

式(2)中，s為導(dǎo)向矢量；An是上三角陣，通過使用n*n維酉陣將xn三角化而得到；對數(shù)據(jù)矩陣xnQR分解的常用方法有Givens旋轉(zhuǎn)和CORDIC算法。通過前向回代和后向回代的方法，可分別對式(2)中的上三角陣與下三角陣求解，從而得到自適應(yīng)權(quán)w[12].

其算法實(shí)現(xiàn)步驟如下：

2)k=1,2,…,遞推更新。

首先，計算中間向量z(n) = [An-1-H]*x(n)

2脈動陣(Systolic陣)

Systolic英文解釋為“心臟收縮”， H.T.Kung根據(jù)心臟按節(jié)拍收縮而使血液流至全身的原理提出了Systolic陣列結(jié)構(gòu)，Systolic陣由一系列僅具有單一功能的處理單元(PE)構(gòu)成，每個PE結(jié)構(gòu)簡單、易于實(shí)現(xiàn)、耗時耗能少，所有的PE單元都在有節(jié)拍的同步運(yùn)行，系統(tǒng)工作時將從存儲器中按節(jié)奏抽取數(shù)據(jù)并壓入脈動陣，沿途經(jīng)過并行的PE流水線，由于脈動陣列的結(jié)構(gòu)特點(diǎn)，使數(shù)據(jù)能夠高效、連續(xù)地完成整個處理過程。脈動陣結(jié)構(gòu)原理如圖1所示。

圖1　Systolic脈動陣列結(jié)構(gòu)原理框圖

以4陣元為例，應(yīng)用Givens旋轉(zhuǎn)IQRD-SMI算法的三角脈動陣列 (GR-TSA,Givens Rotation-Triangular systolic array)示意圖詳見圖2。

圖2　IQRD-SMI算法GR-TSA陣示意圖

內(nèi)部各單元具體功能闡述如下：

1)bPE單元

(4)xout=xin

2)zPE單元

3)vPE單元

yout=vi

4)wPE單元

(1)當(dāng)非對角元bij到來時完成乘積累加；wi(k)=zoutyin+wi(k-1);

(2)當(dāng)對角元bii到來時完成乘積累加后輸出wi并清零；

3IQRD-SMI算法的FPGA優(yōu)化及實(shí)現(xiàn)

3.1CORDIC技術(shù)

GIVENS旋轉(zhuǎn)運(yùn)算需要進(jìn)行開方與除法操作，這些運(yùn)算會消耗大量的硬件資源，造成系統(tǒng)功耗過高的問題，從而達(dá)不到設(shè)計標(biāo)準(zhǔn)。此時引入CORDIC(coordinate rotation digital computer)技術(shù)來實(shí)現(xiàn)Givens旋轉(zhuǎn)。CORDIC技術(shù)的基本思想是將一組固定的角度θi利用循環(huán)迭代算法，通過不斷地擺動進(jìn)而逼近所需旋轉(zhuǎn)的角度θ。由于僅需移位和加/減法即可完成CORDIC運(yùn)算，這樣大大節(jié)約了FPGA硬件資源，非常適合在FPGA系統(tǒng)上實(shí)現(xiàn)。

基于CORDIC的無開方復(fù)數(shù)GIVENS旋轉(zhuǎn)思想[13]，采用多個CORDIC單元依次完成復(fù)數(shù)轉(zhuǎn)化實(shí)數(shù)的相位翻譯、實(shí)數(shù)值與前一時刻值的相位翻譯，從而得到GIVENS變換的相位，再經(jīng)過直接數(shù)字式頻率合成器DDS(Direct Digital Synthesizer)就能得到角度值，進(jìn)而經(jīng)過systolic陣的依次處理實(shí)現(xiàn)矩陣的QR分解。

3.2IQRD-SMI算法脈動陣結(jié)構(gòu)的FPGA實(shí)現(xiàn)

脈動陣列FPGA實(shí)現(xiàn)的核心模塊是旋轉(zhuǎn)單元(bPE)，旋轉(zhuǎn)單元實(shí)現(xiàn)步驟：

1)進(jìn)行兩次CORDIC旋轉(zhuǎn)：首先使用CORDIC核來實(shí)現(xiàn)對輸入數(shù)據(jù)求模，取得輸入數(shù)據(jù)的模|xin|和旋轉(zhuǎn)角θ。再次使用CORDIC核來求得x′和旋轉(zhuǎn)角φ；

2)計算旋轉(zhuǎn)角θ和φ的正余弦值，并計算c,s。

旋轉(zhuǎn)單元FPGA模塊化如圖3所示。

圖3旋轉(zhuǎn)單元的FPGA模塊化框圖

IQRD-SMI脈動陣列結(jié)構(gòu)的完整FPGA實(shí)現(xiàn)同圖3所示，在頂層模塊中通過時序、寄存器和控制口來操控數(shù)據(jù)的采集處理節(jié)拍與流向。

3.3改良的復(fù)用FPGA實(shí)現(xiàn)結(jié)構(gòu) (GR-ITSA,Givens rotation-Improved triangular systolic array)

FPGA芯片內(nèi)部集成了常用的硬件資源，如DSP Slices、乘法器等，但是這些資源的數(shù)量有限。傳統(tǒng)systolic陣列結(jié)構(gòu)會隨著陣元數(shù)的增加而大大消耗硬件資源。為了節(jié)約成本、降低硬件資源消耗，在傳統(tǒng)IQRD-SMI算法的systolic陣列上進(jìn)行改進(jìn)，得到了低消耗的復(fù)用脈動陣結(jié)構(gòu)GR-ITSA，如圖4所示。

圖4　GR-ITSA復(fù)用脈動陣列結(jié)構(gòu)

關(guān)鍵的修改是在原陣列結(jié)構(gòu)的基礎(chǔ)上增加了時序控制器和用于存儲中間量的FIFO。各PE單元實(shí)現(xiàn)的基本功能與傳統(tǒng)結(jié)構(gòu)一致，時序控制單元主要調(diào)度各PE的數(shù)據(jù)采集處理節(jié)拍，并含有寄存器(Block RAM)，用來接收和傳遞相應(yīng)數(shù)據(jù)到各PE端口。

時序控制單元包含5種先入先出數(shù)據(jù)寄存器(FIFO):FIFO_Data、FIFO_bPE、FIFO_CS、FIFO_vPE、FIFO_wPE。FIFO_Data由M對寬度為L(M為陣元個數(shù)，L為量化后的接收數(shù)據(jù)位寬)、深度為N(N為采樣快拍總數(shù))的FIFO構(gòu)成，用來緩存接收到的采樣數(shù)據(jù)，并將數(shù)據(jù)提供給bPE。FIFO_bPE、FIFO_vPE、FIFO_wPE由深度為N的FIFO構(gòu)成，用來接收各個PE單元的輸出數(shù)據(jù)并為下一次的計算提供數(shù)據(jù)。FIFO_CS由3個FIFO構(gòu)成，用來緩存bPE單元計算輸出的C、S，并將C、S送至bPE和vPE單元。

5種FIFO與4類PE單元完成一次數(shù)據(jù)陣的QR分解需多個步驟，期間4類PE單元和5種堆棧在不同的時間段被調(diào)用，實(shí)現(xiàn)硬件資源共享。

4IQRD-SMI 算法的軟硬件仿真及誤差分析

4.1仿真結(jié)果

首先使用Matlab模擬生成信號源，通過Verilog I/O接口文件將信號數(shù)據(jù)輸入到ISE程序中，并在Modesim軟件下進(jìn)行FPGA定點(diǎn)仿真驗(yàn)證，最后將輸出結(jié)果返回Matlab，同Matlab中的浮點(diǎn)仿真計算結(jié)果進(jìn)行比對。仿真參數(shù)如表1所示，仿真結(jié)果如圖5所示。

表1　仿真參數(shù)設(shè)計

圖5　ISE與Matlab仿真結(jié)果對比圖

IQRD-SMI算法在Matlab軟件浮點(diǎn)仿真與FPGA硬件定點(diǎn)仿真的對比波束如圖6所示，仿真采用的采樣數(shù)為64次快拍，滿足基本采樣數(shù)大于2 M的條件。通過對比圖可知，改進(jìn)的GR-ITSA結(jié)構(gòu)實(shí)現(xiàn)了逆QR分解自適應(yīng)波束形成算法，權(quán)向量得以高效實(shí)時的獲取，在波束的期望方向theta= 50°處，算法對信號的增益值達(dá)到最大。

4.2誤差分析與資源消耗

為了得到該算法的平均誤差百分比，將復(fù)用結(jié)構(gòu)FPGA定點(diǎn)計算與MATLAB浮點(diǎn)計算的結(jié)果引入誤差計算公式(3)，取算術(shù)平均值作為最后的結(jié)果。

(3)

其中:rise表示FPGA硬件處理的結(jié)果，rmat表示Matlab浮點(diǎn)計算的輸出，最終計算得到的誤差百分比為0.38%。由誤差數(shù)據(jù)看出，復(fù)用的FPGA結(jié)構(gòu)在自適應(yīng)權(quán)向量的抽取上具有高度的一致有效性。

當(dāng)采樣數(shù)據(jù)寬度為32bit，F(xiàn)PGA芯片采用xc7k325t時，觀察表2中不同設(shè)計結(jié)構(gòu)的硬件資源消耗。

由表2可知，當(dāng)陣元數(shù)較小時，傳統(tǒng)GR-TSA結(jié)構(gòu)和改良的GR-ITSA結(jié)構(gòu)都可以考慮作為自適應(yīng)波束形成算法的實(shí)現(xiàn)結(jié)構(gòu)，但是當(dāng)sensor數(shù)大于等于4時，傳統(tǒng)GR-TSA結(jié)構(gòu)硬件資源消耗極大，不再具有實(shí)用性，觀察此時的XtremeDSPSlices消耗發(fā)現(xiàn)，復(fù)用的GR-ITSA結(jié)構(gòu)能減少的消耗達(dá)38%以上。

表2　不同硬件結(jié)構(gòu)下的資源消耗

5結(jié)論

為了避免自適應(yīng)算法中復(fù)雜的權(quán)抽取，首先研究了改進(jìn)的逆QR分解SMI自適應(yīng)算法，接著運(yùn)用Systolic陣列，將算法的FPGA實(shí)現(xiàn)結(jié)構(gòu)GR-TSA搭建出來。又研究了FPGA實(shí)現(xiàn)中各PE的具體實(shí)現(xiàn)方法，其中用到了CORDIC技術(shù)與DDS技術(shù)。最后在傳統(tǒng)Systolic陣列結(jié)構(gòu)的基礎(chǔ)上改進(jìn)，給出了復(fù)用的GR-ITSA陣列結(jié)構(gòu)，并做了硬件定點(diǎn)仿真與軟件浮點(diǎn)仿真的回饋分析。通過定量分析，復(fù)用結(jié)構(gòu)可以顯著降低資源消耗，在實(shí)際工程應(yīng)用有效節(jié)約了成本。

參考文獻(xiàn)：

[1] 宋丹, 曲紹君, 李高鵬. 基于失配處理的自適應(yīng)干擾抑制系統(tǒng)[J]. 計算機(jī)測量與控制, 2012, 20(2): 480-483,499.

[2] 包志強(qiáng), 丁康利, 單潔. 基于脈動陣的自適應(yīng)波束形成算法仿真[J].無線通信技術(shù), 2014,23(2):1-5,10.

[3] 宋博, 岳翠蘋, 孫晶冬,等. 自適應(yīng)數(shù)字波束形成的研究與實(shí)現(xiàn)[J].電視技術(shù),2014，38(3).

[4] 戴凌燕. 自適應(yīng)波束形成技術(shù)應(yīng)用基礎(chǔ)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)研究生院,2009:2-16.

[5] 黃飛. 陣列天線快速自適應(yīng)波束形成技術(shù)研究[D].南京：南京理工大學(xué),2010:16-20.

[6] 劉倩. 陣列天線自適應(yīng)波束形成算法研究[D].大連：大連理工大學(xué),2008:7-10.

[7]TeitelbaumK.AFlexibleprocessorforadigitaladaptivearrayradar[J].IEEETrans.SystemsMagazine,1991,AES(5):18-22.

[8] 龔耀寰. 自適應(yīng)濾波時域自適應(yīng)濾波和智能天線[M].北京:電子工業(yè)出版社, 2003.

[9] 王永良. 空時自適應(yīng)信號處理[M].北京:清華大學(xué)出版社,2000.

[10] 馮地耘, 陳立萬, 王悅善. 自適應(yīng)波束形成與高性能DSP[M].2007年9月第一版.成都：西南交通大學(xué)出版社，2007.

[11] 劉千里. 基于FPGA的逆QR分解SMI算法的并行實(shí)現(xiàn)方法[J].計算機(jī)工程與應(yīng)用,2012,48(26):71-75,161.

[12]RaderCM.VLSISystolicarraysforadaptivenulling[J] .IEEESignalProcessingMagazine, 1996,13(7):29-49.

[13] 龔耀寰, 李航, 茍仲文. 基于CORDIC的無開方GIVENS旋轉(zhuǎn)處理方法[J].電子科技大學(xué)學(xué)報(自然科學(xué)版),1997,26(6):565-569.

Research and FPGA Optimization Implementation of IQRD-SMI Algorithm Based on Systolic Array

Liu Yutao, Bao Zhiqiang, Li Longlong, Su Zihao

(Xi’an University of Posts and Telecommunications, Xi’an710061,China)

Abstract:For the problem of the weight values need a large amount of calculations in the adaptive beam-forming system, studied the inverse QR decomposition algorithm based on LCMV (IQRD-SMI algorithm) and the structure of traditional Systolic array GR-TSA, built with systolic array structures and simulated in Matlab. The principle of CORDIC technology is analyzed and how to use it on FPGA implement systolic array processing unit. On the basis of this, Based on the reuse of systolic arrays IQRD-SMI algorithm structure is given, Compared it with existing in the literature. Underlying design based on IQRD-SMI algorithm and hardware simulation based on systolic array be realized with xc7k325t in Xilinx FPGA, And the FPGA fixed-point simulation data and the computer floating-point simulation data contrast. The system and error is analysed.

Keywords:adaptive beamforming algorithms; FPGA; Matlab; systolic array; CORDIC techniques; GR-ITSA

文章編號：1671-4598(2016)02-0239-03

DOI：10.16526/j.cnki.11-4762/tp.2016.02.066

中圖分類號：TN975

文獻(xiàn)標(biāo)識碼：A

作者簡介：劉禹韜(1988-)，男，遼寧錦州人，碩士研究生，主要從事信息處理技術(shù)及應(yīng)用方向的研究。

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61271276)；陜西省自然科學(xué)基金資助項(xiàng)目(2012JQ8011)。

收稿日期：2015-08-21；修回日期：2015-09-17。