Rychlá Walsh – Hadamardova transformace - Fast Walsh–Hadamard transform

Rychlá Walsh – Hadamardova transformace aplikovaná na vektor o délce 8

Příklad pro vstupní vektor (1, 0, 1, 0, 0, 1, 1, 0)

Ve výpočetní matematice Hadamard nařídil rychlou Walsh – Hadamardovu transformaci ( FWHT _h ) je účinný algoritmus pro výpočet Walsh – Hadamardovy transformace (WHT). Naivní implementace WHT řádu bude mít výpočetní složitost z O ( ) . FWHT _h vyžaduje pouze sčítání nebo odčítání. ${\ Displaystyle n = 2^{m}}$ ${\ displaystyle n^{2}}$ ${\ displaystyle n \ log n}$

FWHT _h je algoritmus rozděl a panuj, který rekurzivně rozděluje velikost WHT na dvě menší velikosti WHT . Tato implementace se řídí rekurzivní definicí Hadamardovy matice : ${\ 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}}.}

K normalizační faktory pro každou fázi mohou být seskupeny dohromady, nebo dokonce vynechat. ${\ displaystyle 1/{\ sqrt {2}}}$

Sequency uspořádaný , také známý jako Walsh-objednal, rychle Walsh-Hadamardova transformace, FWHT _w , se získá tím, že počítá FWHT _h jak je uvedeno výše, a pak se přeskupí výstupy.

Jednoduchá rychlá nerekurzivní implementace Walsh – Hadamardovy transformace vyplývá z rozkladu Hadamardovy transformační matice jako , kde A je m -tý kořen . ${\ displaystyle H_ {m} = A^{m}}$ ${\ displaystyle H_ {m}}$

Příklad kódu v Pythonu

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