I am in desperate need of an IFFT (Inverse Fast Fourier Transform) algorithm. If anyone has any working source code, or better yet, a tutorial or mathematical explanation, I need to be able to take a bunch of sine/cosine waves and build a composite wave of samples, and have it run as quickly as possible. Thank you.
IFFT?
Cricket FFT has a fast implementation of the inverse as well. The difference between forward and inverse algorithm is very small; the only effective difference is the power applied to the input terms when integrating over them.
Wikipedia has a good summary on the theory.
Also, it is worth noting that DCT (discrete cosine transform) could be better suited for you, if your data is easily represented as a sum of cosines at fixed intervals.
Author
Is DCT the same as DFT but for only cosines and not sines? That would work for my purposes, but ideally I would like to be able to inject a random phase shift into each wave (just to eliminate anomalies where all waves line up in the composite wave). What I'm using is DFT, but I was under the impression that FFT applies to the discrete kind, doesn't it?
BTW I'm generally very good at math (especially calculus), but sometimes I find something that I just either have a hard time understanding (generally do to a poor explanation) or I just can barely find any information about it.
The thing is, I've found a little information here and there about how DFT actually works and I think I understand it for the most part (it's always easier for me if I can visualize it - hence my great ability with calculus, as well as geometry and statistics/probability) but when it gets into abstract stuff, I tend to sometimes have a problem.
But the algorithm becomes more complicated when using the fast version, so I thought maybe if I got some source code I could make sense of it, or at least get something working anyway. I had found some source code for FFT but for some reason I couldn't seem to get it to do quite what it was supposed to do, and when I tested it, I sometimes got very inaccurate results.
In any case, it didn't apply to inverse FFT, which is what I need the most, and it must be especially quick. So if anyone could possibly provide either source code or a link to it, or even pseudocode and an explanation or a link to a tutorial or anything, that would be great.
I already checked the Wikipedia pages before, but unless I missed something, it didn't tell me what I needed for IFFT at all (I don't think it even mentioned it specifically). I'll check the Cricket page but right now I need to take a break...
Edit: Also, is there any possible quick algorithm like this that doesn't require any restriction on the number of wave frequencies (like a power of 2)?
Inverse FFT is almost exactly the same algorithm as forward FFT.
Are you looking for an intuitive explaination of Fourier transform in general, or just the fast variety?
If the former, I recommend this video playlist.
Author
Well I don't have one of those machines but I'll give it a look, thanks. Ultimately I'd like to know how FFT (especially IFFT) works and how to implement it.
The videos I linked to explain (in my opinion) intuitively what Fourier transform (or analysis in the videos) and its inverse (or synthesis in the videos) are and how they are intimately related to each other.
For the derivation of the fast algorithm, consider the discrete Fourier transform operation as a vector * matrix product where the complex coefficients of the frequencies (and their phases) form a 2D matrix of complex numbers.
In said matrix, there exists symmetries, that can be eliminated as a pre-calculation step and the substitution coefficients stored into a lookup table. One example of such symmetry is the positive and negative real and imaginary sectors of the matrix, which are effectively just mirror images of each others, flipped about the real and imaginary axes.
By considering such symmetries and therefore eliminating redundant calculations, FFT is considerably faster than naïvely evaluating the whole DFT matrix. The relationship between FFT and IFFT still remains exactly the same as that between DFT and IDFT, so if you know what inverse DFT represents in relation to forward DFT, it is directly equivalent to inverse FFT in relation to forward FFT.
The Cricket FFT library uses the Cooley-Tukey algorithm to divide the FFT calculation into smaller steps via a Butterfly diagram. By dividing the calculation in such way, the total complexity is reduced. The full source code is included in the zip, and if you look at the calculation core you will notice that the only difference between forward and inverse is the power and sign of the coefficients used for the integration over the input.
I don't own one of those machines either but the videos are very well made so it is easy to figure out the mechanism :)
As to why the complex numbers fit perfectly in this, consider that there is exactly 90 degree phase difference between cos(n) and sin(n). The real and imaginary axes of complex numbers are also exactly 90 degrees apart.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
