# What does it mean that the DFT equals the Complex Fourier Coefficients for even frequencies?

I have a periodic signal, with period $1$

$$x(t) = \begin{cases} 1 \qquad & 0 \le t - \lfloor t \rfloor < \tfrac12 \\ 0 \qquad & \tfrac12 \le t - \lfloor t \rfloor < 1 \\ \end{cases}$$

$\lfloor t \rfloor = \operatorname{floor}(t)$ is the floor() function, returning the largest integer no greater than the argument $t$.

$$x(t+1) = x(t) \qquad \forall t \in \mathbb{R}$$

The complex Fourier series for $x(t)$ is

$$x(t) = \sum\limits_{k=-\infty}^{\infty} c_k \ e^{i 2 \pi k t}$$

The complex Fourier coefficients are

\begin{align} c_k &= \int_{-1/2}^{1/2} x(t) \ e^{-i2\pi k t} \ \mathrm{d}t \qquad \qquad k \in \mathbb{Z} \\ &= \int_{0}^{1/2} 1 \ e^{-i2\pi k t} \ \mathrm{d}t \\ &= \tfrac{1}{-i2\pi k } \big( e^{-i\pi k} - 1 \big) \\ &= \tfrac{i}{2\pi k } \big( (-1)^k - 1 \big) \\ \end{align}

and are $0$ for even $k$.

Now, we sample $x(t)$ at $N\in 2\mathbb{N}$ time values,

\begin{align} x[n] &= x(t_n) \\ &= x\left(\tfrac{1}{N}n\right) \end{align}

where $\tfrac{1}{N}$ is the sampling period, $N$ is the sampling frequency, and $t_n = \frac{n}{N}$, with $n=0, N-1$.

Let $X[k]$ denote the DFT of this finite sequence $x[n]$.

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

One can show that $X[k] = 0$ for even $k$ as well, so $X[2k] = c_{2k}$, but $X[2k+1] \neq c_{2k+1}$.

I'm trying to come up with an intuitive explanation as to why $X[2k] = c_{2k}$, but $X[2k+1]\neq c_{2k+1}$. Obviously, we shouldn't really expect them to be equal in general since $X[k]$ is really just a Riemann sum approximation to $c_k$ with $N$ intervals, but in this case it seems there may be an explanation, since $X[2k] = c_{2k}$.

So far, all I can come up with is that since $x(t)$ isn't bandlimited, the DFT of the discrete sample of $x(t)$ is essentially trying to "fit" a bandlimited signal to the samples $x[n]$, and so for some reason this doesn't have any content at frequencies $2\pi (2k) = 4\pi k$ for any $k\in\mathbb{N}$.

Is there any specific reason for this? From the above argument, I have a feeling it has to do with aliasing, but I can't exactly make the connection.

• it is because of aliasing. all of those Fourier series coefficients where $|k| \ge \tfrac{N}{2}$ fold back on top of those where $|k| \le \tfrac{N}{2}$. – robert bristow-johnson Apr 3 '18 at 22:46
• and if you chose $N$ to be odd, you would be finding out that $F[2k] \ne 0$. – robert bristow-johnson Apr 3 '18 at 23:49
• @robertbristow-johnson Not quite sure what you mean by "fold back on top of these". Could you elaborate in an answer? – user3002473 Apr 4 '18 at 19:24
• i'll try. but it will have to be later. may i change the notation in my answer and change the notation in your question to match it? i usually use "$f$" for non-angular frequency and usually use "$x(t)$" for continuous-time signals and "$x[n]$" for discrete-time signals. – robert bristow-johnson Apr 4 '18 at 21:41
• That's easy enough to understand, sure! – user3002473 Apr 4 '18 at 22:09

okay, i am using these definitions for the continuous Fourier Transform

$$\mathscr{F}\Big\{x(t)\Big\} \triangleq X(f) \triangleq \int_{-\infty}^{+\infty} x(t) \, e^{-i 2 \pi f t} \, \mathrm{d}t$$

and inverse

$$\mathscr{F}^{-1}\Big\{X(f)\Big\} \triangleq x(t) = \int_{-\infty}^{+\infty} X(f) \, e^{i 2 \pi f t} \, \mathrm{d}f$$

$f$ is "ordinary" frequency, not angular frequency (which for the continuous-time signals, the notation we use is $\Omega \triangleq 2 \pi f$). this is a preferred representation of the Fourier Transform for electrical engineers because it is the easiest manner to apply the Duality property (lotsa similarity between the FT and the inverse).

in this answer is shown how sampling in one domain (e.g. the "time" domain) causes periodic extension (repetition and overlapping and adding) in the reciprocal domain (e.g. the "frequency" domain). this is pointed out without regard to bandlimiting, so if the input is not sufficiently bandlimited, there will be aliasing. given the assumption of a real input to start with (which means the Fourier transform or two-sided spectrum has symmetry about $f=0$) frequency components above Nyquist (which is $\tfrac12$ the sample rate) are folded back to locations below Nyquist and added to whatever frequency components existed there.

$$x(t) = \sum\limits_{k=-\infty}^{\infty} c_k \ e^{i 2 \pi k t}$$

has a spectrum (which is not necessarily bandlimited, and is actually not bandlimited since the $c_k$ coefficients are not zero above some finite $k$) of

$$X(f) = \sum\limits_{k=-\infty}^{\infty} c_k \ \delta(f - k)$$

first defining the Dirac comb:

$$\operatorname{III}_T(t) \triangleq \sum_{n=-\infty}^{\infty} \delta(t-nT)$$

now, the ideally sampled signal (still represented in the continuous-time domain) is

\begin{align} x_\text{s}(t) &\triangleq x(t) \cdot T \cdot \operatorname{III}_T(t) \\ &= x(t) \cdot T \sum_{n=-\infty}^{\infty} \delta(t-nT) \\ &= T \sum_{n=-\infty}^{\infty} x(t) \ \delta(t-nT) \\ &= T \sum_{n=-\infty}^{\infty} x(nT) \ \delta(t-nT) \\ &= T \sum_{n=-\infty}^{\infty} x[n] \ \delta(t-nT) \\ \end{align}

and also this

\begin{align} x_\text{s}(t) &\triangleq x(t) \cdot T \cdot \operatorname{III}_T(t) \\ &= x(t) \cdot T \cdot \sum_{m=-\infty}^{\infty} \frac1T e^{i 2 \pi m \frac{t}{T}} \\ &= \sum_{m=-\infty}^{\infty} x(t) \ e^{i 2 \pi m \frac{t}{T}} \\ \end{align}

now from the latter, we know that the spectrum of the ideally sampling signal is this:

$$\mathscr{F}\Big\{x_\text{s}(t)\Big\} = X_\text{s}(f) = \sum_{m=-\infty}^{\infty} X\left(f - \tfrac{m}{T} \right)$$

which is periodic in the frequency domain with period $\frac{1}{T}$ where your sampling period $T=\tfrac{1}{N}$. that means your sample rate is $\tfrac{1}{T}=N$ and your Nyquist frequency is $\tfrac{N}{2}$. that is the "folding frequency" or "foldover frequency".

Okay, winding up, you plug the expression of $X(f)$, the non-bandlimited Fourier series, into the equation for $X_\text{s}(f)$, which is the spectrum of the ideally-sampled signal. And you plug in $N$ for $\tfrac1T$.

$$X(f) = \sum\limits_{k=-\infty}^{\infty} c_k \ \delta(f - k)$$

\begin{align} X_\text{s}(f) &= \sum_{m=-\infty}^{\infty} X\left(f - \tfrac{m}{T} \right) \\ &= \sum_{m=-\infty}^{\infty} X(f - N m) \\ &= \sum_{m=-\infty}^{\infty} \sum\limits_{k=-\infty}^{\infty} c_k \ \delta\big((f - N m) - k\big) \\ &= \sum\limits_{k=-\infty}^{\infty} \sum_{m=-\infty}^{\infty} c_k \ \delta\big(f - (k+Nm) \big) \\ &= \sum\limits_{k=-\infty}^{\infty} \sum_{m=-\infty}^{\infty} c_{k-Nm} \ \delta(f - k) \\ &= \sum\limits_{k=-\infty}^{\infty} \tilde{c}_k \ \delta(f - k) \\ \end{align}

where

$$\tilde{c}_k \triangleq \sum_{m=-\infty}^{\infty} c_{k-Nm}$$

so the coefficients of the Fourier series of the sampled periodic signal $x_\text{s}(t)$ are different from those of $x(t)$. even in the baseband where the DTFT (and following, the DFT) sees the spectrum.