Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I take a discrete Fourier transform of $\{ c_1, c_2, \ldots, c_n\}$ where $n$ is prime, I am rather limited in the FFT algorithms available to me and their performance. Additionally, having mixed-radix FFT algorithms and prime-length FFT algorithms, plus the code necessary to determine which to use, increases my code size which is a limiting factor.

Suppose $n$ is prime and I decide to, instead, take the discrete Fourier transform of $\{ c_1, c_2, \ldots, c_n, 0\}$ so that, now, the length of the data is no longer prime. I know that the "picture" I get will be more smooth as compared to the true DFT of the original data.

Is there any way to zero-pad the original data slightly, perform a FFT, and then reverse the effects of the zero-padding afterwards? By that, I mean the length of the output list should be $n$, not $n + 1$. I do not expect to obtain precisely the same result from the $n + 1$ padded FFT as with the original $O(n^2)$ DFT. I understand it is practically impossible to reverse the smoothing affect of the padding.


Summary: I can zero-pad my data so it has a non-prime length, but then the result of my FFT has the wrong length, and the values on the indices don't match the true DFT. I can't just drop the last element of my FFT result, I need to something more "involved". What post-processing can I do to my zero-padded data so that it looks more like the original DFT, and has the same length?

share|improve this question
1  
This might get more responses from the signal processing community dsp.stackexchange.com –  Fixed Point Dec 12 '12 at 5:56

1 Answer 1

Actually, by padding with zeroes you are not smoothing or losing information.

The original FFT and the "padded FFT" just corresponds to sampling the same (true) DTFT $X(\omega)$ in different points; but both samplings are enought to recover (in theory) the true $X(\omega)$.

Let me change a little notation to be more consistent with common usage.

Let $N$ be the length of the original signal $x_n=x_0, x_1 \cdots x_{N-1}$ and let $X(\omega)$ be its DTFT , $X(\omega)= \sum x_n \exp(-i \omega n)$ Let $y_n$ be the same signal right padded with zeroes, so that its length is $N_p>N$.

It's clear that its DTFT is the same.

The DFT (what the FFT computes) are different, though. That's because they correspond to sampling $X(\omega)$ at different points. If $X_k$ ($k=0,1, \cdots N-1$) is the $k$ component of the DTF of $x_n$, then the correspondence is

$$ X_k \leftrightarrow X(\omega)\biggl|_{\omega=2\pi k /N}$$

They are different, but from one you can get the other. This is quite obvious if one thinks that any DFT -padded or not- is invertible, so from the padded FFT you can recover the original signal, and then you can recover the unpadded FFT.

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi n k /N} = \sum_{n=0}^{N-1} \frac{1}{N_p} \sum_{j=0}^{N_p} Y_j e^{i 2 \pi n j /N_p} e^{-i 2 \pi n k /N}$$

This is sort of a trigonometric interpolation. But this is surely not practical, in your scenario: instead of doing this, you'd directly perform a plain DFT on the original unpadded data.

A more practical option (but non exact) would be to do some simpler interpolation. I guess a quadratic interpolation could work decently. But don't plug blindly the $Y_k$ into some interpolation routine, you must take into account the nature of a DFT or a real signal (preserve hermitic property), and you'd respect the zero component as your true "origin", so it is strictly preserved.

share|improve this answer
    
The n-point DFT is equivalent to multiplying by a certain n x n matrix. So, you can exactly 'undo' the padding in the frequency domain by multiplying by a specific matrix, this operation is embodied in the larger equation above - move the $\sum_n$ to after the $Y_j$ to better see this. The 'simpler interpolation' amounts to approximating that matrix with a much sparser one. It may be helpful to start by explicitly evaluating that exact 'correction' matrix, to see what it is that you are approximating. –  greggo Aug 13 at 18:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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