Forum Menu




 


Log in Problems?
New User? Sign Up!
AVR Freaks Forum Index

Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Author Message
binary
PostPosted: Aug 30, 2010 - 11:03 AM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

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
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
leon_heller
PostPosted: Aug 30, 2010 - 12:01 PM
Raving lunatic


Joined: Jul 27, 2001
Posts: 7609
Location: St. Leonards-on-Sea (UK)

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
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
binary
PostPosted: Aug 30, 2010 - 12:31 PM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

Floating point
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
binary
PostPosted: Aug 30, 2010 - 12:34 PM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

Thanks Leon!

Well, I was also throwing an eye on FPGAs.
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
gchapman
PostPosted: Aug 30, 2010 - 08:06 PM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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
 
 View user's profile Send private message  
Reply with quote Back to top
bobgardner
PostPosted: Aug 31, 2010 - 01:52 AM
10k+ Postman


Joined: Sep 04, 2002
Posts: 24109
Location: Orlando Florida

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.

_________________
I ain't nobody's uncle, so don't call me that.
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
binary
PostPosted: Aug 31, 2010 - 08:02 AM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

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.
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
leon_heller
PostPosted: Aug 31, 2010 - 10:01 AM
Raving lunatic


Joined: Jul 27, 2001
Posts: 7609
Location: St. Leonards-on-Sea (UK)

What is the application?

_________________
Leon Heller
G1HSM
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
gchapman
PostPosted: Aug 31, 2010 - 07:09 PM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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.
 
 View user's profile Send private message  
Reply with quote Back to top
leon_heller
PostPosted: Aug 31, 2010 - 07:45 PM
Raving lunatic


Joined: Jul 27, 2001
Posts: 7609
Location: St. Leonards-on-Sea (UK)

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

_________________
Leon Heller
G1HSM
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
bobgardner
PostPosted: Sep 01, 2010 - 02:48 AM
10k+ Postman


Joined: Sep 04, 2002
Posts: 24109
Location: Orlando Florida

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?

_________________
I ain't nobody's uncle, so don't call me that.
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
gchapman
PostPosted: Sep 01, 2010 - 04:11 AM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

http://gsoc2010-fftw-neon.blogspot.com/2010/08/final-benchmarks.html
My first look at "bench-1d-pot" for 512 is 26us. Am I mistaken?
The project:
http://elinux.org/BeagleBoard/GSoC/2010_Projects/FFTW#Documentation
 
 View user's profile Send private message  
Reply with quote Back to top
leon_heller
PostPosted: Sep 01, 2010 - 10:47 AM
Raving lunatic


Joined: Jul 27, 2001
Posts: 7609
Location: St. Leonards-on-Sea (UK)

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
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
cpluscon
PostPosted: Sep 01, 2010 - 05:32 PM
Raving lunatic


Joined: Jul 10, 2006
Posts: 2690
Location: Minneapolis

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.
 
 View user's profile Send private message  
Reply with quote Back to top
leon_heller
PostPosted: Sep 01, 2010 - 06:04 PM
Raving lunatic


Joined: Jul 27, 2001
Posts: 7609
Location: St. Leonards-on-Sea (UK)

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

_________________
Leon Heller
G1HSM
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
binary
PostPosted: Sep 01, 2010 - 07:36 PM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

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.
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
gchapman
PostPosted: Sep 01, 2010 - 08:27 PM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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.
 
 View user's profile Send private message  
Reply with quote Back to top
bobgardner
PostPosted: Sep 01, 2010 - 08:58 PM
10k+ Postman


Joined: Sep 04, 2002
Posts: 24109
Location: Orlando Florida

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?

_________________
I ain't nobody's uncle, so don't call me that.
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
binary
PostPosted: Sep 01, 2010 - 11:38 PM
Wannabe


Joined: Dec 14, 2005
Posts: 96
Location: Latvia

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.
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
gchapman
PostPosted: Sep 01, 2010 - 11:43 PM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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.
 
 View user's profile Send private message  
Reply with quote Back to top
gchapman
PostPosted: Sep 02, 2010 - 12:04 AM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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.


Last edited by gchapman on Sep 02, 2010 - 01:27 AM; edited 1 time in total
 
 View user's profile Send private message  
Reply with quote Back to top
gchapman
PostPosted: Sep 02, 2010 - 12:15 AM
Raving lunatic


Joined: Jan 09, 2007
Posts: 2852
Location: Arlington, Texas, u.S.A.

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.
 
 View user's profile Send private message  
Reply with quote Back to top
Display posts from previous:     
Jump to:  
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Powered by PNphpBB2 © 2003-2006 The PNphpBB Group
Credits