鐘燕清,閻躍鵬,孟 真,田 易,劉 謀,李繼秀

(1.中國科學院 微電子研究所,北京 100029； 2.中國科學院大學,北京 100049)

FIR數(shù)字濾波器為對稱型結(jié)構(gòu)，階數(shù)和量化位寬是決定數(shù)字濾波器硬件資源的兩個重要因素，通常情況下，階數(shù)越高、量化位寬越大，硬件資源消耗越多.考慮到FIR濾波器的參數(shù)是固定的，人們引入了固定乘數(shù)優(yōu)化算法進行優(yōu)化處理[1]，即將乘法分解成加法和移位計算，降低運算復雜度.在已有的數(shù)字濾波器的固定乘數(shù)優(yōu)化算法中，加法深度LD(logic depth)和加法器個數(shù)LA(logic adder)是衡量算法優(yōu)劣性的兩個重要指標.降低加法器個數(shù)需要盡可能復用系數(shù)中的公共項，從而帶來加法深度的增加；降低加法深度則意味著降低公共項的復雜度，帶來加法器LA的增加.LD和LA的結(jié)果不僅取決于系數(shù)的量化位寬、階數(shù)，也取決于用戶的優(yōu)化方式，是一個綜合性的優(yōu)化問題.考慮到常系數(shù)乘法的加法器個數(shù)與系數(shù)非零項直接相關(guān)，Park等[2-3]提出采用CSD、MSD表示法表示濾波器系數(shù)，在后續(xù)的算法中得到了廣泛應(yīng)用.在此基礎(chǔ)上,人們提出了采用遞歸式算法和非遞歸式算法的不同公共項提取思路來降低電路中的加法器消耗.前者[4-9]以BHM[4]、RAG-n[5-6]、HARTLEY[7]和HCUB[8]為代表，采用迭代運算窮舉固定系數(shù)的所有公共項，可以達到最優(yōu)的降低MCM加法器的效果.RAG-n、BHM和HCUB算法均采取圖形啟發(fā)式方式進行優(yōu)化，即先對系數(shù)進行排序，以最小的系數(shù)為公因子，窮舉各個系數(shù)的公因子組合方式，選取代價最小的作為最優(yōu)解.其中Bull等[4]最早提出采用圖形化的方法來從小到大組合濾波器系數(shù)，取得了較好的效果；Dempster等[5]在此基礎(chǔ)上進行了改良，擴展了系數(shù)范圍，提出了BHM算法；而RAG-n則更進一步，采用查表法遍歷了所有可能，所以加法器個數(shù)LO最少，但是代價是需要預存分解表，算法復雜度最高，運算時間最長，加法深度最高. HCUB算法則是在此基礎(chǔ)上，引入了中間變量算子，降低了算法對分解表的要求，是目前最優(yōu)的啟發(fā)式優(yōu)化算法. 然而，上述圖形啟發(fā)式優(yōu)化方法均存在算法復雜度高、求解時間隨量化位數(shù)增加急劇上升的問題，同時由于采用公共項的多次復用，邏輯深度居高不下，引入大量的路徑延時，對后期電路的設(shè)計和綜合非常不友好.非遞歸式[10-16]則以直接提取公共項進行有限次數(shù)迭代，具有算法復雜度低、可綜合性好等優(yōu)點，代表性的有NR-SCSE、HSSE、VSSE算法等.其中Peiro等[14]提出的非遞歸有符號公共項消去算法(Non-recursive signed common sub-expression elimination, NRSCSE)，采用一維搜索頻次最高的公共項的算法，算法復雜度低，邏輯深度低，取得了非常好的同時降低LO和LD的效果.為了達到降低邏輯深度的目的，該算法只啟用包含2個非零項的公共項，具有最低邏輯深度特性. 然而，上述非遞歸式算法均只進行了一維的共同項(單獨的系數(shù)矩陣的行公共項或者單獨的列公共項)的提取，并沒有考慮到系數(shù)矩陣的二維特性，在加法器個數(shù)的指標上整體落后于遞歸算法.

為了達到邏輯深度和加法器個數(shù)的雙重優(yōu)化效果，本文提出了一種新的二維非遞歸優(yōu)化算法. 其在一維非遞歸式算法的基礎(chǔ)上，對系數(shù)矩陣的第2個維度進行公共項提取，從而達到進一步降低加法器個數(shù)的效果.仿真結(jié)果表明，相比于一維的NRSCSE，本文設(shè)計的濾波器優(yōu)化算法(后文簡稱ONRSCSE)可以降低10%左右的系數(shù)加法器數(shù)量，具有良好的推廣價值.

1 一維非遞歸算法

數(shù)字濾波器的濾波效果是通過輸入信號與濾波系數(shù)的卷積運算來實現(xiàn)的，具體來說，輸入信號x進入一個N階的數(shù)字FIR濾波器后，需要與N-1個系數(shù)進行乘法運算，之后進行累加，得到輸出值.假定N階FIR濾波器的系數(shù)由低階到高階分別為：h(0),h(1),…，h(N-1),則有該濾波器的響應(yīng)為

(1)

式中：x(n)、y(n)分別為濾波器的輸入和輸出.假定濾波器的系數(shù)矩陣為H，H=[h0,h1,…,hN-1]，當前輸入為x(n)，則輸出Y=H×X，X=x(n)×[z0,z-1,z-2,z-3]為輸入矢量.

考慮到FIR濾波器的系數(shù)對稱性，通常采用優(yōu)化的轉(zhuǎn)置式實現(xiàn)，假定FIR為I型濾波器，N為奇數(shù)，則實現(xiàn)的濾波器結(jié)構(gòu)如圖1所示.由于其系數(shù)對稱性，即h0=hN-1，h1=hN-2，對系數(shù)的優(yōu)化只需要對其前1/2系數(shù)h0，h1，…，h(N-1)/2進行即可.

圖1 FIR濾波器的優(yōu)化轉(zhuǎn)置結(jié)構(gòu)

傳統(tǒng)的非遞歸優(yōu)化算法在將系數(shù)hi采用CSD法表示后，對各個系數(shù)的非零項進行統(tǒng)計，依次提取出現(xiàn)頻率最高的間距相同、符號相同/相反的非零項作為公共項，對系數(shù)進行分解，直到系數(shù)無法再提取公共項為止，通常為一維搜索算法.以NRSCSE[14]算法為例，其只搜索系數(shù)內(nèi)的任意間距2個非零位公共項，在量化位數(shù)為b時，單個系數(shù)最多存在2×(b-1)個公共項，邏輯深度最多為「log2b/2?.由于只需要搜索和消去運算，NRSCSE算法復雜度非常低，非常適合于普通濾波器的優(yōu)化.然而，由于只用到了系數(shù)內(nèi)的冗余項，在系數(shù)非零項為單數(shù)時必然會出現(xiàn)單個的1/-1不能復用，而導致2n個非零項和2n-1個非零項的優(yōu)化效果一樣，增加加法器的消耗.以4個系數(shù)為例說明此問題：

h(0)=1 288,h(1)=776,h(2)=1 077,

h(3)=1 189.

(2)

將其表示為12 bit的CSD數(shù)后，系數(shù)如下：

h(0)=0x508=(010100001000)CSD,

h(1)=0x308=(010-100001000)CSD,

h(2)=0x435=(0100010-10101)CSD,

h(3)=0x4a5=(010010100101)CSD.

(3)

采用NRSCSE提取公共項101/10-1后，得到剩余矩陣(后文稱為殘余矩陣)為

(4)

則整體表示法為

(5)

式中:公共項S0=x0?2+x0，S1=x0?2-x0，如圖2中紅色方框內(nèi)所示.共需要加法器8個，邏輯深度(系數(shù)中最大加法器個數(shù)+1)為2層.

圖2 濾波器系數(shù)的NRSCSE優(yōu)化示例

考慮到經(jīng)過系數(shù)內(nèi)的公共項提取后，系數(shù)殘余矩陣內(nèi)還存在冗余信息，如圖2中藍色圓框所示，可以進一步進行優(yōu)化.

2 二維非遞歸優(yōu)化算法

二維非遞歸優(yōu)化算法(Optimized non-recursive signed common sub-expression elimination，ONRSCSE)是行公共項和列公共項提取的結(jié)合，是一種典型的非遞歸固定乘數(shù)優(yōu)化方法.其大致思路為：首先采用CSD法表示FIR濾波器的前1/2系數(shù)，將系數(shù)表示為{-1，0，1}的初始系數(shù)矩陣；然后采用行公共項提取的方法依次分解系數(shù)矩陣的行系數(shù)，直到滿足行分解的終止條件為止；之后對分解后剩余的非0系數(shù)矩陣(后文稱為殘余矩陣)進行列公共項分解，直到滿足終止條件為止；最后將系數(shù)表示成分解出的行與列公共項的移位與加法組合，完成整個算法優(yōu)化.

以一維優(yōu)化為例，本文在一維非遞歸算法的基礎(chǔ)上，對上述殘余矩陣式6進行列公共項的提取，得到列公共項[1 1]T，記為S2=x0+x0[-1]，[-1]表示對系數(shù)進行一個單位的延時，則濾波器此部分的輸出為

(6)

整體實現(xiàn)一共需要加法器7個，邏輯深度2層. 因此，相比于一維的NRSCSE算法，本算法(ONRSCSE)增加了列系數(shù)的非零項搜索，節(jié)省了 1個加法器資源.

不難推算，NRSCSE算法優(yōu)化的殘余矩陣中非零項越多，列公共項出現(xiàn)次數(shù)越多，本算法的優(yōu)化效果越顯著.

2.1 名詞定義

2.1.1 系數(shù)矩陣

由CSD表示后的濾波器系數(shù)組成的矩陣，矩陣元素為{-1，0，1}，假定濾波器系數(shù)量化位寬為b，階數(shù)為n，本算法通常取前1/2系數(shù)第0～m階組成系數(shù)矩陣(如果n為偶數(shù)，m=n/2；如果n為奇數(shù)則m=(n-1)/2).系數(shù)矩陣記為Hi，下標i代表第i次系數(shù)分解，H0為初始化系數(shù)矩陣.

2.1.2 殘余矩陣

系數(shù)矩陣減去公共項元素后剩余的非0矩陣.

2.2 算法描述

在系數(shù)矩陣的基礎(chǔ)上，對公共項進行二維搜索，遵循規(guī)則為——先迭代搜索行公共項，再搜索列公共項.

2)對系數(shù)矩陣Hi進行行系數(shù)分解，方法為統(tǒng)計在整個系數(shù)矩陣中出現(xiàn)次數(shù)最多的行公共項，將其作為最優(yōu)公共項；

3)在系數(shù)矩陣Hi中消去最優(yōu)公共項，得到殘余矩陣Hi+1，則Hi可以表示為Hi+1與最優(yōu)公共項的移位和加法組合；

4)返回步驟2)繼續(xù)分解殘余矩陣Hi+1，直到滿足行分解的終止條件——公共項矩陣中最優(yōu)公共項出現(xiàn)次數(shù)小于2為止，進入步驟5).假定此時已經(jīng)進行了j次迭代，得到了殘余矩陣Hj；

5)對殘余系數(shù)矩陣Hj進行列分解，方法為統(tǒng)計在整個系數(shù)矩陣中出現(xiàn)次數(shù)最多的列公共項，將其作為最優(yōu)公共項；

6)在系數(shù)矩陣Hj中消去最優(yōu)公共項，得到殘余矩陣Hj+1，則Hj可表示為Hj+1與最優(yōu)列公共項的移位和加法組合；

7)返回步驟5)繼續(xù)分解殘余矩陣Hj+1，直到滿足列分解終止條件為止，進入步驟8)；

8)將濾波器的輸出y表示為所有行、列公共項的移位和累加*輸入的組合.

2.3 算法復雜度分析

3 結(jié)果及分析

3.1 實驗數(shù)據(jù)集

本文采用通用的濾波器設(shè)計方法，一共設(shè)計了19個不同特性的濾波器，并對其進行不同量化位寬、不同階數(shù)的例化，產(chǎn)生了共82個濾波器，此為算法優(yōu)化的對象.

其中為對比本算法與一維非遞歸算法，采用MATLAB的FDAtool工具產(chǎn)生了12組數(shù)字FIR帶通濾波器，階數(shù)從37階到649階，并對每組濾波器系數(shù)進行了12、16 bit的量化，覆蓋了常用的數(shù)字濾波器范圍，此為數(shù)據(jù)集1.

為對比本算法與遞歸型優(yōu)化算法，采用Parks-McClellan法設(shè)計7種不同階數(shù)的數(shù)字帶通濾波器，每種階數(shù)內(nèi)有10組不同的濾波器系數(shù)，分別對應(yīng)不同的帶通特性，此為數(shù)據(jù)集2.采用Voronenko等[18]提供的優(yōu)化算法庫對數(shù)據(jù)集2內(nèi)的濾波器進行優(yōu)化. Voronenko[18]算法庫為卡內(nèi)基梅隆大學SPIRAL算法庫的一部分，濾波器優(yōu)化部分由HCUB算法的提出者Voronenko[18]提供，是一個集成多個主流遞歸式濾波器優(yōu)化算法的經(jīng)典算法實現(xiàn)庫，已經(jīng)被Vinod等[16-17]多位學者引用，可以實現(xiàn)包括BHM、RAG-n、HCUB在內(nèi)的3種遞歸式濾波器優(yōu)化算法，量化位寬支持到12 bit，濾波器階數(shù)支持到100階左右.由于Parks-McClellan設(shè)計法和算法庫的限制，只產(chǎn)生了70組30-100階的濾波器，量化位寬均為12 bit.

3.2 本算法與一維非遞歸算法及傳統(tǒng)CSD表示法的對比

對數(shù)據(jù)集1內(nèi)的18組濾波器進行了優(yōu)化，統(tǒng)計采用CSD表示法、NRSCSE算法和ONRSCSE算法時運算需要的加法器資源，得到結(jié)果見表1、2.

表1 CSD表示法的加法器資源

表2 NRSCSE與ONRSCSE算法優(yōu)化后的加法器資源

可以看到，與CSD表示法相比，NRSCSE與ONRSCSE優(yōu)化效果都很顯著.在階數(shù)低于100時，優(yōu)化后的加法器資源均控制在傳統(tǒng)CSD表示法的30%左右；階數(shù)高于100時，優(yōu)化后的加法器資源控制在傳統(tǒng)CSD表示法的50%以內(nèi).

比較NRSCSE與ONRSCSE的優(yōu)化效果發(fā)現(xiàn)，同等情況下，ONRSCSE均優(yōu)于NRSCSE，優(yōu)化效率見表3.可以看到，ONRSCSE對NRSCSE的優(yōu)化效率不隨著濾波器階數(shù)和量化位寬線性變化，而是主要取決于濾波器經(jīng)過一維非遞歸優(yōu)化后的加法器資源.普遍來說,同樣量化位寬的條件下,ONRSCSE對NRSCSE的優(yōu)化效果呈現(xiàn)一定的比例關(guān)系，NRSCSE優(yōu)化后的加法器個數(shù)越多，ONRSCSE節(jié)省的加法器個數(shù)就相對更大.然而由于經(jīng)過NRSCSE優(yōu)化后的殘余系數(shù)矩陣的非零位在不同濾波器系數(shù)矩陣中分布各異，所以優(yōu)化效果會體現(xiàn)出個體差異，如FIR10與FIR11，12 bit量化時經(jīng)過NRSCSE優(yōu)化后加法器個數(shù)分別為109/122個，但是ONRSCSE的節(jié)省加法器個數(shù)卻是12/9個，F(xiàn)IR11的ONRSCSE優(yōu)化效果略差于FIR10.這是因為FIR11經(jīng)過行系數(shù)公共項提取后，殘余稀疏矩陣非零位分布相對發(fā)散，可以提取的列公共項個數(shù)少于FIR10.

表3 ONRSCSE對NRSCSE的提升效果

對上述優(yōu)化結(jié)果的加法器資源進行繪圖，得到ONRSCSE與NRSCSE加法器個數(shù)對比,如圖3所示.

圖3 ONRSCSE與NRSCSE加法器個數(shù)對比

與傳統(tǒng)一維非遞歸算法NRSCSE算法相比，采用ONRSCSE算法的優(yōu)化效果更高，降低加法器資源的比率平均為10.05%(12 bit量化)和7.21%(16 bit量化).同時，優(yōu)化的效果受階數(shù)的變化影響較小，呈現(xiàn)非常穩(wěn)定的特性.由于ONRSCSE對相鄰系數(shù)的共同項提取結(jié)果直接通過D觸發(fā)器進入下一級運算，對濾波器的邏輯深度沒有影響，因此ONRSCSE和一維非遞歸算法一樣，仍然具有最低邏輯深度特性.

3.3 本算法與傳統(tǒng)算法的比較

對數(shù)據(jù)集2的7種12 bit量化的濾波器進行優(yōu)化，分別采用BHM、RAG-n、HCUB、NRSCSE、ONRSCSE算法進行設(shè)計，每種濾波器的10組系數(shù)優(yōu)化結(jié)果LA與LD進行平均，得到相同階數(shù)內(nèi)濾波器優(yōu)化的平均優(yōu)化結(jié)果.記錄最終得到的平均加法器個數(shù)(Mean logic adder,MLA)和平均邏輯深度(Mean logic depth,MLD)，進行優(yōu)化效果對比.其中BHM、RAG-n、HCUB的濾波器優(yōu)化算法由Voronenko[18]提供，優(yōu)化結(jié)果對比見表4.

表4 ONRSCSE與NRSCSE、BHM、RAG-n、HCUB的優(yōu)化效果對比

對優(yōu)化結(jié)果的加法器資源和邏輯深度進行繪圖，得到算法性能對比如圖4所示?？梢钥吹?，在31～101階的一共70組12 bit系數(shù)量化濾波器中，非遞歸的濾波器優(yōu)化算法NRSCSE算法相比于遞歸式算法HCUB、BHM、RAG-n，邏輯深度最低，加法器資源最高，優(yōu)化后的ONRSCSE算法邏輯深度與NRSCSE算法相同，均保持為最低，但是加法器資源已經(jīng)明顯優(yōu)于HCUB、BHM、RAG-n，取得了最好的效果.由于ONRSCSE只依靠系數(shù)內(nèi)的公共項，不利用系數(shù)值進行下一步的系數(shù)優(yōu)化，系數(shù)間不存在依賴關(guān)系，不會對后續(xù)的綜合產(chǎn)生影響，非常有利于算法的綜合與實現(xiàn).

圖4 ONRSCSE/NRSCSE/HCUB/BHM/RAG-n算法的加法器資源與邏輯深度對比

4 結(jié) 論

1)本文首次提出了結(jié)合系數(shù)行公共項優(yōu)化和列公共項優(yōu)化的系數(shù)矩陣二維優(yōu)化方法，并將其運用到了非遞歸的FIR濾波器優(yōu)化算法中，取得了較好的效果. 首先將系數(shù)用CSD法表示，降低了系數(shù)中的非0值個數(shù)；然后對系數(shù)矩陣進行行系數(shù)分解，降低行系數(shù)中的加法器個數(shù)；之后對殘余矩陣進行公共項提取，進一步降低整體加法器個數(shù).

2)相比于現(xiàn)有的一維非遞歸算法，本算法可節(jié)省10.05%(12 bit量化)和7.21%(16 bit量化)加法器個數(shù).在低階濾波器的優(yōu)化中，加法器使用量降低到了傳統(tǒng)的CSD表示法的30%左右.仿真結(jié)果表明，在階數(shù)低于100、量化位寬為12 bit時平均加法器個數(shù)和深度指標均優(yōu)于已發(fā)表的NRSCSE、BHM、RAG-n、HCUB算法.