Diskretna furijeova transformacija
Diskretna Furijeova transformacija ili DFT jeste Furijeova transformacija diskretnog i konačnog (ili periodičnog) signala. Diskretna Furijeova transformacija je time i specijalni oblik Z-transformacije kod koje se z nalazi na jediničnom krugu. Često se koristi pri obradi digitalnih signala, a najpoznatiji algoritam za to je brza furijeova transformacija (FFT, Fast Fourier Transformation, engl.).
Diskretna Furijeova transformacija može da posluži takođe za aproksimaciju (u određenim slučajevima i rekonstrukciju) funkcije koja odgovara signalu ili kao implementacija digitalnih filtera.
Putem inverzne Furijeove transformacije se iz Furijeovih koeficijenata sklapa izlazni signal, a povezivanjem DFT i inverzne DFT možemo da manipulišemo frekvencijama (nalazi primenu pri ekvilajzerima i filterima).
Definicija
Uzmimo da je komutativan, unitaran prsten, u kojem je broj jedinica. Dalje, u je jedinični koren.
Za vektor je diskretna furijeova transformacija na sledeći način definisana:
za
A za , inverzna furijeova transformacija je
za
DFT i IDFT u kompleksnom domenu
U kompleksnom domenu koristimo .
Onda je DFT za : za ,
a IDFT za : za
DFT i IDFT u realnom domenu
Računica u realnom domenu je:
Ojlerov identitet glasi: . Takođe važi i .
Stoga možemo još uprostiti izraz:
Što će reći, nije realan, ali samo N nezavisnih vrednosti (umesto 2N).
Za IDFT možemo zaključiti sledeće: Ukoliko za važi za sve , onda je IDFT realan vektor .
Pomeranje i skaliranje u vremenu i frekvenciji
Ako je signal periodičan, onda nije bitno da li transformišemo u opsegu ili . Indeksna promenljiva j treba da obuhvati N opseg, ali nije bitno gde on počinje odnosno gde se završava (ovo važi samo za slučaj da je signal periodičan, tj. da se vektor periodično ponavlja). Prisetimo se: za važi . Onda .
U praksi često želimo da razlika u indeksima bude istovremeno i razlika u vremenu ili razdaljini dva merenja
- , je perioda našeg merenja.
Često želimo i da koeficijentima dodelimo frekvenciju tako da su centrirane oko
- , je negde u blizini .
Uzmimo neku funkciju kojoj dodeljujemo tako da .
DFT je onda .
Iz toga sledi:
a IDFT je
Primeri
Primer filtera
Naš cilj je da izbacimo sve frekvencije koje su „tiše“ (tj. koje imaju amplitudu) od 1 V. Prvo pravimo tabelu:
0.5000 | 0.6000 | 0.7000 | 0.8000 | 0.9000 | 1.0000 | 1.1000 | 1.2000 | 1.3000 | 1.4000 | |
12.5000 | 10.0995 | 7.6644 | 6.8554 | 9.7905 | 13.5000 | 11.7546 | 7.4815 | 8.2905 | 12.0636 |
Imamo 10 vrednosti na 1 sekundu, što će reći perioda našeg merenja je , a frekvencija . Stoga mi možemo da rekonstruišemo talas do 5 Hz. Ukoliko u našem originalnom signalu ima frekvencija viših od 5 Hz onda će naša rekonstrukcija imati grešku. Ali, kao i uvek u životu, čovek mora biti optimističan te ćemo mi pretpostaviti da nema viših frekvencija (to je uostalom i jedan od razloga zašto kompakt-disk ima frekvenciju od oko 41 kHz; ljudsko uho može da registruje tek do 20 kHz!).
Sledi izračunavanje . Nas zanimaju samo vrednosti vezane za pozitivne indekse:
Sada imamo sve vrednosti i možemo da počnemo sa računanjem:
Izračunavanje ostalih koeficijenata ide analogno, te ćemo ih ovde samo navesti kao rezultate:
Imamo , sada želimo da izbacimo sve previše „tihe“ tonove. Trebaju nam :
10 -0.35i 1.5 - 0i 0.25 - 0.3i 0 + 0i
Znamo da važi: . Na taj način možemo da izračunamo i :
Ostale amplitude:
Iz možemo da zaključimo da frekvencija od 4 Hz nema u našem signalu. Često je vrlo zgodno navesti sve amplitude u grafikonu. Amplituda za neku frekvenciju je .
Sve i za koje važi izbacujemo i na kraju dobijamo rekonstruisanu i obrađenu funkciju:
Sada možemo da ponovo da izračunamo ili da se poslužimo IDFT i tako prerađen signal snimimo u memoriju.
Primer u C-u
#include <stdio.h> #include <math.h> #include <complex.h> #define pi 3.14159265 #define N 1000 #define T 0.001 #define FREQ 25 double my_function (double t ) { /* violina svira ton od 25 Hz */ double ugaona_brzina = 2 * pi * FREQ; return 5 + 10 * cos(ugaona_brzina * t) + 15 * cos(2 * (ugaona_brzina * t) ) + 20 * sin (3 * (ugaona_brzina * t) ); } complex double get_fourier_coef (double omega_n, double* t, double* f ) { complex double coeff = 0; int k = 0; for (k = 0; k < N; k ++ ) { // f[k] == f(t[k] ); coeff += cexp (- I * omega_n * t[k]) * f[ k] ; } return coeff; } int main() { double t[N]; double omega[N]; double f[N]; double a[N/2+1]; double phi[N/2+1]; int n = 0; complex double coeff[N]; /* pripremi vektore t i f_t -> nas signal je f_t !*/ t[0] = 0; f[0] = my_function (t[0] ); omega[0] = 0; for (n = 1; n < N; n ++ ) { omega[n] = 2 * pi * n / (N * T ); t[n] = n * T; f[n] = my_function (t[n] ); } /* izracunavanje koeficijenata */ for (n = 0; n < N/2+1; n ++ ) { coeff[n] = get_fourier_coef (omega[n], t, f ); if (cabs(coeff[n]) > 0.1 ){ printf ("# Koeficijent %d: %e * e^i*%e\n", n, cabs(coeff[n]), carg(coeff[n]) ); } } /* krece inverzija: */ a[0] = cabs(coeff[0]) / N; phi[0] = 0; for (n = 1; n < N/2+1; n++ ) { if (cabs(coeff[n]) > 0.1 ) { // c = 1/2 (a + ib ), zato a = 2 * |c|, b == 0 a[n] = 2 * cabs(coeff[n]) / N; if (abs (carg(coeff[n])) > 0.001 ) { phi[n] = carg(coeff[n] ); } else { phi[n] = 0; } } else { a[n] = 0; phi[n] = 0; } } /* predstavljanje rezultata: */ printf ("Nasa rekonstrukcija:\n f (t) = %e", a[0] ); for (n = 1; n < N/2+1; n++ ) { if (a[n] ) { if (phi[n] ) { printf (" + %e * cos (%d * (2 * pi * t + %e) )", a[n], n, phi[n] ); } else { printf ("+ %e * cos (%d * 2 * pi * t )", a[n], n ); } } } printf ("\n" ); return 0; }
Literatura
- Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-307505-2.
- Alan V. Oppenheim, Ronald W. Schafer, Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 978-0-13-754920-7.
- Smith, Steven W. (1999). „Chapter 8: The Discrete Fourier Transform”. The Scientist and Engineer's Guide to Digital Signal Processing (Second izd.). San Diego, Calif.: California Technical Publishing. ISBN 978-0-9660176-3-2.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). „Chapter 30: Polynomials and the FFT”. Introduction to Algorithms (Second izd.). MIT Press and McGraw-Hill. str. 822-848. ISBN 978-0-262-03293-3. esp. section 30.2: The DFT and FFT, pp. 830–838.
- P. Duhamel, B. Piron, and J. M. Etcheto (1988). „On computing the inverse DFT”. IEEE Trans. Acoust., Speech and Sig. Processing 36 (2): 285-286. DOI:10.1109/29.1519.
- J. H. McClellan and T. W. Parks (1972). „Eigenvalues and eigenvectors of the discrete Fourier transformation”. IEEE Trans. Audio Electroacoust. 20 (1): 66-74. DOI:10.1109/TAU.1972.1162342.
- Bradley W. Dickinson and Kenneth Steiglitz (1982). „Eigenvectors and functions of the discrete Fourier transform”. IEEE Trans. Acoust., Speech and Sig. Processing 30 (1): 25-31. DOI:10.1109/TASSP.1982.1163843.
- F. A. Grünbaum (1982). „The eigenvectors of the discrete Fourier transform”. J. Math. Anal. Appl. 88 (2): 355-363. DOI:10.1016/0022-247X(82)90199-8.
- Natig M. Atakishiyev and Kurt Bernardo Wolf (1997). „Fractional Fourier-Kravchuk transform”. J. Opt. Soc. Am. A 14 (7): 1467-1477. DOI:10.1364/JOSAA.14.001467.
- C. Candan, M. A. Kutay and H. M.Ozaktas (2000). „The discrete fractional Fourier transform”. IEEE Trans. on Signal Processing 48 (5): 1329-1337. DOI:10.1109/78.839980.
- Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). „Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices”. IEEE Trans. Circ. Syst. I 51 (11): 2245-2254. DOI:10.1109/TCSI.2004.836850.
- Shamgar Gurevich and Ronny Hadani (2009). „On the diagonalization of the discrete Fourier transform”. Applied and Computational Harmonic Analysis 27 (1): 87-99. DOI:10.1016/j.acha.2008.11.003. preprint at.
- Shamgar Gurevich, Ronny Hadani, and Nir Sochen (2008). „The finite harmonic oscillator and its applications to sequences, communication and radar”. IEEE Transactions on Information Theory 54 (9): 4239-4253. DOI:10.1109/TIT.2008.926440. preprint at.
- Juan G. Vargas-Rubio and Balu Santhanam (2005). „On the multiangle centered discrete fractional Fourier transform”. IEEE Sig. Proc. Lett. 12 (4): 273-276. DOI:10.1109/LSP.2005.843762.
- James Cooley, P. Lewis, and P. Welch (1969). „The finite Fourier transform”. IEEE Trans. Audio Electroacoustics 17 (2): 77-85. DOI:10.1109/TAU.1969.1162036.
- F.N. Kong (2008). „Analytic Expressions of Two Discrete Hermite-Gaussian Signals”. IEEE Trans. Circuits and Systems –II: Express Briefs. 55 (1): 56-60. DOI:10.1109/TCSII.2007.909865.
Povezano
- Dualnost po Pontrjaginu