Jakich danych powinienem użyć do przetestowania implementacji FFT i jakiej dokładności powinienem się spodziewać?

Jestem zaangażowany w wysiłek wdrożenia algorytmu FFT i jestem ciekawy, jaka zalecana rada jest do użycia wejściowych danych testowych - i dlaczego! - i jakiej dokładności się spodziewać.

Jeśli chodzi o dane testowe, w starych postach Usenetu znalazłem małe wskazówki, które opublikuję jako odpowiedź, ale są to tylko sugestie jednej osoby bez większego uzasadnienia - nie znalazłem nic, co wyglądałoby na solidną odpowiedź.

Jeśli chodzi o dokładność, Wikipedia mówi, że błąd powinien wynosić O (e log N), ale jakie jest uzasadnione oczekiwanie w wartościach bezwzględnych?

Edytuj, aby dodać: Rzeczywiste testy są w formie, w której zapisałem tablice danych wejściowych i wstępnie obliczone dane wyjściowe „referencyjne” do porównania, więc niekoniecznie potrzebuję czegoś z rozwiązaniem w formie zamkniętej.

Jeśli chcesz zweryfikować poprawność algorytmu FFT w tym sensie, że wykonuje on pożądaną funkcję, która ma znane właściwości dyskretnej transformaty Fouriera , możesz zastosować podejście zaproponowane w:

Ergün, Funda. (1995, czerwiec). Testowanie wielowymiarowych funkcji liniowych: przezwyciężenie wąskiego gardła generatora. W Proc. Dwudziesta siódma Ann. ACM Symp. Teoria informatyki . (s. 407–416).

Powyższy artykuł jest przywoływany przez twórców FFTW jako ich metodę wyboru do weryfikacji, czy określona implementacja FFT robi to, co powinna. Proponowana technika dzieli funkcję na trzy główne elementy, które są weryfikowane za pomocą oddzielnych testów:

• Liniowości DFT (wraz z jego innych transformat spokrewnionych z rodziny Fouriera) jest operatorem liniowym , więc dla wszystkich wartości , następujące równanie musi posiadać:$a_1, a_2, x_1[n], x_2[n]$

• DFT impulsu jednostkowego: Sygnał w dziedzinie czasu równy funkcji delta Kroneckera jest przykładany do wejścia algorytmu FFT, a dane wyjściowe są porównywane ze znanym DFT funkcji impulsowej jednostkowej (przekształca się na stałą wartość na wszystkich wyjściach pojemniki). Jeśli algorytm FFT zapewnia IFFT, można go przetestować w odwrotnej kolejności, aby wykazać, że ponownie wywołuje funkcję impulsu jednostkowego.

• Przesunięcie czasowe: dwa zestawy danych są stosowane do wprowadzania algorytmu FFT; jedyną różnicą między nimi w dziedzinie czasu jest stałe przesunięcie czasowe. W oparciu o znane właściwości DFT powinno to spowodować znane liniowe przesunięcie fazowe między reprezentacjami w dziedzinie częstotliwości dwóch sygnałów, gdzie nachylenie przesunięcia fazowego jest proporcjonalne do przesunięcia czasowego.

Autorzy artykułu twierdzą, że testy te są wystarczające do zweryfikowania poprawności implementacji FFT. W przeszłości nie korzystałem z tej techniki, ale wydaje się to mieć sens i ufam autorom FFTW (którzy stworzyli świetny kawałek wolnego oprogramowania) jako wiarygodnym autorytetom w zakresie dobrego podejścia do problemu walidacji.

Jak wspomniano w pytaniu, znalazłem jeden zestaw sugestii w zarchiwizowanych postach usenet comp.dsp ( http://www.dsprelated.com/showmessage/71595/1.php , post przez „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, ....

Wątek sugeruje również wykonanie dwóch sinusów, jednej o dużej amplitudzie i jednej o małej amplitudzie.

Jak mówię w głównym pytaniu, nie jestem pewien, czy jest to szczególnie dobry zestaw odpowiedzi, czy też jest bardzo kompletny, ale umieszczam tutaj, aby ludzie mogli głosować i komentować.