Algoritmus FFT Split-radix - Split-radix FFT algorithm

Split radix FFT je rychlá Fourierova transformace algoritmus (FFT) pro výpočet diskrétní Fourierovy transformace (DFT), a byla poprvé popsána v původně málo ocení papíru R. Yavne (1968), a následně se znovu objevil současně různými autory v 1984. (Název „split radix“ vymysleli dva z těchto objevitelů, P. Duhamel a H. Hollmann .) Zejména split radix je variantou algoritmu FFT Cooley – Tukey, který používá směs radixů 2 a 4 : rekurzivně vyjadřuje DFT délky N ve smyslu jedné menší DFT délky N / 2 a dvou menších DFT délky N / 4.

Split-základ FFT, spolu s jeho variacemi, dlouho měl vyznamenání za dosažení nejnižší publikovanou aritmetický počet operací (celkem přesný počet potřebných reálných sčítání a násobení) k výpočtu DFT power-of-dvou velikostech N . Aritmetický počet původního algoritmu split-radix byl vylepšen v roce 2004 (s počátečními zisky v nepublikované práci J. Van Buskirka prostřednictvím ruční optimalizace pro N = 64 [1] [2] ), ale ukázalo se, že jeden stále může dosáhnout nového nejnižšího počtu modifikací split radix (Johnson a Frigo, 2007). Ačkoli počet aritmetických operací není jediným faktorem (nebo dokonce nutně dominantním faktorem) při určování času potřebného k výpočtu DFT na počítači , otázka minimálního možného počtu je dlouhodobým teoretickým zájmem. (Momentálně nebyla prokázána žádná pevná dolní mez počtu operací.)

Algoritmus split-radix lze použít pouze v případě, že N je násobkem 4, ale protože rozděluje DFT na menší DFT, lze jej podle potřeby kombinovat s jakýmkoli jiným algoritmem FFT.

Rozklad split-radix

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

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x_ {n} \ omega _ {N} ^ {nk}}$

kde je celé číslo v rozmezí od do a označuje primitivní kořen jednoty : ${\ displaystyle k}$${\ displaystyle 0}$${\ displaystyle N-1}$${\ displaystyle \ omega _ {N}}$

${\ displaystyle \ omega _ {N} = e ^ {- {\ frac {2 \ pi i} {N}}},}$

a tím: . ${\ displaystyle \ omega _ {N} ^ {N} = 1}$

Algoritmus split-radix funguje tak, že tento součet vyjádří pomocí tří menších součtů. (Zde uvádíme verzi decimation in time FFT split-radix; duální decimace ve frekvenční verzi je v podstatě jen opakem těchto kroků.)

Nejprve součet přes sudé indexy . Zadruhé, součet přes liché indexy rozdělen na dvě části: a podle toho, zda je index 1 nebo 3 modulo 4. Zde označuje index, který běží od 0 do . Výsledné součty vypadají takto: ${\ displaystyle x_ {2n_ {2}}}$${\ displaystyle x_ {4n_ {4} +1}}$${\ displaystyle x_ {4n_ {4} +3}}$${\ displaystyle n_ {m}}$${\ displaystyle N / m-1}$

${\ displaystyle X_ {k} = \ součet _ {n_ {2} = 0} ^ {N / 2-1} x_ {2n_ {2}} \ omega _ {N / 2} ^ {n_ {2} k} + \ omega _ {N} ^ {k} \ sum _ {n_ {4} = 0} ^ {N / 4-1} x_ {4n_ {4} +1} \ omega _ {N / 4} ^ {n_ {4} k} + \ omega _ {N} ^ {3k} \ sum _ {n_ {4} = 0} ^ {N / 4-1} x_ {4n_ {4} +3} \ omega _ {N / 4} ^ {n_ {4} k}}$

kde jsme využili skutečnost, že . Tyto tři součty odpovídají částem z radix-2 (velikost N / 2) a radix-4 (velikost N / 4) Cooley-Tukey kroky, v tomto pořadí. (Základní myšlenkou je, že subtransformace sudého indexu radix-2 nemá před sebou žádný multiplikativní faktor, takže by měl být ponechán tak, jak je, zatímco lichá indexová subtransforma radix-2 má výhody kombinací druhého rekurzivního dělení .) ${\ displaystyle \ omega _ {N} ^ {mnk} = \ omega _ {N / m} ^ {nk}}$

Tyto menší součty jsou nyní přesně DFT délky N / 2 a N / 4, které lze provádět rekurzivně a poté je znovu zkombinovat .

Přesněji řečeno, označme výsledek DFT délky N / 2 (pro ) a dovolme a označíme výsledky DFT délky N / 4 (pro ). Pak je výstup jednoduše: ${\ displaystyle U_ {k}}$${\ displaystyle k = 0, \ ldots, N / 2-1}$${\ displaystyle Z_ {k}}$${\ displaystyle Z '_ {k}}$${\ displaystyle k = 0, \ ldots, N / 4-1}$${\ displaystyle X_ {k}}$

${\ displaystyle X_ {k} = U_ {k} + \ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k}.}$

Tím se však provádějí zbytečné výpočty, protože se ukázalo, že s nimi sdílíme mnoho výpočtů . Zejména pokud přidáme N / 4 do k , velikost - N / 4 DFT se nezmění (protože jsou periodické v k ), zatímco velikost - N / 2 DFT se nezmění, pokud přidáme N / 2 do k . Jediné, co se mění, jsou termíny a , známé jako dvojité faktory . Zde používáme identity: ${\ displaystyle k \ geq N / 4}$${\ displaystyle k <N / 4}$${\ displaystyle \ omega _ {N} ^ {k}}$${\ displaystyle \ omega _ {N} ^ {3k}}$

${\ displaystyle \ omega _ {N} ^ {k + N / 4} = - i \ omega _ {N} ^ {k}}$

${\ displaystyle \ omega _ {N} ^ {3 (k + N / 4)} = i \ omega _ {N} ^ {3k}}$

konečně dorazit na:

${\ displaystyle X_ {k} = U_ {k} + \ vlevo (\ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k} \ vpravo) ,}$

${\ displaystyle X_ {k + N / 2} = U_ {k} - \ left (\ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k }\že jo),}$

${\ displaystyle X_ {k + N / 4} = U_ {k + N / 4} -i \ left (\ omega _ {N} ^ {k} Z_ {k} - \ omega _ {N} ^ {3k} Z '_ {k} \ vpravo),}$

${\ displaystyle X_ {k + 3N / 4} = U_ {k + N / 4} + i \ left (\ omega _ {N} ^ {k} Z_ {k} - \ omega _ {N} ^ {3k} Z '_ {k} \ vpravo),}$

který dává všechny výstupy, pokud necháme rozsah od do ve výše uvedených čtyřech výrazech. ${\ displaystyle X_ {k}}$${\ displaystyle k}$${\ displaystyle 0}$${\ displaystyle N / 4-1}$

Všimněte si, že tyto výrazy jsou uspořádány tak, že musíme kombinovat různé výstupy DFT dvojicemi sčítání a odčítání, které jsou známé jako motýli . Aby bylo možné získat minimální počet operací pro tento algoritmus, je třeba vzít v úvahu speciální případy pro (kde twiddle faktory jsou jednota) a for (kde twiddle faktory jsou a lze je znásobit rychleji); viz např. Sorensen et al. (1986). Násobení pomocí a jsou obvykle počítány jako volné (všechny negace lze absorbovat převedením sčítání na odčítání nebo naopak). ${\ displaystyle k = 0}$${\ displaystyle k = N / 8}$${\ displaystyle (1 \ pm i) / {\ sqrt {2}}}$${\ displaystyle \ pm 1}$${\ displaystyle \ pm i}$

Tento rozklad se provádí rekurzivně, když N je síla dvou. Základní případy rekurze jsou N = 1, kde DFT je pouze kopie , a N = 2, kde DFT je sčítání a odčítání . ${\ displaystyle X_ {0} = x_ {0}}$${\ displaystyle X_ {0} = x_ {0} + x_ {1}}$${\ displaystyle X_ {1} = x_ {0} -x_ {1}}$

Výsledkem těchto úvah je počet: skutečné sčítání a násobení, pro N > 1 síla dvou. Tento počet předpokládá, že pro liché mocniny 2 je zbylý faktor 2 (po všech krocích split-radix, které dělí N na 4) zpracován přímo definicí DFT (4 skutečné přírůstky a násobení), nebo ekvivalentně a krok FIX radix-2 Cooley – Tukey. ${\ displaystyle 4N \ log _ {2} N-6N + 8}$

Reference

• R. Yavne, „Ekonomická metoda pro výpočet diskrétní Fourierovy transformace,“ v Proc. AFIPS Fall Joint Computer Conf. 33 , 115 - 125 (1968).
• P. Duhamel a H. Hollmann, „FFT algoritmus Split-radix,“ elektron. Lett. 20 (1), 14–16 (1984).
• M. Vetterli a HJ Nussbaumer, „Jednoduché algoritmy FFT a DCT se sníženým počtem operací,“ Signal Processing 6 (4), 267–278 (1984).
• JB Martens, „Rekurzivní cyklotomická faktorizace - nový algoritmus pro výpočet diskrétní Fourierovy transformace,“ IEEE Trans. Acoust., Speech, Signal Processing 32 (4), 750–761 (1984).
• P. Duhamel a M. Vetterli, „Fast Fourier transforms: a tutorial review and the state of the art,“ Signal Processing 19 , 259–299 (1990).
• SG Johnson a M. Frigo, „ Modifikovaný FFT s split-radixem s menším počtem aritmetických operací ,“ IEEE Trans. Proces signálu. 55 (1), 111–119 (2007).
• Douglas L. Jones, „ Split-radix FFT algorithms ,“ web Connexions (2. listopadu 2006).
• HV Sorensen, MT Heideman a CS Burrus, „On computing the split-radix FFT“, IEEE Trans. Acoust., Speech, Signal Processing 34 (1), 152–156 (1986).