Швидке перетворення Волша–Адамара (ШПВА) — це ефективний алгоритм для обчислення перетворення Волша–Адамара (ПВА). Наївна реалізація ПВА порядку матиме обчислювальну складність O() . ШПВА вимагає лише додавань або віднімань.
ШПВА — це алгоритм типу «розділяй і володарюй», який рекурсивно розбиває ПВА розміру на два менших ПВА розміром . Ця реалізація відповідає рекурсивному визначенню матриці Адамара розміром :
Коефіцієнти нормалізації для кожного етапу можуть бути згруповані разом або навіть пропущені.
, також відоме як упорядковане за Волшем ШПВА, отримується шляхом обчислення ШПВА, як зазначено вище, з наступним перегруповуванням виходів.
Проста швидка нерекурсивна реалізація перетворення Волша–Адамара випливає з розкладання матриці перетворення Адамара як , де A — корінь 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