On Wed, 10 Mar 1999, Marc wrote:

> > Ive read the comments put onto the list by Scott , Marc and others with grea
t interest. Ive had a
> > fairly lengthy look at Scotts description on his web page. ( in actual fact
Ive read it lots ... &
> > lots of times ) and I sort of get the jist of what he's achieving.
> > Unforuntately for me Im not right up with the maths involved and actually co
ding this would be a
> > bit daunting for me. Im not really sure where to start !!! ..
>
> You don't need any math. Isn't that a fortunate coincidence?
>
> Imagine you sample a 697Hz signal at 697*8=5576Hz:
>
> A 697 Hz input      0000111100001111000011110000111100001111
>
> Further imagine, that whenever you take a new sample, you XOR it with the 4th
past sample:
>
>                     0000111100001111000011110000111100001111
>                     ^---^
>
>                 bcf     STATUS,C                        ; collect past 8 sampl
es
>                 rlf     OLDSAMPLES,f
>                 btfsc   INPUT_SIGNAL
>                 inc     OLDSAMPLES,f
>
>                 swapf   OLDSAMPLES,w
>                 xorwf   OLDSAMPLES,w                    ; XOR result in W.0
>
> If you were to collect those XOR results (lowest bit of W), they would look li
ke this:
>
>                     0000111100001111000011110000111100001111
>                     ^---^
>                     |^---^
>                     ||^---^
>                     |||^---^
>                     ||||^---^
>                     |||||^---^
>                     ||||||^---^
>                     |||||| ...
>      XOR Results    1111111111111111111111111111111111111111
>
> If, however, the input signal is _not_ a 697 Hz tone, but a 522 Hz tone, it wo
uld
> look like this:
>
> The 522 Hz tone     000111000111000111000111000111000111000111
>                     ^---^
>                     |^---^
>                     ||^---^
>                     |||^---^
>                     ||||^---^
>                     |||||^---^
>                     ||||||^---^
>                     |||||| ...
>      XOR Results    110110110110110110110110110110110110110110
>
>
> Or some weird input 101010001110111101011111110000101000010
>
>      XOR Results    00100110000110101010001111101010110
>
> You see the concept? The more 1s, the more similarity with your "reference sig
nal"
> (which is implied by the sample speed and XOR-width). Just count the 1s:
>
>                 andlw   0x01
>                 btfsc   STATUS,Z
>                 incf    ONES_COUNTER,f
>
>
> After 255 of such comparisons, check if the counter value is near 255 (697 Hz
> detected) or more like 200 (something else detected).
>
> If you're not satisfied with the performance, use a 16 bit counter and do the
> function over a larger time interval, and/or use a higher oversample factor
> (for example 697*64, and XOR each bit with its 6th predessor).

I like this.

Let me point out a couple of caveats.

1) There are 8 different frequencies in DTMF signals. Consequently, you'd
need 8 autocorrelators. This will have an effect of the way in whcih your
data is sample. Mainly because there is no simple relationship between the
tones (their frequencies are logarithmically related). So there is no
sample frequency that will simultaneously produce exactly an integer
number of samples for each tone.


2) The autocorrelation algorithm is sensitive to harmonics. For example,
imagine the 697Hz example above when a 1394 Hz tone is applied. The
autocorrelation is still perfect.

3) If there is a DC offset present in the digitization process or stated
similarly, if the square wave does not have a 50% duty cycle, the
autocorrelation is reduced. Another way of looking at this is from the
frequency point of view; the lower duty cycle has less energy at the
frequency of interest.

All of these caveats exist with the algorithm I use too. I've found ways
around them, and  I'm sure there are ways around them for the
autocorrelation algorithm.

For example, I could envision a relatively high frequency timer-based
interrupt routine stuffing sampled bits into a bit array and a
non-interrupt routine pulling them out. Phase accumulators could be used
to determine which bits in the bit array are of interest. The interrupt
routine would only need to buffer enough bits to protect against the worst
case scenario when all 8 frequencies would need to be processed. This
wouldn't happen to often (that having to process all 8 frequencies)
because the tones are not harmonically related.

I don't have time to right out all of the code, but what I'm trying to
seay can be expressed somewhat like so:

interrupt_routine:
{
 // a circular buffer

 bit_array[current_sample] = get_sample();

 current_sample = (current_sample+1) & ARRAY_SIZE_MASK;
}

process_sample()
{

 for each frequency
  {
    phase_accumulate();
    if phase accumulator rolled over
    {
      if msb(sampled_bits[frequency]   ) ^ bit_array[last_sample]
         autocorrelation[frequency]++;

      sampled_bits[frequency] = sampled_bits[frequency] <<1  |
         bit_array[last_sample]
    }

  }
  last_sample = (last_sample + 1) & ARRAY_SIZE_MASK;

}


main()
{
  do forever{
  if( last_sample != current_sample)
    process_sample();
  }
}

I hope this is understandable. The main point I'm attemptingto illustrate
is that you don't have to save a bazillion bit samples to simultaneously
process mulitple tones


> > Im also curious to know how this system actually compares with using a norma
l DTMF decoder chip .
> > Ie. is it better or worse than - with respect to noise imunity, tone detect
time, tone detect
> > accuracy etc.
>
> The DTMF chip is _far_ better.

yep.

Scott