Algorytm FFT o podstawie wektorowej

Algorytm FFT z wektorową podstawą jest wielowymiarowym algorytmem szybkiej transformaty Fouriera (FFT), który jest uogólnieniem zwykłego algorytmu FFT Cooleya-Tukeya , który dzieli wymiary transformacji przez dowolne podstawy. Rozbija wielowymiarową (MD) dyskretną transformatę Fouriera (DFT) na kolejne mniejsze MD DFT, aż ostatecznie trzeba będzie ocenić tylko trywialne MD DFT.

Najpopularniejszym wielowymiarowym algorytmem FFT jest algorytm kolumnowo-wierszowy, co oznacza transformację tablicy najpierw w jednym indeksie, a następnie w drugim, zobacz więcej w FFT . Następnie opracowano radix-2 direct 2-D FFT, który może wyeliminować 25% mnożeń w porównaniu z konwencjonalnym podejściem wiersz-kolumna. Algorytm ten został rozszerzony na tablice prostokątne i dowolne podstawy, co jest ogólnym algorytmem wektorowo-podstawowym.

Algorytm Vector-radix FFT może znacznie zmniejszyć liczbę złożonych mnożeń w porównaniu z algorytmem wektorów wierszy. Na przykład dla $wynosi$ wymiarów i rozmiaru N w każdym wymiarze) liczba zespolonych wielokrotności algorytmu FFT z wektorową podstawą dla podstawy-2 ${\ Displaystyle {\ Frac {2 ^ {M} -1} {2 ^ {M}}} N ^ {M} \ log _ {2} N}$ tymczasem algorytm kolumnowy, to ${\ Displaystyle {\ Frac {MN ^ {M}} {2}} \ log _ {2} N}$ . Ogólnie rzecz biorąc, jeszcze większe oszczędności w mnożnikach uzyskuje się, gdy algorytm ten działa na większych podstawach i na tablicach o wyższych wymiarach.

Ogólnie rzecz biorąc, algorytm wektor-podstawa znacznie zmniejsza złożoność strukturalną tradycyjnego DFT, mającego lepszy schemat indeksowania, kosztem niewielkiego wzrostu operacji arytmetycznych. Algorytm ten jest więc szeroko stosowany w wielu zastosowaniach w inżynierii, nauce i matematyce, na przykład w implementacjach przetwarzania obrazu i projektowaniu szybkich procesorów FFT.

Obudowa 2-D DIT

Podobnie jak w przypadku algorytmu FFT Cooleya-Tukeya , dwuwymiarowa FFT z wektorową podstawą jest uzyskiwana przez rozłożenie zwykłego 2-D DFT na sumy mniejszych DFT pomnożonych przez współczynnik „twiddle”.

dziesiątkowania w czasie ( DIT ) oznacza $, że$ ​​dekompozycja jest oparta na domenie czasu zobacz więcej w Algorytm Cooley – Tukey FFT .

Zakładamy, że 2-D DFT

${\ Displaystyle X (k_ {1}, k_ {2}) = \ suma _ {n_ {1} = 0} ^ {N_ {1} -1} \ suma _ {n_ {2} = 0} ^ {N_ {2}-1}x[n_{1},n_{2}]\cdot W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2 }n_{2}},}$

gdzie ${\ Displaystyle k_ {1} = 0, \ kropki, N_ {1} -1}$ i ${\ Displaystyle k_ {2} = 0, \ kropki, N_ {2}-1}$ i ${\ Displaystyle x [n_ {1}, n_ {2}]}$ jest ${\ Displaystyle N_ {1}\razy N_{2}}$ macierz i ${\ Displaystyle W_ {N} = \ exp (-j2 \ pi / N)}$ .

Dla uproszczenia załóżmy, że ${\ Displaystyle N_ {1} = N_ {2} = N}$ i radix - ${\ Displaystyle (r \ razy r)}$ ( ${\ displaystyle N/r}$ są liczbami całkowitymi).

Korzystając ze zmiany zmiennych:

• ${\ Displaystyle n_ {i} = rp_ {i} + q_ {i}}$ , gdzie ${\ Displaystyle p_ {i} = 0, \ ldots, (N / r) -1; q_ {i} = 0, \ ldots, r-1;}$
• ${\ Displaystyle k_ {i} = u_ {i} + v_ {i} N/r}$ , gdzie ${\ Displaystyle u_ {i} = 0, \ ldots, (N / r) -1; v_ {i} = 0, \ ldots, r-1;}$

gdzie ${\ displaystyle i = 1}$ lub ${\ displaystyle 2}$ , to dwuwymiarowy DFT można zapisać jako:

${\ Displaystyle X (u_ {1} + v_ {1} N / r, u_ {2} + v_ {2} N / r) = \ suma _ {q_ {1} = 0} ^ {r-1}\suma _{q_{2}=0}^{r-1}\left[\suma _{p_{1}=0}^{N/r-1}\suma _{p_{ 2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{1}+q_{1}]W_{N/r}^{p_{1}u_{1 }}W_{N/r}^{p_{2}u_{2}}\right]\cdot W_{N}^{q_{1}u_{1}+q_{2}u_{2}}W_{ r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}},}$

Jednostopniowy „motylek” dla DIT vector-radix 2x2 FFT

$.$ definiuje podstawową strukturę podstawy 2-D ” (Patrz „motyl” 1-D w algorytmie Cooley – Tukey FFT )

Gdy ${\ displaystyle r = 2}$ równanie można podzielić na cztery podsumowania: jedno na tych próbkach x, dla których zarówno ${\ displaystyle n_ {1}}$ , jak i ${\ displaystyle n_ {2} }$ są parzyste, dla których ${\ displaystyle n_ {1}}$ jest parzyste i ${\ displaystyle n_ {2}}$ jest nieparzyste, z których jedno jest nieparzyste i ${\ displaystyle n_ {2}}$$\ displaystyle n_ {1}}$ jest parzysta i taka, dla której zarówno ${\ displaystyle n_ {1}},$ jak i ${\ displaystyle n_ {2}}$ są nieparzyste, a to prowadzi do: n 1 {\ displaystyle n_ {1}}

${\ Displaystyle X (k_ {1}, k_ {2}) = S_ {00} (k_ {1}, k_ {2}) + S_ {01} (k_ { 1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11 }(k_{1},k_{2})W_{N}^{k_{1}+k_{2}},}$

gdzie ${\ Displaystyle S_ {ij} (k_ {1}, k_ {2}) = \ suma _ {n_ {1} = 0} ^ {N / 2-1} \ suma _ {n_ {2} = 0} ^ {N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{ n_{2}k_{2}}.}$

Obudowa DIF 2-D

Podobnie algorytm decymacji w częstotliwości ( DIF , zwany także algorytmem Sande-Tukeya) oznacza, że ​​dekompozycja jest oparta na dziedzinie częstotliwości $patrz$ więcej w Algorytm FFT Cooleya-Tukeya .

Korzystając ze zmiany zmiennych:

• ${\ Displaystyle n_ {i} = p_ {i} + q_ {i} N/r}$ , gdzie ${\ Displaystyle p_ {i} = 0, \ ldots, (N / r) -1; q_ {i} = 0, \ ldots, r-1;}$
• ${\ Displaystyle k_ {i} = ru_ {i} + v_ {i}}$ , gdzie ${\ Displaystyle u_ {i} = 0, \ ldots, (N / r) -1; v_ {i} = 0, \ ldots, r-1;}$

gdzie ${\ displaystyle i = 1}$ lub ${\ displaystyle 2}$ , a równanie DFT można zapisać jako:

${\ Displaystyle X (ru_ {1} + v_ {1}, ru_ {2} + v_ {2}) = \ suma _ {p_ {1} = 0} ^ {N / r-1 }\suma _{p_{2}=0}^{N/r-1}\left[\suma _{q_{1}=0}^{r-1}\suma _{q_{2}=0 }^{r-1}x[p_{1}+q_{1}N/r,p_{1}+q_{1}N/r]W_{r}^{q_{1}v_{1}} W_{r}^{q_{2}v_{2}}\right]\cdot W_{N}^{p_{1}v_{1}+p_{2}v_{2}}W_{N/r} ^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}},}$

Inne podejścia

algorytm FFT z dzieloną podstawą jest przydatną metodą dla 1-D DFT. I ta metoda została zastosowana do wektorowo-radixowej FFT, aby otrzymać podzieloną wektorowo-radiową FFT.

W konwencjonalnym algorytmie wektora-podstawy 2-D rozkładamy wskaźniki na 4 grupy: ${\ displaystyle k_ {1}, k_ {2}}$

${\ Displaystyle {\ rozpocząć {tablica} {lcl} X (2k_ {1}, 2k_ {2}) &: & {\ tekst {parzysty}} \\ X (2k_ {1} ,2k_{2}+1)&:&{\text{parzysty-nieparzysty}}\\X(2k_{1}+1,2k_{2})&:&{\text{nieparzysty-parzysty}}\\ X(2k_{1}+1,2k_{2}+1)&:&{\text{nieparzyste-nieparzyste}}\end{tablica}}}$

Dzięki algorytmowi podzielonej podstawy wektorów pierwsze trzy grupy pozostają niezmienione, czwarta grupa nieparzysta-nieparzysta jest dalej rozkładana na kolejne cztery podgrupy i łącznie siedem grup:

${\ Displaystyle {\ rozpocząć {tablica} {lcl} X (2k_ {1}, 2k_ {2}) &: & {\ tekst {parzysty}} \\ X (2k_ {1}, 2k_ {2} + 1)&:&{\text{parzysty-parzysty}}\\X(2k_{1}+1,2k_{2})&:&{\text{nieparzysty-parzysty}}\\X(4k_{1} +1,4k_{2}+1)&:&{\text{nieparzysty-nieparzysty}}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{nieparzysty-nieparzysty }}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{nieparzyste-nieparzyste}}\\X(4k_{1}+3,4k_{2}+3) &:&{\text{nieparzyste-nieparzyste}}\end{tablica}}}$

Oznacza to czwarty wyraz w równaniu 2-D DIT radix- ${\ Displaystyle (2 \ razy 2)}$ równanie, ${\ Displaystyle S_ { 11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$ staje się:

${\ Displaystyle A_ {11} (k_ {1}, k_ {2}) W_ {N} ^ {k_ {1} + k_ {2}}+A_{13}(k_{1},k_{2})W_{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2 })W_{N}^{3k_{1}+k_{2}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2 })},}$

gdzie ${\ Displaystyle A_ {ij} (k_ {1}, k_ {2}) = \ suma _ {n_ {1} = 0} ^ {N / 4-1} \ suma _ { n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}} W_{N/4}^{n_{2}k_{2}}}$

Następnie 2-DN przez N DFT uzyskuje się przez kolejne zastosowanie powyższego rozkładu, aż do ostatniego etapu.

Wykazano, że algorytm podzielonej podstawy wektora pozwolił zaoszczędzić około 30% złożonych mnożeń i mniej więcej taką samą liczbę złożonych dodawań dla typowej $porównaniu$ z algorytmem wektora podstawy .