Дискретна Фуријеова трансформација

Дискретна Фуријеова трансформација или ДФТ јесте Фуријеова трансформација дискретног и коначног (или периодичног) сигнала. Дискретна Фуријеова трансформација је тиме и специјални облик Z-трансформације код које се z налази на јединичном кругу. Често се користи при обради дигиталних сигнала, а најпознатији алгоритам за то је брза фуријеова трансформација (FFT, Fast Fourier Transformation, енгл.).

Дискретна Фуријеова трансформација може да послужи такође за апроксимацију (у одређеним случајевима и реконструкцију) функције која одговара сигналу или као имплементација дигиталних филтера.

Путем инверзне Фуријеове трансформације се из Фуријеових коефицијената склапа излазни сигнал, а повезивањем ДФТ и инверзне ДФТ можемо да манипулишемо фреквенцијама (налази примену при еквилајзерима и филтерима).

Дефиниција уреди

Узмимо да је   комутативан, унитаран прстен, у којем је број   јединица. Даље, у   је   јединични корен.

За вектор   је дискретна фуријеова трансформација   на следећи начин дефинисана:

  за  

А за  , инверзна фуријеова трансформација је

  за  

ДФТ и ИДФТ у комплексном домену уреди

У комплексном домену користимо  .

Онда је ДФТ за  :   за  ,

а ИДФТ за  :   за  

ДФТ и ИДФТ у реалном домену уреди

Рачуница у реалном домену је:

 

Ојлеров идентитет гласи:  . Такође важи   и  .

Стога можемо још упростити израз:

 

Што ће рећи,   није реалан, али само N независних вредности (уместо 2N).

За ИДФТ можемо закључити следеће: Уколико за   важи   за све  , онда је ИДФТ реалан вектор  .

Померање и скалирање у времену и фреквенцији уреди

Ако је сигнал периодичан, онда није битно да ли трансформишемо у опсегу   или  . Индексна променљива j треба да обухвати N опсег, али није битно где он почиње односно где се завршава (ово важи само за случај да је сигнал периодичан, тј. да се вектор   периодично понавља). Присетимо се: за   важи  . Онда  .

У пракси често желимо да разлика у индексима буде истовремено и разлика у времену или раздаљини два мерења

 ,   је периода нашег мерења.

Често желимо и да коефицијентима доделимо фреквенцију тако да су центриране око  

 ,   је негде у близини  .

Узмимо неку функцију   којој додељујемо   тако да  .

ДФТ је онда  .

Из тога следи:

 

а ИДФТ је

 

Примери уреди

Пример филтера уреди

Ситуација: Звук који желимо да снимимо има следећи облик (када би га снимао аналоган микрофон):  

Пошто је наш микрофон дигиталан, ми можемо само да снимимо појединачне вредности. На нашем компјутеру добијамо:  

Наш циљ је да избацимо све фреквенције које су „тише“ (тј. које имају амплитуду) од 1 V. Прво правимо табелу:

<math>t_i =\,</math>0.5000    0.6000    0.7000    0.8000    0.9000    1.0000    1.1000    1.2000    1.3000    1.4000
<math>f(t_i) =\,</math>12.5000   10.0995   7.6644    6.8554    9.7905   13.5000   11.7546    7.4815    8.2905    12.0636

Имамо 10 вредности на 1 секунду, што ће рећи периода нашег мерења је  , а фреквенција  . Стога ми можемо да реконструишемо талас до 5 Hz. Уколико у нашем оригиналном сигналу има фреквенција виших од 5 Hz онда ће наша реконструкција имати грешку. Али, као и увек у животу, човек мора бити оптимистичан те ћемо ми претпоставити да нема виших фреквенција (то је уосталом и један од разлога зашто компакт-диск има фреквенцију од око 41 kHz; људско ухо може да региструје тек до 20 kHz!).

Следи израчунавање  . Нас занимају само вредности везане за позитивне индексе:

 
 
 
 

Сада имамо све вредности и можемо да почнемо са рачунањем:

 
 
 

Израчунавање осталих коефицијената иде аналогно, те ћемо их овде само навести као резултате:

 
 

Имамо  , сада желимо да избацимо све превише „тихе“ тонове. Требају нам  :

 

  10 -0.35i 1.5 - 0i 0.25 - 0.3i 0 + 0i

Знамо да важи:  . На тај начин можемо да израчунамо   и  :

 
 

Остале амплитуде:

 
 
 
 

Из   можемо да закључимо да фреквенција од 4 Hz нема у нашем сигналу. Често је врло згодно навести све амплитуде у графикону. Амплитуда   за неку фреквенцију   је  . У нашем случају наш фреквентни спектрум изгледа овако:

 

Све   и   за које важи   избацујемо и на крају добијамо реконструисану и обрађену функцију:

 

 

Сада можемо да поново да израчунамо   или да се послужимо ИДФТ и тако прерађен сигнал снимимо у меморију.

Пример у C-у уреди

#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;
}

Референце уреди

  • Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-307505-2. 
  • Oppenheim,, Alan V.; Schafer, Ronald W.; 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 изд.). San Diego, Calif.: California Technical Publishing. ISBN 978-0-9660176-3-2. 
  • Thomas H. Cormen; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2001). „Chapter 30: Polynomials and the FFT”. Introduction to Algorithms (Second изд.). MIT Press and McGraw-Hill. стр. 822-848. ISBN 978-0-262-03293-3.  esp. section 30.2: The DFT and FFT, pp. 830–838.
  • Duhamel, P.; Piron, B. & Etcheto, J. M. (1988). „On computing the inverse DFT”. IEEE Trans. Acoust., Speech and Sig. Processing. 36 (2): 285—286. doi:10.1109/29.1519. 
  • McClellan, J. H. & Parks, T. W. (1972). „Eigenvalues and eigenvectors of the discrete Fourier transformation”. IEEE Trans. Audio Electroacoust. 20 (1): 66—74. doi:10.1109/TAU.1972.1162342. 
  • Dickinson, Bradley W. & Steiglitz, Kenneth (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. 
  • Grünbaum, F. A. (1982). „The eigenvectors of the discrete Fourier transform”. J. Math. Anal. Appl. 88 (2): 355—363. doi:10.1016/0022-247X(82)90199-8. 
  • Atakishiyev, Natig M. & 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. 
  • Gurevich, Shamgar & Hadani, Ronny (2009). „On the diagonalization of the discrete Fourier transform”. Applied and Computational Harmonic Analysis. 27 (1): 87—99. arXiv:0808.3281 . doi:10.1016/j.acha.2008.11.003. preprint at.  Текст „arXiv

” игнорисан (помоћ)

  • Gurevich, Shamgar; Hadani, Ronny & Sochen, Nir (2008). „The finite harmonic oscillator and its applications to sequences, communication and radar”. IEEE Transactions on Information Theory. 54 (9): 4239—4253. arXiv:0808.1495 . doi:10.1109/TIT.2008.926440. preprint at.  Текст „arXiv

” игнорисан (помоћ)

  • Vargas-Rubio, Juan G. & Santhanam, Balu (2005). „On the multiangle centered discrete fractional Fourier transform”. IEEE Sig. Proc. Lett. 12 (4): 273—276. doi:10.1109/LSP.2005.843762. 
  • J. 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. 

Види још уреди