DSP - Transformada rápida de Fourier

En métodos DFT anteriores, hemos visto que la parte computacional es demasiado larga. Queremos reducir eso. Esto se puede hacer mediante FFT o transformada rápida de Fourier. Entonces, podemos decir que FFT no es más que el cálculo de la transformada discreta de Fourier en un formato algorítmico, donde la parte computacional se reducirá.

La principal ventaja de tener FFT es que a través de ella podemos diseñar los filtros FIR. Matemáticamente, la FFT se puede escribir de la siguiente manera;

$$ x [K] = \ Displaystyle \ sum \ limits_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$

Tomemos un ejemplo para entenderlo mejor. Hemos considerado ocho puntos nombrados desde $ x_0 \ quad a \ quad x_7 $. Elegiremos los términos pares en un grupo y los impares en el otro. A continuación se muestra una vista esquemática de lo anterior -

Aquí, los puntos x ₀ , x ₂ , x ₄ y x ₆ se han agrupado en una categoría y, de manera similar, los puntos x ₁ , x ₃ , x ₅ y x ₇ se han colocado en otra categoría. Ahora, podemos hacerlos en un grupo de dos y podemos proceder con el cálculo. Ahora, veamos cómo esta división en dos más está ayudando en el cálculo.

$ x [k] = \ displaystyle \ sum \ limits_ {r = 0} ^ {\ frac {N} {2} -1} x [2r] W_N ^ {2rk} + \ displaystyle \ sum \ limits_ {r = 0 } ^ {\ frac {N} {2} -1} x [2r + 1] W_N ^ {(2r + 1) k} $

$ = \ sum_ {r = 0} ^ {\ frac {N} {2} -1} x [2r] W_ {N / 2} ^ {rk} + \ sum_ {r = 0} ^ {\ frac {N } {2} -1} x [2r + 1] W_ {N / 2} ^ {rk} \ times W_N ^ k $

$ = G [k] + H [k] \ veces W_N ^ k $

Inicialmente, tomamos una secuencia de ocho puntos, pero luego la dividimos en dos partes G [k] y H [k]. G [k] representa la parte par mientras que H [k] representa la parte impar. Si queremos realizarlo a través de un diagrama, entonces se puede mostrar a continuación:

En la figura anterior, podemos ver que

$ W_8 ^ 4 = -1 $

$ W_8 ^ 5 = -W_8 ^ 1 $

$ W_8 ^ 6 = -W_8 ^ 2 $

$ W_8 ^ 7 = -W_8 ^ 3 $

Del mismo modo, los valores finales se pueden escribir de la siguiente manera:

$ G [0] -H [0] = x [4] $

$ G [1] -W_8 ^ 1H [1] = x [5] $

$ G [2] -W_8 ^ 2H [2] = x [6] $

$ G [1] -W_8 ^ 3H [3] = x [7] $

La anterior es una serie periódica. La desventaja de este sistema es que K no se puede romper más allá de los 4 puntos. Ahora, analicemos lo anterior en más. Conseguiremos las estructuras algo como esto

Ejemplo

Considere la secuencia x [n] = {2,1, -1, -3,0,1,2,1}. Calcule la FFT.

Solution - La secuencia dada es x [n] = {2,1, -1, -3,0,1,2,1}

Organice los términos como se muestra a continuación;