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

Инволютивное изменение базиса в линейной алгебре произведение булевой функции и матрица Уолша - это ее:. (1, 0, 1, 0, 0, 1, 1, 0) × H (8) = (4, 2, 0, −2, 0, 2, 0, 2) Быстрое преобразование Уолша – Адамара, более быстрый способ вычисления спектра Уолша (1, 0, 1, 0, 0, 1, 1, 0). Исходная функция может быть выражена с помощью ее спектра Уолша в виде арифметического полинома.

Преобразование Адамара (также известное как преобразование Уолша – Адамара, Адамара– Преобразование Радемахера – Уолша, преобразование Уолша или преобразование Уолша – Фурье ) является примером обобщенного класса преобразований Фурье. Он выполняет ортогональную, симметричную, инволютивную, линейную операцию с 2 действительными числами (или комплексные или гиперкомплексные числа, хотя сами матрицы Адамара являются чисто действительными).

Преобразование Адамара можно рассматривать как построенное из дискретных преобразований Фурье размера 2 (ДПФ), и фактически оно эквивалентно многомерному ДПФ размером 2 × 2 × ⋯ × 2 × 2. Он разлагает произвольный входной вектор на суперпозицию функций Уолша.

Преобразование названо в честь французского математика Жака Адамара, немецко-американский математик Ганс Радемахер и американский математик Джозеф Л. Уолш.

• 1 Определение
• 2 Вычислительная сложность
• 3 Приложения квантовых вычислений
  • 3.1 Операции ворот Адамара
• 4 Приложения молекулярной филогенетики (эволюционной биологии)
• 5 Другие приложения
• 6 См. Также
• 7 Внешние ссылки
• 8 Ссылки

Преобразование Адамара H m - это матрица 2 × 2, матрица Адамара (масштабированная с помощью коэффициента нормализации), которая преобразует 2 действительных числа x n в 2 действительных числа X k. Преобразование Адамара можно определить двумя способами: рекурсивно или с помощью двоичного (base -2) представления индексов n и k.

Рекурсивно, мы определяем преобразование Адамара 1 × 1 H 0 с помощью тождества H0= 1, а затем определяем H m для m>0 по:

$H\; m\; =\; 1\; 2\; (H\; m\; -\; 1\; H\; m\; -\; 1\; H\; m\; -\; 1\; -\; H\; m\; -\; 1)\; \{\backslash \; displaystyle\; H\_\; \{m\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\}\; \}\}\; \{\backslash \; begin\; \{pmatrix\}\; H\_\; \{m-1\}\; H\_\; \{m-1\}\; \backslash \backslash \; H\_\; \{m-1\}\; -\; H\_\; \{m-1\}\; \backslash \; end\; \{pmatrix\}\}\}$

где 1 / √2 - нормализация, которая иногда опускается.

Для m>1 мы также можем определить H m следующим образом:

$H\; m\; =\; H\; 1\; \otimes \; H\; m\; -\; 1\; \{\backslash \; displaystyle\; H\_\; \{m\}\; =\; H\_\; \{1\}\; \backslash \; otimes\; H\_\; \{m-1\}\}$

, где $\otimes \; \{\backslash \; displaystyle\; \backslash \; otimes\}$представляет произведение Кронекера. Таким образом, за исключением этого коэффициента нормализации, матрицы Адамара полностью состоят из 1 и -1.

Аналогично, мы можем определить матрицу Адамара ее (k, n) -м элементом, записав

$k\; =\; \sum \; i\; =\; 0\; m\; -\; 1\; ki\; 2\; i\; =\; km\; -\; 1\; 2\; m\; -\; 1\; +\; км\; -\; 2\; 2\; м\; -\; 2\; +\; \cdots \; +\; k\; 1\; 2\; +\; k\; 0\; n\; =\; \sum \; i\; =\; 0\; m\; -\; 1\; ni\; 2\; i\; =\; nm\; -\; 1\; 2\; m\; -\; 1\; +\; nm\; -\; 2\; 2\; m\; -\; 2\; +\; \cdots \; +\; n\; 1\; 2\; +\; N\; 0\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{выровнено\}\; k\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{m-1\}\; \{k\_\; \{i\}\; 2\; ^\; \{i\}\}\; =\; k\_\; \{m-1\}\; 2\; ^\; \{m\; -1\}\; +\; k\_\; \{m-2\}\; 2\; ^\; \{m-2\}\; +\; \backslash \; cdots\; +\; k\_\; \{1\}\; 2\; +\; k\_\; \{0\}\; \backslash \backslash \; n\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{m-1\}\; \{\; n\_\; \{i\}\; 2\; ^\; \{i\}\}\; =\; n\_\; \{m-1\}\; 2\; ^\; \{m-1\}\; +\; n\_\; \{m-2\}\; 2\; ^\; \{m-2\}\; +\; \backslash \; cdots\; +\; n\_\; \{1\}\; 2\; +\; n\_\; \{\; 0\}\; \backslash \; end\; \{align\}\}\}$

где k j и n j - это двоичные цифры (0 или 1) для k и n соответственно. Обратите внимание, что для элемента в верхнем левом углу мы определяем: $k\; =\; n\; =\; 0\; \{\backslash \; displaystyle\; k\; =\; n\; =\; 0\}$. В этом случае имеем:

$(ЧАС\; м)\; k,\; n\; =\; 1\; 2\; м\; 2\; (-\; 1)\; \sum \; jkjnj\; \{\backslash \; displaystyle\; \backslash \; left\; (H\_\; \{m\}\; \backslash \; right)\; \_\; \{k,\; n\}\; =\; \{\backslash \; frac\; \{1\}\; \{2\; ^\; \{\backslash \; frac\; \{m\}\; \{2\}\}\}\}\; (-\; 1)\; ^\; \{\backslash \; sum\; \_\; \{j\}\; k\_\; \{j\}\; n\_\; \{j\}\}\}$

Это как раз многомерный $2\; \times \; 2\; \times \; \cdots \; \times \; 2\; \times \; 2\; \{\backslash \; Displaystyle\; \backslash \; scriptstyle\; 2\; \backslash ,\; \backslash \; times\; \backslash ,\; 2\; \backslash ,\; \backslash \; times\; \backslash ,\; \backslash \; cdots\; \backslash ,\; \backslash \; times\; \backslash ,\; 2\; \backslash ,\; \backslash \; times\; \backslash ,\; 2\}$ДПФ, нормализованное до унитарного, если входы и выходы рассматриваются как многомерные массивы, индексированные n j и k j соответственно.

Далее следуют некоторые примеры матриц Адамара.

$H 0 = + (1) H 1 = 1 2 (1 1 1 - 1) H 2 = 1 2 (1 1 1 1 1 - 1 1 - 1 1 1 - 1 - 1 1 - 1 - 1 1) H 3 = 1 2 3 2 (1 1 1 1 1 1 1 1 1 - 1 1 - 1 1 - 1 1 - 1 1 1 - 1 - 1 1 1 - 1 - 1 1 - 1 - 1 1 1 - 1 - 1 1 1 1 1 1 - 1 - 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1 1 1 1 - 1 - 1 - 1 - 1 1 1 1 - 1 - 1 1 - 1 1 1 - 1) (ЧАС N) я, J знак равно 1 2 N 2 (- 1) я ⋅ J {\ Displaystyle {\ begin {align} H_ {0} = + {\ begin {pmatrix} {\ begin {array} { r} 1 \ end {array}} \ end {pmatrix}} \\ H_ {1} = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} {\ begin {array} { rr} 1 1 \\ 1 -1 \ end {array}} \ end {pmatrix}} \\ H_ {2} = {\ frac {1} {2}} {\ begin {pmatrix} {\ begin {array} {rrrr} 1 1 1 1 \\ 1 -1 1 -1 \\ 1 1 -1 -1 \\ 1 -1 -1 1 \ end {array}} \ end {pmatrix}} \\ H_ {3} = {\ frac {1} {2 ^ {\ frac {3} {2}}}} {\ begin {pmatrix} {\ begin {array} {rrrrrrrr} 1 1 1 1 1 1 1 1 1 1 \\ 1 -1 1 -1 1 -1 1 -1 \\ 1 1 -1 -1 -1 1 1 -1 -1 \\ 1 -1 -1 1 1 -1 -1 1 \\ 1 1 1 1 -1 -1 -1 -1 \\ 1 -1 1 -1 -1 1 -1 1 \\ 1 1 -1 -1 -1 -1 1 1 \\ 1 -1 -1 1 -1 1 1 -1 \ end {array}} \ end {pmatrix}} \\\ left (H_ {n} \ right) _ {i, j} = {\ frac {1} {2 ^ { \ frac {n} {2}}}} (- 1) ^ {i \ cdot j} \ end {align}}}$

где $i\; \cdot \; j\; \{\backslash \; displaystyle\; i\; \backslash \; cdot\; j\}$- побитовое скалярное произведение двоичных представлений чисел i и j. Например, если $n\; \ge \; 2\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; n\; \backslash ;\; \backslash \; geq\; \backslash ;\; 2\}$, то $(H\; n)\; 3,\; 2\; =\; (-\; 1)\; 3\; \cdot \; 2\; Знак\; равно\; (-\; 1)\; (1,\; 1)\; \cdot \; (1,\; 0)\; =\; (-\; 1)\; 1\; +\; 0\; =\; (-\; 1)\; 1\; =\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \backslash \; left\; (H\_\; \{n\}\; \backslash \; right)\; \_\; \{\; 3,2\}\; \backslash ;\; =\; \backslash ;\; (-\; 1)\; ^\; \{3\; \backslash \; cdot\; 2\}\; \backslash ;\; =\; \backslash ;\; (-\; 1)\; ^\; \{(1,1)\; \backslash \; cdot\; (1,0)\}\; \backslash ;\; =\; \backslash ;\; (\; -1)\; ^\; \{1\; +\; 0\}\; \backslash ;\; =\; \backslash ;\; (-\; 1)\; ^\; \{1\}\; \backslash ;\; =\; \backslash ;\; -\; 1\}$, согласившись с вышеизложенным (игнорируя общую константу). Обратите внимание, что первая строка, первый элемент столбца матрицы обозначается $(H\; n)\; 0,\; 0\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \backslash \; left\; (H\_\; \{n\}\; \backslash \; right)\; \_\; \{0,0\}\}$.

H1это именно ДПФ размера 2. Его также можно рассматривать как преобразование Фурье на двухэлементной аддитивной группе Z / (2).

Строки матриц Адамара - это функции Уолша.

В классической области преобразование Адамара может быть вычислено за $n\; log\; \; n\; \{\; \backslash \; displaystyle\; n\; \backslash \; log\; n\}$операций ($n\; =\; 2\; m\; \{\backslash \; displaystyle\; n\; =\; 2\; ^\; \{m\}\}$) с использованием быстрого преобразования Адамара алгоритм.

В квантовой области преобразование Адамара может быть вычислено за $O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$времени, поскольку это квантовая логика вентиль, который можно распараллелить.

В квантовой обработке информации преобразование Адамара, которое в данном случае чаще называют вентилем Адамара контекст (см. квантовый вентиль ), является одним кубитом вращением, отображающим базисные состояния кубита $|\; 0⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle\}$и $|\; 1⟩\; \{\backslash \; displaystyle\; |\; 1\; \backslash \; rangle\}$в два состояния суперпозиции с равным весом вычислительного базисного состояний $|\; 0⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle\}$и $|\; 1⟩\; \{\backslash \; displaystyle\; |\; 1\; \backslash \; rangle\}$. Обычно фазы выбираются так, чтобы

$H\; =\; |\; 0⟩\; +\; |\; 1⟩\; 2\; ⟨0\; |\; +\; |\; 0⟩\; -\; |\; 1⟩\; 2\; ⟨1\; |\; \{\backslash \; displaystyle\; H\; =\; \{\backslash \; frac\; \{|\; 0\; \backslash \; rangle\; +\; |\; 1\; \backslash \; rangle\}\; \{\backslash \; sqrt\; \{2\}\}\}\; \backslash \; langle\; 0\; |\; +\; \{\backslash \; frac\; \{|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle\}\; \{\backslash \; sqrt\; \{\; 2\}\}\}\; \backslash \; langle\; 1\; |\}$

в нотации Дирака. Это соответствует матрице преобразования

$H\; 1\; =\; 1\; 2\; (1\; 1\; 1\; -\; 1)\; \{\backslash \; displaystyle\; H\_\; \{1\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\}\}\}\; \{\backslash \; begin\; \{\; pmatrix\}\; 1\; 1\; \backslash \backslash \; 1\; -1\; \backslash \; end\; \{pmatrix\}\}\}$

в $|\; 0⟩,\; |\; 1⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle,\; |\; 1\; \backslash \; rangle\}$основа, также известная как. Состояния $|\; 0⟩\; +\; |\; 1⟩\; 2\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{\backslash \; left\; |\; 0\; \backslash \; right\; \backslash \; rangle\; +\; \backslash \; left\; |\; 1\; \backslash \; right\; \backslash \; rangle\}\; \{\backslash \; sqrt\; \{2\}\}\}\}$и $|\; 0⟩\; -\; |\; 1⟩\; 2\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{\backslash \; left\; |\; 0\; \backslash \; right\; \backslash \; rangle\; -\; \backslash \; left\; |\; 1\; \backslash \; right\; \backslash \; rangle\}\; \{\backslash \; sqrt\; \{2\}\}\}\}$известны как $|\; +⟩\; \{\backslash \; Displaystyle\; \backslash \; left\; |\; \{\backslash \; boldsymbol\; \{+\}\}\; \backslash \; right\; \backslash \; rangle\}$и $|\; -⟩\; \{\backslash \; displaystyle\; \backslash \; left\; |\; \{\backslash \; boldsymbol\; \{-\}\}\; \backslash \; right\; \backslash \; rangle\}$соответственно, и вместе они составляют in квантовые вычисления.

многие квантовые алгоритмы используйте преобразование Адамара в качестве начального шага, поскольку оно отображает m кубитов, инициализированных с помощью $|\; 0⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle\}$к суперпозиции всех двух ортогональных состояний в $|\; 0⟩,\; |\; 1⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle,\; |\; 1\; \backslash \; rangle\}$на основе равного веса.

Примечательно, что вычисление квантового преобразования Адамара представляет собой простое применение логического элемента Адамара к каждому кубиту индивидуально из-за структуры тензорного произведения преобразования Адамара. Этот простой результат означает, что квантовое преобразование Адамара требует log n операций по сравнению с классическим случаем n log n операций.

Операции вентилей Адамара

$H (| 0⟩) ​​= 1 2 | 0⟩ + 1 2 | 1⟩ =: | +⟩ H (| 1⟩) = 1 2 | 0⟩ - 1 2 | 1⟩ =: | -⟩ H (1 2 | 0⟩ + 1 2 | 1⟩) = 1 2 (| 0⟩ + | 1⟩) + 1 2 (| 0⟩ - | 1⟩) = | 0⟩ H (1 2 | 0⟩ - 1 2 | 1⟩) = 1 2 (| 0⟩ + | 1⟩) - 1 2 (| 0⟩ - | 1⟩) = | 1⟩ {\ displaystyle {\ begin {align} H (| 0 \ rangle) = {\ frac {1} {\ sqrt {2}}} | 0 \ rangle + {\ frac {1} {\ sqrt {2 }}} | 1 \ rangle =: | + \ rangle \\ H (| 1 \ rangle) = {\ frac {1} {\ sqrt {2}}} | 0 \ rangle - {\ frac {1} { \ sqrt {2}}} | 1 \ rangle =: | - \ rangle \\ H \ left ({\ frac {1} {\ sqrt {2}}} | 0 \ rangle + {\ frac {1} {\ sqrt {2}}} | 1 \ rangle \ right) = {\ frac {1} {2}} {\ Big (} | 0 \ rangle + | 1 \ rangle {\ Big)} + {\ frac {1 } {2}} {\ Big (} | 0 \ rangle - | 1 \ rangle {\ Big)} = | 0 \ rangle \\ H \ left ({\ frac {1} {\ sqrt {2}}} | 0 \ rangle - {\ frac {1} {\ sqrt {2}}} | 1 \ rangle \ right) = {\ frac {1} {2}} {\ Big (} | 0 \ rangle + | 1 \ rangle {\ Big)} - {\ frac {1} {2}} {\ Big (} | 0 \ rangle - | 1 \ rangle {\ Big)} = | 1 \ rangle \ end {align}}}$

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

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

Механика филогенетического преобразования Адамара включает вычисление вектора $\gamma \; (T)\; \{\backslash \; displaystyle\; \backslash \; gamma\; (T)\}$, который предоставляет информацию о топологии и длинах ветвей для дерева $T\; \{\backslash \; displaystyle\; T\}$с использованием вектора или матрицы шаблона сайта $s\; (T)\; \{\backslash \; Displaystyle\; s\; (T)\}$.

$\gamma \; (T)\; =\; H\; -\; 1\; (пер\; \; (H\; s\; (T)))\; \{\backslash \; displaystyle\; \backslash \; gamma\; (T)\; =\; H\; ^\; \{-\; 1\}\; (\backslash \; ln\; (Hs\; (T)))\}$

где $H\; \{\backslash \; displaystyle\; H\}$- матрица Адамара подходящего размера. Это уравнение можно переписать в виде серии из трех уравнений, чтобы упростить его интерпретацию:

$r\; =\; H\; s\; (T)\; \{\backslash \; displaystyle\; r\; =\; Hs\; (T)\}$

$\rho \; =\; ln\; \; (r)\; \{\backslash \; displaystyle\; \backslash \; rho\; =\; \backslash \; ln\; (r)\}$

$\gamma \; (T)\; =\; H\; -\; 1\; \rho \; \{\backslash \; displaystyle\; \backslash \; gamma\; (T)\; =\; H\; ^\; \{-\; 1\}\; \backslash \; rho\}$

Обратимый характер этого уравнения позволяет рассчитать вектор (или матрицу) ожидаемого шаблона сайта следующим образом:

$s\; (T)\; =\; H\; -\; 1\; (exp\; \; (H\; \gamma \; (T)))\; \{\backslash \; displaystyle\; s\; (T)\; =\; H\; ^\; \{-\; 1\}\; (\; \backslash \; exp\; (H\; \backslash \; gamma\; (T)))\}$

Мы можем использовать модель замещения с двумя состояниями Кавендера-Фарриса-Неймана (CFN) для ДНК, кодируя нуклеотиды в виде двоичных знаков (пурины A и G кодируются как R, а пиримидины C и T кодируются как Y). Это позволяет кодировать множественное выравнивание последовательностей как вектор, который может быть преобразован в вектор дерева, как показано в следующем примере:

Пример, показывающий преобразование Адамара для определенного дерева (значения для рабочего примера адаптированы из Waddell et al. al. 1997)

Индекс	Двоичный шаблон	Шаблоны выравнивания	$\gamma \; (T)\; \{\backslash \; displaystyle\; \backslash \; gamma\; (T)\}$	$\rho \; =\; H\; -\; 1\; \gamma \; (\; T)\; \{\backslash \; displaystyle\; \backslash \; rho\; =\; H\; ^\; \{-\; 1\}\; \backslash \; gamma\; (T)\}$	$r\; =\; exp\; \; (\rho )\; \{\backslash \; displaystyle\; r\; =\; \backslash \; exp\; (\backslash \; rho)\}$	$s\; (T)\; =\; H\; -\; 1\; \rho \; \{\backslash \; displaystyle\; s\; (T)\; =\; H\; ^\; \{-\; 1\}\; \backslash \; rho\}$
0	0000	RRRR и YYYY	-0,475	0	1	0,6479
1	0001	RRRY и YYYR	0,2	-0,5	0,6065	0,1283
2	0010	RRYR и YYRY	0,025	-0,15	0,8607	0,02
3 *	0011	RRYY и YYRR	0,025	-0,45	0,6376	0,0226
4	0100	RYRR и YRYY	0,2	-0,45	0,6376	0,1283
5 *	0101	RYRY и YRYR	0	-0,85	0,4274	0,0258
6 *	0110	RYYR и YRRY	0	-0,5	0.6065	0,0070
7	0111	RYYY и YRRR	0,025	-0.9	0.4066	0.02

В примере, показанном в этой таблице, используется упрощенная схема с тремя уравнениями, и это для дерева четырех таксонов, которое может быть записано как ((A, B), (C, D)); в формате newick. Шаблоны сайта записываются в порядке ABCD. Это конкретное дерево имеет две длинные концевые ветви (0,2 трансверсионных замен на сайт), две короткие концевые ветви (0,025 трансверсионных замен на сайт) и короткую внутреннюю ветвь (0,025 трансверсионных замен на сайт); таким образом, он будет записан как ((A: 0,025, B: 0,2): 0,025, (C: 0,025, D: 0,2)); в формате newick. Это дерево будет демонстрировать притяжение длинных ветвей, если данные анализируются с использованием критерия максимальной экономии (при условии, что анализируемая последовательность достаточно длинна, чтобы наблюдаемые частоты паттернов сайтов были близки к ожидаемым частотам. показано в столбце $s\; (T)\; =\; H\; -\; 1\; \rho \; \{\backslash \; displaystyle\; s\; (T)\; =\; H\; ^\; \{-\; 1\}\; \backslash \; rho\}$). Привлекательность длинной ветви отражает тот факт, что ожидаемое количество шаблонов сайтов с индексом 6, поддерживающих дерево ((A, C), (B, D)); - превышает ожидаемое количество шаблонов сайтов, поддерживающих истинное дерево (индекс 4). Очевидно, обратимая природа филогенетического преобразования Адамара означает, что древовидный вектор означает, что древовидный вектор $\gamma \; (T)\; \{\backslash \; displaystyle\; \backslash \; gamma\; (T)\}$соответствует правильному дереву. Таким образом, экономичный анализ после преобразования статистически согласован, как и стандартный анализ максимального правдоподобия с использованием правильной модели (в данном случае модели CFN).

Обратите внимание, что шаблон сайта 0 соответствует сайтам, которые не изменились (после кодирования нуклеотидов как пурины или пиримидины), индексы со звездочками (3, 5 и 6) являются «информативными для экономии» и. остальные индексы представляют собой паттерны участков, в которых один таксон отличается от трех других таксонов (таким образом, они эквивалентны длине конечных ветвей в стандартном филогенетическом дереве максимального правдоподобия).

Если кто-то желает использовать нуклеотидные данные без перекодирования как R и Y (и в конечном итоге как 0 и 1), можно закодировать данные как матрицу. Если мы рассмотрим дерево из четырех таксонов, то всего будет 256 паттернов сайтов (четыре нуклеотида в четвертой степени). Однако симметрии трехпараметрической модели Кимуры (или K81) позволяют уменьшить количество шаблонов сайтов с 256 до 64 шаблонов, что позволяет кодировать нуклеотидные данные для дерева с четырьмя таксонами как 8 x 8, аналогично вектору из 8 элементов, использованному выше для шаблонов сайтов трансверсии (RY). Это достигается путем перекодирования данных с использованием четырехгруппового кодирования Клейна :

четырехгруппового кодирования Клейна для филогенетического преобразования Адамара

Нуклеотид 1	Нуклеотид 2	Нуклеотид 3	Нуклеотид 4
A (0,0)	G (1,0)	C (0,1)	T (1, 1)
C (0,0)	T (1,0)	A (0,1)	G (1,1)
G (0,0)	A (1,0)	T (0,1)	C (1,1)
T (0,0)	C (1,0)	G (0,1)	A (1,1)

Как и в случае данных RY, шаблоны сайтов индексируются относительно к базе в произвольно выбранном первом таксоне с базами в последующих таксонах, закодированных относительно этой первой базы. Таким образом, первый таксон получает битовую пару (0,0). Используя эти битовые пары, можно создать два вектора, похожие на векторы RY, а затем заполнить матрицу, используя эти векторы. Это можно проиллюстрировать на примере Hendy et al. (1994), который основан на множественном выравнивании последовательностей четырех псевдогенов гемоглобина приматов:

Пример выравнивания кодируемых последовательностей (из Hendy et al. 1994) (значения рассчитаны из 9879 сайтов)

	0	8	16	24	32	40	48	56
0	8988	9	10	12	24			90
1	41	9		**
2	45		13
3	54 *			14				3
4	94				20
5			1
6	2				2
7	356		1		1			75

Гораздо большее количество паттернов сайтов в столбце 0 отражает тот факт, что столбец 0 соответствует переходным различиям, которые накапливаются быстрее, чем различия трансверсии практически во всех сравнениях геномных областей (и определенно быстрее накапливаются в псевдогенах гемоглобина, использованных для этого рабочего примера). Если мы рассмотрим шаблон сайта AAGG, он будет иметь двоичный шаблон 0000 для второго элемента битовой пары группы Клейна и 0011 для первого элемента. в этом случае двоичный шаблон, основанный на первом элементе первого элемента, соответствует индексу 3 (так, строка 3 в столбце 0; обозначена одной звездочкой в ​​таблице). Шаблоны сайтов GGAA, CCTT и TTCC будут закодированы точно так же. Шаблон сайта AACT будет закодирован двоичным шаблоном 0011 на основе второго элемента и 0001 на основе первого элемента; это дает индекс 1 для первого элемента и индекс 3 для второго. Индекс, основанный на второй битовой паре группы Клейна, затем умножается на 8, чтобы получить столбец 24 строки 1 (ячейка обозначена двумя звездочками, но отсутствие числа в примере указывает на то, что выравнивание последовательностей не включает шаблоны сайтов AACT (аналогично, Шаблоны сайтов CCAG, GGTC и TTGA отсутствуют).

Преобразование Адамара также используется в шифровании данных, а также во многих обработка сигналов и алгоритмы сжатия данных , такие как JPEG XR и MPEG-4 AVC. В сжатие видео приложений, он обычно используется в форме суммы абсолютных преобразованных разностей. Он также является важной частью алгоритма Гровера и алгоритма Шора в квантовых вычислениях. Преобразование Адамара также применяется в экспериментальных методах, таких как ЯМР, масс-спектрометрия и кристаллография. Оно дополнительно используется в некоторых версиях местность-сенсити ve хеширование для получения псевдослучайных поворотов матрицы.

• Быстрое преобразование Уолша – Адамара
• Преобразование псевдо-Адамара
• Преобразование Хаара
• Обобщенный закон распределения

• Риттер, Терри (август 1996). «Преобразования Уолша-Адамара: обзор литературы».
• Акансу, A.N.; Полури, Р. (июль 2007 г.). «Нелинейные фазовые ортогональные коды типа Уолша для прямой последовательной связи CDMA» (PDF). Транзакции IEEE по обработке сигналов. 55 (7): 3800–6. doi : 10.1109 / TSP.2007.894229.
• Пан, Дженг-шян Метод шифрования данных с использованием дискретного дробного преобразования Адамара (28 мая 2009 г.)
• Лахович, доктор Павел. Преобразование Уолша – Адамара и серии тестов на случайность финансовой отдачи (7 апреля 2015 г.)
• Беддард, Годфри; Йорк, Бриони А. (январь 2011 г.). «Спектроскопия насос-зонд с использованием преобразований Адамара» (PDF).
• Yorke, Briony A.; Беддард, Годфри; Оуэн, Робин Л.; Пирсон, Арвен Р. (сентябрь 2014 г.). «Кристаллография с временным разрешением с использованием преобразования Адамара». Природные методы. 11 (11): 1131–1134. doi : 10,1038 / nmeth.3139. PMC 4216935. PMID 25282611.