Memahami keluaran FFT

Saya butuh bantuan untuk memahami output dari komputasi DFT / FFT.

Saya seorang insinyur perangkat lunak berpengalaman dan perlu menafsirkan beberapa bacaan akselerometer ponsel cerdas, seperti menemukan frekuensi utama. Sayangnya, saya tidur sepanjang sebagian besar kelas EE kuliah saya lima belas tahun yang lalu, tetapi saya telah membaca tentang DFT dan FFT selama beberapa hari terakhir (tampaknya sedikit berhasil).

Tolong, tidak ada tanggapan "ambil kelas EE". Saya sebenarnya berencana melakukan itu jika majikan saya akan membayar saya. :)

Jadi inilah masalah saya:

Saya telah menangkap sinyal pada 32 Hz. Berikut adalah sampel 1 detik dari 32 poin, yang telah saya buat grafiknya di Excel.

Saya kemudian mendapat beberapa kode FFT yang ditulis di Java dari Columbia University (setelah mengikuti saran dalam posting di " FFT handal dan cepat di Java ").

Output dari program ini adalah sebagai berikut. Saya yakin ini menjalankan FFT di tempat, jadi ini menggunakan kembali buffer yang sama untuk input dan output.

Before: 

Re: [0.887  1.645  2.005  1.069  1.069  0.69  1.046  1.847  0.808  0.617  0.792  1.384  1.782  0.925  0.751  0.858  0.915  1.006  0.985  0.97  1.075  1.183  1.408  1.575  1.556  1.282  1.06  1.061  1.283  1.701  1.101  0.702  ]

Im: [0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  ]

After: 

Re: [37.054  1.774  -1.075  1.451  -0.653  -0.253  -1.686  -3.602  0.226  0.374  -0.194  -0.312  -1.432  0.429  0.709  -0.085  0.0090  -0.085  0.709  0.429  -1.432  -0.312  -0.194  0.374  0.226  -3.602  -1.686  -0.253  -0.653  1.451  -1.075  1.774  ]

Im: [0.0  1.474  -0.238  -2.026  -0.22  -0.24  -5.009  -1.398  0.416  -1.251  -0.708  -0.713  0.851  1.882  0.379  0.021  0.0  -0.021  -0.379  -1.882  -0.851  0.713  0.708  1.251  -0.416  1.398  5.009  0.24  0.22  2.026  0.238  -1.474  ]

Jadi, pada titik ini, saya tidak bisa membuat head atau tail output. Saya memahami konsep DFT, seperti bagian sebenarnya adalah amplitudo gelombang kosinus komponen dan bagian imajinernya adalah amplitudo gelombang sinus komponen. Saya juga dapat mengikuti diagram ini dari buku hebat " The Scientist and Engineer's Guide to Digital Signal Processing ":

Jadi pertanyaan spesifik saya adalah:

1. Dari keluaran FFT, bagaimana cara menemukan "frekuensi yang paling sering terjadi"? Ini adalah bagian dari analisis saya terhadap data akselerometer saya. Haruskah saya membaca array nyata (cosinus) atau imajiner (sinus)?

2. Saya memiliki input 32-poin dalam domain waktu. Bukankah seharusnya keluaran dari FFT berupa larik 16 elemen untuk real dan larik 16 elemen untuk imajiner? Mengapa program ini memberi saya keluaran larik nyata dan imajiner, keduanya berukuran 32?

3. Terkait dengan pertanyaan sebelumnya, bagaimana cara mengurai indeks dalam larik keluaran? Mengingat input saya dari 32 sampel yang diambil sampelnya pada 32 Hz, pemahaman saya adalah bahwa output array 16-elemen harus memiliki indeksnya tersebar secara seragam hingga 1/2 tingkat pengambilan sampel (dari 32 Hz), jadi saya benar dalam memahami bahwa setiap elemen dari array mewakili (32 Hz * 1/2) / 16 = 1 Hz?

4. Mengapa keluaran FFT memiliki nilai negatif? Saya pikir nilai mewakili amplitudo dari sinusoid. Sebagai contoh, keluaran dari Real [3] = -1.075 berarti amplitudo -1.075 untuk gelombang kosinus frekuensi 3. Apakah benar? Bagaimana amplitudo bisa negatif?

1. Anda tidak boleh mencari bagian nyata atau imajinatif dari bilangan kompleks (yang merupakan larik nyata dan imajiner Anda). Sebagai gantinya Anda ingin mencari besaran frekuensi yang didefinisikan sebagai akar persegi (real * real + imag * imag). Angka ini akan selalu positif. Sekarang yang harus Anda cari adalah nilai maksimum (abaikan entri pertama dalam array Anda. Itu adalah offset DC Anda dan tidak membawa informasi yang bergantung pada frekuensi).

2. Anda mendapatkan 32 keluaran nyata dan 32 hasil imajiner karena Anda menggunakan FFT kompleks hingga kompleks. Ingatlah bahwa Anda telah mengubah 32 sampel Anda menjadi 64 nilai (atau 32 nilai kompleks) dengan memperluasnya tanpa bagian imajiner. Ini menghasilkan keluaran FFT simetris di mana hasil frekuensi muncul dua kali. Setelah siap digunakan dalam output 0 hingga N / 2, dan setelah dicerminkan dalam output N / 2 ke N. Dalam kasus Anda, yang paling mudah adalah mengabaikan output N / 2 ke N. Anda tidak membutuhkannya, mereka hanya artefak tentang bagaimana Anda menghitung FFT Anda.

3. Persamaan frekuensi ke fft-bin adalah (bin_id * freq / 2) / (N / 2) di mana freq adalah frekuensi sampel Anda (alias 32 Hz, dan N adalah ukuran FFT Anda). Dalam kasus Anda, ini disederhanakan menjadi 1 Hz per bin. Tempat sampah N / 2 ke N mewakili frekuensi negatif (konsep aneh, saya tahu). Untuk kasus Anda, mereka tidak mengandung informasi penting karena mereka hanyalah cermin dari frekuensi N / 2 pertama.

4. Bagian nyata dan imajiner Anda dari setiap nampan membentuk bilangan kompleks. Tidak apa-apa jika bagian nyata dan imajiner negatif sedangkan besaran frekuensinya sendiri positif (lihat jawaban saya untuk pertanyaan 1). Saya menyarankan agar Anda membaca tentang bilangan kompleks. Menjelaskan bagaimana mereka bekerja (dan mengapa mereka berguna) melebihi apa yang mungkin untuk dijelaskan dalam satu pertanyaan stackoverflow.

Catatan: Anda mungkin juga ingin membaca apa itu autokorelasi, dan bagaimana hal itu digunakan untuk mencari frekuensi fundamental sebuah sinyal. Saya merasa inilah yang sebenarnya Anda inginkan.

Anda sudah memiliki beberapa jawaban yang bagus, tetapi saya hanya akan menambahkan bahwa Anda benar-benar perlu menerapkan fungsi jendela ke data domain waktu Anda sebelum FFT, jika tidak, Anda akan mendapatkan artefak buruk dalam spektrum Anda, karena kebocoran spektral .

1) Cari indeks dalam larik nyata dengan nilai tertinggi, selain yang pertama (itu adalah komponen DC). Anda mungkin membutuhkan sample rate yang jauh lebih tinggi dari 32 Hz, dan ukuran window yang lebih besar, untuk mendapatkan hasil yang berarti.

2) Paruh kedua dari kedua larik adalah cermin dari paruh pertama. Misalnya, perhatikan bahwa elemen terakhir dari larik nyata (1.774) sama dengan elemen kedua (1.774), dan elemen terakhir dari larik imajiner (1.474) adalah negatif dari elemen kedua.

3) Frekuensi maksimum yang dapat Anda ambil pada laju sampel 32 Hz adalah 16 Hz ( batas Nyquist ), jadi setiap langkah adalah 2 Hz. Seperti disebutkan sebelumnya, ingat bahwa elemen pertama adalah 0 Hz (yaitu, offset DC).

4) Tentu, amplitudo negatif sangat masuk akal. Ini hanya berarti bahwa sinyal "dibalik" - FFT standar didasarkan pada kosinus, yang biasanya bernilai = 1 pada t = 0, sehingga sinyal yang memiliki nilai = -1 pada waktu = 0 akan memiliki amplitudo negatif .

Perhatikan bahwa "frekuensi yang paling sering terjadi" dapat terpecah menjadi beberapa kotak FFT, bahkan dengan fungsi jendela. Jadi, Anda mungkin harus menggunakan jendela yang lebih panjang, banyak jendela, atau interpolasi untuk memperkirakan frekuensi puncak spektrum dengan lebih baik.