Goertzel 算法及其应用.doc

5.9 Goertsel 算法及其应用5.9.1 Goertsel 算法 如前所述, 点时域序列的离散付里叶变换式为， （5.9.1）这点频域序列是同时被算出的，不可能只计算其中某一个或几个指定点。Goetzel 算法是为了解决这个问题而提出的。这个算法把离散付里叶变换看作一组滤波器，将输入端的时域序列与其中一个滤波器的冲激响应序列进行卷积运算，求滤波器的输出序列，即得序列的一点。这种算法利用旋转因子的周期性，使DFT运算化为线性滤波运算。 由于 故式（5.9.1）可化为 ， （5.9.2）定义序列为 （5.9.3A）可见是由两个序列卷积而得到的序列。 （5.9.3B）其中，是输入的点序列，另一个序列被看作滤波器的冲激响应序列。 （5.9.4）对比式(5.9.2）和式(5.9.3），可知：按式（5.9.3A）进行卷积运算，当时，滤波器的输出就是： （5.9.5）对式(5.9.4)进行Z变换，可得滤波器的系统函数 （5.9.6）这是一个一阶系统。图5.9.1示出这个系统的信号流图，相应的差分方程为 ， (5.9.7) 按照此式进行递推运算，到了 时刻，即可依据式（5.9.5）得到。 按照式(5.9.6)进行运算时，可先算好旋转因子，储存起来。每次递推包含一次复数乘法。按式(5.9.1)直接计算点离散付里叶变换,需要次实数乘法和次实数加法。按照上述Goertzel算法，所需的实数乘法和实数加法都是次。所以当不大时，上述算法的效率稍差。下面介绍改进的Goertzel 算法，这种算法所需的实数乘法次数约为直接方法的一半。图5.9. 1 用一阶系统实现Goertzel 算法 图 5.9.2 用二阶系统实现Goertzel 算法 把式（5.9.6）的分子和分母都乘上因子，就得到第个滤波器的系统函数为 （5.9.8）与此相应的信号流图示于图5.9.2。由式(5.9.8)可见，滤波器是一个二阶系统，有一对复数共轭极点和一个复数零点。为了便于运算，在图5.9.2所示的流图中，设立状态变量 和。按照图5.9.2计算时，步骤有二，即：1 实现一对复数极点输入点依次取 ，进行递推运算。每次运算中，更新状态变量和。作次迭代所需的计算量是次实 数乘法和次实数加法。2 实现复数零点。是一个点序列， 。在点上。计算状态变量和。这时，按照图5.9.2算出滤波器的输出，此即。所需的计算量是4次实数乘法和次实数加法。 综上所述，计算一点需要进行次实数乘法和次实数加法。这种算法要求的乘法次数约为直接算法的一半。在这种较为有效的方案中，仍具有这样的优点，即必须计算和存储的系数只有和。最后，还要说明图5.9.2所示的算法的另一个优点。当输入序列为实序列时，离散付里叶变换序列是对称的，即。容易证明，图5.9.2的网络形式在计算时和计算时具有完全相同的极点，但前者的零点系数与后者的零点系数成复共轭关系。由于零点仅在最后的迭代中实现，所以诸极点要求的次乘法和 次加法可以用来计算离散付里叶变换的两个值。因此，若用Goertzel 算法计算离散付里叶变换的所有个点的值，需要的乘法次数近似为，加法次数近似为。然而，它同直接计算离散付里叶变换一样，计算量仍然正比于。5.9.2 双音多频（DTMF）信号在数字电话中，每个拨号键产生的信号由两个音频组成，其一是低音频，另一是高音频。4个低音频（697Hz、770Hz、852Hz和941Hz）和4个高音频（1209Hz、1336Hz、1477Hz和1633Hz）分别组成低音组FL和高音组FH。这种信号称为双音多频（dual-tone multifrequency, DTMF）信号。可视化程序B0416演示DTMF信号的产生与检测。其界面示于图5.9.3。图中，左下角是DTMF键盘，由10个数字键和6个功能键组成。每个数字键产生高、低音频信号各一个。例如，按下“7”键时，产生频率为和的正弦序列。其合成序列为。用 Goertzel 算法对序列进行解码，得8点频谱，其中以（相应于）和（）这两条谱线的幅度最大。由此得知被按下的键为“7”。下一节介绍用Goertzel 算法实现DTMF检测。 图5.9.3 DTMF 键盘及其检测5.9.3 用Goertzel 算法实现DTMF检测在实践中，由于通信线路中还包含语音信号。而语音信号的特点是二次谐波比较大，所以在线路终端进行解码时，除了检查DTMF的8个频率点外，还要检查它们的二次谐频。如果二次谐波小，就可以确信这是DTMF信号，进一步检测哪两点的频谱幅度最大，从而确定键值。由于我们只对DTMF的8个频率点及其二次谐频感兴趣，所以最好用 Goertzel 算法代替DFT进行分析。 图5.9.4 基于Goertzel 滤波器的DTMF 解码原理图5.9.4示出基于 Goertzel 算法的DTMF检测方案的框图。整个方案由8对Goertzel 滤波器组成。每对滤波器检出一个DTMF 信号及其二次谐波。二次谐波用来甄别语音和DTMF 信号。语音含有很大的偶次谐波，而DTMF 信号则无。将每个输出求平方，以测出每个DTMF 频率及其二次谐波的信号强度。问题是怎样选择Goertzel 滤波器的参数。首先，数字电话系统中的采样频率已确定为。这个选择是合适的，因为DTMF 信号的8个频率及其二次谐波频率都落在奈奎斯特区间中。其次，主要问题是怎样选择数据点数以得到可靠的频率分辨率。越大，频率分辨率就越高。但是，对于按键的最短时间要求是，所以，可用的数据点数可能少至。在8个基频中，相邻基频差最小值为。若要保证两个相邻基频序号之差至少为2，则频率分辨率应为，故应取200以上。另一方面，在频谱图上，8个基频及其二次谐频由谱点序号标识。由此算出的频率与实际的基频和二次谐频相比，是有误差的。为了使误差最小，应在范围内再做细致选择。人们研究的结论是：对于已选定的8个基频， 是最好的选择。表5.9.1列出详细的数据(引自Ref.12)。 表5.9.1 各个拨号频率及时所对应的DFT序号8个基频 (Hz)准确k 值最近整数k值绝对误差二次谐波频率 (Hz)准确k 值最近整数k值绝对误差697 17.861 18 0.139 1394 35.024 35 0.024 770 19.531 20 0.269 1540 38.692 39 0.308 852 21.833 22 0.167 1704 42.813 43 0.187 941 24.113 24 0.113 1882 47.285 47 0.285 1209 30.981 31 0.019 2418 60.752 61 0.248 1336 34.235 34 0.235 2672 67.134 67 0.134 1477 37.848 38 0.152 2954 74.219 74 0.219 1633 41.846 42 0.154 3266 82.058 82 0.058 程序B0416和M050901.M是基于以上考虑而编