Snabb fouriertransform

(Omdirigerad från FFT)

En snabb fouriertransform, på engelska 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.

Historia redigera

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.

Algoritmer redigera

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

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

 

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

Exempel redigera

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.

Se även redigera

Referenser redigera

  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.