Discrete Fourier Transforms

Definition

Let $x[n]$$\large x[n]$ be a discrete-time signal. Then,

where $W_N=e^{-j\frac{2\pi }{N}}$$\large W_N = e^{-j \frac{2\pi}{N}}$ and $X[k],0\le k<N$$\large X[k], \:\: 0 \le k \lt N$ are the Discrete Fourier Transform coefficients of $x[n]$$\large x[n]$.

Conversely,

can be defined as the Inverse Discrete Fourier Transform to recover $N$$\large N$ samples of $x[n]$$\large x[n]$.

Properties

Linearity

• $y[n]=c_1{x}_1[n]+c_2{x}_2[n]⟺c_1{X}_1[k]+c_2{X}_2[k]$$\Large y[n] = c_1x_1[n] + c_2x_2[n] \iff c_1X_1[k] + c_2X_2[k]$

Time-Reversal Circular Symmetry

• $y[n]=x[⟨-n{⟩}_N]⟺Y[k]=X^{\ast }[k]$$\Large y[n] = x[\langle -n \rangle_N] \iff Y[k] = X^*[k]$

where $x[⟨-n{⟩}_N]=n\text{mod}N$$\large x[\langle -n \rangle_N] = n \:\text{mod}\: N$, and,

• $x[n]$$\Large x[n]$ is circular even $⟺x[n]=x[⟨-n{⟩}_N]$$\Large \iff x[n] = x[\langle -n \rangle_N]$
• $x[n]$$\Large x[n]$ is circular odd $⟺x[n]=-x[⟨-n{⟩}_N]$$\Large \iff x[n] = -x[\langle -n \rangle_N]$

Conjugation

• $y[n]=x^{\ast }[n]⟺X^{\ast }[⟨-k{⟩}_N]$$\Large y[n] = x^*[n] \iff X^*[\langle -k \rangle_N]$

Duality

• $y[n]=X[n]⟺Nx[⟨-k{⟩}_N]$$\Large y[n] = X[n] \iff Nx[\langle -k \rangle_N]$

Circular Time Shift

• $y[n]=x[⟨n-m{⟩}_N]⟺Y[k]=W_N^{mk}X[k]$$\Large y[n] = x[\langle n - m \rangle_N] \iff Y[k] = W_N^{mk} X[k]$

Circular Convolution

• $y[n]=(x\overline{)N}h)[n]⟺Y[k]=X[k]H[k]$$\Large y[n] = (x \:\enclose{circle}{N}\: h)[n] \iff Y[k] = X[k] H[k]$

where,

Circular Correlation

• $r_{xy}[n]=x[n]\overline{)N}y[⟨-n{⟩}_N]⟺R[k]=X[k]Y^{\ast }[k]$$\Large r_{xy}[n] = x[n] \:\enclose{circle}{N}\: y[\langle -n \rangle_N] \iff R[k] = X[k] Y^*[k]$

where,

Frequency Shifting

• $y[n]=W_N^{-mn}x[n]⟺Y[k]=X[⟨k-m{⟩}_N]$$\Large y[n] = W_N^{-mn} x[n] \iff Y[k] = X[\langle k - m \rangle_N]$

Frequency Modulation

• $y[n]=x[n]k_{0}n\cos \left(\frac{2\pi }{N}\right)⟺Y[k]=\frac{1}{2}X[⟨k+k_0{⟩}_N]+\frac{1}{2}X[⟨k-k_0{⟩}_N]$$\Large y[n] = x[n] k_0n \cos(\frac{2\pi}{N}) \iff Y[k] = \frac{1}{2} X[\langle k + k_0 \rangle_N] + \frac{1}{2} X[\langle k - k_0 \rangle_N]$

Windowing

• $y[n]=x[n]w[n]⟺\frac{1}{N}X[k]\overline{)N}W[k]$$\Large y[n] = x[n] w[n] \iff \frac{1}{N} X[k] \:\enclose{circle}{N}\: W[k]$

Parseval's Theorem

• $y[n]=\sum _{n=0}^{N-1}x[n]h^{\ast }[n]⟺Y[k]=\frac{1}{N}\sum _{k=0}^{N-1}X[k]Y^{\ast }[k]$$\Large y[n] = \sum\limits^{N - 1}_{n = 0} x[n] h^*[n] \iff Y[k] = \frac{1}{N} \sum\limits^{N - 1}_{k = 0} X[k] Y^*[k]$
• $y[n]=\sum _{n=0}^{N-1}{|x[n]|}^2⟺Y[k]=\frac{1}{N}\sum _{k=0}^{N-1}{|X[k]|}^2$$\Large y[n] = \sum\limits^{N - 1}_{n = 0} \abs{x[n]}^2 \iff Y[k] = \frac{1}{N} \sum\limits^{N - 1}_{k = 0} \abs{X[k]}^2$