11.1 Transformación discreta de fourier

N-puinto punto transformada discreta de fourier (dft)

Note que:

• $X(k)$ es la DTFT evaluado en $\omega =\frac{2\pi }{N}k\forall k, k=\{0, \dots , N-1\}$
• Completar con ceros $x(n)$ a $M$ muestras antes de sacar el DFT, da como resultado una versión muestreada de $M$ -puntos uniformes del DTFT :
  $X(e^{i\frac{2\pi }{M}k})=\sum_{n=0}^{N-1} x(n)e^{-i\frac{2\pi }{M}k}$
  $$X(e^{i\frac{2\pi }{M}k})=\sum_{n=0}^{N-1} x_{\mathrm{zp}}(n)e^{-i\frac{2\pi }{M}k}$$ $$X(e^{i\frac{2\pi }{M}k})=X_{\mathrm{zp}}(k)\forall k, k=\{0, \dots , M-1\}$$
• La $N$ -pt DFT es suficiente para reconstruir toda la DTFT de una secuencia de $N$ -pt:
  $X(e^{i\omega })=\sum_{n=0}^{N-1} x(n)e^{-i\omega n}$
  $$X(e^{i\omega })=\sum_{n=0}^{N-1} \frac{1}{N}\sum_{k=0}^{N-1} X(k)e^{i\frac{2\pi }{N}kn}e^{-i\omega n}$$ $$X(e^{i\omega })=\sum_{k=0}^{N-1} X(k)\frac{1}{N}\sum_{k=0}^{N-1} e^{-i(\omega -\frac{2\pi }{N}k)n}$$ $$X(e^{i\omega })=\sum_{k=0}^{N-1} X(k)\frac{1}{N}\frac{\sin \left(\frac{\omega N-2\pi k}{2}\right)}{\sin \left(\frac{\omega N-2\pi k}{2N}\right)}e^{-i(\omega -\frac{2\pi }{N}k)\frac{N-1}{2}}$$

• DFT tiene una representación en forma de matriz muy conveniente. Definiendo $W_N=e^{-i\frac{2\pi }{N}}$ ,
  $\begin{pmatrix}X(0)\\ X(1)\\ ⋮\\ X(N-1)\\ \end{pmatrix}=\begin{pmatrix}{W}_N^0 & W_N^0 & W_N^0 & W_N^0 & \dots \\ W_N^0 & W_N^1 & W_N^2 & W_N^3 & \dots \\ W_N^0 & W_N^2 & W_N^4 & W_N^6 & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮\\ \end{pmatrix}\begin{pmatrix}x(0)\\ x(1)\\ ⋮\\ x(N-1)\\ \end{pmatrix}$
  donde $X=W(x)$ respectivamente. $W$ tiene las siguientes propiedades:
  • $W$ es Vandermonde: La $n$ th columna de $W$ es un polinomio en $W_N^n$
  • $W$ es simetrico: $W=W^T$
  • $\frac{1}{\sqrt{N}}W$ es unitaria: $\frac{1}{\sqrt{N}}W(\frac{1}{\sqrt{N}}W)^H=(\frac{1}{\sqrt{N}}W)^H\frac{1}{\sqrt{N}}W=I$
  • $\frac{1}{N}\overline{W}=W^{-1}$ , es la matriz y DFT.
• • Para $N$ un poder de 2, la FFT se puede usar para calcular la DFT usando $\frac{N}{2}\log_{2}N$ en vez de $N^2$ operaciones.