《Goertzel 算法及其应用》由会员分享，可在线阅读，更多相关《Goertzel 算法及其应用（5页珍藏版）》请在金锄头文库上搜索。
1、5.9 Goertsel 算法及其应用5.9.1 Goertsel 算法如前所述，N点时域序列x(n)的离散付里叶变换式为X (k)二 N1x(n)W - kn , k = 0,1,2, .N, 1(5.9.1)Nn = 0这N点频域序列是同时被算出的，不可能只计算其中某一个或几个指定点。Goetzel算法是为了解决 这个问题而提出的。这个算法把离散付里叶变换看作一组滤波器，将输入端的时域序列与其中一个滤 波器的冲激响应序列进行卷积运算，求滤波器的输出序列，即得X (k)序列的一点。这种算法利用旋转因子Wk的周期性，使DFT运算化为线性滤波运算。N由于2兀W - kN = e - j (N)(
2、- kN)= 1 N故式(5.9.1)可化为X(k)= W -kN 乞3 (m)W km =乞S(m)W -k(N -m) ， k =0,1,2,N -1(5.9.2)NNNm=0定义序列y (n)为km=0y (n)=乞k(m)W -k (n-m)kNm=0可见y (n)是由两个序列卷积而得到的序列。 k5.9.3A)y (n) = x(n) h (n)kk5.9.3B)其中，x(n)是输入的N点序列，另一个序列被看作滤波器的冲激响应序列k对比式(5.9.2)和式(5.9.3)，N可知：按式(5.9.3A)进行卷积运算，当n - N时，滤波器的输出y (N) kh (n) =W-knu(n)
3、 。(5.9.4)就是 X(k) ：X(k)=y (n)|kn= N5.9.5)对式(5.9.4)进行 Z 变换，可得滤波器的系统函数H (z) =-(5.9.6)k1-W -kz-1这是一个一阶系统。图 5.9.1 示出这个系统的信号流图，相应的差分方程为y (n)二 W-ky (n 1) + x(n)，y(-1)二 0(5.9.7)kN k按照此式进行递推运算，到了 n二N时刻，即可依据式(5.9.5)得到X(k)。按照式(5.9.6)进行运算时，可先算好旋转因子W -k，储存起来。每次递推包含一次复数乘法。按式：5.9.1)直接计算N点离N散付里叶变换，需要4N2次实数乘法和N( 4N-
4、2)次实数加法。按照上述Goertzel算法，所需的实数乘法和实数加法都是4N2次。所以当N不大时，上述算法的效率稍差。下面介绍改进的Goertzel算法,l 算 法 图 5.9.2用二 阶系统实现这种算法所需的实数乘法次数约为直接方法的一半。图 5.9. 1 用一阶 系统实现GoertzeGoertzel 算法把式(5.9.6)的分子和分母都乘上因子(1-咋-1)，就得到第k个滤波器的系统函数为1-W kz-1N(1 - W-kz -1)(1 - Wkz-1)NN5.9.8)1-W kz-1N1 - 2 cos(2 兀 / N )k) z-1 + z-2与此相应的信号流图示于图 5.9.2。
5、由式(5.9.8)可见，滤波器是一个二阶系统，有一对复数共轭极点和 一个复数零点。为了便于运算，在图5.9.2所示的流图中，设立状态变量u和v。按照图5.9.2计算X(k)时，步 骤有二，即：1 实现一对复数极点输入点依次取 x(0),x(l),x(2),., x(n -1),进行递推运算。每次运算中，更新状态变量u和v。作N次迭代所需的计算量是2N次实 数乘法和 4 N 次实数加法。2 实现复数零点。x(n)是一个N点序列，n = 0,1,2,., N -1。在x(N) = 0点上。计算状态变量弘和v。这时，按 照图5.9.2算出滤波器的输出y (N)，此即X(k)。所需的计算量是4次实数乘
6、法和4N次实数加法。k综上所述，计算一点X (k)需要进行2(N + 2)次实数乘法和4(N +1)次实数加法。这种算法要 求的乘法次数约为直接算法的一半。在这种较为有效的方案中，仍具有这样的优点，即必须计算和存 储的系数只有cos(2兀/ N )k)和Wk。N最后，还要说明图 5.9.2所示的算法的另一个优点。当输入序列为实序列时，离散付里叶变换序列 X(k)是对称的，即X(k) = X*(N-k)。容易证明，图5.9.2的网络形式在计算X(N -k)时和计算 X(k)时具有完全相同的极点，但前者的零点系数与后者的零点系数成复共轭关系。由于零点仅在最 后的迭代中实现，所以诸极点要求的2N次乘
7、法和4N次加法可以用来计算离散付里叶变换的两个 值。因此，若用Goertzel算法计算离散付里叶变换的所有N个点的值，需要的乘法次数近似为N2， 加法次数近似为2 N 2。然而，它同直接计算离散付里叶变换一样，计算量仍然正比于N 2。5.9.2 双音多频(DTMF )信号在数字电话中，每个拨号键产生的信号由两个音频组成，其一是低音频，另一是高音频。4个低 音频(697Hz、770Hz、852Hz 和 941Hz)和 4 个高音频(1209Hz、1336Hz、1477Hz 和 1633Hz)分别 组成低音组FL和高音组FH。这种信号称为双音多频(dual-tone multifrequency,
8、 DTMF)信号。可视 化程序B0416演示DTMF信号的产生与检测。其界面示于图5.9.3。图中，左下角是DTMF键盘，由 10 个数字键和 6 个功能键组成。每个数字键产生高、低音频信号各一个。例如，按下“7”键时，产 生频率为FL二852Hz和FH二1209Hz的正弦序列。其合成序列为x(n)。用Goertzel算法对序列x(n)进行解码，得8点频谱| X(k) |，其中以k = 22 (相应于FL = 852Hz )和k = 31( FH = 1209Hz )这两条谱线的幅度最大。由此得知被按下的键为“7”。下一节介绍用Goertzel算法实现DTMF检测。DTMF键盘模拟始堆终端|
9、67392477 167392477I检测方法退出一4-7703316747852941-F-W-FFL(Hz)I697 1FH(Hz) - 1209 13364 / rITTTTr / I/!7VVVVGoertzel |亠算法DFT算法图 5.9.3 DTMF 键盘及其检测5.9.3 用Goertzel算法实现DTMF检测在实践中，由于通信线路中还包含语音信号。而语音信号的特点是二次谐波比较大，所以在线路 终端进行解码时，除了检查DTMF的8个频率点外，还要检查它们的二次谐频。如果二次谐波小，就 可以确信这是DTMF信号，进一步检测哪两点的频谱幅度最大，从而确定键值。由于我们只对DTMF
10、的8个频率点及其二次谐频感兴趣，所以最好用Goertzel算法代替DFT进行分析。图594基于Goertzel滤波器的DTMF解码原理图5.9.4示出基于Goertzel算法的DTMF检测方案的框图。整个方案由8对Goertzel滤波器组成。 每对滤波器检出一个DTMF信号及其二次谐波。二次谐波用来甄别语音和DTMF信号。语音含有很 大的偶次谐波，而DTMF信号则无。将每个输出求平方，以测出每个DTMF频率及其二次谐波的信 号强度。问题是怎样选择 Goertzel 滤波器的参数。 首先， 数字电话系统中的采样频率已确定为fS = 8000Hz。这个选择是合适的，因为DTMF信号的8个频率及其二
11、次谐波频率都落在奈奎斯特区间中。其次，主要问题是怎样选择数据点数N以得到可靠的频率分辨率。N越大，频率分辨率就 越高。但是，对于按键的最短时间要求是40ms，所以，可用的数据点数可能少至N二0.04 x8000。 在8个基频中，相邻基频差最小值为770-697二73Hz。若要保证两个相邻基频序号之差至少为2,73则频率分辨率应为D 2二36.5，故N应取200以上。另一方面，在频谱图上，8个基频及其二次谐频由谱点序号k标识。由此算出的频率与实际的基频和二次谐频相比，是有误差的。为了使误差最 小,应在N二200 300范围内再做细致选择。人们研究的结论是：对于已选定的8个基频，N二205 是最好
12、的选择。表5.9.1列出详细的数据(引自Ref.12)。表591各个拨号频率及N二205时所对应的DFT序号8个基频(Hz)准确k值最近整 数k值绝对误差二次谐波 频率(Hz)准确k值最近整 数k值绝对误差69717.861180.139139435.024350.02477019.531200.269154038.692390.30885221.833220.167170442.813430.18794124.113240.113188247.285470.285120930.981310.019241860.752610.248133634.235340.235267267.134670.134147737.848380.152295474.219740.219163341.846420.154326682.058820.058程序B0416和M050901.M是基于以上考虑而编制的。可视化VB程序B0416的界面已见于图5.9.3。程序M050901.M运行时，命令窗要求用户输入8位电话号码code，之后，程序检测该码， 并予以显示。例如，若键入 code =“67392477”，则程序显示检测结果，如图5.9.5所示。图5.95 8位电话号码的DTMF检测结果
