Кіріспе
Жылдам Фурье түрлендіру алгоритмі
Брун алгоритмі – 1978 жылы Г. Брун ұсынған, екілік дәрежелерге негізделген және 1996 жылы Х. Мураками кез келген жұп құрамалы өлшемдерге жалпылаған, ерекше рекурсивті полиномдық факторлау тәсіліне негізделген жылдам Фурье түрлендіру (ЖФТ) алгоритмі. Оның операциялары соңғы есептеу сатысына дейін тек нақты коэффициенттерді қолданатындықтан, бастапқыда нақты деректердің дискретті Фурье түрлендірмесін (ДФТ) тиімді есептеу жолы ретінде ұсынылды. Брун алгоритмі кеңінен қолданылмады, себебі қарапайым Кули-Туки ЖФТ алгоритміне негізделген тәсілдер нақты деректерге кемінде сол деңгейде тиімді бейімделді. Сонымен қатар, Брун алгоритмі шектеулі сандық дәлдікте Кули-Туки алгоритмінен кем дәл болуы мүмкін екенін көрсететін деректер бар. Дегенмен, Брун алгоритмі өзінің және Кули-Туки алгоритмінің екеуін де бейнелей алатын балама алгоритмикалық құрылымды ұсынады, осылайша екі алгоритмнің және басқа да жалпыламалардың қосылуына мүмкіндік беретін ЖФТ-ге ерекше көзқарас ұсынады.
Bruun's algorithm is a fast Fourier transform (FFT) algorithm based on an unusual recursive polynomial factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996. Because its operations involve only real coefficients until the last computation stage, it was initially proposed as a way to efficiently compute the discrete Fourier transform (DFT) of real data. Bruun's algorithm has not seen widespread use, however, as approaches based on the ordinary Cooley–Tukey FFT algorithm have been successfully adapted to real data with at least as much efficiency. Furthermore, there is evidence that Bruun's algorithm may be intrinsically less accurate than Cooley–Tukey in the face of finite numerical precision
Nevertheless, Bruun's algorithm illustrates an alternative algorithmic framework that can express both itself and the Cooley–Tukey algorithm, and thus provides an interesting perspective on FFTs that permits mixtures of the two algorithms and other generalizations.
Кули-Туки көптік факторлау ретінде
Стандартты жиілік бойынша кеміту (DIF) радикс r Кули-Туки алгоритмі рекурсивті факторлаумен тығыз байланысты. Мысалы, радикс 2 DIF Кули-Туки факторлары және болып табылады. Бұл модульдік операциялар дәрежесін 2-ге төмендетеді, бұл проблеманың мөлшерін 2-ге бөлуге сәйкес келеді. Бірақ, тікелей рекурсивті факторлаудың орнына, Кули-Туки алдымен x2(z ωN) есептейді, барлық түбірлерді (бұрылыс коэффициентімен) ығыстырып, осылайша екі қосалқы мәселеге де рекурсивті факторлауды қолдана алады. Яғни, Кули-Туки барлық қосалқы мәселелердің де DFT екендігін қамтамасыз етеді, ал бұл кез келген рекурсивті факторлау үшін міндетті түрде дұрыс болмайды (мысалы, Bruun-дікі, төменде көрсетілгендей).
Кез келген түбірге жалпылау
Бруун факторлауы, демек Бруун FFT алгоритмі, кез келген жұп құрама ұзындықтарды өңдеуге бейімделді, яғни полином дәрежесін кез келген радикске (факторға) бөлуге мүмкіндік берді, мынадай түрде: Біріншіден, біз оң бүтін сандар N және α үшін φN,α(z) көпмүшелерінің жиынтығын былай анықтаймыз:
Ескеріңіз, жоғарыдағы Бруун факторлауында қолданылатын барлық көпмүшелерді осы түрде жазуға болады. Бұл көпмүшелердің нөлдері жағдайда және жағдайда тең. Сондықтан бұл көпмүшелерді фактор (радикс) r үшін рекурсивті түрде жіктеуге болады: