留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

高效2n并行快速FIR算法及其实现方法

胡剑浩 曾维棋 费超 陈杰男

胡剑浩, 曾维棋, 费超, 陈杰男. 高效2n并行快速FIR算法及其实现方法[J]. 电子科技大学学报, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
引用本文: 胡剑浩, 曾维棋, 费超, 陈杰男. 高效2n并行快速FIR算法及其实现方法[J]. 电子科技大学学报, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
HU Jian-hao, ZENG Wei-qi, FEI Chao, CHEN Jie-nan. High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
Citation: HU Jian-hao, ZENG Wei-qi, FEI Chao, CHEN Jie-nan. High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076

高效2n并行快速FIR算法及其实现方法

doi: 10.12178/1001-0548.2018076
基金项目: 国家自然科学基金(61571083)
详细信息
    作者简介:

    胡剑浩(1971 − ),男,教授,主要从事通信信号处理方面的研究. E-mail: jhhu@uestc.edu.cn

  • 中图分类号: TN713

High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method

  • 摘要: 快速有限脉冲响应(FIR)算法(FFA)突破了传统并行FIR滤波器复杂度随并行度线性增加的局限性,效率大幅提高。然而目前缺少对高并行FFA通用算法和实现架构的研究。该文提出了高效2n并行FFA,并给出了其通用算法形式与实现架构;同时讨论了对于非2n并行FFA的实现架构。通过算法分析和硬件效率评估,本文算法及其实现架构在相同的并行度和性能条件下,比传统并行算法有显著改善,且随着并行度的增加,这种优势更加明显。该算法在高并行FIR滤波器的应用中有很大优势。
  • 图  1  基于FFA的2n并行FIR滤波器架构

    图  2  基于FFA的160并行FIR滤波器架构

    表  1  设计N−1阶FIR在不同方案下乘法器数目统计表

    并行FIR2并行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.0043.7557.8168.3676.27$[1 - {(3/4)^n}]\times 100 $
    下载: 导出CSV

    表  2  7阶160并行FIR滤波器FPGA资源评估

    并行FIR运算规格/bit数量单个所占LUT总LUT总资源
    传统方法乘法9×88×1603646 08060 960
    加法101×160111 760
    122×160134 160
    134×160148 960
    本文方法乘法9×81×2036720
    10×818×203713 320
    11×88×20386 080
    加法98×20101 60038 880
    1030×20116 600
    1120×20124 800
    1518×20165 760
    下载: 导出CSV
  • [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.
  • [1] 李志鹏, 李兴和, 黄虎, 饶申宇.  无数字时延滤波器的宽带大规模阵列雷达去斜算法 . 电子科技大学学报, 2022, 51(3): 371-376. doi: 10.12178/1001-0548.2021395
    [2] 董玉民, 侯栋, 耿馨雨, 胡万斌.  基于多量子滤波器的QCNN算法预测厌氧消化性能 . 电子科技大学学报, 2022, 51(5): 651-659. doi: 10.12178/1001-0548.2022268
    [3] 马东, 师奕兵, 张伟, 柳国振.  基于钻柱声波信道的随钻数据V-OFDM传输方法研究 . 电子科技大学学报, 2017, 46(1): 46-54. doi: 10.3969/j.issn.1001-0548.2017.01.008
    [4] 刘强, 马建国.  提高SoC硬件系统验证效率方法的综述 . 电子科技大学学报, 2013, 42(2): 162-170. doi: 10.3969/j.issn.1001-0548.2013.02.001
    [5] 甘露, 易舟维, 李立萍.  基于L0范数约束非相邻系数FIR数字滤波器设计 . 电子科技大学学报, 2013, 42(2): 200-204. doi: 10.3969/j.issn.1001-0548.2013.02.004
    [6] 张振东, 吴斌, 周玉梅.  用于FIR滤波器设计的共同子表达式消除新方法 . 电子科技大学学报, 2013, 42(1): 48-52. doi: 10.3969/j.issn.1001-0548.2013.01.012
    [7] 李辉, 李平, 王忆文.  硬件资源消耗少的IMDCT分解算法 . 电子科技大学学报, 2011, 40(1): 26-29. doi: 10.3969/j.issn.1001-0548.2011.01.005
    [8] 屈剑锋, 柴毅, 郭茂耘.  无线传感器网络下的并行粒子滤波目标跟踪算法 . 电子科技大学学报, 2011, 40(2): 231-236. doi: 10.3969/j.issn.1001-0548.2011.02.015
    [9] 马上, 胡剑浩, 叶燕龙.  以{2n-1,2n,2n+1}为基的余数系统2n高性能缩放 . 电子科技大学学报, 2010, 39(2): 306-310,278. doi: 10.3969/j.issn.1001-0548.2010.02.033
    [10] 覃岭, 邓小炜, 何子述, 段军棋.  宽带数字下变频的高效实现方法研究 . 电子科技大学学报, 2008, 37(5): 698-700,708.
    [11] 陈凯亚, 王敏锡.  二阶伏特拉滤波器RLS算法改进 . 电子科技大学学报, 2005, 34(4): 467-469,473.
    [12] 甘露, 李会勇, 徐政五.  最陡下降算法在MTD滤波器设计中的应用 . 电子科技大学学报, 2005, 34(5): 593-595.
    [13] 魏永豪, 袁晓, 滕旭东, 赵元英.  广义希尔伯特变换及其数字实现 . 电子科技大学学报, 2005, 34(2): 175-178.
    [14] 补世荣, 羊恺, 罗正祥.  复杂耦合超导滤波器 . 电子科技大学学报, 2003, 32(4): 409-412.
    [15] 何元清, 孙世新, 陈文宇.  网络通信延迟对并行效率的影响 . 电子科技大学学报, 2002, 31(2): 156-158.
    [16] 谭小刚.  多抽样率频率抽样FIR数字滤波器设计 . 电子科技大学学报, 2002, 31(5): 460-464.
    [17] 韩蒙.  网络集中器的硬件设计 . 电子科技大学学报, 2001, 30(3): 284-286.
    [18] 王玉林.  利用Bernstein多项式设计FIR槽状滤波器 . 电子科技大学学报, 2000, 29(3): 252-255.
    [19] 范勇, 王兆明, 黄香馥.  快速并行σi预测CORDIC算法 . 电子科技大学学报, 1998, 27(1): 29-32.
    [20] 杨朝斌, 徐继麟, 黄香馥.  SAW滤波器等效电路模型参数的精确计算法 . 电子科技大学学报, 1997, 26(1): 40-43.
  • 加载中
图(2) / 表(2)
计量
  • 文章访问数:  7604
  • HTML全文浏览量:  1990
  • PDF下载量:  79
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-03-29
  • 修回日期:  2019-11-18
  • 网络出版日期:  2020-03-17
  • 刊出日期:  2020-03-01

高效2n并行快速FIR算法及其实现方法

doi: 10.12178/1001-0548.2018076
    基金项目:  国家自然科学基金(61571083)
    作者简介:

    胡剑浩(1971 − ),男,教授,主要从事通信信号处理方面的研究. E-mail: jhhu@uestc.edu.cn

  • 中图分类号: TN713

摘要: 快速有限脉冲响应(FIR)算法(FFA)突破了传统并行FIR滤波器复杂度随并行度线性增加的局限性,效率大幅提高。然而目前缺少对高并行FFA通用算法和实现架构的研究。该文提出了高效2n并行FFA,并给出了其通用算法形式与实现架构;同时讨论了对于非2n并行FFA的实现架构。通过算法分析和硬件效率评估,本文算法及其实现架构在相同的并行度和性能条件下,比传统并行算法有显著改善,且随着并行度的增加,这种优势更加明显。该算法在高并行FIR滤波器的应用中有很大优势。

English Abstract

胡剑浩, 曾维棋, 费超, 陈杰男. 高效2n并行快速FIR算法及其实现方法[J]. 电子科技大学学报, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
引用本文: 胡剑浩, 曾维棋, 费超, 陈杰男. 高效2n并行快速FIR算法及其实现方法[J]. 电子科技大学学报, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
HU Jian-hao, ZENG Wei-qi, FEI Chao, CHEN Jie-nan. High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
Citation: HU Jian-hao, ZENG Wei-qi, FEI Chao, CHEN Jie-nan. High-Efficiency 2n-Parallel Fast FIR Algorithm and Its Implementation Method[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(2): 182-186. doi: 10.12178/1001-0548.2018076
  • 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)

      式中,X0X1分别是输入序列{x(2k)}与{x(2k+1)}的z变换,对于更高并行度情况亦类似。滤波器输出为:

      $${{Y}_{2p}} = {\left[ {{Y_0},{Y_1}} \right]^{\rm{T}}}$$ (3)

      同样,Y0Y1分别是输出序列{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)

      H0H1分别是滤波器系数序列{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所示。

      图  1  基于FFA的2n并行FIR滤波器架构

      图  2  基于FFA的160并行FIR滤波器架构

    • 设计一个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在不同方案下乘法器数目统计表

      并行FIR2并行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.0043.7557.8168.3676.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×88×1603646 08060 960
      加法101×160111 760
      122×160134 160
      134×160148 960
      本文方法乘法9×81×2036720
      10×818×203713 320
      11×88×20386 080
      加法98×20101 60038 880
      1030×20116 600
      1120×20124 800
      1518×20165 760
    • 本文根据已有的基于FFA的2、4、8并行FIR滤波器的理论形式,推导了2n并行FFA,然后设计了2n并行FFA及非2n并行FFA的架构。接着,对比了在不同并行度下,高效2n并行FFA与传统并行算法实现的乘法器数目,发现随着并行度的增加前者的优势越发明显。最后,从计算性能以及计算单元层次上分析了该算法,得出结论:虽然高效2n并行FFA相对于传统并行算法会增加若干加法器与乘法器的复杂度,但是由于前者对乘法器资源增益明显,所以其硬件效率较传统并行算法仍有显著改善,且随着并行度增加,这种优势会更加明显。

参考文献 (12)

目录

    /

    返回文章
    返回