一种任意维空域最小二乘算法的硬件实现方法

幸璐璐

(成都天奥信息科技有限公司，四川 成都 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—) ， 女，硕士，工程师，主要研究方向为卫星通信抗干扰理论研究与设计。