使用Goertzel算法识别DTMF信号

Goertzel算法

Goertzel算法由Gerald Goertzel在1958年提出，用于数字信号处理，是属于离散傅里叶变换的范畴，目的是从给定的采样中求出某一特定频率信号的能量，用于有效性的评价。

这个算法有几个关键的参数：

• 采样率R，指的是需要分析的数据每秒钟有多少个采样
• 目标频率f，指的是需要检测并评价的这个频率的值
• 检测区段采样值数量N，也就是每N个采样这个算法会对频率f给出评价
• 检测区段包含目标频率的完整周期个数K

很显然，上述参数应该有这样的关系：

K = Nf / R

这个K值应该是一个整数，而且要大小合适。如果太大，不利于检测的时效，如果太小，则检测可能不准确。例如十几甚至二十几左右应该相对合理。例如R为8000，需要检测800hz的频率，N取值100，那么K为10，很不错。但是，需要检测的频率有时候并不那么整，例如697，那么N应该取值多少呢？N在1000以内，无法得到一个整数K，我们只能退而求其次，找一个四舍五入误差最小的。例如N取115，K的计算结果为10.019375，四舍五入为10，而且有较小的误差。

有了上述的参数，然后我们来计算每个采样在一个目标频率一个周期中所占的弧度ω。既然N个采样表达了K个周期(2π)，那么ω应该这样计算：

ω = 2πK / N

这里需要注意的是，因为K值可能经过了四舍五入，所以上述两个公式必须先后计算，一定不能合在一起化简把K约掉！

然后，我们可以得到后期计算会频繁遇到的系数C:

C = 2cos(ω) = 2cos(2πK / N)

以上参数，我们都可以事先计算好，不必在每个采样分析中再次计算。之后，就开始针对N个采样进行分析计算

首先初始化：

Q₁ = 0
Q₂ = 0

然后按照顺序针对N个采样每一个值S（我认为这个S一般是一个16位的有符号整数，取值范围在-32768到32767之间，如果你得到的是已经进行过编码的媒体流，例如G.711编码，那么需要首先解码。当然也许采样值就是-128到127之间的单字节整数，那么这样对计算结果中的P值会影响巨大，DTMF识别的时候一些判断参数可能要调整），做如下计算：

Q₀ = CQ₁ - Q₂ + S
Q₂ = Q₁
Q₁ = Q₀

上述计算完成之后，我们就可以得到在这N个采样中所体现的频率f的能量值P:

P = Q₁² + Q₂² - CQ₁Q₂

DTMF识别

以上是goertzel算法的全部思想。如果我们要将其用于DTMF识别，还需要做一些工作。DTMF识别，我们需要根据给定的一段时间的采样，能够最大限度地排除噪音的干扰，将有效的DTMF信号识别出来

我们知道DTMF有8个频率：697, 770, 852, 941, 1209, 1336, 1477, 1633，通过前4个频率和后4个频率的两两组合，确定16个符号。那么我们在对给定一段时间的采样进行处理的时候，就需要先将其分为每段为N个采样的多个采样区段，然后对每一区段针对8个频率分别运用goertzel算法进行计算得到每个频率的能量P

为了完成这些能量的计算，我们需要在开始针对8个不同的频率分别计算系数C，而参数N的选择非常关键，因为8个频率的K值都不同，我们要尽可能使得8个频率的K值四舍五入之后都误差尽可能小，经过检验，在采样率为8000的时候，N=205应该是一个最佳值，你可以做一个测试：

N= 

f	K实际值	K近似值	误差
697	4.35625	4	0.3562500000000002
770	4.8125	5	0.1875
852	5.325	5	0.3250000000000002
941	5.88125	6	0.11875000000000036
1209	7.55625	8	0.44374999999999964
1336	8.35	8	0.34999999999999964
1477	9.23125	9	0.2312499999999993
1633	10.20625	10	0.2062500000000007

针对N个采样值，对8个频率分别计算出了能量P之后，我们就可以开始评估这些能量值是否足以表明这N个采样中含有某个DTMF符号

DTMF符号和频率的对应关系如下：

f	1209	1336	1477	1633
679	1	2	3	A
770	4	5	6	B
852	7	8	9	C
941	*	0	#	D

我们从1209, 1336, 1477和1633四个频率对应的能量P中取最大值，记作P_x，从679，770，852和941四个频率对应的能量P中取出最大值P_y。那么P_x和P_y对应的频率组合极有可能代表识别出一个DTMF符号。但是，我们还需要做一系列的判断，来进一步评估：

1. P_x和P_y是否足够强大？我们可以设定一个门限，如果么P_x和P_y这两个任何一个低于这个门限，那么N个采样被评估为没有识别出DTMF符号。参考资料[2]中建议这个门限值为4*10⁵。但是如果采样值的取值范围是-32768到32767的话，实际上计算出来的P值会非常大，这个门限设为4*10⁹都可以。
2. P_x和P_y的差别是否太大？正常的DTMF信号，这两个能量应该接近，那么如果差别较大，我们视为无效。参考资料[2]中建议的方法为：如果P_y < P_x * 0.398，那么认为无效。如果P_x < P_y * 0.158也认为无效。但是实际上，我们将0.158改为0.5，识别效果更佳。
3. 其它频率的能量P有没有很多接近P_x和P_y的？参考资料[2]中建议的方法为：首先取近P_x和P_y中较大的那个，设为P_m，如果其他频率的P值有2个以上达到了P_m的15.8%，那么认为是噪音导致，视为无效。

如果上述三个检验关卡都通过了，那么我们可以将这N个采样评估为包含一个DTMF符号，即P_x和P_y对应的频率组合对应的某个符号。

参考资料：

[1] https://en.wikipedia.org/wiki/Goertzel_algorithm
[2] https://en.wikipedia.org/w/index.php?title=Goertzel_algorithm&oldid=17802166