Skip to main content

Discrete Fourier Transform

There are actually two types of discrete time fourier transform, discrete fourier transform (DFT) and discrete time fourier transform (DTFT).

The former is in fact the fourier series for a discrete signal. The latter is the fourier transform on a discrete signal. We introduce DFT first.

DFT​

Again, DFT is a fourier series, just called discrete fourier transform.

For continuous, periodic signal, we had,

x(t)=∑k=−∞+∞akejkωtx(t) = \sum_{k=-\infty}^{+\infty} a_k e^{j k \omega t} ak=1T∫0Tx(t)e−jkωtdta_k = \frac{1}{T} \int_{0}^{T} x(t) e^{-j k \omega t} \mathrm{d}t

The discrete signal is equal to,

xs(t)=∑k=0N−1x[k]δ(t−k)x_s(t) = \sum_{k=0}^{N - 1} x[k] \delta(t - k)

So,

ak=1T∫0Txs(t)e−jkωtdt=1T∑k=0N−1x[k]e−jkωta_k = \frac{1}{T} \int_{0}^{T} x_s(t) e^{-j k \omega t} \mathrm{d}t = \frac{1}{T} \sum_{k=0}^{N - 1} x[k] e^{-j k \omega t}

Sometimes, we may process signals with a given range (image, for example). Assume it has a rang from 00 to NN, we can treat it as a signal with a period of NN as well.

We note,

X[k]=1N∑k=0N−1x[k]e−jkωtX[k] = \frac{1}{N} \sum_{k=0}^{N - 1} x[k] e^{-j k \omega t}

As the discrete fourier transform.

However we are not done yet, consider,

x[t]=∑k=−∞+∞akejkωtx[t] = \sum_{k=-\infty}^{+\infty} a_k e^{j k \omega t}

We would notice that,

X[k+N]=∑k=0Nx[k]e−jω(k+N)t=e−jωNt∑k=−∞+∞akejkωtX[k + N] = \sum_{k=0}^{N} x[k] e^{-j \omega (k + N) t} \\ = e^{-j \omega N t } \sum_{k=-\infty}^{+\infty} a_k e^{j k \omega t}

So X[k]X[k] is periodic as well, thus, x[t]x[t] after the inverse transform is like not to converge.

The reason is that, consider the discrete complex exponential, we want the period of NN and so,

ejωN=1e^{j \omega N} = 1

There exists NN if and only if ω=2πpq\omega = 2\pi \frac{p}{q}, suppose pp and qq have no common divisor, and thus,

N=min⁡kkqp=qN = \min_k k \frac{q}{p} = q

Which is to say that, the period is only related to the denominator. So it's obvious that, for,

x[t]=∑k=−∞+∞akejk2πNtx[t] = \sum_{k=-\infty}^{+\infty} a_k e^{j k \frac{2\pi}{N} t}

If we sum over −∞-\infty to +∞+\infty, we are repeating the same base signal over and over again.

We only need to sum each signal once, and so,

x[t]=∑k=0N−1akejk2πNtx[t] = \sum_{k=0}^{N - 1} a_k e^{j k \frac{2\pi}{N} t}

Is the legit result.

In conclusion, we had,

x[t]=∑k=0N−1X[k]ejk2πNtX[k]=1N∑k=0N−1x[k]e−jkωtx[t] = \sum_{k=0}^{N - 1} X[k] e^{j k \frac{2\pi}{N} t} \\ X[k] = \frac{1}{N} \sum_{k=0}^{N - 1} x[k] e^{-j k \omega t}

However, for correspondence, because we had 12π\frac{1}{2 \pi} for the fourier inverse transform, and thus, we usually use the following form of DFT,

x[t]=1N∑k=0N−1X[k]ejk2πNtX[k]=∑t=0N−1x[t]e−jk2πNtx[t] = \frac{1}{N} \sum_{k=0}^{N - 1} X[k] e^{j k \frac{2\pi}{N} t} \\ X[k] = \sum_{t=0}^{N - 1} x[t] e^{-j k \frac{2\pi}{N} t}

The two are identical.

This will also come in handy in the next chapter where we need to push X[k]X[k] to a continuous limit, and thus, we need a density divider for x[t]x[t].