格策尔算法 或格兹尔算法 ( 英语: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 外部链接 [ 编辑 ] 
