FFT in FPGA?
FFT in FPGA?
(OP)
This was 1st posted under the PLC forum.
I just had a request yesterday. If I would be able to create a small, say 4, 12 bit inputs, FFT in a FPGA ?
We use the Altera Cyclone series, and Altera does have a MegaCore FFT, which, however, starts at 64 inputs and uses way too many resources in the Cyclone. A posting to Altera's support has revealed, that the function can not be scaled down.
In other words, I have to create something myself.
Does anybody know where to find an algorithm, that can be implemmented without using a DSP core or similar?
I do have a Pascal module (with source!) I can try to figure out, but if it is of any use for hardware is unknown.
I just had a request yesterday. If I would be able to create a small, say 4, 12 bit inputs, FFT in a FPGA ?
We use the Altera Cyclone series, and Altera does have a MegaCore FFT, which, however, starts at 64 inputs and uses way too many resources in the Cyclone. A posting to Altera's support has revealed, that the function can not be scaled down.
In other words, I have to create something myself.
Does anybody know where to find an algorithm, that can be implemmented without using a DSP core or similar?
I do have a Pascal module (with source!) I can try to figure out, but if it is of any use for hardware is unknown.





RE: FFT in FPGA?
TTFN
RE: FFT in FPGA?
I was told that cohenrently adding the complex results of the FFT would give a much better result than just doing it with the 4 raw I/Q samples.
A little too much math for me here and now, but the guy has proved VERY competent before. And his MatLab simulations did show a significant improvement.
How it might work, when everything is limited to 12 bit resolution integers instead of 64 bit double precision floating point, that is another story.
RE: FFT in FPGA?
TTFN
RE: FFT in FPGA?
As I have mentioned, some of the math is a little above me at the moment, but I will try to describe what we are doing.
We have a scientific radar, where each range channel is being recorded at 400 ks/s. I and Q.
Up until now we have integrated over a minimum of four samples by summing I and Q values and transmit the resulting integrated I and Q. The next resulting sample contains the sum of the following 4 input samples, but no pre-history. Integrate & Dump, as we call it.
We could simply sample at 100 kHz and be done with it, but with this we are more flexible with the resulting sample rate. We also gain some in signal / noise.
Now, on aircraft I believe it mainly was, it would give better results if we first did a small FFT and then integrated over the results of that.
As I can recall from the simulations: With the old method we loose up to 10 dB in the integrated signal at certain Dopplers, where as the new should give a loss well below 1 dB. That with a 4 point FFT. Better still with a longer one.
RE: FFT in FPGA?
This filtering in the FFT domain sounds difficult with so few points.
RE: FFT in FPGA?
http://www.dspguide.com/
I have similar doubts as do other responders. For noise reduction, you might consider a Savitzky-Golay Filter. This filter does a Least Squares Polynomial Fit to data samples and is implemented as a FIR filter structure. See
ht
RE: FFT in FPGA?
And we have to do some limited filtering on the input samples, because the next set will come from the same hardware channel, but the RF source may have changed. (Frequency, polarization, range or even monopulse)
It is of course known how many samples that will be received in each set and for each RF source.
The described Integrate & Dump is performed in our FPGA, and reduces the amount of data to transfer to the PC. 100 ks/s is just about what we can handle. (Each burst contains 35 32 bit words.)
RE: FFT in FPGA?
Are we missing something here?
RE: FFT in FPGA?
"Forget that. It will only have minor influence on what we are going to do."
I have now partwise constructed (paper drawing only!) the 4 input butterfly diagram that is the main part of the FFT.
If I am correct, the 0 output bin (DC ?) ends up with exactly the average of the 4 inputs, which does not sound too surprising to me.
This at least implies that some of the information we up until now have lost during the Integrate & Dump can be reclaimed.
The intention as decribed earlier is to sum the four I's and the four Q's on the output and use that I/Q set further on in the process.
Still, the math behind all this is a little bit on the hairy side to me, so I may be wrong.
RE: FFT in FPGA?
As for averaging, neither frequency nor time domain samples should be added together willy-nilly. Registration prior to averaging must be investigated, particularly if you have no other synchronization.
TTFN
RE: FFT in FPGA?
Of course you'll want to process with more bits internally to avoid truncating the information away, but using 12-bit limited input data would be critical to the sim.
One general rule of thumb seems to be that when the volume of processing vastly exceeds the volume of input data, be very suspicious that somebody is fooling themselves. We've all met the math long-hairs that want to process a binary '1' to see if they can extract any further information...
I still don't see how many different frequencies you think can be hidden inside four samples... This is where simulating in math (without condering the actual bits) can be very misleading.
Given the number of high-performance systems (SW radios, modems) that are recently starting to use the sea-of-gates FPGAs (instead of DSPs) to perform signal processing, there must be SW tools available to translate from one domain (DSP) into the other (FPGA). No way people are doing that by hand.
RE: FFT in FPGA?
http://www.opencores.org/
RE: FFT in FPGA?
http://www.dspguide.com/ch15.htm
RE: FFT in FPGA?
I have now tried to simulate a 4 point DFT in Exel, and summing after that actually does give a better power response than what we are used to. All 0.02 dB of it
That with a very slow moving input. I will try something faster tomorrow.
But unless I am wrong, it can be implemmented without any multipier. Sums and differences only! With only 4 points the sine and cosine factors must of course be -1, 0 or 1.
I guess that will reduce the number of cells I need in the FPGA.
I have seen a page on the web, which used two four point converters (plus some adding and multiplication) to create an eight point converter.
Eight or 16 points will of course with optional zero padding give us a much more flexible system.
And the moving average stuff?
I am familiar with the general algorithm, but I am not sure we can use it.
In order to get the best corrolation we must integrate over an entire code length, which is very close to 20 samples.
So I guess we need all the data on equal terms.
RE: FFT in FPGA?
Rounding error... ?
RE: FFT in FPGA?
My sine and cosine input had a period of 100 samples.
If I went to a 15 times higher frequency (6 2/3 sample per period) the difference was 5 dB.
And of course, if if my period matched my 4 point DFT the integration gave out zero.
The power on the frequency side, however, stayed exactly at 16, as always.