Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Discrete Fourier Transform (DFT) is given by

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

for $k=0,1,\ldots N$. I store the variables $X_k$ and would like to add $m$ zeros to the variables $x_n$. After concatenating $m$ zeros I would like to find the values of the new $X_k$. That is, I would like to compute the values

$Y_k = \sum_{n=0}^{N-1+m} y_n e^{2\pi i k n/(N-1+m)}$

for $k=0,1,\ldots N+m$ where $y_n = (x_0,\ldots,x_{N-1},0,\ldots,0)^T$. Currently, I'm using the inverse DFT to get to the x_k coefficients, concatenating $m$ zeros to them and then using the DFT to find the $Y_k$.

Is there a better way?


share|cite|improve this question
There are several typos in your question that should be corrected. With regard to the (corrected) question, in the general case, interpolation is possible but not more efficient than the DFT approach that you have found already. Some of the DFT work can be reduced by using Fast Fourier Transform (FFT) algorithms. That being said, in the special case when $m$ is a multiple of $N$ (usually $m = N$ is most common), some small savings can be achieved. In this case, $Y_{2k} = X_k$ and need not be computed again. This could save one iteration of a suitably chosen FFT algorithm. – Dilip Sarwate Jan 19 '12 at 15:16

You might want to ask this question on dsp.SE instead (maybe the moderators can move it?). For the special case $m = N$, a more general version of the question (when a nonzero sequence of length $N$ is concatenated to the given sequence) is discussed here.

share|cite|improve this answer

Your Answer


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.