Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Что такое быстрое преобразование. В чем заключается идея БМП (Быстрого Преобразования Фурье)
В тетради лекций БПФ описывается только формулами, так что обращусь к сторонним источникам.
Это алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем , требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность .
Т.е. это один из алгоритмов преобразования аналогового сигнала, который представлен в виде какой-либо функции, в дискретный ряд. Если говорить, то это 2 лабораторная, представление бесконечного сигнала в виде конечного числа отсчётов этой функции.
Где первый столбец это индексы входного сигнала, на выходе соответственно выходные индексы.
Шаги: · Преобразование для каждого столбца · Все получившиеся результаты умножаем на константу · Затем построчно вычисляем значение Фурье Дик говорил про " хитрость" со скобками при вычислениях, что и используется для улучшения алгоритма.
Дискретное преобразование Фурье преобразует набор чисел в набор чисел , такой, что , где и при . Чаще всего этот алгоритм применяют к полю комплексных чисел (c ) и кольцам вычетов. Основной шаг алгоритма состоит в сведении задачи для чисел к задаче для числам, где — делитель . Пусть мы уже умеем решать задачу для чисел. Применим преобразование Фурье к наборам для . Заметим, что . Выражения в скобках нам уже известны — это -тое число после преобразования Фурье -той группы. Преобразование Фурье —функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Преобразование Фурье функции вещественной переменной является интегральным и задаётся следующей формулой: -------------------------------------------------------------------------------------------------------------------------------
|