帕克斯-麥克萊倫演算法

来自testwiki

imported>我愛當學生2023年6月18日 (日) 06:21的版本（→帕克斯-麥克萊倫演算法：內容擴充修飾語句）

(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

跳转到导航跳转到搜索

Template:NoteTA

帕克斯-麥克萊倫演算法（Template:Lang-en,又稱為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點有限脈衝響應濾波器

$h [n] = 0, f o r n < 0 a n d n \geq N, N i s a f i n i t e n u m b e r$

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

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

其中 $H (f) = \sum_{n = - \infty}^{\infty} h [n] e^{- j 2 π f n}$ 為設計濾波器的頻率響應， $H_{d} (f)$ 則為理想目標濾波器的頻率響應。

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

$\underset{F}{Max} | H (F) - H_{d} (F) |$

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

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

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

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

帕克斯-麥克萊倫演算法

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

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

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

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

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

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

此時，令在各點極端頻率的誤差為 $[H (F_{m}) - H_{d} (F_{m})] W (F_{m}) = (- 1)^{m + 1} e, w h e r e m = 0, 1, 2 \dots, k + 1$ 。其中e為設計濾波器響應式與理想濾波器響應式在相對應頻率點的誤差值。
計算目前的頻率響應
為了方便演算法運算之後的進行，我們可稍微整理誤差的表示方式。若令

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

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

如此一來，可將在第1步驟中所得到的誤差式表示為：

$[R (F_{m}) - H_{d} (F_{m})] W (F_{m}) = (- 1)^{m + 1} e, w h e r e m = 0, 1, 2 \dots, k + 1$

其中，

$R (F) = \sum_{n = 0}^{k} s [n] \cos (2 π n F) = e^{j 2 π F k} H (F)$ (由於使用 $s [n]$ ,計算項次從0到k)

經過整理之後可得

$\sum_{n = 0}^{k} s [n] \cos (2 π F_{m} n) + (- 1)^{m} W^{- 1} (F_{m}) e = H_{d} (F_{m})$

上述的誤差關係式，可表示為矩陣形式 $A x = H$

$[\begin{matrix} 1 & \cos (2 π F_{0}) & \cos (4 π F_{0}) & \dots & \cos (2 π k F_{0}) & 1 / W (F_{0}) \\ 1 & \cos (2 π F_{1}) & \cos (4 π F_{1}) & \dots & \cos (2 π k F_{1}) & - 1 / W (F_{1}) \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & \cos (2 π F_{k}) & \cos (4 π F_{k}) & \dots & \cos (2 π k F_{k}) & (- 1)^{k} / W (F_{k}) \\ 1 & \cos (2 π F_{k + 1}) & \cos (4 π F_{k + 1}) & \dots & \cos (2 π k F_{k + 1}) & (- 1)^{k + 1} / W (F_{k + 1}) \end{matrix}] [\begin{matrix} s [0] \\ s [1] \\ ⋮ \\ s [k] \\ e \end{matrix}] = [\begin{matrix} H_{d} [F_{0}] \\ H_{d} [F_{1}] \\ ⋮ \\ H_{d} [F_{k}] \\ H_{d} [F_{k + 1}] \end{matrix}]$

因此，我們可由 $x = A^{- 1} H$ 計算 $s [0], s [1], \dots, s [k]$
計算誤差函數
計算誤差函數 $e r r (F), f o r 0 \leq F \leq 0.5, F \notin t r a n s i t i o n b a n d$

$e r r (F) = [R (F) - H_{d} (F)] W (F) = {\sum_{n = 0}^{k} s [n] \cos (2 π F n) - H_{d} (F)} W (F)$
尋找極值點
從 $e r r (F)$ 中，找k+2個區域極大或極小值，將區域極大或極小值出現的頻率標示為 $P_{0}, P_{1}, \dots, P_{k}, P_{k + 1}$
區域極大或極小值的判斷規則：
- 不是在邊界處的區域高峰(peaks)或低谷(dips)。在此，邊界區域即為 $F = 0, F = 0.5$ 以及頻率轉換帶的兩邊。
- 對於在邊界區域的頻率點，可用下列的標準判斷是否為區域極大或極小： $S i g n (e f f (F_{d}))$ 及 $S i g n (e r r^{'} (F_{d}))$ 為同相時，右邊界是極值點；反相時，左邊界是極值點；其他情況非極值點。
若找到多於 $k + 2$ 個極值點，選擇極值點的優先順位為：
1. 優先選擇不在邊界的極值點。
2. 其次選在邊界的極值點中， $| e r r (F) |$ 較大的，直到湊足 $k + 2$ 個極值點為止。
3. 當邊界的極值點的 $| e r r (F) |$ 一樣大時，優先選擇轉換頻帶兩旁的點。
判斷誤差是否收斂
計算誤差的最大值，令其為 $E_{0} = M a x (| e r r (F) |)$ 。

若 $E_{0}$ 為現在的誤差最大值， $E_{1}$ 為前一輪計算的誤差最大值，則利用下列規則判斷演算法的下一步：
1. 若 $E_{1} - E_{0} > Δ, o r E_{1} - E_{0} < 0$ ，設定 $F_{n} = P_{n} a n d E_{1} = E_{0}$ ，回到步驟2。
2. 若 $0 \leq E_{1} - E_{0} \leq Δ$ ，進行步驟6。
計算所設計濾波器的脈衝響應 $h [n]$
由先前在步驟2中的關係式，我們可得

$h [k] = s [0], h [k + n] = s [n] / 2, h [k - n] = s [n] / 2, f o r n = 1, 2, 3, \dots, k$

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

權重函數 $W (F)$ 濾波器響應的影響

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

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

特徵

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

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

過渡頻段

過渡頻段(transition band)對設計濾波器的誤差也會有影響。將過渡頻段設計地窄一些， $R (F)$ 和 $H_{d}$ 的誤差就會比較大；將過渡頻段設計地寬一些， $R (F)$ 和 $H_{d}$ 的誤差就會比較小。再設計上可以適當的增加過渡頻段寬度，讓通帶和止帶地響應更趨近於理想值。

假設我們想要帶通段的漣波小於等於 $δ_{1}$ ，帶止段的漣波小於等於 $δ_{2}$ ,過渡頻段小於 $Δ F$ ( $Δ F = \frac{| f_{1} - f_{2} |}{f_{s}}$ $f_{1}$ ， $f_{2}$ 為過渡頻段的上、下界)。則要設計濾波器長度 $N$ 為：

$N \geq \frac{2}{3 Δ F} \log_{10} (\frac{1}{δ_{1} δ_{2}})$

移項可得： $δ_{1} δ_{2} = 1 0^{\frac{- 3 N Δ F}{2} - 1}$

若要設計的頻段中有多的過渡頻段，則 $Δ F$ 取最小長度的過渡頻段帶入計算。

對於一固定長度的數位濾波器，再設計上可以犧牲一些頻段留給過渡頻段，將漣波縮小。但要注意不可將過渡頻段設計過長，因為過渡頻段是無法使用的。

參考文獻

Jian-Jiun Ding (2013), Advanced Digital Signal Processing Template:Wayback [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.

检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=帕克斯-麥克萊倫演算法&oldid=8093”

分类：