帕克斯-麥克萊倫演算法

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

${\displaystyle h[n]=0,\;for\;n<0\;and\;n\geq N,\;N\,is\,a\,finite\;number}$

有限脈衝響應濾波器的優點在於脈衝響應是有限的，使得設計上較為簡單。然而如何在有限的點數下，設計出效果最近似於理想目標的濾波器，則是帕克斯-麥克萊倫演算法所欲解決的問題。

對於濾波器設計，帕克斯-麥克萊倫演算法的精神在於最小化最大誤差。在忽略通帶與止帶之間轉換帶(transition band)的情況下，最小化通帶與止帶的最大誤差：${\displaystyle {\underset {f}{\operatorname {Max} }}\left|H(f)-H_{d}(f)\right|}$

其中${\displaystyle H(f)=\sum _{n=-\infty }^{\infty }h[n]e^{-j2\pi fn}}$為設計濾波器的頻率響應，${\displaystyle H_{d}(f)}$則為理想目標濾波器的頻率響應。

在數位濾波器設計中，常常會將信號的頻率做取樣，使得頻譜具有週期性。設計者即可針對一個週期去做計算就好,減少計算量。所以前兩行的最大誤差可寫成：

${\displaystyle {\underset {F}{\operatorname {Max} }}\left|H(F)-H_{d}(F)\right|}$

其中${\displaystyle F}$為正規化頻率(normalized frequency)：${\displaystyle F={\frac {f}{f_{s}}}}$

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

若在加入weighting function情況下，可將帕克斯-麥克萊倫演算法一般化。此時的最大誤差則可表示為：${\displaystyle {\underset {f}{\operatorname {Max} }}\left|W(f)\left[H(f)-H_{d}(f)\right]\right|}$

另外在數學上，此種將向量取絕對值並找出某個最大的元素的算法，稱為取${\displaystyle L_{\infty }}$範數。若能將${\displaystyle H(F)-H_{d}(F)}$離散化寫成矩陣的形式，就可以用此方法快速找出最大誤差。

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

• 濾波器長度為N，且N為奇數可表示成${\displaystyle N=2k+1}$
• 目標濾波器的頻率響應${\displaystyle H_{d}(F)}$為偶函數
• ${\displaystyle W(F)}$用以表示所指定的權重函數(weighting function)。功用是將特定頻段(通常是通帶內)的誤差調得更小，重視某頻段的最佳化。

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

1. 設定極值點起始值

   在範圍${\displaystyle 0\leq F\leq 0.5}$的範圍內，任意選擇${\displaystyle k+2}$點頻率${\displaystyle F_{0},\;F_{1},\;F_{2},\;\ldots ,\;F_{k+1}}$作為極值點(extreme frequency)的起始值。

   將此時的最大誤差${\displaystyle E_{1}}$設為${\displaystyle \infty }$，但所選擇的${\displaystyle k+2}$點起始值不能落在轉換頻帶(transition band)，也不能將所有的起始值設在止帶(stop band)上。

   極端頻率為最後完成設計的濾波器頻率響應中，會出現最大誤差的頻率。一開始所給定的起始值是隨機的，會在此演算法之後的步驟中逐漸收斂。

   此時，令在各點極端頻率的誤差為${\displaystyle \left[H(F_{m})-H_{d}(F_{m})\right]W(F_{m})=(-1)^{m+1}e,\;where\;m=0,1,2\ldots ,k+1}$。 其中e為設計濾波器響應式與理想濾波器響應式在相對應頻率點的誤差值。

2. 計算目前的頻率響應

   為了方便演算法運算之後的進行，我們可稍微整理誤差的表示方式。若令

   ${\displaystyle r[n]=h[n+k],\;k=(N-1)/2}$。此${\displaystyle r[n]}$是設計的濾波器響應${\displaystyle h[n]}$的平移。${\displaystyle r[0]}$為${\displaystyle h[n]}$的正中央項 ( 舉例：${\displaystyle r[0]=h[k],r[1]=h[k+1]}$ )。

   ${\displaystyle s[0]=r[0],\ \ s[n]=2r[n],\;for\;0<n\leq k}$ 。因為${\displaystyle H_{d}(F)}$為偶函數，所以${\displaystyle r[n]}$也是偶函數，則再設計${\displaystyle s[n]}$，計算${\displaystyle r[n]}$的一半範圍就好。

   如此一來，可將在第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}$

   其中，

   ${\displaystyle R(F)=\sum _{n=0}^{k}s[n]\cos(2\pi nF)=e^{j2\pi Fk}H(F)}$ (由於使用${\displaystyle s[n]}$,計算項次從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})}$

   上述的誤差關係式，可表示為矩陣形式${\displaystyle Ax=H}$

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

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

3. 計算誤差函數

   計算誤差函數${\displaystyle err(F),\;for0\leq F\leq 0.5\;,F\notin transition\;band}$

   ${\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)}$

4. 尋找極值點

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

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

   • 不是在邊界處的區域高峰(peaks)或低谷(dips)。在此，邊界區域即為${\displaystyle F=0,F=0.5}$以及頻率轉換帶的兩邊。
   • 對於在邊界區域的頻率點，可用下列的標準判斷是否為區域極大或極小：${\displaystyle Sign(eff(F_{d}))}$及${\displaystyle Sign(err'(F_{d}))}$為同相時，右邊界是極值點；反相時，左邊界是極值點；其他情況非極值點。

   若找到多於${\displaystyle k+2}$個極值點，選擇極值點的優先順位為：

   1. 優先選擇不在邊界的極值點。
   2. 其次選在邊界的極值點中，${\displaystyle \left|err(F)\right|}$較大的，直到湊足${\displaystyle k+2}$個極值點為止。
   3. 當邊界的極值點的${\displaystyle \left|err(F)\right|}$一樣大時，優先選擇轉換頻帶兩旁的點。
5. 判斷誤差是否收斂

   計算誤差的最大值，令其為${\displaystyle E_{0}=Max(\left|err(F)\right|)}$。

   若${\displaystyle E_{0}}$為現在的誤差最大值，${\displaystyle E_{1}}$為前一輪計算的誤差最大值，則利用下列規則判斷演算法的下一步：

   1. 若${\displaystyle E_{1}-E_{0}>\Delta ,\;or\;E_{1}-E_{0}<0}$，設定${\displaystyle F_{n}=P_{n}\;and\;E_{1}=E_{0}}$，回到步驟2。
   2. 若${\displaystyle 0\leq E_{1}-E_{0}\leq \Delta }$，進行步驟6。
6. 計算所設計濾波器的脈衝響應${\displaystyle \;h[n]}$

   由先前在步驟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}$

   此${\displaystyle h[k]}$即為我們所求的脈衝響應。

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

1. 有k+2個以上的極值點(極大點與極小點)。
2. 在極點上，${\displaystyle W(F_{m})|R(F_{m})-H_{d}(F_{m})|}$

• 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.