Дискретна Фуријеова трансформација
Из пројекта Википедија
Дискретна Фуријеова трансформација или ДФТ јесте Фуријеова трансформација дискретног и коначног (или периодичног) сигнала. Дискретна Фуријеова трансформација је тиме и специјални облик 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;
}



















