Öppna huvudmenyn

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.

Innehåll

HistoriaRedigera

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 fördes J.W. Cooley på IBM och John W. Tukey på Princeton University samman av Richard Garvin på IBM då de hade intresse för liknande algoritmer. De publicerade sedan en artikel där de återuppfann FFT och visade på hur deras algoritmer kunde användas i datorberäkningar.

AlgoritmerRedigera

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-algoritmenRedigera

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 tydligen kan beräknas en gång för alla:

 

Vi har fortfarande inte vunnit någonting på dessa omskrivningar, varje element av   måste fortfarande räknas ut med lika många multiplikationer och additioner som tidigare. Vinsten från dessa omskrivningar kommer när man ser att den övre halvan av elementen använder samma delsummor som den undre halvan. För att se detta måste man utnyttja att   och bryta ut detta:

 

Som vi kan se här så matchar summorna för   exakt med summorna för  bortsett från tecknet på den andra summan, så 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å. Uppenbarligen är vinsten allra störst när totala antalet element   respektive   är en tvåpotens av ett naturligt tal.

EffektivitetRedigera

Om   beräknas med (1) kommer antalet multiplikationer vara av storleksordningen  . Om vi i stället förutsätter att N är en tvåpotens kan antalet multiplikationer reduceras till  .

ExempelRedigera

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

Se ävenRedigera