Ayrık sinüs dönüşümü - Discrete sine transform

Gelen matematik , ayrık sinüs (DST) dönüşümü a, Fourier dönüşümü ile ilgili benzer bir ayrık Fourier dönüşümü (DFT), ancak tamamen kullanılarak gerçek matris . Bir YFT'nin kabaca iki katı uzunluktaki hayali kısımlarına eşdeğerdir, tek simetriyle gerçek veriler üzerinde çalışır (çünkü gerçek ve tek bir fonksiyonun Fourier dönüşümü hayali ve tuhaftır), burada bazı varyantlarda girdi ve / veya çıktı veriler yarım örnek kaydırılır.

Sinüs ve sinüs hiperbolik fonksiyonlarından oluşan bir dönüşüm ailesi mevcuttur. Bu dönüşümler, farklı sınır koşullarına sahip ince kare plakaların doğal titreşimine göre yapılır .

DST, gerçek ve hatta fonksiyonların DFT'sine eşdeğer olan ayrık kosinüs dönüşümü (DCT) ile ilgilidir . Sınır koşullarının çeşitli DCT ve DST türleriyle nasıl ilişkili olduğuna dair genel bir tartışma için DCT makalesine bakın. Genel olarak, DST değiştirerek DCT türetilmiştir Neumann durum en x = 0 , bir ile Dirichlet durum . Hem DCT hem de DST, 1974'te Nasir Ahmed T. Natarajan ve KR Rao tarafından tanımlandı. Tip-I DST (DST-I) daha sonra 1976'da Anil K. Jain tarafından ve tip-II DST (DST- II) daha sonra 1978'de HB Kekra ve JK Solanka tarafından tanımlandı.

Başvurular

DSTS yaygın çözmede kullanılır kısmi diferansiyel denklemler tarafından spektral yöntem , burada dizinin iki ucundan biraz farklı tek / çift sınır koşullarına DST tekabül farklı varyantları.

Gayri resmi genel bakış

En yaygın dört DST türü (tip I – IV) için N = 9 veri noktası (kırmızı noktalar) için DST giriş verilerinin örtük çift / tek uzantılarının çizimi .

Herhangi bir Fourier ile ilgili dönüşüm gibi, ayrık sinüs dönüşümleri (DST'ler) , farklı frekanslara ve genliklere sahip sinüzoidlerin toplamı cinsinden bir işlevi veya sinyali ifade eder . Gibi ayrık Fourier dönüşümü (DFT), bir DST ayrı veri noktaları sonlu sayıda bir fonksiyonu üzerinde çalışır. Bir DST ve bir DFT arasındaki bariz ayrım, birincisinin yalnızca sinüs fonksiyonlarını kullanırken, ikincisinin hem kosinüsleri hem de sinüsleri ( karmaşık üsler biçiminde ) kullanmasıdır. Bununla birlikte, bu görünür fark yalnızca daha derin bir ayrımın sonucudur: DST , DFT veya diğer ilgili dönüşümlerden farklı sınır koşullarını ifade eder .

DFT veya DST veya bir Fourier serisi gibi sonlu bir alan üzerinde bir fonksiyon üzerinde çalışan Fourier ile ilgili dönüşümler , bu fonksiyonun alan dışındaki bir uzantısını örtük olarak tanımlıyor olarak düşünülebilir . Yani, sinüzoidlerin toplamı olarak bir fonksiyon yazdıktan sonra, bu toplamı herhangi bir zamanda , orijinalin belirtilmediği durumlarda bile değerlendirebilirsiniz . DFT, Fourier serisi gibi , orijinal fonksiyonun periyodik bir genişlemesini ifade eder . DST, sinüs dönüşümü gibi , orijinal işlevin garip bir uzantısını ifade eder . ${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$

Bununla birlikte, DST'ler sonlu , ayrık diziler üzerinde çalıştığından , sürekli sinüs dönüşümü için geçerli olmayan iki sorun ortaya çıkar. İlk olarak, bir fonksiyon tek veya çift altında olup olmadığını belirtmek zorundadır hem (yani minimal- alanın sol ve sağ sınırları n ve MAX- n aşağıda tanımlarında sınırları, sırasıyla). İkinci olarak, fonksiyonun hangi noktada çift ​​veya tek olduğu belirtilmelidir. Özellikle, eşit aralıklı üç veri noktasından oluşan bir diziyi ( a , b , c ) düşünün ve tek bir sol sınır belirlediğimizi söyleyin . İki mantıklı olasılık vardır: ya veri noktası ile ilgili tek bir önceki için bir tek uzantı, bu durumda, (- C , - B -, bir 0, bir , b , c ) ya da veri tek yaklaşık nokta yarım arasında bir tek uzantı, bu durumda önceki noktada, (- c , - b , - bir , bir , b , c )

Bu seçimler, DST'lerin tüm standart varyasyonlarına ve ayrıca ayrık kosinüs dönüşümlerine ( DCT'ler) yol açar . Her sınır çift veya tek (sınır başına 2 seçenek) olabilir ve bir veri noktası veya toplam olasılıklar için iki veri noktası arasındaki nokta (sınır başına 2 seçenek) etrafında simetrik olabilir . Sol sınırın tuhaf olduğu bu olasılıkların yarısı , 8 tür DST'ye karşılık gelir; diğer yarısı 8 tür DCT'dir. ${\ displaystyle 2 \ times 2 \ times 2 \ times 2 = 16}$

Bu farklı sınır koşulları, dönüşümün uygulamalarını güçlü bir şekilde etkiler ve çeşitli DCT türleri için benzersiz şekilde kullanışlı özelliklere yol açar. Çözmek için Fourier ilgili transformu kullanıldığında çoğu doğrudan, kısmi diferansiyel denklemler tarafından spektral yöntemler , sınır koşulları, problemin bir parçası çözülmüş edilen örnekler olarak belirtilmektedir.

Tanım

Resmi olarak, ayrık sinüs dönüşümü doğrusal , tersinir bir fonksiyondur F  : R ^N -> R ^N (burada R , gerçek sayılar kümesini belirtir ) veya eşdeğer olarak bir N × N kare matristir . DST'nin biraz değiştirilmiş tanımlara sahip birkaç çeşidi vardır. K gerçek sayılar x ₀ , x _{N 1 -} dönüştürülen N gerçek sayılar X ₀ , X, _{N - 1} formüllerden birine göre yöntem:

DST-I

${\ displaystyle X_ {k} = \ toplam _ {n = 0} ^ {N-1} x_ {n} \ sin \ sol [{\ frac {\ pi} {N + 1}} (n + 1) ( k + 1) \ sağ] \ quad \ quad k = 0, \ dots, N-1}$

DST-I matrisi ortogonaldir (bir ölçek faktörüne kadar).

Bir DST-I, sıfırıncı ve orta noktaların etrafında tuhaf olan ve 1/2 ile ölçeklenen gerçek bir dizinin YFT'sine tam olarak eşdeğerdir. Örneğin, N = 3 gerçek sayıdan ( a , b , c ) oluşan bir DST-I, sekiz gerçek sayıdan oluşan bir DFT'ye (0, a , b , c , 0, - c , - b , - a ) tam olarak eşdeğerdir. (garip simetri), 1/2 ile ölçeklendirilmiştir. (Aksine, DST türleri II – IV eşdeğer DFT'de yarım örneklem kaymasını içerir.)  Sinüs fonksiyonunun paydasındaki N + 1'in nedeni budur : eşdeğer DFT'nin 2 ( N +1) noktası vardır ve sinüzoid frekansında 2π / 2 ( N +1) vardır, bu nedenle DST-I'in frekansında π / ( N +1) vardır.

Böylece, DST-I sınır koşullarına karşılık gelir: x _n , n  = around1 civarında tektir ve n = N civarında tekdir ; benzer şekilde X _{k için} .

DST-II

${\ displaystyle X_ {k} = \ toplam _ {n = 0} ^ {N-1} x_ {n} \ sin \ sol [{\ frac {\ pi} {N}} \ sol (n + {\ frac { 1} {2}} \ sağ) (k + 1) \ sağ] \ quad \ quad k = 0, \ dots, N-1}$

Bazı yazarlar ayrıca X _{N - 1} terimini 1 / √ 2 ile çarparlar (DST-III'deki ilgili değişiklik için aşağıya bakın). Bu, DST-II matrisini ortogonal yapar (bir ölçek faktörüne kadar), ancak yarı kaydırılmış girdinin gerçek tek DFT'si ile doğrudan yazışmayı bozar.

DST-II, sınır koşullarını ifade eder: x _n , n  = −1/2 civarında tektir ve n  =  N  - 1/2 civarında tekdir ; X _k , k  = −1 civarında ve hatta k  =  N  - 1 civarında tektir .

DST-III

${\ displaystyle X_ {k} = {\ frac {(-1) ^ {k}} {2}} x_ {N-1} + \ toplamı _ {n = 0} ^ {N-2} x_ {n} \ sin \ left [{\ frac {\ pi} {N}} (n + 1) \ left (k + {\ frac {1} {2}} \ sağ) \ sağ] \ quad \ quad k = 0, \ noktalar, N-1}$

Bazı yazarlar ayrıca x _{N - 1} terimini √ 2 ile çarparlar (DST-II'deki karşılık gelen değişiklik için yukarıya bakın). Bu, DST-III matrisini ortogonal yapar (bir ölçek faktörüne kadar), ancak yarı kaydırılmış çıktının gerçek tek DFT'si ile doğrudan yazışmayı bozar.

DST-III, sınır koşullarını ifade eder: x _n , n  = -1 civarında ve hatta n  =  N  - 1 civarında tektir ; X, _k isimli tek çevresinde k  = -1/2 ve tek çevresinde k  =  N  - 1/2.

DST-IV

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

DST-IV matrisi ortogonaldir (bir ölçek faktörüne kadar).

DST-IV, sınır koşullarını ifade eder: x _n , n  = -1/2 civarında ve hatta n  =  N  - 1/2 civarında tektir ; benzer şekilde X _{k için} .

DST V-VIII

DST türleri I – IV, çift sıra gerçek tek DFT'lere eşdeğerdir. Prensipte, sinüs argümanlarının paydalarında N +1/2 faktörlerine sahip olan, mantıksal olarak tek sıra gerçek tek DFT'lere karşılık gelen, aslında dört ek ayrık sinüs dönüşümü türü vardır (Martucci, 1994) . Bununla birlikte, bu varyantların pratikte nadiren kullanıldığı görülmektedir.

Ters dönüşümler

DST-I'in tersi DST-I'in 2 / ( N  + 1) ile çarpımıdır . DST-IV'ün tersi DST-IV'ün 2 / N ile çarpımıdır . DST-II'nin tersi DST-III'ün 2 / N ile çarpımıdır (ve tersi).

DFT'ye gelince , bu dönüşüm tanımlarının önündeki normalleştirme faktörü yalnızca bir konvansiyondur ve işlemler arasında farklılık gösterir. Örneğin, bazı yazarlar dönüşümleri ile çarparak , tersi herhangi bir ek çarpma faktörü gerektirmez. ${\ displaystyle {\ sqrt {2 / N}}}$

Hesaplama

Bu formüllerin doğrudan uygulanması O ( N ² ) işlemleri gerektirse de , aynı şeyi hızlı Fourier dönüşümüne (FFT) benzer hesaplamayı çarpanlara ayırarak sadece O ( N log N ) karmaşıklığı ile hesaplamak mümkündür . (DST'ler, O ( N ) ön ve son işleme adımlarıyla birlikte FFT'ler aracılığıyla da hesaplanabilir .)

Bir DST-III veya DST-IV , girişlerin sırasını ters çevirerek ve diğer her çıkışın işaretini çevirerek ve DST için tersi yaparak, sırasıyla DCT-III veya DCT-IV'ten ( ayrık kosinüs dönüşümü ) hesaplanabilir. -II, DCT-II'den. Bu şekilde, DST'nin II – IV türlerinin, karşılık gelen DCT türleriyle tam olarak aynı sayıda aritmetik işlem (toplama ve çarpma) gerektirdiği anlaşılır.

Referanslar

Kaynakça

• SA Martucci, "Simetrik evrişim ve ayrık sinüs ve kosinüs dönüşümleri," IEEE Trans. Sinyal Süreci. SP-42 , 1038-1051 (1994).
• Matteo Frigo ve Steven G. Johnson : FFTW , http://www.fftw.org/ . Bir veya daha fazla boyutta, rastgele boyutta hızlı DST'leri (tip I – IV) hesaplayabilen ücretsiz ( GPL ) C kitaplığı. Ayrıca M. Frigo ve SG Johnson, " The Design and Implementation of FFTW3 ," Proceedings of the IEEE 93 (2), 216–231 (2005).
• Takuya Ooura: Genel Amaçlı FFT Paketi, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Bir, iki veya üç boyutta, 2 boyutta güçte hızlı DST'leri hesaplamak için ücretsiz C & FORTRAN kitaplıkları.
• Basın, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Bölüm 12.4.1. Sinüs Dönüşümü" , Sayısal Tarifler: Bilimsel Hesaplama Sanatı (3. baskı), New York: Cambridge University Press, ISBN   978-0-521-88068-8 .
• R. Chivukula ve Y. Reznik, " Kesikli Kosinüs ve Tip VI ve VII'nin Sinüs Dönüşümlerinin Hızlı Hesaplanması ", Proc. SPIE Cilt. 8135, 2011.