Reply by Jerry Avins September 12, 20082008-09-12
John wrote:
> On Sep 12, 2:42 am, ste...@coppice.org wrote: >> On Sep 12, 4:59 am, Jerry Avins <j...@ieee.org> wrote: >> >> >> >>> John wrote: >>>> On Sep 3, 4:18 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> >>>> wrote: >>>>> Thomas Magma wrote: >>>>>> Hello, >>>>>> I'm trying to write a very efficient and fast detection algorithm for a >>>>>> dsPIC. >>>>> To detect what? >>>>>> I've already been down the path of the Goertzel and have dismissed it >>>>>> because of it's use of floating point numbers. >>>>> Goertzel can be done in the integer math. >>>>>> I am now using a modified DFT >>>>> There is no point. With dsPIC, Goertzel is more efficient then I/Q >>>>> accumulation. >>>>>> and would like to get rid of the square root algorithm that calculates the >>>>>> magnitude of I & Q. >>>>> sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) >>>>> The error is less then 10% >>>> I think you mean either >>1 or /2, no? >>> Either way. 3/8 is a bit better. Seehttp://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm >> That's considerably better than 1/2 or 1/4, but requires an extra add. >> I remember when that involved numerous extra chips, and we deeply >> debated whether we could live with the reduced precision. One guy >> treated "greater plus three eighths of the lesser" as a mantra. Times >> change. :-) >> >> For most purposes using 1/2 or 1/4 gives comparable results. The >> errors nudge in different directions, so one or other sometimes works >> out better in specific applications. >> >> Regards, >> Steve > > Suppose I want the time-average magnitude of a vector. Is it better to > average |I| and |Q| and then apply the approximation, or average the > approximation?
Whether the magnitudes are calculated exactly or approximated, average the magnitudes. Average magnitude and the magnitude of average I and Q can be very different. Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
Reply by Jerry Avins September 12, 20082008-09-12
steveu@coppice.org wrote:
> On Sep 12, 4:59 am, Jerry Avins <j...@ieee.org> wrote: >> John wrote: >>> On Sep 3, 4:18 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> >>> wrote: >>>> Thomas Magma wrote: >>>>> Hello, >>>>> I'm trying to write a very efficient and fast detection algorithm for a >>>>> dsPIC. >>>> To detect what? >>>>> I've already been down the path of the Goertzel and have dismissed it >>>>> because of it's use of floating point numbers. >>>> Goertzel can be done in the integer math. >>>>> I am now using a modified DFT >>>> There is no point. With dsPIC, Goertzel is more efficient then I/Q >>>> accumulation. >>>>> and would like to get rid of the square root algorithm that calculates the >>>>> magnitude of I & Q. >>>> sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) >>>> The error is less then 10% >>> I think you mean either >>1 or /2, no? >> Either way. 3/8 is a bit better. Seehttp://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm > > That's considerably better than 1/2 or 1/4, but requires an extra add. > I remember when that involved numerous extra chips, and we deeply > debated whether we could live with the reduced precision. One guy > treated "greater plus three eighths of the lesser" as a mantra. Times > change. :-) > > For most purposes using 1/2 or 1/4 gives comparable results. The > errors nudge in different directions, so one or other sometimes works > out better in specific applications.
The page I cited was written by Grant Griffin who did a thorough analysis of various proposed approximations, including the traditional ones. Clay Turner had his oar in. MAX*61/64 + MIN*3/8 has an average error just over 2%. For machines that can multiply by arbitrary constants, .947543636291*MAX + .392485425092*MIN, with an average error of only .055%, is better yet. Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
Reply by John September 12, 20082008-09-12
On Sep 12, 2:42&#2013266080;am, ste...@coppice.org wrote:
> On Sep 12, 4:59&#2013266080;am, Jerry Avins <j...@ieee.org> wrote: > > > > > John wrote: > > > On Sep 3, 4:18 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> > > > wrote: > > >> Thomas Magma wrote: > > >>> Hello, > > >>> I'm trying to write a very efficient and fast detection algorithm for a > > >>> dsPIC. > > >> To detect what? > > > >>> I've already been down the path of the Goertzel and have dismissed it > > >>> because of it's use of floating point numbers. > > >> Goertzel can be done in the integer math. > > > >>> I am now using a modified DFT > > >> There is no point. With dsPIC, Goertzel is more efficient then I/Q > > >> accumulation. > > > >>> and would like to get rid of the square root algorithm that calculates the > > >>> magnitude of &#2013266080;I & Q. > > >> sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) > > >> The error is less then 10% > > > > I think you mean either >>1 or /2, no? > > > Either way. 3/8 is a bit better. Seehttp://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm > > That's considerably better than 1/2 or 1/4, but requires an extra add. > I remember when that involved numerous extra chips, and we deeply > debated whether we could live with the reduced precision. One guy > treated "greater plus three eighths of the lesser" as a mantra. Times > change. :-) > > For most purposes using 1/2 or 1/4 gives comparable results. The > errors nudge in different directions, so one or other sometimes works > out better in specific applications. > > Regards, > Steve
Suppose I want the time-average magnitude of a vector. Is it better to average |I| and |Q| and then apply the approximation, or average the approximation? Thanks, John
Reply by September 12, 20082008-09-12
On Sep 12, 4:59&#2013266080;am, Jerry Avins <j...@ieee.org> wrote:
> John wrote: > > On Sep 3, 4:18 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> > > wrote: > >> Thomas Magma wrote: > >>> Hello, > >>> I'm trying to write a very efficient and fast detection algorithm for a > >>> dsPIC. > >> To detect what? > > >>> I've already been down the path of the Goertzel and have dismissed it > >>> because of it's use of floating point numbers. > >> Goertzel can be done in the integer math. > > >>> I am now using a modified DFT > >> There is no point. With dsPIC, Goertzel is more efficient then I/Q > >> accumulation. > > >>> and would like to get rid of the square root algorithm that calculates the > >>> magnitude of &#2013266080;I & Q. > >> sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) > >> The error is less then 10% > > > I think you mean either >>1 or /2, no? > > Either way. 3/8 is a bit better. Seehttp://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm
That's considerably better than 1/2 or 1/4, but requires an extra add. I remember when that involved numerous extra chips, and we deeply debated whether we could live with the reduced precision. One guy treated "greater plus three eighths of the lesser" as a mantra. Times change. :-) For most purposes using 1/2 or 1/4 gives comparable results. The errors nudge in different directions, so one or other sometimes works out better in specific applications. Regards, Steve
Reply by Jerry Avins September 11, 20082008-09-11
John wrote:
> On Sep 3, 4:18 pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com> > wrote: >> Thomas Magma wrote: >>> Hello, >>> I'm trying to write a very efficient and fast detection algorithm for a >>> dsPIC. >> To detect what? >> >>> I've already been down the path of the Goertzel and have dismissed it >>> because of it's use of floating point numbers. >> Goertzel can be done in the integer math. >> >>> I am now using a modified DFT >> There is no point. With dsPIC, Goertzel is more efficient then I/Q >> accumulation. >> >>> and would like to get rid of the square root algorithm that calculates the >>> magnitude of I & Q. >> sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) >> The error is less then 10% >> > > I think you mean either >>1 or /2, no?
Either way. 3/8 is a bit better. See http://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
Reply by John September 11, 20082008-09-11
On Sep 3, 4:18&#2013266080;pm, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:
> Thomas Magma wrote: > > Hello, > > > I'm trying to write a very efficient and fast detection algorithm for a > > dsPIC. > > To detect what? > > > I've already been down the path of the Goertzel and have dismissed it > > because of it's use of floating point numbers. > > Goertzel can be done in the integer math. > > > I am now using a modified DFT > > There is no point. With dsPIC, Goertzel is more efficient then I/Q > accumulation. > > > and would like to get rid of the square root algorithm that calculates the > > magnitude of &#2013266080;I & Q. > > sqrt(I^2 + Q^2) ~ max(|I|,|Q|) + (min(|I|,|Q|) >> 2) > The error is less then 10% >
I think you mean either >>1 or /2, no?
Reply by September 11, 20082008-09-11
On Sep 4, 3:28&#2013266080;pm, c...@claysturner.com wrote:
> > > And actually a filter method involving a DSP was made compliant to > > > Bell specs. Bell Labs did an implementation modelled around a standard > > > central office line receiver during the early '80s. I have a copy of > > > their writeup from the Bell System Journel which describes in great > > > detail their actual application. > > > Can you please explain briefly what they did. > > > Vladimir Vassilevsky > > DSP and Mixed Signal Design Consultanthttp://www.abvolt.com > > Hello Vladimir, > > Recalling from memory as the article is at home (I haven't looked at > it for years), they really modelled the actual analog unit. First the > signal would have both a mains and dial tone notch filter to clean it > up. Then the signal was split into two branches where one goes through > a high band group and the other branch goes through a low band group. > The band filters would span either 4 row freqs or 4 column freqs > depending on which group we are talking about. Then the output of each > group filter would be split and go into four row(column) narrow band > pass filters ( I seem to recall they were 4th order each - lower Q - > faster transient response). > > Then each filter's ouput would be rectified and passed into a fast > attack slow release circuit akin to a simple AGC. These filtered > results would then go to some comparators for thresholding and then > the band results were compared for twist analysis. > > If I think about it when I get back to the farm, I'll find the paper > and give you more details. > > Clay
Hello Vladimir et al, The paper is "Receiver for TOUCH-TONE Service" by J. R. Boddie, N. Sachs, and J. Tow., The Bell System System Technical Journal, Vol. 60, No. 7, September 1981. The modelled a central office grade receiver - an "H" type. And then they put the design into a single chip. Tests on the design confirmed its equivalency to the actual office receiver. Even though the publishing date is Sept. 1981, the manuscript was received on July 2, 1980! Clay
Reply by lang...@fonz.dk September 5, 20082008-09-05
On 4 Sep., 06:37, Eric Jacobsen <eric.jacob...@ieee.org> wrote:
> On Wed, 03 Sep 2008 22:48:07 -0400, Jerry Avins <j...@ieee.org> wrote: > >langw...@fonz.dk wrote: > > > ... > > >> -Lasse > > >You've been gone a long time. Nice to hear from you! > > >Jerry > > I was thinking the same. Hiya, Lasse! >
Hi guys, dont worry I hang out in the neighborhood :) -Lasse
Reply by September 4, 20082008-09-04
On Sep 5, 12:49&#2013266080;am, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:
> c...@claysturner.com wrote: > > On Sep 4, 11:20 am, Vladimir Vassilevsky <antispam_bo...@hotmail.com> > > wrote: > > >>DTMF is intended to be decoded by > >>the frequency counters; filter methods, although working well, will > >>never be formally compliant to the standard. > > IIRC the receiver must reject the signals which are more then 3.5Hz away > from the standard frequences. With the 40ms duration of the tones, any > method which uses just the frequency filters is prone to 1/T uncertainty.
The DTMF spec varies a bit with the country, but the Bell, ITU and most other specs say you must detect when the frequency is within 1.5% of the target and reject when its more then 3.5% from the target. Maybe you confused 3.5% and 3.5Hz. There is no problem whatsoever meeting the ITU spec by a variety of methods, including Goertzel, LPC and others. The biggest differentiator tends to be how well they perform in talkoff tests.
> An unusual way to make a DTMF decoder was demonstrated here: > > "A Low-Complexity ITU-Compliant Dual Tone Multiple Frequency Detector" > Amey A. Deosthali, Shawn R. McCaslin, Brian L. Evans > > They used the counters and the adaptive notch filters; that allowed to > put the formally compliant decoder into 4 MIPS of PIC16.
That one looks interesting from a quick glance. I keep aiming to find the time to look in more detail at what they did.
> > Well there were two reasons I did it this way. First the standard > > doesn't apply to a two hop scenario and back at that time the lines > > were for certain to be analog, so there was extra twist and observed > > dynamic range. But also the DTMF spec assumes a quiet channel except > > for the tones themselves. But many applications involving DTMF such as > > with voice response systems have to go beyond the spec to work with > > interference. Often an "early detect" is employed to shutdown the > > outbound audio and/or a good echo canceller/ 2wire to 4 wire hybrid is > > used to separate the paths. > > I certainly agree with your reasoning, as I know that the filter based > decoders work very well in practice. However the formal compliance is > good to have.
Format compliance is trivial to achieve. Making it work well in the real world is where it gets tougher. :-)
> > And actually a filter method involving a DSP was made compliant to > > Bell specs. Bell Labs did an implementation modelled around a standard > > central office line receiver during the early '80s. I have a copy of > > their writeup from the Bell System Journel which describes in great > > detail their actual application. > > Can you please explain briefly what they did. > > > The other reason I did it that way, was I was replacing a $200 module > > that did just tone decoding of MFC-R2. My solution was quite a bit > > less expensive and was accepted by Bell and others. > > In 80-x, we build the R1.5 decoder using the set of the analog filters. > It wasn't very trivial to get the desired Q and stability. A digital > solution seemed to be too complex, expensive and impractical :-)
The 80s is a long period. At the start of the 80s a DSP R1, R1.5 or R2 detector would have been expensive with off the shelf devices, like the NEC or TI DSPs appearing at that time. People did this in the late 70s at very low cost and power using custom bit serial DSP silicon, though. When I used off the shelf DSP processors in about 1986/87 to do DTMF, R1, and R2, 2280Hz and 2600Hz generation and detection for a whole E1, the cost per channel was less than a DTMF receiver chip like the popular 8870s. When testing the 2280Hz and 2600Hz stuff against existing analogue implementations I couldn't find a single analogue implementation which actually complied fully with the specs. I don't know any way in which my implementation failed, it was naturally more stable over time, and it was more robust in talk off tests. Considering the behaviour of some 2600Hz kit, it isn't surprising that blue boxing was so popular. :-)
> >>>Analog > >>>Devices put out a pair of books that were full of appnotes (including > >>>a Goertzel) in fixed point arithmetic. > > >>Those two books have many bugs in the code and misprints in the formulae > >>(deliberately?). The books give a good explanation of how the things > >>could be done; however those who look for the canned solutions will be > >>disappointed.
Those books are particularly bad. Few app notes actually work, or have much consistency between the text the diagrams and the supplied code, but Analog's early DSP material gave little more than vague clues about what might be achieved. I suspect they were put together in parallel with the silicon development, and were not shaken out when real silicon was available.
> > > I never programmed an Analog Devices CPU, I've always used Mots and > > TIs. > > I have used ADIs and TIs, now looking toward Mots. IMO the ADI CPUs are > more logical and the common sense based, and the tools and documens are > more friendly then from the other vendors. That makes them very > attractive at the beginning. > > > But I know that TI have an appnote that was quite good which I > > used as a starting point. Even though the AD books contain typos, I > > think a salient engineer can figure those out. I thought the books > > brought fourth a lot of good information.
They were full of good ideas, but in a very rough state. Regards, Steve
Reply by September 4, 20082008-09-04
> > And actually a filter method involving a DSP was made compliant to > > Bell specs. Bell Labs did an implementation modelled around a standard > > central office line receiver during the early '80s. I have a copy of > > their writeup from the Bell System Journel which describes in great > > detail their actual application. > > Can you please explain briefly what they did. > > Vladimir Vassilevsky > DSP and Mixed Signal Design Consultanthttp://www.abvolt.com
Hello Vladimir, Recalling from memory as the article is at home (I haven't looked at it for years), they really modelled the actual analog unit. First the signal would have both a mains and dial tone notch filter to clean it up. Then the signal was split into two branches where one goes through a high band group and the other branch goes through a low band group. The band filters would span either 4 row freqs or 4 column freqs depending on which group we are talking about. Then the output of each group filter would be split and go into four row(column) narrow band pass filters ( I seem to recall they were 4th order each - lower Q - faster transient response). Then each filter's ouput would be rectified and passed into a fast attack slow release circuit akin to a simple AGC. These filtered results would then go to some comparators for thresholding and then the band results were compared for twist analysis. If I think about it when I get back to the farm, I'll find the paper and give you more details. Clay