1
$\begingroup$

If I have a length $N$ signal and ask Matlab for an $M$-point FFT, $M \gg N$, of course the computer has to allocate memory for $M$ output samples, but my question is if it ever has to allocate memory for $M$ input and fill it with the input vector along with zeros? Or are FFT algorithms capable of generating the $M$-point result without having to explicitly store the $M$-length padded input?

(Motivation I have a library that can automatically give me zero-padded data (or unpadded data), which I then perform FFTs on. Assume everything before the result of this library call has already happened, and we only care about what we do once those results (padded or unpadded) are available. If Matlab or FFTW don't need to explicitly allocate $M$-long zero-padded inputs to the FFT, then I'd be wasting memory by asking the library to zero-pad for me, and should just ask it for unpadded data.)

$\endgroup$
1
$\begingroup$

There is an FFT trick to perform a $2N$-point FFT on $2N$ real-only input samples using a single complex $N$-point FFT operation. But I've never heard of performing an $M$-point FFT on $N$ input samples without zero padding the input sequence out to length $M$. Ahmed, if you can develop a way to do that you would become famous and someone would write a song about you.

$\endgroup$
  • $\begingroup$ I am honored to have my silly question answered by Rick Lyons! No, I grok that an $M$-point FFT on $N$ input samples implicitly requires zero-padding the input to $M$-length. But I guess I'm asking if implementations explicitly construct this $M$-long padded input, or if they could construct the $M$ output samples without first allocating space for $M$ input samples, writing zeros to it, and copying the original $N$ samples to the first $N$ slots in the array. $\endgroup$ – Ahmed Fasih Dec 19 '15 at 16:04
1
$\begingroup$

After reviewing the butterfly structure employed in FFT, it looks like explicit zero-padding or increasing the memory allocation at the input is required. For example, in zero-padding a N-point FFT to a M-point FFT, say N=6 and M=8. As shown in the FFT algorithm with the basic butterfly computation below. enter image description here

We will need to explicitly zero-padded the sequence as shown in the figure. Despite x(6) and x(7) are just zeros (the zero-padded coefficients), their memory locations will eventually be used to hold X(3) and X(7) respectively, and they will become non-zero quickly after the first stage (assuming x(2) & x(3) are both non-zero). My assumption is, the output of the FFT overwrites the input though.

$\endgroup$
  • $\begingroup$ Thanks! From this line of reasoning, assuming the input was copied to a newly-allocated $M$-long block of memory which becomes the output after the FFT, the answer would be, no, an implementation doesn't need to allocate an intermediate $M$-long array: the only array it allocates becomes the output! $\endgroup$ – Ahmed Fasih Dec 21 '15 at 2:33

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.