[Back to Home Page]
www.RomanBlack.com
Black DTMF Decoding Algorithm
Decoding DTMF tones on the minimum PIC hardware - a new algorithm.
Roman Black - 5th March 2011.
Note!! This page is about decoding DTMF. If instead you want to generate
DTMF I have a nice sinewave DTMF generator algorithm in C code you can see
here.
DTMF
DTMF is Dual Tone Multi Frequency, (or "Touchtone") these are the sounds
made by telephones to dial a number. Each DTMF sound is made by two frequencies
which are mixed together.
Standard DTMF encoding
DTMF decoding normally uses a specialty IC that receives the DTMF waveform
and "decodes" it to one of the 16 possible outputs, usually as a 4bit binary
output. These IC's are hard to get for hobby and project use, and can be
expensive in small quantities, and require extra components including
a 3.79MHz xtal.
DTMF decoding can be done in software on a high power microcontroller or DSP micro
using FFT (Fast Fourier Transform).
DTMF decoding can be done reasonably well in software using mid power micros using
a modified Goertzel's algorithm or a similar form of DFT (Direct Fourier
Transform) but this still requires a decent amount of processing power,
ROM for the sin/cos tables and the process is complex and not very versatile.
My DTMF decoding algorithm
I decided to try a totally different approach. Rather than use a math
system like Goertzel or DFT and then try to squeeze it into a tiny low-cost PIC,
I would start with the small PIC then try different techniques which
are each optimised for the strengths of the small PIC and hopefully combine
the techniques to work synergistically to get a "good enough" finished
result that will decode DTMF reasonably reliably with simple and
tunable code.
Capitalising on the strengths of a small PIC meant starting with the
things it could do well;
1. Internal comparator; good zero-crossing detection
2. Since the PIC has a xtal; accurate period measurement
And well, that's about it. :)
I made up some standard DTMF waveforms in a spreadsheet program, and
analysed the waveforms. These waveforms have zero "twist" which means the
high DTMF tone and the low DTMF tone have the same amplitude. This is a
reasonable enough representation of the received DTMF tone from a telephone line.
The minimal hardware dictated that the DTMF waveform
would simply be AC coupled to the PIC comparator input pin through a capacitor,
to make a zero crossing detector. This produces a simple ON-OFF signal or
"1 bit DAC".
If this was going to be possible using period measurement I needed a way
to reduce the period triggering to the most secure parts of the waveform,
which was done creating the "HI-LO debounce system" that is very good
at removing zero-cross noise and high frequency mis-triggering and produces
reliable periods, synchronised to the DTMF waveform.
The HI-LO debounce system detects the more reliable parts of the
DTMF wave, the major peaks and troughs. This is done by cyclic testing using
a debounce feature;
1. Wait until it detects a 220uS period that is at least 90% high (sampled every 5 uS)
2. Grab the timer value (used to capture a period)
3. Wait until it detects a 220uS period that is at least 90% low (sampled every 5 uS)
4. (repeat)
As you can see above, this seems to work quite well in theory, it eliminates
the noise and high frequencies and zero-cross fluff very well, and seems to
capture the major periods fairly reliably. It also reduces the need for external
hardware as it provides a significant filtering effect by software alone.
This debounce feature works synergistically to be more than just a period
measurement, because it is only triggered on a certain characteristics of
the DTMF waveform it perfoms a crude pattern recogniton too, as you
can see it triggers only in response to certain major peaks.
This will be very useful later.
Another benefit of this system is that unlike Goertzel or DFT this is not
limited to any specific frequency, so the same hardware and code can just
as easily detect the dial tone, ring tone, or ringback tones etc, and can
detect a single tone if needed or dual tones, all of which
may be of benefit in a PIC telephone application.
Analysing the periods - ideas?
Since these periods looked reliable (in theory) and are closely correlated
to the frequencies of the 2 sinewaves in the DTMF waveform, the next step was
to see if a small PIC could somehow analyse the periods to deduce the DTMF tones.
Fortunately these periods are fairly long, from 800 to 1600 uS (a synergistic
benefit of the HI-LO debounce system) so there is plenty of time even on
a small PIC to do some processing or testing between each period capture.
The obvious thing would be to test the frequency spectrum, (period spectrum?)
for the most popular periods that are detected and see if these periods
can be directly used to indicate the DTMF frequencies. For convenience,
instead of trying to detect the 2 separate sine frequencies it would be
simpler to test for a "match" to each one of the 16 DTMF combinations and
it's particular signature.
The DTMF 941 1633 example from above produces a lot of periods
of about 1155 uS and some periods of about 788 uS, and not much of anything
else. In fact there are about 5 of the longer periods for every 2 of the
shorter periods. So for 50 periods tested, the spectrum analyser should
look something like this;
Testing it in real world hardware
First I made a spectrum analyser, this was actually easier than it sounds.
I used my trusty MikroElektronika SmartGLCD and wrote some code so it can
capture periods on the PIC comparator input using the zero-cross HI-LO debounce
system I designed above. This enabled testing of the actual comparator system
as well as just being a period spectrum analyser.
I simplified the HI-LO debounce by just checking for 200uS continuous HI and
200uS continuous LO to trigger each cycle. The DTMF was generated by another PIC
using my PIC dual sine accurate DTMF generator (see link at page top). The systems
were linked by a 3k trimpot to adjust the DTMF waveform amplitude and a 0.1uF
AC coupling cap. A very crude and simple hardware setup.
The software is quite simple; it measures 50 consecutive "debounced" periods, records them
as 50 entries in ram, and then draws them on a bar chart where each period
is drawn as 1 pixel high on the bar. Only 128 bars were used, keeping it
simple as this will be ported to a small PIC 12F or 16F later.
I really didn't expect this good a result, but it worked perfectly. :)
Using the simplest period measurement possible, the PIC TMR0 was set to 16uS
per timer tick. So the period of 72 shown above = 72 x 16uS = 1152uS. On the
right of the bargraph is shown the 6 most common periods, ranked vertically.
It matches the expected result very well, although each period may be +/-
1 count because of the crude resolution used to measure period. (In reality it
tested significantly better than +/- 1 count). The most common period was detected
as period 72 and 73, with a total number of samples of 27+8 = 35 samples. The next
period was detected as 49 and 50 with total samples of 10+3 = 13. Then there
are a couple of defective samples, due to noise etc.
This result almost perfectly matches the math model generated in the spreadsheet
as the original concept waveform! That predicted 36 and 14 samples for the
two main frequencies, the actual hardware produced 35 and 13.
I set the spectrum analyser to continuously log and display, and turned the DTMF
waveform amplitude up and down. The result was always good, with DTMF waveforms
ranging from 2.6v p/p (the max) down to about 0.4v p/p and all amplitudes gave
a very similar result on the spectrum analyser. This was excellent!
Can this simple period data decode the DTMF?
The periods shown below are from my testing in hardware. A period of 100 = 1600uS.
Percentages are approximate but seemed reasonably reliable over many sample
iterations and different DTMF waveform amplitudes. I have guesstimated fractional periods
based on the appearance of the spectrum analyser bars.
The time taken to get 50 period samples is somewhere in the 40 to 70 mS range.
DTMF pair per1 % per2 %
697 1209 98 56 66 30
770 1209 63.3 46 94 44
852 1209 60.7 65 90.4 35
941 1209 58.1 70 86.5 26
697 1336 92 74 62 5 ?
770 1336 88.7 66 60 26
852 1336 85 52 57.6 40
941 1336 55 56 82 42
697 1477 86 80 114 6 ?
770 1477 83 88
852 1477 80 72 54 26
941 1477 76.9 54 52.1 42
697 1633 80.7 66 106.3 32
770 1633 78 86 102.5 12
852 1633 75 90
941 1633 72.2 72 49.3 26
The figures above were quite reliable, with a fixed frequency source (my xtal locked
DTMF sine generator) the periods remained within about 0.3% from test to test.
Much less than 1 bar period error on the bargraph.
The percentages of the 2 main periods also remained reliable, within 4% and generally better.
How to decode it?
If the DTMF generator frequencies were quite exact (say < 0.5% freq error) this would be
as easy as using the most common (primary) period. The two closest periods are 85 and 86
so they are separated by 1.1% difference in period. That would already be
a workable DTMF decoder, but relies on having a good DTMF generator.
The DTMF spec requires that the decoder will accept generated DTMF
up to +/- 1.5% freq error.
Usually the real life DTMF is made by dedicated DTMF generator ICs, and
although these are xtal locked their frequencies are approximate and
according to some popular IC datasheets the frequencies are normally
within 0.3% or so, with an occasional error as large as 0.7%.
So for general use it won't be accurate enough just using the one
primary period for testing although it does come close.
The good news is that it has been extremely easy to get this data, consisting
only of a simple comparator, software debounce, and recording 50 consecutive periods.
Can this meet DTMF decoder requirements?
The period data from 50 period samples contains more data than just the most common
(primary) period. It might be possible to make use of the other data to improve the
decoder spec.
As an example, for these two DTMF "worst case" tones;
Tone"8" 852 1336 85 52% 57.6 40%
Tone"3" 697 1477 86 80% 114 6%
If both use a wider period match, like accepting +/- 1.5% freq
error each period filter will be;
(85) 83.7 to 86.3
(86) 84.7 to 87.3
So there will be a significant overlap and both primary periods (85 and 86) will be detected.
But the other data can be processed, as with DTMF Tone"8" the 85 period occurs only 52%
of the time and has a second period of 57.6 that occurs 40% of the time.
Where the DTMF Tone"3" has period 86 very dominant at 80% and its second period is 114
and occurs only 6% of the time.
It can use a weighted points system that allocates points for each detected
period;
if(period is 83 to 87); Tone"8" += 1 and Tone"3" += 1
if(period is 56 to 59); Tone"3" += 4
if(period is 112 to 116); Tone"3" += 20
Those figures were just chosen arbitrarily. For 100 tested periods from each Tone,
the points result would be;
Actual DTMF Tone"8"
Tone"8" points = 52*1 + 40*4 = 212
Tone"3" points = 52*1 + 0*20 = 52
Actual DTMF Tone"3"
Tone"8" points = 80*1 + 0*4 = 80
Tone"3" points = 80*1 + 6*20 = 200
So in the case of those two DTMF tone examples, even though the primary periods
were both indistinguishable (85 and 86) there was enough difference in the
weighted points that were allocated to clearly identify each DTMF tone and
meet the required spec for +/- 1.5% frequency deviation in all the tested periods.
A practical DTMF decoder?
Given that we can very easily collect the periods on a small PIC and
can very easily add weighted points values into 16 "Tone accumulators" for
each period we get, this should be a workable DTMF decoder system.
My first practical decoder seems to work ok and uses this system;
1. HI-LO debounce of 220uS continuous state
2. Record 30 consecutive periods, as bytes, using TMR0 with resolution 16uS
3. Count the periods and allocate weighted points into 16 byte result accumulators
4. The accumulator with the highest number is the DTMF Tone, but only if;
5. that number is within a "safe window" to eliminate non-DTMF signals
Sampling only 30 periods takes under 45 mS and complies good enough
with the standard minimum DTMF tone length of 51mS. The decoder seems to
work well enough to find the highest points to match the DTMF Tone, but
a "window" is needed to reject non-DTMF signals like solid tones and
complex tones (like voice).
Note! I recorded the 30 periods into RAM, then did post-processing
to allocate the weighted points. This was done because I also wanted to
chart the results and needed to record them. For a practical decoder
the recording is not needed, it can analyse each period easily in real time
and only needs the 16 RAM bytes for the result accumulators.
Results of testing;
The numbers on the right of the display show the 16 result accumulators.
Above is an example of what most of the tones look like, there is
a clear winner, in this case it is Tone 10 (852 1477).
Tone 3 (941 1209) shows a clear winner. Again this is pretty typical.
Tone 6 (852 1336) is one of the worst cases, it's reliable enough but there
is not a very large safety margin.
Here are the weighted points values I used for the different periods;
DTMF_simple_points.c
This is looking promising. Although it is not fully practical, this simple decoder
uses no input hardware, very litle ROM, only TMR0 set to a low 16uS
resolution, very little RAM, no interrupts, and only needs a slow PIC
(assuming it does the weighted points in real time after each period capture).
And it gives a working decode from as little as 30 periods (under 45 mS).
It's not a great decoder but it's working and would be possible even on
a 4MHz PIC 10F, 12F or 16F, ie the bottom end PICs!
Decoder version 2 - a major improvement
The simple decoder above is basically just a crude spectrum analyser.
All its decoding is based on the number of periods that fall within
specific zones, and it JUST has enough information to decode the 16 DTMF
Tones.
It occurred to me when making the top waveform diagram on this page that
my HI-LO debounce actually performs a crude pattern recognition task as it
will only synchronise to certain characteristics of the DTMF waveform.
But the benefits of this pattern recognition are largely wasted as the
simple decoder above makes no use of the order the periods are in, only
the amount of each period.
So if the decoder could evaluate the order that the periods were captured in
it would provide a lot more data to improve the separation between detecting
individual DTMF Tones, and also improve the noise rejection so the decoder can
more easily eliminate non-DTMF sounds.
How would this extra pattern recognition work?
Below are the two DTMF tone waveforms that the simple decoder was having some
difficulty separating. The captured periods (in purple) are almost identical on each
DTMF tone. It was separating the two tones based on the fact that Tone 3
has a lot more of the shorter periods than the longer period, a ratio of
about 5:2. Where Tone 6 has different numbers of the shorter and longer
periods, a ratio of about 3:4.
Above in Tone 3 you can see the new data, with some "double" periods drawn in
orange and brown. These demonstrate the most basic pattern that is present;
the 2 consecutive periods.
If we call the short period S and the long period L,
most double periods consist of an SL pair with SS pairs too. The
frequency of the patterns in Tone 3 is; SL/LS=4, SS=3, LL=0.
Above in Tone 6 the period pairs look very different! They are mostly
SL pairs with one LL pair, the pair frequency is; SL/LS=6, SS=0, LL=1.
Making the best of the pattern data
Some system of allocating weighted points for each pattern that appears
would quickly identify each DTMF tone signature. However if the points
are based mainly on the SL pairs these will be common to more than one tone
(see Tone 3 and Tone 6 example above), and also if points are allocated
for SS and LL pairs this will compromise the rejection of single frequencies
like SSSSSS and LLLLLL.
The first solution I tried was to allocate points for tiplets. Triplets
like SSL, LSS will be extremely common in Tone 3, but never appear in Tone
6 which will be full of LSL, SLL and LLS pairs that never appear in Tone 3.
Itentifying triplets can be done extremely fast and efficiently in real time
as each new period is captured. It only needs 32 captured periods to make 30
triplets in real time. It should be possible to add weighted points for "good"
triplets and maybe subtract weighted points for "bad" triplets. This will give
excellent separation between DTMF tone signatures and provide very high
rejection of non-DTMF sound and single frequencies.
I built a DTMF period triplet analyser;
This uses the same hardware as the spectrum analyser, and really it is a
triplet sepctrum analyser. It identifies the DTMF tone, then records 1002 periods
(1000 triplets) which are then displayed to show how popular the Short and Long
periods are, and then the 8 possible triplets.
Here are the triplet analysis results for Tone 3 and Tone 6,
the triplets are exactly as predicted by the theory waveform.
This is data for 1000 triplets.
Here is data from hardware testing 1000 triplets for each DTMF Tone.
It shows periods as Short/Long periods, and shows the most common triplets by percentage;
Tone DTMF pair Short % Long % SSS LLL SSL LSS LLS SLL SLS LSL BAD
0 697 1209 66 29 98 57 9 19 19 20 32
1 770 1209 63.3 43 94 49 10 10 27 32 19
2 852 1209 60.7 58 90.4 39 16 16 39 22 8
3 941 1209 58.1 71 86.5 28 14 28 28 28 1
4 697 1336 62 10 92 77 53 7 7 4 23
5 770 1336 60 27 88.7 66 16 23 23 23 13
6 852 1336 57.6 43 85 56 13 13 29 42 3
7 941 1336 55 58 82 42 16 16 42 26 1
8 697 1477 86 84 114 9 58 10 10 10 11
9 770 1477 56.8 8 83 91 75 8 8 8 1
10 852 1477 54 26 80 73 20 26 26 26 1
11 941 1477 52.1 43 76.9 57 14 14 29 43 1
The triplet pattern recognition seems very reliable! Surprisingly, I did not see
one false positive triplet even after many tests.
The only DTMF tones that may cause issues are Tones 4, 8 and 9, these have a
very low incidence of one period.
The Black DTMF triplet decoder
Basics;
1. the debounce system produces 2 distinct periods from any DTMF waveform
2. these 24 specific periods are detected with narrow windows (very high rejection)
3. a "triplet" of the last 3 periods is checked for a match
4. if it matches, it allocates points scores for the 12 DTMF signatures
The algorithm procedure;
1. HI-LO debouncing on the input signal, both must be stable for 220uS
2. Capture the period using TMR0 with resolution 16uS
3. See if that period matches one of the 24 periods in the table,
4. if so, test for a valid triplet and allocate weighted points
5. Repeat 1-4 until 30 triplets have been tested
6. The accumulator with the highest score is the DTMF Tone!
7. (That highest number can be further checked within a window if needed)
Triplet weighted points
The triplets that match a DTMF tone will cause points to be added to the
accumulator for that DTMF tone. If a tone is perfect (like in testing above)
the points should equal about 150 but they should never be high enough to
roll the variable, ie they will always be under 256.
Practical testing
I coded the new DTMF triplet algorithm into the same hardware. It still
displays the spectrum analysis of the periods (like the first algorithm) but
this is not used for the decoding. Now it uses the period triplet decoding.
Some results are shown below.
Tone 3 and Tone 5 are shown.
The display shows the spectrum chart of the 30 period samples, then text showing
the periods and the number of periods, and on the right it shows the
12 DTMF points scores.
All 12 DTMF signatures have extremely high separation as seen in the two
examples above. Even from a short 45mS sample time, with as little as 32 periods
(30 triplets) it looks to be a solid reliable DTMF detection.
The particular triplets I chose for the tests have both a Short and Long
period so this new decoder is completely immune to being triggered from
a single frequency tone.
Here is the crude system I used for decoding triplets into weighted points;
DTMF_decode_triplet_points.c
Using the decoder
This decoder will run on extremely limited hardware and has the benefit of
having very high rejection of non-DTMF waveforms.
It is also very open-ended and can be optimised to detect a single DTMF tone
(or just a couple of DTMF tones) to save code space.
Both these features can make it ideal for a cheap DTMF remote control type
receiver, or adding that type of function to a small PIC project.
It also forms a companion to my
DTMF dual sine generator PIC code,
so it provides the ability to use a couple of low-end PICs to do both the
DTMF generation and decoding without needing specialty chips.
The strong period filters and pattern recognition should mean that this
system will outperform standard analog DTMF decoder ICs and Goertzel systems
for rejection of non-DTMF waveforms (ie remote control use), but they will
be superior to it for accepting DTMF in a very noisy environment. If needed,
my system can be made more noise tolerant with a larger sample sizes, and
a little more processing.
Optimising the decoder
HI-LO debounce time. This needs to be right around 220uS for best
triggering from the DTMF waveform. Also test very often within the 220uS, I used
5uS samples. If this is done right the decoder will detect 2 very dominant
periods from any DTMF tone, as seen in examples above.
Period filtering. I used +/- 1 count, so if the period was 80 it
would detect 79-81 and reject everything else. This gives a very high
rejection of non-DTMF signals. You can go to +/-2 or even more if needed
which improves detection in a noisy environment. Just watch for overlap
as some tones use similar triplets so they should not be allowed to overlap
period filter windows.
Triplet analysing for pattern recognition.
You probably don't need to adjust these, my code
gives good performance by picking the right triplets to match for each
DTMF signature and I have tuned the weighted points for a sample size
of 30 triplets, so that's done.
Testing the points result. All you need to do here is find the
highest score out of the 12 results, and check it is >X. For my code
above >50 would work well.
A working decoder in a PIC 12F675!
As a proof of concept here is a complete project, it is a DTMF remote control
decoder using a PIC 12F675 and 8MHz xtal. It would also work with a 4MHz
xtal if you change TMR0 to 1:8 prescale. A xtal is recommended as the internal
4MHz osc may not maintain a good enough frequency reference.
Hardware
It receives DTMF audio into pin GP1 (comparator input) and needs a 0.1uF to
1uF input cap (AC coupling cap). It also needs a 4k7 or 10k resistor from
GP1 to ground. That's about it, it works fine with DTMF amplitude from about
0.4v peak to peak to over 2v peak to peak.
This DTMF decoder uses 25 RAM (and the C stack) and 318 ROM. If you need to
decode all 12 DTMF tones it will fit in this PICs 1k ROM but you
need to reduce or remove the make_beeps() function. I have not tried to
shrink any of the code, as that should be quite possible.
Operation
All the PIC does is continually test the incoming signal in groups of
60 periods (60 triplets) which takes about 95mS for each group. The triplet decoding and
points allocating is done in real time after each period capture and there
is plenty of time even on this little PIC.
Two DTMF tones can be detected;
Tone 0 (the phone "1" key) = set output GP0 HI
Tone 7 (the phone "0" key) = set output GP0 LO
Also, after the GPO output has been changed the PIC makes one or two
"beeps" confirmation on GP2, these beeps can be to a LED or a speaker to
tell the user the signal has been received.
The project will decode any or all of the 12 DTMF tones, but the 10 tones
not used are commented out to save ROM and processing time.
It worked very well in testing, and should work for you too provided
the DTMF waveform is reasonably clean. If you have dirty DTMF waveform you
can clean it up a lot by adding a RC low-pass filter of 1k5 and 0.033uF
or 2 filters of 1k2 and 0.033uF. But this should not be needed in
most cases as the algorithm itself will tolerate a decent amount of noise.
The extra filter will be most useful for radio apps that may have hiss
on the signal.
An obvious use for this would be as a remote receiver connected to a radio
or other audio system, to turn something on or off with a DTMF tone.
Likewise it could be used as a phone remote to turn something on-off at
home when you ring home from work. However you must check the legality
of connecting equipment to the phone line (it can be illegal in some
areas) and of course check for the spec and safety of the way you connect
the electronics to the phone line. There is a lot of info on the internet.
Here is the MikroC source code for the PIC 16F675;
DTMF_remote.c
Here is the HEX file if you just want to program a PIC;
DTMF_remote.hex
- end -
[Back to Home Page]