Transformada Discreta de Fourier (DFT)

La Transformada Discreta de Fourier (DFT) de una señal digital x[n] es equivalente a realizar un muestreo de la Transformada de Fourier (TF) de la señal en el dominio continuo x(t):

Denotaremos a X[k] como la DFT de x[n]:

X[k] = DFT {x[n]} ········ X(f) = TF {x(t)} ········ X[k] = Muestreo {X(f)}

Propiedades importantes de la DFT son:

• Linealidad: siendo N=max(N1,N2)
• Desplazamiento: Hablaremos de un desplazamiento circular que es el que tiene sentido aquí.

x[((n-n0))N] <==> X[k]*{-exp[2*pi*(k/N)*n]} ; siendo ((n))N la función Módulo N

• Dualidad
• Modulación
• Simetría: X[k] tendrá simetría Hermítica.
  
• Producto en frecuencia (convolución en el tiempo): Usaremos una convolución circular.

Una de las utilidades de la DFT es Filtrar eficientemente (computacionalmente hablando), utilizando para ello el recurso de la convolución lineal.

Métodos de implementación de Filtros LTI (Linear Time Invariante) usando DFT:
Permiten filtrar una señal mediante DFT "por trozos" para poder trabajar en tiempo real, no esperar a tener toda la señal; útil por tanto para señales "largas".

1. Overlap-And-Sum: Utiliza convolución lineal
   
2. Overlap-And-Save: Utiliza convolución circular

El cálculo eficiente de la DFT en un procesador se realiza mediante la implementación del algoritmo FFT (Fast Fourier Transform), que data del año 1964!.
Posibilidades de implementación (buscamos eficiencia):

• Algoritmo FFT de diezmado en el Tiempo: se trata de dividir las muestras de x[n] en pares e impares (el número de muestras total debe ser par) de forma iterativa, hasta reducir el número de muestras a tratar a dos.
  Se utilizan estructuras de mariposa o mariposa simplificada para representar gráficamente el algoritmo.
  
• Algoritmo FFT de diezmado en Frecuencia: La estrategia es similar, pero la división de las muestras se realiza sobre la transformada DFT X[n].