Преобразование Уолша – Адамара

Преобразова́ние Уо́лша – Адама́ра порядка ${\displaystyle m,}$ умножает вектор-столбец высоты ${\displaystyle n=2^{m}}$ на ${\displaystyle 2^{m}\times 2^{m}}$ матрицу ${\displaystyle H_{m},}$ заданную рекуррентной формулой: ${\displaystyle H_{0}=\|1\|}$ и при ${\displaystyle m>0}$

${\displaystyle H_{m}={\begin{Vmatrix}H_{m-1}&H_{m-1}\mathbb {H} _{m-1}&-H_{m-1}\end{Vmatrix}}}$.

Опубликованный в 1932 г. быстрый алгоритм этого преобразования требует проведения ${\displaystyle O(n\,\log _{2}n)}$ сложений и вычитаний исходных данных и может рассматриваться как предтеча алгоритма быстрого преобразования Фурье Кули – Тьюки для ${\displaystyle n=2^{m}}$.

Преобразование Уолша – Адамара является частным случаем многомерного дискретного преобразования Фурье для ${\displaystyle n_{1}=n_{2}=\ldots =n_{m}=2}$. Это преобразование является ортогональным (скалярные произведения различных строк или различных столбцов матрицы ${\displaystyle H_{m}}$ равны нулю) и используется в обработке сигналов, в частности в современной аппаратуре и алгоритмах сотовой связи.

В литературе встречается и нормированный вариант определения, использующий формулу

${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{Vmatrix}H_{m-1}&H_{m-1}\mathbb {H} _{m-1}&-H_{m-1}\end{Vmatrix}}}$.

Этот вариант удобен тем, что при его использовании все строки (или столбцы) матрицы ${\displaystyle H_{m}}$ имеют длину ${\displaystyle 1}$ и образуют ортонормированный базис.