帕克斯-麥克萊倫演算法

维基百科,自由的百科全书
跳转至: 导航搜索

帕克斯-麥克萊倫演算法(Parks–McClellan algorithm),為一個疊代演算法(iterative algorithm)用以設計最佳化有限脈衝響應濾波器(finite impulse response filter),由James McClellan and Thomas Parks於1972年的著作中提出。

此演算法的主要精神,在於利用疊代的方式最小化濾波器在通帶(pass band)和止帶(stop band)的最大誤差,因此有時也稱為最小化最大誤差演算法(Mini-max filter design)。由於帕克斯-麥克萊倫演算法也屬於Remez-exchange algorithm為了設計有限脈衝響應濾波器而產生的一種變形,因此也有人以Remez-exchange algorithm代稱。

有限脈衝響應濾波器設計[编辑]

有限脈衝響應濾波器(finite impulse response filter)利用有限的點數來表示濾波器的脈衝響應,對於N點有限脈衝響應濾波器

h[n] = 0,\; for\; n<0\; and\; n\ge N, \;N\, is\, a\, finite\; number

有限脈衝響應濾波器的優點在於脈衝響應是有限的,使得設計上較為簡單,

然而如何在有限的點數下,設計出效果最近似於理想目標的濾波器,則是帕克斯-麥克萊倫演算法所欲解決的問題。

對於濾波器設計,帕克斯-麥克萊倫演算法的精神在於最小化最大誤差。在忽略通帶與止帶之間轉換帶(transition band)的情況下,最小化通帶與止帶的最大誤差:

 \underset{f}{\operatorname{Max}} \left| H(f) - H_d(f) \right| 

其中H(f) = \sum_{n=-\infty}^{\infty } h[n] e^{-j2\pi Fn} 為設計濾波器的頻率響應,F為正規化頻率(normalized frequency),H_d(f)則為理想目標濾波器的頻率響應

濾波器設計時,可利用weighting function將較重要的頻帶比重放大。如此一來,在利用帕克斯-麥克萊倫演算法設計濾波器時,則會較重視比重較大頻帶的誤差

若在加入weighting function情況下,可將帕克斯-麥克萊倫演算法一般化。此時的最大誤差則可表示為

 \underset{f}{\operatorname{Max}} \left| W(f) \left[H(f) - H_d(f) \right] \right| 

帕克斯-麥克萊倫演算法[编辑]

下面的文章將說明如何以該演算法設計最佳化濾波器,假設

  • 濾波器長度為N,且N為奇數可表示成N = 2k+1
  • 目標濾波器的頻率響應H_d(F)為偶函數
  • W(F)用以表示所指定的weighting function

此演算法共分為6個步驟:

1.設定極值點起始值

在範圍0\le F\le 0.5的範圍內,任意選擇k+2點頻率F_0 ,\; F_1,\; F_2,\; \ldots,\; F_{k+1}作為極值點(extreme frequency)的起始值。
將此時的最大誤差E_1設為\infty ,所選擇的k+2點起始值必續滿足下列條件:
  • 不能落在轉換頻帶(transition band)
  • 不能將所有的起始直設在止帶(stop band)上
極端頻率為最後完成設計的濾波器頻率響應中,會出現最大誤差的頻率。一開始所給定的起始值是隨機的,會在此演算法之後的步驟中逐漸收斂。
此時,令在各點極端頻率的誤差為
 \left[ H(F_m)-H_d(F_m) \right] W(F_m) = (-1)^{m+1} e,\; where\;m=0,1,2 \ldots , k+1

2.計算目前的頻率響應

為了方便演算法運算之後的進行,我們可稍微整理誤差的表示方式。若令
r[n]=h[n+k],\; k=(N-1)/2
s[0]=r[0],\ \ s[n]=2r[n],\; for\; 0 < n \le k
如此一來,可將在第1步驟中所得到的誤差式表示為:
	\left[ R(F_m)-H_d(F_m) \right] W(F_m) = (-1)^{m+1} e,\; where\;m=0,1,2 \ldots , k+1
其中,
 R(F) = \sum_{n=0}^k s[n] \cos (2 \pi nF) = e^{j2 \pi Fk} H(F) 
經過整理之後可得
 \sum_{n=0}^k s[n] \cos (2 \pi F_m n) + (-1)^m W^{-1} (F_m) e = H_d(F_m) 
上述的誤差關係式,可表示為矩陣形式 Ax = H


\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}

因此,我們可由 x = A^{-1} H 計算 s[0], s[1], \ldots, s[k]

3.計算誤差函數

計算誤差函數err(F), \; for 0 \le F \le 0.5 \; , F \notin transition \; band
 err(F)= \left[ R(F)-H_d(F) \right] W(F_m) = \left\{ \sum_{n=0}^k s[n] \cos (2 \pi F n) - H_d(F) \right\} W(F) 

4.尋找極值點

err(F)中,找k+2個區域極大或極小值,將區域極大或極小值出現的頻率標示為 P_0, P_1, \ldots, P_k, P_{k+1}
區域極大或極小值的判斷規則:
(a)不是在邊界處的區域高峰(peaks)或低谷(dips)。在此,邊界區域即為F=0, F=0.5 以及頻率轉換帶的兩邊。
(b)對於在邊界區域的頻率點,可用下列的標準判斷是否為區域極大或極小:
Sign(eff(F_d))\; and \; Sign(err'(F_d)) 同相 反相
左邊界 非極值點 極值點
右邊界 極值點 非極值點
若找到多於k+2個極值點,選擇極值點的優先順位為:
(1)優先選擇不在邊界的極值點。
(2)其次選在邊界的極值點中, \left| err(F) \right| 較大的,直到湊足k+2個極值點為止。
(3)當邊界的極值點的\left| err(F) \right| 一樣大時,優先選擇轉換頻帶兩旁的點。

5.判斷誤差是否收斂

計算誤差的最大值,令其為E_0 = Max(\left| err(F) \right|)
E_0為現在的誤差最大值,E_1為前一輪計算的誤差最大值,則利用下列規則判斷演算法的下一步:
(1)若E_1 - E_0 > \Delta, \; or \; E_1 - E_0 < 0
設定 F_n = P_n \; and \; E_1 = E_0 ,回到步驟2。
(2)若 0 \le E_1 - E_0 \le \Delta ,進行步驟6。

6.計算所設計濾波器的脈衝響應\;h[n]

由先前在步驟2中的關係式,我們可得
h[k] = s[0], h[k+n] = s[n]/2, h[k-n]=s[n]/2, \; for \; n=1,2,3, \ldots, k 

參考文獻[编辑]

  • Jian-Jiun Ding (2013), Advanced Digital Signal Processing [viewed 27/06/2013]
  • T. W. Parks and J. H. McClellan, “Chebychev approximation for nonrecursive digital filter-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.