Dlaczego powinienem zerować sygnał przed podjęciem transformacji Fouriera?

77

W odpowiedzi na poprzednie pytanie stwierdzono, że należy

zeruj pad na sygnały wejściowe (dodaj zera na końcu, aby co najmniej połowa fali była „pusta”)

Jaki jest tego powód?

Jonas
źródło
To zależy od tego, co robisz. To mógłby być komentarz do mojej odpowiedzi. Dodałem do tego wyjaśnienie.
endolith
@endolith: Początkowo zastanawiałem się nad tym, aby wypowiedzieć to jako komentarz, ale myślę, że pytanie to może być przedmiotem ogólnego zainteresowania i szkoda byłoby, gdyby gdzieś w komentarzach zakopano dobrą odpowiedź. Jeśli się nie zgadzasz, usunę to pytanie.
Jonas
9
To bardzo ogólne pytanie. Możesz wyzerować pad, aby uzyskać potęgę 2, możesz wyzerować pad, aby transformacja kołowa zachowywała się jak transformacja nieokrągła, możesz to zrobić, aby ponownie próbkować sygnał, zmienić rozdzielczość częstotliwości itp.
Endolith
Powiązane również: dsp.stackexchange.com/questions/331/…
finnw

Odpowiedzi:

82

Wypełnienie zerowe pozwala na użycie dłuższego FFT, co spowoduje powstanie dłuższego wektora wyniku FFT.

Dłuższy wynik FFT ma więcej przedziałów częstotliwości, które są bliżej rozmieszczone w częstotliwości. Będą one jednak zasadniczo zapewniać ten sam wynik, co wysokiej jakości interpolacja Sinc krótszego FFT niezerowanego z zerami oryginalnych danych.

Może to skutkować gładszym wyglądem widma, gdy zostanie wydrukowane bez dalszej interpolacji.

Chociaż ta interpolacja nie pomoże w rozdzieleniu lub rozdzielczości i / lub pomiędzy sąsiednimi lub pobliskimi częstotliwościami, może ułatwić wizualne rozpoznanie piku pojedynczej izolowanej częstotliwości, która nie ma żadnych znaczących sąsiednich sygnałów lub szumu w widmie . Statystycznie większa gęstość koszy wyników FFT prawdopodobnie zwiększy prawdopodobieństwo, że bin wielkości piku jest bliższy częstotliwości losowo izolowanej sinusoidy częstotliwości wejściowej i bez dalszej interpolacji (paraboliczna, i in.).

Zasadniczo zerowanie dopełniania przed DFT / FFT jest wydajną obliczeniowo metodą interpolacji dużej liczby punktów.

Wypełnianie zerowe dla korelacji krzyżowej, autokorelacji lub filtrowania splotowego służy do nie mieszania wyników splotu (z powodu splotu kołowego). Pełny wynik splotu liniowego jest dłuższy niż jeden z dwóch wektorów wejściowych. Jeśli nie zapewnisz miejsca na zakończenie tego dłuższego wyniku splotu, szybki splot FFT po prostu pomieszać go i uzyskać pożądany wynik. Zero-padding zapewnia kilka zer, w które można zmieszać dłuższy wynik. O wiele łatwiej jest cofnąć miksowanie czegoś, co zostało tylko zmiksowane / zsumowane z wektorem zer.

hotpaw2
źródło
12
Ostatni akapit jest kluczową odpowiedzią na pierwotne pytanie, chociaż myślę, że można by to wyrazić jaśniej. Można zastosować zerowanie w kontekście korelacji lub splotu, aby zapewnić, że wdrożenie procesu w dziedzinie częstotliwości daje liniowy zamiast kołowego splotu / korelacji. Jednak nie jest to wymagane, jeśli chcesz wykonać pewne czynności księgowe na boku, na przykład w algorytmach nakładania-zapisywania i nakładania-dodawania.
Jason R
4
@Jason R: W rzeczywistości oba są okrągłym splotem. Normalny (nie przycięty) FFT wykonuje wszystkie pomnożenia i dodaje do zawiniętej części wyniku. Tyle tylko, że w przypadku wystarczająco wyrównanego zera wszystkie te mnożenia i sumy mają wartość zero, więc nikt nie dba o nic, co zostanie obliczone i owinięte wokół koła.
hotpaw2
9
W rzeczy samej; zwielokrotnienie DFT dwóch sygnałów zawsze realizuje splot kołowy. Powinienem to sformułować inaczej: wypychasz zera na końcu jednego sygnału, aby upewnić się, że wynik uzyskany przez ich kołowy splot jest taki sam, jak to, co otrzymujesz, gdy je splot liniowo (zakładając, że splot liniowy jest tym, czego chcesz, co jest zwykle tak jest).
Jason R
27

Jest kilka rzeczy do rozważenia, zanim zdecydujesz się wyzerować sygnał w dziedzinie czasu. Być może nie trzeba wcale zerować padu!

1) Wydłuż dane w dziedzinie czasu (nie wypełnianie zerami), aby uzyskać lepszą rozdzielczość w dziedzinie częstotliwości.

2) Zwiększ liczbę punktów FFT poza długość sygnału w dziedzinie czasu (wypełnienie zerowe), jeśli chcesz zobaczyć lepszą definicję przedziałów FFT, chociaż nie kupi to już prawdziwej rozdzielczości. Możesz także pad, aby uzyskać moc 2 punktów FFT.

fs/NfsN

Istnieje kilka fajnych liczb ilustrujących te punkty na http://www.bitweenie.com/listings/fft-zero-padding/

I ostatnia rzecz do wspomnienia: jeśli zerujesz pad sygnału w dziedzinie czasu i chcesz użyć funkcji okienkowania, upewnij się, że ustawiłeś sygnał przed zerowaniem padu. Jeśli zastosujesz funkcję okna po wypełnieniu zerą, nie osiągniesz tego, co powinno osiągnąć okno. Mówiąc dokładniej, nadal będziesz mieć ostre przejście od sygnału do zera zamiast płynnego przejścia do zera.

użytkownik19460
źródło
8

Zasadniczo wypełnianie zera przed DFT jest równoważne interpolacji lub próbkowaniu częściej w dziedzinie transformowanej.

Oto krótka wizualizacja tego, jak działa przeciwieństwo. Jeśli próbkujesz sygnał o ograniczonym paśmie w czasie z większą częstotliwością, otrzymujesz bardziej „zgniecione” widmo, tj. Widmo z większą liczbą zer na obu końcach. Innymi słowy, możesz uzyskać więcej próbek w czasie, po prostu wypełniając zero częstotliwością po DFT, a następnie IDFT, wypełniając wynik zerowany.

Ten sam efekt zachowuje się w odwrotnej kolejności, gdy dopełnianie zera następuje w czasie. Wszystko to dlatego, że możliwa jest idealna rekonstrukcja sygnału, o ile sygnał jest ograniczony pasmem i próbkowany co najmniej z częstotliwością Nyquista.

Termin „rozdzielczość” zależy od tego, jak go zdefiniujesz. Dla mnie oznacza to, jak dobrze dwa sąsiednie punkty obserwacji w czasie lub częstotliwości można wiarygodnie (statystycznie) rozróżnić. W takim przypadku rozdzielczość faktycznie zależy od wielkości DFT z powodu wycieku widmowego. Oznacza to, że mniejszy rozmiar okna, bardziej rozmazany lub rozmazany transformowany sygnał i na odwrót. Różni się od częstotliwości próbkowania lub tego, co nazywam „definicją”. Na przykład możesz uzyskać bardzo rozmazany obraz próbkowany z dużą szybkością (wysoka rozdzielczość), ale nadal nie możesz uzyskać więcej informacji niż próbkowanie z niższą częstotliwością. Podsumowując, wypełnianie zerami wcale nie poprawia rozdzielczości, ponieważ nie zyskujesz więcej informacji niż wcześniej.

Pan T.
źródło
6

Jeśli ktoś interesuje się widmem funkcji okienkowania zastosowanej do izolacji próbki w dziedzinie czasu, wówczas wypełnienie zerą BĘDZIE zwiększyć rozdzielczość częstotliwości funkcji okienkowania.

x(t)w(t)w(t)X(fa)W.(fa)

x(t)X(fa), zobaczysz próbki w miejscach innych niż pik i przecięcia zera, odsłaniając kształt funkcji synchronizacji w wynikowym widmie. Więc jaki jest pożytek z wypełnienia zerowego? Jest to z pewnością użyteczne w celach edukacyjnych do ujawnienia natury dyskretnej transformacji sygnałów okienkowych, co jest typowym przypadkiem. W sensie praktycznym może być przydatny w każdym przypadku, gdy interesuje Cię spektralny kształt izolowanej obwiedni poruszającej się na fali nośnej.

Paweł
źródło
4

Przyczyny tego mogą być różne, w zależności od procesów przeprowadzonych przed transformacją Fouriera i po niej. Najczęstszym powodem jest uzyskanie wyższej rozdzielczości częstotliwości w każdej wynikowej transformacji. Oznacza to, że im większa liczba próbek użytych w transformacji, tym węższa szerokość przedziału w wynikowym spektrum mocy. Pamiętaj: binwidth = sample_frequency / transform_size (często nazywany rozmiarem okna). Możesz sobie wyobrazić, że wraz ze wzrostem wielkości transformacji zmniejsza się szerokość pasma (= lepsza rozdzielczość częstotliwości). Wypełnienie zerowe jest sposobem na zwiększenie rozmiaru transformacji bez wprowadzania nowych informacji do sygnału.

Dlaczego więc nie wziąć większej transformacji bez zerowania? Czy to nie osiągnęłoby tego samego efektu? Dobre pytanie. W wielu przypadkach możesz chcieć przeanalizować strumień danych w dziedzinie czasu, dla którego możesz użyć krótkotrwałej transformacji Fouriera (stft). Wymaga to wykonania transformacji co N próbek zgodnie z potrzebną rozdzielczością czasową w celu scharakteryzowania zmian w spektrum częstotliwości. Na tym polega problem. Zbyt duże okno i stracisz rozdzielczość czasową, zbyt małe okno i stracisz rozdzielczość częstotliwości. Rozwiązaniem jest wtedy wziąć małe okna domen czasowych, które zapewniają dobrą rozdzielczość czasową, a następnie zerować je, aby uzyskać dobrą rozdzielczość częstotliwości. Mam nadzieję, że to ci się przyda

Aktualizacja
Nie wyjaśniłem tego dobrze. Powinienem był to lepiej wyjaśnić. Odnosząc się do transformacji okienkowej, rzeczywiście nie uzyskuje się „rzeczywistej” większej rozdzielczości częstotliwości, ale dla celów wizualizacji (odczyt spektrum mocy okiem) może zapewnić wyraźniejsze wyniki. Przy użyciu krytycznej częstotliwości próbkowania każdy płat boczny zajmuje jeden pojemnik, co w zależności od techniki graficznej może wprowadzać w błąd. Wypełnienie zerowe zapewnia interpolowane spektrum częstotliwości, które może być bardziej odkrywcze. Dodatkowo, jeśli używasz prostej metody pikowania do oszacowania częstotliwości, efekt interpolacji widmowej wypełnienia zerowego da próbkę widmową bliższą prawdziwemu pikowi głównego płata. Ten link zawiera przydatne diagramy: http://www.dsprelated.com/dspbooks/sasp/Practical_Zero_Padding.html

Dan Barry
źródło
9
Ta odpowiedź jest nieprawidłowa. Zero-padding w ogóle nie poprawia rozdzielczości częstotliwości; interpoluje jedynie między wyjściami mniejszej transformaty. Można pomyśleć o wypełnianiu zera jako dodawaniu większej liczby przedziałów częstotliwości, które mają taką samą szerokość pasma, jak w przypadku mniejszej transformacji; dlatego z perspektywy banku filtrów ich pasma nakładają się.
Jason R
1
Jeśli to pomaga zrozumieć: Możesz także zrobić coś przeciwnego: weź FFT sygnału, następnie wciśnij zero i odwróć FFT. Spowoduje to interpolację oryginalnego sygnału. Ale oczywiście sygnał nadal będzie tym samym sygnałem, z tą samą przepustowością Nyquista. Interpolacja nie dostarczy Ci więcej informacji o wyższej częstotliwości niż wcześniej.
endolith,
1
@Jason R - Masz rację, moja odpowiedź była myląca, próbowałem wyjaśnić powyżej oryginalny post. Nie powinienem był stwierdzać, że wypełnienie zerem zwiększa rozdzielczość częstotliwości.
Dan Barry,
2

Nie widziałem ich wspomnianych w poprzednich dobrych odpowiedziach, więc dodam następujące dodatkowe ważne powody zerowania wypełnienia:

Algorytmy Radix-2 są bardziej wydajne, więc zerowanie dopełniania do następnej potęgi 2 (lub potęgi 4 w niektórych przypadkach dla Radix-4) lub bardziej znaczące unikanie dużych czynników pierwszych może poprawić wydajność w czasie rzeczywistym. Również podczas korzystania z FFT do analizy często wykonuje się wypełnianie zerami w celu obliczenia próbek DTFT, takich jak określenie odpowiedzi częstotliwościowej FIR: porównaj fft ([1 1 1 1]) z fft ([1 1 1 1], 512), który jest identyczny z freqz ([1 1 1 1]).

Dan Boschen
źródło