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?

fft dft

— 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

razy dla

-FFT, w których wektory wejściowe są pełne". Oczywiście potrzebujesz tylko

wyjść z każdego wywołania podprogramu.

4 N

$4N$

4

$4$

N

$N$

N / 4

$N/4$

— Dilip Sarwate

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ów

N

$N$

, 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

multiplikacji na bin, podczas gdy każdy bin obliczany jako ocena wielomianowa za pomocą reguły Hornera potrzebuje tylko

multiplikacji. Zatem 2) również nie wydaje się szczególnie rozsądną opcją.

4 N

$4N$

2 N + 4

$2N+4$

N

$N$

— 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) = \sum_{i = 0}^{N - 1} x_{i} z^{i}

$x(z)=\sum_{i=0}^{N-1}x_iz^{i}$

x_{i}

$x_i$

N - 1

$N-1$

N

$N$

α^{n}, 0 \leq n \leq N - 1

$\alpha^n, 0\leq n\leq N-1$

α = \exp (- j 2 π / N)

$\alpha=\exp(-j2\pi/N)$

N

$N$

N

$N$

X_{n} = x (α^{n})

$X_n=x(\alpha^n)$

x (z)

$x(z)$

N

$N$

x (z)

$x(z)$

β^{n}, 0 \leq n \leq N - 1

$\beta^n, 0\leq n\leq N-1$

β = \exp (- j 2 π / 4 N)

$\beta=\exp(-j2\pi/4N)$

N

$N$

β^{4} = α

$\beta^4 = \alpha$

x (β^{4 k})

$x(\beta^{4k})$

x (β^{4 k}) = x (α^{k})

$x(\beta^{4k})=x(\alpha^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,