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

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

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

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

1 一維非遞歸算法

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

(1)

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

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

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

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

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提取公共項(xiàng)101/10-1后，得到剩余矩陣(后文稱(chēng)為殘余矩陣)為

(4)

則整體表示法為

(5)

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

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

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

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

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

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

(6)

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

不難推算，NRSCSE算法優(yōu)化的殘余矩陣中非零項(xiàng)越多，列公共項(xiàng)出現(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，下標(biāo)i代表第i次系數(shù)分解，H0為初始化系數(shù)矩陣.

2.1.2 殘余矩陣

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

2.2 算法描述

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

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

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

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

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

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

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

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

2.3 算法復(fù)雜度分析

3 結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

表3 ONRSCSE對(duì)NRSCSE的提升效果

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

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

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

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

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

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

對(duì)優(yōu)化結(jié)果的加法器資源和邏輯深度進(jìn)行繪圖，得到算法性能對(duì)比如圖4所示?？梢钥吹剑?1～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)的公共項(xiàng)，不利用系數(shù)值進(jìn)行下一步的系數(shù)優(yōu)化，系數(shù)間不存在依賴(lài)關(guān)系，不會(huì)對(duì)后續(xù)的綜合產(chǎn)生影響，非常有利于算法的綜合與實(shí)現(xiàn).

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

4 結(jié) 論

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

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