# Concatenation within DFT

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?

Thanks.

-
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.