Преобразование Адамара

Преобразование Адамара (также преобразование Уолша — Адамара, преобразование Уолша) — это ортогональное, симметричное, инволютивное линейное преобразование, широко используемое в области обработки сигналов, теории сжатия данных (например, в JPEG XR и стандартах видеокодирования H.264 и H.265), комбинаторике и квантовых вычислениях. Оно может рассматриваться как обобщение дискретного преобразования Фурье (ДПФ), где вместо комплексных экспонент (синусов и косинусов) в качестве базисных функций используются функции Уолша — прямоугольные волны, принимающие значения ${\displaystyle +1}$ и ${\displaystyle -1}$. Названо в честь французского математика Жака Адамара и американского математика Джозефа Л. Уолша.

Определение

Дискретное преобразование Адамара

Дискретное преобразование Адамара (ДПА) порядка ${\displaystyle N}$ (где ${\displaystyle N}$ — степень двойки: ${\displaystyle N=2^{n}}$) линейно выражает любой вектор ${\displaystyle x}$ размерности ${\displaystyle N}$ через базис, состоящий из функций Уолша.

Преобразование задается матрицей Адамара ${\displaystyle H_{N}}$ размера ${\displaystyle N\cdot N}$. Матрица Адамара строится рекуррентно:

• Базис: ${\displaystyle H_{1}}$ = [1]

• Рекуррентное построение: Для любого натурального n матрица Адамара порядка 2^n определяется через матрицу Адамара порядка ${\displaystyle 2^{n-1}}$ с помощью тензорного (кронекеровского) произведения: ${\displaystyle H_{2^{n}}=H_{2}\otimes H_{2^{n-1}}={\begin{bmatrix}H_{2^{n-1}}&H_{2^{n-1}}\\H_{2^{n-1}}&-H_{2^{n-1}}\end{bmatrix}}}$

Таким образом, матрицы Адамара низших порядков имеют вид:
${\displaystyle H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$
${\displaystyle H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}}$

Строки и столбцы этих матриц ортогональны и нормированы. Матрица Адамара является симметричной ${\displaystyle (H_{N}=H_{N}^{T})}$ и унитарной (с точностью до нормирующего множителя): ${\displaystyle H_{N}\cdot H_{N}^{T}=N\cdot I_{N}}$, где ${\displaystyle I_{N}}$ — единичная матрица.

Прямое и обратное преобразование Адамара для вектора ${\displaystyle x}$ определяются следующим образом:

• Прямое преобразование: ${\displaystyle {\hat {x}}=H_{N}\cdot x}$

• Обратное преобразование: ${\displaystyle x={\frac {1}{N}}H_{N}\cdot {\hat {x}}}$

Обратное преобразование возможно именно благодаря свойству инволютивности (с точностью до константы): применение преобразования дважды к исходному сигналу дает сам сигнал, умноженный на ${\displaystyle N}$.

Быстрое преобразование Адамара

Аналогично быстрому преобразованию Фурье (БПФ), существует алгоритм быстрого преобразования Адамара (БПА), который позволяет вычислить преобразование за время ${\displaystyle O(N\log N)}$. Алгоритм использует рекуррентную структуру матрицы Адамара, разбивая преобразование размера ${\displaystyle N}$ на два преобразования размера ${\displaystyle N/2}$, что приводит к "бабочке вычислений", похожей на схему БПФ, но без использования комплексных чисел и операций умножения. Это делает БПА чрезвычайно эффективным с вычислительной точки зрения.

Свойства

Ортогональность и унитарность: Матрица Адамара является ортогональной и унитарной (с точностью до константы ${\displaystyle {\sqrt {N}}).}$

Симметричность: ${\displaystyle H_{N}=H_{N}^{T}.}$

Инволютивность: ${\displaystyle H_{N}^{-1}={\frac {1}{N}}H_{N}}$. Применение преобразования дважды дает: ${\displaystyle H_{N}(H_{N}\cdot x)=N\cdot x}$.

Простота вычислений: Не требует операций умножения, только сложение и вычитание. Это ключевое преимущество перед ДПФ.

Базисные функции: Базисные функции (строки матрицы ${\displaystyle H_{N}}$) — это функции Уолша, которые являются естественным представлением для двоично-кодированных сигналов.

Применения

Обработка и сжатие сигналов и изображений

Преобразование Адамара используется как упрощенная и быстрая альтернатива преобразованию Фурье или дискретному косинусному преобразованию (ДКП) в тех случаях, когда вычислительная сложность критична. Оно эффективно для декорреляции сигналов и используется в:

• Стандартах видеокодирования: H.264/AVC, H.265/HEVC и других, где малые блоки (например, 4x4) преобразуются с помощью целочисленного ДКП или преобразования, очень близкого к Адамару.

• Стандарте сжатия изображений JPEG XR (HD Photo).

• Спектральном анализе сигналов, принимающих два значения.

Комбинаторика и теория кодирования

Матрицы Адамара являются центральным объектом в комбинаторике. Они используются при построении кодов с исправлением ошибок, например, в кодах Рида — Мюллера.

Квантовые вычисления

В квантовых вычислениях преобразование Адамара является одной из фундаментальных операций над кубитами. Вращение Адамара (или гейт Адамара) — это квантовый логический вентиль, который создает равновероятную суперпозицию состояний для одного кубита:

• ${\displaystyle H|0\rangle ={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}}$
• ${\displaystyle H|1\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

Матрица этого преобразования точно соответствует матрице ${\displaystyle H_{2}}$, деленной на ${\displaystyle {\sqrt {2}}}$ для обеспечения унитарности. Гейт Адамара является ключевым элементом во многих квантовых алгоритмах, включая алгоритм Дойча — Йожи и алгоритм Шора.

Сравнение с преобразованием Уолша

Часто термины «преобразование Адамара» и «преобразование Уолша» используются как синонимы, что является допустимым, поскольку они используют один и тот же набор базисных функций. Однако между ними существует техническое различие, заключающееся в порядке следования этих функций.

• Порядок Адамара: Строки в матрице ${\displaystyle H_{N}}$ упорядочены по частоте Адамара (количеству переходов знака в строке). Первая строка имеет частоту ${\displaystyle 0}$, вторая — ${\displaystyle 1}$, третья — ${\displaystyle 2}$ и так далее. Этот порядок является естественным следствием рекуррентного построения матрицы.

• Порядок Уолша (Пели): Функции упорядочены по частоте Уолша (числу нулей), но без учета рекуррентной структуры Адамара. Этот порядок также называют порядком Пели.

Таким образом, преобразование Адамара — это конкретный вид преобразования Уолша с определенным порядком базисных функций. Для большинства практических приложений (сжатие, обработка) это различие не является критичным, так как вся информация в коэффициентах сохраняется, просто их расположение отличается.

Пример вычисления

Рассмотрим прямое преобразование Адамара для вектора ${\displaystyle x=[a,b]^{T}}$.

Умножим его на матрицу ${\displaystyle H_{2}}$: ${\displaystyle {\hat {x}}=H_{2}\cdot x={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}a+b\\a-b\end{bmatrix}}}$

Коэффициенты ${\displaystyle (a+b)}$ и ${\displaystyle (a-b)}$ представляют собой проекции исходного вектора на базисные функции Адамара.

Восстановим исходный сигнал с помощью обратного преобразования: ${\displaystyle x={\frac {1}{2}}H_{2}\cdot {\hat {x}}={\frac {1}{2}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}a+b\\a-b\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}(a+b)+(a-b)\\(a+b)-(a-b)\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}2a\\2b\end{bmatrix}}={\begin{bmatrix}a\\b\end{bmatrix}}}$ Что и требовалось получить.

Применение в квантовых вычислениях (подробнее)

Гейт Адамара (H) является одним из фундаментальных вентилей в квантовых вычислениях. Его действие на базисные состояния кубита |0⟩ и |1⟩ выглядит следующим образом:

• ${\displaystyle H|0\rangle ={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}=|+\rangle }$
• ${\displaystyle H|1\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2}}}=|-\rangle }$

Это преобразование переводит кубит из классического состояния (|0⟩ или |1⟩) в состояние равновероятной суперпозиции, где оба базисных состояния равновероятны при измерении. Это свойство лежит в основе многих квантовых алгоритмов, позволяя квантовому компьютеру обрабатывать множество возможных входных данных одновременно (квантовый параллелизм).

• Алгоритм Дойча — Йожи: Гейт Адамара используется на входе для создания суперпозиции всех возможных входных данных и на выходе для интерференции результатов, которая позволяет извлечь глобальную информацию о функции.

• Алгоритм Гровера (поиска): Гейты Адамара используются для создания равномерной суперпозиции всех состояний в начале алгоритма и для операций инверсии относительно среднего, которые усиливают амплитуду вероятности нужного состояния.

• Квантовое преобразование Фурье: Является обобщением гейта Адамара на многокубитные системы.

См. также

• Матрица Адамара

• Функции Уолша

• Дискретное преобразование Фурье

• Дискретное косинусное преобразование

• Алгоритм Гровера

• Алгоритм Дойча — Йожи

Литература

Монографии и учебники

• Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша: теория и применения. — М.: Наука, 1987. — 360 с. — ISBN 5-02-014050-4.
  Классическая монография, посвящённая теоретическим основам и применениям преобразований Уолша и Адамара.

• Beauchamp K. G. Walsh Functions and Their Applications. — London: Academic Press, 1975. — 240 p. — ISBN 0-12-084350-5.
  Подробное описание свойств функций Уолша и их применений в обработке сигналов.

• Нильсен М. А., Чанг И. Л. Квантовые вычисления и квантовая информация. — М.: Мир, 2006. — 824 с. — ISBN 5-03-003524-9.
  Содержит разделы, посвящённые использованию преобразования Адамара в квантовых алгоритмах.

Научные статьи

• Prabha K., Sam I. S. Optimal blind colour image watermarking based on adaptive chaotic grasshopper optimization algorithm // The Imaging Science Journal. — 2022. — Vol. 70, № 4. — P. 215–230. — DOI: 10.1080/13682199.2022.2086715.
  Исследование применения преобразования Адамара в методах "водной" маркировки изображений.

• Saraiva A. A., Castro F. M. J., Melo R. T. Electroencephalography applied compression algorithms qualitative analysis // Computer Methods in Biomechanics and Biomedical Engineering: Imaging & Visualization. — 2020. — Vol. 8, № 5. — P. 512–520. — DOI: 10.1080/21681163.2020.1750316.
  Сравнение эффективности быстрого преобразования Адамара (FWHT) и быстрого преобразования Фурье (FFT) в обработке сигналов ЭЭГ.

• Rao K. K., Swamy K. V. Multimodal medical image fusion using residual network 50 in non subsampled contourlet transform // The Imaging Science Journal. — 2023. — Vol. 71, № 3. — P. 180–195. — DOI: 10.1080/13682199.2023.2175698.
  Анализ использования преобразования Адамара в fusion медицинских изображений.

Дополнительная литература

• Ahmed N., Rao K. R. Orthogonal Transforms for Digital Signal Processing. — Berlin: Springer-Verlag, 1975. — 280 p. — ISBN 3-540-06556-3.
  Содержит подробное описание ортогональных преобразований, включая преобразование Адамара.

• Fino B. J., Algazi V. R. Unified Matrix Treatment of the Fast Walsh-Hadamard Transform // IEEE Transactions on Computers. — 1976. — Vol. C-25, № 11. — P. 1142–1146. — DOI: 10.1109/TC.1976.1674569.
  Статья о быстрых алгоритмах вычисления преобразования Уолша—Адамара.

• Shanks J. L. Computation of the Fast Walsh-Fourier Transform // IEEE Transactions on Computers. — 1969. — Vol. C-18, № 5. — P. 457–459. — DOI: 10.1109/TC.1969.222795.
  Один из первых трудов, посвящённых быстрому вычислению преобразования Уолша—Фурье.

• Трахтман А. М., Трахтман В. А. Основы теории дискретных сигналов на конечных интервалах. — М.: Советское радио, 1975. — 208 с.
  Книга посвящена теоретическим аспектам дискретных сигналов, включая преобразование Адамара.

Ссылки

• Walsh-Hadamard Transform (Microsoft Docs)