6.3. Быстрое преобразование Уолша-Адамара, упорядоченное по Адамару (БПУА)

Напомним, что БПФ является алгоритмом для эффективного вычисления ДПФ. Подобным же образом БПУА с упорядочением по Адамару является алгоритмом для эффективного вычисления ПУА. Быстрое преобразование Уолша — Адамара с упорядочением по Адамару можно получить либо с помощью факторизации матриц [5, 6], либо с помощью разбиения матриц [7]. Рассмотрим вывод алгоритма с помощью разбиения матриц для случая . При формула (6.2.3) записывается как

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

(6.3.1)

Из разбиения матрицы, приведенного в (6.3.2), следует, что

и

(6.3.3б)

где

Последовательность сложений и вычитаний в и (6.3.3б) показана на примере графа БПУА, приведенного на рис. 6.2, где она обозначена как итерация .

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

Вновь применяя (6.1.6) к формулам и (6.3.3б), получаем

и

(6.3.4б)

Из разбиения матрицы, приведенного в и (6.3.4б), получаем следующие выражения:

(6.3.5б)

Последовательность сложений и вычитаний в и (6.3.5б) показана на примере графа БПУА и обозначена как итерация (рис. 6.2). Так как

,

то эти формулы приводят к

(6.3.6)

Последовательность сложений и вычитаний в (6.3.6) обозначена как итерация (см. рис. 6.2). Из графа БПУА с упорядочением по Адамару следует, что для его осуществления, за исключением нормировки с помощью множителя , требуются только сложения и вычитания. Число сложений и вычитаний, необходимое для вычисления восьми коэффициентов , равняется .

Обобщения. Обобщения БПУА с упорядочением по Адамару могут быть получены непосредственно. Общая структура графа БПУА для любого такая же, как и у графа, изображенного на рис. 6.2. Следует сделать замечания для общего случая .

1. Общее число итераций равно . Индекс итерации принимает значения .

2. В итерации участвует групп по элементов в каждой группе. Половина элементов в каждой группе связана с операцией сложения, а другая половина — с операцией вычитания.

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

4. Алгоритм БПУА можно применять для вычисления обратного преобразования Уолша — Адамара по формуле (6.2.4).

Пример 6.3.1. Пусть дана последовательность . Пользуясь БПУА с упорядочением по Адамару, вычислить коэффициенты ПУА .

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

Следовательно,

Частости, связанные с коэффициентами ПУА с упорядочением по Адамару. С помощью двоичной инверсии можно получить частость, связанную с данными . Начнем с (5.4.9), из которого следует, что

(6.3.7)

где — результат двоичной инверсии соответствует переходу от кода Грея к двоичному представлению , и — дискретные значения функций Уолша упорядоченных по Адамару и Уолшу соответственно.

Объединяя выражения (5.4.2) и (6.3.7), получаем частость, связанную с коэффициентом ПУА, упорядоченным по Адамару:

(6.3.8)

Для иллюстрации результаты вычисления, соответствующие выражению (6.3.8) и полученные для , сведены в табл. 6.3.1.

Таблица 6.3.1. Частости, связанные с коэффициентами ПУА при упорядочении по Адамару