帕克斯-麥克萊倫演算法 （英語：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點有限脈衝響應濾波器
h
[
n
]
=
0
,
f
o
r
n
<
0
a
n
d
n
≥
N
,
N
i
s
a
f
i
n
i
t
e
n
u
m
b
e
r
{\displaystyle h[n]=0,\;for\;n<0\;and\;n\geq N,\;N\,is\,a\,finite\;number}
有限脈衝響應濾波器的優點在於脈衝響應是有限的，使得設計上較為簡單。然而如何在有限的點數下，設計出效果最近似於理想目標的濾波器，則是帕克斯-麥克萊倫演算法所欲解決的問題。
對於濾波器設計，帕克斯-麥克萊倫演算法的精神在於最小化最大誤差。在忽略通帶與止帶之間轉換帶(transition band)的情況下，最小化通帶與止帶的最大誤差：
Max
f
|
H
(
f
)
−
H
d
(
f
)
|
{\displaystyle {\underset {f}{\operatorname {Max} }}\left|H(f)-H_{d}(f)\right|}
其中
H
(
f
)
=
∑
n
=
−
∞
∞
h
[
n
]
e
−
j
2
π
f
n
{\displaystyle H(f)=\sum _{n=-\infty }^{\infty }h[n]e^{-j2\pi fn}}
H
d
(
f
)
{\displaystyle H_{d}(f)}
在數位濾波器設計中，常常會將信號的頻率做取樣，使得頻譜具有週期性。設計者即可針對一個週期去做計算就好,減少計算量。所以前兩行的最大誤差可寫成：
Max
F
|
H
(
F
)
−
H
d
(
F
)
|
{\displaystyle {\underset {F}{\operatorname {Max} }}\left|H(F)-H_{d}(F)\right|}
其中
F
{\displaystyle F}
F
=
f
f
s
{\displaystyle F={\frac {f}{f_{s}}}}
濾波器設計時，可利用weighting function將較重要的頻帶比重放大。如此一來，在利用帕克斯-麥克萊倫演算法設計濾波器時，則會較重視比重較大頻帶的誤差。
若在加入weighting function情況下，可將帕克斯-麥克萊倫演算法一般化。此時的最大誤差則可表示為：
Max
f
|
W
(
f
)
[
H
(
f
)
−
H
d
(
f
)
]
|
{\displaystyle {\underset {f}{\operatorname {Max} }}\left|W(f)\left[H(f)-H_{d}(f)\right]\right|}
另外在數學上，此種將向量取絕對值並找出某個最大的元素的算法，稱為取
L
∞
{\displaystyle L_{\infty }}
H
(
F
)
−
H
d
(
F
)
{\displaystyle H(F)-H_{d}(F)}
帕克斯-麥克萊倫演算法
编辑
下面的文章將說明如何以該演算法設計最佳化濾波器，假設
濾波器長度為N，且N為奇數可表示成
N
=
2
k
+
1
{\displaystyle N=2k+1}
目標濾波器的頻率響應
H
d
(
F
)
{\displaystyle H_{d}(F)}
偶函數
W
(
F
)
{\displaystyle W(F)}
此演算法共分為6個步驟：
設定極值點起始值
在範圍
0
≤
F
≤
0.5
{\displaystyle 0\leq F\leq 0.5}
k
+
2
{\displaystyle k+2}
F
0
,
F
1
,
F
2
,
…
,
F
k
+
1
{\displaystyle F_{0},\;F_{1},\;F_{2},\;\ldots ,\;F_{k+1}}
將此時的最大誤差
E
1
{\displaystyle E_{1}}
∞
{\displaystyle \infty }
k
+
2
{\displaystyle k+2}
極端頻率為最後完成設計的濾波器頻率響應中，會出現最大誤差的頻率。一開始所給定的起始值是隨機的，會在此演算法之後的步驟中逐漸收斂。
此時，令在各點極端頻率的誤差為
[
H
(
F
m
)
−
H
d
(
F
m
)
]
W
(
F
m
)
=
(
−
1
)
m
+
1
e
,
w
h
e
r
e
m
=
0
,
1
,
2
…
,
k
+
1
{\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}
計算目前的頻率響應
為了方便演算法運算之後的進行，我們可稍微整理誤差的表示方式。若令
r
[
n
]
=
h
[
n
+
k
]
,
k
=
(
N
−
1
)
/
2
{\displaystyle r[n]=h[n+k],\;k=(N-1)/2}
r
[
n
]
{\displaystyle r[n]}
h
[
n
]
{\displaystyle h[n]}
r
[
0
]
{\displaystyle r[0]}
h
[
n
]
{\displaystyle h[n]}
r
[
0
]
=
h
[
k
]
,
r
[
1
]
=
h
[
k
+
1
]
{\displaystyle r[0]=h[k],r[1]=h[k+1]}
s
[
0
]
=
r
[
0
]
,
s
[
n
]
=
2
r
[
n
]
,
f
o
r
0
<
n
≤
k
{\displaystyle s[0]=r[0],\ \ s[n]=2r[n],\;for\;0<n\leq k}
H
d
(
F
)
{\displaystyle H_{d}(F)}
偶函數 ，所以
r
[
n
]
{\displaystyle r[n]}
偶函數 ，則再設計
s
[
n
]
{\displaystyle s[n]}
r
[
n
]
{\displaystyle 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
…
,
k
+
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}
其中，
R
(
F
)
=
∑
n
=
0
k
s
[
n
]
cos
(
2
π
n
F
)
=
e
j
2
π
F
k
H
(
F
)
{\displaystyle R(F)=\sum _{n=0}^{k}s[n]\cos(2\pi nF)=e^{j2\pi Fk}H(F)}
s
[
n
]
{\displaystyle s[n]}
經過整理之後可得
∑
n
=
0
k
s
[
n
]
cos
(
2
π
F
m
n
)
+
(
−
1
)
m
W
−
1
(
F
m
)
e
=
H
d
(
F
m
)
{\displaystyle \sum _{n=0}^{k}s[n]\cos(2\pi F_{m}n)+(-1)^{m}W^{-1}(F_{m})e=H_{d}(F_{m})}
上述的誤差關係式，可表示為矩陣形式
A
x
=
H
{\displaystyle Ax=H}
[
1
cos
(
2
π
F
0
)
cos
(
4
π
F
0
)
⋯
cos
(
2
π
k
F
0
)
1
/
W
(
F
0
)
1
cos
(
2
π
F
1
)
cos
(
4
π
F
1
)
⋯
cos
(
2
π
k
F
1
)
−
1
/
W
(
F
1
)
⋮
⋮
⋮
⋱
⋮
⋮
1
cos
(
2
π
F
k
)
cos
(
4
π
F
k
)
⋯
cos
(
2
π
k
F
k
)
(
−
1
)
k
/
W
(
F
k
)
1
cos
(
2
π
F
k
+
1
)
cos
(
4
π
F
k
+
1
)
⋯
cos
(
2
π
k
F
k
+
1
)
(
−
1
)
k
+
1
/
W
(
F
k
+
1
)
]
[
s
[
0
]
s
[
1
]
⋮
s
[
k
]
e
]
=
[
H
d
[
F
0
]
H
d
[
F
1
]
⋮
H
d
[
F
k
]
H
d
[
F
k
+
1
]
]
{\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}}}
因此，我們可由
x
=
A
−
1
H
{\displaystyle x=A^{-1}H}
s
[
0
]
,
s
[
1
]
,
…
,
s
[
k
]
{\displaystyle s[0],s[1],\ldots ,s[k]}
計算誤差函數
計算誤差函數
e
r
r
(
F
)
,
f
o
r
0
≤
F
≤
0.5
,
F
∉
t
r
a
n
s
i
t
i
o
n
b
a
n
d
{\displaystyle err(F),\;for0\leq F\leq 0.5\;,F\notin transition\;band}
e
r
r
(
F
)
=
[
R
(
F
)
−
H
d
(
F
)
]
W
(
F
)
=
{
∑
n
=
0
k
s
[
n
]
cos
(
2
π
F
n
)
−
H
d
(
F
)
}
W
(
F
)
{\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)}
尋找極值點
從
e
r
r
(
F
)
{\displaystyle err(F)}
P
0
,
P
1
,
…
,
P
k
,
P
k
+
1
{\displaystyle P_{0},P_{1},\ldots ,P_{k},P_{k+1}}
區域極大或極小值的判斷規則：
不是在邊界處的區域高峰(peaks)或低谷(dips)。在此，邊界區域即為
F
=
0
,
F
=
0.5
{\displaystyle F=0,F=0.5}
對於在邊界區域的頻率點，可用下列的標準判斷是否為區域極大或極小：
S
i
g
n
(
e
f
f
(
F
d
)
)
{\displaystyle Sign(eff(F_{d}))}
S
i
g
n
(
e
r
r
′
(
F
d
)
)
{\displaystyle Sign(err'(F_{d}))}
若找到多於
k
+
2
{\displaystyle k+2}
優先選擇不在邊界的極值點。
其次選在邊界的極值點中，
|
e
r
r
(
F
)
|
{\displaystyle \left|err(F)\right|}
k
+
2
{\displaystyle k+2}
當邊界的極值點的
|
e
r
r
(
F
)
|
{\displaystyle \left|err(F)\right|}
判斷誤差是否收斂
計算誤差的最大值，令其為
E
0
=
M
a
x
(
|
e
r
r
(
F
)
|
)
{\displaystyle E_{0}=Max(\left|err(F)\right|)}
若
E
0
{\displaystyle E_{0}}
E
1
{\displaystyle E_{1}}
若
E
1
−
E
0
>
Δ
,
o
r
E
1
−
E
0
<
0
{\displaystyle E_{1}-E_{0}>\Delta ,\;or\;E_{1}-E_{0}<0}
F
n
=
P
n
a
n
d
E
1
=
E
0
{\displaystyle F_{n}=P_{n}\;and\;E_{1}=E_{0}}
若
0
≤
E
1
−
E
0
≤
Δ
{\displaystyle 0\leq E_{1}-E_{0}\leq \Delta }
計算所設計濾波器的脈衝響應
h
[
n
]
{\displaystyle \;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
,
…
,
k
{\displaystyle h[k]=s[0],h[k+n]=s[n]/2,h[k-n]=s[n]/2,\;for\;n=1,2,3,\ldots ,k}
此
h
[
k
]
{\displaystyle h[k]}
權重函數
W
(
F
)
{\displaystyle W(F)}
编辑
當權重函數在帶內設計為1，在帶外設計為小於1，會讓濾波器較重視通過帶通頻段的訊號。
當權重函數在帶外設計為1，在內設計為小於1，會讓濾波器具有較好的濾除雜訊的能力。
參考文獻
编辑
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. 
![{\displaystyle h[n]=0,\;for\;n<0\;and\;n\geq N,\;N\,is\,a\,finite\;number}](https://wikimedia.org/api/rest_v1/media/math/render/svg/064bc48ebdb392c5ec8b1bde9a3fc2ae26897e29)
![{\displaystyle H(f)=\sum _{n=-\infty }^{\infty }h[n]e^{-j2\pi fn}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/129408fdc078e5b0906466f659a56d299ca82d9d)
![{\displaystyle {\underset {f}{\operatorname {Max} }}\left|W(f)\left[H(f)-H_{d}(f)\right]\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c6390c15c64fe4f605cb35b9fab68c71e4db4f6)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f0a6c1f36b927f51e29bfc7022d4f6a5b2f086b)
![{\displaystyle r[n]=h[n+k],\;k=(N-1)/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b18e646ba85b2c4e2727ca90ba6b3379f5f83309)
![{\displaystyle r[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c09959f03d3759ff5f0fdd49b786757032ef1c02)
![{\displaystyle h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89981bbbb05ffd469eeadb828c18359965985e46)
![{\displaystyle r[0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/faf998129cfb3fda8d8a363592027dc8a07c7838)
![{\displaystyle r[0]=h[k],r[1]=h[k+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b226aa83570c1de14847cffb12b3ee6a302668b3)
![{\displaystyle s[0]=r[0],\ \ s[n]=2r[n],\;for\;0<n\leq k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21cabec5c6e04474593a1d8ced74bb90b79f6bbb)
![{\displaystyle s[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffe878c033cc70d1aa3ffbd156394791aa8dffde)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99b9d2737dc24a103b3ce783332de8a6a2d57fb3)
![{\displaystyle R(F)=\sum _{n=0}^{k}s[n]\cos(2\pi nF)=e^{j2\pi Fk}H(F)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/787f129e4c4d86700b418af6da278b5d3083ac51)
![{\displaystyle \sum _{n=0}^{k}s[n]\cos(2\pi F_{m}n)+(-1)^{m}W^{-1}(F_{m})e=H_{d}(F_{m})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/590987e0ee5bdd3a2410794e64ad695f90d7f052)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d769856cafac7f7757fb73cd71db0faf53630c2e)
![{\displaystyle s[0],s[1],\ldots ,s[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d14e9ef64f809feba5e977062351a03f080a7fb6)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8bed4342f38a5e4408c6821fa957c474ede46d5)
![{\displaystyle \;h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f1bc67d638640e2ee66232c0de3fc293bfb6212)
![{\displaystyle h[k]=s[0],h[k+n]=s[n]/2,h[k-n]=s[n]/2,\;for\;n=1,2,3,\ldots ,k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/662d186c76c130e47444bdddade941ae41d45f6f)
![{\displaystyle h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e944606b94261ca96a82ff41b4b8aade7ff14acc)
