How to implement the FFT algorithm. An article on how to implement the FFT algorithm in C, C++ or C#. Introduction. Basically, this article describes one way to implement the 1. D version of the FFT algorithm for an array of complex samples. The intention of this article is to show an efficient and fast FFT algorithm that can easily be modified according to the needs of the user. I've studied the FFT algorithm when I was developing a software to make frequency analysis on a sample of captured sound. Background. First of all, 9. This is practically the code that is described in the book Numerical Recipes In C of 1. Yes, more than 2. But still, in my opinion, very, very good. But this code is slightly different from the original one. When I was studying the algorithm, I had noticed a pattern that could be exploited, and based on that, I've managed to improve the algorithm with a small change in the code, and the O() (The Big O) (unit measure to the complexity of the algorithm) is reduced in N computations. I've just noticed something that someone had already seen : -P)I will not get . Other forms of the FFT like the 2. D or the 3. D FFT can be found on the book too. Fast Fourier Transform (FFT). Now the N-point DFT can be expressed in terms of the DFT's of the decimated sequences as. The FFT - an algorithm the whole family can use. FFT is an algorithm for computing the DFT in O. The FFTThe Fast Fourier Transform is an optimized computational algorithm to implement the Discreet Fourier Transform to an array of 2^N samples. It allows to determine the frequency of a discreet signal, represent the signal in the frequency domain, convolution, etc.. This algorithm has a complexity of O(N*log. N)). Actually, the complexity of the algorithm is a little higher because the data needs to be prepared by an operation called bit- reversal. This bit- reversal section is presented in the Numerical Recipes In C as a O(2.
N) complexity. With a small change I've made to the code presented here, it makes it in O(N). This represents something like an 8% improvement of performance. Example of a signal in the frequency domain. The FFT is calculated in two parts. The first one transforms the original data array into a bit- reverse order array by applying the bit- reversal method. This makes the mathematical calculations of the second part . The second part processes the FFT in N*log. N) operations (application of the Danielson- Lanzcos algorithm). Let's start with an array of complex data. This array could be, for example, in this case, an array of floats in witch the data. In case the sample doesn't match that size, just put it in an array with the next 2^N size and fill the remaining spaces with 0s. Just a small and not very significant consideration: the original code uses data arrays considering the beginning of the information is in index 1 - > data. My code modifies that to start from 0 - > data. For example, the complex. If the index (in binary) is 0b. In figure 1, you can see what happens to the data array after the transformation. The implementation of this method according to Numerical Recipes In C goes like this: n=number. Let's see: divide the array in half with a mirror. If you look at the reflecting side of the mirror, you will see exactly the same thing of what's in the other side. This mirrored effect allows you to do the bit- reversal method in the first half of the array and use it almost directly in the second half. But you must be careful with one thing. You can only apply this effect if the change happens in the first half only. This means that if the change is between an index of the first half and an index from the second, this is not valid, otherwise you would be making the swap and then undoing it again (do this on a 1. I'm saying). So the code becomes something like this: n=number. This applies the N*log. N) trigonometric recurrences to the data. The code I will show here is my version (data starts at index 0): mmax=2. Imagine that you want to collect a sample of a signal or a function, and you want to know the fundamental frequency of it. This sample may come from any source: a function that you've inserted in the code, a piece of captured sound, etc.. Let's say that the signal is a real array signal (just like the sound capture buffer), how do I use the FFT??? First of all, you need to choose the FFT variant that you will use. There is a specific variant for real arrays, but in this case, I will use this. It's not the most efficient, but it's easy to use. Next concern is the amount of data you're going to send to the FFT and the sample rate. The sample rate must be a 2^N number, but you don't need to send an array of 2^N samples to be processed (read the NR for different implementations). You can just send 5. But remember, the more data you send for calculation, the more precise is the FFT. After the real array has been passed to a complex array with the complex part equal to 0, you compute the FFT. And now for the results. After the FFT is calculated, you can use the complex array that resulted from the FFT to extract the conclusions. If you are interested in knowing the fundamental frequency of the signal, find the absolute maximum of the array, and the frequency will be given by the index of the array. The absolute value of a complex number is the square root of the square of the real plus the square of the complex. If the absolute maximum occurs in the complex number given by indexes . You have to divide it in half because the array is twice longer (remember: real, complex), so the result is not the index position (1. If your intention is to draw the Fourier signal, it goes the same way. Frequency 3. 0 is given by the absolute value of complex . The second half of the computed FFT array must be ignored due to the Nyquist redundancy (the minimum sample rate must twice the highest frequency of the signal). It's only a mirror of the first half. If you want to measure frequencies up to 6. N number next to 2*6. See the example were I apply the FFT to a Sine signal. It's on the On. Paint function of the CChild. View class. The FFT is implemented on the CFourier class. The example is a stupid example and has a stupid structure, but I think it's easy to understand. Change the parameters, play with it, try different things, and see the results. This way, you will be able to take your own conclusions. Precautions. If you intend to use this FFT implementation, read the NR license. There are lots of documentation on this matter. It's not an easy thing to understand, but I think it's a very interesting subject.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
January 2017
Categories |