Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Быстрое преобразование Фурье

Ориентация кусочно-гладких поверхностей | Формула Гаусса-Остроградского | Формула Стокса | Доказательство. | Формулы Эйлера | Билет 51 | Ряды Фурье для чётных и нечётных функций. Ряд Фурье для функции периода 2l | Билет 53 | Билет 54 | Свойства непрерывного преобразования Фурье |


Читайте также:
  1. Быстрое начало
  2. Быстрое начало
  3. Быстрое питание
  4. Быстрое чтение
  5. Быстрое, либо длительное
  6. Дискретное преобразование Фурье

Сколько операций требуется на проведение дискретного преобразования Фурье? Посчитав по определению (N раз суммировать N слагаемых), получаем величину порядка N 2. Тем не менее, можно обойтись существенно меньшим числом операций.

Способ, при помощи которого ДПФ вычисляется за Nlog2 N операций чем-то неуловимо напоминает быструю сортировку. В ходе этого способа также проводится рекурсивное разбиение массива чисел на два подмассива и сведение вычисления ДПФ от целого массива к вычислению ДПФ от подмассив в отдельности. Этот способ носит название быстрого преобразования Фурье (БПФ). В деталях он рассмотрен в описании соответствующего исходника

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

Единственным (и существеннейшим) ограничением БПФ является то, что оно работает только с наборами данных, длина которых является степенью двойки. Впрочем, существуют модификации, которые частично обходят это ограничение, но общий алгоритм, который решает задачу вычисления ДПФ на наборе произвольной длины за время порядка Nlog2 N, так и не найден.

 

 


Дата добавления: 2015-07-19; просмотров: 111 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Дискретное преобразование Фурье| ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

mybiblioteka.su - 2015-2024 год. (0.006 сек.)