8.9. Быстрое преобразование Адамара

Как отмечалось в разделе 6.4, матрица ядра Адамара

Поэтому алгоритм быстрого преобразования Адамара может быть легко получен на основе алгоритма БПФ₂, если из него удалить операцию умножения на матрицу D поворачивающих элементов. На основании этого из выражения (3.10) можно получить:

(8.26)

где, как и в (8.10) l = 2^m-1, k = (n)_{mod l}, n - текущий индекс вектора ().

Иначе говоря, “бабочка” в таком алгоритме имеет вид как это показано на рис.8.9

Рис.8.9. Бабочка алгоритма быстрого преобразования Адамара, где

Такая же точно “бабочка”, как и представленная на рис.7.7, служит основой алгоритмов быстрого преобразования Пэли и Уолша, отличие которых состоит лишь в упорядочении исходных данных перед первой итерацией (см. раздел 6.2).

Граф быстрого алгоритма Уолша – Пэли для N = 16 приведен на рис.8.10.

Сложность же алгоритма быстрых ортогональных преобразований Уолша - Адамара в числе Б0 алгоритма Q_БПФ и Q_БПХ для , однако сложность самой базовой операции значительно меньше и составит только 2 операции сложения, что значительно меньше чем для алгоритма БПХ (не говоря уже о БПФ). Поэтому можно записать, что:

.

Рис.8.10. Граф алгоритма быстрого преобразования Адамара-Уолша для N=16

Быстрые алгоритмы БДОП Адамара-Уолша являются «обратимыми», т.е. вычисления по графу (см., например, рис.8.10) могут выполняться как «слева направо», так и «справа налево» [6].

Заметим, что для алгоритма БДОП с прореживанием по частоте не выполняется двоично-инверсная перестановка элементов вектора X перед первой итерацией, но зато необходимо переставлять элементы векторов результата по закону двоичной инверсии.

На рис. 8.11 представлен граф быстрого преобразования Хаара. Нетрудно видеть, что он является частично вырожденным по отношению к графу БДОП Адамара-Уолша.

Сам алгоритм быстрого преобразования Хаара (за исключением итоговой нормировки) будет описываться выражением (7.26), за тем лишь исключением, что при обработке каждого блока данных выполняется только первая базовая операция (k=0) Для БП Хаара сложность отдельной базовой операции такая же, как и у БПУ. Однако общее число базовых операций меньше, чем в алгоритмах БПХ и БПУ, и составляет всего Q = (2N-1) БО.

Рис.8.11. Граф быстрого преобразования Хаара для N =16.