帕克斯-麥克萊倫演算法

帕克斯-麥克萊倫演算法(英語: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.