ДиÑкретна Фуријеова транÑформација
Из пројекта Википедија
ДиÑкретна Фуријеова транÑформација или ДФТ јеÑте Фуријеова транÑформација диÑкретног и коначног (или периодичног) Ñигнала. ДиÑкретна Фуријеова транÑформација је тиме и Ñпецијални облик Z-транÑформације код које Ñе z налази на јединичном кругу. ЧеÑто Ñе кориÑти при обради дигиталних Ñигнала, а најпознатији алгоритам за то је брза фуријеова транÑформација (FFT, Fast Fourier Transformation, енгл.).
ДиÑкретна Фуријеова транÑформација може да поÑлужи такође за апрокÑимацију (у одређеним Ñлучајевима и реконÑтрукцију) функције која одговара Ñигналу или као имплементација дигиталних филтера.
Путем инверзне Фуријеове транÑформације Ñе из Фуријеових коефицијената Ñклапа излазни Ñигнал, а повезивањем ДФТ и инверзне ДФТ можемо да манипулишемо фреквенцијама (налази примену при еквилајзерима и филтерима).
Садржај[Ñакриј] |
[уреди] Дефиниција
Узмимо да је R комутативан, унитаран прÑтен, у којем је број N јединица. Даље, у R је w јединични корен.
За вектор је диÑкретна фуријеова транÑформација
на Ñледећи начин дефиниÑана:
за
Рза , инверзна фуријеова транÑформација је
за
[уреди] ДФТ и ИДФТ у комплекÑном домену
У комплекÑном домену кориÑтимо .
Онда је ДФТ за :
за
,
а ИДФТ за :
за
[уреди] ДФТ и ИДФТ у реалном домену
Рачуница у реалном домену је:
}-
Ојлеров идентитет глаÑи: e2Ï€i = 1. Такође важи и
.
Стога можемо још упроÑтити израз:
Што ђе рећи, није реалан, али Ñамо N незавиÑних вредноÑти (умеÑто 2N).
За ИДФТ можемо закључити Ñледеће: Уколико за важи
за Ñве
, онда је ИДФТ реалан вектор
.
[уреди] Померање и Ñкалирање у времену и фреквенцији
Ðко је Ñигнал периодичан, онда није битно да ли транÑформишемо у опÑегу или
. ИндекÑна променљива j треба да обухвати N опÑег, али није битно где он почиње одноÑно где Ñе завршава (ово важи Ñамо за Ñлучај да је Ñигнал периодичан, тј. да Ñе вектор
периодично понавља). ПриÑетимо Ñе: за w важи wN = 1. Онда
.
У пракÑи чеÑто желимо да разлика у индекÑима буде иÑтовремено и разлика у времену или раздаљини два мерења
, T је периода нашег мерења.
ЧеÑто желимо и да коефицијентима доделимо фреквенцију тако да Ñу центриране око 0
, K је негде у близини
.
Узмимо неку функцију f којој додељујемо тако да xn = f(tn).
ДФТ је онда .
Из тога Ñледи:
а ИДФТ је
[уреди] Примери
[уреди] Пример филтера
Ситуација: Звук који желимо да Ñнимимо има Ñледећи облик (када би га Ñнимао аналоган микрофон):
Пошто је наш микрофон дигиталан, ми можемо Ñамо да Ñнимимо појединачне вредноÑти. Ðа нашем компјутеру добијамо:
Ðаш циљ је да избацимо Ñве фреквенције које Ñу "тише" (тј. које имају амплитуду) од 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 нема у нашем Ñигналу. ЧеÑто је врло згодно навеÑти Ñве амплитуде у графикону. Ðмплитуда
за неку фреквенцију k је
. У нашем Ñлучају наш фреквентни Ñпектрум изгледа овако:
Све и
за које важи
избацујемо и на крају добијамо реконÑтруиÑану и обрађену функцију:
Сада можемо да поново да израчунамо или да Ñе поÑлужимо ИДФТ и тако прерађен Ñигнал Ñнимимо у меморију.
[уреди] Пример у 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; }