-
FIR又称为非递归型滤波器,是数字信号处理系统中最基本的模块之一。FIR滤波器在通信、雷达、图像、模式识别等领域都有着广泛的应用[1-3]。某些应用领域如光通信、5G通信系统、高速遥感卫星接收机等,对滤波器的速率要求越来越高,而移动设备、手持终端等领域对设备的功耗有着严格的要求[3]。
文献[3]的研究表明,并行技术可以提高滤波器的信息吞吐率,同时降低设备功耗。然而传统的并行处理方式会使硬件复杂度随并行度线性增加,并行滤波器的硬件效率并没有得到改善,难以支持高并行度的应用。FFA能打破传统并行方式的这种局限性[3-6],可仅用约2L−1个N/L抽头的子滤波器实现L并行N抽头的FIR滤波器[3]。文献[7]提出了基于FFA的2和4并行FIR滤波器的理论形式与结构,文献[8]介绍了基于FFA的8并行FIR滤波器,文献[9]改进了基于FFA的3并行FIR滤波器,文献[10]给出了基于FFA的16并行FIR滤波器的ASIC实现方式。然而,目前的研究工作没有给出基于FFA的2n并行FIR滤波器的通用算法。
此外,在高速FIR滤波器或滤波器组滤波等应用场合[11-12],对FIR滤波器并行度的要求达到了160并行甚至更高。目前基于FFA的算法没有提出针对高并行滤波器的设计架构,很多工程实践仍然采用传统并行FIR滤波器的实现方式,造成了很大的硬件资源浪费。
对此,本文根据已有的基于FFA的2、4、8并行FIR滤波器的理论形式,提出了通用的2n并行FFA,并给出了其相应结构,进一步给出了160并行FFA的实现架构。通过硬件复杂度评估和算法分析,本文提出的算法和实现架构,可以满足高并行度FIR的设计要求,并且算法复杂度和硬件效率较传统方法有显著改善。
-
文献[8]已经推导出了基于FFA的2、4与8并行FIR滤波器的理论形式。本节主要对上述理论形式进行整理,方便后面进行推导和分析。
-
基于FFA的2并行FIR滤波器的算法形式:
$${{Y}_{2p}}{\bf{ = }}{{Q}_2}{{H}_{2p}}{{P}_2}{{X}_{2p}}$$ (1) 式中的滤波器输入为:
$${{X}_{2p}} = {\left[ {{X_0},{X_1}} \right]^{\rm{T}}}$$ (2) 式中,X0和X1分别是输入序列{x(2k)}与{x(2k+1)}的z变换,对于更高并行度情况亦类似。滤波器输出为:
$${{Y}_{2p}} = {\left[ {{Y_0},{Y_1}} \right]^{\rm{T}}}$$ (3) 同样,Y0和Y1分别是输出序列{y(2k)}与{y(2k+1)}的z变换。预加矩阵为:
$${{P}_2} = \left[ {\begin{aligned} & 1 \quad 0\\ & 1 \quad 1\\ & 0 \quad 1 \end{aligned}} \right]$$ (4) 滤波器系数矩阵为:
$${{H}_{2p}} = {\rm{diag}}({{P}_2}{{h}_2})$$ (5) $${{h}_2} = {\left[ {{H_0},{H_1}} \right]^{\rm{T}}} \hspace{17pt} $$ (6) H0和H1分别是滤波器系数序列{h(2k)}与{h(2k+1)}的z变换。后级加法及延时矩阵为:
$${{Q}_2} = \left[ {\begin{array}{*{20}{c}} 1&0&{{z^{ - 2}}}\\ { - 1}&1&{ - 1} \end{array}} \right]$$ (7) -
基于FFA的4并行FIR滤波器的算法形式为:
$${{Y}_{4p}}{\bf{ = }}{{Q}_4}{{H}_{4p}}{{P}_4}{{X}_{4p}}$$ (8) 式中的滤波器输入为:
$${{X}_{4p}} = {\left[ {{X_0},{X_2},{X_1},{X_3}} \right]^{\rm{T}}}$$ (9) 输出为:
$${{Y}_{4p}} = {\left[ {{Y_0},{Y_2},{Y_1},{Y_3}} \right]^{\rm{T}}}$$ (10) 预加矩阵:
$${{P}_4} = {{P}_2} \otimes {{P}_2}$$ (11) 滤波系数矩阵:
$${{H}_{4p}} = {\mathop{\rm diag}\nolimits} ({{P}_4}{{h}_4}) \hspace{17pt} $$ (12) $${{h}_4} = {\left[ {{H_0},{H_2},{H_1},{H_3}} \right]^{\rm{T}}}$$ (13) 后级加法及延时矩阵:
$${{Q}_4} = {{Q}_{{4_2}}}({{{I}}_{3 \times 3}} \otimes {{Q}_{{4_1}}}) $$ (14) $$\begin{split} & {{Q}_{{4_2}}} = \left[ {\begin{array}{*{20}{c}} {{{{I}}_{2 \times 2}}}&{{{O}_{2 \times 2}}}&{\left[ {\begin{array}{*{20}{c}} 0&{{z^{ - 4}}}\\ 1&0 \end{array}} \right]}\\ { - {{{I}}_{2 \times 2}}}&{{{{I}}_{2 \times 2}}}&{ - {{{I}}_{2 \times 2}}} \end{array}} \right]\\ &\qquad\quad {{Q}_{{4_1}}} = \left[ {\begin{array}{*{20}{c}} 1&0&{{z^{ - 4}}}\\ { - 1}&1&{ - 1} \end{array}} \right] \end{split}$$ (15) -
基于FFA的8并行FIR滤波器的算法形式为:
$${{Y}_{8p}}{\bf{ = }}{{Q}_8}{{H}_{8p}}{{P}_8}{{X}_{8p}}$$ (16) 式中的滤波器输入为:
$${{X}_{8p}} = {\left[ {{X_0},{X_4},{X_2},{X_6},{X_1},{X_5},{X_3},{X_7}} \right]^{\rm{T}}}$$ (17) 输出为:
$${{Y}_{8p}} = {\left[ {{Y_0},{Y_4},{Y_2},{Y_6},{Y_1},{Y_5},{Y_3},{Y_7}} \right]^{\rm{T}}}$$ (18) 预加矩阵:
$${{P}_8} = {{P}_2} \otimes ({{P}_2} \otimes {{P}_2})$$ (19) 滤波系数矩阵:
$${{H}_{8p}} = {\rm{diag}}({{P}_8}{{h}_8}) \hspace{75pt} $$ (20) $${{h}_8} = {\left[ {{H_0},{H_4},{H_2},{H_6},{H_1},{H_5},{H_3},{H_7}} \right]^{\rm{T}}}$$ (21) 后级加法及延时矩阵:
$${{Q}_8} = {{Q}_{{8_3}}}({{{I}}_{3 \times 3}} \otimes {{Q}_{{8_2}}})[{{{I}}_{3 \times 3}} \otimes ({{{I}}_{3 \times 3}} \otimes {{Q}_{{8_1}}})]$$ (22) 式中,
$$\begin{split} & {{Q}_{{8_3}}} = \left[ {\begin{array}{*{20}{c}} {{{{I}}_{4 \times 4}}}&{{{O}_{4 \times 4}}}&{\left[ {\begin{array}{*{20}{c}} 0&0&0&{{z^{ - 8}}}\\ 0&0&1&0\\ 1&0&0&0\\ 0&1&0&0 \end{array}} \right]}\\ { - {{{I}}_{4 \times 4}}}&{{{{I}}_{4 \times 4}}}&{ - {{{I}}_{4 \times 4}}} \end{array}} \right]\\ & \qquad {{Q}_{{8_2}}} = \left[ {\begin{array}{*{20}{c}} {{{{I}}_{2 \times 2}}}&{{{O}_{2 \times 2}}}&{\left[ {\begin{array}{*{20}{c}} 0&{{z^{ - 8}}}\\ 1&0 \end{array}} \right]}\\ { - {{{I}}_{2 \times 2}}}&{{{{I}}_{2 \times 2}}}&{ - {{{I}}_{2 \times 2}}} \end{array}} \right]\\ &\qquad \qquad \quad {{Q}_{{8_1}}} = \left[ {\begin{array}{*{20}{c}} 1&0&{{z^{ - 8}}}\\ { - 1}&1&{ - 1} \end{array}} \right] \end{split}$$ (23) -
基于FFA的2、4、8并行FIR滤波器的算法形式,推导出2n并行算法,并设计了基于FFA的2n并行与非2n并行的FIR滤波器整体结构。
-
由式(1)→式(8)→式(16),可归纳得到2n并行的理论形式为:
$${{Y}_{{2^n}p}} = {{Q}_{{2^n}}}{{H}_{{2^n}p}}{{P}_{{2^n}}}{{X}_{{2^n}p}}$$ (24) 由式(2)→式(9)→式(17)可归纳其输入:
$$\begin{split} {{X}_{{2^n}p}} =& [{X_0},{X_{{2^{n - 1}}}},{X_{{2^{n - 2}}}},{X_{{2^{n - 2}} + {2^{n - 1}}}},\\ & {X_{{2^{n - 3}}}},{X_{{2^{n - 3}} + {2^{n - 1}}}}, \cdots ,{X_{{2^{n - 1}} - 1}},{X_{{2^n} - 1}}]_{1 \times {2^n}}^{\rm{T}} \end{split}$$ (25) 由式(3)→式(10)→式(18),归纳得输出为:
$$\begin{split} {{Y}_{{2^n}p}} =& [{Y_0},{Y_{{2^{n - 1}}}},{Y_{{2^{n - 2}}}},{Y_{{2^{n - 2}} + {2^{n - 1}}}},\\ & {Y_{{2^{n - 3}}}},{Y_{{2^{n - 3}} + {2^{n - 1}}}}, \cdots ,{Y_{{2^{n - 1}} - 1}},{Y_{{2^n} - 1}}]_{1 \times {2^n}}^{\rm{T}} \end{split}$$ (26) 对于预加矩阵,由式(4) →式(11)→式(19)推知:
$${{P}_{{2^n}}} = \underbrace {{{P}_2} \otimes \{ {{P}_2} \otimes [{{P}_2} \otimes \cdots \otimes ({{P}_2} \otimes {{P}_2})]\} }_{n{\rm{ - 1\; caculating \;operations}}}$$ (27) 对于滤波系数矩阵,由式(5)→式(12)→式(20)推知:
$${{H}_{{2^n}p}} = {\rm{diag}}({{P}_{{2^n}}}{{h}_{{2^n}}})$$ (28) 由式(6)→式(13)→式(21)推知:
$$\begin{split} {{h}_{{2^n}}} =& [{H_0},{H_{{2^{n - 1}}}},{H_{{2^{n - 2}}}},{H_{{2^{n - 2}} + {2^{n - 1}}}},{H_{{2^{n - 2}}}},\\ & {H_{{2^{n - 3}} + {2^{n - 1}}}}, \cdots ,{H_{{2^{n - 1}} - 1}},{H_{{2^n} - 1}}]_{1 \times {2^n}}^{\rm{T}} \end{split}$$ (29) 对于后级加法及延时矩阵,由式(7)→式(14)→式(22)推知:
$$\begin{split} {{Q}_{{2^n}}} = & {{Q}_{{2^n}_n}}({{{I}}_{3 \times 3}} \otimes {{Q}_{{2^n}_{n - 1}}})[{{{I}}_{3 \times 3}} \otimes ({{{I}}_{3 \times 3}} \otimes {{Q}_{{2^n}_{n - 2}}})]\\ & \times \cdots \times \{ {{{I}}_{3 \times 3}} \otimes [{{{I}}_{3 \times 3}} \otimes \cdots \otimes ({{{I}}_{3 \times 3}} \otimes {{Q}_{{2^n}_1}})]\} \end{split}$$ (30) 由式(7)→式(15)→式(23)可归纳得:
$$\begin{split} & \quad\quad\qquad{{Q}_{{2^n}_1}} = \left[ {\begin{array}{*{20}{c}} 1&0&{{{A}_1}}\\ { - 1}&1&{ - 1} \end{array}} \right]\\ &\qquad\quad {{Q}_{{2^n}_2}} = \left[ {\begin{array}{*{20}{c}} {{{{I}}_{2 \times 2}}}&{{{O}_{2 \times 2}}}&{{{A}_2}}\\ { - {{{I}}_{2 \times 2}}}&{{{{I}}_{2 \times 2}}}&{ - {{{I}}_{2 \times 2}}} \end{array}} \right]\\ & \qquad\qquad\qquad\qquad\qquad \vdots \\ & {{Q}_{{2^n}_n}} = \left[ {\begin{array}{*{20}{c}} {{{{I}}_{{2^{n - 1}} \times {2^{n - 1}}}}}&{{{O}_{{2^{n - 1}} \times {2^{n - 1}}}}}&{{{A}_n}}\\ { - {{{I}}_{{2^{n - 1}} \times {2^{n - 1}}}}}&{{{{I}}_{{2^{n - 1}} \times {2^{n - 1}}}}}&{ - {{{I}}_{{2^{n - 1}} \times {2^{n - 1}}}}} \end{array}} \right] \end{split}$$ (31) 式中,Ak满足:
$$\begin{split} & \quad\quad\qquad\qquad{{A}_1} = [{{z}^{ - {2^n}}}]\\ & {{A}_k} = \left[ {\begin{array}{*{20}{c}} {{{O}_{{2^{k - 2}} \times {2^{k - 2}}}}}&{{{A}_{k - 1}}}\\ {{{{I}}_{{2^{k - 2}} \times {2^{k - 2}}}}}&{{{O}_{{2^{k - 2}} \times {2^{k - 2}}}}} \end{array}} \right]\quad k = 2,3, \cdots ,n \end{split}$$ (32) 所归纳的式(24)~式(32)即为基于FFA的通用2n并行FIR滤波器的算法形式。分析式(24)~式(32)可以看出,2n并行FIR算法保持了原FIR滤波器的传递函数,因此该算法具有与原FIR滤波器的信号处理性能。
-
根据2.1节中的算法形式,对基于FFA的2n并行FIR滤波器架构进行设计。
式(24)对结构设计起主要指导作用。
${{P}_{{2^n}}}{{X}_{{2^n}p}}$ 意味着首先要进行对输入的预加操作;${{H}_{{2^n}p}}({{P}_{{2^n}}}{{X}_{{2^n}p}})$ 则说明接下来对预加的结果进行子滤波;${{Q}_{16}}{(}{{H}_{{2^n}p}}{{P}_{{2^n}}}$ ${{X}_{{2^n}p}}) $ 则指导着对子滤波结果的后级加法与延时。如此,再根据式(25)~(32)的具体指导,可得到基于FFA的2n并行FIR滤波器架构,如图1所示。图中,预加处理子模块实现对2n并行输入数据的预加操作,预加后得到3n路输出。并行滤器子模块含3n路子滤波器,完成对3n路输入数据的子滤波操作。延时及后加处理子模块完成对子滤波结果的后级加法及延时功能,得到2n并行输出。这样,达到2n并行滤波的目的。 -
对于非2n并行的FFA,可以用较低并行度的基于FFA的并行FIR滤波器组设计高并行度滤波器,本文设计并实现了基于FFA的160并行FIR滤波器。由于
$160{\rm{ = }}20 \times 8$ ,因此可以用20个基于FFA的8并行FIR滤波器组构建基于FFA的160并行FIR滤波器。其设计结构如图2所示。 -
设计一个L并行N−1阶的FIR滤波器,若多相滤波方式,需要NL个乘法器及 (N−1)L个加法器。
若基于FFA实现,当L=2时,需要3N/2个乘法器实现;当L=4时,需要9N/4个乘法器;当L=8时,需要27N/8个乘法器;L=16时,需要81N/16个乘法器。那么,可以归纳出基于FFA的2n并行N−1阶FIR滤波器所需乘法器的个数为3nN/2n,所需加法器数量需要具体计算。
由此,可以统计出N−1阶不同并行度下,传统方式与基于FFA方式并行FIR滤波器的乘法器数量的对比情况,如表1所示。
表 1 设计N−1阶FIR在不同方案下乘法器数目统计表
并行FIR 2并行 4并行 8并行 16并行 32并行 ${2^n}$并行 传统并行 $2N$ $4N$ $8N$ $16N$ $32N$ $N{2^n}$ FFA $3N/2$ $9N/4$ $27N/8$ $81N/16$ $243N/32$ $N{3^n}/{2^n}$ FFA相对于传统并行节约/% 25.00 43.75 57.81 68.36 76.27 $[1 - {(3/4)^n}]\times 100 $ 由表1可知,基于FFA的并行FIR滤波器所需乘法器个数少于传统方式。且随着并行度的增加,FFA相对于传统方式将节省更多的乘法器资源。
-
在硬件实现过程中,在计算单元层面,假设传统并行FIR结构中加法器的整数位宽为m bit,小数位宽为n bit。由于FFA架构在前级有预加运算,如16并行FFA在前级最多会有16个数的预加,若仍然采用m bit的整数位宽,会存在运算溢出的情况。此时,需要拓宽预加16个数的加法器的整数位宽至m+4 bit。这样,会使FFA加法器及乘法器的复杂度高于传统FIR滤波器。并且相同并行度下FFA的加法器个数也多于传统方式。由于FFA相比传统方式能节约大量的乘法器,所以高效2n并行FFA还是有显著增益。
为了评估硬件资源总体的收益情况,针对高速光纤通信系统需要的7阶160并行FIR滤波器进行设计实现。其架构如图2所示。根据前文所述算法性能的分析,在计算单元层面,传统方式与本文提出的方式的加法器和乘法器的复杂度不尽相同。为了对比分析,采用本文提出的设计方法和传统的设计方法对该滤波器在FGPA上进行资源评估。资源评估按FPGA上对应IPCORE所占用的查找表LUTs等效折算,所使用FPGA为Xilinx XC7K325T,乘法器IPCORE使用Multiplier 11.2中的常系数乘法器。最终,基于FFA的方法比传统方法的乘法器资源缩减了56.3%,总资源缩减了36.2%,如表2所示。
表 2 7阶160并行FIR滤波器FPGA资源评估
并行FIR 运算 规格/bit 数量 单个所占LUT 总LUT 总资源 传统方法 乘法 9×8 8×160 36 46 080 60 960 加法 10 1×160 11 1 760 12 2×160 13 4 160 13 4×160 14 8 960 本文方法 乘法 9×8 1×20 36 720 10×8 18×20 37 13 320 11×8 8×20 38 6 080 加法 9 8×20 10 1 600 38 880 10 30×20 11 6 600 11 20×20 12 4 800 15 18×20 16 5 760
High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method
-
摘要: 快速有限脉冲响应(FIR)算法(FFA)突破了传统并行FIR滤波器复杂度随并行度线性增加的局限性,效率大幅提高。然而目前缺少对高并行FFA通用算法和实现架构的研究。该文提出了高效2n并行FFA,并给出了其通用算法形式与实现架构;同时讨论了对于非2n并行FFA的实现架构。通过算法分析和硬件效率评估,本文算法及其实现架构在相同的并行度和性能条件下,比传统并行算法有显著改善,且随着并行度的增加,这种优势更加明显。该算法在高并行FIR滤波器的应用中有很大优势。Abstract: Fast finite impulse response (FIR) algorithm (FFA) can break the limitation that the hardware complexity of traditional parallel algorithm linearly increases with the degree of parallelism, which can improve FIR algorithm efficiency. However, there is few research focusing on the general algorithm and implementation structure for high-parallelism FFA. In this case, we propose high-efficiency 2n-parallel general FFA and its implementation structure. We also provide the high-parallelism FFA structure with non-2n-parallelism. According to the algorithm analysis and hardware efficiency estimation, we know that the efficient 2n-parallel FFA algorithm and structure proposed in this paper can achieve significant advantage over traditional methods, and this advantage is becoming more obvious with the parallelism increasing. Thus, the proposed high-efficiency 2n-parallel FFA can be used for the implementation of high-parallelism FIR filters.
-
Key words:
- 2n-parallel /
- FFA /
- FIR filter /
- hardware efficiency
-
表 1 设计N−1阶FIR在不同方案下乘法器数目统计表
并行FIR 2并行 4并行 8并行 16并行 32并行 ${2^n}$ 并行传统并行 $2N$ $4N$ $8N$ $16N$ $32N$ $N{2^n}$ FFA $3N/2$ $9N/4$ $27N/8$ $81N/16$ $243N/32$ $N{3^n}/{2^n}$ FFA相对于传统并行节约/% 25.00 43.75 57.81 68.36 76.27 $[1 - {(3/4)^n}]\times 100 $ 表 2 7阶160并行FIR滤波器FPGA资源评估
并行FIR 运算 规格/bit 数量 单个所占LUT 总LUT 总资源 传统方法 乘法 9×8 8×160 36 46 080 60 960 加法 10 1×160 11 1 760 12 2×160 13 4 160 13 4×160 14 8 960 本文方法 乘法 9×8 1×20 36 720 10×8 18×20 37 13 320 11×8 8×20 38 6 080 加法 9 8×20 10 1 600 38 880 10 30×20 11 6 600 11 20×20 12 4 800 15 18×20 16 5 760 -
[1] ARIYADOOST H, KAVIAN Y S, ANSARI-ASL K. Two dimensional systolic adaptive DLMS FIR filters for image processing on FPGA[C]//20th Iranian Conference on Electrical Engineering (ICEE2012). Tehran, Iran: [s.n.], 2012: 243-248. [2] ZHANG Y, HE W, HONG W, et al. Flat topped radiation pattern synthesis based on FIR filter concept[C]//2017 IEEE Asia Pacific Microwave Conference (APMC). Kuala Lumpar, Malaysia: IEEE, 2017: 751-754. [3] TIAN J, LI G, LI Q. Hardware-efficient parallel structures for linear-phase FIR digital filter[C]//2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS). Columbus, USA: IEEE, 2013: 995-998. [4] SELVAKUMAR J, BHASKAR V, NARENDRAN S. FPGA based efficient fast FIR algorithm for higher order digital fir filter[C]//2012 International Symposium on Electronic System Design (ISED). Kolkata, India: [s.n.], 2012: 43-47. [5] LEIGH G M. Fast FIR algorithms for the continuous wavelet transform from constrained least squares[J]. IEEE Transactions on Signal Processing, 2013, 61(1): 28-37. doi: 10.1109/TSP.2012.2222376 [6] KYRITSIS E, PEKMESTZI K. Hardware efficient fast FIR filter based on Karatsuba algorithm[C]//2016 5th International Conference on Modern Circuits and Systems Technologies (MOCAST). Thessaloniki, Greece: [s.n.], 2016: 1-4. [7] PARKER D A, PARHI K K. Area-efficient parallel FIR digital filter implementations[C]//Proceedings of International Conference on Application Specific Systems, Architectures and Processors. Chicago, USA: [s.n.], 1996: 93-111. [8] PARHI K K. VLSI digital signal processing systems: Design and implementation[M]. New York: John Wiley & Sons, 2007. [9] TSAO Y C, CHOI K. Hardware-efficient VLSI implementation for 3-parallel linear-phase FIR digital filterof odd length[C]//2012 IEEE International Symposium on Circuits and Systems. Seoul, Korea: IEEE, 2012: 998-1001. [10] ANNANGI S, PULI R. ASIC implementation of efficient 16-parallel fast FIR algorithm filter structure[C]//2017 8th International Conference on Computing, Communication and Networking Technologies (ICCCNT). Delhi, India: IEEE, 2017: 1-5. [11] LEI M, MA Z. Design of high-speed FIR filter with distributed parallel structure[C]//2016 IEEE Information Technology, Networking, Electronic and Automation Control Conference. Chongqing, China: IEEE, 2016: 511-514. [12] PARK S, SHIN D, KOH K J, et al. A low-power 3.25GS/s 4th-order programmable analog FIR filter using split-CDAC coefficient multipliers for wideband analog signal processing[C]//2018 IEEE International Solid-State Circuits Conference (ISSCC). San Francisco, USA: IEEE, 2018: 62-64.