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

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

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

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

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

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

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

Пример кода Python

def fwht(a) -> None:
    """In-place Fast Walsh–Hadamard Transform of array a."""
    h = 1
    while h < len(a):
        # perform 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
        # normalize and increment
        a /= math.sqrt(2)
        h *= 2

См. также

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

Ссылки

^ Фино, Би Джей; Альгази, В.Р. (1976). «Единая матричная обработка быстрого преобразования Уолша – Адамара». Транзакции IEEE на компьютерах . 25 (11): 1142–1146. дои : 10.1109/TC.1976.1674569 . S2CID 13252360 .
^ Ярлагадда и Херши, «Анализ и синтез матрицы Адамара», 1997 (Springer)

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

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

Эта обработке сигналов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[1] Фино, Би Джей; Альгази, В.Р. (1976). «Единая матричная обработка быстрого преобразования Уолша – Адамара». Транзакции IEEE на компьютерах . 25 (11): 1142–1146. дои : 10.1109/TC.1976.1674569 . S2CID 13252360 .

[2] Ярлагадда и Херши, «Анализ и синтез матрицы Адамара», 1997 (Springer)

[ 1 ]

[ 2 ]