FIR

FIR 是甚么

全名为 Finite Impulse Response，指输入讯号的脉冲响应( $\delta$ 函数的频率响应)会在有限的时间变为0，与 IIR 相反。 IIR 因为包含负回授系统，因此任一时间点的输入都可能会对之后任一时间点的输出造成影响。通过filter的讯号可以表示为 $y[n]=h[n]*x[n]$，其中 FIR filter的输出可以表示为 $\sum_{i=0}^{N-1} h(i)x(n-i), n=0,1,2,...$，依照 N 的大小也称之为 N 阶 FIR。
主要的优点是相较IIR容易在硬体实践，且较为stable(指 input bounded 则 output bounded，在此例任一时间点的输出不会超过$\sum|h|*max(input)$)，误差也不会累积。缺点是在低截止频率时比IIR耗运算资源。

FIR 的用途

滤波器的核心，几乎在所有通讯相关场合都会用到。

FIR 有甚么作法？各自的实际价值？

最传统的方法是藉由一长串的buffer来解决时序问题，然而block FIR 的价值是将一群输入与频率响应一起计算，在串联各block拼凑成整个FIR。Parallel FIR则是直接增加throughput，且因为有许多计算用到的讯号可以共用，因此原先需要$N*L$个buffer变为仅需要N个buffer，且每个输出从N-1个delay变为只有$N/L-1$ or $N/L$个delay。

FIR 相关论文

元祖论文

Fast FIR Filtering

先简单介绍 FFA(Fast FIR Algorithm)，由于乘法的运算资源比加法的运算资源多很多，因此 FFA 主要是缩减乘法的使用数量(此时加法使用数量会大幅提升)来使硬体加速与面积缩减。
这篇论文是最初始的FFA介绍，主要看点是知道配比法不只一种，但每个都互相等价。

非对称係数(初始)

Area-Efficient Parallel FIR Digital Filter Implementation

这篇为很概括性的介绍许多不同的技术，同时也是 16-Parallel 的主要参考论文。
首先先说到 Parallel 本身能同时提高 throghput(我觉得同时也有降低 latency)与降低power耗损(降低$\beta^2$倍，$\beta$约反比于$L$)。接着他介绍了 FFA 在 2, 3, 4, 6-parallel 的架构，其中 4,6 皆为下级FFA cascade而来的。
接着他介绍了数字量化的方式。由于硬体运算要求以及未知 passband 和 stopband ，因此他採用了特殊的量化模式。
关于面积缩减部分，他使用了许多shifter取代乘法器，其中使用canonic digit 去最小化需要的shifter个数。此外藉由将参数相同部分的shifter共用也很好的缩减了所需硬体。

Low-Area/Power Parallel FIR Digital Filter Implementation

与上一篇差不多，但有附更多例子和实验结果。

非对称係数(延伸)

此篇最主要要带出的观念是藉由类似FFT硬体实践的radix方法，使用 L=2 的 Parallel FFA 并联集 4 阶。然而此篇论文并没有达到winograd需求(31)，也没有达到联集需求(81)，但也没有比较其他结构，过程也推得乱七八糟，没有甚么参考价值。

Low-Complexity General FIR Filters Based on Winograd’s Inner Product Algorithm

这是一篇很有趣的论文，0 citation 但是想法很新奇。使用Sequencial FIR的方式，主要是凑出 h1h2 和 x1x2 连加项，h1h2 连加项可预先算完，而 x1x2 连加项则是每个 cycle 增加最新项与扣除最旧项，因此乘法只需 1~2 个。因此结论来说只需一半的乘法运算量，但并没有拓展的可能，只在 2-parallel 和 4-parallel 时有优势。

对称係数

Area-reduced Parallel FIR Digital Filter Structures Based on Modified Winograd Algorithm

这篇其实没有甚么参考价值，主要是将过去有的对称细数分配法重推一次。

Area-Efficient Parallel FIR Digital Filter Structures for Symmetric Convolutions Based on Fast FIR Algorithm

这篇是神作，一般结构的 FIR 其实在面对symmetric coefficient 时能达到只使用一半的乘法器，然而面对FFA这种 block FIR 时就会造成许多 subfilter block 是无法成功合併的，因此无法 share multiplier 。因此作者提出了一个新的FFA结构，与原先的FFA等价，但能使三个subfilter其中有两个是可以share的，而L=3的情况6个subfilter中有4个是可以share，使得乘法使用数也来到一半。而至于FFA在此时的必要性???学长是表示仍会有不少考量，涉及latency, pipeline等考虑。

High Speed Low Complexity FPGA-based FIR Filters Using Pipelined Adder Graphs

係数共用结构改变，感觉改变不多

Hardware Efficient Fast Parallel FIR Filter Structures Based on Iterated Short Convolution

ISCA，低parallel时能省10%附近，高parallel时比较可观，一个非常完整的系统，优化也是有目共睹，很值得试试看PPA。

Low-Cost Parallel FIR Filter Structures With 2-stage Parallelism

很有意思，标準ISCA，pre/post process有点多，且latency为16，但乘法气真的少太多，很值得试试看PPA结果。

结论

由于公司主力目标为 adaptive filter ，因此係数对称与係数共用等技巧都不适用，且现行产业大多在乎 power，因此目前先选定以 ISCA 和 FFA 去进行 chip design ，并观察 tape out power。