Dyskretna transformacja Fouriera

Transformacji Fouriera, dyskretna (DFT) narzędzia matematyczne służy do przetwarzania sygnału cyfrowego. Jest to oddzielny równoważne z (ciąg dalszy) transformacie Fouriera stosowany do przetwarzania sygnału analogowego.

Szybka transformacja Fouriera jest szczególnie algorytm obliczania transformaty Fouriera dyskretny.

Jego definicja dla sygnału z próbek jest następująca: $s$ $NIE$

{\ Displaystyle S (k) = \ suma _ {n = 0} ^ {N-1} s (n) \ matematyka {e} ^ {- 2 \ matematyka {i} \ pi k {\ Frac {n} { N}}} \ qquad {\ text {pour}} \ qquad 0 \ leqslant k <N}

Odwrotną transformację daje:

{\ Displaystyle s (n) = {\ Frac {1} {N}} \ suma _ {k = 0} ^ {N-1} S (k) \ operatorname {e} ^ {2 \ operatorname {i} \ pi n {\ frac {k} {N}}}}

Dyskretnej reprezentacji widmowej z próbkowanego sygnału jest tak otrzymany . $s (n)$

DFT nie oblicza ciągłego widma sygnału ciągłego. Umożliwia jedynie ocenę dyskretnej reprezentacji widmowej (widma próbkowanego) sygnału dyskretnego (sygnału próbkowanego) w określonym oknie czasowym (próbkowanie ograniczone w czasie).

Poniższy przykład może prowadzić do przekonania, że DFT umożliwia obliczenie widma sygnału ciągłego, ale dzieje się tak tylko wtedy, gdy okno próbkowania odpowiada wielokrotności ściśle większej niż dwukrotność okresu próbkowanego sygnału (w tym przypadku mamy koniecznie uniknął aliasingu widma , jest to twierdzenie o próbkowaniu Nyquista-Shannona ):

Definicje te nie są unikalne: można całkiem znormalizować DFT , a nie normalizować odwrotnej DFT, lub nawet znormalizować obie , ponieważ celem we wszystkich przypadkach jest znalezienie oryginalnego sygnału przez odwrotność DFT jego TFD. ${\ displaystyle 1 / N}$ ${\ displaystyle {\ tfrac {1} {\ sqrt {N}}}}$

TFD odpowiada ocenie na okręgu jednostkowym z przekształcić w Z dla dyskretnych wartości z częstotliwością.

Częstotliwość próbkowania i interpolacja

Można zauważyć, że sygnał ten jest okresowy i dostarcza informacji o częstotliwościach pomiędzy a (gdzie jest częstotliwość próbkowania , często odnotowywana w literaturze angielskiej). Dlatego mamy tylko punkty do analizy widma i może być interesujące zwiększenie tej liczby punktów analizy w celu zwiększenia precyzji widmowej ( ; bez wypełnienia zerami rozdzielczość łączy się z precyzją), a tym samym w celu lepszego zlokalizowania maksimów widma (sygnał o częstotliwości nie będącej wielokrotnością nie będzie widoczny po TFD. Następuje wtedy utrata informacji). Musimy wyróżnić precyzję rozdzielczości, czyli zdolność rozróżnienia dwóch sinusoid przy bliskich częstotliwościach ( ). $NIE$ $- {\ mathrm {F_ {e}}} / 2$ ${\ mathrm {F_ {e}}} / 2$ ${\ mathrm {F_ {e}}}$ $f _ {{\ mathrm {s}}}$ $NIE$ $\ delta {\ mathrm {F}} = {\ mathrm {F_ {e}}} / N$ ${\ Displaystyle \ mathrm {F_ {e}} / N}$ ${\ Displaystyle \ mathrm {F_ {e}} / N}$

Aby zwiększyć liczbę punktów, możesz:

zwiększyć częstotliwość próbkowania. Ale wiąże się to z kosztami w postaci zasobów materialnych;
dokonać interpolacji .

Odbywa się to przez technicznym zera zakończeniu (w języku angielskim zerami ), która ma zakończyć sygnał z zerami. W związku z tym zwiększa się liczba punktów analizy, ale liczba użytecznych punktów sygnału pozostaje taka sama (co nie zmienia rozdzielczości). Nowa definicja brzmi: $s (n)$ $P.$

{\ Displaystyle S (k) = \ suma _ {n = 0} ^ {N + P-1} s (n) \ matematyka {e} ^ {- 2 \ matematyka {i} \ pi k {\ Frac {n } {N + P}}} = \ sum _ {n = 0} ^ {N-1} s (n) \ mathrm {e} ^ {- 2 \ mathrm {i} \ pi k {\ frac {n} {N + P}}}}

Zawsze sumujemy te same wartości ( pozostałe wynoszą zero), ale otrzymujemy okres DFT zamiast po prostu : mamy dodatkowe punkty do opisania tego samego DFT, dlatego zwiększyliśmy jego dokładność. Technika ta jest stosowana w szczególności, aby mieć całkowitą liczbę punktów w sile 2 , i aby móc korzystać z szybkiej transformacji Fouriera algorytmu . $s (n)$ $P.$ ${\ displaystyle N + P}$ $NIE$ $P.$ ${\ displaystyle N + P}$

W ten sam sposób możliwe jest wypełnienie widma zerami w celu uzyskania, poprzez transformację odwrotną, interpolacji sygnału początkowego.

Zawsze rozważamy tutaj częstotliwość próbkowania równą 1. Mówiąc w obniżonych częstotliwościach (znormalizowanych w odniesieniu do częstotliwości próbkowania), DFT jest opisana dla wartości zredukowanej częstotliwości wahających się od 0 (dla ) do 1 (dla ). $k = 0$ ${\ Displaystyle k = N + P}$

Interpretacja macierzy

Macierz Vandermonde-Fouriera

Niech będzie sygnałem okresowości N i jej transformatą Fouriera. Może być połączony a jego transformatę Fouriera przez mnożenie macierzy z matrycy, która zależy tylko od N . ${\ displaystyle {\ hat {s}}}$

{\ displaystyle {\ hat {s}} = W_ {N} s}

{\ Displaystyle W_ {N} = {\ rozpocząć {pmatrix} w_ {N} ^ {0,0} & \ cdots i w_ {N} ^ {0, N-1} \\\ vdots & \ ddots & \ vdots \ \ w_ {N} ^ {N-1,0} & \ cdots & w_ {N} ^ {N-1, N-1} \ end {pmatrix}}}

z . ${\ Displaystyle w_ {N} ^ {n, k} = \ mathrm {e} ^ {- 2 \ pi \ mathrm {i} {\ frac {nk} {N}}}}$

Zauważ, że znajdujemy definicję transformaty Fouriera, ponieważ dla każdego elementu mamy, mnożąc każdy element m-tego rzędu przez wektor s : ${\ Displaystyle {\ kapelusz {s}} (m), m \ w [[0, N-1]]}$ ${\ displaystyle W_ {N}}$

{\ Displaystyle {\ kapelusz {s}} (m) = \ suma _ {n = 0} ^ {N-1} s (n) w_ {N} ^ {n, m} = \ suma _ {n = 0 } ^ {N-1} s (n) \ mathrm {e} ^ {- 2 \ pi \ mathrm {i} {\ frac {nm} {N}}}}

Macierze Vandermonde-Fouriera dla wymiarów 2 i 4

Możemy zastosować ogólny wzór na N = 2:

{\ Displaystyle W_ {2} = {\ rozpocząć {pmatrix} w_ {2} ^ {0,0} i w_ {2} ^ {0,1} \\ w_ {2} ^ {1,0} i w_ {2} ^ {1, 1} \ end {pmatrix}} = {\ begin {pmatrix} \ mathrm {e} ^ {- 2 \ pi \ mathrm {i} {\ frac {0 \ times 0} {2}}} & \ mathrm {e } ^ {- 2 \ pi \ mathrm {i} {\ frac {0 \ times 1} {2}}} \\\ mathrm {e} ^ {- 2 \ pi \ mathrm {i} {\ frac {1 \ times 0} {2}}} & \ mathrm {e} ^ {- 2 \ pi \ mathrm {i} {\ frac {1 \ times 1} {2}}} \ end {pmatrix}} = {\ begin { pmatrix} 1 i 1 \\ 1 & -1 \ end {pmatrix}}}

Podobnie dla N = 4:

{\ Displaystyle W_ {4} = {\ zacząć {pmatrix} 1 i 1 i 1 i 1 \\ 1 i - \ mathrm {i} i -1 i \ mathrm {i} \\ 1 i -1 i 1 i - 1 \\ 1 & \ mathrm {i} & -1 & - \ mathrm {i} \ end {pmatrix}}}

Przykład zastosowania do sygnału

Niech będzie sygnałem okresowości 4.

s (0) = 2, s (1) = 4, s (2) = –1, s (3) = 3, s (4) = 2 = s (0), s (5) = 4 = s ( 1)…

Sygnał ten można zsumować w wektorze . ${\ Displaystyle s = {\ rozpocząć {pmatrix} 2 \\ 4 \\ - 1 \\ 3 \ koniec {pmatrix}}}$

Transformacja Fouriera tego sygnału będzie zatem wyglądać następująco:

{\ displaystyle {\ hat {s}} = W_ {4} s = {\ kapelusz {s}} = {\ początek {pmatrix} 1 i 1 i 1 i 1 \\ 1 i - \ mathrm {i} i - 1 & \ mathrm {i} \ \ 1 & -1 & 1 & -1 \\ 1 & \ mathrm {i} & -1 & - \ mathrm {i} \ end {pmatrix}} {\ begin {pmatrix} 2 \\ 4 \\ - 1 \\ 3 \ end {pmatrix}} = {\ begin {pmatrix} 8 \\ 3-i \\ - 6 \\ 3 + i \ end {pmatrix}}}

Prawdziwe sygnały

Dla prawdziwego sygnału mamy relację

{\ Displaystyle S (k) ^ {*} = S (-k)}

(własność symetrii hermitowskiej ). Gdy interesuje nas widmo amplitud sygnału (lub jego gęstość widmowa mocy ), obliczamy moduł odpowiadający modułowi : widmo to jest więc parzyste. ${\ Displaystyle S (k)}$ ${\ Displaystyle S (k) ^ {*}}$

Jednak widzieliśmy, że DFT jest okresowy, okresowy : częstotliwości między i są takie same jak między i 0. Częstotliwości ujemne są identyczne z dodatnimi, cała informacja widmowa jest zawarta między częstotliwościami i . ${\ displaystyle N + P}$ ${\ displaystyle {\ tfrac {N + P} {2}}}$ ${\ displaystyle N + P}$ ${\ displaystyle - {\ tfrac {N + P} {2}}}$ ${\ displaystyle {\ tfrac {N + P} {2}}}$ ${\ displaystyle N + P}$

Transformacja dwuwymiarowa

W przetwarzaniu obrazu używamy dwuwymiarowej transformacji Fouriera. Jego dyskretna definicja to:

{\ Displaystyle S (u, v) = \ suma _ {m = 0} ^ {M-1} \ suma _ {n = 0} ^ {N-1} s (m, n) \ operatorname {e} ^ {-2 \ mathrm {i} \ pi \ left ({\ frac {um} {M}} + {\ frac {vn} {N}} \ right)}}

Aplikacje

TFD jest używany w szerokim spektrum zastosowań, tutaj wymieniono tylko najbardziej powszechne. Wszystkie te aplikacje wymagają istnienia szybkiego algorytmu obliczania DFT i jej odwrotności, patrz na ten temat szybkie metody transformacji Fouriera .

Analiza spektralna

Analiza widmowa sygnałów jest istotnym elementem w elektronice dla wielu powodów, w tym:

określanie szerokości pasma częstotliwości zajmowanej przez transmisję;
ocenić zniekształcenia harmoniczne spowodowane przetwarzaniem sygnału;
filtry pomiarowe.

Inżynier elektronik, który zawsze musi weryfikować eksperymentalnie, potrzebuje narzędzia pomiarowego, analizatora widma. Istnieją trzy główne rodziny analizatorów widma, z których każda ma charakterystyczne cechy:

Analizator widma skanowania (analogowy)

Jak sama nazwa wskazuje, analizator skanuje zakres częstotliwości za pomocą filtra o regulowanej szerokości. Jest w stanie mierzyć zakresy częstotliwości od audio po optykę dla sygnałów o bardzo niskiej amplitudzie.

Analizator widma FFT (cyfrowy)

FFT (szybka transformata Fouriera) jest tutaj używana po próbkowaniu sygnału wejściowego niskiej częstotliwości (audio). Zaleta: jest w stanie przechwytywać sygnały w czasie rzeczywistym z bardzo dobrą rozdzielczością widmową, która zależy od liczby punktów i zastosowanego okna ważenia. $NIE$

Zwiększona prędkość i rozdzielczość przetworników analogowo-cyfrowych pozwolą na analizę sygnałów przy coraz wyższych częstotliwościach.

Analizator sygnałów wektorowych (analogowy / cyfrowy)

Dzięki połączeniu technologii dwóch pierwszych (skanowania i FFT) umożliwia analizę sygnałów, których częstotliwości są oddzielone tylko o kilka MHz w całym zakresie częstotliwości radiowych. Szeroko stosowany w dziedzinie transmisji cyfrowych do analizy sygnałów złożonych (QAM, QPSK)

Kompresja danych

Przetwarzanie sygnału ogólnie szeroko wykorzystuje operacje w dziedzinie częstotliwości, w szczególności DFT lub jeden z jego wariantów. W przypadku kompresji dźwięku lub obrazu transformacje bliskie DFT (na przykład dyskretna transformata kosinusowa ) są zwykle stosowane do fragmentów sygnału w celu zmniejszenia ich złożoności. Współczynniki są następnie kwantyzowane z wyższymi krokami kwantyzacji dla wysokich częstotliwości, uważanych za nieistotne dla ludzkiej percepcji. Wzrost kompresji wynika ze zmniejszenia precyzji tych współczynników (lub nawet ich całkowitej eliminacji), które następnie wymagają kodowania mniejszej liczby bitów. Generalnie następuje etap kodowania entropijnego . Rekonstrukcja sygnału jest następnie przeprowadzana na podstawie tego zredukowanego zestawu skwantyzowanych współczynników. ${\ Displaystyle S (k)}$

Przykład: Na rysunku 1 łatwo zauważyć, że czasowe przetwarzanie sygnału bez utraty informacji wymaga zapamiętania 64 próbek, podczas gdy przetwarzanie częstotliwości wymaga tylko jednego punktu (pamiętając, że dwie linie niosą te same informacje). I nie ma żadnej straty.

Równania różniczkowe cząstkowe

Mnożenie dużych liczb całkowitych

Niektóre z najszybszych algorytmów mnożenia dużych liczb całkowitych są oparte na DFT. Ciągi cyfr są interpretowane jako elementy wektora, którego splot jest obliczany . W tym celu obliczamy ich DFT, które są mnożone razem ( splot czasu jest iloczynem częstotliwości), a następnie wykonujemy odwrotność DFT.

Analiza szeregów czasowych

DFT służy do badania szeregów czasowych (lub chronologicznych), gdzie celem jest znalezienie korelacji między dwiema sekwencjami danych. Klasycznym przykładem jest analiza cen giełdowych w celu wykrycia określonych wydarzeń. Problem polega na ogół na eksploracji danych lub wyszukiwaniu według podobieństw. TFD jest tu używany jako sposób na zmniejszenie wymiarowości problemu. DFT umożliwia dekorelację danych początkowych i pracę tylko na niewielkiej liczbie istotnych współczynników.

Niektóre klasyczne sygnały DFT

Niektóre sygnały i ich TFD

${\ Displaystyle x_ {k} = {\ Frac {1} {N}} \ suma _ {n = -N / 2} ^ {(N / 2) -1} X_ {n} \ operatorname {e} ^ { \ mathrm {i} 2 \ pi kn / N}}$	${\ Displaystyle X_ {n} = \ suma _ {k = 0} ^ {N-1} x_ {k} \ mathrm {e} ^ {- \ mathrm {i} 2 \ pi kn / N}}$	Uwaga
${\ displaystyle y_ {k} = x_ {k} \ mathrm {e} ^ {\ mathrm {i} 2 \ pi kl / N}}$	${\ Displaystyle Y_ {n} = X_ {nl}}$	Właściwość tłumaczenia
${\ displaystyle y_ {k} = x_ {kn}}$	${\ Displaystyle Y_ {n} = X_ {n} \ mathrm {e} ^ {- \ mathrm {i} 2 \ pi kn / N}}$	Właściwość tłumaczenia
${\ Displaystyle x_ {n} \ in \ mathbb {R}}$	${\ Displaystyle X_ {n} = X_ {Nn} ^ {*}}$	TFD prawdziwego sygnału
${\ displaystyle a ^ {k}}$	${\ Displaystyle {\ Frac {1-a ^ {N}} {1-a \ mathrm {e} ^ {- \ mathrm {i} 2 \ pi n / N}}}}$
${\ displaystyle {N-1 \ wybierz k}}$	${\ Displaystyle \ lewo (1+ \ mathrm {e} ^ {- \ mathrm {i} 2 \ pi n / N} \ prawej) ^ {N-1}}$

Zobacz też

Powiązane artykuły

Krążąca macierz, która daje geometryczną interpretację dyskretnej transformacji Fouriera
Krótkoterminowa transformata Fouriera

Bibliografia

Claude Gasquet i Patrick Witomski, Analiza Fouriera i zastosowania , Dunod, 1996
(en) Rakesh Agrawal, Christos Faloutsos i Arun Swami, „Efficient Podobneity Search In Sequence Databases”, w: Proceedings of the 4th International Conference of Foundations of Data Organisation and Algorithms , 1993, s. 69-84