Koše, rozlišení a proč je FFT rychlá
Diskrétní transformace nedá spojité spektrum, ale N čísel. Každé odpovídá jedné frekvenci a mezi nimi se nic nedozvíme. Ty frekvence se jmenují koše a jejich rozestup je jediný vzorec, který se z téhle kapitoly musí znát:
Rozlišení nezávisí na vzorkovací frekvenci, ale na DÉLCE ZÁZNAMU. Vzorkovat rychleji znamená vidět výš (vyšší Nyquistovu mez), ne jemněji. Kdo chce rozlišit dva tóny vzdálené 1 Hz, potřebuje záznam alespoň 1 sekundu dlouhý — a je jedno, jestli vzorkuje na 1 kHz nebo na 1 MHz. Tohle plete skoro každý, kdo spektrum používá poprvé.
| chci | musím |
|---|---|
| vidět vyšší frekvence | vzorkovat rychleji (větší fs) |
| rozlišit bližší frekvence | měřit déle (větší T) |
| obojí | víc vzorků — N = fs·T |
Cena přímého výpočtu
Přímá definice potřebuje pro každý z N košů projít všech N vzorků, tedy N² operací. Pro N = 1024 je to milion, pro N = 10⁶ je to bilion — a to už je mimo možnosti čehokoli.
Cooleyho-Tukeyho trik
Rozděl signál na sudé a liché vzorky. Ukáže se, že transformace celku se dá složit ze transformací obou polovin — a to jde opakovat, dokud nezbudou jednotlivé vzorky.
| N | přímo (N²) | FFT (N log N) | poměr |
|---|---|---|---|
| 1 024 | 1 milion | 10 tisíc | 100× |
| 65 536 | 4,3 miliardy | 1 milion | 4 000× |
| 1 048 576 | 1,1 bilionu | 21 milionů | 52 000× |
Tenhle rozdíl není zrychlení, je to rozdíl mezi „jde to“ a „nejde to“. Bez FFT by neexistoval digitální zvuk, MRI, ani nic, co dělá spektrum v reálném čase.
FFT má podmínku a solver ji vynucuje. Radix-2 verze
potřebuje délku, která je mocnina dvou. Doplnit zbytek nulami je legitimní postup, ale
mění spektrum — interpoluje ho, takže vypadá jemnější, aniž by přibyla jakákoli
informace. Dělat to potichu za zády volajícího je způsob, jak čtenáři podstrčit rozlišení, které
si nevyžádal, a proto fft() v téhle labce nesprávnou délku odmítne místo
aby ji doplnila.
Jak se ověřilo, že je FFT správně. V repu jsou dvě implementace: pomalá, přepsaná doslova z definice, a rychlá. Testy je porovnávají na náhodných datech pro N od 16 do 512 — shoda na 1,6·10⁻¹³. Kontrola má cenu jen proto, že ty dvě cesty nesdílejí ani řádek: kdyby byly obě „chytré“ stejným způsobem, shodly by se i na stejné chybě.