Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Глава 8. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯМинуя древа молодые, По грубой треснувшей земле Скакал он на коне галопом К подножию холма. И лишь внизу коню дал отдых И сам был цел и невредим. А. Б. (Банджо) Патерсон. Человек со снежной реки Мы убедились в том, что может быть определено вещественное дискретное преобразование по аналогии с дискретным преобразованием Фурье; теперь мы покажем, что имеется быстрый метод вычислений, аналогичный быстрому преобразованию Фурье. Как было показано выше при рассмотрении факторизации матриц, данная процедура представляет собой простой способ перехода от дискретного преобразования Хартли к дискретному преобразованию Фурье. Следовательно, анализируемая ниже процедура быстрого преобразования также создает основу быстрого метода получения дискретного преобразования Фурье. Действительно, метод, предусматривающий переход от преобразования Хартли, оказывается предпочтительным, в основном в силу упрощения, обусловленного тем, что при обработке вещественных данных не требуются операции с комплексными величинами. Определяющие соотношенияКогда раскрывается знак суммирования, фигурирующий в определении дискретного преобразования Хартли, мы получаем N равенств, в правой части каждого из которых имеется N слагаемых. Четыре равенства, приведенные в предыдущей главе с целью иллюстрации сказанного, применительно к дискретному преобразованию Хартли
можно переписать в виде
Для N = 2 имеем только два равенства
Рис. 8.1. График функции При
В правильности значений соответствующих коэффициентов можно убедиться, анализируя график функции При
Можно рассчитать число онераций умножения и сложения и использовать результаты этого расчета для оценки временных затрат, необходимых для вычисления всех N значений преобразования.
|
1 |
Оглавление
|