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?
Best Answer
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.