Bruunův FFT algoritmus - Bruun's FFT algorithm

Bruunův algoritmus je rychlý algoritmus Fourierovy transformace (FFT) založený na neobvyklém rekurzivním polynomiálním -faktorizačním přístupu, navržený pro síly dvou G. Bruunem v roce 1978 a zobecněný na libovolné i kompozitní velikosti H. Murakami v roce 1996. Protože jeho operace zahrnují Pouze skutečné koeficienty do poslední výpočetní fáze byly původně navrženy jako způsob, jak efektivně vypočítat diskrétní Fourierovu transformaci (DFT) skutečných dat. Bruunův algoritmus však neviděl široké použití, protože přístupy založené na běžném algoritmu Cooley – Tukey FFT byly úspěšně přizpůsobeny reálným datům s přinejmenším stejně vysokou účinností. Kromě toho existují důkazy, že Bruunův algoritmus může být při konečné numerické přesnosti skutečně méně přesný než Cooley – Tukey (Storn, 1993).

Bruunův algoritmus nicméně ilustruje alternativní algoritmický rámec, který dokáže vyjádřit sebe i algoritmus Cooley – Tukey, a poskytuje tak zajímavý pohled na FFT, který umožňuje kombinace těchto dvou algoritmů a dalších zobecnění.

Polynomiální přístup k DFT

Připomeňme, že DFT je definován vzorcem:

Pro usnadnění označme N kořenů jednoty ω N n ( n  = 0, ...,  N  - 1):

a definujte polynom x ( z ), jehož koeficienty jsou x n :

DFT lze potom chápat jako redukci tohoto polynomu; to znamená, že X k je dáno vztahem:

kde mod označuje operaci zbytku polynomu . Klíč k rychlým algoritmům, jako je Bruunův nebo Cooley – Tukey, pochází ze skutečnosti, že lze tuto sadu N zbývajících operací provádět v rekurzivních fázích.

Rekurzivní faktorizace a FFT

Abychom mohli vypočítat DFT, musíme vyhodnotit zbytek polynomů modulo N stupně 1, jak je popsáno výše. Vyhodnocení těchto zbytků jeden po druhém je ekvivalentní přímému vyhodnocení obvyklého vzorce DFT a vyžaduje operace O ( N 2 ). Lze však tyto zbytky kombinovat rekurzivně ke snížení nákladů pomocí následujícího triku: pokud chceme vyhodnotit modulo dva polynomy a můžeme nejprve vzít zbytek modulo jejich produkt , který snižuje stupeň polynomu a provádí následné operace modulo výpočetně méně nákladné.

Součin všech monomiálů pro k = 0 .. N -1 je prostě (jehož kořeny jsou jasně N kořeny jednoty). Jeden si pak přeje najít rekurzivní faktorizaci do polynomů několika členů a menšího a menšího stupně. Pro výpočet DFT je třeba postupně modulovat každou úroveň této faktorizace, rekurzivně, dokud nedorazíme k monomiálům a konečnému výsledku. Pokud každá úroveň faktorizace rozdělí každý polynom na počet O (1) (konstantní ohraničení) menších polynomů, každý s počtem N (1) nenulových koeficientů, pak operace modulo pro tuto úroveň zabere O ( N ) čas ; protože bude existovat logaritmický počet úrovní, je celková složitost O ( N log N ).

Přesněji řečeno, předpokládejme například to a to atd. Odpovídající algoritmus FFT by sestával z prvního výpočtu x k ( z ) = x ( z ) mod F k ( z ), poté výpočtu x k , j ( z ) = x k ( z ) mod F k , j ( z ), a tak dále, rekurzivně vytvářející stále více a více zbývajících polynomů menšího a menšího stupně, dokud jeden nedosáhne konečných výsledků stupně 0.

Kromě toho, pokud jsou polynomiální faktory v každé fázi relativně primitivní (což pro polynomy znamená, že nemají společné kořeny), lze sestrojit dvojitý algoritmus obrácením procesu s čínskou větou o zbytku .

Cooley – Tukey jako polynomiální faktorizace

Standardní decimace-in-frekvence (DIF) radix- r Cooley-Tukey algoritmus odpovídá blízko k rekurzivní faktorizace. Například faktory radix-2 DIF Cooley – Tukey do a . Tyto modulo operace snižují stupeň o 2, což odpovídá dělení velikosti problému na 2. Místo přímé rekurzivní faktorizace však Cooley – Tukey místo toho nejprve spočítá x 2 ( z ω N ) a posune všechny kořeny (o twiddle faktor ), aby mohl použít rekurzivní faktorizaci obou podproblémů. To znamená, že Cooley – Tukey zajišťuje, že všechny dílčí problémy jsou také DFT, zatímco u arbitrární rekurzivní faktorizace (jako je Bruunova níže) to obecně neplatí.

Bruunova faktorizace

Základní Bruunův algoritmus pro mocniny dvou N = 2 n rekurzivně faktorizuje z 2 n - 1 pomocí pravidel:

kde a je skutečná konstanta s | a | ≤ 2. V případě , pak i .

Ve stadiu s , s = 0,1,2, n -1 se přechodný stav skládá z 2 s polynomů stupně 2 n - s - 1 nebo méně, kde

Konstrukcí faktorizace z 2 n - 1 kódují polynomy p s , m ( z ) vždy 2 hodnoty n - s

Fourierovy transformace, pro m = 0, kryté indexy K = 0 , 2 K , 2 ∙ 2 s , 3 ∙ 2 s , ..., (2 n - y 1) ∙ 2 s , pro m > 0 na kryté indexy jsou k = m , 2 s +1 - m , 2 s +1 + m , 2 ∙ 2 s +1 - m , 2 ∙ 2 s +1 + m ,…, 2 n - m .

Během přechodu do další fáze se polynom redukuje na polynomy a dělí se na polynomy. Pokud někdo chce udržet polynomy ve vzrůstajícím pořadí indexů, vyžaduje tento vzor implementaci se dvěma poli. Implementace na místě produkuje předvídatelnou, ale vysoce neuspořádanou posloupnost indexů, například pro N = 16 je konečné pořadí 8 lineárních zbytků ( 0 , 4 , 2 , 6 , 1 , 7 , 3 , 5 ).

Na konci rekurze pro s = n - 1 zůstávají 2 n - 1 lineární polynomy kódující dva Fourierovy koeficienty X 0 a X 2 n -1 pro první a pro jakýkoli další k- tý polynom koeficienty X k a X 2 n - k .

V každé rekurzivní fázi jsou všechny polynomy společného stupně 4M - 1 redukovány na dvě části poloviny stupně 2M - 1 . Dělitelem tohoto výpočtu zbytku polynomu je kvadratický polynom z m , takže všechna redukce mohou být redukována na polynomiální dělení kubických kvadratickými polynomy. Existuje N / 2 = 2 n - 1 těchto malých divizí v každé fázi, což vede k algoritmu O ( N log N ) pro FFT.

Navíc, protože všechny tyto polynomy mají čistě reálné koeficienty (až do poslední fáze), automaticky využívají speciální případ, kdy jsou vstupy x n čistě reálné, aby ušetřily zhruba dvojnásobný faktor ve výpočtu a ukládání. Lze také využít přímou výhodu případu reálných symetrických dat pro výpočet diskrétní kosinové transformace (Chen a Sorensen, 1992).

Zobecnění na libovolné radice

Bruunova faktorizace, a tedy Bruunův FFT algoritmus, byla zobecněna pro zpracování libovolných i složených délek, tj. Dělení polynomiálního stupně libovolným radixem (faktorem), jak je uvedeno dále. Nejprve definujeme množinu polynomů φ N , α ( z ) pro kladná celá čísla N a pro α v [0,1) pomocí:

Všimněte si, že všechny polynomy, které se objevují v Bruunově faktorizaci výše, lze zapsat v této formě. Nuly těchto polynomů je pro v případě, a pro v případu. Tyto polynomy lze tedy rekurzivně faktorizovat pro faktor (radix) r pomocí:

Reference

  • Georg Bruun, „ z -Transform DFT filtry a FFT,“ IEEE Trans. o akustice, řeči a zpracování signálu (ASSP) 26 (1), 56-63 (1978).
  • HJ Nussbaumer, Fast Fourier Transform and Convolution Algorithms (Springer-Verlag: Berlin, 1990).
  • Yuhang Wu, „Nové struktury FFT založené na Bruunově algoritmu“, IEEE Trans. ASSP 38 (1), 188-191 (1990)
  • Jianping Chen a Henrik Sorensen, „Efektivní algoritmus FFT pro reálná symetrická data,“ Proc. ICASSP 5 , 17-20 (1992).
  • Rainer Storn, „Některé výsledky v analýze chyb s pevným bodem algoritmu Bruun-FTT [ sic ],“ IEEE Trans. Proces signálu. 41 (7), 2371-2375 (1993).
  • Hideo Murakami, „Real-valued decimation-in-time and decimation-in-frequency algorithms,“ IEEE Trans. Circuits Syst. II: Analogové a digitální signály. Proc. 41 (12), 808-816 (1994).
  • Hideo Murakami, „Skutečně oceňované rychlé diskrétní Fourierovy transformace a cyklické konvoluční algoritmy vysoce složené sudé délky,“ Proc. ICASSP 3 , 1311-1314 (1996).
  • Shashank Mittal, MD Zafar Ali Khan, MB Srinivas, „Srovnávací studie různých architektur FFT pro softwarově definované rádio“, poznámky k přednášce v informatice 4599 ( Embedded Computer Systems: Architectures, Modeling, and Simulation ), 375-384 (2007 ). Proc. 7. mezinárodní letiště Workshop, SAMOS 2007 (Samos, Řecko, 16. – 19. Července 2007).