关键字 |
遗传算法,信号处理,抽取,数字滤波,优化,重采样。 |
I.INTRODUCTION |
在信号处理理论中,在许多应用中,转换(增加或减少)采样率[1]是有利的,甚至是必要的。将原始信号的采样率降低到某个整数因子下的采样率的过程是低通滤波和抽取过程的结合。当在多个阶段实现时,采样率转换(SRC)通常需要更少的乘法和每秒加法。尽管多级实现提高了某些滤波器系数的计算速度,但总体每秒乘法和加法(MADS)和所需的系数存储都减少了。此外,多级实现减轻了信号和滤波器系数的字长要求,进一步减少了计算量。多级SRC的另一个好处是使用特殊的滤波器结构。例如,半带滤波器在抽取两个有效,因为它们的多相分支之一是纯延迟[1]。级联积分器-梳状抽取器[2][23]由于其简单,无乘法器结构,在窄止带应用中表现良好,是高效的。这是多级抽取法利用两者的x好处。之前Crochiere和Rabiner定量地考虑了进行采样率降低[1]的计算成本。 Occasional examples of multistage decimation filters appear in more recent literature [3], [4]. For instance, Kale et al. [4] used a cascade of seven stages with a sample-rate reduction of two at each stage. That work employed all-pass infinite impulse response recursive digital filters and was concerned with efficient hardware realizations. However, the best way to split mentioned operations into its component stages is not known to best of our knowledge [11]. A possible solution for the design of multistage decimators using finite impulse response (FIR) filters based upon the minimization of the multiplies and add per sec is presented in [20] and [21]. Starting from the method for determination of multistage decimation ratios published in [20], the method for design of the optimized multistage decimation filter chain for two and three-stages and four stage is analysed and number of stages are finally decided for the case which have minimum multiplies and addition per second as three [1]. The aim is to minimize overall multiplication and addition per second which can be achieved by reducing overall number of multipliers, and by shifting the most of multipliers to the lower sampling rate [22]. In this work genetic algorithm is used for finding optimum decimation factor of multistage decimator components for minimum multiplication and addition per second. Genetic algorithm is an optimization technique based on natural evolution that is the change over a long period of time .The Genetic Algorithms [7], [9] provide robust and efficient search in complex spaces. Survival of the fittest “genes” and structured yet randomized genetic operations are the basic philosophies behind the algorithms. The main advantages of Genetic Algorithms have been successfully applied to control problems in ATM networks, such as bandwidth allocation [16] and buffer management [17]. Recently, they have been applied to point-to-point routing [18] and spanning tree problem [19] in communication networks. |
并与已有方法的结果进行了比较。仿真结果表明,该方法在抽取率较高的情况下,也能求解几乎相同的多级抽取器优化问题,降低了数学复杂度。在第二节中,讨论了多级抽取器结构。第三节讨论了遗传算法,第四节用遗传算法求解了多阶段优化问题。第4节给出了设计实例,第5节给出了结论。 |
2优化的多级抽取 |
多级抽取(或插值)可以减少滤波器规格中滤波器系数的数量。由讨论[1]可知,滤波级的过渡宽度、滤波长度取决于该特定级的抽取率。因此,在多级抽取中,每段抽取率的确定是非常重要的。如果总抽样率抽取比D可以因数带入乘积 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1794-e001.gif) |
一个¯害怕一个½¯害怕一个½¯害怕害怕一个½¯½是整数,然后杀害多人者可以使用K implemen ted阶段是图1所示(一个),其中x (n)和y (m)表示离散输入和离散输出信号和H (z)传递函数。为了设计和分析,可以将图1(a)所示的图重新画成图1(b)[1],[2]的等效单级形式,其中D=D1*D2。and H(z)= H1(z)*H2(z) |
设Δf=(fc-fp)/fs为归一化跃迁带宽,其中fc为停止带边频率,fp为通带边频率,fs为采样频率。为了使每秒的乘法和加法总数最小化,使用近似目标函数[1],如式(2)所示。 |
(2) |
![](//www.cheescube.com/articles-images/IJAREEIE-1794-e003.gif) |
很明显,为了获得函数RT的最小值,对于给定的阶段数,多元函数S必须最小,K.由于多元函数S依赖于组成阶段的抽取因子,且只有使用d的最优值才能使其最小化,因此,在K=2和K=3的情况下,即三阶段和两阶段抽取器,对上述函数进行了优化。用所提出的方法计算了相应的个体抽取比和目标函数的最小值,为抽取器中阶段数的选择提供了逻辑比较。 |
3(1)所提出的遗传算法方法 |
III.1.1遗传算法 |
遗传算法的基本原理由Holland[7]首先提出。此后出现了一系列文献[8]、[9]和报告[10]、[11]、[12]。遗传算法是一种受自然选择机制启发的优化技术。自然选择是一种生物过程,具有最佳特征的个体更有可能适应环境,从而繁衍和生存。这些有利的个体在它们之间交配,产生具有相似特征的后代,因此有利的特征被保留,不利的特征被破坏,导致物种的渐进进化。 |
人工遗传算法的目标是通过保持输入变量的最佳组合来改进问题的解决方案。首先定义要优化的问题,生成一个目标函数来评估可能的候选解决方案(染色体)。生成n个个体的初始随机种群。种群大小通常是用户指定的参数,是影响遗传算法可扩展性和性能的重要因素之一。例如,较小的种群规模可能导致过早收敛并产生不合格的解决方案。另一方面,较大的种群规模会导致不必要的宝贵计算时间的消耗。尽管在[15]中给出了一些指导方针,但这个群体的大小因问题而异。这n个个体被称为染色体,用二进制字符串表示,其中染色体的每个二进制位置称为一个基因,表示一个特定的特征(输入变量)。 |
每个染色体都在目标函数中进行评估,选择最好的个体进行交配(父母),而最差的则被丢弃,为新的后代腾出空间。下一步是根据父母的信息,创造出第二代个体。[14]有几种交配方式。 |
通过遗传算子交叉点和突变将父节点的二进制信息传递给子节点。为每个新孩子随机选择新的父母,这一过程一直持续到染色体种群恢复到原始大小n。突变的目的是为种群引入多样性,允许算法通过在染色体中产生新的基因组合来避免局部极小值。 |
最后,在突变完成后,用目标函数评估新一代染色体,并用于所述算法的下一个迭代。该算法迭代,直到创建最大数量的染色体代或达到一个满意的解决方案 |
计算多级Decimator的最佳抽取比,使每秒的乘法和加法最小化。当K=2(两级decimator)时,[20]中给出的计算量最小的目标函数为 |
(3) |
当K=3(三级decimator)时,[20]中给出的计算量最小的目标函数为 |
(4) |
其中,遗传算法作为启发式搜索方法,用于上述问题中最优抽取因子检测的高效搜索和快速收敛工具。对于上述明确定义的问题,简单遗传算法的工作参数设置如下: |
1.Population:初始Population类型指定适应度函数的输入类型。这里使用的填充是双向量类型。这里定义一代人中个体数量的种群大小为20。第一阶段抽取因子的边界基于[5]所选择的迭代方法。类似地,后续阶段的抽取因子将被认为接近2,因为它是最小的整数抽取因子。总体的初始范围也可以借助这些界限得到。2.适应度函数:本例中的适应度函数为(3)式中每个个体的适应度函数。适应度函数的主要目的是获得最优个体进行最优检测。 Now the scaling function converts raw fitness scores returned by the fitness function to values in a range that is suitable for the selection function. Scaling function Rank is used here which scales the raw scores based on the rank of each individual, rather than its score. The rank of an individual is its position in the sorted scores. The rank of the fittest individual is 1, the next fittest is 2, and so on. Rank fitness scaling removes the effect of the spread of the raw scores. |
3.选择:选择函数根据适应度缩放函数中的缩放值为下一代选择父母。随机均匀分布是这样一条线,在这条线中,每个父结点对应于一条长度与其期望成比例的线的一段。算法沿着这条线以相同大小的步骤移动,每一步代表每一个父节点。在每一步中,算法从它所在的部分分配一个父节点。第一步是一个小于步长的均匀随机数。 |
4.繁殖:它决定了遗传算法如何在每一代创造后代。Elite count指定保证存活到下一代的个体数量,在本例中设置为2。Elite count必须是小于或等于Population size的正整数。现在执行交叉和突变。交叉产生的下一代的比例为0.8。突变在下一代中产生剩下的个体。因此,对于初始种群为20,精英数为2,交叉分数为0.8,则除精英子女外还有18个个体,因此算法将0.8*18 = 14.4舍入到14以得到交叉子女的数量。除了精英儿童外,其余4人都是突变儿童。 |
5.现在再次为这些新的子函数计算适应度函数,并重复此过程,直到满足停止标准。算法一直运行到适应度函数值随代的加权平均变化小于10- 6。这个过程的每一次迭代都被称为一代。GA通常迭代50到500或更多代。整个代的集合被称为一个运行。在运行结束时,种群中通常有一条或多条高度匹配的染色体。由于随机性在每次运行中扮演着重要角色,两次具有不同随机数种子的运行通常会产生不同的详细行为。遗传算法研究人员经常报告统计数据(例如在一次跑步中发现的最佳适合度以及发现最佳适合度的个体的世代),这些统计数据是在同一问题的许多次遗传算法的不同跑步中平均得出的。 |
四、结果与讨论 |
本节介绍应用优化方法所获得的一些结果。针对[5]中给定的规格,采用遗传算法计算了多级分量抽取因子。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1794-e005.gif) |
考虑不同阶段数的优化问题结果如表I所示。 |
由上表可知,对于同一组规格,K=3时所需的最小计算量。在K=3时,将所提方法的结果与前两种方法选择的符合条件的抽取因子集进行比较。[5]为迭代法D1选择一个合适的初始估计值,从而确定第一阶段抽取因子初始总体的界。另一个假设是,以后阶段的最小抽取因子必须在2附近,因为有抽取因子1将问题转换为更少阶段的抽取。对适合度最好的代的结果求平均,并且个体的数值与[20]中的结果匹配。 |
由于GA在每次运行中由于随机性给出不同的结果,然后对100次运行的结果进行平均。这些抽取比以十进制形式给出,以便与[1]直接比较。在实践中,比值必须取整数值,对于上述情况,值可以是D1= 6, D2= 2, D3=2。具体地说,这意味着总体的抽取率应该被选择为高比率的高度复合(非素数)。这些要点将被更详细地讨论,其中提出了提供整值率的一些指导方针。 |
此外,对于图3中Δf= 0.5和Δf= 0.1,使用所提出的方法的结果,将抽取率D1、D2和D3 = D/D1D2绘制在K = 3个阶段的对数-对数尺度上。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1794-e006.gif) |
诉的结论 |
本文提出了一种新的信号处理技术,利用遗传算法优化多速率多级抽取器的单次抽取比,使滤波器每秒的乘法和加法量最小。对于[1]中考虑的多级抽取器,计算并比较了独立抽取比。本文提出的多级抽取器设计方法采用了遗传算法技术,成功地适用于抽取率较高的任意规格集。 |
表格一览 |
![Click Here 表的图标](//www.cheescube.com/articles-images/table-icon.gif) |
![Click Here 表的图标](//www.cheescube.com/articles-images/table-icon.gif) |
表1 |
表2 |
|
|
数字一览 |
![Click Here 图1](//www.cheescube.com/articles-images/IJAREEIE-1794-g001.gif) |
![Click Here 图3](//www.cheescube.com/articles-images/IJAREEIE-1794-g003.gif) |
图1 |
图3 |
|
|
参考文献 |
- 罗奇埃,李国强,李国强,一九七五年。“用于抽取、插值和窄带滤波的最佳FIR数字滤波器实现”,IEEE Trans。Acoust。,Speech Signal Processing, vol. ASSP-23, 444.
- cliff Englewood多速率数字信号处理。新泽西州:Prentice-Hall, 1983。
- 克鲁科夫斯基A,凯尔I,海因K,还有。凯恩G. D,1994,“多相抽取器的设计技术”,第2版。计算机协会。通信系统的DSP(1994年4月)。每股26到29。
- 曾志伟、曾志伟、李志刚、李志刚1995。“用于测量σ - δ调制器性能的高保真十进制芯片,”IEEE Trans。Instrum。量。,vol. 44 (Oct.1995), 933–939.
- Feinleib R. E.和2001“数字多级子带调谐器的分析、设计和实现”,TRW系统。信息。抛光工艺。修订版J. 23, 2001春夏。
- Shively R. R 1975“带抽取的多级FIR滤波器”,IEEE tran . acoust。,语音信号处理,vol. assp - 23,1975。
- 霍兰德,1975。适应自然和人工系统。马萨诸塞州剑桥:麻省理工学院出版社。
- Van Nostrand Reinhold, 1991年《遗传算法手册》。纽约。
- 遗传算法在搜索、优化和机器学习中的应用。
- 比斯利博士,布尔博士,还有。Martin R. R 1993“遗传算法概述:部分I-Fundamentals,”计算机大学。,第15卷,no。2, 58 - 69。
- 比斯利博士,布尔博士,还有。Martin R. R 1993,“遗传算法的概述:第2部分研究课题”,清华大学学报(自然科学版)。第一版。,vol. 15, no.4, pp. 170-181.
- Srinivas M., Patnaik L. M. 1994。“遗传算法:一个调查”,计算机(1994年6月)17-26。
- 惠特利D. 1993“遗传算法教程”,计算机系。科罗拉多州立大学理工学院科学博士,众议员CS-93 103
- Haupt,兰迪。Haupt, Sue, 2004年。实用遗传算法。第二版。新泽西州:John Wiley & Sons
- 马福德。S. W.,1994,“共享方法的人口规模”,计算部。Sci,大学。伊利诺伊州厄巴纳-香槟市,非法众议员94005
- 潘慧、王宜义1991。“通过遗传算法的ATM带宽分配”,IEEE GLOBECOM ' 91, 125-129。
- .周L.-D。和。吴建龙。1995。“使用遗传算法和神经网络的缓冲区管理”,IEEE GLOBECOM ' 95, 1333-1337。
- 岛本,平松,山崎,1993。“基于遗传算法的动态路由控制”,1993年IEEE神经网络国际会议,1123-1128。
- Palmer C. C.和Kershenbaum A 1993。寻找最优通信生成树的两种算法。技术报告,IBM T. J.沃森研究中心,约克敦高地,纽约州。
- 科菲M.W. 2003“优化多级抽取和插值处理”,IEEE信号处理。列托人。,Vol. 10,No. 4, pp. 107-110, Apr. 2003.
- 科菲M.W. 2007“优化多级抽取和插值处理-第二部分”,IEEE信号处理。列托人。,Vol. 14, No. 1, 24-26, Jan. 2007.
- DE Troncoso Romero, M Laddomada“补偿梳状抽取滤波器的最优锐化:分析与设计”科学世界杂志2014年卷。
- Guillermo a . jacenod, Javier Valls, Javier Siman,“高效FPGA硬件复用的无乘子抽取链”,国际可重构计算杂志,论文ID 546264,卷2014。
|