Kiire Fourier' teisendus

N valimi diskreetne Fourier' teisendus koosneb N summast, millest igaühes on N liiget. Kui jagada see summa väiksemateks summadeks, saab sama vastuse kätte palju väiksema vaevaga. Vaata, kuidas see jaotumine liblikdiagrammil toimub, või uuri Gaussi viisi kaheteistkümne asteroid Pallasest rääkiva arvuga.

Näidisarvutus — Kiire Fourier' teisendus

Mitu korda vähem	5,3

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kiire Fourier' teisendus

Kiire Fourier' teisendus (FFT) on mistahes algoritm, mis arvutab diskreetse Fourier' teisenduse X[k] = Σ x[n] W^kn, W = e^−2πi/N (kuni ümardamiseni täpselt), kasutades N² asemel ligikaudu N log N tehet. Cooley ja Tukey kuju jaotab N = N₁N₂. See on N₂ põimitud teisendust pikkusega N₁, kus teisenduse n₂ iga väljund k₁ korrutatakse tema oma pöördeteguriga W^n₂k₁. Seejärel tehakse nende peal N₁ teisendust pikkusega N₂. Kui seda rakendada korduvalt N = 2^m puhul, on tulemuseks alusega 2 FFT: m etappi, millest igaühes on N/2 liblikat.

Mida iga sümbol tähendab

N: valimite ja arvutatud sageduste arv
W: ühejuur e^−2πi/N; selle astmed on pöördetegurid
m: log₂N, alusega 2 FFT etappide arv

Gauss pani FFT jaotuse kirja umbes 160 aastat enne Cooley't ja Tukey't 🖖

Vajuta nuppu Gauss, 3 perioodi 4 kaupa. Need kaksteist arvu pärinevad Gaussi käsikirjast: asteroid Pallase taevavööndi põhjapiiri kääne iga 30° otsetõusu järel, esitatuna kaareminutites ja kopeerituna von Zachi ajakirjast. Ta tahtis leida neid punkte läbivat trigonomeetrilist rida. Ühe kaheteistkümneliikmelise summa asemel võttis ta iga kolmanda väärtuse (0°, 90°, 180°, 270°; seejärel 30°, 120°, …; siis 60°, …), sobitas iga neljase rühma eraldi ja ühendas need kolm lühikest sobitust. Kriipsjoontega kõverad ongi needsamad sobitused, kuid need ei kattu. Neli punkti ei suuda tuvastada kiiremaid võnkumisi. Seega saab iga rühm erineva vastuse, mis viiski ta õige ühendamise otsingutele. Tulemuste all olev tabel näitab tema arvutust uuesti läbi tehtuna. Esimene periood annab väärtusteks 779,5; −415,0; −726,0 ja 43,5 – samad arvud, mis on tema käsikirjas –, ja ühendatud rida ongi otsene kaheteistkümneliikmeline rida. Ta tegi seda ka teistmoodi, nelja kolmest koosneva perioodina, ja sai tulemuseks sama rea. Indeksite matemaatika on sama, mille Cooley ja Tukey avaldasid aastal 1965, nagu näitasid Heideman, Johnson ja Burrus 1984. aastal. Sama oluline on ka see, mida käsikiri ei ütle. See ei loenda kordagi kokkuhoitud tööd. Kuigi Gauss ütleb, et jaotus on kiirem, jätab ta tõestuse praktika hooleks: praxis tentantem docebit ehk „kes proovib, see näeb”. Selle läbilahendatud näidetes on kaks tegurit (12 = 3 × 4 ja 36 = 6 × 6) ning 27. artikkel märgib vaid, et jaotus laieneb ka teistele juhtudele. Tema eluajal seda ei avaldatud. See ilmus ladina keeles tema kogutud teostes aastal 1866 ja on dateerimata. Väljaande „Werke” toimetaja nimetab seda arvatavasti 1805. aasta oktoobris alustatud mustandi ümbertöötluseks. Heideman, Johnson ja Burrus paigutavad selle mitmesuguste vihjete põhjal 1805. aasta oktoobrisse või novembrisse. Üks neist vihjetest on Juno ekstsentrilisus 0,254236, mida käsikiri kasutab ja mis trükiti ära 1805. aasta mais.

Kokkuhoid ei ole püsiv suurus, vaid kasvab koos N-iga 🖖

Vajuta nuppu 1024 punkti. Otsene summa korrutab iga valimi iga pöördeteguriga: tehes nii N² = 1 048 576 korrutamist. FFT läbib log₂N = 10 etappi, kus igas on N/2 = 512 liblikat ja üks korrutamine iga liblika kohta: seega 5120 korrutamist. See on 204,8 korda vähem. Nende suhe on 2N/log₂N, mis tähendab, et see muudkui kasvab. Vajuta nuppu Miljon punkti: 1 099 511 627 776 korrutamist otsese summa 10 485 760 korrutamise vastu, mille suhe on 104 857,6. Kahekordista N ja otsese summa töömaht suureneb neli korda. Tuhande punkti juures suureneb FFT töömaht vaid 2,2 korda, ja mida edasi, seda lähemale liigub see kahekordistumisele. 8 punkti juures on kokkuhoid vaid 5,3 korda. Seetõttu näeb diagramm välja nagu suur hulk juhtmeid minimaalse kasu nimel. Mõlemad loendid sisaldavad korrutamisi W⁰ = 1-ga, täpselt nagu ka Cooley ja Tukey enda N². Nemad lugesid korrutamis- ja liitmispaare ning said tulemuseks vähem kui 2N log₂N. Igal juhul kasvab suhe nagu N/log N. Ükski arvuti ei muuda kumbagi loendit ega ka nende suhet. Kiirem arvuti muudab vaid kestust, ja sedagi mitte ilmtingimata sama teguri võrra. Tabelite all asuv nupp mõõdab mõlema meetodi aega sinu brauseris. Mõõdetud suhe kasvab samuti koos N-iga, ehkki see ei jõua näidatud arvudeni, sest andmevahetus mäluga ja liitmised võtavad samuti aega, kuid neisse loenditesse pole neid kaasatud.

Suurte N-ide puhul on kiirem meetod ühtlasi täpsem 🖖

Täpsuse tabel käivitab mõlemad meetodid nii, et iga tehe on ümardatud ühekordse täpsuseni (umbes seitse tüvenumbrit), ja võrdleb neid topelttäpsusega arvutatud vastusega. 1024 punkti juures eksib otsene summa 5,75×10⁻⁷ võrra vastuse suurusest, FFT aga 1,23×10⁻⁷ võrra, mis on umbes 4,7 korda vähem. Liikudes 16 punkti juurest 1024 juurde – kogus suurenes 64 korda – kasvas otsese summa viga 7,3 korda ja FFT viga 1,4 korda. Iga otsese summa väljund on N ümardatud korrutise jooksev kogusumma, nii et selle ümardamisvead kuhjuvad 1024 liitmisega. See-eest iga FFT väljund läbib ainult log₂N = 10 liblikat. 16 punkti juures pole aga mingit vahet ja selle sisendi puhul on FFT isegi pisut halvem: 8,74×10⁻⁸ vs. 7,91×10⁻⁸. Mõlemad meetodid leiavad iga pöördeteguri samamoodi: arvutades topelttäpsusega ja ümardades üks kord. Seega võrdleb tabel kaht algoritmi, mitte kaht siinuse leidmise viisi.

Ülesanne täielikult lahendatud

Gaussi teine näide: Juno, 36 väärtust 4 sammu
Gaussi käsikirja 41. artikkel interpoleerib Juno keskpunkti võrrandi 36 väärtusest, üks iga 10° järel, mis on jaotatud 6 × 6. Kui suur on otsese summa töömaht Cooley ja Tukey loendi järgi, kui palju säästab Gaussi jaotus ning kas peenem jaotus annaks parema tulemuse? Vajuta esmalt nuppu Gauss, 3 perioodi 4 kaupa: leht arvutab kaheteistkümne väärtuse puhul samamoodi.

Ava see ülesanne tööriistas
1. Otsene summa teeb ühe tehte iga valimi ja sageduse kohta:
  
  $N^{2} = 3 6^{2} = 1, 296$
2. Gaussi jaotus ehk kuus kuuest koosnevat perioodi: Cooley ja Tukey kaheastmelise loendi puhul on töömaht N korda tegurite summa.
  
  $T = N (N_{1} + N_{2}) = 36 \times (6 + 6) = 432$
3. Täielikult osadeks jagatuna on 36 = 2 × 2 × 3 × 3:
  
  $T = 36 \times (2 + 2 + 3 + 3) = 360$
4. Cooley ja Tukey reegel: teguri r = st puhul (kus s, t > 1) kehtib alati s + t < r, välja arvatud siis, kui s = t = 2:
  
  $s + t < s t (s, t > 1, (s, t) \neq = (2, 2)); 6 = 2 \times 3 : 2 + 3 = 5 < 6$
Vastus

1296 tehet otseselt, 432 Gaussi 6 × 6 jaotusega ning 360 lõpuni jaotatult. Gaussi jaotus teeb juba kolm korda vähem tööd, peeneim jaotus aga säästab allesjäänust veel kuuendiku. Lehel olevate kaheteistkümne väärtuse puhul on olukord sarnane: 144 otseselt ja 84 jaotusega ehk lõpuni jaotatult 12 × (2 + 2 + 3) = 84. Põhjus peitub selles, et teguri 4 jaotamine 2 × 2 kujul on sama kulukas.

$1, 296 \to 432 \to 360; 1 2^{2} = 144 \to 12 \times (4 + 3) = 12 \times (2 + 2 + 3) = 84$

Õpitee

Fourier' teisendus praktikas

Allikad (3)

Gauss's manuscript on trigonometric interpolation, printed after his death. Article 28 is the page's Gauss mode: twelve declinations of the northern limit of Pallas's zodiac at every 30° of right ascension, split into three periods of four and into four periods of three. Article 27 says the split extends to three or more factors and that practice will teach whoever tries it ("praxis tentantem docebit"); article 41 works Juno's equation of the centre from 36 values with the eccentricity 0.254236. The editor's note calls the text a reworking of a draft apparently begun in October 1805: C. F. Gauss, Theoria interpolationis methodo nova tractata (Nachlass). Werke, Band III, Königliche Gesellschaft der Wissenschaften, Göttingen, 1866; second printing 1876, where the treatise begins on p. 265 and arts. 25–28 are on pp. 303–310.
The paper that showed Gauss's split is the Cooley–Tukey FFT: the change of index n = N₂n₁ + n₂, k = k₁ + N₁k₂ written as Gauss's procedure, his examples (N = 12 as 4 × 3 and 3 × 4, N = 36 as 6 × 6), the dating to October–November 1805 from the Juno eccentricity and other clues, and what the manuscript does not contain: "Gauss did not, however, go on to quantify the computational requirements of his method": M. T. Heideman, D. H. Johnson and C. S. Burrus, Gauss and the history of the fast Fourier transform. IEEE ASSP Magazine 1(4), 14–21 (October 1984). doi:10.1109/MASSP.1984.1162257
The paper that made the FFT standard: the split N = r₁r₂ with T = N(r₁ + r₂) operations, its repetition to T = N(r₁ + … + r_m), the radix-2 form with bit-reversed order, and the count of N² operations for the direct sum against fewer than 2N log₂N, where an operation is a complex multiplication followed by a complex addition: J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19(90), 297–301 (1965). doi:10.1090/S0025-5718-1965-0178586-1

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.