Jak skutecznie obliczyć tylko niskie współczynniki FFT z wypełnieniem zerowym

14

Mam algorytm, który zeruje dopełnianie sekwencji do 4N, wykonuje FFT i używa tylko najniższych częstotliwości N punktów z wygenerowanego 4N.

To wydaje się dużo zmarnowanej pracy, jakieś pomysły, jak można to zrobić szybciej?

Mark Borgerding
źródło
@Dilip. Będę używać bibliotek FFTW lub IMKL. Mógłbym oczywiście skorzystać z mojej biblioteki kissfft, ale zaczyna się ona od prędkości niekorzystnej w porównaniu z innymi
Mark Borgerding,
2
Usunąłem komentarz, na który odpowiedziałeś, ponieważ chciałem powiedzieć „dziesiątkowanie z częstotliwością”, ale zamiast tego napisałem „dziesiątkowanie z czasem”. Ale spójrz na schemat motyla tutaj. Jeśli napiszesz kod dla pierwszych dwóch etapów dla -FFT, aby wziąć pod uwagę dużą liczbę zer i pominąć odpowiednie mnożenie, możesz następnie wywołać podprogram biblioteki FFT 4 razy dla N -FFT, w których wektory wejściowe są pełne". Oczywiście potrzebujesz tylko N / 4 wyjść z każdego wywołania podprogramu. 4N4NN/4
Dilip Sarwate

Odpowiedzi:

2

Jeśli masz tylko kilka przedziałów, poniższe informacje mogą być dla Ciebie bardzo wydajne:
1. Po prostu wykonaj DFT dla każdej potrzebnej częstotliwości.
2. Użyj algorytmu Goertzela dla każdej częstotliwości, o której mowa.

Jakub
źródło
Mark powiedział, że potrzebuje z pojemnikówN , więc 1) wydaje się nie być rozsądną opcją. Algorytm Goertzela ma takie zalety, jak obliczenia on-line podczas odbierania danych, mała pamięć itp., Ale wymaga 2 N + 4 multiplikacji na bin, podczas gdy każdy bin obliczany jako ocena wielomianowa za pomocą reguły Hornera potrzebuje tylko N multiplikacji. Zatem 2) również nie wydaje się szczególnie rozsądną opcją. 4N2N+4N
Dilip Sarwate 10.11.11
Masz rację, czytając pytanie, jakoś przegapiłem szczegóły. Kiedy odpowiadałem, myślałem: „Ojej, byłoby miło wiedzieć, ile pojemników on chce ...” Chyba powinienem ponownie przeczytać pytanie, zanim odpowiem.
Jakub
2

Zero wypełnienia do 4-krotnej długości, obliczenie dłuższego FFT, a następnie użycie tylko dolnych 1/4 pojemników daje prawie identyczne wyniki do interpolacji Sinc w oryginalnej długości FFT.

Więc po prostu użyj oryginalnej długości FFT i interpoluj za pomocą 3-fazowego jądra interpolacji Sinc o odpowiedniej szerokości okna.

hotpaw2
źródło
0

Zero wypełnienia w dziedzinie czasu daje rozwiązanie o wyższej częstotliwości, ale nie ma nowych informacji, więc zapewnia zasadniczo interpolację w dziedzinie częstotliwości. W zależności od charakteru twoich sygnałów i wymaganej precyzji możesz być w stanie uzyskać dodatkowe punkty częstotliwości z regularną FFT N punktów i wykonując odpowiednią interpolację (liniową, splajnową, pchip, sinc itp.).

Hilmar
źródło
x(z)=i=0N1xizixiN1Nαn,0nN1α=exp(j2π/N)NNXn=x(αn)x(z)Nx(z)βn,0nN1β=exp(j2π/4N)N
β4=αx(β4k)x(β4k)=x(αk)
Podejrzewam, że trudno byłoby wykonać przyzwoitą interpolację szybciej niż w przypadku większego FFT.
Mark Borgerding
Załóżmy, że masz 128-punktową częstotliwość próbkowania FFT i częstotliwość próbkowania 12800Hz. FFT o wartości 128 punktów daje wartości przy 0 Hz, 100 Hz, 200 Hz, 300 Hz itp. Wypełnienie zerowe polega na zwiększeniu rozdzielczości częstotliwości do 0 Hz, 25 Hz, 50 Hz, 100 Hz itp. Można to postrzegać jako problem interpolacji. Dla mnie precyzyjnie matematycznie trzeba wykonać interpolację kołową cynku 128 rzędu. To z pewnością nie jest warte zawracania głowy, ale w zależności od zastosowania i wymaganej precyzji wystarczy interpolacja na niższym poziomie
Hilmar,