DSP - Transformée de Fourier rapide

Dans les méthodes DFT précédentes, nous avons vu que la partie calcul est trop longue. Nous voulons réduire cela. Cela peut être fait par FFT ou transformée de Fourier rapide. Ainsi, nous pouvons dire que la FFT n'est rien d'autre qu'un calcul de transformée de Fourier discrète dans un format algorithmique, où la partie calcul sera réduite.

Le principal avantage d'avoir FFT est que grâce à elle, nous pouvons concevoir les filtres FIR. Mathématiquement, la FFT peut être écrite comme suit;

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

Prenons un exemple pour mieux le comprendre. Nous avons considéré huit points nommés de $ x_0 \ quad à \ quad x_7 $. Nous choisirons les termes pairs dans un groupe et les termes impairs dans l'autre. Une vue schématique de ce qui précède a été montrée ci-dessous -

Ici, les points x ₀ , x ₂ , x ₄ et x ₆ ont été regroupés dans une catégorie et de même, les points x ₁ , x ₃ , x ₅ et x ₇ ont été placés dans une autre catégorie. Maintenant, nous pouvons en outre les faire par groupe de deux et procéder au calcul. Voyons maintenant comment la division en deux autres aide au calcul.

$ 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} \ fois W_N ^ k $

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

Au départ, nous avons pris une séquence de huit points, mais plus tard, nous avons divisé cette séquence en deux parties G [k] et H [k]. G [k] représente la partie paire tandis que H [k] représente la partie impaire. Si nous voulons le réaliser à travers un diagramme, alors cela peut être montré comme ci-dessous -

À partir de la figure ci-dessus, nous pouvons voir que

$ W_8 ^ 4 = -1 $

$ W_8 ^ 5 = -W_8 ^ 1 $

$ W_8 ^ 6 = -W_8 ^ 2 $

$ W_8 ^ 7 = -W_8 ^ 3 $

De même, les valeurs finales peuvent être écrites comme suit -

$ 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] $

Celui ci-dessus est une série périodique. L'inconvénient de ce système est que K ne peut pas être cassé au-delà de 4 points. Maintenant, décomposons ce qui précède en plus. Nous obtiendrons les structures quelque chose comme ça