Что такое быстрое преобразование. В чем заключается идея БМП (Быстрого Преобразования Фурье)

В тетради лекций БПФ описывается только формулами, так что обращусь к сторонним источникам.

Это алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем , требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность .

Т.е. это один из алгоритмов преобразования аналогового сигнала, который представлен в виде какой-либо функции, в дискретный ряд. Если говорить, то это 2 лабораторная, представление бесконечного сигнала в виде конечного числа отсчётов этой функции.

		0 1 2 3 4 5 6 7 8...

Где первый столбец это индексы входного сигнала, на выходе соответственно выходные индексы.

Шаги:

· Преобразование для каждого столбца

· Все получившиеся результаты умножаем на константу

· Затем построчно вычисляем значение Фурье

Дик говорил про " хитрость" со скобками при вычислениях, что и используется для улучшения алгоритма.

Дискретное преобразование Фурье преобразует набор чисел в набор чисел , такой, что , где и при .

Чаще всего этот алгоритм применяют к полю комплексных чисел (c ) и кольцам вычетов.

Основной шаг алгоритма состоит в сведении задачи для чисел к задаче для числам, где — делитель . Пусть мы уже умеем решать задачу для чисел. Применим преобразование Фурье к наборам для .

Заметим, что . Выражения в скобках нам уже известны — это -тое число после преобразования Фурье -той группы.

Преобразование Фурье —функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.

Преобразование Фурье функции вещественной переменной является интегральным и задаётся следующей формулой:

-------------------------------------------------------------------------------------------------------------------------------