Дискретна Фуријеова трансформација или ДФТ јесте Фуријеова трансформација дискретног и коначног (или периодичног) сигнала. Дискретна Фуријеова трансформација је тиме и специјални облик Z-трансформације код које се z налази на јединичном кругу. Често се користи при обради дигиталних сигнала, а најпознатији алгоритам за то је брза фуријеова трансформација (FFT, Fast Fourier Transformation, енгл.).
Дискретна Фуријеова трансформација може да послужи такође за апроксимацију (у одређеним случајевима и реконструкцију) функције која одговара сигналу или као имплементација дигиталних филтера.
Путем инверзне Фуријеове трансформације се из Фуријеових коефицијената склапа излазни сигнал, а повезивањем ДФТ и инверзне ДФТ можемо да манипулишемо фреквенцијама (налази примену при еквилајзерима и филтерима).
Дефиниција
Узмимо да је комутативан, унитаран прстен, у којем је број јединица. Даље, у је јединични корен.
За вектор је дискретна фуријеова трансформација на следећи начин дефинисана:
за
А за , инверзна фуријеова трансформација је
за
ДФТ и ИДФТ у комплексном домену
У комплексном домену користимо .
Онда је ДФТ за : за ,
а ИДФТ за : за
ДФТ и ИДФТ у реалном домену
Рачуница у реалном домену је:
Ојлеров идентитет гласи: . Такође важи и .
Стога можемо још упростити израз:
Што ће рећи, није реалан, али само N независних вредности (уместо 2N).
За ИДФТ можемо закључити следеће: Уколико за важи за све , онда је ИДФТ реалан вектор .
Померање и скалирање у времену и фреквенцији
Ако је сигнал периодичан, онда није битно да ли трансформишемо у опсегу или . Индексна променљива j треба да обухвати N опсег, али није битно где он почиње односно где се завршава (ово важи само за случај да је сигнал периодичан, тј. да се вектор периодично понавља). Присетимо се: за важи . Онда .
У пракси често желимо да разлика у индексима буде истовремено и разлика у времену или раздаљини два мерења
, је периода нашег мерења.
Често желимо и да коефицијентима доделимо фреквенцију тако да су центриране око
, је негде у близини .
Узмимо неку функцију којој додељујемо тако да .
ДФТ је онда .
Из тога следи:
а ИДФТ је
Примери
Пример филтера
Ситуација: Звук који желимо да снимимо има следећи облик (када би га снимао аналоган микрофон): Датотека:dft_signal_originalan.gif
Пошто је наш микрофон дигиталан, ми можемо само да снимимо појединачне вредности. На нашем компјутеру добијамо: Датотека:dft_signal_diskretan.gif
Наш циљ је да избацимо све фреквенције које су „тише“ (тј. које имају амплитуду) од 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}- нема у нашем сигналу. Често је врло згодно навести све амплитуде у графикону. Амплитуда за неку фреквенцију је . У нашем случају наш фреквентни спектрум изгледа овако:
Датотека:dft_signal_amplitude.gif
Све и за које важи избацујемо и на крају добијамо реконструисану и обрађену функцију:
Датотека:dft_signal_obradjen.gif
Сада можемо да поново да израчунамо или да се послужимо ИДФТ и тако прерађен сигнал снимимо у меморију.
Пример у -{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; f = my_function (t ); omega = 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 = cabs(coeff) / N; phi = 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 ); 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;
Референце
esp. section 30.2: The DFT and FFT, pp. 830–838.
Види још Дуалност по Понтрјагину
Категорија:Дискретна математика Категорија:Математичка анализа Категорија:Дигитална обрада сигнала Категорија:Фуријеова анализа Категорија:Нумеричка анализа
cs:Fourierova transformace#Diskrétní Fourierova transformace pt:Transformada de Fourier#Transformada discreta de Fourier fi:Fourier'n muunnos#Diskreetti Fourier'n muunnos