В вычислительной математике упорядоченное быстрое преобразование Уолша-Адамара ( FWHT h ) является эффективным алгоритмом для вычисления преобразования Уолша-Адамара (WHT). Наивная реализация WHT порядкабудет иметь вычислительную сложность из O () . Для FWHT h требуется только сложения или вычитания.
FWHT h - это алгоритм «разделяй и властвуй», который рекурсивно разбивает WHT размера на два WHT меньшего размера . [1] Эта реализация следует рекурсивному определению Матрица Адамара :
В Коэффициенты нормализации для каждого этапа могут быть сгруппированы вместе или даже опущены.
Последовательные этапы заказали , также известный как приказано Уолша, быстрое преобразование Уолша-Адамара, FWHT ж , получается путем вычисления FWHT ч , как указано выше, и затем перегруппировки выходы.
Простая быстрая нерекурсивная реализация преобразования Уолша-Адамара следует из разложения матрицы преобразования Адамара как , где A - корень m-й степени из . [2]
Пример кода Python
def fwht ( a ) -> None : "" "Быстрое преобразование Уолша – Адамара на месте массива a." "" h = 1, а h < len ( a ): для i в диапазоне ( 0 , len ( a ), h * 2 ): для j в диапазоне ( i , i + h ): x = a [ j ] y = a [ j + h ] a [ j ] = x + y a [ j + h ] = x - y h * = 2
Смотрите также
Рекомендации
- ^ Fino, BJ; Альгази, В.Р. (1976). "Единая матричная трактовка быстрого преобразования Уолша-Адамара". Транзакции IEEE на компьютерах . 25 (11): 1142–1146. DOI : 10.1109 / TC.1976.1674569 .
- ^ Ярлагадда и Херши, "Анализ и синтез матрицы Адамара", 1997 (Springer)
Внешние ссылки
- Чарльз Константин Гумас, столетней давности быстрое преобразование Адамара оказалось полезным в цифровых коммуникациях