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。