帕克斯-麦克莱伦算法(英语: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为奇数可表示成
![{\displaystyle N=2k+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a27d5460e00f90698ba9ae53c31c5f943bf63845)
- 目标滤波器的频率响应
为偶函数
用以表示所指定的权重函数(weighting function)。功用是将特定频段(通常是通带内)的误差调得更小,重视某频段的优化。
此算法共分为6个步骤:
- 设置极值点起始值
- 在范围
的范围内,任意选择
点频率
作为极值点(extreme frequency)的起始值。
- 将此时的最大误差
设为
,但所选择的
点起始值不能落在转换频带(transition band),也不能将所有的起始值设在止带(stop band)上。
- 极端频率为最后完成设计的滤波器频率响应中,会出现最大误差的频率。一开始所给定的起始值是随机的,会在此算法之后的步骤中逐渐收敛。
- 此时,令在各点极端频率的误差为
。 其中e为设计滤波器响应式与理想滤波器响应式在相对应频率点的误差值。
- 计算目前的频率响应
- 为了方便算法运算之后的进行,我们可稍微整理误差的表示方式。若令
。此
是设计的滤波器响应
的平移。
为
的正中央项 ( 举例:
)。
。因为
为偶函数,所以
也是偶函数,则再设计
,计算
的一半范围就好。
- 如此一来,可将在第1步骤中所得到的误差式表示为:
![{\displaystyle \left[R(F_{m})-H_{d}(F_{m})\right]W(F_{m})=(-1)^{m+1}e,\;where\;m=0,1,2\ldots ,k+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99b9d2737dc24a103b3ce783332de8a6a2d57fb3)
- 其中,
(由于使用
,计算项次从0到k)
- 经过整理之后可得
![{\displaystyle \sum _{n=0}^{k}s[n]\cos(2\pi F_{m}n)+(-1)^{m}W^{-1}(F_{m})e=H_{d}(F_{m})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/590987e0ee5bdd3a2410794e64ad695f90d7f052)
- 上述的误差关系式,可表示为矩阵形式
![{\displaystyle Ax=H}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aba34ba82c87bb4bc646b0aa2de2a019dfbf7f57)
![{\displaystyle {\begin{bmatrix}1&\cos(2\pi F_{0})&\cos(4\pi F_{0})&\cdots &\cos(2\pi kF_{0})&1/W(F_{0})\\1&\cos(2\pi F_{1})&\cos(4\pi F_{1})&\cdots &\cos(2\pi kF_{1})&-1/W(F_{1})\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&\cos(2\pi F_{k})&\cos(4\pi F_{k})&\cdots &\cos(2\pi kF_{k})&(-1)^{k}/W(F_{k})\\1&\cos(2\pi F_{k+1})&\cos(4\pi F_{k+1})&\cdots &\cos(2\pi kF_{k+1})&(-1)^{k+1}/W(F_{k+1})\\\end{bmatrix}}{\begin{bmatrix}s[0]\\s[1]\\\vdots \\s[k]\\e\end{bmatrix}}={\begin{bmatrix}H_{d}[F_{0}]\\H_{d}[F_{1}]\\\vdots \\H_{d}[F_{k}]\\H_{d}[F_{k+1}]\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d769856cafac7f7757fb73cd71db0faf53630c2e)
- 因此,我们可由
计算![{\displaystyle s[0],s[1],\ldots ,s[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d14e9ef64f809feba5e977062351a03f080a7fb6)
- 计算误差函数
- 计算误差函数
![{\displaystyle err(F),\;for0\leq F\leq 0.5\;,F\notin transition\;band}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b11db8551d6a5c67344c845770c457d98be1310)
![{\displaystyle err(F)=\left[R(F)-H_{d}(F)\right]W(F)=\left\{\sum _{n=0}^{k}s[n]\cos(2\pi Fn)-H_{d}(F)\right\}W(F)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8bed4342f38a5e4408c6821fa957c474ede46d5)
- 查找极值点
- 从
中,找k+2个区域极大或极小值,将区域极大或极小值出现的频率标示为![{\displaystyle P_{0},P_{1},\ldots ,P_{k},P_{k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f183c972d3bb97225bc15e6b574f86dd1c947a29)
- 区域极大或极小值的判断规则:
- 不是在边界处的区域高峰(peaks)或低谷(dips)。在此,边界区域即为
以及频率转换带的两边。
- 对于在边界区域的频率点,可用下列的标准判断是否为区域极大或极小:
及
为同相时,右边界是极值点;反相时,左边界是极值点;其他情况非极值点。
- 若找到多于
个极值点,选择极值点的优先顺位为:
- 优先选择不在边界的极值点。
- 其次选在边界的极值点中,
较大的,直到凑足
个极值点为止。
- 当边界的极值点的
一样大时,优先选择转换频带两旁的点。
- 判断误差是否收敛
- 计算误差的最大值,令其为
。
- 若
为现在的误差最大值,
为前一轮计算的误差最大值,则利用下列规则判断算法的下一步:
- 若
,设置
,回到步骤2。
- 若
,进行步骤6。
- 计算所设计滤波器的脉冲响应
- 由先前在步骤2中的关系式,我们可得
![{\displaystyle h[k]=s[0],h[k+n]=s[n]/2,h[k-n]=s[n]/2,\;for\;n=1,2,3,\ldots ,k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/662d186c76c130e47444bdddade941ae41d45f6f)
- 此
即为我们所求的脉冲响应。
权重函数
滤波器响应的影响
[编辑]
当权重函数在带内设计为1,在带外设计为小于1,会让滤波器较重视通过带通频段的信号。
当权重函数在带外设计为1,在内设计为小于1,会让滤波器具有较好的滤除噪声的能力。
用此方法设计出来的滤波器,一定会满足以下两个情况:
- 有k+2个以上的极值点(极大点与极小点)。
- 在极点上,
![{\displaystyle W(F_{m})|R(F_{m})-H_{d}(F_{m})|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7b82727fbb77c196a8929fd4af02ed8e0f36c1a)
过渡频段(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.