6.5. Быстрое преобразование Уолша—Адамара, упорядоченное по Уолшу

Быстрое преобразование Уолша — Адамара с упорядочением по Уолшу представляет собой алгоритм для вычисления с помощью сложения и вычитания без умножения на множитель в уравнении (6.4.1). При этом можно сначала вычислить коэффициенты . Соответственно коэффициенты можно получить, пользуясь соотношением (6.4.4). Однако при таком подходе требуется переход от кода Грея к двоичному коду, а также двоичная инверсия, и поэтому он не является достаточно эффективным. Эндрюс и Пратт предложили алгоритм, который отличается от алгоритма Кули — Тьюки [8] и может быть осуществлен за операций сложения и вычитания.

В этом разделе рассматривается алгоритм БПУА с упорядочением по Уолшу, предложенный Манцем [9]. В этом алгоритме используется граф типа Кули — Тьюки, а сам алгоритм осуществляется за операций сложения и вычитания. Этот алгоритм по существу является простой модификацией БПУА с упорядочением по Адамару и наиболее просто может быть проиллюстрирован при . Для удобства граф БПУА с упорядочением по Адамару , изображенный на рис. 6.2, повторяется на рис. 6.3. Первый шаг алгоритма заключается в двоичной инверсии входной последовательности и расположении ее в порядке возрастания двоично-инвертированных индексов. Если обозначает входную последовательность, то двоично-инвертированная последовательность с возрастающими индексами будет обозначаться как . Второй шаг заключается в определении «инверсии», которая наилучшим образом может быть проиллюстрирована с помощью простого примера, изображенного на рис. 6.4. Обычно, т. е. без инверсии) граф преобразования строится следующим образом:

(6.5.1)

С учетом инверсии граф преобразования строится следующим образом:

(6.5.2)

Рис. 6.3. Граф БПУА с упорядочением по Адамару при N (штрих-пунктирные линии разделяют отдельные блоки)

Рис. 6.4. Влияние инверсии на структуру графа

Как следует из (6.5.1) и (6.5.2), инверсия приводит к замене сложений в данной итерации графа преобразования на вычитания и наоборот.

Третий шаг заключается в определении «блока». Блок определяется как группа сложений и вычитаний, которая не связана с соседними группами, расположенными как выше, так и ниже. На рис. 6.3 блоки обозначены штрих-пунктиром. Например, итерация имеет блок; итерация 2 имеет 2 блока и т. д. В общем случае итерация имеет блоков.

Наконец, приведем правила формирования блоков для алгоритма БПУА с упорядочением по Уолшу с учетом инверсии сложений и вычитаний.

Правило 1. В итерации инверсия не применяется. Правило 2. Если обозначить через , блоки в итерации, то тогда блоки с инверсией располагаются, как показано ниже, где R обозначает инверсию

т. е. каждый второй блок, начиная с блока , претерпевает инверсию. На рис. 6.5 показан порядок инверсии при , а соответствующий граф БПУА с упорядочением по Уолшу , приведен на рис. 6.6. В общем случае БПУА с упорядочением по Уолшу имеет граф с итерациями.

Рис. 6.5. Схема расположения блоков в графе БПУА с упорядочением по Уолшу при (И — блок с инверсией; ДИП — двоично-инвертированный порядок)

Пример 6.5.1. Требуется найти ПУА с упорядочением по Уолшу с помощью БПУА для последовательности .

Решение. Пусть — последовательность, полученная в результате двоичной инверсии , тогда

Рис. 6.6. Граф БПУА с упорядочением по Уолшу при

Подставляя и в граф, изображенный на рис. 6.6, получаем

Таким образом,

Полученные значения совпадают со значениями, полученными в примере 6.4.1 в результате матричного умножения.