Hoppa till innehållet

Snabb fouriertransform

Från Wikipedia

En snabb fouriertransform (en: Fast Fourier Transform FFT) är en effektiv algoritm för att beräkna en diskret, begränsad fouriertransform. Vanligtvis kräver en diskret fouriertransform av en signal med sampelpunkter multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen multiplikationer.

Det finns olika FFT-algoritmer med egenskaper som passar för olika definitionsmängder. En av de vanligaste algoritmerna är Cooley–Tukey-algoritmen där radix-2 DIT är det vanligaste fallet.

Cooley–Tukey-algoritmens historia börjar kring år 1805 då Carl Friedrich Gauss sökte samband för 2 Pallas och Junos asteroidbanor. Eftersom Gauss artikel kring detta endast publicerades postumt och dessutom på latin blev detta inte vida uppmärksammat. I mitten på 1960-talet sammanfördes J. W. Cooley(en)IBM och John W. TukeyPrinceton University av Richard Garvin på IBM då de hade intresse för liknande algoritmer. De publicerade sedan 1965 en artikel[1] där de återuppfann FFT och visade på hur deras algoritmer kunde användas i datorberäkningar.

En komplex vektor har diskret fouriertransform , båda med element, enligt definition:

(1)

Det har visat sig att beräkningen kan förenklas långt om antalet element är en tvåpotens av ett naturligt tal, dvs .

Radix-2-algoritmen

[redigera | redigera wikitext]

Redan om antalet element är jämnt delbart med två kan summan i (1) skrivas om som två hälften så långa summor med udda respektive jämna element vilket är samma som en enda hälften så lång summa med två termer i taget enligt följande:

Exponentialuttrycket i båda summorna är lika sånär som på faktorn som för ett stort antal element kan beräknas en gång för alla:

Så här långt har ingenting vunnits med dessa omskrivningar, då varje element av måste fortfarande räknas ut med lika många multiplikationer och additioner som tidigare. Vinsten från dessa omskrivningar kommer av att den övre halvan av elementen använder samma delsummor som den undre halvan, vilket kan visas genom att utnyttja att och bryta ut detta:

Det framgår att summorna för är identiska med summorna för bortsett från tecknet på den andra summan, vilket innebär att algoritmen räknar ut båda element på en gång.

Algoritmen bygger sedan på att förenklingen drivs vidare så länge antalet termer är jämnt delbart med två, och vinsten är allra störst när totala antalet element respektive är en tvåpotens av ett naturligt tal.

Effektivitet

[redigera | redigera wikitext]

Om beräknas med (1) kommer antalet multiplikationer vara av storleksordningen . Om N istället är en tvåpotens kan antalet multiplikationer reduceras till .

För att beräkna den diskreta fouriertransformen för en samplad signal med 4096 mätvärden behövs komplexa multiplikationer. Med FFT sjunker antalet till vilket typiskt går flera hundra gånger snabbare att utföra.

  1. ^ Cooley, James W.; Tukey, John W. (1965). ”An algorithm for the machine calculation of complex Fourier series” (på engelska). Mathematics of Computation 19 (90): sid. 297–301. doi:10.1090/S0025-5718-1965-0178586-1. ISSN 0025-5718. https://www.ams.org/mcom/1965-19-090/S0025-5718-1965-0178586-1/. Läst 28 december 2022.