Algoritmus FFT Prime-factor - Prime-factor FFT algorithm

Prime-faktor algoritmus (PFA) , také volal algoritmus Good-Thomas (1958/1963), je rychlá Fourierova transformace (FFT) algoritmus, který re-vyjadřuje diskrétní Fourierova transformace (DFT) o velikosti N = N ₁ N ₂ jako dvourozměrný N ₁ × N ₂ DFT, ale pouze pro případ, kdy N ₁ a N ₂ jsou relativně primární . Tyto menší transformace velikosti N ₁ a N ₂ lze poté vyhodnotit rekurzivní aplikací PFA nebo použitím jiného algoritmu FFT.

PFA by neměla být zaměňována s generalizací smíšeného radixu populárního algoritmu Cooley – Tukey , který také rozděluje DFT velikosti N = N ₁ N ₂ na menší transformace velikosti N ₁ a N ₂ . Druhý algoritmus může používat jakékoli faktory (ne nutně relativně prime), ale má tu nevýhodu, že kromě menších transformací vyžaduje také další násobení kořeny jednoty zvané twiddle faktory . Na druhou stranu má PFA nevýhody v tom, že funguje pouze pro relativně hlavní faktory (např. Je zbytečné pro sílu dvou velikostí) a že vyžaduje složitější přeindexování dat na základě čínské věty o zbytku ( CRT). Všimněte si však, že PFA lze kombinovat s Cooley – Tukey se smíšeným radixem, přičemž první faktorizuje N do relativně hlavních složek a druhý zpracovává opakované faktory.

PFA je také úzce spojena s vnořené algoritmu FFT Winograd , pokud toto spojení provádí rozložené N ₁ pomocí N ₂ transformace pomocí sofistikovanějších dvourozměrných konvolučních techniky. Některé starší články proto také nazývají Winogradův algoritmus PFA FFT.

(Ačkoli PFA je odlišný od algoritmu Cooley-Tukey, Good ‚s 1958 práce na PFA byl citován jako inspirace Cooley a Tukey v jejich 1965 papíru, a tam byl zpočátku nějaký zmatek o tom, zda tyto dva algoritmy byly různé. Ve skutečnosti , byla to jediná předchozí práce FFT, kterou citovali, protože si tehdy nebyli vědomi dřívějšího výzkumu Gaussa a dalších.)

Algoritmus

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

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} nk} \ quad k = 0 , \, \ tečky, \, N-1.}$

PFA zahrnuje opětovné indexování vstupního a výstupního pole, které při nahrazení do vzorce DFT transformuje na dva vnořené DFT (dvourozměrný DFT).

Opětovné indexování

Předpokládejme, že kde a jsou relativně prime, tj . Poté se provede opětovné indexování pomocí dvou bijektivních mapování mezi a . ${\ displaystyle N = N_ {1} N_ {2}}$${\ displaystyle N_ {1}}$${\ displaystyle N_ {2}}$${\ displaystyle \ gcd (N_ {1}, N_ {2}) = 1}$${\ displaystyle \ mathbb {Z} _ {N_ {1}} \ times \ mathbb {Z} _ {N_ {2}}}$${\ displaystyle \ mathbb {Z} _ {N}}$

První mapa

${\ displaystyle n = \ eta (n_ {1}, n_ {2}) = (n_ {1} N_ {2} + n_ {2} N_ {1}) {\ bmod {N}}}$

Je bijection nazývá ruritánského mapování (také Goodův mapping).

Ve skutečnosti jde o homomorfismus , protože a : ${\ displaystyle \ mathbb {Z} _ {N_ {1}} \ times \ mathbb {Z} _ {N_ {2}} \ do \ mathbb {Z} _ {N}}$${\ displaystyle \ forall n_ {1}, m_ {1} \ in \ mathbb {Z} _ {N_ {1}}}$${\ displaystyle \ forall n_ {2}, m_ {2} \ in \ mathbb {Z} _ {N_ {2}}}$

${\ displaystyle {\ begin {aligned} \ eta \ left ((n_ {1} + m_ {1}) {\ bmod {N}} _ {1}, (n_ {2} + m_ {2}) {\ bmod {N}} _ {2} \ right) & = \ left (\ left ((n_ {1} + m_ {1}) {\ bmod {N}} _ {1} \ right) N_ {2} + \ left ((n_ {2} + m_ {2}) {\ bmod {N}} _ {2} \ right) N_ {1} \ right) {\ bmod {N}} \\ & = \ left (\ left ((n_ {1} + m_ {1}) N_ {2} \ right) {\ bmod {(}} N_ {1} N_ {2}) + \ left ((n_ {2} + m_ {2} ) N_ {1} \ right) {\ bmod {(}} N_ {1} N_ {2}) \ right) {\ bmod {N}} \\ & = \ left ((n_ {1} + m_ {1 }) N_ {2} + (n_ {2} + m_ {2}) N_ {1} \ vpravo) {\ bmod {N}} \\ & = \ vlevo (n_ {1} N_ {2} + m_ { 1} N_ {2} + n_ {2} N_ {1} + m_ {2} N_ {1} \ vpravo) {\ bmod {N}} \\ & = \ left ((n_ {1} N_ {2} + n_ {2} N_ {1}) {\ bmod {N}} + (m_ {1} N_ {2} + m_ {2} N_ {1}) {\ bmod {N}} \ vpravo) {\ bmod {N}} \\ & = \ left (\ eta (n_ {1}, n_ {2}) + \ eta (m_ {1}, m_ {2}) \ right) {\ bmod {N}}. \ konec {zarovnáno}}}$

Proto, v souladu s prvním izomorfizmu teorém , je vstřikování do skupiny kvocient . Tady jádro , protože jinak by existoval pár a , které nejsou současně nulové, takové, že pro nenulovou . Protože jediná zbývající hodnota je 1. V tomto případě by bylo celé číslo, ze kterého je nemožné, protože aby zlomek poskytl celočíselnou hodnotu, musí být násobkem (od ). To by však bylo v rozporu . To je tedy injekce . Nyní, protože , je skutečně bijektivní, tj. Pro odlišné hodnoty páru produkuje odlišné hodnoty v celé sadě . ${\ displaystyle \ eta}$ ${\ displaystyle \ mathbb {Z} _ {N} / \ ker (\ eta)}$ ${\ displaystyle \ ker (\ eta) = \ {0 \}}$${\ displaystyle n_ {1} \ in \ mathbb {Z} _ {N_ {1}}}$${\ displaystyle n_ {2} \ in \ mathbb {Z} _ {N_ {2}}}$${\ displaystyle n_ {1} N_ {2} + n_ {2} N_ {1} = tN_ {1} N_ {2}}$${\ displaystyle t \ in \ mathbb {N}}$${\ displaystyle n_ {1} N_ {2} + n_ {2} N_ {1} \ leq 2N_ {1} N_ {2} - (N_ {1} + N_ {2}) <2N_ {1} N_ {2 }}$${\ displaystyle t}$${\ displaystyle n_ {1} = N_ {1} - {\ frac {n_ {2} N_ {1}} {N_ {2}}}}$${\ displaystyle \ mathbb {Z} _ {N_ {1}}}$${\ displaystyle {\ frac {n_ {2} N_ {1}} {N_ {2}}}}$${\ displaystyle n_ {2}}$${\ displaystyle N_ {2}}$${\ displaystyle \ gcd (N_ {1}, N_ {2}) = 1}$${\ displaystyle n_ {1} \ in \ mathbb {Z} _ {N_ {1}} \ land n_ {2} \ in \ mathbb {Z} _ {N_ {2}}}$${\ displaystyle \ mathbb {Z} _ {N} / \ ker (\ eta) \ cong \ mathbb {Z} _ {N}}$${\ displaystyle \ eta}$${\ displaystyle \ mathbb {Z} _ {N}}$${\ displaystyle \ operatorname {karta} \ left (\ mathbb {Z} _ {N_ {1}} \ times \ mathbb {Z} _ {N_ {2}} \ right) = \ operatorname {card} \ left (\ mathbb {Z} _ {N} \ right) = N_ {1} N_ {2}}$${\ displaystyle \ eta}$${\ displaystyle n_ {1}, n_ {2}}$${\ displaystyle n}$${\ displaystyle \ mathbb {Z} _ {N}}$

Druhá mapa

${\ displaystyle k = \ kappa (k_ {1}, k_ {2}) = (k_ {1} N '_ {2} N_ {2} + k_ {2} N' _ {1} N_ {1}) {\ bmod {N}}}$

se nazývá CRT mapování. Název odkazuje na čínský zbytek věty, která poskytuje bijective mapování , ve kterém a jsou jakékoli řešení lineární rovnice diophantine rovnice (viz Bézout identitu ). ${\ displaystyle \ kappa: \ mathbb {Z} _ {N_ {1}} \ krát \ mathbb {Z} _ {N_ {2}} \ do \ mathbb {Z} _ {N}}$${\ displaystyle N '_ {1}}$${\ displaystyle N '_ {2}}$${\ displaystyle N '_ {1} N_ {1} + N' _ {2} N_ {2} = \ gcd (N_ {1}, N_ {2}) = 1}$

Aby bylo možné provést DFT, je třeba mapovat různé páry a na odlišné hodnoty a také páry a na . K tomu lze použít ruritánské mapování k vytvoření indexů ve vstupním vektoru a mapování CRT k vyhodnocení indexů výstupního vektoru nebo použít dvě mapování opačně. ${\ displaystyle n_ {1} \ in \ mathbb {Z} _ {N_ {1}}}$${\ displaystyle n_ {2} \ in \ mathbb {Z} _ {N_ {2}}}$${\ displaystyle n \ in \ mathbb {Z} _ {N}}$${\ displaystyle k_ {1} \ in \ mathbb {Z} _ {N_ {1}}}$${\ displaystyle k_ {2} \ in \ mathbb {Z} _ {N_ {2}}}$${\ displaystyle k \ in \ mathbb {Z} _ {N}}$

Velká část výzkumu byla věnována schématům pro efektivní vyhodnocení této reindexace, ideálně na místě , při minimalizaci počtu nákladných operací modulo (zbytek) (Chan, 1991 a reference).

DFT re-výraz

Výše uvedená opětovná indexace se poté nahradí do vzorce pro DFT a zejména do produktu v exponentu. Protože tento exponent je vyhodnocován modulo . Podobně a jsou implicitně periodické , takže jejich dolní indexy jsou vyhodnocovány modulo . ${\ displaystyle nk}$${\ displaystyle \ forall t \ in \ mathbb {Z}: e ^ {2 \ pi it} = 1}$${\ displaystyle N}$${\ displaystyle X_ {k}}$${\ displaystyle x_ {n}}$${\ displaystyle N}$${\ displaystyle N}$

Nejprve nahraďte ruritánské mapování do vzorce pro DFT:

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} nk} = \ součet _ { n = 0} ^ {N_ {1} N_ {2} -1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N_ {1} N_ {2}}} nk} = \ součet _ {n_ {1} = 0} ^ {N_ {1} -1} \ suma _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2} + n_ {2} N_ {1}} e ^ {- 2 \ pi ik {\ frac {n_ {1} N_ {2} + n_ {2} N_ {1}} {N_ {1} N_ {2}}}} = \ sum _ {n_ {1} = 0} ^ {N_ {1} -1} e ^ {- {\ frac {2 \ pi i} {N_ {1}}} n_ {1} k} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2} + n_ {2} N_ {1}} e ^ {- {\ frac {2 \ pi i} {N_ {2}}} n_ {2} k}}$.

Nyní nahradit mapování CRT namísto vyrábět ${\ displaystyle k}$

${\ displaystyle {\ begin {seřazeno} X_ {k_ {1} N_ {2} N '_ {2} + k_ {2} N_ {1} N' _ {1}} & = \ sum _ {n_ {1 } = 0} ^ {N_ {1} -1} e ^ {- 2 \ pi in_ {1} {\ frac {k_ {1} N_ {2} N '_ {2} + k_ {2} N_ {1 } N '_ {1}} {N_ {1}}}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2} + n_ {2 } N_ {1}} e ^ {- 2 \ pi in_ {2} {\ frac {k_ {1} N_ {2} N '_ {2} + k_ {2} N_ {1} N' _ {1} } {N_ {2}}}} \\ & = \ sum _ {n_ {1} = 0} ^ {N_ {1} -1} e ^ {- 2 \ pi in_ {1} k_ {1} {\ frac {N_ {2} N '_ {2}} {N_ {1}}}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2 } + n_ {2} N_ {1}} e ^ {- 2 \ pi in_ {2} k_ {2} {\ frac {N_ {1} N '_ {1}} {N_ {2}}}} \ \ & = \ sum _ {n_ {1} = 0} ^ {N_ {1} -1} e ^ {- 2 \ pi in_ {1} k_ {1} {\ frac {1-N_ {1} N ' _ {1}} {N_ {1}}}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2} + n_ {2} N_ { 1}} e ^ {- 2 \ pi in_ {2} k_ {2} {\ frac {1-N_ {2} N '_ {2}} {N_ {2}}}} \\ & = \ sum _ {n_ {1} = 0} ^ {N_ {1} -1} e ^ {- {\ frac {2 \ pi in_ {1} k_ {1}} {N_ {1}}}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ {2} + n_ {2} N_ {1}} e ^ {- {\ frac {2 \ pi in_ {2} k_ {2}} {N_ {2}}}}. \ end {zarovnáno}}}$

Podobně substituce mapování CRT namísto mapování Ruritanian namísto výnosů ${\ displaystyle n}$${\ displaystyle k}$

${\ displaystyle X_ {k_ {1} N_ {2} + k_ {2} N_ {1}} = \ součet _ {n_ {1} = 0} ^ {N_ {1} -1} e ^ {- {\ frac {2 \ pi ik_ {1} n_ {1}} {N_ {1}}}} \ sum _ {n_ {2} = 0} ^ {N_ {2} -1} x_ {n_ {1} N_ { 2} N '_ {2} + n_ {2} N_ {1} N' _ {1}} e ^ {- {\ frac {2 \ pi ik_ {2} n_ {2}} {N_ {2}} }}}$.

V obou případech jsou vnitřní a vnější částky jsou jednoduše DFT velikosti a , v tomto pořadí. ${\ displaystyle N_ {2}}$${\ displaystyle N_ {1}}$

Reference

• Dobře, IJ (1958). "Algoritmus interakce a praktická Fourierova analýza". Journal of královské statistické společnosti, série B . 20 (2): 361–372. JSTOR  2983896 .Dodatek, tamtéž. 22 (2), 373-375 (1960) JSTOR  2984108 .
• Thomas, LH (1963). "Použití počítače k ​​řešení problémů ve fyzice". Aplikace digitálních počítačů . Boston: Ginn.
• Duhamel, P .; Vetterli, M. (1990). "Fast Fourier transforms: a tutorial review and a state of the art" . Zpracování signálu . 19 (4): 259–299. doi : 10.1016 / 0165-1684 (90) 90158-U .
• Chan, SC; Ho, KL (1991). "Při indexování algoritmu rychlé Fourierovy transformace prime-factor". IEEE Trans. Obvody a systémy . 38 (8): 951–953. doi : 10,1109 / 31,85638 .

Viz také

• Raderův FFT algoritmus
• Bluesteinův FFT algoritmus