Filtr dolnoprzepustowy z wykorzystaniem FFT zamiast implementacji splotowania

Question

Wdrażanie filtra dolnoprzepustowego FIR, kiedy należy użyć FFT i IFFT zamiast splotu w dziedzinie czasu?

Celem jest osiągnięcie najniższego czasu procesora wymaganego do obliczeń w czasie rzeczywistym. Z tego co wiem, FFT ma o O (n log n) złożoność, ale splot w dziedzinie czasu jest O (n²) złożoności. W celu realizacji filtru dolnoprzepustowego w domenie częstotliwości należy stosować FFT następnie mnożenie każdej z wartości współczynników filtrowania (które są przeliczane w dziedzinie częstotliwości), a następnie wykonać IFFT.

Pytanie brzmi, kiedy uzasadnione jest stosowanie filtrowania opartego na częstotliwościach (FFT + IFFT) zamiast stosowania filtru FIR opartego na bezpośrednim sprzężeniu? Powiedzmy, jeśli mamy 32 stałe współczynniki, czy FFT + IFFT powinno być używane czy nie? Jak około 128 współczynników? I tak dalej ...

Próbując zoptymalizować istniejący kod źródłowy (filtr FIR oparty na konwolucji), jestem całkowicie zdezorientowany, albo powinienem użyć FFT, albo po prostu zoptymalizować go, aby użyć SSE, czy nie.

Answer 1

Konwolucja to właściwie O (m * n), gdzie m jest szerokością skończonej odpowiedzi impulsowej, a N to okno próbki.

Zatem punkt krytyczny m, w którym warto zmienić FFT + IFFT, odnosi się do log (N) okna próbki.

W czasie rzeczywistym fakt, że FFT jest zorientowany wsadowo może być ważniejszy niż względna ilość cykli zegara, ponieważ może nie być możliwe odczekanie 1024 punktów próbki przed filtrowaniem, jeśli aplikacja jest na przykład w pętli regulacji .

Teraz wiele się rozwinęło w tym obszarze i mnóstwo kodu jest dostępnych, więc wypróbowanie kilku rozwiązań i testów porównawczych jest tutaj kluczowe.

Answer 2

To zależy od używanej architektury i różnych innych czynników, ale ogólną "regułą" dla 1D DSP jest to, że jeśli rozmiar filtra jest mały, powiedzmy mniej niż 100 terminów, prawdopodobnie lepiej z bezpośrednim splotem, ale w przypadku większych rozmiarów filtrów warto wykonać szybkie splatanie w dziedzinie częstotliwości.

Oczywiście musisz być pewien, że filtrowanie jest najpierw wąskim gardłem, ponieważ nie ma sensu podejmować dodatkowego wysiłku związanego z szybkim splataniem, jeśli twoja domena czasu jest wystarczająco szybka.

Dolna linia: zacznij od prostego bezpośredniego splotu, a następnie przejdź do szybkiego splotu później: , jeśli potrzebujesz tego. (Musisz zachować pierwsze wdrożenie walidacji realizacja drugiego, więc to nie jest zmarnowany wysiłek, za pomocą dowolnych środków.)