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

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

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

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

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

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

Проста швидка нерекурсивна реалізація перетворення Волша–Адамара випливає з розкладання матриці перетворення Адамара як $H_{m}=A^{m}$ , де A — корінь m -го числа $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

Див. також

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

Примітки

↑ Fino, B. J.; Algazi, V. R. (1976). Unified Matrix Treatment of the Fast Walsh–Hadamard Transform. IEEE Transactions on Computers. 25 (11): 1142—1146. doi:10.1109/TC.1976.1674569.
↑ Yarlagadda, R. K. Rao; Hershey, John E. (1997). Hadamard Matrix Analysis and Synthesis. Boston, MA: Springer US. doi:10.1007/978-1-4615-6313-6. ISBN 978-1-4613-7898-3.

Посилання

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

[1] Fino, B. J.; Algazi, V. R. (1976). Unified Matrix Treatment of the Fast Walsh–Hadamard Transform. IEEE Transactions on Computers. 25 (11): 1142—1146. doi:10.1109/TC.1976.1674569.

[2] Yarlagadda, R. K. Rao; Hershey, John E. (1997). Hadamard Matrix Analysis and Synthesis. Boston, MA: Springer US. doi:10.1007/978-1-4615-6313-6. ISBN 978-1-4613-7898-3.

[1]

[2]