低復(fù)雜度FIR 濾波器NR-SCSE 優(yōu)化設(shè)計

李 成，郭 濤，石 帥，暢彥祥

（1.中北大學(xué)儀器科學(xué)與動態(tài)測試教育部重點實驗室，山西太原 030051；2.中國航天科技集團有限公司中國運載火箭技術(shù)研究院，北京 100000）

在工程領(lǐng)域發(fā)展趨勢中，如數(shù)字醫(yī)學(xué)中心電信號處理[1]、實時應(yīng)用的嵌入式系統(tǒng)[2]、軟件無線電和通信中數(shù)據(jù)大規(guī)模輸入、輸出等[3]，對數(shù)字信號處理系統(tǒng)的要求越來越高。數(shù)字濾波器作為數(shù)字信號處理系統(tǒng)的主要處理部件，其性能直接決定了系統(tǒng)的信號處理能力。與無限沖激響應(yīng)濾波器相比，有限沖激響應(yīng)（Finite Impulse Response,FIR）濾波器具有很強的穩(wěn)定性和嚴(yán)格的線性相位特性，得到了更廣泛的應(yīng)用。但是FIR 濾波器的乘法器增加了系統(tǒng)的功耗和硬件復(fù)雜度，限制了FIR 濾波器的發(fā)展。因此，F(xiàn)IR 濾波器的低功耗設(shè)計成為提高整個系統(tǒng)信號處理效率的重點。目前主要的方法是降低硬件復(fù)雜度和優(yōu)化濾波器系數(shù)。對于濾波器系數(shù)優(yōu)化，文獻(xiàn)[4]中采用規(guī)范有符號數(shù)字（Canonical Signed Digit,CSD）編碼來最小化濾波器系數(shù)中非零元素的個數(shù)，從而實現(xiàn)濾波器的結(jié)構(gòu)優(yōu)化。文獻(xiàn)[5]在CSD 碼的基礎(chǔ)上設(shè)計了一種轉(zhuǎn)換器，提高了二進制數(shù)轉(zhuǎn)換為CSD 碼的速度。文獻(xiàn)[6-7]采用基于CSD 編碼的遺傳算法優(yōu)化濾波器的設(shè)計，文獻(xiàn)[8]采用花粉授粉算法結(jié)合公共子表達(dá)式消除（Common Subexpression Elimination,CSE）進一步提高了加法器的效率，實現(xiàn)了無乘法器設(shè)計。

在乘法器優(yōu)化方面，針對快速傅里葉變換中乘法運算多、內(nèi)存占用率高，通過設(shè)計CSD 乘法器對其進行優(yōu)化[9-11]。在圖像處理系統(tǒng)中，使用CSD 編碼優(yōu)化離散余弦系統(tǒng)中的乘法運算[12-13]。文中基于CSE算法和CSD 編碼，提出了一種低復(fù)雜度FIR 濾波器的設(shè)計方法。

1 基本原理和模型

1.1 濾波器原理

FIR 濾波器輸出Y(n)為輸入序列X(n)與單位取樣響應(yīng)h(n)的線性卷積，輸出表達(dá)式與系統(tǒng)函數(shù)分別為：

式中，N為FIR 濾波器的階數(shù)，根據(jù)上式可以得出FIR 濾波器的直接型結(jié)構(gòu)[14]，如1 圖所示。

根據(jù)圖1 的結(jié)構(gòu)，對于N階FIR 濾波器，總共需要N個乘法運算、N-1 個延時單元和一個N輸入的加法運算。在通常情況下，相較于加法和移位運算，乘法運算會耗費更多的硬件資源，故需要把設(shè)計中的乘法器轉(zhuǎn)換為移位加法器。

圖1 FIR濾波器直接型結(jié)構(gòu)

1.2 規(guī)范有符號數(shù)編碼

CSD 編碼作為一種三元編碼方式，不同于二進制編碼，它具有{1,0,-1}三元值（文中用代替-1），其基本原理是盡量減少乘法器中的非零元素，減少移位和加法次數(shù)，從而降低了乘法器的硬件復(fù)雜度。將二進制編碼轉(zhuǎn)化為CSD 碼的具體實現(xiàn)方法：二進制數(shù)碼從最低的有效位開始，將大于2 的1 序列全部替換為10,…,0，并將1011 替換為1 10；最后從最高有效位開始，用011 代替10[15]。最佳的CSD 編碼方式可以減少非零元素的數(shù)量，降低資源消耗，縮短計算時間。其特點有：

1）在一個CSD 數(shù)據(jù)里，沒有兩個連續(xù)的非零位；

2）CSD 數(shù)據(jù)是所有數(shù)字表示法里所含非零位數(shù)最少的一種；

3）二進制數(shù)碼與CSD 碼一一對應(yīng)。

1.3 CSE算法

濾波器初始系數(shù)組可表示為向量組h=[h(0)h(1)…h(huán)(N)]T，將向量組h中的每個系數(shù)按照1.2 里的步驟轉(zhuǎn)化為CSD 碼，得到新的系數(shù)向量組hC，其中第i個系數(shù)向量

在系數(shù)hC(i)中，若存在與為非零量，且中間量全都為0（中間有w個0），則稱這個多項子式為w階2 項子式。如果與同號，則稱該子式為2 項偶子式，例如1001，00；反之，與異號，則稱該子式為2 項奇子式，例如100，001。若系數(shù)向量hC(i)中只含有一個非零元素，無法構(gòu)成任何2 項子式時，如0010，則稱hC(i)為孤子。

CSE 算法的基本原理是在系數(shù)向量組（即公共表達(dá)式）中找到兩個相同階次的項，并計算出輸入信號與公共表達(dá)式相乘的結(jié)果，使不同的位置和系數(shù)共享結(jié)果，減少運算單元數(shù)。例如，假設(shè)13 位量化系數(shù)hC(1)=10010010000，可以看出有2 階2 項偶子式1001，如果使用通常的移位加法，則需要4 個加法器，如圖2（a）所示；采用CSE 算法，則需3 個加法器，如圖2（b）所示。

圖2 系數(shù)hC(1)實現(xiàn)方法

針對CSE 算法的原理，其難點在于如何從系數(shù)向量組中高效快速地找出公共子式，文獻(xiàn)[16]提出了一種非遞歸的帶符號共同子式消除（Non Recursive Signed Common Subexpression Elimination,NR-SCSE），具體實現(xiàn)方法如下：

子表達(dá)式表示為S1 和S2，其中S1 表示2 項偶子式，S2 表示2 項奇子式。每一個系數(shù)向量組hC對應(yīng)一個子式矩陣Pn，元素Pn(i,j)的值為j階2 項子式出現(xiàn)的次數(shù)，i值表示該2 項子式類別（S1 或S2）。例如Pn(1,3)=3 表示3 階2 項偶子式0 001（或10 00）出現(xiàn)的次數(shù)為3。將系數(shù)向量組hC寫作系數(shù)集YCSD，假設(shè)系數(shù)向量集YCSD如下：

其對應(yīng)的子式矩陣Pn{1}為：

因Pn(2,1)=Pn(2,4)=4 為最大值，此處取01（或10）為第一個公共子式，然后將公共子式對應(yīng)在YCSD中的數(shù)字置零，得到新系數(shù)集如式（5）所示：

該濾波器系數(shù)集YCSD通過NR-SCSE 算法實現(xiàn)的結(jié)構(gòu)如圖3 所示，最終需要的加法器數(shù)量為10，相較于直接法，數(shù)量減少了4 個。

圖3 系數(shù)集YCSD的CSE實現(xiàn)

2 FIR濾波器設(shè)計

2.1 FIR濾波器結(jié)構(gòu)設(shè)計

首先，利用Matlab 設(shè)計了一個15 階（長度16 位）低通線性相位FIR 濾波器。窗口函數(shù)是Blackman 窗口函數(shù)。根據(jù)要求設(shè)計了濾波器系數(shù)，并在FPGA中搭建了FIR 濾波器結(jié)構(gòu)。然后在Matlab 中生成兩個不同頻率的合成輸入信號，在Modelsim 中用濾波器對輸入信號進行仿真，對高頻分量進行濾波，將低頻部分輸出，并用Matlab 對輸出信號進行分析。

FPGA 在實現(xiàn)FIR 濾波器結(jié)構(gòu)時，主要采用串行結(jié)構(gòu)。首先，將輸入數(shù)據(jù)的每個延遲單元串行相加并乘以相應(yīng)的系數(shù)，將乘積結(jié)果累加后輸出。因此，整個設(shè)計只使用了一個乘法器單元。串行結(jié)構(gòu)有兩種形式：全串行結(jié)構(gòu)和半串行結(jié)構(gòu)。由于全串行結(jié)構(gòu)結(jié)合了加法器中的對稱量化系數(shù)運算，與半串行結(jié)構(gòu)相比，加法器的數(shù)目可以減少一半，因此采用全串行結(jié)構(gòu)。同時根據(jù)第一節(jié)中的內(nèi)容，使用移位加法運算取代乘法運算，將乘法器移出設(shè)計。全串行FIR 濾波器結(jié)構(gòu)如圖4 所示。

圖4 全串行FIR濾波器結(jié)構(gòu)

從圖中可以看出，系統(tǒng)時鐘通過1/8 分頻器獲得分頻時鐘，控制數(shù)據(jù)輸入，使輸入數(shù)據(jù)以1/8系統(tǒng)時鐘頻率存儲在移位寄存器中，使一個加法器在一個系統(tǒng)時鐘周期內(nèi)完成8 次加法運算。經(jīng)過量化、CSD 編碼和NR-SCSE 優(yōu)化后，濾波器的原始系數(shù)轉(zhuǎn)化為新系數(shù)表，然后與加法結(jié)果進行移位相加，得到濾波輸出。

2.2 濾波器系數(shù)量化

FIR濾波器主要參數(shù)：截止頻率為500 Hz，采樣頻率為2 000 Hz 的16 階FIR 低通濾波器。利用Matlab工具箱設(shè)計出滿足指標(biāo)的FIR 濾波器，系數(shù)的量化位數(shù)為12 位，輸入數(shù)據(jù)位寬為12 位，輸出數(shù)據(jù)位寬為29 位，系統(tǒng)時鐘為16 kHz。將濾波器系數(shù)進行量化取整，并轉(zhuǎn)換為CSD 碼如表1 所示。

表1 FIR濾波器系數(shù)表示

由表1 可得FIR 濾波器量化系數(shù)向量組，根據(jù)前文提出的NR-SCSE 算法，取001（或100）、1001（或00）為兩個3 階2 項公共子式進行優(yōu)化，加法器數(shù)量從14 個減少至10 個，效果明顯。

3 仿真分析

采用Matlab 生成200 Hz 和800 Hz 的合成輸入信號源，在Modelsim 中使用優(yōu)化后的FIR 低通濾波器處理該信號，對800 Hz 的高頻部分進行濾波，得到200 Hz 的低頻正弦波。利用Matlab 對輸出結(jié)果進行了分析。最后對輸入、輸出數(shù)據(jù)進行了頻域和時域分析，最終結(jié)果如圖5 所示。結(jié)果表明，F(xiàn)IR 低通濾波器具有良好的性能。

圖5 輸入輸出信號對比

為了更好地體現(xiàn)出CSD 編碼結(jié)合NR-SCSE 技術(shù)在優(yōu)化乘法運算中的優(yōu)勢，分別以兩種方法設(shè)計32、64、128 階的低通FIR 濾波器，進行對照比較，其結(jié)果如表2 所示。相較于乘法直接實現(xiàn)，優(yōu)化NRSCSE 資源減少率約為30%，并隨著階數(shù)的增大，優(yōu)化效果也越好，有效降低了加法器的數(shù)量，改善了濾波器性能。

表2 FIR濾波器兩種算法性能對照

4 結(jié)論

文中提出了一種無乘法器的低復(fù)雜度FIR 低通濾波器。其將公共子表達(dá)式消除與CSD 編碼相結(jié)合，用移位加法代替濾波器中的乘法單元，有效降低了設(shè)計的硬件資源。仿真結(jié)果表明，與傳統(tǒng)的FIR濾波器設(shè)計方法相比，加法器的數(shù)量可以減少約30%，濾波器的復(fù)雜度降低。