Algorytm FFT z dzieloną podstawą

Split -radix FFT jest algorytmem szybkiej transformaty Fouriera ( FFT) do obliczania dyskretnej transformaty Fouriera (DFT) . różni autorzy w 1984 r. (Nazwa „split radix” została wymyślona przez dwóch z tych wynalazców, P. Duhamela i H. Hollmanna). W szczególności split radix jest wariantem algorytmu FFT Cooleya-Tukeya, który wykorzystuje mieszankę radices 2 i 4: rekurencyjnie wyraża DFT długości N pod względem jednej mniejszej DFT o długości N /2 i dwóch mniejszych DFT o długości N /4.

FFT z dzieloną podstawą, wraz z jej odmianami, od dawna wyróżnia się osiągnięciem najniższej opublikowanej liczby operacji arytmetycznych (całkowita dokładna liczba wymaganych rzeczywistych dodań i mnożeń) do obliczenia DFT potęgi dwóch rozmiarów N . Liczba arytmetyczna oryginalnego algorytmu podzielonej podstawy została ulepszona w 2004 r. (Początkowe korzyści osiągnięte w niepublikowanej pracy J. Van Buskirka poprzez optymalizację ręki dla N = 64 [2] [3] ), ale okazuje się, że wciąż można osiągnąć nową najniższą liczbę poprzez modyfikację podzielonej podstawy (Johnson i Frigo, 2007). Chociaż liczba operacji arytmetycznych nie jest jedynym czynnikiem (a nawet koniecznie dominującym) przy określaniu czasu potrzebnego do obliczenia DFT na komputerze , kwestia minimalnej możliwej liczby ma od dawna zainteresowanie teoretyczne. (Obecnie nie udowodniono żadnej ścisłej dolnej granicy liczby operacji).

Algorytm podzielonej podstawy można zastosować tylko wtedy, gdy N jest wielokrotnością 4, ale ponieważ dzieli DFT na mniejsze DFT, można go łączyć z dowolnym innym algorytmem FFT zgodnie z potrzebami.

Dekompozycja podzielonej podstawy

Przypomnijmy, że DFT jest zdefiniowany wzorem:

${\ Displaystyle X_ {k} = \ suma _ {n = 0} ^ {N-1} x_ {n} \ omega _ {N} ^ {nk }}$

gdzie ${\ Displaystyle N-1}$ liczbą całkowitą z zakresu od {\ $Displaystyle$$0}$ do i $k {\ displaystyle k}$ pierwiastek jedności :

${\ Displaystyle \ omega _ {N} = e ^ {- {\ Frac {2 \ pi ja} {N}}}}$

i tak: ${\ Displaystyle \ omega _ {N} ^ {N} = 1}$ .

Algorytm podzielonej podstawy działania polega na wyrażeniu tej sumy w postaci trzech mniejszych sum. (Tutaj podajemy wersję „z dziesiątkowaniem w czasie” FFT z podzieloną podstawą; wersja z podwójnym dziesiątkowaniem w częstotliwości jest zasadniczo odwrotnością tych kroków.)

Najpierw sumowanie po parzystych indeksach ${\ displaystyle x_ {2n_ {2}}}$ . Po drugie, sumowanie nieparzystych indeksów podzielonych na dwie części: ${\ Displaystyle x_ {4n_ {4} +1}}$ i ${\ Displaystyle x_ {4n_ {4} +3 }}$ , w zależności od tego, czy indeks wynosi 1, czy 3 modulo 4. Tutaj ${\ displaystyle n_ {m}}$ oznacza indeks, który biegnie od 0 do ${\ Displaystyle N/m-1}$ . Wynikowe podsumowania wyglądają następująco:

${\ Displaystyle X_ {k} = \ suma _ {n_ {2} = 0} ^ {N / 2-1} x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\suma _{n_{4}=0}^{N/4 -1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\suma _{n_{4}=0} ^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}}$

gdzie wykorzystaliśmy fakt, że ${\ Displaystyle \ omega _ {N} ^ {mnk} = \ omega _ {N/m} ^ {nk}}$ . Te trzy sumy odpowiadają częściom radix -2 (rozmiar N /2) i radix-4 (rozmiar N /4) Odpowiednio kroki Cooleya-Tukeya. (Główną ideą jest to, że podtransformacja podstawy-2 o indeksie parzystym nie ma przed sobą mnożnika, więc należy ją pozostawić bez zmian, podczas gdy transformacja podrzędna podstawy-2 o indeksie nieparzystym przynosi korzyści dzięki połączeniu drugiego podziału rekurencyjnego .)

Te mniejsze sumowania są teraz dokładnie DFT o długości N /2 i N /4, które można wykonać rekurencyjnie, a następnie ponownie połączyć.

Dokładniej, niech $}$ wynik DFT o długości / 2 (dla $-1}$${\ Displaystyle k = 0, \ ldots, N/2) U k {\ Displaystyle U_ {k}$$N$ niech $N$ niech wyniki o długości ${\ Displaystyle k = 0, \ kropki, N / 4-1}$ 4 (dla ). Wtedy wyjście to po prostu: ${\ displaystyle X_ {k}}$

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

Powoduje to jednak niepotrzebne obliczenia, ponieważ $/4$ się, że wiele obliczeń dzieli się z $N$ . W szczególności, jeśli dodamy N /4 do k , DFT rozmiaru N /4 nie ulegną zmianie (ponieważ są okresowe w N /4), podczas gdy DFT rozmiaru N /2 nie ulegnie zmianie, jeśli dodamy N /2 do k . Tak więc jedyne rzeczy, które się zmieniają, to terminy znane jako ${\ Displaystyle \ omega _ {N} ^ {k}}$ i ${\ Displaystyle \ omega _ {N} ^ {3k}}$ czynniki . Tutaj używamy tożsamości:

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

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

by w końcu dojść do:

${\ Displaystyle X_ {k} = U_ {k} + \ lewo (\ omega _ {N} ^ {k} Z_ { k}+\omega _{N}^{3k}Z'_{k}\right),}$

$2} = U_ {k} - \ lewo (\ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z'_ {k} \ prawej),}$

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

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

co daje wszystkie wyjścia $zakres$ jeśli pozwolimy na od ${\ Displaystyle$$0}$ N $\ Displaystyle N/4-1}$ powyższym cztery wyrażenia.

Zauważ, że te wyrażenia są ułożone w taki sposób, że musimy połączyć różne wyniki DFT za pomocą par dodawania i odejmowania, które są znane jako motyle . Aby uzyskać minimalną liczbę operacji dla tego algorytmu, należy wziąć pod uwagę szczególne przypadki dla $k$ czynniki twiddle są jednością) i $\ displaystyle k = N/8}$ (gdzie czynniki twiddle to ${\ displaystyle (1 \ pm i) / {\ sqrt {2}}}$ i można je pomnożyć szybciej); patrz np. Sorensen i in. (1986). Mnożenia przez $wszystkie$$są zwykle liczone jako wolne ($ odejmowanie lub odwrotnie).

Ten rozkład jest wykonywany rekurencyjnie, gdy N jest potęgą dwójki. Podstawowe przypadki rekurencji to N = 1, gdzie DFT jest tylko kopią ${\ displaystyle X_ {0}=$ N = 2, gdzie DFT jest dodatkiem ${\ Displaystyle X_ {0} = x_ {0} + x_ {1}}$ i odejmowanie ${\ Displaystyle X_ {1} = x_ {0} -x_ {1}}$ .

Te rozważania skutkują liczeniem: ${\ Displaystyle 4N \ log _ {2} N-6N + 8}$ rzeczywiste dodawanie i mnożenie, dla N > 1 potęga dwóch. Ta liczba zakłada, że ​​​​dla nieparzystych potęg 2 pozostały współczynnik 2 (po wszystkich krokach podzielonej podstawy, które dzielą N przez 4) jest obsługiwany bezpośrednio przez definicję DFT (4 rzeczywiste dodawania i mnożenia) lub równoważnie przez a krok radix-2 Cooley-Tukey FFT.

• R. Yavne, „ Ekonomiczna metoda obliczania dyskretnej transformaty Fouriera ”, w Proc. AFIPS Fall Joint Konf. komputera. 33 , 115-125 (1968).
• P. Duhamel i H. Hollmann, „Algorytm Split-radix FFT”, Electron. Łotysz. 20 (1), 14–16 (1984).
• M. Vetterli i HJ Nussbaumer, „Proste algorytmy FFT i DCT ze zmniejszoną liczbą operacji”, Signal Processing 6 (4), 267–278 (1984).
• JB Martens, „Rekurencyjna faktoryzacja cyklotomiczna - nowy algorytm do obliczania dyskretnej transformaty Fouriera”, IEEE Trans. Akus., Mowa, przetwarzanie sygnału 32 (4), 750–761 (1984).
• P. Duhamel i M. Vetterli, „Szybkie transformaty Fouriera: przegląd samouczków i stan techniki”, Signal Processing 19 , 259–299 (1990).
• SG Johnson i M. Frigo, „ Zmodyfikowana FFT z podzieloną podstawą i mniejszą liczbą operacji arytmetycznych ”, IEEE Trans. Proces sygnału. 55 (1), 111–119 (2007).
• Douglas L. Jones, „ Algorytmy Split-radix FFT” , witryna internetowa Connexions (2 listopada 2006).
• HV Sorensen, MT Heideman i CS Burrus, „O obliczaniu FFT z podzieloną podstawą”, IEEE Trans. Akus., Mowa, Przetwarzanie sygnału 34 (1), 152–156 (1986).