Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Fast Fourier Transform

Tags:

c++

c

signal-processing

fft

dft

I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I need code which is not too long and can be very easily used and compiled in a single .c/.cpp file.

  1. FFT should be optimized for real inputs at least if not small integers.
  2. Radix 4 implementation if available would be fine too.
  3. Compiling it should take no special compilation flags as compilation of program has to be done in external environment which I can't control.

One that very well matches my needs is here. But I need something twice as fast.

like image 308
Nikhil Garg Avatar asked Mar 10 '11 04:03

Nikhil Garg

People also ask

What is Fast Fourier Transform?

As the name implies, the Fast Fourier Transform (FFT) is an algorithm that determines Discrete Fourier Transform of an input significantly faster than computing it directly. In computer science lingo, the FFT reduces the number of computations needed for a problem of size N from O(N^2) to O(NlogN) .

Why is FFT used?

The FFT algorithm is used to convert a digital signal (x) with length (N) from the time domain into a signal in the frequency domain (X), since the amplitude of vibration is recorded on the basis of its evolution versus the frequency at that the signal appears [40].

What does an FFT tell you?

The output of the FFT is a complex vector containing information about the frequency content of the signal. The magnitude tells you the strength of the frequency components relative to other components. The phase tells you how all the frequency components align in time.

What is FFT and its advantages?

The fast Fourier transform (FFT) is a computationally efficient method of generating a Fourier transform. The main advantage of an FFT is speed, which it gets by decreasing the number of calculations needed to analyze a waveform.

2 Answers

For a straightforward and easy to use FFT implementation try KissFFT. If you need absolute maximum performance though, and don't mind a little complexity, then it has to be FFTW.

like image 174
Paul R Avatar answered Oct 01 '22 03:10

Paul R

I've adapted the smbFft function from this example on DspDimension to my needs in the past.

like image 23
LnxPrgr3 Avatar answered Oct 01 '22 04:10

LnxPrgr3
Sign in to Comment

Related questions

Does anyone know of a C/C++ Unix QR-Code library? [closed]
How to develop a DirectFB app without leaving X.11 environment
MAP file analysis - where's my code size comes from?
How to synchronize SVN revision and version ressources of EXE/DLL files?
Fast Cross-Platform C/C++ Hashing Library [closed]
How is STL iterator equality established?
boost exceptions
Passing an operator along with other parameters
What does boost::thread sleep() do?
Compiler error in declaring template friend class within a template class
C++ console keyboard events
How do I use the C preprocessor to make a substitution with an environment variable
C++ library to load Excel (.xls) files [closed]
Do boost::shared_ptr<T> and boost::shared_ptr<const T> share the reference count?
When is VTable in C++ created?
What is the best way to display an animated icon in a QTableView?
Bit twiddling for checking whether a number is in particular range
Is there memory area called 'stack' in C++ to store automatic variables
Can I use a lambda function or std::function object in place of a function pointer?
`*this = rhs` in Java?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!