DFT Frequency domain analysis and interpolation

Question

I have a 2 part question, one may be related to why I'm not understanding the other.

A while back, I remember some professor saying that for the $N$ point DFT frequency domain, the values for $k$ around $N/2$ (halfway point for the spectral domain - those around $\pi$) are considered high frequencies, and the end points $(0, N-1)$ (those around 0, $2\pi$) are considered low frequencies. I am having trouble seeing this mathematically given the definition for computing the coefficients of the DFT.

$$X[k]=\sum_{n=0}^{N-1}\left(x_ne^{\frac{-i2\pi{}kn}{N}}\right)$$

To me, it seems that the frequencies grow as $k$ increases right up until $k=N-1$, where the coefficients repeat due to periodicity. Perhaps I am mis-remembering and this may be an incorrect assumption?

This leads on to my second question. I have seen a few examples floating around online, where to interpolate in the time domain, one may pad in the frequency domain (running the IFFT after of course). The examples I have seen seem to decide to pad the coefficients around the middle, i.e. for $N=4$ and a desired sampling of $2N$, [1 2 3 4] become [1 2 0 0 0 0 3 4]. Is there a reason why the middle is targeted and not the end like [1 2 3 4 0 0 0 0]?

If my first question is correct, then this simply pads the higher frequencies as 0. I am aware that these zeroes add nothing to the frequency information as $X[k]=0$ cancels any effect during the inverse DFT. But wouldn't moving any of the coefficients change some frequency information, i.e. for [1 2 3 4] becoming [1 2 0 0 0 0 3 4]

$N=4, k=2, X[k]=3$, becomes $2N=8, k=6, X[k]=3$

$$e^{\frac{+i2\pi{}2n}{N}}\neq{}e^{\frac{+i2\pi{}6n}{2N}}$$

Answer 1

Concerning your first question, the fact that $k=N/2$ (for even $N$) corresponds to the highest frequency has to do with the periodicity of $X[k]$. Note that due to periodicity, the indices $k=N-1$, $k=N-2$, etc. correspond to the negative indices $k=-1$, $k=-2$, etc., which are low (negative) frequencies. As an example consider $x[n]=\cos(2\pi n/N)$. If you take the DFT of $x[n]$ you'll obtain a spectrum $X[k]$ with contributions at $k=1$ and at $k=N-1$. It would be wrong, however, to conclude that the signal has one component at low frequencies and one at high frequencies. It's just that a real-valued signal has a conjugate symmetric spectrum and so you get components at positive and at the corresponding negative frequencies. The latter appear at higher DFT indices due to periodicity of $X[k]$. The figure below shows the signal and its DFT coefficients for $N=8$:

Concerning your second question, as mentioned before, a real-valued signal has a conjugate symmetric spectrum and its DFT coefficients satisfy

$$X[k]=X^*[N-k]\tag{1}$$

If you want to interpolate a real-valued signal, then also the zero-padded spectrum must satisfy $(1)$. This means that you must zero-pad in the middle of the given frequency domain vector. Otherwise, the inverse DFT would generate a complex-valued time-domain signal.

Answer 2

A while back, I remember some professor saying that for the N point DFT Frequency Domain, the values for k around N/2 (halfway point for the spectral domain - those around π) are considered high frequencies, and the end points (0, N-1) (those around 0, 2π) are considered low frequencies. I am having trouble seeing this mathematically given the definition for computing the coefficients of the DFT.

You can define the DFT however you like, as long as in effect the same frequencies are covered - remember, $f(x) = e^{jx}$ is $2\pi$-periodic, so that, for example, the sum over $k=0,\ldots, N-1$ is the same as the sum over $k=-\left\lfloor\frac N2\right\rfloor,\ldots,0,\ldots,+\left\lfloor\frac {N-1}2\right\rfloor$.

The examples I have seen seem to decide to pad the coefficients around the middle, i.e. for N=4 and a desired sampling of 2N, [1 2 3 4] become [1 2 0 0 0 0 3 4]. Is there a reason why the middle is targeted and not the end like [1 2 3 4 0 0 0 0]?

Again, different definitions of the DFT lead to different forms for zero-padding here.

Answer 3

(1) I think the first question is indeed why the digital frequency is periodic. For this matter, it can be checked on the definition of the DFT but it is not intuitive about the reason. To understand this, we can refer to the periodic sampling process and the change of the spectrum extension. Then, since a real value signal has symmetric spectrum, it is also easy to understand why the $\pi$ is the highest frequency in the DTFT (in the DFT, the $\pi$ may not be sampled for odd sizes).

(2) Interpolation means resampling with smaller sampling interval or higher sampling frequency. Also by means of the sampling perspective, the higher sampling frequency $f_s$ make the extension more wider, thus the new contents should be zeros. Then, in the frequency domain, padding zeros in the highest frequency is equivalent to interpolation in the temporal domain. Also, as others have pointed out, why padding in the center is actually why the highest frequency is on the center, and this is due to the common definition of the DFT.

Answer 4

If you remember the reason why baseband signals must be bandlimited to below half the sampling rate, the reason was that any frequencies (in strictly real data) above Fs/2 will be aliased to frequencies below Fs/2. So if the data was real and bandlimited to below Fs/2, the bins in a DFT above N/2 can't represent frequencies that are not present in properly bandlimited sampled data.

Also note that given strictly real data, the result of a DFT will be conjugate symmetric. So those DFT result bins at the "upper" end are not independent of the lower half, and thus can't represent frequencies different from those in the lower half of the DFT.

Maintaining that conjugate symmetry so the result of an IDFT will produce strictly real data is the reason why padding has to be done in a manner circularly symmetric around the 0th element. Asymmetric padding might produce a complex result given a real input, which is probably not the desired result of just a sample rate change.