一種任意維空域最小二乘算法的硬件實現方法

幸璐璐

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

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

關鍵詞：最小二乘；現場可編程門陣列；實現

doi:10.3969/j.issn.1002-0802.2015.06.023

一種任意維空域最小二乘算法的硬件實現方法

幸璐璐

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

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

關鍵詞：最小二乘；現場可編程門陣列；實現

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

中圖分類號：TN957

文獻標志碼：碼：A

文章編號：號：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.

作者簡介：

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引言

在空域自適應濾波算法中，RLS(recursive least squares)算法是一種指數加權的最小二乘方法此方法使用指數加權的誤差平方和作為代價函數使此函數最小化利用遞歸的方法完成矩陣求逆運算。它具有收斂速度快，實時性好，對非平穩信號適應性強的優點。

在工程運用中可以對信號的矩陣進行QR分解從而計算出方程組解，且對矩陣進行直接分解較標準RLS具有更好的數值穩定性和更小的運算量。傳統的QR_RLS算法在FPGA(現場可編程門陣列)實現的時候，是通過Systolic(脈動)結構來進行硬件實現的，這需要用到很多的乘法器和寄存器資源，如果算法的維數M變多會導致乘法器和寄存器資源不夠用。而如果選用資源夠多的硬件來實現，又會造成硬件成本的增加。

在FPGA設計實現中，有時可用的邏輯資源有限,這時可能只有犧牲數據吞吐率來獲得更小的資源消耗。在資源有限的情況下，可以對某一個模塊分時進行使用，運算過程中產生的中間量用寄存器暫存，這種實現方法便是折疊。相比脈動結構，折疊算法在RLS的FPGA實現中的運用還不是很常見。

針對空域RLS算法的特點，本文在折疊算法思想基礎上提出了一種任意維空域遞推最小二乘算法的硬件實現的方法。該算法可以在硬件結構中使用較少的乘法器和寄存器進行任意維空域遞推最小二乘運算，從而解決當算法中的維數變多后資源不夠用的問題。

1QR-RLS算法

(1)

(2)

2QR-RLS算法的Systolic處理實現

(3)

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

(4)

相應地可得到QR_RLS算法的Systolic結構(脈動結構)如圖1所示。圖1中M=3，共有10個處理單元。

由此可見，傳統的QR_RLS算法在FPGA(現場可編程門陣列)實現的時候，是通過Systolic(脈動)結構來進行硬件實現的，這需要用到很多的乘法器和寄存器資源，如果算法的維數M變多會導致乘法器和寄存器資源不夠用。而如果選用資源夠多的硬件來實現，又會造成硬件成本的增加。

3改進的QR-RLS硬件實現算法

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

圖2　本文改進方法流程

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

a．在對QR_RLS算法進行Givens旋轉時，將M維空域遞推最小二乘算法的脈動結構劃分為均具有輸入和輸出的邊界處理單元、內部處理單元和乘積單元，其中M為自然數。邊界處理單元對應于圖1中標有z11,…,z12的圓圈，如圖3所示，共有M個。

圖3　邊界處理單元示意

邊界單元的表達式為：

(5)

內部處理單元對應于圖1中的方框，它分為兩類：如圖4所示的第一內部處理單元。

圖4　第一內部處理單元

對應圖1標zji的方框，共有M(M-1)/2個：

(6)

如圖5所示的第二內部處理單元，對應于圖1中標有ui的方框，共有M個。

圖5　第二內部處理單元

表達式為：

(7)

如圖6示的乘積處理單元，對應圖2中標有×的圓圈，該單元只有一個。

圖6　乘積處理單元示意

b．根據步驟a劃分出的三個處理單元，將M維空域遞推最小二乘算法的脈動結構進行等效劃分，并將邊界處理單元命名為PEA(PE: processing elements，處理單元)，內部處理單元命名為PEB，乘積處理單元此處省略，因為乘積單元只影響最終的誤差信號輸出，不會影響內部單元和邊界單元的運算。由此圖1所示的systolic結構可以簡化成如圖7示，其中D表示延遲，在系統中可以認為是一個采樣時刻。

圖7等效劃分后的Systolic結構示意

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

圖8　四維Systolic結構的折疊原理

4仿真分析

用本文的折疊RLS的算法在QuartusII上分別實現一個4維和16維的RLS算法，觀察其仿真資源，并與4維脈動結構的RLS算法資源消耗對比如表1所示。

表1　仿真資源消耗對比

我們可以看出4維折疊QR_RLS與16維折疊QR_RLS所消耗的資源基本上相通，除了后者要比前者多有一些RAM資源，這是因為后者的結構只是在前者的基礎上多加了一些D延時單元，其基本運算結構是保持不變的。這一點對更高維的QR_RLS算法實現同樣適用。而脈動結構不消耗存儲單元，但是會消耗更多的乘法器，當完成四維的RLS實現時，所用乘法器資源已經占了乘法器資源的91%，當維數再增加時，硬件資源已經不夠，故無法實現更高維的RLS算法。

5結語

本文分析了QR-RLS算法的原理，介紹了現有的基于Systolic結構的實現算法。目前QR-RLS的實現大多采用這種結構，但是當維數增加后，資源的耗費也會隨之增加。針對該問題，本文提出了一種通過折疊算法進行改進的方法。該方法通過折疊的思想，在原有算法的結構上進行了改進。經過仿真驗證，使用該算法時，當維數增加時，消耗的硬件資源并沒有隨之增加。該算法在原有算法的基礎上大大減少資源的耗費情況，進而解決了當維數增加時硬件資源不夠的問題，可以在維數較大時很好地實現QR-RLS算法。

參考文獻：

[1]李成, 舒勤. RLS算法自適應信道估計的性能分析[J]. 通信技術,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分解的低復雜度RLS算法研究[J]. 機電設備, 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算法的浮點脈動陣結構研究與FPGA實現[J]. 現代雷達, 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]何子述,夏威.現代數字信號處理及其運用[M].北京:清華大學出版社,2005.

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

[5]Keshab, Parhi K. VLSI數字信號處理系統設計與實現[M].北京：機械工業出版社出版, 2003.

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

幸璐璐(1981—) ， 女，碩士，工程師，主要研究方向為衛星通信抗干擾理論研究與設計。