Швидке перетворення Волша–Адамара

Швидке перетворення Волша–Адамара, застосоване до вектора довжини 8

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

Швидке перетворення Волша–Адамара (ШПВА) — це ефективний алгоритм для обчислення перетворення Волша–Адамара (ПВА). Наївна реалізація ПВА порядку $n=2^m$ матиме обчислювальну складність O($n^2$) . ШПВА вимагає лише $n\log n$ додавань або віднімань.

ШПВА — це алгоритм типу «розділяй і володарюй», який рекурсивно розбиває ПВА розміру $n$ на два менших ПВА розміром $n/2$. Ця реалізація відповідає рекурсивному визначенню матриці Адамара $H_m$ розміром $2^m\times 2^m$:

$H_m=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{H}_{m-1}& H_{m-1}\\ H_{m-1}& -H_{m-1}\end{array}\right).$

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

Шаблон:Li, також відоме як упорядковане за Волшем ШПВА, отримується шляхом обчислення ШПВА_, як зазначено вище, з наступним перегруповуванням виходів.

Проста швидка нерекурсивна реалізація перетворення Волша–Адамара випливає з розкладання матриці перетворення Адамара як $H_m=A^m$, де A — корінь m -го числа $H_m$.

Приклад коду Python

import math
def fwht(a) -> None:
    """In-place Fast Walsh–Hadamard Transform of array a."""
    assert math.log2(len(a)).is_integer(), "length of a is a power of 2"
    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

Див. також

• Швидке перетворення Фур'є

Посилання

• Charles Constantine Gumas, A century old, the fast Hadamard transform proves useful in digital communications