Fast FFT calculations

Last post
22 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

I need fast 512 point Complex FFT calculations. I found two controllers capable of one FFT calculation in about 50us - ADSP by Analog Devices and C6000 by Texas Instruments. Howerver the price of development tools (JTAG + software) is too high - more than 1000$.

Could you recommend any other DSP or controller capable of FFT calculation in about 100us.

Thanks!

Janis

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You could implement it on a suitable FPGA:

http://www.xilinx.com/products/ipcenter/FFT.htm

You will have to buy the ISE (I don't think it is available with the free tools), but it should work out cheaper than having to buy the TI or ADI tools. It'll be faster, as well.

Leon Heller
G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Floating point

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks Leon!

Well, I was also throwing an eye on FPGAs.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Not quite what you want but how about 256-pt complex FFT:
http://opencores.org/project,pipelined_fft_256
with Actel's Libero:
http://www.actel.com/products/software/libero/default.aspx

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This does a 32 point fp fft in 60ms. In a mega128, it has enough ram for a 64 or 128 point fft, which takes 220ms.

Attachment(s): 

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks gchapman and bobgardner!

I will take a look, at those solutions.
But atmega is too slow for this solution. I have to do 10'000 512 point FFT calculations in less than a second.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What is the application?

Leon Heller
G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Would a Cortex-A8 on a BeagleBoard work?
CodeSourcery makes a Lite (open) GCC C/C++ for it.
The Cortex-M4 in 2011 may be a more embedded option.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm quite sure that neither will be able to do a 512-point floating-point FFT in 100 us.

Leon Heller
G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But tell us the problem and let us propose the fft range and resolution and speed required to solve it, and maybe propose a cpu?

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That could be an option. I didn't realise that the NEON extension has 64-bit registers and supports single-precision floating point.

Leon Heller
G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

FFTs don't NEED to be in floating point. I haven't done integer transforms but know people that have.

Also, if perchance you are only interested in a single frequency you can skip the FFT and implement the DFT inner loop, yielding O(n) calculation.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It depends on the dynamic range that is required. Some applications need floating-point.

Leon Heller
G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, I have to record 512 shot video(100x100) and do FFT calculations for each pixel.

I got a Xilinx Spartan 3AN development board from my work, so I'll give that a try. But it's a long way to get to FFT, because VHDL isn't as intuitive as c programming.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

binary wrote:
Well, I have to record 512 shot video(100x100) and do FFT calculations for each pixel.
What is the source of the video?
USB, pixel parallel, analog composite, etc.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What is a shot video? Do you mean 512 short videos? I guess you DONT mean 'an FFT of each pixel'. Maybe you mean a 2D FFT of each 100x100 frame? Are you looking for the brightest spot or some other image processing trick?

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
What is the source of the video?

The source of video is a CMOS camera module.

Quote:
What is a shot video? Do you mean 512 short videos? I guess you DONT mean 'an FFT of each pixel'. Maybe you mean a 2D FFT of each 100x100 frame? Are you looking for the brightest spot or some other image processing trick?

By 'shot' I meant 'frame'. Sorry for my english.
I think it'll be easier for me to explain the idea by an example.
I will get a 512 frame video with size of 100x100 pixels and store it in RAM. Than I'll take all first(0,0) pixels from each frame and do a FFT calculation. And so on for all the other pixels.
It's like FFT for audio, but here I have 10000 "channels".
I hope you got the idea.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
This does a 32 point fp fft in 60ms. In a mega128, it has enough ram for a 64 or 128 point fft, which takes 220ms.
A comparison though not quite apples-to-apples since its 32-bit fixed point:
UC3A0, 60 MHz: 64 points = 0.2ms, 256 points = 1.3ms.
Not optimized for UC3 (i.o.w. source code is all C instead of using assembly language).
References are application notes AVR32718 and AVR32765.
The AVR32 AP7 is probably very similar to AVR32 UC3 for arithmetic except much faster.
If use fixed-point, maybe reduce scope one notch, optimize, and port to AP7 (or fixed-point on a faster MCU) then Janis may have a solution.
Floating point does greatly reduce the solution space.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If fixed point, maybe an Atmel SAM9G20 would work. It is a 400 MHz ARM9, DRAM interface for frame buffers, USB host interface or image sensor interface for video input. Some boards from Atmel and third parties; a SAM9G45 pico-ITX board from mini-box.com is imminent.
Edit: corrected ITX board.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

binary wrote:
Quote:
What is the source of the video?

The source of video is a CMOS camera module.
What is the camera module's interface?
USB, parallel pixel, etc.