This page is optimized for mobile devices, if you would prefer the desktop version just
click here
The dft is linear
As the DFT of a signal amounts to being a weighted sum, it follows naturally that the DFT operation is linear. So if we have two arbitrary signals $x_1[n]$ and $x_2[n]$ (with DFTs $X_1[k]$ and $X_2[k]$) and arbitrary constants $\alpha_1$ and $\alpha_2$, then the DFT of $\alpha_1 x_1[n]+\alpha_2 x_2[n]$ is simply $\alpha_1 X_1[k]+\alpha_2 X_2[k]$: $x_1[n]~\stackrel{\textrm{DFT}}{\longleftrightarrow}~ X_1[k], ~~x_2[n] ~\stackrel{\textrm{DFT}}{\longleftrightarrow}~ X_2[k]\\ \alpha_1 x_1[n]+ \alpha_2 x[2] ~\stackrel{\textrm{DFT}}{\longleftrightarrow}~ \alpha_1 X_1[k]+ \alpha_2 X_2[k]$The proof is straightforward: $\begin{align*}\textrm{DFT}\{\alpha_1 x_1[n]+ \alpha_2 x_2[n]\}&=\sum_{n=0}^{N-1} (\alpha_1 x_1[n] + \alpha_2 x[2]) e^{-j \frac{2\pi}{N}kn}\\&=(\alpha_1\sum_{n=0}^{N-1} x_1[n]e^{-j \frac{2\pi}{N}kn}) + (\alpha_2\sum_{n=0}^{N-1}x_2[n]e^{-j \frac{2\pi}{N}kn})\\&=\alpha_1 X_1[k] + \alpha_2 X_2[k]\end{align*}$
The convolution/multiplication time/frequency relationship
We now reach perhaps the most significant DFT property, the relationship between convolution and multiplication in time and frequency. Suppose we have 2 discrete-time finite length signals $x_1[n]$ and $x_2[n]$, whose DFTs are $X_1[k]$ and $X_2[k]$. Let $y[n]$ be the circular convolution $y[n]=x_1[n]\circledast x_2[n]$. Then the DFT of $y[n]$ is equivalent to the product of the DFTs of $x_1[n]$ and $x_2[n]$: $Y[k]=X_1[k]X_2[k]$. Or, to express this relationship in DFT pair notation, we have: $x_1[n]\circledast x_2[n] \stackrel{\textrm{DFT}}{\longleftrightarrow} X_1[k]X_2[k]$The proof of this relationship will use the $r=(n-m)_N=n-m+lN$ change of variable we used earlier. $\begin{align*}\textrm{DFT}\{x_1[n]\circledast x_2[n]\}&=~ \sum_{n=0}^{N-1} \left( \sum_{m=0}^{N-1} \: x_1[(n-m)_N] \, x_2[m]\right) e^{-j\frac{2\pi}{N}k n} \\&= \sum_{m=0}^{N-1} x_2[m] \left( \sum_{n=0}^{N-1} x_1[(n-m)_N]e^{-j\frac{2\pi}{N}k n} \right)\\&=\sum_{m=0}^{N-1} x_2[m] \left( \sum_{r=0}^{N-1} x_1[r]e^{-j\frac{2\pi}{N}k (r+m+lN)} \right) \\&=\sum_{m=0}^{N-1} x_2[m] \left( \sum_{r=0}^{N-1} x_1[r]e^{-j\frac{2\pi}{N}kr}e^{-j\frac{2\pi}{N}k m}e^{-j\frac{2\pi}{N}klN} \right) \\&= \left( \sum_{m=0}^{N-1} x_2[m] e^{-j\frac{2\pi}{N}km} \right) \left( \sum_{r=0}^{N-1} x_1[r]e^{-j\frac{2\pi}{N}kr} \right)\\&=X_1[k]X_2[k]\end{align*}$ So we see that convolution in two signals' time corresponds to their multiplication in frequency. It is certainly an interesting relationship, but it is also very practical: $N$ multiplications in the frequency domain is obviously much than the $N^2$ multiplications required to compute for an $N$-length signal. Of course, this requires first that the DFT of the two signals be computed, but we will see there are ways to compute that efficiently. What it all means is that a system's output (which is found via convolution) can be computed efficiently by way of multiplication in the frequency domain.
Dft symmetry properties
As the DFT is a weighted sum of complex signals (complex harmonic sinusoids), it follows that the DFT of signals is, in general, complex-valued.This symmetry was not a coincidence for the DFT of that particular $x[n]$; because the complex harmonic sinusoid signals that make up the DFT sum formula are conjugate symmetric (the real part is even, the imaginary part is odd), the DFTs of all purely real signals will also be conjugate symmetric. The converse is true for purely imaginary signals; their DFTs will be symmetric such that the real part is odd and the imaginary part is even. If, in addition to being purely real or purely imaginary, the signal itself is also even or odd, that will further limit the characteristics of its DFT. All of these DFT symmetry properties are listed on the table below:DFT SYMMETRY TABLE
Read also:
OpenStax, Discrete-time signals and systems. OpenStax CNX. Oct 07, 2015 Download for free at https://legacy.cnx.org/content/col11868/1.2
Google Play and the Google Play logo are trademarks of Google Inc.