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

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

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

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

ШПВА — це алгоритм типу «розділяй і володарюй», який рекурсивно розбиває ПВА розміру ${\displaystyle n}$ на два менших ПВА розміром ${\displaystyle n/2}$.^[1] Ця реалізація відповідає рекурсивному визначенню матриці Адамара ${\displaystyle H_{m}}$ розміром ${\displaystyle 2^{m}\times 2^{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}}}$ для кожного етапу можуть бути згруповані разом або навіть пропущені.

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

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

Приклад коду 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

Див. також

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