Diskrétní sinusová transformace - Discrete sine transform

V matematiky je diskrétní sinus transformace (DST) je Fourierova transformace související podobný diskrétní Fourierovy transformace (DFT), ale za použití čistě reálnou matici . Je ekvivalentní imaginárním částem DFT zhruba dvojnásobné délky, fungujícím na reálných datech s lichou symetrií (protože Fourierova transformace reálné a liché funkce je imaginární a lichá), kde v některých variantách vstup a / nebo výstup data jsou posunuta o polovinu vzorku.

Existuje řada transformací složených ze sinusových a sinusových hyperbolických funkcí. Tyto transformace jsou prováděny na základě přirozených vibrací tenkých čtvercových desek s různými okrajovými podmínkami .

DST souvisí s diskrétní kosinusovou transformací (DCT), která je ekvivalentní DFT skutečných a sudých funkcí. V článku DCT najdete obecnou diskusi o tom, jak okrajové podmínky souvisejí s různými typy DCT a DST. Obecně platí, že DST je odvozen od DCT nahrazením stav Neumann při x = 0 s Dirichlet stavu . DCT i DST popsali Nasir Ahmed T. Natarajan a KR Rao v roce 1974. Typ DST typu I (DST-I) popsal později Anil K. Jain v roce 1976 a typ II DST (DST- II) poté popsali HB Kekra a JK Solanka v roce 1978.

Aplikace

DST jsou široce používají v řešení parciálních diferenciálních rovnic pomocí spektrálních metod , kde se různé varianty DST odpovídají mírně odlišnými liché / sudé okrajových podmínek na obou koncích pole.

Neformální přehled

Ilustrace implicitních sudých / lichých rozšíření vstupních dat DST, pro N = 9 datových bodů (červené tečky), pro čtyři nejběžnější typy DST (typy I – IV).

Jako každá Fourierova transformace, diskrétní sinusové transformace (DST) vyjadřují funkci nebo signál, pokud jde o součet sinusoidů s různými frekvencemi a amplitudami . Stejně jako diskrétní Fourierova transformace (DFT) pracuje DST na funkci v konečném počtu diskrétních datových bodů. Zjevný rozdíl mezi DST a DFT spočívá v tom, že první používá pouze sinusové funkce , zatímco druhý používá kosiny i sinusy (ve formě komplexních exponenciálů ). Tento viditelný rozdíl je však pouze důsledkem hlubšího rozlišení: DST implikuje jiné okrajové podmínky než DFT nebo jiné související transformace.

Fourierovy transformace, které fungují na funkci nad konečnou doménou , jako je DFT nebo DST nebo Fourierova řada , lze považovat za implicitně definující rozšíření této funkce mimo doménu. To znamená, že jakmile napíšete funkci jako součet sinusoid, můžete tuto částku vyhodnotit kdykoli , dokonce i tam, kde nebyl zadán originál. DFT, stejně jako Fourierova řada, implikuje periodické rozšíření původní funkce. DST, jako sinusová transformace , implikuje liché rozšíření původní funkce. ${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$

Nicméně, protože DSTs pracují na Finite , nespojitých sekvencí, dvě otázky vyvstávají, které neplatí pro kontinuální sine transformace. Za prvé, je třeba určit, zda funkce sudé nebo liché na obou levé a pravé hranice domény (tj min- n a MAX n hranice v následujících definicích, v tomto pořadí). Zadruhé je třeba určit, kolem kterého bodu je funkce sudá nebo lichá. Zvažte zejména posloupnost ( a , b , c ) tří stejně rozmístěných datových bodů a řekněte, že určujeme lichou levou hranici. Existují dvě rozumné možnosti: buď data zvláštní kolem bodu před na , v tomto případě je zvláštní rozšíření je (- c , - b , - , 0, , b , c ), nebo data je divného bod na půli cesty mezi a a předchozím bodem, v takovém případě je liché prodloužení (- c , - b , - a , a , b , c )

Tyto volby vedou ke všem standardním variantám DST a také k diskrétním kosinovým transformacím (DCT). Každá hranice může být sudá nebo lichá (2 volby na hranici) a může být symetrická ohledně datového bodu nebo bodu na půli cesty mezi dvěma datovými body (2 volby na hranici), což je celkem možností. Polovina z těchto možností, ty, kde je levá hranice lichá, odpovídají 8 typům DST; druhá polovina je 8 typů DCT. ${\ displaystyle 2 \ krát 2 \ krát 2 \ krát 2 = 16}$

Tyto různé okrajové podmínky silně ovlivňují aplikace transformace a vedou k jedinečně užitečným vlastnostem pro různé typy DCT. Většina přímo, při použití s Fourierovou transformací související řešit parciální diferenciální rovnice podle spektrálních metod , okrajové podmínky jsou přímo určeny jako součást řešeného problému.

Definice

Formálně diskrétní sinus transformace je lineární , invertibilní funkce F  : R ^N -> R ^N (kde R označuje soubor reálných čísel ), nebo ekvivalentně N x N čtvercová matice . Existuje několik variant letního času s mírně upravenými definicemi. Tyto N reálná čísla x ₀ , x _{N - 1} se přemění na N reálných čísel X ₀ , X _{N - 1} podle jednoho ze vzorců:

DST-I

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

Matice DST-I je ortogonální (až do měřítka).

DST-I je přesně ekvivalentní DFT skutečné sekvence, která je lichá kolem nulového a středního bodu, zmenšená o 1/2. Například DST-I N = 3 reálná čísla ( a , b , c ) je přesně ekvivalentní DFT osmi reálných čísel (0, a , b , c , 0, - c , - b , - a ) (lichá symetrie), zmenšen o 1/2. (Naproti tomu typy DST II – IV zahrnují posun poloviny vzorku v ekvivalentním DFT.) To je důvod pro N  + 1 ve jmenovateli sinusové funkce: ekvivalentní DFT má 2 ( N +1) body a má 2π / 2 ( N +1) ve své sinusoidní frekvenci, takže DST-I má ve své frekvenci π / ( N +1).

DST-I tedy odpovídá okrajovým podmínkám: x _n je liché kolem n  = −1 a liché kolem n = N ; podobně pro X _k .

DST-II

${\ displaystyle X_ {k} = \ součet _ {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}$

Někteří autoři dále vynásobí X _{N - 1} člen 1 / √ 2 (odpovídající změnu v DST-III viz níže). Díky tomu je matice DST-II ortogonální (až do měřítka), ale přeruší přímou korespondenci se skutečným lichým DFT s polovičně posunutým vstupem.

DST-II implikuje okrajové podmínky: x _n je liché kolem n  = −1/2 a liché kolem n  =  N  - 1/2; X _k je liché kolem k  = −1 a sudé kolem k  =  N  - 1.

DST-III

${\ displaystyle X_ {k} = {\ frac {(-1) ^ {k}} {2}} x_ {N-1} + \ součet _ {n = 0} ^ {N-2} x_ {n} \ sin \ left [{\ frac {\ pi} {N}} (n + 1) \ left (k + {\ frac {1} {2}} \ right) \ right] \ quad \ quad k = 0, \ tečky, N-1}$

Někteří autoři dále Vynásobte x _{N - 1} termín √ 2 (viz výše pro odpovídající změny DST-II). Díky tomu je matice DST-III ortogonální (až do měřítka), ale přerušuje přímou korespondenci se skutečným lichým DFT s polovičně posunutým výstupem.

DST-III implikuje okrajové podmínky: x _n je liché kolem n  = −1 a sudé kolem n  =  N  - 1; X _k je liché kolem k  = −1/2 a liché kolem k  =  N  - 1/2.

DST-IV

${\ displaystyle X_ {k} = \ součet _ {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, \ dots, N-1}$

Matice DST-IV je ortogonální (až do měřítka).

DST-IV implikuje okrajové podmínky: x _n je liché kolem n  = −1/2 a sudé kolem n  =  N  - 1/2; podobně pro X _k .

DST V – VIII

Typy DST I – IV jsou ekvivalentní skutečným lichým DFT sudého pořadí. V zásadě vlastně existují čtyři další typy diskrétní sinusové transformace (Martucci, 1994), které odpovídají skutečným lichým DFT logicky lichého řádu, které mají ve jmenovatelích sine argumentů faktory N +1/2. Zdá se však, že se tyto varianty v praxi používají jen zřídka.

Inverzní transformace

Inverze DST-I je DST-I vynásobená 2 / ( N  + 1). Inverzní DST-IV je DST-IV násobí 2 / N . Inverze DST-II je DST-III vynásobená 2 / N (a naopak).

Pokud jde o DFT , normalizační faktor před těmito definicemi transformace je pouze konvence a liší se mezi léčbami. Někteří autoři například vynásobí transformace tak, že inverze nevyžaduje žádný další multiplikativní faktor. ${\ displaystyle {\ sqrt {2 / N}}}$

Výpočet

Ačkoli přímé použití těchto vzorců by vyžadovalo operace O ( N ² ), je možné vypočítat totéž s pouze složitostí O ( N log N ) faktorizováním výpočtu podobného rychlé Fourierově transformaci (FFT). (Lze také vypočítat DST pomocí FFT v kombinaci s kroky O ( N ) před a po zpracování.)

DST-III nebo DST-IV lze vypočítat z DCT-III nebo DCT-IV (viz diskrétní kosinová transformace ) obrácením pořadí vstupů a převrácením znaménka všech ostatních výstupů a naopak pro DST -II z DCT-II. Tímto způsobem vyplývá, že typy II – IV letního času vyžadují přesně stejný počet aritmetických operací (sčítání a násobení) jako odpovídající typy DCT.

Reference

Bibliografie

• SA Martucci, „Symetrická konvoluce a diskrétní sinusové a kosinové transformace,“ IEEE Trans. Proces signálu. SP-42 , 1038–1051 (1994).
• Matteo Frigo a Steven G. Johnson : FFTW , http://www.fftw.org/ . Volná ( GPL ) C knihovna, která dokáže vypočítat rychlé DST (typy I – IV) v jedné nebo více dimenzích libovolné velikosti. Také M. Frigo a SG Johnson, „ The Design and Implementation of FFTW3 ,“ Proceedings of the IEEE 93 (2), 216–231 (2005).
• Takuya Ooura: Balíček FFT pro všeobecné použití, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Zdarma knihovny C & FORTRAN pro výpočet rychlých letních časů v jedné, dvou nebo třech rozměrech, výkon 2 velikostí.
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 12.4.1. Sinusová transformace“ , Numerické recepty: Umění vědecké práce na počítači (3. vydání), New York: Cambridge University Press, ISBN   978-0-521-88068-8 .
• R. Chivukula a Y. Reznik, „ Rychlé výpočty diskrétních kosinových a sinusových transformací typů VI a VII “, Proc. SPIE sv. 8135, 2011.