剖析子项空间技术的低复杂度FIR滤波器实现
摘要： 基于子项空间共享技术，利用硬件描述语言编程，在fpga上对fir数字滤波器进行了实现。该设计将常系数乘法模块用加法和移位操作来实现，并利用子项共享有效地减少加法器个数。综合结果表明，所提方法可以有效节省硬件资源，降低实现成本，适用于低功耗数字系统设计。
当前在信息与通信领域，无论是为了解决能源问题还是满足产品本身的需要，如何设计低功耗通信电子产品已成为当前国际上的研究热点之一。数字滤波器是各类电子系统中重要的组成部分，从实现的网络结构上可分为有限冲激响应（fir）滤波器和无限冲激响应（iir）滤波器。对同样的设计要求，fir滤波器通常比iir滤波器需要更高的阶数，但fir滤波器较iir滤波器更为优化和简单，且能保证绝对稳定和线性相位，因此在语音图像处理、数字电视系统等领域都得到了极广泛的应用［1-2］。
数字滤波器实质上是一系列包括加法、乘法和数据传输在内的运算，最终要用物理器件来实现。当把这些设计好的数字滤波器用现场可编程门阵列（fpga）器件来实现时［3］，通常用综合后的逻辑单元le（logic element）数来衡量硬件消耗。子项空间技术利用滤波器系数之间的子项共享，可以有效减少滤波器实现时加法器的个数［4-8］，从而降低实现复杂度，节省硬件资源。
1 子项空间及子项共享
图1（a）为fir滤波器的转置型结构。在这种结构中，输入信号与滤波器的各个常系数h（k）（k=0，1，…，n-1）相乘并送入延时单元，这种操作通常被称为多常数乘法mcm（multiple constants multiplication）问题［9］，可以用移位寄存器和加法器网络来实现。因此，加法器可以进一步分为延迟单元的结构加法器sa（structural adders）和常数乘法单元的加法器mba（multiplier block adders），如图1（b）所示。当滤波器阶数固定后，延时单元和sa的数量相对固定（除非有些系数为0，sa会有所减少），因此fir滤波器的实现复杂度主要决定于mba的个数。
一个离散子项空间中的元素可以通过下式构建［4］：
不论是单个系数内部，还是多个系数之间，用来实现公共子项的加法器都可以共享，从而达到减少加法器个数的目的。下面举例说明：
（1）假设某个系数用二进制序列表示为1010101，如果直接实现，则需要3个加法器，如图2（a）所示；如果将公共子项101提取出来先实现，则只需要2个加法器，如图2（b）所示。
（2）假设某两个系数用二进制序列表示分别为100101和10101，若两个系数独立实现，则每个系数都需要2个加法器，即总共需要4个加法器，如图3（a）所示;而将公共子项101提取出来先实现，则每个系数只需要增加1个额外的加法器，即总共需要3个加法器，如图3（b）所示。因此，合理利用子项共享，可有效降低数字滤波器的硬件消耗 ［4］。
2 fpga内部结构及综合特点
硬件描述语言hdl（hardware description language）支持行为级（behavioral level）、寄存器传输级rtl（register transfer level）和门级（gate level）3个不同级别的设计，目前普遍使用寄存器传输级源代码进行设计。综合是把设计转化为可制造器件的转移过程，而该器件能执行预期的功能。
fpga是专用集成电路（asic）领域中的一种半定制电路，应用非常广泛，经常作为高阶数字滤波器的实现器件。altera公司的fpga器件一般由二维的行列结构来实现用户自定义逻辑，内部最小的逻辑单元le可以高效地实现用户逻辑函数［10］。一个le主要由一个4输入查找表、一个寄存器及进位和互连逻辑组成。查找表简称为lut，lut本质上是一个ram。
当用户通过原理图或hdl语言描述了一个逻辑电路后，fpga开发软件会自动计算逻辑电路所有可能的结果，并把结果事先写入ram，这样每输入一个信号进行逻辑运算就等于输入一个地址进行查表，找出地址所对应的内容后输出即可。也可以把le当作一个4输入的函数发生器，能够实现4变量输入的所有逻辑［10］。
由于rtl级设计不涉及具体的工艺，不同的综合工具、不同的器件类型可能会产生不同的综合结果，即所需要的le数量会有差异。因此，在同一种综合工具、同一种器件类型的前提下对不同的实现方法进行比较。
3 基于verilog hdl的rtl级实现
verilog hdl是目前广泛使用的ieee标准硬件描述语言，可以用不同的工具进行综合和验证。本文基于子项空间共享技术，采用verilog hdl进行fir数字滤波器的rtl级描述。下面举例介绍具体的实现方法。以参考文献［4］中的较低阶滤波器s1为例，下面给出滤波器s1的系数，其中，h（n）=h（24-n），13≤n≤24；通带增益为485.268 2。
h（12）=3×26-1×20；h（11）=5×25-1×24；h（10）=3×24；
h（9）=-3×23；h（8）=-1×25；h（7）=-3×20；h（6）=1×24；
h（5）=5×21；h（4）=-1×22；h（3）=-1×23；h（2）=-1×21；
h（1）=3×20；h（0）=1×21。
由上可知，s1对应基组为{3，5}，此基组的阶数等于2，即产生基组需要2个加法器，由基组产生滤波器系数需要2个加法器，因此，mba的个数为4，系数都不为零；sa的个数为24。
（1）子项基组的产生
assign x3={x_n，1‘b0}+ x_n； //x_n为输入信号
assign x5={x_n，2’b00}+x_n；
（2）mba的实现
利用已经产生的基组，参照s1的系数，就可以得到mba部分各常系数乘法的值，部分程序段如下：
assign mba12={x3，6‘b000000}-x_n； //实现h［12］×x_n
……
assign mba0 = {x_n，1’b0}； //实现h［0］×x_n
（3）延时单元和sa的实现
例s1中不存在值为0的系数，且考虑到线性相位fir滤波器系数对称，因此程序段如下：
delay_sa0 《= mba0；
delay_sa1 《= delay_sa0 + mba1；
……
delay_sa11 《= delay_sa10 + mba11；
delay_sa12 《= delay_sa11 + mba12；
delay_sa13 《= delay_sa12 + mba11；
……
delay_sa23 《= delay_sa22 + mba1；
delay_sa24《= delay_sa23 + mba0；
（4）输出的实现
考虑到s1的系数在有限字长实现时单位脉冲响应乘以512（=29）倍，因此在输出时要进行截短处理，即去掉低9位。
4 综合结果
本节将选取参考文献［4］中的4个例子分别在fpga上进行综合比较。4个例子的性能指标如表1所示。
参考文献［4］中基于子项共享进行系数离散化得到的结果如表2所示，具体的滤波器系数参见参考文献［4］。
如前所述，fpga实现硬件资源的消耗可以通过综合后le的数量来衡量。分别选择cyclone系列的ep1-
c12q240c8和apex20ke系列的 ep20k600ebc652-3两种型号的fpga对4个滤波器两种不同的实现方法（子项共享实现和直接实现）进行综合，综合工具选用quartus ii，结果如表3所示。
从表3可以看出，基于子项共享的实现可以有效减少fpga中le的消耗数量，且滤波器阶数越高，共享的机会越大，效果越好。
本文通过verilog hdl编程在fpga上实现了子项共享的fir数字滤波器设计。子项空间共享技术可以有效地减少fir滤波器实现时加法器的个数，从而使得综合后消耗的le数量明显减少，有利于数字系统的低成本、低功耗设计，具有实际的应用意义。
参考文献
［1］ 唐博，李锦明，李士照。基于fpga的高阶fir滤波器强抗干扰数据采集系统［j］。电子技术应用，2012，38（9）：89-92.
［2］ 林志典，张方佩，袁国顺。基于fpga的高速fir滤波器的设计与实现［j］。微电子学，2013，43（4）：200-202.
［3］ 惠鹏飞，姚仲敏，夏颖，等。基于fpga的无线传感网络信道波形整形滤波器［j］。电子技术应用，2013，39（7）：35-37.
［4］ yu y j，lim y c.design of linear phase fir filters in subexpression space using mixed integer linear programming［j］.ieee trans.circuits syst.i，2007，54（10）：2330-2338.
［5］ yu y j，lim y c.optimization of linear phase fir filters in dynamically expanding subexpression space［j］.circuit syst.signal process.，2010，29（1）：65-80.
［6］ shi d，yu y j.design of linear phase fir filters with high probability of achieving minimum number of adders［j］.ieee trans.circuits syst.i，2011，58（1）：126-136.
［7］ potkonjak m，shrivasta m b，chandrakasan a p.multiple constant multiplication：efficient and versatile framework and algorithms for exploring common subexpression elimination［j］.ieee trans.comput.aided，1996，15（2）：151-165.
［8］ xu fei，chang c h，jong c c.design of low-complexity fir filters based on signed-powers-of-two coefficients with reusable common subexpressions［j］.ieee trans.comput.aided，2007，26（10）：1898-1907.
［9］ wang y，roy k.csdc：a new complexity reduction technique for multiplierless implementation of fir filters［j］.ieee trans.circuits sysm.i，2005，52（9）：1845-1853.
［10］ altera公司.cyclone2系列器件数据手册：cyclone device handbook，volume 1［z］.2007.
iPhone 14系列手机将推出新的配色
Cirrus Logic宣布同意收购Lion Semiconductor
铝壳气体耐压爆破两不误，新能源动力电池壳体测试设备全面升级
设计经验谈：模拟地与信号地的区别
卡尔曼滤波的总结和思维扩展
剖析子项空间技术的低复杂度FIR滤波器实现
传音拍照专利解决人体肤色差异
这次换亚菲特克莱斯勒的汽车排放作假连环爆
除了谷歌“亲儿子” 还有Galaxy S8、诺基亚8...这些手机都能升级Android 8.0
华为收到美国商务部传票 聚焦向制裁国家出口技术问题
基于混合信号FPGA的功率管理解决方案
NVIDIA全新架构将向新一代超级计算机发起冲击
数字D类音频功率放大器设计方案
NVIDIA RTX GPU助力打造城市新区绿化
中国移动打造湖北首家5G智慧医院
HLPM025K3 PM2.5传感器的驱动设计与实现
传感器的新应用有哪些？传感器产业发展的痛点
中兴通讯助力浙江移动完成5G消息平台建设
华为mate10/mate10pro还未发布就来真机开箱:这颜值你觉得多少钱合适?
三星银河A52在印度的发布指日可待
当前在信息与通信领域，无论是为了解决能源问题还是满足产品本身的需要，如何设计低功耗通信电子产品已成为当前国际上的研究热点之一。数字滤波器是各类电子系统中重要的组成部分，从实现的网络结构上可分为有限冲激响应（fir）滤波器和无限冲激响应（iir）滤波器。对同样的设计要求，fir滤波器通常比iir滤波器需要更高的阶数，但fir滤波器较iir滤波器更为优化和简单，且能保证绝对稳定和线性相位，因此在语音图像处理、数字电视系统等领域都得到了极广泛的应用［1-2］。
数字滤波器实质上是一系列包括加法、乘法和数据传输在内的运算，最终要用物理器件来实现。当把这些设计好的数字滤波器用现场可编程门阵列（fpga）器件来实现时［3］，通常用综合后的逻辑单元le（logic element）数来衡量硬件消耗。子项空间技术利用滤波器系数之间的子项共享，可以有效减少滤波器实现时加法器的个数［4-8］，从而降低实现复杂度，节省硬件资源。
1 子项空间及子项共享
图1（a）为fir滤波器的转置型结构。在这种结构中，输入信号与滤波器的各个常系数h（k）（k=0，1，…，n-1）相乘并送入延时单元，这种操作通常被称为多常数乘法mcm（multiple constants multiplication）问题［9］，可以用移位寄存器和加法器网络来实现。因此，加法器可以进一步分为延迟单元的结构加法器sa（structural adders）和常数乘法单元的加法器mba（multiplier block adders），如图1（b）所示。当滤波器阶数固定后，延时单元和sa的数量相对固定（除非有些系数为0，sa会有所减少），因此fir滤波器的实现复杂度主要决定于mba的个数。
一个离散子项空间中的元素可以通过下式构建［4］：
不论是单个系数内部，还是多个系数之间，用来实现公共子项的加法器都可以共享，从而达到减少加法器个数的目的。下面举例说明：
（1）假设某个系数用二进制序列表示为1010101，如果直接实现，则需要3个加法器，如图2（a）所示；如果将公共子项101提取出来先实现，则只需要2个加法器，如图2（b）所示。
（2）假设某两个系数用二进制序列表示分别为100101和10101，若两个系数独立实现，则每个系数都需要2个加法器，即总共需要4个加法器，如图3（a）所示;而将公共子项101提取出来先实现，则每个系数只需要增加1个额外的加法器，即总共需要3个加法器，如图3（b）所示。因此，合理利用子项共享，可有效降低数字滤波器的硬件消耗 ［4］。
2 fpga内部结构及综合特点
硬件描述语言hdl（hardware description language）支持行为级（behavioral level）、寄存器传输级rtl（register transfer level）和门级（gate level）3个不同级别的设计，目前普遍使用寄存器传输级源代码进行设计。综合是把设计转化为可制造器件的转移过程，而该器件能执行预期的功能。
fpga是专用集成电路（asic）领域中的一种半定制电路，应用非常广泛，经常作为高阶数字滤波器的实现器件。altera公司的fpga器件一般由二维的行列结构来实现用户自定义逻辑，内部最小的逻辑单元le可以高效地实现用户逻辑函数［10］。一个le主要由一个4输入查找表、一个寄存器及进位和互连逻辑组成。查找表简称为lut，lut本质上是一个ram。
当用户通过原理图或hdl语言描述了一个逻辑电路后，fpga开发软件会自动计算逻辑电路所有可能的结果，并把结果事先写入ram，这样每输入一个信号进行逻辑运算就等于输入一个地址进行查表，找出地址所对应的内容后输出即可。也可以把le当作一个4输入的函数发生器，能够实现4变量输入的所有逻辑［10］。
由于rtl级设计不涉及具体的工艺，不同的综合工具、不同的器件类型可能会产生不同的综合结果，即所需要的le数量会有差异。因此，在同一种综合工具、同一种器件类型的前提下对不同的实现方法进行比较。
3 基于verilog hdl的rtl级实现
verilog hdl是目前广泛使用的ieee标准硬件描述语言，可以用不同的工具进行综合和验证。本文基于子项空间共享技术，采用verilog hdl进行fir数字滤波器的rtl级描述。下面举例介绍具体的实现方法。以参考文献［4］中的较低阶滤波器s1为例，下面给出滤波器s1的系数，其中，h（n）=h（24-n），13≤n≤24；通带增益为485.268 2。
h（12）=3×26-1×20；h（11）=5×25-1×24；h（10）=3×24；
h（9）=-3×23；h（8）=-1×25；h（7）=-3×20；h（6）=1×24；
h（5）=5×21；h（4）=-1×22；h（3）=-1×23；h（2）=-1×21；
h（1）=3×20；h（0）=1×21。
由上可知，s1对应基组为{3，5}，此基组的阶数等于2，即产生基组需要2个加法器，由基组产生滤波器系数需要2个加法器，因此，mba的个数为4，系数都不为零；sa的个数为24。
（1）子项基组的产生
assign x3={x_n，1‘b0}+ x_n； //x_n为输入信号
assign x5={x_n，2’b00}+x_n；
（2）mba的实现
利用已经产生的基组，参照s1的系数，就可以得到mba部分各常系数乘法的值，部分程序段如下：
assign mba12={x3，6‘b000000}-x_n； //实现h［12］×x_n
……
assign mba0 = {x_n，1’b0}； //实现h［0］×x_n
（3）延时单元和sa的实现
例s1中不存在值为0的系数，且考虑到线性相位fir滤波器系数对称，因此程序段如下：
delay_sa0 《= mba0；
delay_sa1 《= delay_sa0 + mba1；
……
delay_sa11 《= delay_sa10 + mba11；
delay_sa12 《= delay_sa11 + mba12；
delay_sa13 《= delay_sa12 + mba11；
……
delay_sa23 《= delay_sa22 + mba1；
delay_sa24《= delay_sa23 + mba0；
（4）输出的实现
考虑到s1的系数在有限字长实现时单位脉冲响应乘以512（=29）倍，因此在输出时要进行截短处理，即去掉低9位。
4 综合结果
本节将选取参考文献［4］中的4个例子分别在fpga上进行综合比较。4个例子的性能指标如表1所示。
参考文献［4］中基于子项共享进行系数离散化得到的结果如表2所示，具体的滤波器系数参见参考文献［4］。
如前所述，fpga实现硬件资源的消耗可以通过综合后le的数量来衡量。分别选择cyclone系列的ep1-
c12q240c8和apex20ke系列的 ep20k600ebc652-3两种型号的fpga对4个滤波器两种不同的实现方法（子项共享实现和直接实现）进行综合，综合工具选用quartus ii，结果如表3所示。
从表3可以看出，基于子项共享的实现可以有效减少fpga中le的消耗数量，且滤波器阶数越高，共享的机会越大，效果越好。
本文通过verilog hdl编程在fpga上实现了子项共享的fir数字滤波器设计。子项空间共享技术可以有效地减少fir滤波器实现时加法器的个数，从而使得综合后消耗的le数量明显减少，有利于数字系统的低成本、低功耗设计，具有实际的应用意义。
参考文献
［1］ 唐博，李锦明，李士照。基于fpga的高阶fir滤波器强抗干扰数据采集系统［j］。电子技术应用，2012，38（9）：89-92.
［2］ 林志典，张方佩，袁国顺。基于fpga的高速fir滤波器的设计与实现［j］。微电子学，2013，43（4）：200-202.
［3］ 惠鹏飞，姚仲敏，夏颖，等。基于fpga的无线传感网络信道波形整形滤波器［j］。电子技术应用，2013，39（7）：35-37.
［4］ yu y j，lim y c.design of linear phase fir filters in subexpression space using mixed integer linear programming［j］.ieee trans.circuits syst.i，2007，54（10）：2330-2338.
［5］ yu y j，lim y c.optimization of linear phase fir filters in dynamically expanding subexpression space［j］.circuit syst.signal process.，2010，29（1）：65-80.
［6］ shi d，yu y j.design of linear phase fir filters with high probability of achieving minimum number of adders［j］.ieee trans.circuits syst.i，2011，58（1）：126-136.
［7］ potkonjak m，shrivasta m b，chandrakasan a p.multiple constant multiplication：efficient and versatile framework and algorithms for exploring common subexpression elimination［j］.ieee trans.comput.aided，1996，15（2）：151-165.
［8］ xu fei，chang c h，jong c c.design of low-complexity fir filters based on signed-powers-of-two coefficients with reusable common subexpressions［j］.ieee trans.comput.aided，2007，26（10）：1898-1907.
［9］ wang y，roy k.csdc：a new complexity reduction technique for multiplierless implementation of fir filters［j］.ieee trans.circuits sysm.i，2005，52（9）：1845-1853.
［10］ altera公司.cyclone2系列器件数据手册：cyclone device handbook，volume 1［z］.2007.
iPhone 14系列手机将推出新的配色
Cirrus Logic宣布同意收购Lion Semiconductor
铝壳气体耐压爆破两不误，新能源动力电池壳体测试设备全面升级
设计经验谈：模拟地与信号地的区别
卡尔曼滤波的总结和思维扩展
剖析子项空间技术的低复杂度FIR滤波器实现
传音拍照专利解决人体肤色差异
这次换亚菲特克莱斯勒的汽车排放作假连环爆
除了谷歌“亲儿子” 还有Galaxy S8、诺基亚8...这些手机都能升级Android 8.0
华为收到美国商务部传票 聚焦向制裁国家出口技术问题
基于混合信号FPGA的功率管理解决方案
NVIDIA全新架构将向新一代超级计算机发起冲击
数字D类音频功率放大器设计方案
NVIDIA RTX GPU助力打造城市新区绿化
中国移动打造湖北首家5G智慧医院
HLPM025K3 PM2.5传感器的驱动设计与实现
传感器的新应用有哪些？传感器产业发展的痛点
中兴通讯助力浙江移动完成5G消息平台建设
华为mate10/mate10pro还未发布就来真机开箱:这颜值你觉得多少钱合适?
三星银河A52在印度的发布指日可待