Zrozumienie wyników FFT

87

Potrzebuję pomocy w zrozumieniu wyników obliczeń DFT / FFT.

Jestem doświadczonym inżynierem oprogramowania i muszę zinterpretować niektóre odczyty akcelerometru smartfona, takie jak znajdowanie głównych częstotliwości. Niestety piętnaście lat temu przespałem większość moich zajęć na uczelniach EE, ale czytałem o DFT i FFT przez ostatnie kilka dni (najwyraźniej bezskutecznie).

Proszę, nie ma odpowiedzi „idź na zajęcia EE”. Planuję to zrobić, jeśli mój pracodawca mi zapłaci. :)

Oto mój problem:

Przechwyciłem sygnał przy 32 Hz. Oto 1-sekundowa próbka 32 punktów, które sporządziłem na wykresie w programie Excel.

wprowadź opis obrazu tutaj

Potem dostałem kod FFT napisany w Javie z Columbia University (postępując zgodnie z sugestiami w poście „ Niezawodny i szybki FFT w Javie ”).

Wynik tego programu jest następujący. Uważam, że działa w miejscu FFT, więc ponownie używa tego samego bufora zarówno dla wejścia, jak i wyjścia.

Before: 

Re: [0.887  1.645  2.005  1.069  1.069  0.69  1.046  1.847  0.808  0.617  0.792  1.384  1.782  0.925  0.751  0.858  0.915  1.006  0.985  0.97  1.075  1.183  1.408  1.575  1.556  1.282  1.06  1.061  1.283  1.701  1.101  0.702  ]

Im: [0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  ]

After: 

Re: [37.054  1.774  -1.075  1.451  -0.653  -0.253  -1.686  -3.602  0.226  0.374  -0.194  -0.312  -1.432  0.429  0.709  -0.085  0.0090  -0.085  0.709  0.429  -1.432  -0.312  -0.194  0.374  0.226  -3.602  -1.686  -0.253  -0.653  1.451  -1.075  1.774  ]

Im: [0.0  1.474  -0.238  -2.026  -0.22  -0.24  -5.009  -1.398  0.416  -1.251  -0.708  -0.713  0.851  1.882  0.379  0.021  0.0  -0.021  -0.379  -1.882  -0.851  0.713  0.708  1.251  -0.416  1.398  5.009  0.24  0.22  2.026  0.238  -1.474  ]

Tak więc w tym momencie nie mogę zrobić orzeł ani reszki z wyjścia. Rozumiem pojęcia DFT, takie jak część rzeczywista to amplitudy składowych fal cosinusowych, a część urojona to amplitudy składowych fal sinusoidalnych. Mogę również postępować zgodnie z tym schematem ze wspaniałej książki „ The Scientist and Engineer's Guide to Digital Signal Processing ”: wprowadź opis obrazu tutaj

Więc moje konkretne pytania to:

  1. Jak na podstawie danych wyjściowych FFT znaleźć „najczęściej występujące częstotliwości”? To część mojej analizy danych z akcelerometru. Czy powinienem czytać tablice rzeczywiste (cosinus) czy urojone (sinus)?

  2. Mam 32-punktowe wejście w dziedzinie czasu. Czy wynikiem FFT nie powinna być 16-elementowa tablica dla liczb rzeczywistych i 16-elementowa tablica dla urojonych? Dlaczego program daje mi rzeczywiste i urojone tablice wyjściowe o rozmiarze 32?

  3. W związku z poprzednim pytaniem, jak przeanalizować indeksy w tablicach wyjściowych? Biorąc pod uwagę moje dane wejściowe 32 próbek próbkowanych z częstotliwością 32 Hz, rozumiem, że 16-elementowa tablica wyjściowa powinna mieć swój indeks równomiernie rozłożony do 1/2 częstotliwości próbkowania (32 Hz), więc mam rację, rozumiejąc, że każdy element tablicy reprezentuje (32 Hz * 1/2) / 16 = 1 Hz?

  4. Dlaczego wynik FFT ma wartości ujemne? Myślałem, że wartości reprezentują amplitudy sinusoidy. Na przykład wyjście Real [3] = -1,075 powinno oznaczać amplitudę -1,075 dla fali cosinusowej o częstotliwości 3. Czy to prawda? Jak amplituda może być ujemna?

stackoverflowuser2010
źródło
Co chciałbyś obliczyć na podstawie odczytów akcelerometru: prędkość, odległość? Szum odczytów akcelerometru jest zgodny z rozkładem Gaussa i nie widzę, jak dopasowanie fali sinusoidalnej mogłoby temu zaradzić.
Ali
2
tag java powinien zostać usunięty, ponieważ jest bardziej ogólny niż dla konkretnego języka
user3791372
Patrząc na źródło Uniwersytetu Columbia, nie jest to wcale wydajne. Jest to zwykła, niezoptymalizowana implementacja Cooley-Tucky'ego z tabelami wyszukiwania motyli, a odwrócenie bitów odbywa się ręcznie zamiast korzystania z istniejących funkcji bibliotecznych
Mark Jeronimus
@MarkJeronimus: Czy możesz polecić wydajną implementację FFT w Javie? Jeśli dobrze pamiętam, powodem, dla którego wybrałem kod Uniwersytetu Columbia, był fakt, że biblioteka FFTW była zbyt złożona, aby można ją było uruchomić na smartfonie z Androidem.
stackoverflowuser2010
Znalazłem kilka rozproszonych „zoptymalizowanych” implementacji, ale są one w zasadzie jednym algorytmem na rozmiar N, więc jeśli potrzebujesz zakresu rozmiarów, potrzebujesz wszystkich tych procedur. W praktyce używałem głównie Intel Integrated Performance Primitives (tak, od Javy, do JNA), ale to nie jest wolne. W domu używam zasadniczo tego samego algorytmu, który podłączyłeś, ale napisanego od podstaw w 2005 roku przy użyciu podręcznika. To tylko FFT (szybka transformata Fouriera), nic tak „szybkiego”, aby uzasadnić nazwę „Fast FFT”.
Mark Jeronimus

Odpowiedzi:

85
  1. Nie powinieneś szukać rzeczywistej ani urojonej części liczby zespolonej (czyli to, jaka jest twoja rzeczywista i urojona tablica). Zamiast tego chcesz poszukać wielkości częstotliwości, która jest zdefiniowana jako sqrt (real * real + imag * imag). Ta liczba zawsze będzie dodatnia. Teraz wszystko, co musisz szukać, to maksymalna wartość (zignoruj ​​pierwszy wpis w swojej tablicy. To jest twoje przesunięcie DC i nie zawiera informacji zależnych od częstotliwości).

  2. Otrzymujesz 32 rzeczywiste i 32 urojone wyjścia, ponieważ używasz złożonego do złożonego FFT. Pamiętaj, że przekonwertowałeś swoje 32 próbki na 64 wartości (lub 32 wartości zespolone), rozszerzając je o zero części urojonych. Powoduje to symetryczne wyjście FFT, w którym wynik częstotliwości występuje dwukrotnie. Gotowe do użycia na wyjściach od 0 do N / 2 i po odbiciu lustrzanym na wyjściach od N / 2 do N. W twoim przypadku najłatwiej jest po prostu zignorować wyjścia N / 2 do N. Nie potrzebujesz ich, są one tylko artefakt dotyczący sposobu obliczania FFT.

  3. Częstotliwość do równania fft-bin to (bin_id * freq / 2) / (N / 2), gdzie freq to częstotliwość próbkowania (czyli 32 Hz, a N to rozmiar FFT). W twoim przypadku upraszcza to do 1 Hz na pojemnik. Pojemniki od N / 2 do N reprezentują ujemne częstotliwości (dziwna koncepcja, wiem). W twoim przypadku nie zawierają one żadnych istotnych informacji, ponieważ są tylko odbiciem pierwszych częstotliwości N / 2.

  4. Twoje rzeczywiste i urojone części każdego pojemnika tworzą liczbę zespoloną. W porządku, jeśli części rzeczywiste i urojone są ujemne, podczas gdy wielkość samej częstotliwości jest dodatnia (zobacz moją odpowiedź na pytanie 1). Sugeruję, abyś czytał na liczbach zespolonych. Wyjaśnienie, jak działają (i dlaczego są przydatne) wykracza poza to, co można wyjaśnić w jednym pytaniu dotyczącym przepełnienia stosu.

Uwaga: Możesz również przeczytać, czym jest autokorelacja i jak jest używana do znalezienia podstawowej częstotliwości sygnału. Mam wrażenie, że tego naprawdę chcesz.

Nils Pipenbrinck
źródło
1
Dzięki. Odnośnie 1: Widziałem tę stronę Matlab, która pokazuje widmo częstotliwości ( mathworks.com/help/techdoc/ref/fft.html ). Na tej stronie znajduje się wykres z tytułem „Jednostronne widmo amplitudy y (t)”. Czy to wykreślanie wielkości częstotliwości, jak sugerowałeś, sqrt (real ^ 2 + img ^ 2)? Odnośnie 3: nadal nie otrzymuję wyniku 2 Hz na pojemnik. W moim przypadku N = 32 i freq = 32, prawda? Mamy więc N / 2 = 32/2 = 16 pojemników, a najwyższa częstotliwość (Nyquist) to freq / 2 = 32/2 = 16 Hz, co daje 16 Hz na 16 pojemników, co daje 1 Hz na pojemnik?
stackoverflowuser2010
1
Tak, wykres pokazuje wielkość widma - | Y (f) |. Słupki wartości bezwzględnych oznaczają wielkość. Szerokość pojemnika = częstotliwość próbkowania / rozmiar FFT. Twoja częstotliwość próbkowania to 32 Hz, a Twój rozmiar FFT to 32. Tak, masz rację co do szerokości pojemnika!
Matt Montag,
Naprawiono częstotliwość bin.
André Chalella,
1
Dobra odpowiedź, dzięki! Przepraszam, że trochę się spóźniłem na imprezę, ale może mógłbyś mi odpowiedzieć, jaka jest ogólnie jednostka wielkości częstotliwości (jak wspomniałeś w punkcie 1)? W moim przypadku na sygnale wartości z akcelerometru (to m / s ^ 2). Nie mogę tego rozgryźć.
Markus Wüstenberg
Fascynujący! Moje paski częstotliwości wizualizacji muzyki wychodziły w lustrzanym odbiciu od lewej do prawej; odpowiedź nr 2 wyjaśnia to !! Zwariowany!!
Ryan S
11

Masz już kilka dobrych odpowiedzi, ale dodam tylko, że naprawdę musisz zastosować funkcję okna do danych w dziedzinie czasu przed FFT, w przeciwnym razie otrzymasz paskudne artefakty w swoim widmie z powodu wycieku widma .

Paul R.
źródło
Doceniam, że od tej odpowiedzi minęło sporo czasu. Czy byłbyś jednak w stanie wyjaśnić, o jakie artefakty masz na myśli?
MattHusz
1
@MattHusz: ogólny termin określający pochodzenie tych artefaktów to „wyciek widmowy” - dodałem teraz link do odpowiedzi, który to wyjaśnia. Najlepszym sposobem, w jaki mogę opisać ten efekt, jest jednak to, że widmo będzie „rozmazane” z powodu niejawnego prostokątnego okna.
Paul R
6

1) Poszukaj indeksów w tablicy rzeczywistej o najwyższych wartościach, oprócz pierwszego (to jest składowa DC). Prawdopodobnie będziesz potrzebować częstotliwości próbkowania znacznie większej niż 32 Hz i większego rozmiaru okna, aby uzyskać znaczące wyniki.

2) Druga połowa obu tablic jest zwierciadłem pierwszej połowy. Na przykład zwróć uwagę, że ostatni element tablicy rzeczywistej (1.774) jest taki sam jak drugi element (1.774), a ostatni element tablicy urojonej (1.474) jest minusem drugiego elementu.

3) Maksymalna częstotliwość, jaką można odebrać przy częstotliwości próbkowania 32 Hz, to 16 Hz ( granica Nyquista ), więc każdy krok to 2 Hz. Jak wspomniano wcześniej, pamiętaj, że pierwszy element to 0 Hz (tj. Przesunięcie DC).

4) Jasne, ujemna amplituda ma sens. Oznacza to po prostu, że sygnał jest „odwrócony” - standardowa FFT jest oparta na cosinusie, który normalnie ma wartość = 1 w t = 0, więc sygnał, który miał wartość = -1 w czasie = 0 miałby ujemną amplitudę .

duskwuff-nieaktywny-
źródło
Dziękuję za odpowiedź. (1) Czy masz na myśli, że mogę zignorować wyimaginowaną tablicę (sinus), a jeśli tak, to dlaczego? Z pewnością składnik sinusoidalny musi być ważny? (2) Dlaczego ma miejsce to odbicie lustrzane? Czy to tylko wynik algorytmu FFT? Czy większość ludzi ignoruje lustrzaną połowę? (3) Jak obliczyłeś kroki co 2 Hz? Rozumiem limit Nyquista wynoszący 16 Hz, więc jeśli jest 16 (nie lustrzanych) elementów tablicy, każdy element musi mieć 16 Hz / 16 = 1 Hz każdy? (4) Aby znaleźć główne częstotliwości, czy mam po prostu wziąć bezwzględną wartość wartości amplitudy w tablicach wyjściowych?
stackoverflowuser2010
Nie powinieneś szukać najwyższej wartości w prawdziwej tablicy i nie możesz ignorować tablicy sinus / I. Zamiast tego chcesz mieć wielkość złożonego wektora złożonego. Odbicie lustrzane występuje, ponieważ połowa danych wejściowych (tablica I) to same zera, więc wynik ma połowę stopni swobody. Możesz to zignorować, jeśli twoje dane są ściśle prawdziwe.
hotpaw2
@duskwuff Wielkie dzięki: odpowiedziałeś na pytanie, które zamierzałem zamieścić, gdybym nie znalazł odpowiedzi: jak zinterpretować DRUGĄ część FFT. Chcę zmodyfikować dane i wykonać odwrotność i nadal otrzymywałem tylko połowę wyników, ponieważ zmodyfikowałem nieprawidłowe dane w tej części. Dzięki jeszcze raz.
Martin
(3), wartość kroku = 2 Hz pozostaje dla mnie domniemana. Mamy 16 pojemników, reprezentowanych przez tablicę długości = 16. Musimy opisać wszystkie częstotliwości od 0 Hz do 16 Hz. Zakładam, że każdy bin opisuje kawałek z tego zakresu, prawda?
krafter
@krafter Myślę, że jest zmniejszona o połowę, ponieważ nie można wywnioskować częstotliwości z pojedynczej wartości (ponieważ nie ma powtórzeń).
JVE999
5

Zwróć uwagę, że „najczęściej występująca częstotliwość” może zostać rozbita na wiele pojemników FFT, nawet z funkcją okna. Być może będziesz musiał użyć dłuższego okna, wielu okien lub interpolacji, aby lepiej oszacować częstotliwość jakichkolwiek pików widmowych.

hotpaw2
źródło