Ο Fast Fourier Transform (FFT) είναι ένας αποτελεσματικός αλγόριθμος για την υπολογιστική του Discrete Fourier Transform (DFT). Ο αλγόριθμος Cooley-Tukey είναι η πιο συνηθισμένη μέθοδος για την εφαρμογή του FFT, βασιζόμενος στην αναδρομική αποσύνθεση του DFT. Η κατανόηση των μαθηματικών του θεμελίων βοηθά στη βελτιστοποίηση και την αποτελεσματική εφαρμογή του αλγόριθμου.

Μαθηματική βάση της FFT

Το DFT μετατρέπει μια ακολουθία σύνθετων αριθμών σε συστατικά συχνότητας. Ορίζεται ως:

X(k) = ⁇ n=0]N-1 x(n) e-2pi kn/N

όπου x(n) είναι η ακολουθία εισόδου, X(k) είναι το συστατικό συχνότητας, και N] είναι το μήκος ακολουθίας.

Η δημιουργία του Αλγόριθμου Κούλεϊ-Τούκεϊ

Ο αλγόριθμος Cooley-Tukey αποσυνθέτει το DFT σε μικρότερα DFTs διαιρώντας την ακολουθία σε ομοιόμορφα και παράξενα μέρη:

X(k) = ⁇ [n=0N-1 x(n) e-2pi kn/N]

που μπορεί να ξαναγραφεί ως:

X(k) = ⁇ [n=0]N/2-1 x(2n) e-2pi 2n k/N] + e-2pi k/N] ⁇ n=0]N/2-1 x(2n+1) e]-2pi 2n k/N

Αυτός ο διαχωρισμός επιτρέπει αναδρομικό υπολογισμό των μικρότερων DFTs, μειώνοντας την υπολογιστική πολυπλοκότητα από O(N2) σε O(N log N).

Εφαρμογή του Αλγόριθμου

Ο αλγόριθμος FFT εφαρμόζει την αναδρομική αποσύνθεση επανειλημμένα μέχρι να επιτευχθεί η βασική περίπτωση του μεγέθους 1. Τα αποτελέσματα στη συνέχεια συνδυάζονται χρησιμοποιώντας συντελεστές του μέσου, οι οποίοι είναι σύνθετοι εκθετικοί όροι:

W[N](k) = e-2pi k/N

Οι παράγοντες αυτοί προσαρμόζουν τη φάση των μικρότερων DFTs κατά τον ανασυνδυασμό, επιτρέποντας τον αποτελεσματικό υπολογισμό του πλήρους μετασχηματισμού.