0
$\begingroup$

I am trying to understand the functionality of fft.m in matlab .

For example: if I input a signal of length $7$, and use the FFT function, the output is of the same length.

How does that occur if the radix-$2$ takes the nearest power of $2$, which is $8$?

So how does it return an output of length $7$, assuming it operates the way I described?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ I think that the program takes an original length of 8, which is power of 2 (by adding a null sample at the end of the input sequence), then calculates the FFT and after that you are shown the length you wanted at the beginning (MATLAB is clever and knows that the 8th sample was added by itself, but you didn't want it). This is just a suposition but I think that's the way it actually works. Maybe someone with more knowledge about the topic can give you more information about this. $\endgroup$ – Tendero May 8 '16 at 2:49
  • $\begingroup$ @Shaman The concept of Fast Fourier Transform is not limited to powers of two. Did you have a look at the help, going down to the reference to FFTW: Frigo, M., and S. G. Johnson. "FFTW: An Adaptive Software Architecture for the FFT." Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. Vol. 3, 1998, pp. 1381-1384? $\endgroup$ – Laurent Duval May 8 '16 at 9:16
  • $\begingroup$ @LaurentDuval , the FFTW is based on the Cooley-Tukey algorithm , and uses other algorithms such as prime factor , split-radix , and Rader’s algorithm . All the examples and figures in the paper , demonstrate the use of a 2^n signal length size . $\endgroup$ – Shaman May 8 '16 at 23:54
0
$\begingroup$

There are lots of FFT algorithms, and they don't all require power of 2 sizes. For instance, you can do any size (including prime sizes like 7) with Bluestein's (Chirp-Z) algorithm, and the algorithm is still fast ($N \log(N)$).

I've heard that MATLAB uses FFTW under the hood, and FFTW includes many (all?) of these other algorithms. So MATLAB can do a length 7 FFT without rounding it to a power of 2.

| improve this answer | | | | |
$\endgroup$
0
$\begingroup$

I think it has to do with the DFT expansion

$$X[k] = \sum\limits_{n=0}^{N-1} x[n]e^{-j2\pi nk/N}$$

Now,

$$X[0] = \sum\limits_{n=0}^{N-1} x[n]$$

and you will see that

\begin{align} X[N] &= \sum\limits_{n=0}^{N-1} x[n]e^{-j2\pi n N/N}\\ &= \sum\limits_{n=0}^{N-1} x[n]e^{-j2\pi n}\\ &= \sum\limits_{n=0}^{N-1} x[n] \end{align}

which is again same as $X[0]$. Basically the DFT starts repeating after $N$ samples. So all the required information is already present in the first N frequencies.

Now $N$ could be defined by you. It is recommended to use $N$ to be the nearest power of $2$ of the length of the input signal. This is done to speed up the FFT computation (radix-2 as you pointed out). If the length of the input signal is more than that, it will be truncated else $0$s will be added. The output length will be same as the input length or the $N$ that you describe.

Hope this helps!

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Well after adding 0's to the input signal ( which is not a power of 2 ) , the fft in a radix-2 algorithm should return 2^n signal length , but that's not the case in matlab . $\endgroup$ – Shaman May 8 '16 at 23:29
  • $\begingroup$ Can you give an example. This sounds strange. $\endgroup$ – Amal May 9 '16 at 1:36
  • $\begingroup$ write this on matlab : Z = [ 1+1i ; 2+2i ; 3+3i] y = fft(Z) this is a simple example , I got 3 inputs , and the output length is 3 , shouldn't it be 4 if padding was applied ? $\endgroup$ – Shaman May 9 '16 at 1:48
  • $\begingroup$ No that is what I wrote earlier. It would be 3 unless YOU pad zeros to it to make it 4. So usually you will use n = 2^nextpow2(L) where L is the length of the input vector and then call fft as y = fft(x,n) $\endgroup$ – Amal May 9 '16 at 1:56
  • $\begingroup$ If you call it y = fft(Z,4), you'll see the length of y is 4. $\endgroup$ – Amal May 9 '16 at 1:57
0
$\begingroup$

If a length can be broken down into very small prime factors, such as 2, then the FFT of that length can be computed using less steps (MACs, etc.) than using a full DFT to compute the same result. If not, such as with a length 7, which can't be broken down into smaller factors, then a simple FFT engine often defaults to doing the same computational steps as a DFT, and thus not really a F/Faster FT. And a DFT is the same for any length, output length = input length.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ This was just a simple example of the larger picture . I wasn't specifically talking about a signal length of 7 , but any length that is not a power of 2. $\endgroup$ – Shaman May 8 '16 at 23:26
  • $\begingroup$ If there is a factor of 2 in the length, use radix-2 on 2 slices. If a factor of 3 or 5, use a radix-3 or radix-5 on shorter slices to speed up the previous or following steps. Etc. for any small prime factor. $\endgroup$ – hotpaw2 May 9 '16 at 1:52
  • $\begingroup$ FFT algorithm is fast because of any factoring of the length, not because all the factors are 2. Small primes allow an FFT to be done a bit faster than much bigger factors. $\endgroup$ – hotpaw2 May 9 '16 at 2:27
  • $\begingroup$ so before applying fft , matlab checks the signal length to apply radix-N (N being the factor) , or any other built-in algorithm that would return the original signal length, unless specified by me ? $\endgroup$ – Shaman May 10 '16 at 2:07
  • $\begingroup$ IIRC, MatLab uses fftw; and the current fftw implementations use many many different algorithms depending on the input length, its factorization, and even the targeted processor architecture and memory subsystem. $\endgroup$ – hotpaw2 May 10 '16 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.