幸璐璐

(成都天奧信息科技有限公司，四川 成都 610000)

摘　要：在自適應(yīng)濾波算法中，空域遞推最小二乘(RLS)算法以其較快的收斂速度以及能計(jì)算出精確的最佳濾波器系數(shù)等優(yōu)勢(shì)得到了廣泛的運(yùn)用。但是由于該算法較為復(fù)雜，計(jì)算量大，因此硬件實(shí)現(xiàn)時(shí)耗費(fèi)資源多，難度大。提出了一種任意維空域遞推最小二乘算法的FPGA(現(xiàn)場(chǎng)可編程門陣列)實(shí)現(xiàn)的方法，該方法可以在硬件結(jié)構(gòu)中使用較少的乘法器和寄存器進(jìn)行任意維空域遞推最小二乘運(yùn)算，從而解決維數(shù)變多后資源不夠用的問(wèn)題。

關(guān)鍵詞：最小二乘；現(xiàn)場(chǎng)可編程門陣列；實(shí)現(xiàn)

doi:10.3969/j.issn.1002-0802.2015.06.023

一種任意維空域最小二乘算法的硬件實(shí)現(xiàn)方法

幸璐璐

(成都天奧信息科技有限公司，四川 成都 610000)

摘要：在自適應(yīng)濾波算法中，空域遞推最小二乘(RLS)算法以其較快的收斂速度以及能計(jì)算出精確的最佳濾波器系數(shù)等優(yōu)勢(shì)得到了廣泛的運(yùn)用。但是由于該算法較為復(fù)雜，計(jì)算量大，因此硬件實(shí)現(xiàn)時(shí)耗費(fèi)資源多，難度大。提出了一種任意維空域遞推最小二乘算法的FPGA(現(xiàn)場(chǎng)可編程門陣列)實(shí)現(xiàn)的方法，該方法可以在硬件結(jié)構(gòu)中使用較少的乘法器和寄存器進(jìn)行任意維空域遞推最小二乘運(yùn)算，從而解決維數(shù)變多后資源不夠用的問(wèn)題。

關(guān)鍵詞：最小二乘；現(xiàn)場(chǎng)可編程門陣列；實(shí)現(xiàn)

doi:10.3969/j.issn.1002-0802.2015.06.023

收稿日期：2015-01-16；修回日期：2015-04-29Received date:2015-01-16；Revised date：2015-04-29

中圖分類號(hào)：TN957

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

文章編號(hào)：號(hào)：1002-0802(2015)06-0746-04

Abstract：Among all the adaptive filtering algorithms, RLS is widely applied for its fast convergence rate and precise calculation of the filter coefficients. However, due to its complexity and large computation, the hardware implementation of RLS would bring many difficulties and consume a lot of resources. This paper proposes a method that could implement the RLS algorithm with any dimension in FPGA(Field Programmable Gate Array) and solve the problem in lacking resources due to less multipliers and registers in hardware construction.

作者簡(jiǎn)介：

Hardware Implementation of RLS with Any Dimension

XING Lu-lu

(Chengdu Spaceon Technology Co., Ltd.，Chengdu Sichuan 610000, China)

Key words：Key words：RLS; FPGA; implementation

0引言

在空域自適應(yīng)濾波算法中，RLS(recursive least squares)算法是一種指數(shù)加權(quán)的最小二乘方法此方法使用指數(shù)加權(quán)的誤差平方和作為代價(jià)函數(shù)使此函數(shù)最小化利用遞歸的方法完成矩陣求逆運(yùn)算。它具有收斂速度快，實(shí)時(shí)性好，對(duì)非平穩(wěn)信號(hào)適應(yīng)性強(qiáng)的優(yōu)點(diǎn)。

在工程運(yùn)用中可以對(duì)信號(hào)的矩陣進(jìn)行QR分解從而計(jì)算出方程組解，且對(duì)矩陣進(jìn)行直接分解較標(biāo)準(zhǔn)RLS具有更好的數(shù)值穩(wěn)定性和更小的運(yùn)算量。傳統(tǒng)的QR_RLS算法在FPGA(現(xiàn)場(chǎng)可編程門陣列)實(shí)現(xiàn)的時(shí)候，是通過(guò)Systolic(脈動(dòng))結(jié)構(gòu)來(lái)進(jìn)行硬件實(shí)現(xiàn)的，這需要用到很多的乘法器和寄存器資源，如果算法的維數(shù)M變多會(huì)導(dǎo)致乘法器和寄存器資源不夠用。而如果選用資源夠多的硬件來(lái)實(shí)現(xiàn)，又會(huì)造成硬件成本的增加。

在FPGA設(shè)計(jì)實(shí)現(xiàn)中，有時(shí)可用的邏輯資源有限,這時(shí)可能只有犧牲數(shù)據(jù)吞吐率來(lái)獲得更小的資源消耗。在資源有限的情況下，可以對(duì)某一個(gè)模塊分時(shí)進(jìn)行使用，運(yùn)算過(guò)程中產(chǎn)生的中間量用寄存器暫存，這種實(shí)現(xiàn)方法便是折疊。相比脈動(dòng)結(jié)構(gòu)，折疊算法在RLS的FPGA實(shí)現(xiàn)中的運(yùn)用還不是很常見。

針對(duì)空域RLS算法的特點(diǎn)，本文在折疊算法思想基礎(chǔ)上提出了一種任意維空域遞推最小二乘算法的硬件實(shí)現(xiàn)的方法。該算法可以在硬件結(jié)構(gòu)中使用較少的乘法器和寄存器進(jìn)行任意維空域遞推最小二乘運(yùn)算，從而解決當(dāng)算法中的維數(shù)變多后資源不夠用的問(wèn)題。

1QR-RLS算法

(1)

(2)

2QR-RLS算法的Systolic處理實(shí)現(xiàn)

(3)

如果式(3)中前M行每個(gè)元素看成一個(gè)計(jì)算單元，最后一行看成輸入，可進(jìn)一步演化出如下的形式[4]：

(4)

相應(yīng)地可得到QR_RLS算法的Systolic結(jié)構(gòu)(脈動(dòng)結(jié)構(gòu))如圖1所示。圖1中M=3，共有10個(gè)處理單元。

由此可見，傳統(tǒng)的QR_RLS算法在FPGA(現(xiàn)場(chǎng)可編程門陣列)實(shí)現(xiàn)的時(shí)候，是通過(guò)Systolic(脈動(dòng))結(jié)構(gòu)來(lái)進(jìn)行硬件實(shí)現(xiàn)的，這需要用到很多的乘法器和寄存器資源，如果算法的維數(shù)M變多會(huì)導(dǎo)致乘法器和寄存器資源不夠用。而如果選用資源夠多的硬件來(lái)實(shí)現(xiàn)，又會(huì)造成硬件成本的增加。

3改進(jìn)的QR-RLS硬件實(shí)現(xiàn)算法

本文提出了一種折疊算法，可以有效地降低資源使用率，該算法的流程圖如圖2所示。

圖2　本文改進(jìn)方法流程

以4維RLS(空域遞推最小二乘)算法為例，該算法的具體實(shí)現(xiàn)方法為：

a．在對(duì)QR_RLS算法進(jìn)行Givens旋轉(zhuǎn)時(shí)，將M維空域遞推最小二乘算法的脈動(dòng)結(jié)構(gòu)劃分為均具有輸入和輸出的邊界處理單元、內(nèi)部處理單元和乘積單元，其中M為自然數(shù)。邊界處理單元對(duì)應(yīng)于圖1中標(biāo)有z11,…,z12的圓圈，如圖3所示，共有M個(gè)。

圖3　邊界處理單元示意

邊界單元的表達(dá)式為：

(5)

內(nèi)部處理單元對(duì)應(yīng)于圖1中的方框，它分為兩類：如圖4所示的第一內(nèi)部處理單元。

圖4　第一內(nèi)部處理單元

對(duì)應(yīng)圖1標(biāo)zji的方框，共有M(M-1)/2個(gè)：

(6)

如圖5所示的第二內(nèi)部處理單元，對(duì)應(yīng)于圖1中標(biāo)有ui的方框，共有M個(gè)。

圖5　第二內(nèi)部處理單元

表達(dá)式為：

(7)

如圖6示的乘積處理單元，對(duì)應(yīng)圖2中標(biāo)有×的圓圈，該單元只有一個(gè)。

圖6　乘積處理單元示意

b．根據(jù)步驟a劃分出的三個(gè)處理單元，將M維空域遞推最小二乘算法的脈動(dòng)結(jié)構(gòu)進(jìn)行等效劃分，并將邊界處理單元命名為PEA(PE: processing elements，處理單元)，內(nèi)部處理單元命名為PEB，乘積處理單元此處省略，因?yàn)槌朔e單元只影響最終的誤差信號(hào)輸出，不會(huì)影響內(nèi)部單元和邊界單元的運(yùn)算。由此圖1所示的systolic結(jié)構(gòu)可以簡(jiǎn)化成如圖7示，其中D表示延遲，在系統(tǒng)中可以認(rèn)為是一個(gè)采樣時(shí)刻。

圖7等效劃分后的Systolic結(jié)構(gòu)示意

d．根據(jù)步驟c的新延時(shí)表得到Systolic結(jié)構(gòu)的折疊原理圖，如圖8所示，圖8的l表示的是迭代次數(shù)。由此得到了4維RLS算法的Systolic折疊結(jié)構(gòu)，當(dāng)實(shí)際工程要求中RLS算法的維數(shù)大于4時(shí)，根據(jù)圖1畫出相應(yīng)維數(shù)的Systolic結(jié)構(gòu)，然后根據(jù)步驟b得到等效后的Systolic結(jié)構(gòu)圖，重復(fù)步驟c即可得到任意維的RLS算法的Systolic折疊結(jié)構(gòu)。

圖8　四維Systolic結(jié)構(gòu)的折疊原理

4仿真分析

用本文的折疊RLS的算法在QuartusII上分別實(shí)現(xiàn)一個(gè)4維和16維的RLS算法，觀察其仿真資源，并與4維脈動(dòng)結(jié)構(gòu)的RLS算法資源消耗對(duì)比如表1所示。

表1　仿真資源消耗對(duì)比

我們可以看出4維折疊QR_RLS與16維折疊QR_RLS所消耗的資源基本上相通，除了后者要比前者多有一些RAM資源，這是因?yàn)楹笳叩慕Y(jié)構(gòu)只是在前者的基礎(chǔ)上多加了一些D延時(shí)單元，其基本運(yùn)算結(jié)構(gòu)是保持不變的。這一點(diǎn)對(duì)更高維的QR_RLS算法實(shí)現(xiàn)同樣適用。而脈動(dòng)結(jié)構(gòu)不消耗存儲(chǔ)單元，但是會(huì)消耗更多的乘法器，當(dāng)完成四維的RLS實(shí)現(xiàn)時(shí)，所用乘法器資源已經(jīng)占了乘法器資源的91%，當(dāng)維數(shù)再增加時(shí)，硬件資源已經(jīng)不夠，故無(wú)法實(shí)現(xiàn)更高維的RLS算法。

5結(jié)語(yǔ)

本文分析了QR-RLS算法的原理，介紹了現(xiàn)有的基于Systolic結(jié)構(gòu)的實(shí)現(xiàn)算法。目前QR-RLS的實(shí)現(xiàn)大多采用這種結(jié)構(gòu)，但是當(dāng)維數(shù)增加后，資源的耗費(fèi)也會(huì)隨之增加。針對(duì)該問(wèn)題，本文提出了一種通過(guò)折疊算法進(jìn)行改進(jìn)的方法。該方法通過(guò)折疊的思想，在原有算法的結(jié)構(gòu)上進(jìn)行了改進(jìn)。經(jīng)過(guò)仿真驗(yàn)證，使用該算法時(shí)，當(dāng)維數(shù)增加時(shí)，消耗的硬件資源并沒(méi)有隨之增加。該算法在原有算法的基礎(chǔ)上大大減少資源的耗費(fèi)情況，進(jìn)而解決了當(dāng)維數(shù)增加時(shí)硬件資源不夠的問(wèn)題，可以在維數(shù)較大時(shí)很好地實(shí)現(xiàn)QR-RLS算法。

參考文獻(xiàn)：

[1]李成, 舒勤. RLS算法自適應(yīng)信道估計(jì)的性能分析[J]. 通信技術(shù),2009,42(07):53-54.

LI Cheng,SHU Qin.Performance Analysis of RLS Algorithm Adaptive Channel Estimation[J],Communications Technology.2009,42(07):53-54.

[2]楊鐵軍, 李軍華. 基于QR分解的低復(fù)雜度RLS算法研究[J]. 機(jī)電設(shè)備, 2013(04):71-74.

YANG Tie-jun，LI Jun-hua，Low Complexity RLS Algorithm Based on QR Decomposition[J].Mechanical and Electronic Equipment, 2013, (4):71-74.

[3]杜鶴, 買培培, 蘇濤等. QR—RLS算法的浮點(diǎn)脈動(dòng)陣結(jié)構(gòu)研究與FPGA實(shí)現(xiàn)[J]. 現(xiàn)代雷達(dá), 2011,33(05):26-29.

DU He，MAI Pei-pei，SU Tao，et al. Study on Floating-Point Systolic Array Structure and FPGA Implementation based on QR-RLS Algorithm[J].Morden Radar, 2011, 33(05):26-29.

[4]何子述,夏威.現(xiàn)代數(shù)字信號(hào)處理及其運(yùn)用[M].北京:清華大學(xué)出版社,2005.

HE Zi-shu，XIA Wei.Modern Digital Signal Processing and Its Application. Beijing:Tsinghua University Press,2005.

[5]Keshab, Parhi K. VLSI數(shù)字信號(hào)處理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[M].北京：機(jī)械工業(yè)出版社出版, 2003.

Keshab, Parhi K. VLSI Digital Signal Processing Systems: Design and Implementation[M].China Machine Press,2003.

幸璐璐(1981—) ， 女，碩士，工程師，主要研究方向?yàn)樾l(wèi)星通信抗干擾理論研究與設(shè)計(jì)。