Глава 8. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ

Минуя древа молодые,

По грубой треснувшей земле Скакал он на коне галопом К подножию холма.

И лишь внизу коню дал отдых И сам был цел и невредим.

А. Б. (Банджо) Патерсон. Человек со снежной реки

Мы убедились в том, что может быть определено вещественное дискретное преобразование по аналогии с дискретным преобразованием Фурье; теперь мы покажем, что имеется быстрый метод вычислений, аналогичный быстрому преобразованию Фурье. Как было показано выше при рассмотрении факторизации матриц, данная процедура представляет собой простой способ перехода от дискретного преобразования Хартли к дискретному преобразованию Фурье. Следовательно, анализируемая ниже процедура быстрого преобразования также создает основу быстрого метода получения дискретного преобразования Фурье. Действительно, метод, предусматривающий переход от преобразования Хартли, оказывается предпочтительным, в основном в силу упрощения, обусловленного тем, что при обработке вещественных данных не требуются операции с комплексными величинами.

Определяющие соотношения

Когда раскрывается знак суммирования, фигурирующий в определении дискретного преобразования Хартли, мы получаем N равенств, в правой части каждого из которых имеется N слагаемых. Четыре равенства, приведенные в предыдущей главе с целью иллюстрации сказанного, применительно к дискретному преобразованию Хартли

можно переписать в виде

Для N = 2 имеем только два равенства

Рис. 8.1. График функции по которому могут быть определены коэффициенты Для используются символы Для случая значения этих коэффициентов соответствуют точкам на графике, обозначенным символами Случай в дополнение к этим символам обозначен простыми точками.

При выполняя подстановку численных значений для четырех вышеприведенных равенств получим выражения

В правильности значений соответствующих коэффициентов можно убедиться, анализируя график функции (рис. 8.1) и отмечая точки, равноудаленные друг от друга на четверть периода этой функции, крестиками в кружочке.

При соответствующие равенства для ДПХ, в чем можно убедиться при анализе рис. 8.1, имеют вид

Можно рассчитать число онераций умножения и сложения и использовать результаты этого расчета для оценки временных затрат, необходимых для вычисления всех N значений преобразования.