Weekend Prorgaming Challenge – Week #54 – FFT


Image

Problem:

Fourier Transform is basic instrument for spectrum analyze of signals. Make Fast Fourier Transform (FFT) implementation in your favourite language, try to compute the spectrum on sample sound file and to visualize it.

The rules:

You can code the solution in any programming language during the weekend and have to submit it to info@olimex.com latest on Sunday May 25th.

On Monday we will upload the solutions on GitHub https://github.com/OLIMEX/WPC

You can play with your real name or with nick if you want to be anonymous, we will not disclosure your personal info if you do not want to.

3 Comments (+add yours?)

  1. scout_3pm
    May 23, 2014 @ 17:35:43

    This is a big subject , there has not been great improvement on the FFT since a long time. Even at MIT try to make it faster http://newsoffice.mit.edu/2012/faster-fourier-transforms-0118, but they succeeded with some conditionality “when it will be faster”, not all cases, but if some conditions are met😉 So this challenge will be more of a coding practice, which is a good thing also. But for MCU/SoC cores the manufactures release optimized FFT versions. Example is the CMSIS dsp library for Cortex-M3/M4 for example🙂

    Reply

    • OLIMEX Ltd
      May 23, 2014 @ 17:45:27

      there are ton of implementations, as you write here is nothing new, everything is already done
      the intention with this challenge is not to expect that one would make faster fourier transform for one weekend, but just to see the solutions and to dip his toes in the water by re-using with some kind of visualization🙂

      Reply

    • Emiliano Daddario
      May 23, 2014 @ 22:39:05

      Yes, the MIT algorithm is the “sparse FFT”; for example there is the implementation on spiral.net which is optimized for modern hardware, but it only works either for signals without noise or for specific size/sparsity pairs (20 possible pairs in total).That said, the sparser the signal spectrum, the faster the sFFT. For signals with very sparse spectra there are great improvements.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: