Участник:Ivanov.kir.m/Быстрое дискретное преобразование Фурье: различия между версиями
Перейти к навигации
Перейти к поиску
Нет описания правки |
Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Быстрое преобразование Фурье (БПФ, FFT)''' — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем <math>O(N^{2})</math>, требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность <math>O(N\log(N))</math>. | |||
= ЧАСТЬ. Свойства и структура алгоритмов = | = ЧАСТЬ. Свойства и структура алгоритмов = | ||
| Строка 46: | Строка 47: | ||
= Литература = | = Литература = | ||
[1] Википедия [Электронный ресурс]. Тема: Быстрое преобразование Фурье – Электрон. дан. – URL [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье] (дата обращения 17.09.2016) | |||
[[en:Fast Discrete Fourier Transform]] | [[en:Fast Discrete Fourier Transform]] | ||
Версия от 10:01, 17 сентября 2016
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем [math]\displaystyle{ O(N^{2}) }[/math], требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность [math]\displaystyle{ O(N\log(N)) }[/math].
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
ЧАСТЬ. Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Динамические характеристики и эффективность реализации алгоритма
Существующие реализации алгоритма
Литература
[1] Википедия [Электронный ресурс]. Тема: Быстрое преобразование Фурье – Электрон. дан. – URL Быстрое преобразование Фурье (дата обращения 17.09.2016)