基于CSD编码混合遗传算法的IIR滤波器优化设计

岳颀　沈建东

摘要：该文针对滤波器功耗过大的问题，采用基于CSD（canonic signed digit）编码的模拟退火遗传算法对IIR（Infinite Impulse Response）滤波器进行优化设计.给出了CSD编码经过交叉、变异后可能出现问题的解决方法.并根据CSD编码特点对遗传算子进行改进，提高了寻优速度.仿真表明，该文方法在降低功耗的同时，可有效加快优化搜索速度，减小通带波纹.

关键词：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

通常，數字滤波器的硬件实现需要大量乘法器[1].因此减少硬件资源开销、降低功耗成为滤波器设计中急需解决的问题.由De la Serna A.E提出的CSD（Canonic Signed Digit）量化编码，可有效减少硬件乘法器结构，为设计基于CSD 量化系数的滤波器提供了理论依据[2].

IIR数字滤波器由于可用较低的阶数实现较好的选频特性，因而得到广泛应用.目前IIR数字滤波器一般都是在一定的优化准则下用优化算法设计.本文引入CSD编码后，将滤波器设计问题转换成了STP（Sign Two Power）空间上的非线性寻优[3].这时，常规优化算法都不再适用.而混合遗传算法克服了普通遗传算法早熟、跳出局部最优能力弱的缺点，鲁棒性强且全局收敛，成为求解非线性优化问题的有力工具.

本文以基于CSD编码的混合遗传算法为工具，对IIR滤波器优化进行研究.对CSD编码在遗传算子操作后可能不再符合编码规则的问题， 提出来简明的解决方法.并对遗传算子进行了一定改进，提高了算法的寻优速度，避免了陷入局部极值.

1 CSD编码规则

数字电路通过序列移位相加来实现乘法运算，每增加一位非零位就要增加一次移位操作，因而编码中的非零位数直接影响芯片的面积和功耗.CSD编码是一种三元数值系统， 和其它编码相比，在表示同一浮点数时具有较少的非零位.因此，在乘法运算中可有效减少部分积的乘积项，从而减少加法器数量[2][4].

3 针对CSD编码的混合遗传算法

模拟退火遗传算法是一种混合优化算法.它综合了模拟退火算法局部搜索能力强和遗传算法全局寻优控制优秀的特点.利用模拟退火算法控制混合算法的收敛性以避免“早熟”、提高寻优性能，利用遗传算法的并行化抽样过程加快寻优速度.

混合算法的基本思想是通过选择、交叉、变异产生一组新个体，然后再独立地对产生的各个个体进行模拟退火操作，以其结果作为子代个体.如此反复迭代直至满足终止条件为止.混合算法包括编码、初始种群生成、适应度函数、选择、交叉、变异、模拟退火、终止条件等八个主要部分.

3.1编码、初始种群生成

编码就是将问题的解空间数据映射成遗传空间的基因串，本文映射为CSD编码.

对于IIR滤波器，由式（2），（5），（6）可看出其实际待优化参数共[4N]个，即[（a1，b1，c1，d1，a2，b2，c2，d2，…，aN，bN，cN，dN）]为了保证滤波器的稳定性，要求每个二阶环节的极点都位于[Z]平面单位圆内，因而得到[-2初始化时可直接根据待优化参数个数[4N]、初始种群数[C]、量化长度[L]及量化非零位数[B]，随机生成[C]组[4N×L]位CSD编码作为初始种群.其中[B]位非零位均匀分布在各[L]位编码中.

3.2适应度函数

3.3遗传算子

采用CSD编码的混合遗传算法优化设计IIR滤波器，存在收敛速度慢及CSD编码交叉、变异后可能不再符合编码规则等问题.针对这些问题，我们采取以下若干措施.

3.3.1 遗传算子改进

1）选择算子

选择就是从当前群体中选出优良个体，使其有机会繁衍子孙.为了保证收敛到全局最优解、避免早熟.本文在选择操作时，将适应度最高的个体直接遗传到子代，将适应度最低的个体放弃.

2） 交叉

虽然选择算子直接复制最优个体可保证种群向最优方向移动，但只能在现有种群内寻优，交叉算子可保证个体的多样性，是获得全局最优解的基础.由于滤波器待优化参数个数的编码长度随系统传递函数阶数的增长而变长，因而染色体单点交叉难以满足收敛速度需求.为此，我们以交叉概率[pc]在每个编码中随机选择[L4]个点进行多点交叉.并在交叉后计算父代、子代适应度，选择其中适应度高的2个个体进入子代.

3）变异算子

复制、交叉只能在现有的基因型的排列组合内寻找最优，不能产生新的基因型.为了防止陷入局部最优解，并防止过多的零位突变为非零位后增大运算复杂度，我们采用染色体多点等概率变异方式.即当在子代种群最大适应度与最小适应度的差小于规定数值时，以远大于通常的变异概率对其变异，否则，从每个基因中随机选取一个变异位置以一定的变异概率[pm]在[{-1，0，1}]中进行突变.并且要求从0突变到[{-1，1}]的概率等于从[{-1，1}]突变到0的概率.这样可以保证有效减少乘法运算复杂度.

4）模拟退火算子

将子代中10%的最优个体保留，10%的最差个体抛弃.然后再在余下个体中随机选择60%的个体，根据模拟退火法Metropolis准则[5]进化产生新个体.与保留的最优个体共同组成新的子代种群.

3.3.2 CSD编码在变异交叉时遇到的问题与解决方法

在采用CSD编码的模拟退火遗传算法中，CSD编码在交叉、变异后编码可能不再符合编码规则.对于这些不合规则的染色体，本文用与其十进制数最相近的CSD编码替代.步骤如下：

首先，将操作后编码[d0，d1，d2...，dx，...，dM]记为[CSD]，将[d1，d2...，dx，...，dM，d0]的转置记为[CSDcheck].计算[CSD?CSDcheck]，其中若有非零位，则编码不符合规则.记非零位位置为[P]。

其次，对于不合规则的CSD编码，将其解码为十进制数.若解码后编码可表示的上、下界，则将用最大、最小编码替代当前编码.否则，将紧邻[P]位的后两位分别置为[0，1]。

最后，循环前两步，直至编码非零位总数等于规定量化非零位数[B]时终止循环， 并将循环結束位后所有位置0

4 应用实例

设计带通IIR数字滤波器，滤波器技术要求为：

初始化时，规定系数编码长度[L]=17，非零位数[B]=6， 种群[C]=200，交叉概率[Pc]=0.2，变异概率[Pm]=0.08. 图1、图2为直接截断系数和优化IIR滤波器系数的频率响应比较.图2是图1的放大.图3为IIR滤波器优化设计的进化误差曲线.

仿真表明，直接截断滤波器通带纹波约为0.0081，优化设计滤波器的通带纹波约为0.0035，通带纹波大约减小了2.31倍. 从图中可以看出，用本文方法设计的带通滤波器具有较好幅频响应.

5 结束语

本文为了减少滤波器硬件资源开销，降低运算量，将CSD （Canonic Signed Digit） 编码引入混合遗传算法，优化设计IIR滤波器.针对滤波器设计多参数多极值的具体特点，对混合算法算子进行改进. 并给出解决CSD编码在交叉、变异后可能出现的问题的方法.仿真表明本文方法在减少滤波器运算量的同时，可有效减少通带波纹，提高搜索速度.

参考文献：

[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] 康立山，谢云，尤矢勇，等.非数值并行算法（第一册）模拟退火算法[M].北京：科学出版社，2000：78-79.