|
Читайте также: |
Сколько операций требуется на проведение дискретного преобразования Фурье? Посчитав по определению (N раз суммировать N слагаемых), получаем величину порядка N 2. Тем не менее, можно обойтись существенно меньшим числом операций.
Способ, при помощи которого ДПФ вычисляется за Nlog2 N операций чем-то неуловимо напоминает быструю сортировку. В ходе этого способа также проводится рекурсивное разбиение массива чисел на два подмассива и сведение вычисления ДПФ от целого массива к вычислению ДПФ от подмассив в отдельности. Этот способ носит название быстрого преобразования Фурье (БПФ). В деталях он рассмотрен в описании соответствующего исходника
Изобретение БПФ привело к потрясающему всплеску популярности преобразования Фурье. Целый ряд важных задач раньше решался за время порядка N 2, но после проведения преобразования Фурье над исходными данными (за время порядка Nlog2 N) решается практически мгновенно. Преобразование Фурье лежит в основе цифровых корелляторов и методов свертки, активно используется при спектральном анализе (практически в чистом виде), применяется при работе с длинными числами.
Единственным (и существеннейшим) ограничением БПФ является то, что оно работает только с наборами данных, длина которых является степенью двойки. Впрочем, существуют модификации, которые частично обходят это ограничение, но общий алгоритм, который решает задачу вычисления ДПФ на наборе произвольной длины за время порядка Nlog2 N, так и не найден.
Дата добавления: 2015-07-19; просмотров: 111 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Дискретное преобразование Фурье | | | ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ |