Shvidke peretvo rennya Fur ye chasto FFT vid angl Fast Fourier Transform shvidkij algoritm obchislennya diskretnogo peretvorennya Fur ye Yaksho dlya pryamogo obchislennya diskretnogo peretvorennya Fur ye z N tochok danih potribno O N 2 arifmetichnih operacij to FFT dozvolyaye obchisliti takij zhe rezultat vikoristovuyuchi O N log N operacij Algoritm FFT chasto vikoristovuyetsya dlya cifrovoyi obrobki signaliv dlya peretvorennya diskretnih danih z chasovogo u chastotnij diapazon Zmist 1 Osnovnij algoritm 2 Obernene peretvorennya Fur ye 3 Zagalnij vipadok 4 Visnovok peretvorennya z DPF 5 Algoritm Kuli Tyuki 6 Inshi algoritmi ShPF 7 Div takozh 8 Dzherela 9 PosilannyaOsnovnij algoritm RedaguvatiPokazhemo yak vikonati diskretne peretvorennya Fur ye za O N p 1 p n displaystyle O N p 1 cdots p n nbsp obchislen pri N p 1 p 2 p n displaystyle N p 1 p 2 cdots p n nbsp Zokrema pri N 2 n displaystyle N 2 n nbsp znadobitsya O N log N displaystyle O N log N nbsp obchislen Diskretne peretvorennya Fur ye peretvoryuye nabir chisel a 0 a n 1 displaystyle a 0 dots a n 1 nbsp v nabir chisel b 0 b n 1 displaystyle b 0 dots b n 1 nbsp takij sho b i j 0 n 1 a j e i j displaystyle b i sum j 0 n 1 a j varepsilon ij nbsp de e n 1 displaystyle varepsilon n 1 nbsp i e k 1 displaystyle varepsilon k neq 1 nbsp pri 0 lt k lt n displaystyle 0 lt k lt n nbsp Algoritm shvidkogo peretvorennya Fur ye mozhe buti zastosovanij do bud yakih komutativnih asociativnih kilec z odiniceyu Najchastishe cej algoritm zastosovuyut do polya kompleksnih chisel z e e 2 p i n displaystyle varepsilon e 2 pi i n nbsp i do kilec zalishkiv za modulem n Osnovnij krok algoritmu polyagaye u zvedenni zadachi dlya N displaystyle N nbsp chisel do zadachi dlya p N q displaystyle p N q nbsp chisel de q displaystyle q nbsp dilnik N displaystyle N nbsp Nehaj mi vzhe vmiyemo virishuvati zadachu dlya N q displaystyle N q nbsp chisel Zastosuyemo peretvorennya Fur ye do naboriv a i a q i a q p 1 i displaystyle a i a q i dots a q p 1 i nbsp dlya i 0 1 q 1 displaystyle i 0 1 dots q 1 nbsp Teper pokazhemo yak za O N p displaystyle O Np nbsp obchislen rozv yazati vihidnu zadachu Zauvazhimo sho b i j 0 q 1 e i j k 0 p 1 a k q j e k i q displaystyle b i sum j 0 q 1 varepsilon ij sum k 0 p 1 a kq j varepsilon kiq nbsp Virazi v duzhkah nam uzhe vidomi ce i mod p displaystyle i pmod p nbsp te chislo pislya peretvorennya Fur ye j displaystyle j nbsp toyi grupi Takim chinom dlya obchislennya kozhnogo b i displaystyle b i nbsp potribno O q displaystyle O q nbsp obchislen a dlya obchislennya vsih b i displaystyle b i nbsp O N q displaystyle O Nq nbsp obchislen Obernene peretvorennya Fur ye RedaguvatiDlya obernenogo peretvorennya Fur ye mozhna zastosovuvati algoritm pryamogo peretvorennya Fur ye potribno lishe vikoristovuvati e 1 displaystyle varepsilon 1 nbsp zamist e displaystyle varepsilon nbsp abo zastosuvati operaciyu kompleksnogo spryazhennya spochatku do vhidnih danih a potim do rezultatu otrimanogo pislya pryamogo peretvorennya Fur ye i ostatochnij rezultat podiliti na N displaystyle N nbsp Zagalnij vipadok RedaguvatiZagalnij vipadok mozhna zvesti do poperednogo Nehaj 4 N gt 2 k 2 N displaystyle 4N gt 2 k geq 2N nbsp Zauvazhimo sho b i e i 2 2 j 0 N 1 e i j 2 2 e j 2 2 a j displaystyle b i varepsilon i 2 2 sum j 0 N 1 varepsilon i j 2 2 varepsilon j 2 2 a j nbsp Poznachimo a i e i 2 2 a i b i e i 2 2 b i c i e 2 N 2 i 2 2 displaystyle bar a i varepsilon i 2 2 a i bar b i varepsilon i 2 2 b i c i varepsilon 2N 2 i 2 2 nbsp Todi b i j 0 2 N 2 i a j c 2 N 2 i j displaystyle bar b i sum j 0 2N 2 i bar a j c 2N 2 i j nbsp yaksho poklasti a i 0 displaystyle bar a i 0 nbsp pri i N displaystyle i geq N nbsp Takim chinom zadachu zvedeno do obchislennya zgortki ale ce mozhna zrobiti za dopomogoyu troh peretvoren Fur ye dlya 2 k displaystyle 2 k nbsp elementiv Spochatku vikonayemo pryame peretvorennya Fur ye dlya a i i 0 i 2 k 1 displaystyle bar a i i 0 i 2 k 1 nbsp i c i i 0 i 2 k 1 displaystyle c i i 0 i 2 k 1 nbsp dali peremnozhimo poelementno rezultati i vikonayemo obernene peretvorennya Fur ye Obchislennya vsih a i displaystyle bar a i nbsp i c i displaystyle c i nbsp potrebuye O N displaystyle O N nbsp operacij tri peretvorennya Fur ye vikonuyetsya za O N log N displaystyle O N log N nbsp operacij peremnozhennya rezultativ peretvoren Fur ye vimagaye O N displaystyle O N nbsp operacij znayuchi znachennya zgortki obchislennya vsih b i displaystyle b i nbsp vimagaye O N displaystyle O N nbsp operacij Usogo dlya diskretnogo peretvorennya Fur ye potribno O N log N displaystyle O N log N nbsp dij dlya bud yakogo N displaystyle N nbsp Cej algoritm shvidkogo peretvorennya Fur ye mozhe pracyuvati nad kilcem tilki koli vidomi pervisni koreni z odinici stupeniv 2 N displaystyle 2N nbsp i 2 k displaystyle 2 k nbsp Visnovok peretvorennya z DPF RedaguvatiDiskretne peretvorennya Fur ye dlya vektora x displaystyle vec x nbsp Sho skladayetsya z N displaystyle N nbsp elementiv maye viglyad X A x displaystyle vec X hat A vec x nbsp dd elementi matrici A displaystyle hat A nbsp mayut viglyad a N m n exp 2 p i m n N displaystyle a N mn exp left 2 pi i frac mn N right nbsp Nehaj N displaystyle N nbsp parne todi DPF mozhna perepisati takim chinom X m n 0 N 1 x n a N m n n 0 N 2 1 x 2 n a N 2 n m n 0 N 2 1 x 2 n 1 a N 2 n 1 m displaystyle X m sum n 0 N 1 x n a N mn sum n 0 N 2 1 x 2n a N 2nm sum n 0 N 2 1 x 2n 1 a N 2n 1 m nbsp dd Koeficiyenti a N 2 n m displaystyle a N 2nm nbsp i a N 2 n 1 m displaystyle a N 2n 1 m nbsp mozhna perepisati nastupnim chinom M N 2 displaystyle M N 2 nbsp a N 2 n m exp 2 p i 2 m n N exp 2 p i m n N 2 a M n m displaystyle a N 2nm exp left 2 pi i frac 2mn N right exp left 2 pi i frac mn N 2 right a M nm nbsp a N 2 n 1 m exp 2 p i m N a M n m displaystyle a N 2n 1 m exp left 2 pi i frac m N right a M nm nbsp dd U rezultati otrimayemo X m n 0 M 1 x 2 n a M n m exp 2 p i m N n 0 M 1 x 2 n 1 a M n m displaystyle X m sum n 0 M 1 x 2n a M nm exp left 2 pi i frac m N right sum n 0 M 1 x 2n 1 a M nm nbsp dd Tobto diskretne peretvorennya Fur ye vid vektora sho skladayetsya z N displaystyle N nbsp vidlikiv zvelosya do linijnoyi kompoziciyi dvoh DPF vid N 2 displaystyle frac N 2 nbsp vidlikiv i yaksho dlya pochatkovoyi zadachi potribno N 2 displaystyle N 2 nbsp operacij to dlya otrimanoyi kompoziciyi N 2 2 displaystyle frac N 2 2 nbsp Yaksho M displaystyle M nbsp ye stepenem dvijki to cej podil mozhna prodovzhuvati rekursivno doti poki ne dijdemo do dvotochkovogo peretvorennya Fur ye yake obchislyuyetsya za takimi formulami X 0 x 0 x 1 X 1 x 0 x 1 displaystyle begin cases X 0 x 0 x 1 X 1 x 0 x 1 end cases nbsp dd Algoritm Kuli Tyuki RedaguvatiDokladnishe Algoritm Kuli TyukiNajbilsh rozpovsyudzhenim algoritmom rozrahunku FFT ye algoritm Kuli Tyuki zaproponovanij Dzhejmsom Kuli ta Dzhonom Tyuki v 1965 roci 1 Yak z yasuvalosya zgodom cej algoritm buv vinajdenij Karlom Gausom she v 1805 roci Algoritm zasnovanij na rekursivnomu rozdilenni peretvorennya na kozhnomu kroci na dvi chastini rozmirom N 2 displaystyle N 2 nbsp Yaksho N displaystyle N nbsp ne dilitsya na dva to robitsya faktorizaciya Dlya rozrahunku zastosovuyut koreni z odinici Diskretne peretvorennya Fur ye velichini 2n viznachayetsya yak f m k 0 2 n 1 x k e 2 p i 2 n m k m 0 2 n 1 displaystyle f m sum k 0 2n 1 x k e frac 2 pi i 2n mk qquad m 0 dots 2n 1 nbsp Yaksho poznachiti vkladi parnih indeksiv yak x 0 x1 x 1 x2 x n 1 x2n 2ta yihni peretvorennya velichini n yak f 0 f n 1 ta vkladi neparnih indeksiv x 0 x1 x 1 x3 x n 1 x2n 1ta yihni peretvorennya velichini n yak f 0 f n 1 todi f m k 0 n 1 x 2 k e 2 p i 2 n m 2 k k 0 n 1 x 2 k 1 e 2 p i 2 n m 2 k 1 k 0 n 1 x k e 2 p i n m k e p i n m k 0 n 1 x k e 2 p i n m k f m e p i n m f m m lt n f m n e p i n m n f m n m n displaystyle begin aligned f m amp sum k 0 n 1 x 2k e frac 2 pi i 2n m 2k sum k 0 n 1 x 2k 1 e frac 2 pi i 2n m 2k 1 0 5em amp sum k 0 n 1 x k e frac 2 pi i n mk e frac pi i n m sum k 0 n 1 x k e frac 2 pi i n mk 0 5em amp begin cases f m e frac pi i n m f m amp text m lt n 0 5em f m n e frac pi i n m n f m n amp text m geq n end cases end aligned nbsp Inshi algoritmi ShPF RedaguvatiKrim algoritmu Kuli Tyuki isnuyut takozh inshi Dlya N N 1 N 2 displaystyle N N1 times N2 nbsp zi vzayemno prostimi N 1 displaystyle N1 nbsp i N 2 displaystyle N2 nbsp mozhna zastosuvati algoritm Guda Tomasa rozkladu na prosti dilniki Prime Factor Algorithm zasnovanij na kitajskij teoremi pro zalishki shob faktorizuvati DPF analogichno Kuli Tyuki ale bez koeficiyentiv povorotu Div takozh RedaguvatiPeretvorennya Fur ye Diskretne peretvorennya Fur ye Algoritm Shonhage ShtrassenaDzherela Redaguvati James W Cooley John W Tukey An algorithm for the machine calculation of complex Fourier series In Math Comput 19 1965 S 297 301 Posilannya RedaguvatiBrigham E O 2002 The Fast Fourier Transform New York Prentice Hall Shvidke peretvorennya Fur ye na bazi cifrovogo signalnogo procesoru Cifrovi signalni procesori TMS320C55x firmi Texas Instruments Kurs laboratornih robit Arhiv originalu za 8 travnya 2013 Otrimano z https uk wikipedia org w index php title Shvidke peretvorennya Fur 27ye amp oldid 40109846
