---

Discrete Fourier Transform

---

From the previous few sections, it is probably now evident that a discreet function in one domain is accompanied by a periodic function in another domain. If everything we’ve seen so far has confused you more than helped, look at this grand overview of what each transform is and come back.

In a discreet Fourier transform, both the time and frequency domains have discreet, periodic functions. Due to the periodicity, the limits on the Fourier transform integral change to a finite range. This allows us to compute and represent both the function on a computer!

This is the reason why the discreet Fourier transform is the bread and butter of signal processing engineers.

The Discreet Fourier transform is represented by the equations:

$$\begin{equation*} \begin{split} f_n &= \sum\limits_{k=0}^{N-1} F_k e^{j 2\pi nk/N} \\[0.2cm] F_k &= \frac{1}{N}\sum\limits_{n=0}^{N-1} f_n e^{-j 2\pi nk/N} \end{split} \end{equation*}$$

The Fourier transform pairs that we saw in the Fourier Transforms tutorial remain the same for the Discrete Fourier Transform as well. The only difference is that the frequency domain is both discrete and periodic in this case.

---

Properties of Fourier Transforms

---

1. Linearity

$$\begin{equation*} \begin{split} ax_n &\longleftrightarrow aX_k \\[0.3cm] ax_n + by_n &\longleftrightarrow aX_k + bY_k \\ \end{split} \end{equation*}$$

---

2. Periodicity

Both $x_n$ and $X_k$ are periodic with period $N$.

$$\begin{equation*} \begin{split} x_{n+mN} &= x_n \\[0.3cm] X_{k+mN} &= X_k \end{split} \end{equation*}$$

---

3. Shift

$$\begin{equation*} \begin{split} x_{n-p} &\longleftrightarrow e^{-j2\pi pk/N} X_k \\[0.3cm] x_n e^{j 2\pi pk/N} &\longleftrightarrow X_{k-p} \end{split} \end{equation*}$$

---

4. Conjugation in time

$$\begin{equation*} x^*_{n} \longleftrightarrow X^*_{N-k} \end{equation*}$$

---

5. Time and Frequency Reversal

$$\begin{equation*} \begin{split} x_n &\longleftrightarrow X_k \\[0.3cm] x_{N-n} &\longleftrightarrow X_{N-k} \end{split} \end{equation*}$$

---

6. Symmetry

$$\begin{equation*} \begin{split} x_n \text{ real and even} \longleftrightarrow X_k \text{ real and even}\\[0.3cm] x_n \text{ real and odd} \longleftrightarrow X_k \text{ imag and odd} \end{split} \end{equation*}$$

---

7. Circular Convolution

$$\begin{equation*} x_n * y_n = \sum\limits_{k=0}^{N-1 }x_k y_{n-k} \end{equation*}$$ $$\begin{equation*} x_n * y_n \longleftrightarrow \frac{1}{N} X_k Y_k \end{equation*}$$

---

8. Circular Correlation

$$\begin{equation*} x_n \star y_n \longleftrightarrow \frac{1}{N} X_k Y_k^* \end{equation*}$$

---

Number of Samples

---