一种基于DA-RNS算法的FIR滤波器的实现方法

摘要

本发明涉及一种基于DA-RNS算法的FIR滤波器的实现方法，该方法包括以下步骤：1)利用按位查表方法对滤波输入和滤波系数进行十进制有权系统向余数无权系统的转化；2)将滤波输入分解为单比特形式；3)对滤波输入和滤波系数进行单比特卷积运算；4)通过滤波输入在余数无权系统下的余数对卷积运算后的滤波输入进行缩放运算；5)利用中国剩余定理进行余数向十进制的恢复。与现有技术相比，本发明具有资源消耗小、吞吐量大等优点。

说明书

技术领域

本发明涉及一种数字信号处理器件的实现方法，尤其是涉及一种基于DA-RNS 算法的FIR滤波器的实现方法。

背景技术

在数字信号处理中，经常使用FIR滤波器对输入信号进行滤波以获取高质量 的信号。FIR(Finite Impulse Response)滤波器是数字信号处理系统中最基本的元 件，可以在保证任意幅频特性的同时具有严格的线性相频特性，同时其单位抽样响 应是有限长的，因而滤波器是稳定的系统。因此，FIR滤波器在通信、图像处理、 模式识别等领域都有着广泛的应用。例如在中国数字电视地面传输国家标准中，对 成型滤波的平方根升余弦滚降FIR滤波器滚降系数要求为0.05，其过渡带很窄， 频谱利用率很高，但对于硬件实现而言滤波器阶数很高，硬件实现复杂度很高。因 此，FIR滤波器实现是一个十分现实的问题。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种资源消耗 小、吞吐量大的基于DA-RNS算法的FIR滤波器的实现方法。

本发明的目的可以通过以下技术方案来实现：

一种基于DA-RNS算法的FIR滤波器的实现方法，该方法包括以下步骤：

1)利用按位查表方法对滤波输入和滤波系数进行十进制有权系统向余数无权 系统的转化；

2)将滤波输入分解为单比特形式；

3)对滤波输入和滤波系数进行单比特卷积运算；

4)通过滤波输入在余数无权系统下的余数对卷积运算后的滤波输入进行缩放 运算；

5)利用中国剩余定理进行余数向十进制的恢复。

所述的步骤1)具体为：

11)将二进制数每一位为1时在基下的余数存入ROM中，作为查询表；

12)对输入的有符号二进制数X依次判断每一位是否为1，且根据查询表查询 相对应的余数进行累加；

13)获得X在所有基下对应的余数，存入ROM中。

所述的步骤3)具体为：

31)在某个基下，根据滤波输入的余数对滤波输入进行分组处理，将余数相同 的滤波输入分为一组；

32)根据分组结果通过以下公式和查询表进行单比特卷积计算：

$S_j={\left|\underset{i=0}{\overset{N-1}{\Sigma }}\right[{\alpha }_i+\underset{g=1}{\overset{(M-1)/2}{\Sigma }}g({\zeta }_i\left(g\right)x_{i,j}+\overline{x_{i,j}}{\zeta }_i(M-g))\left]\right|}_M$

其中，x_i，j为第i个数的第j个比特位，为x_i，j取反，α_i为第i个滤波系数对 应的常数，ζ_i(g)为构造函数，第i个数的滤波系数C_i在基M下的模等于g时，ζ_i(g) 为1，否则为0，N为滤波系数的个数。

所述的步骤4)中缩放运算的公式为：

y_i＝＜(x_i-＜X_i＞k)*(k^-1)＞m_i

其中，m_i为基，X_i为要在基m_i下要缩放的数，k为缩放系数，y_i则为缩放之后 在基m_i下的数，x_i为X_i在基m_i下的余数。

所述的步骤5)具体为：

51)对缩放运算后得到的基进行分组；

52)根据以下公式计算获得余数向十进制转化后的结果：

$Y=r_b+\frac{(r_a-r_b)+{\mathrm{\theta m}}_a}{m_b-m_a}*m_b$

式中，r_a、r_b分别为对应基m_a、m_b下的余数，θ为常数。

与现有技术相比，本发明具有以下优点：

(1)本发明将滤波输入和滤波系数转换成余数数制(RNS，Residue Number System)来完成滤波计算，减小FIR滤波器在FPGA上实现的面积和功耗，减少 资源的消耗；

(2)本发明DA(Distributed Arithmetic)算法，将中间的滤波部分转换成多 路并行的单比特卷积来增大整个滤波器的吞吐量。

附图说明

图1为本发明方法的流程示意图。

图中，下标i表示第i个滤波系数，下标j表示第j条余数支路，上标b表示 第b个比特位。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。

实施例

本实施例以二十四阶的成形滤波器实现为例，研究余数数制(RNS)下滤波， 进而利用DA(Distributed Arithmetic)算法在余数系统设计FIR滤波器的实现方法。 本方法首先因为在RNS下，可以更少的使用资源，所以将滤波输入和滤波系数转 换成余数来完成滤波计算。又利用DA算法，将中间的滤波部分转换成多路并行的 单比特卷积来增大整个系统的吞吐量。最后又利用中国剩余定理(CRT)将余数系 统的数转换成有权十进制数。

如图1所示，本实施基于DA RNS算法的FIR滤波器的实现方法，包括以下 步骤：

步骤一，利用按位查表方法进行十进制有权系统向余数无权系统的转化 (B2R)。本实施例使用6个基(29，31，33，35，59，61)，完全覆盖实现滤波过 程中所有模乘和模加所达到的位宽范围，因此在计算的过程中不会发生溢出。R2B 具体包括以下步骤：

11)为了节省资源，用按位查表的方法取代求模运算。首先，将16位二进制 数每一位为1时在基(29，31，33，35，59，61)下的余数存入ROM中，作为查 询表，如111代表十进制下的15，则最低位的1对29取模为1，则将1存入ROM 中相应的位置，最低第二位的1为2对29取模为2，则将2存入ROM中相应的位 置，第三位为4对29取模为4，则将4存入ROM中相应的位置；

12)输入为十六位有符号数X(Signed16bit)，然后依次判断输入X每一位是 否为1，如果为1则查表进行累加；

13)分别对基29、31、33、35、59、61做同样的运算，最后得到滤波输入X 分别在基(29，31，33，35，59，61)下的余数。

步骤二，将数据分解为单比特形式(Bit Shift)。FPGA在实现FIR滤波器的时 候，对于处理数据X，它的每一位都是分开存放的，故无须过多操作进行拆分。

滤波器公式为$Y={\left|\underset{i=0}{\overset{N-1}{\Sigma }}{C}_i{X}_i\right|}_M---\left(1\right)$

单比特分解后的公式为$Y={\left|\underset{g=1}{\overset{M-1}{\Sigma }}g\underset{i=0}{\overset{N-1}{\Sigma }}\underset{j=0}{\overset{L-1}{\Sigma }}{2}^j{\zeta }_i\left(g\right)x_{i,j}\right|}_M---\left(2\right)$

其中，x_i，j为第i个数的第j个比特位，ζ_i(g)为构造函数，g为设定值，第i个 数的滤波系数C_i在基M下的模等于g时，ζ_i(g)为1，否则为0，N为滤波系数的个 数，L为滤波输入的长度。

步骤三，对数据进行单比特卷积运算(Single Bit Convolution)，将乘法转化为 加法和查表操作，减小了资源的消耗，以基29为例，在其他基下步骤一致：

31)输入基29下的余数，共5bit，每一个比特都进行滤波运算，结果为 d₀，d₁，d₂，d₃，d₄；

32)根据滤波输入的余数对滤波输入进行分组处理，将余数相同的滤波输入分 为一组，以减少计算量；输入的24个需要滤波的数在每组内，根据下述公式，进 行相同比特位加法，乘以系数后累加，再加上常数：

$S_j={\left|\underset{i=0}{\overset{N-1}{\Sigma }}\right[{\alpha }_i+\underset{g=1}{\overset{(M-1)/2}{\Sigma }}g({\zeta }_i\left(g\right)x_{i,j}+\overline{x_{i,j}}{\zeta }_i(M-g))\left]\right|}_M---\left(3\right)$

其中，为x_i，j取反，α_i为第i个滤波系数对应的常数；

33)根据公式(3)，先计算余数相同项的比特相加和，比如系数相同项有4 项，那么比特相加的和最大也就是为4，可以事先算好0，1，2，3，4乘以系数后对应的 值，即可查表；

34)公式前面的常数项，也是事先按照系数相同项，算出对应的值，查表即可。 这样，就算出基29下，第一个比特的卷积和，其他方法相同。

步骤四，通过滤波输入在余数无权系统下的余数对卷积运算后的滤波输入进行 缩放运算(Scaling)，缩放运算的公式为：

y_i＝＜(x_i-＜X_i>k)*(k^-1)>m_i(4)

其中，m_i为基，X_i为要在基m_i下要缩放的数，k为缩放系数，y_i则为缩放之后 在基m_i下的数，x_i为X_i在基m_i下的余数。

本实施例中缩放运算分为两步进行，第一步用k＝61作为缩放常数，第二步用 k＝59做为缩放常数：

41)将61和59的乘法逆元即1/61和1/59，然后将次数左移7位，将所得到 的数保存在相应的ROM中；

42)取第6个基k＝61作为缩放的常数，根据公式(4)，将滤波输入的数X减 去k后，然后乘以k的乘法逆元，因为k的乘法逆元是左移7位存入ROM中的， 所以将计算得到的数右移7位，最后查表得到对应基下的模，舍弃最后一个基的余 数，作为第二步缩放的输入；

43)取第5个基k＝59作为缩放常数，步骤42)的输出，作为这步的输入，然 后重复上一步的操作，进行缩放，即为缩放的最终结果。

步骤五，利用中国剩余定理进行余数向十进制的恢复(R2B)。

51)对缩放运算后得到的基进行分组，分为(29，33)和(31，35)两组；

52)其中一组根据公式(5)计算：

$Y=r_b+\frac{(r_a-r_b)+{\mathrm{\theta m}}_a}{m_b-m_a}*m_b---\left(5\right)$

式中，r_a、r_b分别为对应基m_a、m_b下的余数，θ为常数；

53)将两组的计算结果再进行步骤52)的操作即可得到最后R2B的结果。

以上所述，仅是本发明的较佳实例，本发明所主张的权利范围并不局限于此。 本发明还有其他多种实施例，在不背离本发明精神及其实质的情况下，本领域技术 人员可根据本发明作出各种相应的改变和变形，但这些改变和变形都应属于本发明 所附的权利要求的保护范围。