Algoritmus FFT Vector-radix - Vector-radix FFT algorithm

Vektor-radix FFT algoritmus , je multidimenzionální rychlá Fourierova transformace (FFT) algoritmus, který je zobecněním běžného algoritmu Cooley-Tukey FFT , která rozděluje transformace rozměry libovolnými radices. Rozbíjí multidimenzionální (MD) diskrétní Fourierovu transformaci (DFT) dolů na postupně menší MD DFT, dokud nakonec nemusí být hodnoceny pouze triviální MD DFT.

Nejběžnějším vícerozměrným algoritmem FFT je algoritmus řádek-sloupec, což znamená transformaci pole nejprve v jednom indexu a poté v druhém, více viz FFT . Poté byl vyvinut radix-2 direct 2-D FFT, který může eliminovat 25% násobení ve srovnání s konvenčním přístupem řádek-sloupec. A tento algoritmus byl rozšířen na obdélníková pole a libovolné radice, což je obecný algoritmus vektorových radixů.

Algoritmus FFT s vektorovým radixem může významně snížit počet složitých násobení ve srovnání s algoritmem řádek-vektor. Například pro elementovou matici (M rozměry a velikost N na každé dimenzi) je počet složitých násobků algoritmu FFT vektorový radix pro radix-2 mezitím pro algoritmus řádek-sloupec . A obecně se ještě větší úspory v násobcích dosáhnou, když je tento algoritmus provozován na větších radicích a na polích vyšších dimenzí.${\ displaystyle N ^ {M}}$${\ displaystyle {\ frac {2 ^ {M} -1} {2 ^ {M}}} N ^ {M} \ log _ {2} N}$${\ displaystyle {\ frac {MN ^ {M}} {2}} \ log _ {2} N}$

Celkově algoritmus vektorový radix významně snižuje strukturální složitost tradičního DFT s lepším indexovacím schématem, na úkor mírného zvýšení aritmetických operací. Tento algoritmus je tedy široce používán pro mnoho aplikací ve strojírenství, vědě a matematice, například při implementaci zpracování obrazu a při navrhování vysokorychlostního FFT procesoru.

2-D DIT pouzdro

Stejně jako u algoritmu Cooley – Tukey FFT je dvourozměrný vektorový radix FFT odvozen rozkladem běžného 2-D DFT na součty menších DFT vynásobených faktorem „twiddle“.

Algoritmus DIM (decimation-in-time ) znamená, že rozklad je založen na časové doméně , více viz algoritmus Cooley – Tukey FFT . ${\ displaystyle x}$

Předpokládáme 2-D DFT

${\ displaystyle X (k_ {1}, k_ {2}) = \ součet _ {n_ {1} = 0} ^ {N_ {1} -1} \ součet _ {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}},}$

kde , a , a je matice, a . ${\ displaystyle k_ {1} = 0, \ tečky, N_ {1} -1}$${\ displaystyle k_ {2} = 0, \ tečky, N_ {2} -1}$${\ displaystyle x [n_ {1}, n_ {2}]}$${\ displaystyle N_ {1} \ krát N_ {2}}$${\ displaystyle W_ {N} = \ exp (-j2 \ pi / N)}$

Pro jednoduchost předpokládejme, že a radix- ( jsou celá čísla). ${\ displaystyle N_ {1} = N_ {2} = N}$${\ displaystyle (r \ krát r)}$${\ displaystyle N / r}$

Použití změny proměnných:

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

kde nebo , pak lze dvourozměrný DFT zapsat jako:${\ displaystyle i = 1}$${\ displaystyle 2}$

${\ displaystyle X (u_ {1} + v_ {1} N / r, u_ {2} + v_ {2} N / r) = \ součet _ {q_ {1} = 0} ^ {r-1} \ součet _ {q_ {2} = 0} ^ {r-1} \ left [\ sum _ {p_ {1} = 0} ^ {N / r-1} \ sum _ {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}} \ vpravo] \ cdot W_ {N} ^ {q_ {1} u_ {1} + q_ {2} u_ {2}} W_ {r} ^ {q_ { 1} v_ {1}} W_ {r} ^ {q_ {2} v_ {2}},}$

Jednostupňový „motýl“ pro DIT vector-radix 2x2 FFT

Výše uvedená rovnice definuje základní strukturu 2-D DIT radix - „motýl“. (Viz 1-D „motýl“ v Cooley – Tukey FFT algoritmu ) ${\ displaystyle (r \ krát r)}$

Když lze rovnici rozdělit na čtyři součty: jeden nad těmi vzorky x, pro které jsou oba a sudé, jeden, pro který je sudý a lichý, jeden z nich je lichý a sudý, a jeden, pro který jsou oba a liché , a to vede k: ${\ displaystyle r = 2}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$

${\ 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}},}$

kde ${\ displaystyle S_ {ij} (k_ {1}, k_ {2}) = \ součet _ {n_ {1} = 0} ^ {N / 2-1} \ součet _ {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}}.}$

2-D DIF pouzdro

Podobně algoritmus decimation-in-frequency ( DIF , nazývaný také Sande – Tukeyův algoritmus) znamená, že rozklad je založen na frekvenční doméně , viz více v algoritmu Cooley – Tukey FFT . ${\ displaystyle X}$

Použití změny proměnných:

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

kde nebo a rovnici DFT lze zapsat jako:${\ displaystyle i = 1}$${\ displaystyle 2}$

${\ displaystyle X (ru_ {1} + v_ {1}, ru_ {2} + v_ {2}) = \ součet _ {p_ {1} = 0} ^ {N / r-1} \ součet _ {p_ {2} = 0} ^ {N / r-1} \ left [\ sum _ {q_ {1} = 0} ^ {r-1} \ sum _ {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}},}$

Další přístupy

Ukázalo se, že algoritmus split-radix FFT je užitečnou metodou pro 1-D DFT. A tato metoda byla použita na vektorový radix FFT k získání rozděleného vektorového radixu FFT.

V konvenčním algoritmu 2D-radix vektoru rozložíme indexy na 4 skupiny: ${\ displaystyle k_ {1}, k_ {2}}$

${\ displaystyle {\ begin {array} {lcl} X (2k_ {1}, 2k_ {2}) &: & {\ text {even-even}} \\ X (2k_ {1}, 2k_ {2} + 1) &: & {\ text {even-odd}} \\ X (2k_ {1} + 1,2k_ {2}) &: & {\ text {odd-even}} \\ X (2k_ {1} + 1,2k_ {2} +1) &: & {\ text {odd-odd}} \ end {array}}}$

Podle algoritmu split vektor-radix zůstávají první tři skupiny beze změny, čtvrtá lichá-lichá skupina je dále rozložena na další čtyři podskupiny a celkem sedm skupin:

${\ displaystyle {\ begin {array} {lcl} X (2k_ {1}, 2k_ {2}) &: & {\ text {even-even}} \\ X (2k_ {1}, 2k_ {2} + 1) &: & {\ text {even-odd}} \\ X (2k_ {1} + 1,2k_ {2}) &: & {\ text {odd-even}} \\ X (4k_ {1} + 1,4k_ {2} +1) &: & {\ text {odd-odd}} \\ X (4k_ {1} + 1,4k_ {2} +3) &: & {\ text {odd-odd }} \\ X (4k_ {1} + 3,4k_ {2} +1) &: & {\ text {odd-odd}} \\ X (4k_ {1} + 3,4k_ {2} +3) &: & {\ text {odd-odd}} \ end {pole}}}$

To znamená, že čtvrtý člen ve 2D-DIT radixové rovnici se stává:${\ displaystyle (2 \ krát 2)}$${\ displaystyle S_ {11} (k_ {1}, k_ {2}) W_ {N} ^ {k_ {1} + k_ {2}}}$

${\ 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})},}$

kde ${\ displaystyle A_ {ij} (k_ {1}, k_ {2}) = \ součet _ {n_ {1} = 0} ^ {N / 4-1} \ součet _ {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}}}$

2-DN pomocí N DFT se poté získá postupným použitím výše uvedeného rozkladu až do poslední fáze.

Ukázalo se, že algoritmus děleného vektorového radixu ve srovnání s algoritmem vektorového radixu zachránil asi 30% komplexních multiplikací a přibližně stejný počet komplexních sčítání pro typické pole.${\ displaystyle 1024 \ krát 1024}$

Reference