Radix2 fft - zero padding output size

Question

With zeros padding the FFT radix2 has different input size than output. How to deal with that? I see two solutions but not sure which one is better/appropriate. Maybe you know some other and better solutions?

Let me explain:

let’s sey I have signal buffer size 400, and I want to perform radix2 fft with zeros padding. So the nearest $2^L$ is 512. So I need to add 112 zeros for each buffer. Then in the fact the output buffer is 512. But I need 400, the same as input.

So first solution I see is to provide some FIFO algirithm for output signal.

And the second solution I see is to shrink my output from 512 to 400, and spread all 512 bins evenly on 400 bins. But then adjacent bins will partly overlap each other. So I need to avarage them in some way. HOW? And is it at all solution that would give me nice results, for example for pitch shifting?

For any help thanks in advance.

Answer 1

Note the convention of notation: "$X[\cdot]$" is not the same as "$X(\cdot)$" (but they are defined solely in terms of the same "$x[\cdot]$"). The square brackets [] allow only discrete integer arguments, the round parenths () allow continuous real or complex arguments.

Discrete-Time Fourier Transform (DTFT):

$$ \mathscr{F}\big\{x[n]\big\} \triangleq X\big( e^{j\omega} \big) = \sum\limits_{n=-\infty}^{\infty} x[n] \, e^{-j\omega n} $$

This is literally the double-sided $\mathcal{Z}$-transform of $x[n]$ evaluated at $z=e^{j \omega}$.

If your original $x[n]$ has non-zero length of $N$, then DTFT is:

$$ X\big( e^{j\omega} \big) = \sum\limits_{n=0}^{N-1} x[n] \, e^{-j\omega n} $$

The length-$N$ Discrete Fourier Transform (DFT) of $x[n]$ is

$$ X[k] = \sum\limits_{n=0}^{N-1} x[n] \, e^{-j 2 \pi n k /N} $$

The DTFT is a mathematical operation for the blackboard (or whiteboard or on paper). The DFT is what computers do when they perform the Fast Fourier Transform, (FFT).

And the DFT is the DTFT of this finite-length sequence evaluated at $N$ equally-spaced frequencies between $0$ and $2\pi$.

$$ X[k] = X\big( e^{j\omega} \big) \bigg|_{\omega = 2 \pi k/N} $$

---

So now, what if you zero-pad $x[n]$ to a longer length $\tilde{N}>N$?

$$ \tilde{x}[n] = \begin{cases} x[n] \qquad & 0 \le n < N \\ \\ 0 \qquad & N \le n < \tilde{N} \\ \end{cases} $$

Then the DTFT of this is:

$$ \mathscr{F}\big\{\tilde{x}[n]\big\} = \tilde{X}\big( e^{j\omega} \big) = \sum\limits_{n=-\infty}^{\infty} \tilde{x}[n] \, e^{-j\omega n} $$

But the funny thing is that the two DTFTs are the same

$$ \tilde{X}\big( e^{j\omega} \big) = X\big( e^{j\omega} \big) $$

because there is no difference between $x[n]$ and $\tilde{x}[n]$ in the zero-extended DTFT.

But the DFTs come out a little different (only because $\tilde{N} \ne N$).

$$\begin{align} \tilde{X}[k] &= \sum\limits_{n=0}^{\tilde{N}-1} \tilde{x}[n] \, e^{-j 2 \pi n k /\tilde{N}} \\ \\ &= \sum\limits_{n=0}^{N-1} \tilde{x}[n] \, e^{-j 2 \pi n k /\tilde{N}} \\ \end{align}$$

(Note the change of $\tilde{N}$ to $N$ in the second summation is because $\tilde{x}[n]=0$ for $N \le n < \tilde{N}$. That has an interesting consequence below.)

Also this:

$$ \tilde{X}[k] = \tilde{X}\big( e^{j\omega} \big) \bigg|_{\omega = 2 \pi k/\tilde{N}} $$

Now it turns out that the inverse DFT is similar for $\tilde{x}[n]$

$$ \tilde{x}[n] = \tfrac1{\tilde{N}} \sum\limits_{k=0}^{\tilde{N}-1} \tilde{X}[k] \, e^{+j 2 \pi n k /\tilde{N}} $$

and the DTFT can be evaluated in terms of this expression for $\tilde{x}[n]$.

$$\begin{align} \tilde{X}\big( e^{j\omega} \big) &= \sum\limits_{n=0}^{\tilde{N}-1} \tilde{x}[n] \, e^{-j\omega n} \\ \\ &= \sum\limits_{n=0}^{N-1} \tilde{x}[n] \, e^{-j\omega n} \\ \\ &= \sum\limits_{n=0}^{N-1} \tfrac1{\tilde{N}} \sum\limits_{ k=0}^{\tilde{N}-1} \tilde{X}[k] \, e^{+j 2 \pi n k /\tilde{N}} \, e^{-j\omega n} \\ \\ &= \sum\limits_{k=0}^{\tilde{N}-1} \tilde{X}[k] \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi n k /\tilde{N}} \, e^{-j\omega n} \\ \end{align}$$

The DFT of $x[n]$ you seek is

$$\begin{align} X[k] &= X\big( e^{j\omega} \big) \bigg|_{\omega = 2 \pi k/N} \\ \\ &= \tilde{X}\big( e^{j\omega} \big) \bigg|_{\omega = 2 \pi k/N} \\ \\ &= \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi n \tilde{k} /\tilde{N}} \, e^{-j\omega n} \bigg|_{\omega = 2 \pi k/N} \\ \\ &= \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi n \tilde{k} /\tilde{N}} \, e^{-j2 \pi n k/N} \\ \\ &= \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)n} \\ \end{align}$$

Note the $\tilde{k}$ is just a different "$k$" as a token counting variable in the summation.

There is this exponential summation identity in closed-form:

$$ \sum\limits_{m=0}^{M-1} a^m = \frac{a^M-1}{a-1}$$

so

$$\begin{align} \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)n} &= \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} \big(e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)}\big)^n \\ \\ &= \frac{\big(e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)}\big)^N - 1}{\tilde{N} \big(e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)} - 1 \big)} \\ \\ &= \frac{e^{+j \pi (\tilde{k}N/\tilde{N} - k)}\big( e^{+j \pi (\tilde{k}N/\tilde{N} - k)} - e^{-j \pi (\tilde{k}N/\tilde{N} - k)} \big)}{\tilde{N} e^{+j \pi (\tilde{k}/\tilde{N} - k/N)}\big(e^{+j \pi (\tilde{k}/\tilde{N} - k/N)} - e^{-j \pi (\tilde{k}/\tilde{N} - k/N)} \big)} \\ \\ &= \frac{e^{+j \pi (\tilde{k}N/\tilde{N} - k)}e^{-j \pi (\tilde{k}/\tilde{N} - k/N)}\big( e^{+j \pi (\tilde{k}N/\tilde{N} - k)} - e^{-j \pi (\tilde{k}N/\tilde{N} - k)} \big)/(2j)}{\tilde{N} \big(e^{+j \pi (\tilde{k}/\tilde{N} - k/N)} - e^{-j \pi (\tilde{k}/\tilde{N} - k/N)} \big)/(2j)} \\ \\ &= \frac{e^{+j \pi (N-1)(\tilde{k}/\tilde{N} - k/N)} \sin\big( \pi N (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)}{\tilde{N} \sin\big( \pi (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)} \\ \end{align}$$

This shows the DFT of the original data (at the original size of $N$) can be extracted from the DFT of the zero-padded data:

$$\begin{align} X[k] &= \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \tfrac1{\tilde{N}} \sum\limits_{n=0}^{N-1} e^{+j 2 \pi (\tilde{k}/\tilde{N} - k/N)n} \\ \\ &= \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \left( e^{+j \pi (N-1)(\tilde{k}/\tilde{N} - k/N)} \frac{\sin\big( \pi N (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)}{\tilde{N} \sin\big( \pi (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)} \right) \\ \end{align}$$

It ain't purty, but I think this is the simplest I can make it. This is one form of expressing the Dirichlet kernel.

---

Edit note:

I made a completely legitimate change of $\tilde{N}$ to $N$ (because $\tilde{x}[n]=0$ for $N \le n < \tilde{N}$) and this results in some changes in the answer. With $\tilde{N}$ unchanged the previous answer (which is just as correct) was:

$$ X[k] = \sum\limits_{ \tilde{k}=0}^{\tilde{N}-1} \tilde{X}[\tilde{k}] \left( e^{+j \pi (\tilde{N}-1)(\tilde{k}/\tilde{N} - k/N)}\frac{\sin\big( \pi \tilde{N}(\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)}{\tilde{N} \sin\big( \pi (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)} \right) $$

They both have to be correct. But clearly these two expressions are not equal:

$$ e^{+j \pi (\tilde{N}-1)(\tilde{k}/\tilde{N} - k/N)}\frac{\sin\big( \pi \tilde{N}(\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)}{\tilde{N} \sin\big( \pi (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)} \ne e^{+j \pi (N-1)(\tilde{k}/\tilde{N} - k/N)}\frac{\sin\big( \pi N (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)}{\tilde{N} \sin\big( \pi (\tfrac{\tilde{k}}{\tilde{N}} - \tfrac{k}{N}) \big)} $$

So how is it that the summations (with the very same $\tilde{X}[\tilde{k}]$ coefficients) add up to be the same?

I would be very interested in anyone's answer to that.

Answer 2

you actually need to resample (or interpolate) either the 400 sample input to 512, then FFT (with $N=$512), then pick only the bottom 400 samples (that's sorta like zero-padding the output) or you need to zero-pad like you are doing, then FFT, then (resample) interpolate the 512 output values to 400. the interpolation kernel is something we call the Dirichlet kernel.