岳頎　沈建東

摘要：該文針對濾波器功耗過大的問題，采用基于CSD（canonic signed digit）編碼的模擬退火遺傳算法對IIR（Infinite Impulse Response）濾波器進行優(yōu)化設計.給出了CSD編碼經(jīng)過交叉、變異后可能出現(xiàn)問題的解決方法.并根據(jù)CSD編碼特點對遺傳算子進行改進，提高了尋優(yōu)速度.仿真表明，該文方法在降低功耗的同時，可有效加快優(yōu)化搜索速度，減小通帶波紋.

關鍵詞：CSD編碼；遺傳算法；模擬退火算法；IIR濾波器

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）08-0201-03

Abstract： This paper is concerned with the development of a new technique for the optimization of IIR digital filters over the CSD coefficient space based on the simulated annealing-genetic algorithms. A novel approach was presented for the restoration of CSD numbers to their correct format after the application of crossover and mutation operations in the algorithm. By improving the genetic operations， the algorithms converge faster. Simulation results show that the passband ripple is reduced and faster convergence is obtained.

Key words： CSD Encoding；Genetic Algorithm；Simulated Annealing； IIR Filter

通常，數(shù)字濾波器的硬件實現(xiàn)需要大量乘法器[1].因此減少硬件資源開銷、降低功耗成為濾波器設計中急需解決的問題.由De la Serna A.E提出的CSD（Canonic Signed Digit）量化編碼，可有效減少硬件乘法器結構，為設計基于CSD 量化系數(shù)的濾波器提供了理論依據(jù)[2].

IIR數(shù)字濾波器由于可用較低的階數(shù)實現(xiàn)較好的選頻特性，因而得到廣泛應用.目前IIR數(shù)字濾波器一般都是在一定的優(yōu)化準則下用優(yōu)化算法設計.本文引入CSD編碼后，將濾波器設計問題轉換成了STP（Sign Two Power）空間上的非線性尋優(yōu)[3].這時，常規(guī)優(yōu)化算法都不再適用.而混合遺傳算法克服了普通遺傳算法早熟、跳出局部最優(yōu)能力弱的缺點，魯棒性強且全局收斂，成為求解非線性優(yōu)化問題的有力工具.

本文以基于CSD編碼的混合遺傳算法為工具，對IIR濾波器優(yōu)化進行研究.對CSD編碼在遺傳算子操作后可能不再符合編碼規(guī)則的問題， 提出來簡明的解決方法.并對遺傳算子進行了一定改進，提高了算法的尋優(yōu)速度，避免了陷入局部極值.

1 CSD編碼規(guī)則

數(shù)字電路通過序列移位相加來實現(xiàn)乘法運算，每增加一位非零位就要增加一次移位操作，因而編碼中的非零位數(shù)直接影響芯片的面積和功耗.CSD編碼是一種三元數(shù)值系統(tǒng)， 和其它編碼相比，在表示同一浮點數(shù)時具有較少的非零位.因此，在乘法運算中可有效減少部分積的乘積項，從而減少加法器數(shù)量[2][4].

3 針對CSD編碼的混合遺傳算法

模擬退火遺傳算法是一種混合優(yōu)化算法.它綜合了模擬退火算法局部搜索能力強和遺傳算法全局尋優(yōu)控制優(yōu)秀的特點.利用模擬退火算法控制混合算法的收斂性以避免“早熟”、提高尋優(yōu)性能，利用遺傳算法的并行化抽樣過程加快尋優(yōu)速度.

混合算法的基本思想是通過選擇、交叉、變異產(chǎn)生一組新個體，然后再獨立地對產(chǎn)生的各個個體進行模擬退火操作，以其結果作為子代個體.如此反復迭代直至滿足終止條件為止.混合算法包括編碼、初始種群生成、適應度函數(shù)、選擇、交叉、變異、模擬退火、終止條件等八個主要部分.

3.1編碼、初始種群生成

編碼就是將問題的解空間數(shù)據(jù)映射成遺傳空間的基因串，本文映射為CSD編碼.

對于IIR濾波器，由式（2），（5），（6）可看出其實際待優(yōu)化參數(shù)共[4N]個，即[（a1，b1，c1，d1，a2，b2，c2，d2，…，aN，bN，cN，dN）]為了保證濾波器的穩(wěn)定性，要求每個二階環(huán)節(jié)的極點都位于[Z]平面單位圓內(nèi)，因而得到[-2初始化時可直接根據(jù)待優(yōu)化參數(shù)個數(shù)[4N]、初始種群數(shù)[C]、量化長度[L]及量化非零位數(shù)[B]，隨機生成[C]組[4N×L]位CSD編碼作為初始種群.其中[B]位非零位均勻分布在各[L]位編碼中.

3.2適應度函數(shù)

3.3遺傳算子

采用CSD編碼的混合遺傳算法優(yōu)化設計IIR濾波器，存在收斂速度慢及CSD編碼交叉、變異后可能不再符合編碼規(guī)則等問題.針對這些問題，我們采取以下若干措施.

3.3.1 遺傳算子改進

1）選擇算子

選擇就是從當前群體中選出優(yōu)良個體，使其有機會繁衍子孫.為了保證收斂到全局最優(yōu)解、避免早熟.本文在選擇操作時，將適應度最高的個體直接遺傳到子代，將適應度最低的個體放棄.

2） 交叉

雖然選擇算子直接復制最優(yōu)個體可保證種群向最優(yōu)方向移動，但只能在現(xiàn)有種群內(nèi)尋優(yōu)，交叉算子可保證個體的多樣性，是獲得全局最優(yōu)解的基礎.由于濾波器待優(yōu)化參數(shù)個數(shù)的編碼長度隨系統(tǒng)傳遞函數(shù)階數(shù)的增長而變長，因而染色體單點交叉難以滿足收斂速度需求.為此，我們以交叉概率[pc]在每個編碼中隨機選擇[L4]個點進行多點交叉.并在交叉后計算父代、子代適應度，選擇其中適應度高的2個個體進入子代.

3）變異算子

復制、交叉只能在現(xiàn)有的基因型的排列組合內(nèi)尋找最優(yōu)，不能產(chǎn)生新的基因型.為了防止陷入局部最優(yōu)解，并防止過多的零位突變?yōu)榉橇阄缓笤龃筮\算復雜度，我們采用染色體多點等概率變異方式.即當在子代種群最大適應度與最小適應度的差小于規(guī)定數(shù)值時，以遠大于通常的變異概率對其變異，否則，從每個基因中隨機選取一個變異位置以一定的變異概率[pm]在[{-1，0，1}]中進行突變.并且要求從0突變到[{-1，1}]的概率等于從[{-1，1}]突變到0的概率.這樣可以保證有效減少乘法運算復雜度.

4）模擬退火算子

將子代中10%的最優(yōu)個體保留，10%的最差個體拋棄.然后再在余下個體中隨機選擇60%的個體，根據(jù)模擬退火法Metropolis準則[5]進化產(chǎn)生新個體.與保留的最優(yōu)個體共同組成新的子代種群.

3.3.2 CSD編碼在變異交叉時遇到的問題與解決方法

在采用CSD編碼的模擬退火遺傳算法中，CSD編碼在交叉、變異后編碼可能不再符合編碼規(guī)則.對于這些不合規(guī)則的染色體，本文用與其十進制數(shù)最相近的CSD編碼替代.步驟如下：

首先，將操作后編碼[d0，d1，d2...，dx，...，dM]記為[CSD]，將[d1，d2...，dx，...，dM，d0]的轉置記為[CSDcheck].計算[CSD?CSDcheck]，其中若有非零位，則編碼不符合規(guī)則.記非零位位置為[P]。

其次，對于不合規(guī)則的CSD編碼，將其解碼為十進制數(shù).若解碼后編碼可表示的上、下界，則將用最大、最小編碼替代當前編碼.否則，將緊鄰[P]位的后兩位分別置為[0，1]。

最后，循環(huán)前兩步，直至編碼非零位總數(shù)等于規(guī)定量化非零位數(shù)[B]時終止循環(huán)， 并將循環(huán)結束位后所有位置0

4 應用實例

設計帶通IIR數(shù)字濾波器，濾波器技術要求為：

初始化時，規(guī)定系數(shù)編碼長度[L]=17，非零位數(shù)[B]=6， 種群[C]=200，交叉概率[Pc]=0.2，變異概率[Pm]=0.08. 圖1、圖2為直接截斷系數(shù)和優(yōu)化IIR濾波器系數(shù)的頻率響應比較.圖2是圖1的放大.圖3為IIR濾波器優(yōu)化設計的進化誤差曲線.

仿真表明，直接截斷濾波器通帶紋波約為0.0081，優(yōu)化設計濾波器的通帶紋波約為0.0035，通帶紋波大約減小了2.31倍. 從圖中可以看出，用本文方法設計的帶通濾波器具有較好幅頻響應.

5 結束語

本文為了減少濾波器硬件資源開銷，降低運算量，將CSD （Canonic Signed Digit） 編碼引入混合遺傳算法，優(yōu)化設計IIR濾波器.針對濾波器設計多參數(shù)多極值的具體特點，對混合算法算子進行改進. 并給出解決CSD編碼在交叉、變異后可能出現(xiàn)的問題的方法.仿真表明本文方法在減少濾波器運算量的同時，可有效減少通帶波紋，提高搜索速度.

參考文獻：

[1] Pngw W. Fully sigma-delta modulation encoded FIR filter [J]. IEEE Trans Signal Processing， 1992， 40（6）：1605-1610.

[2] De la Serna A.E， Soderstrand M.A. Trade-off between FPGA resource utilization and round-off error in optimized CSD FIR digital filters [C]. IEEE Asilomar Conference， Paris： Circuits and Systems， 1994：105-106.

[3] Abhijit C.， Sudipta C.， Supremacy of Differential Evolution Algorithm in Designing Multiplier-Less Low-Pass FIR Filter[C]. World Academy of Science， Engineering and Technology， International Journal of Electrical， Electronic Science and Engineering， 2014；8（2）：110-112.

[4] Guo R.， L. S. DeBrunner， K. Johansson. Truncated MCM using Pattern Modification for FIR Filter Implementation. 2010 IEEE International Circuits and Systems， London： Circuits and Systems， 2010：3881-3884.

[5] Ashrafzadeh F.， Nowrouzian B.， Crossover and mutation in genetic algorithms employing canonical signed-digit number system [J]. In Proceedings of the 1997 Midwest Symposium on Circuits and Systems， Sacramento， California， Aug.1997：259-264.

[6] Oppenheim A. V.， Schafer R. W. Digital Signal Processing [M].London： Prentice-Hall， 1975：39～40.

[7] 康立山，謝云，尤矢勇，等.非數(shù)值并行算法（第一冊）模擬退火算法[M].北京：科學出版社，2000：78-79.