The FFT result output, implemented in a FPGA, is a complex number with 16-bit real part and 16-bit imaginary part. In the application, I only care about the FFT result magnitude, Mag = sqrt(Re*Re+Im*Im).So I wonder if there is an approximate estimation about this operation. and even more, the decibel algorithm. I think the decibel algorithm can be easily implemented by a looking-up-table scheme, but I still have no idea about simple complex magnitude algorithm. I appreciate your suggestions. Sun Lei.
Is there a complex magnitude approximation algorithm?
Started by ●January 7, 2007
Reply by ●January 7, 20072007-01-07
On Jan 7, 12:58 pm, "SunLei" <iamsun...@gmail.com> wrote:> The FFT result output, implemented in a FPGA, is a complex number with > 16-bit real part and 16-bit imaginary part. In the application, I only care > about the FFT result magnitude, Mag = sqrt(Re*Re+Im*Im).So I wonder if there > is an approximate estimation about this operation. and even more, the > decibel algorithm. I think the decibel algorithm can be easily implemented > by a looking-up-table scheme, but I still have no idea about simple complex > magnitude algorithm. I appreciate your suggestions. > > Sun Lei.Well I suppose you could simply create a look up table based on the function sqrt(x * x + y * y) and look it up using the real and imaginary values as coordinates.
Reply by ●January 7, 20072007-01-07
If you can tolerate a peak error of 1db - Take absolute value of largest axis and add 1/2 absolute value of smallest axis. This can be achieved numerically using only shifts, complements, and adds. I think Rick Lyons has a more accurate algorithm in his book, but I don't have it to hand at the moment to refer. Jeff
Reply by ●January 7, 20072007-01-07
Jeff Caunter wrote:> If you can tolerate a peak error of 1db - > > Take absolute value of largest axis and add 1/2 absolute value of smallest > axis. > > This can be achieved numerically using only shifts, complements, and > adds. > > I think Rick Lyons has a more accurate algorithm in his book, but I don't > have it to hand at the moment to refer. > > JeffYou can find all of the gory details here: http://groups.google.com/group/comp.dsp/browse_frm/thread/981e0ff3e58e078c/e55848cb1cce09a5?lnk=st&q=%2Bclay+%2Bturner+%2Bmagnitude+%2Bgrant+%2Bdsp&rnum=1&hl=en#e55848cb1cce09a5 Clay
Reply by ●January 7, 20072007-01-07
Jeff Caunter wrote:> If you can tolerate a peak error of 1db - > > Take absolute value of largest axis and add 1/2 absolute value of smallest > axis.Actually, taking the 1/4 of the smallest is a little bit more accurate. And (1/4 + 1/16) is even better then that. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●January 7, 20072007-01-07
> > >Jeff Caunter wrote: > >> If you can tolerate a peak error of 1db - >> >> Take absolute value of largest axis and add 1/2 absolute value ofsmallest>> axis. > >Actually, taking the 1/4 of the smallest is a little bit more accurate. >And (1/4 + 1/16) is even better then that. > >Vladimir Vassilevsky > >DSP and Mixed Signal Design Consultant > >http://www.abvolt.com >
Reply by ●January 7, 20072007-01-07
> > >Jeff Caunter wrote: > >> If you can tolerate a peak error of 1db - >> >> Take absolute value of largest axis and add 1/2 absolute value ofsmallest>> axis. > >Actually, taking the 1/4 of the smallest is a little bit more accurate. >And (1/4 + 1/16) is even better then that. > >Vladimir Vassilevsky > >DSP and Mixed Signal Design Consultant > >http://www.abvolt.com >Are you sure about that? I have always used 1/2 as a good compromise. I have just spreadsheeted this, and it seems 0.44375 would be near the ideal factor to use (variation 0.6dB) Using 1/4 I get 1.34dB, and 1/2 I get 0.77dB. These are the variations over PI/4, which are, of course, replicated over the 2PI range. Am I missing something? Jeff
Reply by ●January 7, 20072007-01-07
Jeff Caunter wrote:> Are you sure about that? I have always used 1/2 as a good compromise. > > I have just spreadsheeted this, and it seems 0.44375 would be near the > ideal factor to use (variation 0.6dB) Using 1/4 I get 1.34dB, and 1/2 I > get 0.77dB. These are the variations over PI/4, which are, of course, > replicated over the 2PI range. > > Am I missing something? >Hello Jeff, I believe you missed the link I posted earlier. The following table shows a bunch of sets of coefs along with the RMS and peak errors. The following table is from Grant Griffin's program. See www.dspguru.com for details. I work out the 1st three sets of coefs from a theoretical basis. Alpha * Min + Beta * Max Magnitude Estimator Name Alpha Beta Avg Err RMS Peak (linear) (dB) (dB) --------------------------------------------------------------------- Min RMS Err 0.947543636291 0.392485425092 0.000547 -32.6 -25.6 Min Peak Err 0.960433870103 0.397824734759 -0.013049 -31.4 -28.1 Min RMS w/ Avg=0 0.948059448969 0.392699081699 0.000003 -32.6 -25.7 1, Min RMS Err 1.000000000000 0.323260990000 -0.020865 -28.7 -23.8 1, Min Peak Err 1.000000000000 0.335982538000 -0.025609 -28.3 -25.1 1, 1/2 1.000000000000 0.500000000000 -0.086775 -20.7 -18.6 1, 1/4 1.000000000000 0.250000000000 0.006456 -27.6 -18.7 Frerking 1.000000000000 0.400000000000 -0.049482 -25.1 -22.3 1, 11/32 1.000000000000 0.343750000000 -0.028505 -28.0 -24.8 1, 3/8 1.000000000000 0.375000000000 -0.040159 -26.4 -23.4 15/16, 15/32 0.937500000000 0.468750000000 -0.018851 -29.2 -24.1 15/16, 1/2 0.937500000000 0.500000000000 -0.030505 -26.9 -24.1 31/32, 11/32 0.968750000000 0.343750000000 -0.000371 -31.6 -22.9 31/32, 3/8 0.968750000000 0.375000000000 -0.012024 -31.4 -26.1 61/64, 3/8 0.953125000000 0.375000000000 0.002043 -32.5 -24.3 61/64, 13/32 0.953125000000 0.406250000000 -0.009611 -31.8 -26.6
Reply by ●January 7, 20072007-01-07
>Hello Jeff, >I believe you missed the link I posted earlier. The following table >shows a bunch of sets of coefs along with the RMS and peak errors. The >following table is from Grant Griffin's program. See www.dspguru.com >for details. I work out the 1st three sets of coefs from a theoretical >basis. > > Alpha * Min + Beta * Max Magnitude Estimator >Hi Clay, Yes, I am familiar with this, but it involves multiplications, which I tried to avoid. There are many instances where errors of < +/- 0.4dB are acceptable, and speed/simplicity is of the essence. That is when I use the simple algorithm I quoted. Jeff
Reply by ●January 7, 20072007-01-07
On Sun, 07 Jan 2007 13:28:12 -0600, "Jeff Caunter" <jeffcaunter@sparkysworld.co.uk> wrote:>> >> >>Jeff Caunter wrote: >> >>> If you can tolerate a peak error of 1db - >>> >>> Take absolute value of largest axis and add 1/2 absolute value of >smallest >>> axis. >> >>Actually, taking the 1/4 of the smallest is a little bit more accurate. >>And (1/4 + 1/16) is even better then that. >> >>Vladimir Vassilevsky >> >>DSP and Mixed Signal Design Consultant >> >>http://www.abvolt.com >> > >Are you sure about that? I have always used 1/2 as a good compromise. > >I have just spreadsheeted this, and it seems 0.44375 would be near the >ideal factor to use (variation 0.6dB) Using 1/4 I get 1.34dB, and 1/2 I >get 0.77dB. These are the variations over PI/4, which are, of course, >replicated over the 2PI range. > >Am I missing something? > >JeffHi Jeff of the two simple expressions: Mag1 = Max + Min/2 Mag2 = Max + Min/4 as far as I know they have very similar maximum errors (roughly 11-12% error). But Mag2 has a lower average error. What that means to me is that Mag2 yields a more correct result, most of the time, than Mag1. See Ya, [-Rick-]
