帕克斯-麦克莱伦算法

帕克斯-麦克莱伦算法(英语:Parks–McClellan algorithm,又称为Remez-exchange algorithm、Mini-max algorithm),为一个用以设计优化有限脉冲响应滤波器(finite impulse response filter)的迭代算法,由James McClellan和Thomas Parks于1972年的著作中提出。

此算法的主要精神,在于利用迭代的方式最小化滤波器在通带(pass band)和止带(stop band)的最大误差,因此有时也称为最小化最大误差算法(Mini-max filter design)。由于帕克斯-麦克莱伦算法也属于Remez-exchange algorithm为了设计有限脉冲响应滤波器而产生的一种变形,因此也有人以Remez-exchange algorithm代称。

有限脉冲响应滤波器设计

编辑

有限脉冲响应滤波器(finite impulse response filter)利用有限的点数来表示滤波器的脉冲响应,对于N点有限脉冲响应滤波器

 

有限脉冲响应滤波器的优点在于脉冲响应是有限的,使得设计上较为简单。然而如何在有限的点数下,设计出效果最近似于理想目标的滤波器,则是帕克斯-麦克莱伦算法所欲解决的问题。

对于滤波器设计,帕克斯-麦克莱伦算法的精神在于最小化最大误差。在忽略通带与止带之间转换带(transition band)的情况下,最小化通带与止带的最大误差: 

其中 为设计滤波器的频率响应, 则为理想目标滤波器的频率响应。

在数字滤波器设计中,常常会将信号的频率做取样,使得频谱具有周期性。设计者即可针对一个周期去做计算就好,减少计算量。所以前两行的最大误差可写成:

 

其中 为正规化频率(normalized frequency): 

滤波器设计时,可利用weighting function将较重要的频带比重放大。如此一来,在利用帕克斯-麦克莱伦算法设计滤波器时,则会较重视比重较大频带的误差。

若在加入weighting function情况下,可将帕克斯-麦克莱伦算法一般化。此时的最大误差则可表示为: 

另外在数学上,此种将向量取绝对值并找出某个最大的元素的算法,称为取 范数。若能将 离散化写成矩阵的形式,就可以用此方法快速找出最大误差。

帕克斯-麦克莱伦算法

编辑

下面的文章将说明如何以该算法设计优化滤波器,假设

  • 滤波器长度为N,且N为奇数可表示成 
  • 目标滤波器的频率响应 偶函数
  •  用以表示所指定的权重函数(weighting function)。功用是将特定频段(通常是通带内)的误差调得更小,重视某频段的优化。

此算法共分为6个步骤:

  1. 设置极值点起始值
    在范围 的范围内,任意选择 点频率 作为极值点(extreme frequency)的起始值。
    将此时的最大误差 设为 ,但所选择的 点起始值不能落在转换频带(transition band),也不能将所有的起始值设在止带(stop band)上。
    极端频率为最后完成设计的滤波器频率响应中,会出现最大误差的频率。一开始所给定的起始值是随机的,会在此算法之后的步骤中逐渐收敛。
    此时,令在各点极端频率的误差为 。 其中e为设计滤波器响应式与理想滤波器响应式在相对应频率点的误差值。
  2. 计算目前的频率响应
    为了方便算法运算之后的进行,我们可稍微整理误差的表示方式。若令
     。此 是设计的滤波器响应 的平移。  的正中央项 ( 举例:  )。
      。因为 偶函数,所以 也是偶函数,则再设计 ,计算 的一半范围就好。
    如此一来,可将在第1步骤中所得到的误差式表示为:
     
    其中,
      (由于使用 ,计算项次从0到k)
    经过整理之后可得
     
    上述的误差关系式,可表示为矩阵形式 
     
    因此,我们可由 计算 
  3. 计算误差函数
    计算误差函数 
     
  4. 查找极值点
     中,找k+2个区域极大或极小值,将区域极大或极小值出现的频率标示为 
    区域极大或极小值的判断规则:
    • 不是在边界处的区域高峰(peaks)或低谷(dips)。在此,边界区域即为 以及频率转换带的两边。
    • 对于在边界区域的频率点,可用下列的标准判断是否为区域极大或极小:  为同相时,右边界是极值点;反相时,左边界是极值点;其他情况非极值点。
    若找到多于 个极值点,选择极值点的优先顺位为:
    1. 优先选择不在边界的极值点。
    2. 其次选在边界的极值点中, 较大的,直到凑足 个极值点为止。
    3. 当边界的极值点的 一样大时,优先选择转换频带两旁的点。
  5. 判断误差是否收敛
    计算误差的最大值,令其为 
     为现在的误差最大值, 为前一轮计算的误差最大值,则利用下列规则判断算法的下一步:
    1.  ,设置 ,回到步骤2。
    2.  ,进行步骤6。
  6. 计算所设计滤波器的脉冲响应 
    由先前在步骤2中的关系式,我们可得
     
     即为我们所求的脉冲响应。
权重函数 滤波器响应的影响
编辑

当权重函数在带内设计为1,在带外设计为小于1,会让滤波器较重视通过带通频段的信号。

当权重函数在带外设计为1,在内设计为小于1,会让滤波器具有较好的滤除噪声的能力。

特征

编辑

用此方法设计出来的滤波器,一定会满足以下两个情况:

  1. 有k+2个以上的极值点(极大点与极小点)。
  2. 在极点上, 
过渡频段
编辑

过渡频段(transition band)对设计滤波器的误差也会有影响。将过渡频段设计地窄一些,  的误差就会比较大;将过渡频段设计地宽一些,  的误差就会比较小。再设计上可以适当的增加过渡频段宽度,让通带和止带地响应更趋近于理想值。

假设我们想要带通段的涟波小于等于 ,带止段的涟波小于等于 ,过渡频段小于  (    为过渡频段的上、下界)。则要设计滤波器长度 为:

 

移项可得: 

若要设计的频段中有多的过渡频段,则 取最小长度的过渡频段带入计算。

对于一固定长度的数字滤波器,再设计上可以牺牲一些频段留给过渡频段,将涟波缩小。但要注意不可将过渡频段设计过长,因为过渡频段是无法使用的。

参考文献

编辑
  • Jian-Jiun Ding (2013), Advanced Digital Signal Processing页面存档备份,存于互联网档案馆) [viewed 27/06/2013]
  • T. W. Parks and J. H. McClellan, “Chebyshev Approximation for Nonrecursive Digital Filter with Linear Phase”, IEEE Trans. Circuit Theory, vol. 19, no. 2, pp. 189-194, March 1972.
  • J. H. McClellan, T. W. Parks, and L. R. Rabiner “A computer program for designing optimum FIR linear phase digital filter”, IEEE Trans. Audio- Electroacoustics, vol. 21, no. 6, Dec. 1973.
  • F. Mintz and B. Liu, “Practical design rules for optimum FIR bandpass digital filter”, IEEE Trans. ASSP, vol. 27, no. 2, Apr. 1979.