Cooley – Tukey FFT алгоритмі - Cooley–Tukey FFT algorithm

The Кули-Тукей алгоритмі, атындағы Джули В.Кули және Джон Туки, ең көп таралған жылдам Фурье түрлендіруі (FFT) алгоритмі. Ол қайтадан білдіреді дискретті Фурье түрлендіруі (DFT) ерікті құрама өлшемі N = N1N2 жөнінде N1 кіші өлшемді DFT N2, рекурсивті, есептеу уақытын O дейін азайту үшін (N журнал N) жоғары құрамды N (тегіс сандар ). Алгоритм маңызды болғандықтан, төменде сипатталғандай, нақты нұсқалар мен енгізу стильдері өз атауларымен белгілі болды.

Cooley-Tukey алгоритмі DFT-ны кіші DFT-ге бөлетіндіктен, оны DFT кез келген басқа алгоритмімен ерікті түрде біріктіруге болады. Мысалға, Радер немесе Блюстейндікі алгоритмді Кули-Туки немесе оны бұза алмайтын үлкен жай факторларды басқаруға пайдалануға болады қарапайым фактор алгоритмі бөліп алудың үлкен тиімділігі үшін пайдалануға болады салыстырмалы түрде қарапайым факторлар.

Алгоритм оны рекурсивті қолданумен бірге ойлап тапты Карл Фридрих Гаусс. Кули мен Туки оны 160 жылдан кейін дербес қайта ашты және танымал етті.

Тарих

Бұл алгоритм, оның рекурсивті қолданылуын қоса, шамамен 1805 ж Карл Фридрих Гаусс, оны траекторияларды интерполяциялау үшін қолданған астероидтар Паллас және Джуно, бірақ оның жұмысы көпшілікке танымал болмады (тек қайтыс болғаннан кейін және кейін жарияланды) нео-латын ).[1][2] Алайда Гаусс асимптотикалық есептеу уақытын талдамады. Әр түрлі шектеулі формалар 19-шы және 20-шы ғасырлардың басында бірнеше рет қайта ашылды.[2] ФФТ кейін танымал болды Джеймс Кули туралы IBM және Джон Туки туралы Принстон алгоритмді қайта ойлап тапқан және оны компьютерде қалай ыңғайлы түрде орындауға болатындығы туралы 1965 жылы мақала жариялады.[3]

Тукей бұл идеяны президент Кеннедидің ғылыми консультативті комитетінің анықтау тәсілдерін талқылауы кезінде айтқан болатын. ядролық қаруды сынау ішінде кеңес Одағы елден тыс орналасқан сейсмометрлерді пайдалану арқылы. Бұл датчиктер сейсмологиялық уақыт қатарын тудырады. Алайда, бұл деректерді талдау датчиктердің саны мен уақыт ұзақтығына байланысты DFT есептеудің жылдам алгоритмдерін қажет етеді. Бұл міндет ұсынылған ядролық сынақтарға тыйым салуды ратификациялау үшін өте маңызды болды, сондықтан кеңестік мекемелерге барудың қажеті жоқ кез-келген бұзушылықтар анықталуы мүмкін еді.[4][5] Осы кездесуге тағы бір қатысушы, Ричард Гарвин IBM компаниясы әдістің әлеуетін мойындады және Тукейді Кулимен байланыстырды, алайда Кули бастапқы мақсатын білмейтіндігіне сенімді болды. Оның орнына Кулиге бұл 3-D кристаллындағы спин бағдарларының периодтылығын анықтау үшін қажет деп айтты Гелий-3. Кули мен Туки кейіннен өздерінің бірлескен мақалаларын жариялады, және кеңінен қабылдау бір уақытта дамуына байланысты тез жүрді Аналогты-сандық түрлендіргіштер 300 кГц дейінгі жылдамдықпен сынама алуға қабілетті.

Гаусстың бірдей алгоритмді сипаттағаны (оның асимптотикалық құнын талдамай болса да) Кули мен Тукидің 1965 жылғы мақаласынан бірнеше жыл өткен соң ғана жүзеге асты.[2] Олардың қағаздары шабыт ретінде тек жұмысты келтірді I. J. Жақсы қазір деп аталатын нәрседе қарапайым фактор FFT алгоритмі (PFA);[3] Гуд алгоритмі бастапқыда Cooley-Tukey алгоритміне балама деп есептелгенімен, PFA мүлдем басқа алгоритм екендігі тез түсінілді (тек өлшемдері үшін жұмыс істейді) салыстырмалы түрде қарапайым факторларға тәуелді және Қытайлық қалдық теоремасы, Cooley-Tukey кез-келген композициялық өлшемді қолдауға қарағанда).[6]

Radix-2 DIT корпусы

A radix-2 уақытында бөлшектеу (DIT) FFT - бұл Cooley-Tukey алгоритмінің ең қарапайым және кең таралған түрі, дегенмен жоғары оңтайландырылған Cooley-Tukey іске асырулары алгоритмнің басқа формаларын төменде сипатталғандай пайдаланады. Radix-2 DIT мөлшері DFT бөледі N көлеміндегі екі DFT-ге (демек, «radix-2») N/ 2 әр рекурсивті кезеңмен.

Дискретті Фурье түрлендіруі (DFT) келесі формуламен анықталады:

қайда дейінгі бүтін сан болып табылады дейін .

Radix-2 DIT алдымен индекстелген кірістердің DFT-ін есептейдіжәне тақ индекстелген кірістер , содан кейін осы екі нәтижені біріктіріп, бүкіл тізбектегі DFT шығарады. Содан кейін бұл идеяны орындауға болады рекурсивті жалпы жұмыс уақытын O дейін азайту үшін (N журнал N). Бұл жеңілдетілген форма деп болжайды N Бұл екінің күші; таңдалған нүктелер санынан бастап N әдетте қолданба арқылы еркін таңдалуы мүмкін (мысалы, үлгінің жылдамдығын немесе терезесін, нөлдік төсеуді және т.б. өзгерту арқылы), бұл көбінесе маңызды шектеу емес.

Radix-2 DIT алгоритмі функцияның DFT-ін қайта реттейді екі бөлікке: жұп сандар бойынша қосынды және тақ индекстердің үстінен :

Жалпы көбейткішті факторға айналдыруға болады төмендегі теңдеуде көрсетілгендей екінші қосындыдан. Содан кейін екі қосынды тең индекстелген бөліктің DFT екендігі түсінікті және тақ индекстелген бөліктің DFT функциясы . DFT деп белгілеңіз Eиндекстелген кірістер арқылы және DFT Odd индекстелген кірістер арқылы және біз мыналарды аламыз:

Арқасында кешен экспоненциалының кезеңділігі, -дан алынған және :

Біз қайта жаза аламыз сияқты:

Бұл DFT ұзындығын білдіретін нәтиже N екі DFT өлшемі бойынша рекурсивті N/ 2, radix-2 DIT жылдам Фурье түрлендіруінің өзегі болып табылады. Алгоритм DFT бірнеше шығысын есептеу үшін аралық есептеу нәтижелерін қайта қолдану арқылы жылдамдыққа ие болады. Соңғы нәтижелер +/− тіркесімі арқылы алынатынын ескеріңіз және , бұл жай-2 DFT өлшемі (кейде а көбелек осы тұрғыда); бұл төмендегі үлкен радикалдарға жалпыланған кезде, өлшемі-2 DFT үлкен DFT-мен ауыстырылады (оны FFT көмегімен бағалауға болады).

Мәліметтер ағынының диаграммасы N= 8: уақыт радиусы-2 FFT бөлшектеу ұзындығын бұзады -N DFT екі ұзындыққаN/ 2 DFT, содан кейін «көбелек» операциялары деп аталатын көптеген өлшемді-2 DFT-лерден тұратын біріктіру кезеңі (мәліметтер ағынының диаграммасы формасына байланысты).

Бұл процесс жалпы техниканың мысалы болып табылады алгоритмдерді бөлу және бағындыру; көптеген дәстүрлі бағдарламаларда нақты рекурсияға жол берілмейді, ал оның орнына есептеу ағашынан өтеді ені - бірінші сән.

Жоғарыда көрсетілген өлшемді қайта өрнектеуN DFT екі өлшем ретіндеN/ 2 DFT кейде деп аталады ДаниэлсонЛанкзос лемма, өйткені бұл екі автор 1942 жылы атап өткен[7] (әсер еткен Рунге 1903 жұмыс[2]). Олар леммасын бірнеше рет «артқа» рекурсивті түрде қолданды екі еселенеді DFT өлшемі трансформация спектрі жинақталғанға дейін (бірақ олар оны түсінбесе керек) сызықтық арифмикалық [яғни, тапсырыс N журналN] олар қол жеткізген асимптотикалық күрделілік). Даниельсон-Ланчос жұмыстары бұрын қол жетімді болды механикалық немесе электрондық есептеуіш машиналар және қажет қолмен есептеу (мысалы, механикалық көмекші құралдармен болуы мүмкін) қосу машиналары ); олар жұмыс істеп тұрған 64 DFT өлшемі үшін 140 минутты есептеу уақыты туралы хабарлады нақты кірістер 3-5 маңызды цифрларға дейін. Кули мен Тукидің 1965 жылғы мақаласында 2048 өлшемді DFT кешені үшін 0,02 минуттық жұмыс уақыты көрсетілген. IBM 7094 (мүмкін 36-биттік) бір дәлдік, ~ 8 сан).[3] Уақытты операциялар санымен өлшейтін болсақ, бұл шамамен 800,000 жылдамдық коэффициентіне сәйкес келеді. (Қолды есептеу уақытын перспективаға қою үшін 64 өлшемі үшін 140 минут өзгермелі нүктелік операцияға орташа алғанда ең көп дегенде 16 секундқа сәйкес келеді, оның 20% көбейту).

Псевдокод

Жылы псевдокод, төмендегі процедураны жазуға болады:[8]

X0,...,N−1ditfft2(х, N, с):             DFT (x0, хс, х2с, ..., х(N-1)с):    егер N = 1 содан кейін        X0х0                                      тривиальды өлшем-1 DFT базалық жағдайы    басқа        X0,...,N/2−1ditfft2(х, N/2, 2с)             DFT (x0, х2с, х4с, ...)        XN/2,...,N−1ditfft2(х+ с, N/2, 2с)           DFT (xс, хс+2с, хс+4с, ...)        үшін к = 0-ден N/2−1 істеу                        екі жартыдағы DFT-ді толық DFT-ге біріктіру:            т ← Xк            Xк ← t + exp (−2πмен к/N) Xк+N/2            Xк+N/2 ← t - exp (−2π.)мен к/N) Xк+N/2        үшін аяқтау    егер аяқталса

Мұнда, ditfft2(х,N, 1), есептейді X= DFT (х) орынсыз radix-2 DIT FFT бойынша, мұндағы N бүтін дәрежесі 2 және с= 1 - қадам кіріс х массив. х+с массивін бастап бастайды хс.

(Нәтижелер дұрыс тәртіпте X және бұдан әрі ауыстыруды ауыстыру талап етіледі; Бит-реверстің жеке кезеңінің жиі айтылатын қажеттілігі тек төменде сипатталған кейбір алгоритмдер үшін туындайды.)

FFT жоғары өнімділігі осы алгоритмді іске асыруда осы қарапайым псевдокодпен салыстырғанда көптеген өзгертулер енгізеді. Мысалы, қарағанда үлкенірек корпусты қолдануға болады N= 1-ден амортизациялау рекурсияның үстеме шығысы, твит факторлары алдын-ала есептелуі мүмкін, және одан үлкен радикалдар жиі қолданылады кэш себептер; осы және басқа оңтайландырулар бірге өнімділікті немесе одан да көп деңгейге жақсарта алады.[8] (Көптеген оқулықтарда бірінші-тереңдік рекурсия толығымен рекурсивті емес пайдасына жойылады ені - бірінші тәсіл, дегенмен тереңдік-бірінші рекурсия жақсырақ деп тұжырымдалды есте сақтау қабілеті.[8][9]) Осы идеялардың кейбіреулері төменде толығырақ сипатталған.

Идея

Жалпы факторизациялау үшін Cooley-Tukey FFT-нің негізгі қадамы 1D DFT-ді 2d DFT сияқты қайта түсіндіру ретінде қарастырылуы мүмкін. Ұзындықтың 1-өлшемді жиымы N = N1N2 2д ретінде қайта түсіндіріледі N1×N2 матрица сақталған баған-бұйрық. Біреуі 1D DFT-ді бойлай орындайды N2 бағыт (сабақтас емес бағыт), содан кейін фазалық факторларға көбейтіледі (твайд факторлары), және соңында 1d DFT орындайды N1 бағыт. Транспозиция сатысы мұнда көрсетілгендей ортасында немесе басында немесе соңында орындалуы мүмкін. Бұл кішігірім түрлендірулер үшін рекурсивті түрде жасалады.
Негізгі және бағаналы ретті иллюстрациялау

Жалпы алғанда, Cooley-Tukey алгоритмдері композициялық өлшемдегі DFT-ді рекурсивті түрде қайта көрсетеді N = N1N2 сияқты:[10]

  1. Орындаңыз N1 DFT өлшемі N2.
  2. Кешен бойынша көбейтіңіз бірліктің тамыры (жиі деп аталады твит факторлары ).
  3. Орындаңыз N2 DFT өлшемі N1.

Әдетте, немесе N1 немесе N2 кішігірім фактор (емес міндетті түрде қарапайым), деп аталады радикс (бұл рекурсия кезеңдері арасында ерекшеленуі мүмкін). Егер N1 радиусы, ол а деп аталады уақытында жою (DIT) алгоритмі, егер болса N2 бұл радиус, ол жиіліктегі бөлшектеу (DIF, оны Сэнд-Тукей алгоритмі деп те атайды). Жоғарыда келтірілген нұсқа radix-2 DIT алгоритмі болды; соңғы өрнекте тақ түрлендіруді көбейту фазасы твиддел факторы және +/- тіркесімі (көбелек) жұп және тақ түрлендірулердің өлшемі-2 DFT. (Радикстің кішігірім DFT а ретінде белгілі көбелек, пішініне байланысты деп аталады берілгендер диаграммасы radix-2 корпусы үшін.)

Вариациялар

Cooley-Tukey алгоритмінде көптеген басқа нұсқалар бар. Аралас-радикс іске асырулар O-ны қолданатын екіге (әрдайым емес) әр түрлі (әдетте кішігірім) факторлардан тұратын композициялық өлшемдерді басқарадыN2) рекурсияның қарапайым жағдайларының алгоритмі (және N журналN сияқты қарапайым негізгі жағдайларға арналған алгоритм Радер немесе Блюстейн алгоритмі). Бөлінген радиус радиус 2-нің бірінші түрлендіруі екі өлшемнің қуаттылығы үшін ең аз арифметикалық операция санау ұзақтығына жету үшін екі рет айналу факторын қажет етпейтіндігін пайдаланып, 2 және 4 радикалдарын біріктіреді,[10] дегенмен, соңғы вариациялар санаудың төмен деңгейіне жетеді.[11][12] (Қазіргі компьютерлерде өнімділік көбірек анықталады кэш және CPU құбыры операцияларды қатаң санауға қарағанда ойлар; FFT-ді жақсы оңтайландырылған бағдарламалар көбінесе үлкен көлемдегі радикалдарды және / немесе қатты кодталған базалық корпусты түрлендірулерді қолданады.[13]).

Кули-Тукей алгоритмін қараудың тағы бір тәсілі - оның өлшемін қайта көрсетуі N бір өлшемді DFT ретінде N1 арқылы N2 екі өлшемді DFT (плюс жұмыртқалар), мұнда шығу матрицасы болады ауыстырылды. Осы транспозициялардың барлығының таза нәтижесі, radix-2 алгоритмі үшін, кіріс (DIF) немесе шығыс (DIT) индекстерінің сәл өзгеруіне сәйкес келеді. Егер кішігірім радиусты қолданудың орнына, шамамен бір радиус қолданылса N және нақты енгізу / шығару матрицасының транспозициясы, оны а деп атайды төрт сатылы алгоритм (немесе алты сатылы, транспозициялар санына байланысты), бастапқыда есте сақтау қабілетін жақсарту үшін ұсынылған,[14][15] мысалы кэшті оңтайландыру үшін немесе ядродан тыс кейінірек оңтайлы болып көрсетілді ескертусіз алгоритм.[16]

Жалпы Cooley-Tukey факторизациясы индекстерді қайта жазады к және n сияқты және сәйкесінше, онда индекстер ка және nа 0-ден басталады ..Nа-1 (үшін а 1 немесе 2). Яғни, бұл кірісті қайта индекстейді (n) және шығу (к) сияқты N1 арқылы N2 екі өлшемді массивтер майор және қатардағы негізгі тәртіп сәйкесінше; бұл индекстеу арасындағы айырмашылық жоғарыда айтылғандай транспозиция болып табылады. Бұл қайта индекстеу DFT формуласына ауыстырылған кезде nk, кросс-термин жоғалады (оның экспоненциалды бірлігі), ал қалған терминдер береді

.

мұндағы әрбір ішкі қосынды өлшем DFT болып табылады N2, әрбір сыртқы қосынды өлшем DFT болып табылады N1, ал [...] жақшалы термин - твидт факторы.

Ерікті радиус р (сонымен қатар аралас радикалдар) жұмыс істей алады, мұны Кули де, Туки де көрсетті[3] сонымен қатар Гаусс (radix-3 және radix-6 қадамдарына мысалдар келтірді).[2] Кули мен Туки бастапқыда радикс көбелегіне O (р2) жұмыс жасаңыз және радиус үшін күрделілікті есептеңіз р O болур2 N/р журналрN) = O (N журнал2(Nр/ журнал2р); мәндерін есептеп шығарудан р/ журнал2р бүтін мәндері үшін р 2-ден 12-ге дейін оңтайлы радиус 3-ке тең болады (ең жақын бүтін сан e, бұл азайтады р/ журнал2р).[3][17] Бұл талдау қате болды, дегенмен: радикс-көбелек сонымен қатар DFT болып табылады және оны FFT алгоритмі арқылы O (р журнал р) амалдар, демек радикс р шынымен O күрделілігінен бас тартады (р журнал (рN/р журналрN) және оңтайлы р неғұрлым күрделі ойлармен анықталады. Іс жүзінде өте үлкен р (32 немесе 64) тиімді пайдалану үшін маңызды. үлкен саны процессор регистрлері қазіргі заманғы процессорларда,[13] және тіпті шексіз радиус р=N сонымен қатар O (N журналN) күрделілігі және үлкен үшін теориялық және практикалық артықшылықтары бар N жоғарыда айтылғандай.[14][15][16]

Деректерді қайта ретке келтіру, разрядты өзгерту және орнында алгоритмдер

Жоғарыда келтірілген DFT-дің абсолютті Cooley-Tukey факторизациясы қандай-да бір түрде алгоритмнің барлық іске асырылуына қатысты болғанымен, FFT-нің әр кезеңінде деректерге тапсырыс беру және оларға қол жеткізу әдістемелерінде едәуір әртүрлілік бар. Анды құру проблемасы ерекше қызығушылық тудырады орнында алгоритм тек O (1) қосалқы сақтау орнын қолданып, оның шығыс деректерімен жазуды бастайды.

Қайта реттеудің ең танымал әдістемесі айқын болып табылады бит қалпына келтіру орнындағы radix-2 алгоритмдері үшін. Битті қайтару болып табылады ауыстыру мұндағы мәліметтер индекс бойынша n, жазылған екілік сандармен б4б3б2б1б0 (мысалы, 5 сан N= 32 кіріс), кері цифрлармен индекске ауыстырылады б0б1б2б3б4 . Радиx-2 DIT алгоритмінің жоғарыда көрсетілген алгоритмінің соңғы кезеңін қарастырыңыз, мұнда нәтиже кіріс орнына орнына жазылады: қашан және өлшемі-2 DFT-мен біріктірілген, бұл екі мән нәтижелермен жазылады. Дегенмен, екі шығыс мәні бірінші және екінші деңгейге өтуі керек жартысы сәйкес массивтің шығысы ең маңызды бит б4 (үшін N= 32); ал екі кіріс және тармағына сәйкес жұп және тақ элементтерде қабаттасады ең аз маңызды бит б0. Осылайша, өнімді дұрыс жерде алу үшін, б0 орын алу керек б4 және индекс болады б0б4б3б2б1. Келесі рекурсивті кезең үшін ең аз 4 бит болады б1б4б3б2, Егер сіз radix-2 DIT алгоритмінің барлық рекурсивті кезеңдерін қоссаңыз, барлық биттер өзгертілуі керек, сондықтан кірісті алдын-ала өңдеу керек (немесе кейіннен өңдеуден кейін) ретімен шығуды алу үшін сәл керісінше. (Егер әрбір өлшемN/ 2 субтрансформасы - бұл DIT-тің іргелес деректерімен жұмыс істеу енгізу сәйкесінше, егер сіз барлық қадамдарды кері тәртіпте орындайтын болсаңыз, онда кейін өңдеуден кейін (немесе сәйкесінше алдын ала өңдеуден) кейін биттің айналуымен radix-2 DIF алгоритмін аласыз.

Бұл алгоритмде қолданылатын логарифм (журнал) негіздік 2 логарифм болып табылады.

Төменде bit-reversal permutation қолдану арқылы жүзеге асырылатын итерациялық radix-2 FFT алгоритміне арналған псевдокод келтірілген.[18]

алгоритм қайталанатын-fft болып табылады    енгізу: Массив а туралы n күрделі мәндер, мұндағы n - 2 дәрежесі. шығу: Массив A а. ДФТ бит-кері-көшірме (а, А) nа.ұзындық үшін с = 1 дейін журнал (n) істеу        м ← 2с        ωм ← exp (−2π.)мен/м)         үшін к = 0 дейін n-1 арқылы м істеу            ω ← 1            үшін j = 0 дейін м/2 – 1 істеу                тω A[к + j + м/2]                сенA[к + j]                A[к + j] ← сен + т                A[к + j + м/2] ← сент                ωω ωм       қайту A

Бит-кері көшіру процедурасын келесідей жүзеге асыруға болады.

алгоритм бит-кері-көшірме (а,A) болып табылады    енгізу: Массив а туралы n күрделі мәндер, мұндағы n - 2 дәрежесі. шығу: Массив A өлшемі n.    nа.ұзындық үшін к = 0 дейін n – 1 істеу        A[rev (k)]: = а[k]

Сонымен қатар, кейбір қосымшалар (мысалы, конволюция) разрядталған мәліметтерде бірдей жақсы жұмыс істейді, сондықтан табиғи түрдегі түпкілікті нәтиже алу үшін тура түрлендірулер, өңдеулер, содан кейін кері түрлендірулер барлығын биттік айналдырусыз орындай алады.

Алайда көптеген FFT пайдаланушылары табиғи тәртіптегі шығуды қалайды, ал биттің нақты өзгеру кезеңі есептеу уақытына елеусіз әсер етуі мүмкін,[13] битті қалпына келтіруді O (N) уақыт және көптеген зерттеулердің тақырыбы болды.[19][20][21] Сонымен қатар, ауыстыру radix-2 жағдайында сәл өзгеріс болғанымен, жалпы радиадалған жағдай үшін ерікті (аралас-базалық) цифрлық реверсия болып табылады және ауыстыру алгоритмдерін жүзеге асыру күрделене түседі. Сонымен қатар, көптеген аппараттық архитектураларда FFT алгоритмінің аралық кезеңдерін ретімен (немесе, ең болмағанда, локализацияланған) деректер элементтерінде жұмыс істеуі үшін қайта тапсырыс берген жөн. Осы мақсатта Cooley-Tukey алгоритмі үшін биттің бөлек бұрылуын қажет етпейтін және / немесе аралық кезеңдерде қосымша ауыстыруды қажет ететін бірқатар баламалы схемалар ойлап табылды.

Егер бұл болса, мәселе айтарлықтай жеңілдетілген орынсыз: шығыс жиым кіріс жиымнан ерекшеленеді немесе оған тең өлшемді көмекші массив бар. The Стокхем автоматты сұрыптау алгоритм[22][23] ФФТ-нің әр кезеңін орынсыз орындайды, әдетте екі массив арасында алға-артқа жазады, әр сатыға индекстердің бір «цифрын» ауыстырады және әсіресе танымал болды SIMD сәулет.[23][24] SIMD үшін одан да үлкен әлеуетті артықшылықтар (бірізді қол жетімділік) ұсынылды Пиз алгоритм,[25] ол әр сатыда орын ауыстыруды реттейді, бірақ бұл әдіс бөлек биттік / цифрлық қалпына келтіруді және O (N журнал N) сақтау. Сонымен қатар, Cooley-Tukey факторизациясының анықтамасын нақты (бірінші-тереңдік ) жеке ауыстыру сатысы жоқ табиғи тәртіптегі өнімді шығаратын рекурсия және шағын радикалдар (жоғарыдағы псевдокодтағы сияқты) ескертусіз жүйелердегі жергілікті артықшылықтар иерархиялық жады.[9][13][26]

Көмекші сақтаусыз және бөлек цифрлық-бұрылыс өтулерсіз орнында алгоритмдердің типтік стратегиясы аралық кезеңдерде кіші матрицалық транспозицияларды (жеке жұп цифрларды ауыстырады) қамтиды, оларды радиус көбелектерімен біріктіру арқылы өту санын азайтуға болады. деректер.[13][27][28][29][30]

Әдебиеттер тізімі

  1. ^ Гаусс, Карл Фридрих (1876) [nd.]. Theoria Interpolationis Methodo Nova Tractata. Карл Фридрих Гаусс Верке. 3-топ. Геттинген: Königliche Gesellschaft der Wissenschaften. 265–327 беттер.
  2. ^ а б c г. e Хайдман, М.Т., Д.Х.Джонсон және C. S. Burrus, "Гаусс және жылдам Фурье түрленуінің тарихы, «IEEE ASSP журналы, 1, (4), 14–21 (1984)
  3. ^ а б c г. e Кули, Джеймс В .; Туки, Джон В. (1965). «Күрделі Фурье серияларын машиналық есептеу алгоритмі». Математика. Есептеу. 19 (90): 297–301. дои:10.2307/2003354. JSTOR  2003354.
  4. ^ Кули, Джеймс В .; Льюис, Питер А. В .; Уэлч, Питер Д. (1967). «Фурьенің жылдам түрленуі туралы тарихи жазбалар» (PDF). Аудио және электроакустика бойынша IEEE транзакциялары. 15 (2): 76–79. CiteSeerX  10.1.1.467.7209. дои:10.1109 / tau.1967.1161903.
  5. ^ Рокмор, Даниэль Н., Есептеу. Ғылыми. Eng. 2 (1), 60 (2000). FFT - бүкіл отбасы қолдана алатын алгоритм «Ғасырдың он алгоритмі» бойынша арнайы шығарылым«Мұрағатталған көшірме» (PDF). Архивтелген түпнұсқа (PDF) 2009-04-07. Алынған 2009-03-31.CS1 maint: тақырып ретінде мұрағатталған көшірме (сілтеме)
  6. ^ Джеймс В.Кули, Питер А.В.Льюис және Питер В.Велч, «Фурьедің жылдам түрленуі туралы тарихи жазбалар» Proc. IEEE, т. 55 (№ 10), б. 1675–1677 (1967).
  7. ^ Даниэлсон, Г.С. және Ч.Ланчос, «Фурьедегі практикалық анализдің кейбір жетілдірулері және оларды сұйықтықтардан рентгендік шашырауға қолдану» Дж. Франклин Инст. 233, 365–380 және 435–452 (1942).
  8. ^ а б c С.Г.Джонсон және М.Фриго »FFT-ді тәжірибеде енгізу, «in Фурье жылдам өзгереді (C. S. Burrus, ред.), Ш. 11, Райс университеті, Хьюстон TX: Коннекциялар, қыркүйек 2008 ж.
  9. ^ а б Синглтон, Ричард С. (1967). «Фурье түрлендіруінің жылдамдығын есептеу туралы». Коммун. ACM. 10 (10): 647–654. дои:10.1145/363717.363771. S2CID  6287781.
  10. ^ а б Дюамель, П., және М. Веттерли, «Жылдам Фурье түрлендірулері: оқулыққа шолу және қазіргі заманғы жағдай» Сигналды өңдеу 19, 259–299 (1990)
  11. ^ Ланди, Т. және Дж. Ван Бускирк, «Нақты ФФТ-ға жаңа матрицалық тәсіл және 2 ұзындықтағы консоляциялар.к," Есептеу 80, 23–45 (2007).
  12. ^ Джонсон, С.Г. және М.Фриго »Арифметикалық амалдары аз модификацияланған сплит-радикс FFT," IEEE Транс. Сигнал процесі. 55 (1), 111–119 (2007).
  13. ^ а б c г. e Фриго, М .; Джонсон, С.Г. (2005). «FFTW3 жобалау және енгізу» (PDF). IEEE материалдары. 93 (2): 216–231. CiteSeerX  10.1.1.66.3097. дои:10.1109 / JPROC.2004.840301. S2CID  6644892.
  14. ^ а б Джентльмен В.М. және Г.Санде, «Фурьенің жылдам өзгерістері - көңіл көтеру және пайда табу үшін» Proc. AFIPS 29, 563–578 (1966).
  15. ^ а б Бэйли, Дэвид Х., «сыртқы немесе иерархиялық жадыдағы ФФТ», Суперкомпьютер 4 (1), 23–35 (1990)
  16. ^ а б М.Фриго, С.Э.Лейзерсон, Х.Прокоп және С.Рамачандран. Кэшті ескермейтін алгоритмдер. Жылы IEEE 40-шы информатика негіздеріне арналған симпозиум материалдары (FOCS 99), s.285-297. 1999 ж. IEEE кеңейтілген реферат, Citeseer-де.
  17. ^ Кули, Дж. В., П. Льюис және П. Уэлч, «Фурьенің жылдам өзгеруі және оның қолданылуы», IEEE Trans on Education 12, 1, 28–34 (1969)
  18. ^ әл.], Томас Х.Кормен ... [et; Лейзерсон, Чарльз; Ривест, Рональд; Stein, Clifford (2009). Алгоритмдермен таныстыру (3-ші басылым). Кембридж, Массачусетс: MIT Press. 915–918 беттер. ISBN  978-0-262-03384-8.
  19. ^ Карп, Алан Х. (1996). «Унпроцессорлардағы реверсия». SIAM шолуы. 38 (1): 1–26. CiteSeerX  10.1.1.24.2913. дои:10.1137/1038001. JSTOR  2132972.
  20. ^ Картер, Ларри; Гатлин, Кан Су (1998). Орнын ауыстырудың оңтайлы ауыстыру бағдарламасына қарай. Proc. 39 анн. Симптом. Табылды. Комп. Ғылыми. (ФОКС). 544-553 бет. CiteSeerX  10.1.1.46.9319. дои:10.1109 / SFCS.1998.743505. ISBN  978-0-8186-9172-0. S2CID  14307262.
  21. ^ Рубио, М .; Гомес, П .; Друйче, К. (2002). «Жаңа жылдам жылдамдықты қалпына келтіру алгоритмі». Халықаралық J. Адаптивті басқару және сигналды өңдеу. 16 (10): 703–707. дои:10.1002 / акс.718.
  22. ^ Бастапқыда В.Т.Кохрандағы Стокхемге жатқызылған т.б., Фурье жылдам өзгерісі дегеніміз не?, Proc. IEEE т. 55, 1664–1674 (1967).
  23. ^ а б Сварцтраубер, Векторлық компьютерлерге арналған FFT алгоритмдері, Параллельді есептеу т. 1, 45-63 (1984).
  24. ^ Swarztrauber, P. N. (1982). «ФФТ-ларды векторизациялау». Родригеде Г. (ред.) Параллель есептеулер. Нью-Йорк: Academic Press. бет.51–83. ISBN  978-0-12-592101-5.
  25. ^ Pease, M. C. (1968). «Параллельді өңдеу үшін жылдам Фурье түрлендіруін бейімдеу». J. ACM. 15 (2): 252–264. дои:10.1145/321450.321457. S2CID  14610645.
  26. ^ Фриго, Маттео; Джонсон, Стивен Г. «FFTW». Тегін (GPL Cooley-Tukey алгоритмін қолдана отырып, ерікті өлшемдегі бір немесе бірнеше өлшемдегі дискретті Фурье түрлендірулерін есептеуге арналған C кітапханасы
  27. ^ Джонсон, Х. В .; Burrus, C. S. (1984). «Өз орнында орналасқан radix-2 FFT». Proc. ICASSP: 28A.2.1–28A.2.4.
  28. ^ Темпертон, C. (1991). «Фурье түріндегі түрлендіруді өздігінен сұрыптау». SIAM ғылыми және статистикалық есептеу журналы. 12 (4): 808–823. дои:10.1137/0912043.
  29. ^ Цянь, З .; Лу, С .; Ан, М .; Толимиери, Р. (1994). «Минималды жұмыс кеңістігімен FFT алгоритмін өздігінен сұрыптау». IEEE Транс. ASSP. 52 (10): 2835–2836. Бибкод:1994ITSP ... 42.2835Q. дои:10.1109/78.324749.
  30. ^ Хегланд, М. (1994). «Фурье түріндегі жылдам сұрыптау алгоритмі векторлық және параллельді өңдеу үшін қолайлы». Numerische Mathematik. 68 (4): 507–547. CiteSeerX  10.1.1.54.5659. дои:10.1007 / s002110050074. S2CID  121258187.

Сыртқы сілтемелер