Быстрое преобразование Уолша-Адамара

Быстрое преобразование Уолша–Адамара, примененное к вектору длиной 8

Алгоритм «разделяй и властвуй» для вычисления преобразования Адамара

Пример для входного вектора (1, 0, 1, 0, 0, 1, 1, 0)

В вычислительной математике преобразование Уолша–Адамара, упорядоченное по Адамару ( FWHT _h ), является эффективным алгоритмом для вычисления преобразования Уолша–Адамара (WHT). Наивная реализация WHT порядка имела бы вычислительную сложность O ( ) . FWHT _h требует только сложений или вычитаний. ${\displaystyle n=2^{m}}$ ${\displaystyle n^{2}}$ ${\displaystyle n\log n}$

FWHT _h — это алгоритм «разделяй и властвуй» , который рекурсивно разбивает WHT размером на два меньших WHT размером . ^[1] Эта реализация следует рекурсивному определению матрицы Адамара : ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle 2^{m}\times 2^{m}}$ ${\displaystyle H_{m}}$

${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}$

Коэффициенты нормализации для каждого этапа могут быть сгруппированы или даже опущены. ${\displaystyle 1/{\sqrt {2}}}$

Упорядоченное по последовательности , также известное как упорядоченное по Уолшу, быстрое преобразование Уолша–Адамара, FWHT _w , получается путем вычисления FWHT _h, как указано выше, и последующей перестановки выходных данных.

Простая быстрая нерекурсивная реализация преобразования Уолша–Адамара следует из разложения матрицы преобразования Адамара как , где A — корень степени m из . ^[2] ${\displaystyle H_{m}=A^{m}}$ ${\displaystyle H_{m}}$

Пример кода Python

def  fwht ( a )  ->  None : """Быстрое преобразование Уолша–Адамара на месте для массива a.""" h = 1 while h < len ( a ): # выполнить FWHT for i in range ( 0 , len ( a ), h * 2 ): for j in range ( i , i + h ): x = a [ j ] y = a [ j + h ] a [ j ] = x + y a [ j + h ] = x - y # нормализовать и увеличить a /= math . sqrt ( 2 ) h *= 2                                                   

Смотрите также

• Быстрое преобразование Фурье

Ссылки

1. Fino, BJ; Algazi, VR (1976). «Единая матричная обработка быстрого преобразования Уолша–Адамара». IEEE Transactions on Computers . 25 (11): 1142–1146. doi :10.1109/TC.1976.1674569. S2CID  13252360.
2. Ярлагадда и Херши, «Анализ и синтез матрицы Адамара», 1997 (Springer)

Внешние ссылки

• Чарльз Константин Гумас, Быстрое преобразование Адамара, которому уже сто лет, оказывается полезным в цифровых коммуникациях