帕克斯-麥克萊倫演算法

帕克斯-麥克萊倫演算法（,又稱為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個步驟：
設定極值點起始值
在範圍的範圍內，任意選擇點頻率作為極值點(extreme frequency)的起始值。
將此時的最大誤差設為，但所選擇的點起始值不能落在轉換頻帶(transition band)，也不能將所有的起始值設在止帶(stop band)上。
極端頻率為最後完成設計的濾波器頻率響應中，會出現最大誤差的頻率。一開始所給定的起始值是隨機的，會在此演算法之後的步驟中逐漸收斂。
此時，令在各點極端頻率的誤差為。  其中e為設計濾波器響應式與理想濾波器響應式在相對應頻率點的誤差值。
計算目前的頻率響應 
為了方便演算法運算之後的進行，我們可稍微整理誤差的表示方式。若令
。此是設計的濾波器響應的平移。為的正中央項 ( 舉例： )。
 。因為為偶函數，所以也是偶函數，則再設計，計算的一半範圍就好。
如此一來，可將在第1步驟中所得到的誤差式表示為：

其中，
  (由於使用,計算項次從0到k)
經過整理之後可得

上述的誤差關係式，可表示為矩陣形式

因此，我們可由計算
計算誤差函數 
計算誤差函數

尋找極值點
從中，找k+2個區域極大或極小值，將區域極大或極小值出現的頻率標示為
區域極大或極小值的判斷規則：
不是在邊界處的區域高峰(peaks)或低谷(dips)。在此，邊界區域即為以及頻率轉換帶的兩邊。
對於在邊界區域的頻率點，可用下列的標準判斷是否為區域極大或極小：及為同相時，右邊界是極值點；反相時，左邊界是極值點；其他情況非極值點。
若找到多於個極值點，選擇極值點的優先順位為：
優先選擇不在邊界的極值點。
其次選在邊界的極值點中，較大的，直到湊足個極值點為止。
當邊界的極值點的一樣大時，優先選擇轉換頻帶兩旁的點。
判斷誤差是否收斂 
計算誤差的最大值，令其為。
若為現在的誤差最大值，為前一輪計算的誤差最大值，則利用下列規則判斷演算法的下一步：
若，設定，回到步驟2。
若，進行步驟6。
計算所設計濾波器的脈衝響應
由先前在步驟2中的關係式，我們可得

此即為我們所求的脈衝響應。

 權重函數濾波器響應的影響 
當權重函數在帶內設計為1，在帶外設計為小於1，會讓濾波器較重視通過帶通頻段的訊號。

當權重函數在帶外設計為1，在內設計為小於1，會讓濾波器具有較好的濾除雜訊的能力。

 特徵 
用此方法設計出來的濾波器，一定會滿足以下兩個情況：

 有k+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.

Category:滤波器理论
Category:数字信号处理