Перегляд вихідного коду сторінки Перетворення Адамара

{{unibox}}[[Файл:1010 0110 Walsh spectrum (single row).svg|thumb|300px|Добуток булевої функції на матрицю Уолша є спектром Уолша:<ref>Compare Figure 1 in {{cite journal | citeseerx=10.1.1.74.8029 | title = Walsh Spectrum Computations Using Cayley Graphs | first1 = W. J. | last1 = Townsend | first2 = M. A. | last2 = Thornton }}</ref><br/>(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)]]
[[Файл:1010 0110 Walsh spectrum (fast WHT).svg|thumb|300px|Швидке перетворення Уолша-Адамара&nbsp;— швидший шлях до обчислення спектра Уолша від (1, 0, 1, 0, 0, 1, 1, 0).]]
[[Файл:1010 0110 Walsh spectrum (polynomial).svg|thumb|300px|Оригінальна функція може бути виражена у термінах її спектра Уолша через арифметичний поліном.]]'''Перетворення Адамара''' (також відоме як '''Перетворення Уолша&nbsp;— Адамара''', '''Перетворення Адамара&nbsp;— Радемахера&nbsp;— Уолша''', '''Перетворення Уолша''', або '''Перетворення Уолша&nbsp;— Фур'є''')&nbsp;— приклад узагальненого класу [[Перетворення Фур'є|перетворень Фур'є]]. Воно виконує [[Ортогональна матриця|ортогональне]], [[Симетрична матриця|симетричне]], [[Інволюція (математика)|інволютивне]], [[Лінійний оператор|лінійне]] перетворення над матрицею розміром {{math|2<sup>''m''</sup>}} з [[Дійсне число|дійсних чисел]] (або [[Комплексне число|комплексних чисел]], або [[Гіперкомплексне число|гіперкомплексних чисел]], хоча самі матриці Адамара є суто дійсними).

Перетворення Адамара можна розглядати як побудоване з розміру-2 [[дискретне перетворення Фур'є]] (ДПФ) і насправді еквівалентне багатовимірному ДПФ розміру {{math|2 &times; 2 &times; ⋯ &times; 2 &times; 2}}.<ref>{{cite journal |first=H.O. |last=Kunz |title=On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms |journal=IEEE Transactions on Computers |volume=28 |issue=3 |pages=267–8 |year=1979 |doi=10.1109/TC.1979.1675334 }}</ref> Воно розкладає довільний вхідний вектор на суперпозицію [[Функція Уолша|функцій Уолша]].

Перетворення названо на честь французького математика [[Жак Соломон Адамар|Жака Адамара]], німецько-американського математика {{li|Ганс Радемахер|text=Ганса Радемахера|Q=Q68554}} та американського математика {{li|Джозеф Уолш|text=Джозефа Л. Уолша|Q=Q1336492}}.

== Визначення ==
Перетворення Адамара ''H''<sub>''m''</sub> це 2<sup>''m''</sup>&nbsp;×&nbsp;2<sup>''m''</sup> матриця, [[Матриці Адамара|матриця Адамара]] (масштабована коефіцієнтом нормалізації), яка перетворює 2<sup>''m''</sup> дійсних чисел ''x''<sub>''n''</sub> у 2<sup>''m''</sup> дійсних чисел ''X''<sub>''k''</sub>. Перетворення Адамара може бути визначене двома способами: рекурсивно, або за допомогою представлення у [[Двійкова система числення|двійковій системі числення]] індексів ''n'' і ''k''.

Рекурсивно перетворення Адамара 1&nbsp;×&nbsp;1 визначається як ''H''<sub>0</sub> за ідентичністю ''H''<sub>0</sub> = 1, і після визначається ''H''<sub>''m''</sub> для ''m''&nbsp;>&nbsp;0 як:

: <math>H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix}</math>

де 1/{{radic|2}}&nbsp;— це нормалізація, яку іноді опускають.

Для ''m''&nbsp;>&nbsp;1 можна також визначити ''H''<sub>''m''</sub> як:

: <math>H_m = H_{1} \otimes H_{m-1}</math>

де <math> \otimes </math> представляє [[добуток Кронекера]]. Таким чином, крім цього коефіцієнта нормалізації, матриці Адамара повністю складаються з 1 і −1.

Еквівалентно, матриця Адамара може бути визначена за її (''k'',&nbsp;''n'')-ми елементами
: <math>\begin{align}
  k &= \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0 \\
  n &= \sum^{m-1}_{i=0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \cdots + n_1 2 + n_0
\end{align}</math>

де ''k''<sub>''j''</sub> та ''n''<sub>''j''</sub>&nbsp;— це двійкові цифри (0 та 1) ''k'' і ''n'' відповідно. Зверніть увагу, що для елемента у верхньому лівому куті визначається: <math>k = n = 0</math>. У цьому випадку ми маємо:
: <math>\left( H_m \right)_{k,n} = \frac{1}{2^\frac{m}{2}} (-1)^{\sum_j k_j n_j}</math>

Це саме багатовимірне <math>\scriptstyle 2 \,\times\, 2 \,\times\, \cdots \,\times\, 2 \,\times\, 2</math> ДПФ нормується щоб бути [[унітарний оператор | унітарним]], якщо входи та виходи розглядаються як багатовимірні масиви, проіндексовані ''n''<sub>''j''</sub> and ''k''<sub>''j''</sub>, відповідно.

Далі наводяться деякі приклади матриць Адамара.
: <math>\begin{align}
  H_0 = +&\begin{pmatrix}\begin{array}{r}1\end{array}\end{pmatrix}\\
  H_1 = \frac{1}{\sqrt2}
            &\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
   \end{array}\end{pmatrix}\\
  \left(H_n\right)_{i,j} = \frac{1}{2^\frac{n}{2}} &(-1)^{i \cdot j}
\end{align}</math>

де <math> i \cdot j </math>&nbsp;— побітовий добуток<!--уточнити--> двійкових подань чисел i та j. Наприклад, якщо <math>\scriptstyle n \;\geq\; 2</math>, то <math>\scriptstyle \left(H_n\right)_{3,2} \;=\;  (-1)^{3 \cdot 2} \;=\; (-1)^{(1,1) \cdot (1,0)} \;=\; (-1)^{1+0} \;=\; (-1)^1 \;=\; -1</math>, погоджується із вищесказаним (ігноруючи загальну константу). Зверніть увагу, що перший рядок, перший елемент стовпця матриці позначається <math>\scriptstyle \left(H_n\right)_{0,0} </math>.

''H''<sub>1</sub> є саме ДПФ розміру 2. Це також можна розглядати як [[перетворення Фур'є]] над двоелементною ''адитивною'' групою '''Z'''/(2).

Рядки матриць Адамара&nbsp;— це [[Функція Уолша|функції Уолша]].

== Обчислювальна складність ==
У класичній [[Модель обчислення|моделі обчислень]] перетворення Адамара можна обчислити за <math>n \log n</math> операцій (<math>n = 2^m</math>), використовуючи алгоритм [[Швидке перетворення Уолша-Адамара|швидкого перетворення Адамара]].

У квантовій моделі обчислень перетворення Адамара можна обчислити за час <math>O(1)</math>, оскільки це квантові логічні вентилі, які можуть бути паралелізовані.

== Застосування у квантових обчисленнях ==
У [[Квантова інформатика|квантовій інформатиці]] перетворення Адамара, яке в цьому контексті частіше називають '''вентилем Адамара''' (див. [[Квантовий вентиль]]), є однокубітним обертанням, відображенням станів кубіта <math>|0 \rangle </math> і <math>|1 \rangle </math> у суперпозицію станів з однаковою вагою обчислювальних базисів <math>|0 \rangle </math> і <math>|1 \rangle </math>. Зазвичай фази вибираються таким чином, щоб отримати:
: <math>H=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|</math>

у [[Нотація бра-кет|нотації Дірака]]. Це відповідає матриці перетворень
: <math>H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}</math>

у базисі <math>|0 \rangle , |1 \rangle </math> також відомому як обчислювальний базис. Стани <math display="inline">\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt{2}}</math> і <math display="inline">\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt{2}}</math> відомі як <math>\left|\boldsymbol{+}\right\rangle</math> and <math>\left|\boldsymbol{-}\right\rangle</math> відповідно, і разом складають полярний базис у квантових обчисленнях.

Багато квантових алгоритмів використовують перетворення Адамара як початковий крок, оскільки воно відображає ''m'' кубітів, ініціалізованих за допомогою <math>|0 \rangle</math> у суперпозицію всіх 2<sup>''m''</sup> ортогональних станів у <math> |0 \rangle , |1 \rangle </math> рівноважному базисі.

Примітно, що обчислення квантового перетворення Адамара&nbsp;— це просто застосування вентиля Адамара до кожного кубіта окремо через тензорну структуру добутку у перетворенні Адамара. Цей простий результат означає, що квантове перетворення Адамара вимагає ''log&nbsp;n''операцій порівняно з класичним випадком у ''n&nbsp;log&nbsp;n'' операцій.

=== Операції з вентилем Адамара ===
: <math>\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}</math>

Одне застосування вентиля Адамара до кубіта 0 або 1 створить квантовий стан, який, якщо його спостерігатимуть, буде рівним 0 або 1 з однаковою ймовірністю (як це видно на перших двох операціях). Це точно як підкидання справедливої монети у стандартній [[Імовірнісна машина Тюрінга|імовірнісній моделі обчислення]]. Однак, якщо вентиль Адамара застосовується двічі поспіль (як це робиться в останніх двох операціях), то кінцевий стан завжди збігається з початковим.

== Застосування у молекулярній філогенетиці (еволюційній біології) ==
Перетворення Адамара може бути використано для оцінки [[Філогенетичне дерево|філогенетичних дерев]] за молекулярними даними.<ref>{{Cite journal|last=Hendy|first=Michael D.|last2=Penny|first2=David|date=December 1989|title=A Framework for the Quantitative Study of Evolutionary Trees|url=https://academic.oup.com/sysbio/article-lookup/doi/10.2307/2992396|journal=Systematic Zoology|volume=38|issue=4|pages=297|doi=10.2307/2992396}}</ref><ref>{{Cite journal|last=Hendy|first=Michael D.|last2=Penny|first2=David|date=January 1993|title=Spectral analysis of phylogenetic data|url=http://link.springer.com/10.1007/BF02638451|journal=Journal of Classification|language=en|volume=10|issue=1|pages=5–24|doi=10.1007/BF02638451|issn=0176-4268}}</ref><ref>Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. ''Applied mathematics letters'', ''6''(2), 13-16.</ref> [[Філогенетика]]&nbsp;— це галузь [[Еволюційна біологія|еволюційної біології]], орієнтоване на розуміння взаємозв'язків між організмами. Перетворення Адамара, застосоване до вектора (або матриці) частот шаблонів сайтів, отриманих з ДНК [[Множинне вирівнювання послідовностей|множинним вирівнюванням послідовностей]], може бути використано для створення іншого вектора, який несе інформацію про топологію дерева. Оборотна природа філогенетичного перетворення Адамара також дозволяє обчислювати ймовірності ділянок за вектором дерева топології, дозволяючи використовувати перетворення Адамара для [[Метод максимальної правдоподібності|оцінки максимальної правдоподібності]] філогенетичних дерев. Однак останнє застосування менш корисне, ніж перетворення з вектора шаблонів сайту на вектор дерева, оскільки існують інші способи обчислення ймовірності сайту<ref>{{Cite journal|last=Felsenstein|first=Joseph|date=November 1981|title=Evolutionary trees from DNA sequences: A maximum likelihood approach|url=http://link.springer.com/10.1007/BF01734359|journal=Journal of Molecular Evolution|language=en|volume=17|issue=6|pages=368–376|doi=10.1007/BF01734359|issn=0022-2844}}</ref><ref>{{Citation|last=Stamatakis|first=Alexandros|title=A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations|date=2019|url=http://link.springer.com/10.1007/978-3-030-10837-3_1|work=Bioinformatics and Phylogenetics|volume=29|pages=1–19|editor-last=Warnow|editor-first=Tandy|place=Cham|publisher=Springer International Publishing|language=en|doi=10.1007/978-3-030-10837-3_1|isbn=978-3-030-10836-6|access-date=2020-10-10}}</ref> які набагато ефективніші. Однак оборотний характер філогенетичного перетворення Адамара справді забезпечує елегантний інструмент для математичної філогенетики.<ref>{{Cite journal|last=Chor|first=Benny|last2=Hendy|first2=Michael D.|last3=Holland|first3=Barbara R.|last4=Penny|first4=David|date=2000-10-01|title=Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach|url=http://academic.oup.com/mbe/article/17/10/1529/956181|journal=Molecular Biology and Evolution|language=en|volume=17|issue=10|pages=1529–1541|doi=10.1093/oxfordjournals.molbev.a026252|issn=1537-1719}}</ref><ref>{{Cite journal|last=Matsen|first=Frederick A.|last2=Steel|first2=Mike|date=2007-10-01|editor-last=Ané|editor-first=Cécile|editor2-last=Sullivan|editor2-first=Jack|title=Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology|url=https://academic.oup.com/sysbio/article/56/5/767/1695511|journal=Systematic Biology|language=en|volume=56|issue=5|pages=767–775|doi=10.1080/10635150701627304|issn=1076-836X}}</ref>

Механіка філогенетичного перетворення Адамара включає обчислення вектора <math>\gamma(T)</math>, що надає інформацію про топологію та довжини гілок для дерева <math>T</math> з використанням вектора або матриці шаблонів сайту <math>s(T)</math>.

<math>\gamma(T)=H^{-1}(\ln(Hs(T)))</math>

де <math>H</math>&nbsp;— матриця Адамара відповідного розміру. Це рівняння можна переписати як серію з трьох рівнянь для спрощення його інтерпретації:

<math>r=H s(T)</math>

<math>\rho=\ln(r)</math>

<math>\gamma(T)=H^{-1}\rho</math>

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

<math>s(T)=H^{-1}(\exp(H\gamma(T)))</math>

Ми можемо використовувати двоступінчасту [[Модель заміщення нуклеотидів|модель замін]] Кавендера-Фарріса-Неймана (CFN) для ДНК, кодуючи [[нуклеотиди]] як двійкові символи ([[Пурин|пурини]] A і G кодуються як R, а [[Піримідин|піримідини]] C і T кодуються як Y). Це дає можливість кодувати множинне [[вирівнювання послідовностей]] як вектор шаблонів сайту <math>s(T)</math> який можна перетворити на вектор дерева <math>\gamma(T)</math>, як показано на наступному прикладі:

{| class="wikitable"
|+Приклад, що показує застосування перетворення Адамара до специфічного дерева
(значення для прикладу&nbsp;— з Waddell et al. 1997<ref>{{Cite journal|last=Waddell|first=Peter J|last2=Steel|first2=M.A|date=December 1997|title=General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites|url=https://linkinghub.elsevier.com/retrieve/pii/S1055790397904528|journal=Molecular Phylogenetics and Evolution|language=en|volume=8|issue=3|pages=398–414|doi=10.1006/mpev.1997.0452}}</ref>)
!Індекс
!Двійковий шаблон
!Шаблони вирівнювання
!<math>\gamma(T)</math>
!<math>\rho=H^{-1}\gamma(T)</math>
!<math>r=\exp(\rho)</math>
!<math>s(T)=H^{-1}\rho</math>
|-
|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|форматі newick|en|Newick format}}. Шаблони сайтів написані в порядку ABCD. Це конкретне дерево має дві довгі кінцеві гілки (0,2 {{Не перекладено|Трансверсія|трансверсії|en|Transversion}} на сайт), дві короткі кінцеві гілки (0,025 трансверсії на сайт) і коротку внутрішню гілку (0,025 заміни трансверсії на сайт); таким чином, це буде записано як ((A: 0,025, B: 0,2): 0,025, (C: 0,025, D: 0,2)); у форматі newick. У цьому дереві буде показано {{Не перекладено|Притягання довгих гілок|притягання довгих гілок|en|Long branch attraction}}, якщо дані аналізуються за допомогою {{Не перекладено|Критерій максимальної ощадливості|критерію максимальної ощадливості|en|Maximum parsimony (phylogenetics)}} (припускаючи, що проаналізована послідовність досить довга, щоб частоти спостережуваних картин сайту були близькі до очікувані частоти, показаної в стовпці <math>s(T)=H^{-1}\rho</math>). Тривале притягання гілок відображає той факт, що очікувана кількість шаблонів сайтів з індексом 6&nbsp;— які підтримують дерево ((A, C), (B, D));&nbsp;— перевищує очікувану кількість шаблонів сайтів, які підтримують справжнє дерево (індекс 4). Очевидно, що обернена природа філогенетичного перетворення Адамара означає, що вектор дерева <math>\gamma(T)</math> відповідає правильному дереву. Тому аналіз ощадливості після перетворення є статистично узгодженим,<ref>{{Cite journal|last=Steel|first=M. A.|last2=Hendy|first2=M. D.|last3=Penny|first3=D.|date=1993-12-01|title=Parsimony Can Be Consistent!|url=https://academic.oup.com/sysbio/article-lookup/doi/10.1093/sysbio/42.4.581|journal=Systematic Biology|language=en|volume=42|issue=4|pages=581–587|doi=10.1093/sysbio/42.4.581|issn=1063-5157}}</ref> як це було б стандартним аналізом максимальної правдоподібності з використанням правильної моделі (у цьому випадку моделі CFN).

Зверніть увагу, що шаблон сайту з 0 відповідає сайтам, які не змінилися (після кодування нуклеотидів як пуринів або піримідинів). Індекси із зірочками (3, 5 та 6) є «інформаційними», і решта індексів представляють схеми ділянок, де один таксон відрізняється від інших трьох таксонів (тому вони еквівалентні довжинам кінцевих гілок у стандартному філогенетичному дереві з максимальною правдоподібністю).

Якщо хтось хоче використовувати дані нуклеотидів без перекодування як R і Y (і, зрештою, як 0 і 1), можна закодувати шаблони сайтів як матрицю. Якщо ми розглянемо дерево з чотирма таксонами, то загалом існує 256 візерунків (чотири нуклеотиди у 4-й степені). Однак симетрії {{Не перекладено|Моделі еволюції ДНК|трипараметричної (або K81) моделі Кімури|en|Models of DNA evolution}} дозволяють нам звести 256 можливих моделей ділянок ДНК до 64 шаблонів, що робить можливим кодування нуклеотидних даних для чотири-таксонного дерева як матриці 8х8<ref name=":0">{{Cite journal|last=Hendy|first=M. D.|last2=Penny|first2=D.|last3=Steel|first3=M. A.|date=1994-04-12|title=A discrete Fourier analysis for evolutionary trees.|url=http://www.pnas.org/cgi/doi/10.1073/pnas.91.8.3339|journal=Proceedings of the National Academy of Sciences|language=en|volume=91|issue=8|pages=3339–3343|doi=10.1073/pnas.91.8.3339|issn=0027-8424|pmc=43572|pmid=8159749}}</ref> способом, аналогічним вектору з 8 елементів, що використовувались вище для схеми перетворення (RY). Це досягається шляхом перекодування даних за допомогою [[4-група Клейна|4-групи Клейна]]:
{| class="wikitable"
|+Кодування 4-групи Клейна для філогенетичного перетворення Адамара
!Нуклеотид 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),<ref name=":0" /> який заснований на множинному вирівнюванні послідовностей чотирьох псевдогенів гемоглобіну приматів:

{| class="wikitable"
|+Приклад вирівнювання закодованої послідовності (з Hendy et al. 1994<ref name=":0" />)
'''(значення з підрахунку 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 відповідає перехідним відмінностям, які накопичуються швидше, ніж відмінності трансверсії практично у всіх порівняннях геномних областей (і, безумовно, накопичуються швидше в псевдогенах гемоглобіну, що використовуються для цього працюючого прикладу<ref>{{Cite journal|last=Miyamoto|first=M. M.|last2=Koop|first2=B. F.|last3=Slightom|first3=J. L.|last4=Goodman|first4=M.|last5=Tennant|first5=M. R.|date=1988-10-01|title=Molecular systematics of higher primates: genealogical relations and classification.|url=http://www.pnas.org/cgi/doi/10.1073/pnas.85.20.7627|journal=Proceedings of the National Academy of Sciences|language=en|volume=85|issue=20|pages=7627–7631|doi=10.1073/pnas.85.20.7627|issn=0027-8424|pmc=282245|pmid=3174657}}</ref>). Якщо ми розглянемо шаблон сайту AAGG, це буде двійковий шаблон 0000 для другого елемента пари бітів групи Клейна та 0011 для першого елемента. У цьому випадку двійковий шаблон, заснований на першому елементі, перший елемент відповідає індексу 3 (тому рядок 3 у стовпці 0; в таблиці позначається однією зірочкою). Шаблони сайтів GGAA, CCTT та TTCC кодувалися б точно так само. Шаблон сайту AACT кодувався двійковим шаблоном 0011 на основі другого елемента та 0001 на основі першого елемента; це дає індекс 1 для першого елемента та індекс 3 для другого. Індекс, заснований на другій парі бітів групи Клейна, множиться на 8, даючи індекс стовпця (у цьому випадку це буде стовпець 24) Клітинка, яка включатиме кількість шаблонів сайтів AACT, позначена двома зірочками; однак відсутність номера у прикладі вказує на те, що вирівнювання послідовностей не включає шаблони сайтів AACT (аналогічно, відсутні шаблони вебсайтів CCAG, GGTC та TTGA, які кодувалися б однаково).

== Інші застосування ==
Перетворення Адамара також використовується в шифруванні даних, а також у багатьох методах обробки сигналів та алгоритмах стиснення даних, таких як JPEG XR та MPEG-4 AVC. У додатках стиснення відео він зазвичай використовується у формі суми абсолютних трансформованих різниць. Це також найважливіша частина [[Алгоритм Грувера|алгоритму Грувера]] та [[Алгоритм Шора|алгоритму Шора]] в квантових обчисленнях. Перетворення Адамара також застосовується в експериментальних методах, таких як [[Ядерний магнітний резонанс|ЯМР]], [[мас-спектрометрія]] та [[кристалографія]]. Воно додатково використовується в деяких версіях локально-чутливого гешування для отримання псевдовипадкових обертань матриці.

== Див. також ==
* {{Не перекладено|Псевдоперетворення Адамара||en|Pseudo-Hadamard transform}}
* [[Гаарів вейвлет#Гаарове перетворення]]
* {{Не перекладено|Узагальнений дистрибутивний закон||en|Generalized distributive law}}

== Посилання ==
* {{cite web |first=Terry |last=Ritter |title=Walsh-Hadamard Transforms: A Literature Survey |date=August 1996 |url=http://www.ciphersbyritter.com/RES/WALHAD.HTM}}
* {{cite journal |first1=A.N. |last1=Akansu |first2=R. |last2=Poluri |title=Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications |journal=IEEE Transactions on Signal Processing |volume=55 |issue=7 |pages=3800–6 |date=July 2007 |doi=10.1109/TSP.2007.894229  |url=http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf }}
* Pan, Jeng-shyang [http://www.freepatentsonline.com/y2009/0136023.html Data Encryption Method Using Discrete Fractional Hadamard Transformation] (May 28, 2009)
* Lachowicz, Dr. Pawel. [http://www.quantatrisk.com/2015/04/07/walsh-hadamard-transform-python-tests-for-randomness-of-financial-return-series/ Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series] (April 7, 2015)
* {{cite web |first1=Godfrey |last1=Beddard |first2=Briony A.|last2=Yorke |title=Pump-probe Spectroscopy using Hadamard Transforms |date=January 2011 |url=http://www1.chem.leeds.ac.uk/People/GSB/Hadamard_for_web.pdf }}
* {{cite journal |first1=Briony A. |last1=Yorke |first2=Godfrey |last2=Beddard |first3=Robin L. |last3=Owen |first4=Arwen R. |last4=Pearson| title= Time-resolved crystallography using the Hadamard transform |journal= Nature Methods |date=September 2014 |doi=10.1038/nmeth.3139  |volume=11 |issue=11 |pages=1131–1134 |pmid=25282611 |pmc=4216935}}

== Примітки ==
{{reflist}}
[[Категорія:Інтегральні перетворення]]
[[Категорія:Цифрова обробка сигналів]]
[[Категорія:Квантова електроніка]]
[[Категорія:Квантова інформатика]]