> On Sun, 7 Jan 2007 20:00:54 +0800, "SunLei" <iamsunlei@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.
>
>
> I don't know what precision you need, so the following may be totally
> unsuitable. But it's worth mentioning, if only as a history lesson.
>
> Back in the 70's, when life was cheap and digital hardware was
> expensive, I was designing parts of radar signal processors. Most of
> these things had an FFT in the front end, and at some point we had to
> produce a magnitude from I and Q. In those days a 12-by-16 multiplier
> took an entire circuit board of AMD 25S05 2-by-4 multipliers, which
> seemed kind of excessive for such a function.
>
> We got pretty good results by comparing the magnitudes of I and Q,
> then adding the larger plus half the smaller. The average result
> error is around 8.6 percent. There are variations on this theme that
> use different coefficients, i.e. alpha*|larger| + beta*|smaller|, and
> produce much lower average and peak errors. You can read more about
> this at:
>
> http://dspguru.com/comp.dsp/tricks/alg/mag_est.htm
>
> If you're using one of those new-fangled FPGAs with a zillion
> multipliers on it, this isn't the solution for you. Still, it's
> interesting how much performance designers used to squeeze out of not
> all that much logic. And coffee was only a quarter. And the music
> was better. I could go on.
>
> Bob Perlman
> Cambrian Design Works
> http://www.cambriandesign.com
And if you are using dB output only, the larger plus half smaller yields
a max error of less than 1 dB, so if you don't have the luxury of
multipliers at a reasonable cost, a dB output using larger plus half
smaller is very workable in many situations.
My experience is similar to Bob's regarding radar systems. In a former
job, we frequently used larger plus half smaller and a simple look-up to
get dB output, also in radar systems dating from the mid 70's, when DSP
was done with boards full of TTL devices, high speed meant clocks as
high as *gasp* 12 MHz (and that was a significant feat while meeting the
mil environment specs). Debug was done with an oscilloscope and if you
were real lucky you got access to a storage scope. Still, the stuff we
do today is cooler, but it also doesn't require as much magic to pull it
off.
Reply by Bob Perlman●January 8, 20072007-01-08
On Sun, 7 Jan 2007 20:00:54 +0800, "SunLei" <iamsunlei@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.
I don't know what precision you need, so the following may be totally
unsuitable. But it's worth mentioning, if only as a history lesson.
Back in the 70's, when life was cheap and digital hardware was
expensive, I was designing parts of radar signal processors. Most of
these things had an FFT in the front end, and at some point we had to
produce a magnitude from I and Q. In those days a 12-by-16 multiplier
took an entire circuit board of AMD 25S05 2-by-4 multipliers, which
seemed kind of excessive for such a function.
We got pretty good results by comparing the magnitudes of I and Q,
then adding the larger plus half the smaller. The average result
error is around 8.6 percent. There are variations on this theme that
use different coefficients, i.e. alpha*|larger| + beta*|smaller|, and
produce much lower average and peak errors. You can read more about
this at:
http://dspguru.com/comp.dsp/tricks/alg/mag_est.htm
If you're using one of those new-fangled FPGAs with a zillion
multipliers on it, this isn't the solution for you. Still, it's
interesting how much performance designers used to squeeze out of not
all that much logic. And coffee was only a quarter. And the music
was better. I could go on.
Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com
Reply by ●January 8, 20072007-01-08
If you're just using the magnitude to compare to some constant
threshold or something like that, then you can just square the number
you are comparing to and avoid the sqrt in logic.
SunLei 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.
Reply by SunLei●January 8, 20072007-01-08
Thank you. yes , iam with your algorithm.
"Ray Andraka" <ray@andraka.com> ??????:hwgoh.23481$Dy2.116@newsfe20.lga...
> SunLei 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.
>>
>>
>>
>>
>
> If you are only interested in the result expressed in dB, then you don't
> need the square root:
>
> dB = 20*log(mag) = 20*log(sqrt(I^2+Q^2)) = 10*log(I^2+Q^2)
>
> If about 1/4 dB is sufficient precision, then you can use the quick and
> dirty log I posted to dsp-guru many years ago. To do that, left shift
> the sum I^2+Q^2 until you eliminate the leading zero bits, counting the
> bit positions shifted. Each bit shift corresponds to 6dB (3dB after
> taking into account the square root). Then ignore the MSB (that will
> always be '1' after shifting), and feed the next 4 most significant bits
> into a 4 input look-up table containing 10*logs of 1.0 to 1-15/16 in 1/16
> increments. The output of that table gets added to the shift log to get
> your total value.
Reply by Ray Andraka●January 7, 20072007-01-07
SunLei 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.
>
>
>
>
If you are only interested in the result expressed in dB, then you don't
need the square root:
dB = 20*log(mag) = 20*log(sqrt(I^2+Q^2)) = 10*log(I^2+Q^2)
If about 1/4 dB is sufficient precision, then you can use the quick and
dirty log I posted to dsp-guru many years ago. To do that, left shift
the sum I^2+Q^2 until you eliminate the leading zero bits, counting the
bit positions shifted. Each bit shift corresponds to 6dB (3dB after
taking into account the square root). Then ignore the MSB (that will
always be '1' after shifting), and feed the next 4 most significant bits
into a 4 input look-up table containing 10*logs of 1.0 to 1-15/16 in
1/16 increments. The output of that table gets added to the shift log
to get your total value.
Reply by cpope●January 7, 20072007-01-07
"SunLei" <iamsunlei@gmail.com> wrote in message
news:enqq36$voc$1@news.cn99.com...
> 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.
>
>
>
>
I assume the data is serialized going into your FFT block (i.e. comes from
one ADC), so it should be a simple matter to serialize the bins coming out
of your FFT. All you need then is a cordic coregen function (which is tiny
compared to an FFT block so you'll have the space) and then a BRAM look up
table to convert from magnitude to dB.
Unless you serialize the cordic I think you need 1 stage per output bit so I
would expect 16 stages times 32 registers = 512 registers (256 slices) and
then 2^16*8 bits magnitude (about .5 dB accuracy) or 512 kbits memory.
Though there is probably a more efficient way to calculate the log10. Maybe
take the log2 by converting to floating point and then just use LUT on the
mantissa and scaling.
-Clark
Reply by Jonathan Bromley●January 7, 20072007-01-07
On Sun, 7 Jan 2007 20:00:54 +0800, "SunLei"
<iamsunlei@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.
There are many possibilities, but to narrow down the choice
we need to know more about your specification.
What accuracy do you need?
How much time do you have available to process each result? The
complex FFT takes some time to process, so presumably you have
some time to get the result? CORDIC may be a good solution;
it gives nice accuracy with small hardware, but it needs either
many clock cycles to do the calculation, or bigger hardware
so that the calculation is pipelined.
Tell us more.
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
You are right that conversion from magnitude to dB can be done
using a lookup table, or a combination of LUT and interpolation,
or by using normalisation as a first step.
Reply by SunLei●January 7, 20072007-01-07
I am using a Xilinx one.
There is a IP core in the ISE envirement, but it cost too resources and
running time.
Regards,
Sun Lei
"Peppermint Pumpkin" <pepperpump@make.a.mint> д����Ϣ����:45a0e342$0$8715$ed2619ec@ptn-nntp-reader02.plus.net...
>
> "SunLei" <iamsunlei@gmail.com> wrote in message
> news:enqq36$voc$1@news.cn99.com...
>> 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.
>>
>
> If you are using an Altera part, code it exactly the same. There are both
> SQR and SQRT megafunctions which can be pipelined and get extremely high
> throughput at 16 bits resolution.
>
> Using schematics the algorithm is trivial, don't know about VHDL/Verilog
> implementation though.
>
> Lorne
>
Reply by Peppermint Pumpkin●January 7, 20072007-01-07
"SunLei" <iamsunlei@gmail.com> wrote in message
news:enqq36$voc$1@news.cn99.com...
> 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.
>
If you are using an Altera part, code it exactly the same. There are both
SQR and SQRT megafunctions which can be pipelined and get extremely high
throughput at 16 bits resolution.
Using schematics the algorithm is trivial, don't know about VHDL/Verilog
implementation though.
Lorne
Reply by SunLei●January 7, 20072007-01-07
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.