Apa saja perbedaan antara DFT dan FFT yang membuat FFT begitu cepat?

Saya mencoba memahami FFT, inilah yang saya miliki sejauh ini:

Untuk menemukan besarnya frekuensi dalam bentuk gelombang, kita harus menyelidikinya dengan mengalikan gelombang dengan frekuensi yang mereka cari, dalam dua fase berbeda (sin dan cos) dan rata-rata masing-masing. Fase ditemukan oleh hubungannya dengan keduanya, dan kode untuk itu adalah sesuatu seperti ini:

//simple pseudocode
var wave = [...];                //an array of floats representing amplitude of wave
var numSamples = wave.length;
var spectrum = [1,2,3,4,5,6...]  //all frequencies being tested for.  

function getMagnitudesOfSpectrum() {
   var magnitudesOut = [];
   var phasesOut = [];

   for(freq in spectrum) {
       var magnitudeSin = 0;
       var magnitudeCos = 0;

       for(sample in numSamples) {
          magnitudeSin += amplitudeSinAt(sample, freq) * wave[sample];
          magnitudeCos += amplitudeCosAt(sample, freq) * wave[sample];
       }

       magnitudesOut[freq] = (magnitudeSin + magnitudeCos)/numSamples;
       phasesOut[freq] = //based off magnitudeSin and magnitudeCos
   }

   return magnitudesOut and phasesOut;
}

Untuk melakukan ini untuk frekuensi yang sangat banyak dengan sangat cepat, FFT menggunakan banyak trik.

Apa saja trik yang digunakan untuk membuat FFT jauh lebih cepat daripada DFT?

PS Saya sudah mencoba melihat algoritma FFT yang sudah selesai di web, tetapi semua trik cenderung diringkas menjadi satu bagian kode yang indah tanpa banyak penjelasan. Yang saya butuhkan pertama, sebelum saya bisa memahami semuanya, adalah beberapa pengantar untuk setiap perubahan efisien ini sebagai konsep.

Terima kasih.

Pelaksanaan naif dari -titik DFT pada dasarnya adalah perkalian oleh N × N matriks. Ini menghasilkan kompleksitas O ( N 2$N$$N \times N$$\mathcal{O}(N^2)$ .

Salah satu algoritma Fast Fourier Transform (FFT) yang paling umum adalah radix-2 Cooley-Tukey algoritma FFT penipisan-in-Time. Ini adalah pendekatan pembagian dan penaklukan dasar.

Pertama menentukan "faktor bermalas" sebagai: dimanaj≜

$$W_N \triangleq e^{-j\frac{2\pi}{N}}$$ adalah unit imajiner, maka DFTX[k]darix[n]diberikan oleh X[k]= N - 1 ∑ n = 0 x[n$j \triangleq \sqrt{-1}$$X[k]$$x[n]$ Jika N adalah genap (dan $$X[k] = \sum_{n=0}^{N-1} x[n] \, W_N^{kn} \, .$$ $N$ adalah bilangan bulat), jumlah yang kemudian dapat dibagi dalam dua jumlah sebagai berikut X[k]= N / 2 - 1 Σ n=0x[2n]W 2 k n N + N / 2 - 1 Σ n=0x[2n+1]W k ( 2 n + 1 )$\tfrac{N}{2}$ $$X[k] = \sum_{n=0}^{N/2-1} x[2n]W_N^{2kn} + \sum_{n=0}^{N/2-1} x[2n+1]W_N^{k(2n+1)}$$ dimana penjumlahan pertama berurusan dengan sampel genap dan yang kedua dengan sampel ganjil x [ n ] . Mendefinisikan $x[n]$$x[n]$ dan x o [ n ] ≜ x [ 2 n + 1 ] dan menggunakan fakta bahwa$x_e[n] \triangleq x[2n]$$x_o[n] \triangleq x[2n+1]$

1. , dan$W_N^{k(2n+1)} = W_N^{2kn}W_N^k$
2. $W_N^{2kn} = W_{N/2}^{kn}$ ,

$$\begin{align} X[k] &= \sum_{n=0}^{N/2-1} x_e[n] W_{N/2}^{kn} + W_N^k\sum_{n=0}^{N/2-1} x_o[n]W_{N/2}^{kn} \\ & = X_e[k] + W_N^k X_o[k] \end{align}$$ $X_e[k]$$X_o[k]$$\tfrac{N}{2}$$x[n]$$N$$\tfrac{N}{2}$ $$2 \left( \frac{N}{2} \right)^2 + N < N^2$$ $N > 2$ .

$\mathcal{O}(N\log N)$$\mathcal{O}(N^2)$

http://nbviewer.jupyter.org/gist/leftaroundabout/83df89a7d3bdc24373ea470fb50be629

DFT, ukuran 16

FFT, ukuran 16

Perbedaan dalam kompleksitas cukup jelas dari itu, bukan?

---

Begini cara saya memahami FFT.

Pertama, saya akan selalu berpikir tentang transformasi Fourier terutama sebagai transformasi fungsi kontinu , yaitu pemetaan bijektif$\operatorname{FT} : \mathcal{L}^2(\mathbb{R}) \to \mathcal{L}^2(\mathbb{R})$. Dalam terang itu jelas bahwa itu tidak mungkin benar-benar perlu untuk pergi ke "level terdalam" dan loop atas elemen individu , karena "elemen individu" adalah titik tunggal pada garis nyata, di mana ada tak terhingga tak terhitung jumlahnya .

Jadi bagaimana transformasi ini masih didefinisikan dengan baik? Yah, sangat penting untuk beroperasi bukan pada ruang fungsi umum$\mathbb{R}\to\mathbb{C}$tetapi hanya pada ruang fungsi integrable (Lebesgue-, square-) . Sekarang, keterpaduan ini bukan properti yang sangat kuat (jauh lebih lemah daripada diferensiabilitas, dll.), Tetapi ia menuntut agar fungsi tersebut menjadi “dapat dijelaskan secara lokal dengan informasi yang dapat dihitung”. Discription seperti itu diberikan oleh koefisien Fourier Transform jangka pendek . ^†Kasus paling sederhana adalah bahwa fungsi Anda kontinu dan Anda membaginya dalam wilayah sangat kecil sehingga pada dasarnya konstan di masing-masing. Kemudian masing-masing STFT memiliki paling kuat istilah nol. Jika Anda mengabaikan (lagian membusuk) koefisien lainnya maka setiap domain hanya satu titik data tunggal. Dari semua koefisien waktu-pendek-LF-batas ini, Anda bisa mengambil transformasi Fourier diskrit. Bahkan, itulah yang Anda lakukan ketika melakukan FT apa pun pada data dunia nyata yang diukur!

Namun, data yang diukur tidak harus sesuai dengan kuantitas fisik dasar. Misalnya, ketika Anda mengukur intensitas cahaya , Anda benar-benar hanya mengukur amplitudo gelombang elektromagnetik yang frekuensinya terlalu tinggi untuk dicoba dengan ADC. Tapi yang jelas Anda juga dapat menghitung DFT dari sinyal intensitas cahaya sampel, dan murah, meskipun frekuensi gelombang cahaya gila.

Ini bisa dipahami karena alasan terpenting FFT murah:

Jangan repot-repot mencoba melihat siklus osilasi individu dari tingkat tertinggi. Alih-alih, ubah hanya informasi tingkat tinggi yang sudah diproses sebelumnya secara lokal.

Namun, tidak hanya itu yang ada. Hal yang hebat tentang FFT adalah masih memberi Anda semua informasi yang DFT lengkap akan berikan . Yaitu semua informasi yang juga akan Anda dapatkan ketika mengambil sampel gelombang elektromagnetik yang tepat dari sebuah berkas cahaya. Bisakah ini dicapai dengan mengubah sinyal fotodioda? - Dapatkah Anda mengukur frekuensi cahaya yang tepat dari itu?

Yah, jawabannya tidak, Anda tidak bisa. Yaitu, kecuali Anda menerapkan trik tambahan.
Pertama-tama, Anda perlu setidaknya sekitar mengukur frekuensi dalam blok waktu singkat. Ya, itu mungkin dengan spektograf. Tapi itu hanya mungkin sampai dengan ketepatan$\Delta \nu = 1/{\Delta t}$, hubungan ketidakpastian yang khas ^‡ .

Dengan memiliki keseluruhan rentang waktu yang lebih lama, kita juga harus dapat mempersempit ketidakpastian frekuensi. Dan ini memang mungkin, jika Anda mengukur secara lokal tidak hanya frekuensi kasar tetapi juga fase gelombang. Anda tahu bahwa sinyal 1000 Hz akan memiliki fase yang persis sama jika Anda melihatnya satu detik kemudian. Sedangkan sinyal 1000,5 Hz, sementara tidak dapat dibedakan dalam skala pendek, akan membalik fase satu detik kemudian.

Untungnya, informasi fase itu dapat disimpan dengan baik dalam satu bilangan kompleks. Dan itulah cara kerja FFT! Ini dimulai dengan banyak transformasi lokal kecil. Ini murah - untuk satu hal jelas karena mereka hanya menggunakan sejumlah kecil data, tetapi kedua karena mereka tahu bahwa, karena rentang waktu yang singkat, mereka tidak dapat menyelesaikan frekuensinya dengan sangat tepat - jadi tetap terjangkau meskipun Anda melakukan banyak transformasi seperti itu.

Ini, bagaimanapun, merekam juga fase , dan dari sana Anda kemudian dapat membuat resolusi frekuensi lebih tepat di tingkat atas. Transformasi yang diperlukan sekali lagi murah, karena itu sendiri tidak mengganggu osilasi frekuensi tinggi tetapi hanya dengan data frekuensi rendah pra-diproses.

---

^† _{Yup, argumentasi saya agak melingkar pada titik ini. Sebut saja itu rekursif dan kami baik-baik saja ...}

^‡ _{Hubungan ini adalah tidak kuantum mekanik, tetapi ketidakpastian Heisenberg memiliki sebenarnya alasan mendasar yang sama.}

Berikut adalah gambar untuk ditambahkan ke jawaban Robert yang bagus yang menunjukkan "penggunaan kembali" operasi, dalam hal ini untuk DFT 8 poin. "Faktor-faktor Twiddle" diwakili dalam diagram menggunakan notasi$W_N^{nk}$ yang sama dengan $e^{j2\pi \frac{nk}{N}}$

Perhatikan jalur yang ditunjukkan dan persamaan di bawahnya menunjukkan hasil untuk frekuensi bin X (1), seperti yang diberikan oleh persamaan Robert.

Garis putus-putus tidak berbeda dari garis padat hanya untuk memperjelas di mana penjumlahan bergabung.

pada dasarnya, dalam menghitung DFT naif langsung dari penjumlahan:

$$X[k] = \sum\limits_{n=0}^{N-1} x[n] \, e^{j 2 \pi \frac{nk}{N}}$$

Ada $N$ Tabel lookup untuk faktor twiddle $e^{j 2 \pi \frac{nk}{N}}$, $N$ perkalian yang kompleks, dan $N-1$tambahan. dan itu hanya untuk satu nilai$X[k]$ dan satu contoh dari $k$. kemudian DFT yang naif membuang semua data antara itu dan memeriksa semuanya lagi$X[k+1]$.

1. jadi FFT menyimpan beberapa data perantara.
2. FFT juga akan menggunakan faktor faktor twiddle sedikit sehingga faktor yang sama dapat digunakan untuk kombinasi data antara.

Saya orang yang visual. Saya lebih suka membayangkan FFT sebagai trik matriks daripada trik penjumlahan.

Untuk menjelaskan di tingkat tinggi:

DFT naif menghitung setiap sampel keluaran secara independen dan menggunakan setiap sampel input dalam setiap perhitungan (algoritma N² klasik).

FFT umum menggunakan simetri dan pola dalam definisi DFT untuk melakukan perhitungan dalam "lapisan" (lapisan log N), setiap lapisan dengan persyaratan waktu-konstan per sampel membuat algoritma N log N.

Lebih spesifik:

Salah satu cara untuk memvisualisasikan simetri ini adalah dengan melihat DFT sebagai input matriks 1 × N dikalikan dengan matriks NxN dari semua eksponensial kompleks Anda. Mari kita mulai dengan case "radix 2". Kita akan membagi baris genap dan ganjil dari matriks (sesuai dengan sampel input genap dan ganjil) dan menganggapnya sebagai dua perkalian matriks terpisah yang ditambahkan bersama untuk mendapatkan hasil akhir yang sama.

Sekarang lihatlah matriks-matriks ini: yang pertama setengah kiri identik dengan setengah kanan. Di sisi lain, setengah kanan adalah setengah kiri x −1. Ini berarti kita hanya perlu menggunakan setengah kiri dari matriks ini untuk perkalian dan membuat setengah kanan dengan murah dengan mengalikan dengan 1 atau −1. Selanjutnya, amati bahwa matriks kedua berbeda dari matriks pertama dengan faktor-faktor yang sama di setiap kolom, sehingga kita dapat memperhitungkan dan mengalikannya menjadi input sehingga sekarang sampel genap dan ganjil menggunakan matriks yang sama, tetapi membutuhkan pengali pertama. Dan langkah terakhir adalah mengamati bahwa matriks N / 2 × N / 2 yang dihasilkan ini identik dengan matriks DFT N / 2 dan kita dapat melakukan ini berulang-ulang hingga mencapai matriks 1 × 1 di mana DFT adalah fungsi identitas.

Untuk menggeneralisasi di luar radix 2, Anda dapat melihat pemisahan setiap baris ketiga dan melihat tiga potongan kolom, atau setiap 4 dll.

Dalam hal input berukuran prima, terdapat metode untuk zero-pad, FFT, dan truncate, tetapi itu berada di luar cakupan jawaban ini.

Lihat: http://whoiskylefinn.com/MatrixFFT.html

DFT melakukan pengganda matriks N ^ 2 dengan kekuatan kasar.

FFT memang melakukan trik-trik pintar, mengeksploitasi sifat-sifat matriks (degeneralisasi kelipatan matriks) untuk mengurangi biaya komputasi.

Mari kita lihat DFT kecil:

W = fft (mata (4));

x = rand (4,1) + 1j * rand (4,1);

X_ref = fft (x);

X = W * x;

menegaskan (maks (abs (X-X_ref)) <1e-7)

Sangat bagus sehingga kita dapat mengganti panggilan MATLAB ke perpustakaan FFTW dengan perkalian matriks 4x4 (kompleks) kecil dengan mengisi matriks dari fungsi FFT. Jadi seperti apa bentuk matriks ini?

N = 4,

Wn = exp (-1j * 2 * pi / N),

f = ((0: N-1) '* (0: N-1))

f =

 0     0     0     0
 0     1     2     3
 0     2     4     6
 0     3     6     9

W = Wn. ^ F

W =

1 1 1 1

1 -i -1 i

1 -1 1 -1

1 i -1 -i

Setiap elemen adalah +1, -1, + 1j atau -1j. Jelas, ini berarti bahwa kita dapat menghindari perkalian yang kompleks sepenuhnya. Selanjutnya, kolom pertama identik, artinya kita mengalikan elemen pertama x berulang dengan faktor yang sama.

Ternyata produk tensor Kronecker, "faktor dua arah" dan matriks permutasi di mana indeks diubah sesuai dengan representasi biner yang dibalik keduanya kompak dan memberikan perspektif alternatif tentang bagaimana FFT dihitung sebagai serangkaian operasi matriks yang jarang.

Baris di bawah ini adalah Decimation in Frequency (DIF) sederhana radix 2 forward FFT. Walaupun langkah-langkahnya mungkin terlihat rumit, lebih mudah untuk menggunakan kembali untuk FFT maju, terbalik, radix4 / split-radix atau penipisan waktu, sementara menjadi representasi yang adil tentang bagaimana FFT di tempat cenderung diterapkan di dunia nyata, Aku percaya.

N = 4;

x = randn (N, 1) + 1j * randn (N, 1);

T1 = exp (-1j * 2 * pi * ([nol (1, N / 2), 0: (N / 2-1)])). '/ N),

M0 = kron (mata (2), fft (mata (2))),

M1 = kron (fft (eye (2)), eye (2)),

X = bitrevorder (x. '* M1 * diag (T1) * M0),

X_ref = fft (x)

menegaskan (maks (abs (X (:) - X_ref (:))) <1e-6)

CF Van Loan memiliki buku yang bagus tentang hal ini.

Jika Anda ingin minum dari Firehose of Wisdom, saya sarankan:

"Transformasi Cepat - Algoritma, Analisis, Aplikasi" oleh Douglas F. Elliott, K. Ramamohan Rao

Ini mencakup FFT, Hartley, Winograd dan aplikasi.

Satu poin kuat adalah menunjukkan bagaimana FFT adalah seperangkat faktorisasi matriks jarang dengan urutan pembalikan bit.