Data apa yang harus saya gunakan untuk menguji implementasi FFT, dan akurasi apa yang harus saya harapkan?

Saya terlibat dengan upaya untuk mengimplementasikan algoritma FFT, dan saya ingin tahu apa saran yang disarankan untuk input data uji untuk digunakan - dan mengapa! - dan akurasi apa yang diharapkan.

Pada input pengujian, saya telah menemukan sedikit panduan dalam posting Usenet lama yang akan saya posting sebagai jawaban, tetapi itu hanya saran satu orang tanpa banyak pembenaran - saya belum menemukan apa pun yang tampak seperti jawaban yang solid.

Pada keakuratan, Wikipedia mengatakan bahwa kesalahannya seharusnya O (e log N), tapi apa harapan yang masuk akal dari segi absolut?

Sunting untuk ditambahkan: Tes yang sebenarnya adalah dalam bentuk di mana saya telah menyimpan array data input dan data keluaran "referensi" yang sudah dihitung sebelumnya untuk dibandingkan, jadi saya tidak perlu sesuatu dengan solusi bentuk tertutup.

Jika Anda ingin memverifikasi algoritma FFT untuk kebenaran , dalam arti melakukan fungsi yang diinginkan yang memiliki sifat diketahui dari transformasi Fourier diskrit , maka Anda dapat menggunakan pendekatan yang diusulkan dalam:

Ergün, Funda. (1995, Juni). Menguji fungsi linier multivarian: Mengatasi hambatan generator. Dalam Proc. Ann Dua Puluh Tujuh. ACM Symp. Teori Komputasi . (hal. 407-416).

Makalah di atas direferensikan oleh pembuat FFTW sebagai metode pilihan mereka untuk memverifikasi bahwa implementasi FFT tertentu melakukan apa yang seharusnya. Teknik yang diusulkan menyaring fungsi menjadi tiga komponen utama yang diverifikasi dengan tes terpisah:

• Linearitas: The DFT (bersama dengan transformasi sepupu lainnya dalam keluarga Fourier) adalah operator linear , sehingga untuk semua nilai , persamaan berikut harus memegang:$a_1, a_2, x_1[n], x_2[n]$

• DFT dari impuls unit: Sinyal domain-waktu yang sama dengan fungsi Kronecker delta diterapkan pada input dari algoritma FFT dan hasilnya diperiksa terhadap DFT yang diketahui dari fungsi impuls unit (itu berubah menjadi nilai konstan dalam semua output sampah). Jika algoritma FFT menyediakan IFFT, itu dapat diuji secara terbalik untuk menunjukkan bahwa ia menghasilkan fungsi impuls unit lagi.

• Pergeseran waktu: Dua set data diterapkan pada input dari algoritma FFT; satu-satunya perbedaan antara keduanya dalam domain waktu adalah pergeseran waktu yang konstan. Berdasarkan pada sifat-sifat DFT yang diketahui, ini harus memengaruhi pergeseran fasa linier yang diketahui antara representasi domain frekuensi dua sinyal, di mana kemiringan pergeseran fasa sebanding dengan pergeseran waktu.

Para penulis makalah ini menegaskan bahwa tes ini cukup untuk memvalidasi kebenaran implementasi FFT. Saya tidak pernah menggunakan teknik ini di masa lalu, tetapi tampaknya masuk akal, dan saya akan mempercayai penulis FFTW (yang telah menghasilkan perangkat lunak gratis yang hebat) sebagai otoritas yang kredibel pada pendekatan yang baik untuk masalah validasi.

Seperti disebutkan dalam pertanyaan, saya memang menemukan satu set saran dalam arsip Usenet comp.dsp yang diarsipkan ( http://www.dsprelated.com/showmessage/71595/1.php , dikirim oleh "tdillon"):

A.Single FFT tests - N inputs and N outputs
 1.Input random data
 2.Inputs are all zeros
 3.Inputs are all ones (or some other nonzero value)
 4.Inputs alternate between +1 and -1.
 5.Input is e^(8*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 6.Input is cos(8*2*pi*i/N) for i = 0,1,2, ...,N-1.
 7.Input is e^((43/7)*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 8.Input is cos((43/7)*2*pi*i/N) for i = 0,1,2, ...,N-1.

B.Multi FFT tests - run continuous sets of random data
 1.Data sets start at times 0, N, 2N, 3N, 4N, ....
 2.Data sets start at times 0, N+1, 2N+2, 3N+3, 4N+4, ....

Thread juga menyarankan melakukan dua sinus, satu dengan amplitudo besar dan satu dengan amplitudo kecil.

Seperti yang saya katakan dalam pertanyaan utama, saya tidak yakin apakah ini adalah set jawaban yang sangat bagus, atau apakah itu sangat lengkap, tapi saya taruh di sini sehingga orang dapat memilih dan mengomentarinya.