Описание
Программа предназначается для вычисления быстрой свертки сигналов с использованием алгоритмов БПФ (схема Кули-Тьюки), Тума-Кука, Винограда, Хартли (Быстрое преобразование Хартли – БПХ) и Уолша-Адамара (Быстрое преобразование Уолша-Адамара – БПУ). Вычисление свёртки требует O(N2) операций. Это количество может быть существенно уменьшено с помощью вычисления свёртки различными быстрыми алгоритмами.
Программа предназначается для вычисления быстрой свертки сигналов с использованием алгоритмов БПФ (схема Кули-Тьюки), Тума-Кука, Винограда, Хартли (Быстрое преобразование Хартли – БПХ) и Уолша-Адамара (Быстрое преобразование Уолша-Адамара – БПУ).
Вычисление свёртки требует O(N2) операций. Это количество может быть существенно уменьшено с помощью вычисления свёртки различными быстрыми алгоритмами.
Чаще всего для уменьшения количества операций свёртка вычисляется с помощью двух преобразований Фурье, каждое из которых рассчитывается с помощью быстрых алгоритмов. Это позволяет снизить вычислительную сложность операции свёртки до O(NlogN).
Использование алгоритмов Тума-Кука и Винограда позволяет достигнуть вычислительной сложности O(N).
Сложность БПХ совпадает со сложностью БПФ (асимптотически) и равняется NlogN с точностью до константы 0.5 (только вещественные числа).
Сложность БПУ совпадает со сложностью БПФ (асимптотически) и равняется NlogN (без умножителей).
Если вы обнаружили ошибку, пожалуйста, уведомите нас — выделите текст с ошибкой и нажмите клавиши Ctrl+Enter. Отключите блокировщик рекламы, если после нажатия комбинации кнопок не срабатывает всплывающее окно.
