Dyskretna transformata sinusoidalna

W matematyce dyskretna transformata sinusoidalna (DST) jest transformacją związaną z Fourierem, podobną do dyskretnej transformaty Fouriera (DFT), ale wykorzystującą czysto rzeczywistą macierz . Jest to równoważne urojonym częściom DFT o mniej więcej dwukrotnie większej długości, operującym na rzeczywistych danych z nieparzystą symetrią (ponieważ transformata Fouriera funkcji rzeczywistej i nieparzystej jest urojona i nieparzysta), gdzie w niektórych wariantach wejście i / lub wyjście dane są przesunięte o połowę próbki.

rodzina przekształceń złożonych z sinusoidalnych i sinusoidalnych funkcji hiperbolicznych. Transformacje te są wykonywane w oparciu o drgania własne cienkich płyt kwadratowych o różnych warunkach brzegowych .

DST jest powiązany z dyskretną transformatą kosinusową (DCT), która jest odpowiednikiem DFT funkcji rzeczywistych i parzystych . Zobacz artykuł DCT, aby zapoznać się z ogólnym omówieniem, w jaki sposób warunki brzegowe odnoszą się do różnych typów DCT i DST. Ogólnie rzecz biorąc, DST wyprowadza się z DCT przez zastąpienie warunku Neumanna przy x=0 warunkiem Dirichleta . Zarówno DCT, jak i DST zostały opisane przez Nasira Ahmeda , T. Natarajana i KR Rao w 1974 r. DST typu I (DST-I) został później opisany przez Anila K. Jaina w 1976 r., a DST typu II ( DST-II) został następnie opisany przez HB Kekrę i JK Solankę w 1978 roku.

Aplikacje

DST są szeroko stosowane w rozwiązywaniu równań różniczkowych cząstkowych metodami spektralnymi , gdzie różne warianty DST odpowiadają nieco różnym nieparzystym/parzystym warunkom brzegowym na dwóch końcach tablicy.

Nieformalny przegląd

Ilustracja niejawnych parzystych / nieparzystych rozszerzeń danych wejściowych DST dla N = 9 punktów danych (czerwone kropki) dla czterech najpowszechniejszych typów DST (typy I – IV).

Jak każda transformata związana z Fourierem, dyskretne transformaty sinusoidalne (DST) wyrażają funkcję lub sygnał w kategoriach sumy sinusoid o różnych częstotliwościach i amplitudach . Podobnie jak dyskretna transformata Fouriera (DFT), DST działa na funkcji w skończonej liczbie dyskretnych punktów danych. Oczywista różnica między DST i DFT polega na tym, że ta pierwsza używa tylko funkcji sinusoidalnych , podczas gdy ta druga używa zarówno cosinusów, jak i sinusów (w postaci złożonych wykładników ). Jednak ta widoczna różnica jest jedynie konsekwencją głębszego rozróżnienia: DST implikuje inne warunki brzegowe niż DFT lub inne powiązane transformacje.

Transformacje związane z Fourierem, które działają na funkcji w dziedzinie skończonej , takie jak DFT lub DST lub szereg Fouriera , można traktować jako niejawnie definiujące rozszerzenie tej funkcji poza dziedzinę. $,$ to, że gdy napiszesz funkcję $displaystyle x$ sumę sinusoid, możesz oszacować tę sumę w dowolnym miejscu x $}$ gdzie oryginał nie został określony ${\ Displaystyle f (x)} .$ DFT, podobnie jak szereg Fouriera, implikuje okresowe rozszerzenie pierwotnej funkcji. Czas letni, podobnie jak transformata sinusoidalna , implikuje dziwne rozszerzenie oryginalnej funkcji.

Ponieważ jednak DST działają na skończonych , dyskretnych sekwencjach, pojawiają się dwa problemy, które nie dotyczą ciągłej transformacji sinusoidalnej. Najpierw należy określić, czy funkcja jest parzysta czy nieparzysta zarówno na lewej, jak i prawej granicy dziedziny (tj. odpowiednio na granicach min- n i max- n w poniższych definicjach). Po drugie, należy określić, wokół którego punktu funkcja jest parzysta lub nieparzysta. W szczególności rozważ sekwencję ( a , b , c ) trzech równomiernie rozmieszczonych punktów danych i powiedz, że określamy nieparzystą lewą granicę. Istnieją dwie sensowne możliwości: albo dane są nieparzyste względem punktu poprzedzającego a , w którym to przypadku nieparzyste rozszerzenie wynosi (− c , − b , − a ,0, a , b , c ), albo dane są nieparzyste względem punkt w połowie drogi między a a poprzednim punktem, w którym to przypadku nieparzyste rozszerzenie wynosi (− c , − b , − a , a , b , c )

Te wybory prowadzą do wszystkich standardowych odmian DST, a także dyskretnych transformat kosinusowych (DCT). Każda granica może być parzysta lub nieparzysta (2 wybory na granicę) i może być symetryczna względem punktu danych lub punktu w połowie drogi między dwoma punktami danych (2 wybory na granicę), w sumie ${\ Displaystyle 2 \ razy 2 \ razy 2 \ razy 2 = 16}$ możliwości. Połowa z tych możliwości, gdzie lewa granica jest nieparzysta, odpowiada 8 typom czasu letniego; druga połowa to 8 rodzajów DCT.

Te różne warunki brzegowe silnie wpływają na zastosowania transformacji i prowadzą do wyjątkowo użytecznych właściwości dla różnych typów DCT. Najbardziej bezpośrednio, gdy używa się transformat związanych z Fourierem do rozwiązywania równań różniczkowych cząstkowych metodami spektralnymi , warunki brzegowe są bezpośrednio określane jako część rozwiązywanego problemu.

Definicja

₀₀ Formalnie dyskretna transformata sinusoidalna jest liniową , odwracalną funkcją F : R ^N -> R ^N ( gdzie R oznacza zbiór liczb rzeczywistych ) lub równoważnie macierzą kwadratową N × N. Istnieje kilka wariantów DST z nieco zmodyfikowanymi definicjami. N liczb rzeczywistych x ,..., x _{N − 1} przekształcamy na N liczb rzeczywistych X ,..., X _{N 1} − według jednego ze wzorów:

czas letni-I

${\ Displaystyle X_ {k} = \ suma _ {n =0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N+1}}(n+1)(k+1)\right]\quad \quad k= 0,\kropki ,N-1}$

Macierz DST-I jest ortogonalna (do współczynnika skali).

DST-I jest dokładnie równoważny DFT rzeczywistej sekwencji, która jest nieparzysta wokół punktu zerowego i środkowego, przeskalowana o 1/2. Na przykład DST-I N = 3 liczb rzeczywistych ( a , b , c ) jest dokładnie równoważne DFT ośmiu liczb rzeczywistych (0, a , b , c , 0, − c , − b , − a ) (symetria nieparzysta), przeskalowane o 1/2. (Dla kontrastu, typy DST II – IV obejmują przesunięcie o połowę w równoważnej DFT.) To jest powód N + 1 w mianowniku funkcji sinus: równoważna DFT ma 2 ( N + 1) punkty i ma 2π/2( N +1) w swojej częstotliwości sinusoidalnej, więc DST-I ma π/( N +1) w swojej częstotliwości.

Zatem DST-I odpowiada warunkom brzegowym: x _n jest nieparzyste wokół n = −1 i nieparzyste wokół n = N ; podobnie dla X _k .

DST-II

${\ Displaystyle X_ {k} = \ suma _ {n = 0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)(k+1) \right]\quad \quad k=0,\dots ,N-1}$

Niektórzy autorzy dodatkowo mnożą termin X _{N - 1} przez 1/ √ 2 (patrz poniżej odpowiednia zmiana w DST-III). To sprawia, że ​​​​matryca DST-II jest ortogonalna (do współczynnika skali), ale przerywa bezpośrednią zgodność z rzeczywistą nieparzystą DFT półprzesuniętego wejścia.

DST-II implikuje warunki brzegowe: x _n jest nieparzyste wokół n = -1/2 i nieparzyste wokół n = N - 1/2; X _k jest nieparzyste wokół k = −1, a nawet wokół k = N − 1.

DST-III

$${\ Displaystyle X_{k}={\frac {(-1)^{k}}{2}}x_{N-1}+\suma _{n=0}^{N-2}x_{n}\sin \ left[{\frac {\pi}}{N}}(n+1)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\kropki ,N -1}$$

Niektórzy autorzy dalej mnożą wyraz x _{N - 1} przez √ 2 (patrz powyżej dla odpowiedniej zmiany w DST-II). To sprawia, że ​​​​matryca DST-III jest ortogonalna (do współczynnika skali), ale przerywa bezpośrednią zgodność z rzeczywistą nieparzystą DFT wyjścia przesuniętego w połowie.

DST-III implikuje warunki brzegowe: x _n jest nieparzyste wokół n = −1, a nawet wokół n = N − 1; X _k jest nieparzyste wokół k = −1/2 i nieparzyste wokół k = N − 1/2.

DST-IV

${\ Displaystyle X_ {k} = \ suma _ {n =0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+ {\frac {1}{2}}\right)\right]\quad \quad k=0,\kropki ,N-1}$

Macierz DST-IV jest ortogonalna (do współczynnika skali).

DST-IV implikuje warunki brzegowe: x _n jest nieparzyste wokół n = -1/2, a nawet wokół n = N - 1/2; podobnie dla X _k .

DST V–VIII

Typy DST I – IV są równoważne rzeczywistym nieparzystym DFT parzystego rzędu. Zasadniczo istnieją cztery dodatkowe typy dyskretnej transformaty sinusoidalnej (Martucci, 1994), odpowiadające rzeczywistym-nieparzystym DFT logicznie nieparzystego rzędu, które mają współczynniki N +1/2 w mianownikach argumentów sinusoidalnych. Jednak te warianty wydają się być rzadko stosowane w praktyce.

Transformacje odwrotne

Odwrotnością DST-I jest pomnożenie DST-I przez 2/( N + 1). Odwrotnością DST-IV jest pomnożenie DST-IV przez 2/ N . Odwrotnością DST-II jest pomnożenie DST-III przez 2/ N (i odwrotnie).

Jeśli chodzi o DFT , współczynnik normalizacji przed tymi definicjami transformacji jest jedynie konwencją i różni się w zależności od leczenia. Na przykład niektórzy $autorzy$ mnożą przekształcenia przez tak żadnego dodatkowego mnożnika.

Obliczenie

Chociaż bezpośrednie zastosowanie tych wzorów wymagałoby operacji O( N ² ), możliwe jest obliczenie tego samego przy złożoności jedynie O ( N log N ) poprzez faktoryzację obliczeń podobnych do szybkiej transformaty Fouriera (FFT). (Można również obliczyć DST za pomocą FFT w połączeniu z etapami przetwarzania wstępnego i końcowego O ( N ).)

DST-III lub DST-IV można obliczyć odpowiednio z DCT-III lub DCT-IV (patrz dyskretna transformata kosinusowa ), odwracając kolejność wejść i odwracając znak każdego innego wyjścia i odwrotnie dla DST -II z DCT-II. W ten sposób wynika, że ​​typy II–IV DST wymagają dokładnie takiej samej liczby operacji arytmetycznych (dodawania i mnożenia), jak odpowiadające im typy DCT.

Bibliografia

• SA Martucci, „Splot symetryczny i dyskretne przekształcenia sinusoidalne i cosinusowe”, IEEE Trans. Proces sygnału. SP-42 , 1038-1051 (1994).
• Matteo Frigo i Steven G. Johnson : FFTW , strona główna FFTW . Wolna ( GPL ) biblioteka C, która może obliczać szybkie DST (typy I – IV) w jednym lub więcej wymiarach, o dowolnym rozmiarze. Również M. Frigo i SG Johnson, „ Projektowanie i wdrażanie FFTW3 ”, Proceedings of the IEEE 93 (2), 216–231 (2005).
• Takuya Ooura: pakiet FFT ogólnego przeznaczenia, pakiet FFT 1-dim / 2-dim . Darmowe biblioteki C & FORTRAN do obliczania szybkich DST w jednym, dwóch lub trzech wymiarach, potęga 2 rozmiarów.
•   Prasa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Sekcja 12.4.1. Transformacja sinusoidalna” , Przepisy numeryczne: sztuka obliczeń naukowych (wyd. 3), Nowy Jork: Cambridge University Press, ISBN 978-0-521-88068-8 .
• R. Chivukula i Y. Reznik, „ Szybkie obliczanie dyskretnych transformacji cosinusowych i sinusoidalnych typów VI i VII ”, Proc. SPIE Cz. 8135, 2011.