帕克斯-麥克萊倫演算法

**帕克斯 - 麥克萊倫演算法**（英語：Parks–McClellan 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 點有限脈衝響應濾波器

$$
h[n]=0,\;for\;n<0\;and\;n\geq 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\leq F\leq 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\leq 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),\;for0\leq F\leq 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 Fn)-H_{d}(F)\right\}W(F)$
4. 尋找極值點

　
: 從 $err(F)$ 中，找 k+2 個區域極大或極小值，將區域極大或極小值出現的頻率標示為 $P_{0},P_{1},\ldots ,P_{k},P_{k+1}$

　
: 區域極大或極小值的判斷規則：

  * 不是在邊界處的區域高峰 (peaks) 或低谷 (dips)。在此，邊界區域即為 $F=0,F=0.5$ 以及頻率轉換帶的兩邊。
  * 對於在邊界區域的頻率點，可用下列的標準判斷是否為區域極大或極小： $Sign(eff(F_{d}))$ 及 $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\leq E_{1}-E_{0}\leq \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.