Introduction to Discrete Time Signal Processing

DFT is given by X[k] = (1/N) Σ (x[n] e^(-j(2π/N)kn)) for n=0 to N-1

W_N = e^(-j(2π/N))

N(N-1)

N(N-1)

DFT{ax1[n] + bx2[n]} = aX1(k) + bX2(k)

If DFT{x[n]} = X(k), then DFT{x[N - n]} = X(N - k)

If DFT{x[n]} = X(k), then DFT{x[n – n0]} = X(k) e^(-j2πkn0/N)

If DFT{x1[n]} = X1(k) and DFT{x2[n]} = X2(k), then DFT{x1[n] * x2[n]} = X1(k) * X2(k)

If DFT{x1[n] * x2[n]} = 1/N {X1(k) * X2(k)} (Dual of Circular convolution)

DFT requires O(N^2) computations.