DSP - Trasformata di Fourier veloce

Nei metodi DFT precedenti, abbiamo visto che la parte computazionale è troppo lunga. Vogliamo ridurlo. Questo può essere fatto tramite FFT o trasformata di Fourier veloce. Quindi, possiamo dire che FFT non è altro che il calcolo della trasformata di Fourier discreta in un formato algoritmico, in cui la parte computazionale sarà ridotta.

Il vantaggio principale di avere FFT è che attraverso di esso, possiamo progettare i filtri FIR. Matematicamente, la FFT può essere scritta come segue;

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

Facciamo un esempio per capirlo meglio. Abbiamo considerato otto punti denominati da $ x_0 \ quad a \ quad x_7 $. Sceglieremo i termini pari in un gruppo e i termini dispari nell'altro. La vista schematica di quanto sopra è stata mostrata di seguito:

Qui, i punti x ₀ , x ₂ , x ₄ e x ₆ sono stati raggruppati in una categoria e, analogamente, i punti x ₁ , x ₃ , x ₅ e x ₇ sono stati inseriti in un'altra categoria. Ora possiamo crearli ulteriormente in un gruppo di due e procedere con il calcolo. Ora, vediamo come questi due ulteriori due aiutano nel calcolo.

$ 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] \ volte W_N ^ k $

Inizialmente, abbiamo preso una sequenza di otto punti, ma in seguito l'abbiamo divisa in due parti G [k] e H [k]. G [k] sta per la parte pari mentre H [k] sta per la parte dispari. Se vogliamo realizzarlo attraverso un diagramma, allora può essere mostrato come di seguito -

Dalla figura sopra, possiamo vederlo

$ W_8 ^ 4 = -1 $

$ W_8 ^ 5 = -W_8 ^ 1 $

$ W_8 ^ 6 = -W_8 ^ 2 $

$ W_8 ^ 7 = -W_8 ^ 3 $

Allo stesso modo, i valori finali possono essere scritti come segue:

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

Quella sopra è una serie periodica. Lo svantaggio di questo sistema è che K non può essere rotto oltre i 4 punti. Ora analizziamo ulteriormente quanto sopra. Otterremo le strutture qualcosa del genere

Esempio

Considera la sequenza x [n] = {2,1, -1, -3,0,1,2,1}. Calcola la FFT.

Solution - La sequenza data è x [n] = {2,1, -1, -3,0,1,2,1}

Disporre i termini come mostrato di seguito;