Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Diskrétní Fourierova Transformace (DFT)

Diskrétní Fourierova transformace se používá, chceme-li zachytit hodnotu (přepokládejme, že -periodické) funkce na intervalu v nějakých bodech. To je dobré např. pro vzorkování elektrického nebo zvukového signálu a jiné operace. Pro nějakou funkci nám tak stačí znát vektor dimenze (a je počet vzorků na ).

Je to založeno na Fourierových řadách - dá se ukázat, že funkce , a pro tvoří ortogonální bázi prostoru spojitých funkcí na intervalu . Protože potřebujeme znát jenom konečný počet vzorků, stačí nám jen konečný podprostor s konečnou bází. Máme-li rozklad nějaké -periodické funkce do Fourierovy řady , dá se jednoduše ukázat, že pro hodnoty v bodech stačí sumy do pro sinusové řady a pro kosinové - vyšší koeficienty v takových bodech jsou nulové. Takže hodnot funkce na intervalu lze reprezentovat vektorem čísel v bázi .

Jednodušeji to lze ukázat v komplexních číslech - je známo, že

takže vektor hodnot funkce lze ekvivalentně reprezentovat v bázi , neboť všechny vektory původní báze lze zapsat jako lineární kombinace vektorů nové báze. Definujeme hodnotu

vidíme, že je -periodická funkce, takže nezáleží na hranicích sumace ( je ekvivalentní ). Potom se posloupnost komplexních čísel (např. hodnot naší funkce v bodech ) transformuje na posloupnost komplexních čísel (do báze ) použitím vzorečku:

Tento převod označujeme jako diskrétní Fourierovu transformaci.

Inverzní diskrétní Fourierova transformace je opačný problém - z Fourierových koeficientů chceme zpětně vypočítat hodnoty funkce v bodech . Platí:

Důkaz

Definujeme matici , potom (vektorově), takže . Definujeme a dokážeme, že . Máme

a potom pro

- platí
- definujeme

  a dostaneme geometrickou posloupnost , pro jejíž součet prvních členů platí vzorec

Algoritmus (Fast Fourier transform (FFT))

Fast Fourier transform je algoritmus pro počítání diskrétní Fourierovy transformace vektorů rozměru v čase . Mám-li matici Fourierových koeficientů , mohu ji rozdělit na liché a sudé sloupce, u sudých vyjádřit a pro spodní polovinu řádek (se sumami jdoucími po dvou) mohu snížit exponent u o (díky periodicitě) a vyjdou stejná čísla:

Poznámka: pro rychlé a jednoduché pochopení těch blektů co jsem tu napsal doporučuji Kučerův program Algovision
`http://kam.mff.cuni.cz/~ludek/AlgovisionPage.html`
DFT je tam názorně a přehledně ukázaná.

TODO: Související obecné věci o Fourierově transofrmaci, použití při spektrální analýze (Nyquist-Shannon sampling theorem), datové kompresi (Diskrétní kosinová transformace), násobení polynomů (+násobení velkých integerů).