CODEWITHSUNDEEP
matlabfftsample
Ali
Ali

Reputation: 91

FFT number of input samples

I am wondering if I use 10000 samples and do the fft, my results would be much different comparing to when I have exactly the samples equal to n power of 2 or it just affects the speed of doing fft ? is Matlab doing the zero padding automatically ? or I should do zero padding ?

further information :

I am using matlab version 2012b, fft function to perform the dft on my samples. I have the time domain data for 10 minutes with sampling rate of 50 KHz. type of my work necessitates me to devide the time domain data in 200 ms windows. and after performing the fft on these 200 ms windows, I make an average over the different window results. 200 ms in 50 Hz frequency system which is sampled by 50Khz means about 10000 samples for each fft operation.

regards, Ali

Upvotes: 1

Views: 472

Answers (2)

Mark Borgerding
Mark Borgerding

Reputation: 8476

The original Cooley-Tukey form of the FFT was limited to powers of 2. A lot of people are still stuck in that mindset. Even professors still perpetuate the myth that FFTs need to be 2^K to be fast. The truth is that modern FFT libraries use a mixed radix approach. It allows fast transforms for a size that is an aggregate of small primes. Usually a number that factorizes over {2,3,5} is quite fast. If not, zero pad to the next number that is an aggregate of small primes, but not (necessarily) a power of 2.

As an aside, there are tricks that can technically achieve O(n log n) scalability with large primes, such as Chirp-Z and Rader's Prime algorithm , but they usually have a very large constant in front of them and should be avoided if possible.

Bottom line: Your size 10000 factorizes nicely over {2,3,5}, so it will be fast with most modern FFT implementations (even kissfft ). When in doubt, benchmark!

Upvotes: 5

Jommy
Jommy

Reputation: 1105

Matlab's fft is based on the fftw library which compute the result in O(n*log(n)) operations for any n (see http://www.fftw.org/fftw-paper-ieee.pdf), hence you won't obtain a gain in speed by zero padding your data.

Matlab's doesn't do the zero padding automatically, it's up to you to do it or not. Zero padding in the time domain is equivalent to interpolate your data in the frequency domain (see https://dsp.stackexchange.com/a/745/10782).

Upvotes: 0

Related Questions