格策爾演算法 或格茲爾演算法 ( 英語:Goertzel algorithm )是數位訊號處理 的一種運算技巧，此運算技巧提供一個有效率的方式來估計部分區域的離散傅立葉轉換 ，廣泛的運用在數字電話中的的雙音多頻信號 (每個撥號的數字鍵由兩個頻率的音所組成，一個低頻，一個高頻)，此演算法在1958年被傑拉德 · 格策爾 [1]
格策爾演算法與離散傅立葉轉換的相似處在於他們都可以分析某個特定頻段的離散訊號[2] [3] [4]
格策爾演算法逆向操作生成出弦波，而這個過程只需花費一個乘法和一個加法運算[5]
格策爾演算法把離散傅立葉轉換 看成是一組濾波器，將輸入的訊號與濾波器 中的脈衝響應 做卷積運算，求得濾波器 的輸出，即得到頻率域其中一點的頻率
X
(
k
)
{\displaystyle X(k)}
旋轉因子
ω
N
k
{\displaystyle {\omega }_{N}^{k}}
離散傅立葉轉換 轉換為線性的濾波運算。
因為旋轉因子
ω
N
−
k
N
=
e
−
j
(
2
π
/
N
)
(
−
k
N
)
=
1
{\displaystyle {\omega }_{N}^{-kN}=e^{-j(2{\pi /N})(-kN)}=1}
(1)
可得轉換後第k點的頻率為
X
(
k
)
=
ω
N
−
k
N
∑
m
=
0
N
−
1
x
(
m
)
ω
N
k
m
=
∑
m
=
0
N
−
1
x
(
m
)
ω
N
−
k
(
N
−
m
)
,
k
=
0
,
1
,
2
,
.
.
.
,
N
−
1
{\displaystyle X(k)={\omega }_{N}^{-kN}\sum _{m=0}^{N-1}x(m){\omega }_{N}^{km}=\sum _{m=0}^{N-1}x(m){\omega }_{N}^{-k(N-m)}\qquad \quad ,k=0,1,2,...,N-1}
(2)
定義
y
k
(
n
)
{\displaystyle y_{k}(n)}
y
k
(
n
)
=
∑
m
=
0
N
−
1
x
(
m
)
ω
N
−
k
(
n
−
m
)
{\displaystyle y_{k}(n)=\sum _{m=0}^{N-1}x(m){\omega }_{N}^{-k(n-m)}}
(3.A)
可將
y
k
(
n
)
{\displaystyle y_{k}(n)}
卷積 運算得出的結果
y
k
(
n
)
=
x
(
n
)
⊗
h
k
(
n
)
{\displaystyle y_{k}(n)=x(n)\otimes h_{k}(n)}
(3.B)
其中
x
(
n
)
{\displaystyle x(n)}
h
k
(
n
)
{\displaystyle h_{k}(n)}
IIR 濾波器的脈衝頻率響應
h
k
(
n
)
=
ω
N
−
k
n
u
(
n
)
{\displaystyle h_{k}(n)={\omega }_{N}^{-kn}\ u(n)}
(4)
對比(2)和(3)式，可推知(3.A)進行卷積運算，當n=N時，濾波器的輸出
y
k
(
N
)
{\displaystyle y_{k}(N)}
X
(
k
)
{\displaystyle X(k)}
X
(
k
)
=
y
k
(
n
)
⌊
n
=
N
{\displaystyle X(k)=y_{k}(n)\lfloor _{n=N}}
(5)
對(4)進行Z轉換，可得一階IIR 轉移函數
H
k
(
z
)
=
1
1
−
ω
−
k
z
−
1
{\displaystyle H_{k}(z)={\frac {1}{1-{{\omega }^{-k}\ z^{-1}}}}}
(6)
圖一為此系統的流程圖 ，其對應的差分方程式 為:
y
k
(
n
)
=
ω
N
−
k
y
k
(
n
−
1
)
+
x
(
n
)
,
y
(
−
1
)
=
0
{\displaystyle y_{k}(n)={\omega }_{N}^{-k}\ y_{k}(n-1)+x(n),\qquad \ y(-1)=0}
(7)
圖一、格策爾一階濾波器系統示意圖 依照此差分方程進行疊代運算 ，疊代到
n
=
N
{\displaystyle n=N}
X
(
k
)
{\displaystyle X(k)}
旋轉因子
ω
N
k
{\displaystyle {\omega }_{N}^{k}}
離散傅立葉轉換 時則需要
4
N
2
{\displaystyle 4N^{2}}
N
(
4
N
−
2
)
{\displaystyle N(4N-2)}
[6]
4
N
2
{\displaystyle 4N^{2}}
將式(6)上下同乘以
1
−
ω
N
k
z
−
1
{\displaystyle 1-{\omega }_{N}^{k}\ z^{-1}}
H
k
(
z
)
=
1
−
ω
N
k
z
−
1
(
1
−
ω
N
−
k
z
−
1
)
(
1
−
ω
N
k
z
−
1
)
=
1
−
ω
N
k
z
−
1
1
−
2
cos
(
(
2
π
/
N
)
k
)
z
−
1
+
z
−
2
)
{\displaystyle {\begin{alignedat}{2}H_{k}(z)&={\frac {1-{{\omega }_{N}^{k}\ z^{-1}}}{(1-{{\omega }_{N}^{-k}\ z^{-1}})(1-{{\omega }_{N}^{k}\ z^{-1})}}}\\&={\frac {1-{{\omega }_{N}^{k}\ z^{-1}}}{1-2\ \cos((2{\pi }/N)k)z^{-1}+z^{-2})}}\\\end{alignedat}}}
(8)
圖二、格策爾二階濾波器系統圖 此轉移函數所對應的系統流程圖如圖二所示，複數分析(8)式，可得知此二階濾波器有一對共軛的極點與一個零點。圖二中在計算
x
(
n
)
{\displaystyle x(n)}
X
(
k
)
{\displaystyle X(k)}
共軛極點疊代計算 依序將輸入訊號
x
(
0
)
,
x
(
1
)
,
x
(
2
)
,
.
.
.
,
x
(
n
−
1
)
{\displaystyle x(0),x(1),x(2),...,x(n-1)}
2
N
{\displaystyle 2N}
4
N
{\displaystyle 4N}
零點疊代計算 輸入訊號
x
(
n
)
{\displaystyle x(n)}
n
=
0
,
1
,
2
,
3
,
.
.
.
,
N
−
1
{\displaystyle n=0,1,2,3,...,N-1}
x
(
N
)
=
0
{\displaystyle x(N)=0}
y
k
(
N
)
{\displaystyle y_{k}(N)}
x
(
n
)
{\displaystyle x(n)}
X
(
k
)
{\displaystyle X(k)}
綜合以上步驟，總共的計算量為
2
N
+
4
{\displaystyle 2N+4}
4
N
+
4
{\displaystyle 4N+4}
ω
N
k
{\displaystyle {\omega }_{N}^{k}}
cos
(
(
2
π
/
N
)
k
)
{\displaystyle \cos((2{\pi }/N)k)}
[7]
相關條目
编辑
參考資料
编辑
^ Goertzel, G. (January 1958), "An Algorithm for the Evaluation of Finite Trigonometric Series" , American Mathematical Monthly , 65 (1): 34–35, doi :10.2307/2310304
^ Mock, P. (March 21, 1985), "Add DTMF Generation and Decoding to DSP-μP Designs （页面存档备份 ，存于互联网档案馆 ）" (PDF), EDN, ISSN 0012-7515 （页面存档备份 ，存于互联网档案馆 ）; also found in DSP Applications with the TMS320 Family, Vol. 1, Texas Instruments, 1989.
^ Chen, Chiouguey J. (June 1996), Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80 DSP
^ Schmer, Gunter (May 2000), DTMF Tone Generation and Detection: An Implementation Using the TMS320C54x 页面存档备份 ，存于互联网档案馆 ） (PDF), Application Report, Texas Instruments, SPRA096a
^ http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf.
^ http://www.docin.com/p-577391532.html ^ 格策爾介紹網站(英文) . [2017-06-22 ] . （原始内容 存档于2017-06-22）.
延伸閱讀
编辑
Proakis, J. G.; Manolakis, D. G. (1996), Digital Signal Processing: Principles, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, pp. 480–481 外部連結
编辑
