아다마르 변환

아다마르 변환(영어: Hadamard transform, 월시-아다마르 변환(Walsh–Hadamard transform), 아다마르-라데마허-월시 변환(Hadamard–Rademacher–Walsh transform), 월시 변환(Walsh transform), 또는 월시-푸리에 변환(Walsh–Fourier transform)이라고도 함)은 일반화된 푸리에 변환의 한 예시이다. 이는 2^m개의 실수 (또는 복소수 또는 초복소수)에 대해 직교, 대칭, 대합적, 선형 연산을 수행한다 (아다마르 행렬 자체는 순수하게 실수이다).

행렬 곱과 불 함수 및 아다마르 행렬의 월시 스펙트럼:^[1]
(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의 이산 푸리에 변환(DFT)으로 구성된 것으로 간주될 수 있으며, 실제로는 2 × 2 × ⋯ × 2 × 2 크기의 다차원 DFT와 동일하다.^[2] 이는 임의의 입력 벡터를 월시 함수의 중첩으로 분해한다.

이 변환은 프랑스의 수학자인 자크 아다마르(프랑스어: [adamaʁ]), 독일계 미국인 수학자 한스 라데마허, 그리고 미국인 수학자 조세프 월시의 이름을 따서 명명되었다.

정의

아다마르 변환 H_m은 2^m × 2^m 행렬인 아다마르 행렬(정규화 인자로 스케일링됨)로, 2^m개의 실수 x_n을 2^m개의 실수 X_k로 변환한다. 아다마르 변환은 두 가지 방식으로 정의될 수 있다: 재귀적으로 정의하거나, 인덱스 n과 k의 이진 (기수-2) 표현을 사용하여 정의한다.

재귀적으로, 우리는 1 × 1 아다마르 변환 H₀를 단위 H₀ = 1로 정의하고, m > 0에 대해 H_m을 다음과 같이 정의한다: $${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$ 여기서 1/√2는 때때로 생략되는 정규화 요소이다.

m > 1의 경우, H_m은 다음과 같이 정의될 수도 있다: $${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$$ 여기서 ${\displaystyle \otimes }$는 크로네커 곱을 나타낸다. 따라서, 이 정규화 인자를 제외하면, 아다마르 행렬은 완전히 1과 −1로 구성된다.

동등하게, 아다마르 행렬은 (k, n)-번째 항목을 다음과 같이 정의할 수 있다: $${\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

여기서 k_j와 n_j는 각각 k와 n의 비트 요소(0 또는 1)이다. 왼쪽 상단 모서리의 요소에 대해 ${\displaystyle k=n=0}$으로 정의한다. 이 경우, 다음이 성립한다: $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

이는 입력과 출력을 각각 n_j와 k_j로 인덱싱된 다차원 배열로 간주할 때, 정확히 ${\textstyle 2\times 2\times \cdots \times 2\times 2}$의 다차원 DFT이며, 유니터리가 되도록 정규화되었다.

아다마르 행렬의 몇 가지 예시는 다음과 같다. $${\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\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}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}$$ 여기서 ${\displaystyle i\cdot j}$는 i와 j의 이진 표현의 비트 단위 스칼라곱이다. 예를 들어, ${\textstyle n\;\geq \;2}$인 경우, $${\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$$이 되며, 이는 위 결과와 일치한다(전체 상수 무시). 행렬의 첫 번째 행, 첫 번째 열 요소는 ${\textstyle (H_{n})_{0,0}}$으로 표시된다.

H₁은 정확히 크기 2의 DFT이다. 이는 또한 Z/(2)의 두 요소 덧셈 그룹에 대한 푸리에 변환으로 간주될 수 있다.

아다마르 행렬의 행은 월시 함수이다.

월시-아다마르 변환의 장점

실수

행렬 H의 위 정의에 따르면, 여기서 H = H[m,n]으로 둔다. $${\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$

월시 변환에서는 행렬에 1과 -1만 나타난다. 1과 -1은 실수이므로 복소수 계산을 수행할 필요가 없다.

곱셈이 필요 없음

DFT는 무리수 곱셈이 필요한 반면, 아다마르 변환은 그렇지 않다. 부호 반전만으로 충분하므로 유리수 곱셈도 필요하지 않다.

일부 속성은 DFT와 유사

월시 변환 행렬에서 각 행과 각 열은 월시 함수이며, 부호 변화의 수가 연속적으로 증가한다. 즉, 첫 번째 행과 첫 번째 열에는 부호 변화가 없다(모든 항목이 1과 같다). 두 번째 행에는 하나의 부호 변화가 있고, 세 번째 행에는 두 개의 부호 변화가 있으며, 이런 식으로 마지막 행까지 이어진다. $${\displaystyle H[m,n]=\left({\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}}\right)}$$이를 이산 푸리에 변환 ${\textstyle e^{-j2\pi mn/N}}$과 비교하면, 각 행 i에는 ${\textstyle i-1}$개의 영점 교차가 포함된다.

이산 푸리에 변환에서 m이 0과 같을 때(첫 번째 행에 해당), 결과도 1이다. 이후 행에 대해서는 행렬의 특성인 신호 주파수가 첫 번째 원본 행렬에서는 낮게 시작하여 다음 행으로 갈수록 증가하다가 마지막 행에서 최고조에 달하는 것을 관찰할 수 있다.

푸리에 변환과의 관계

아다마르 변환은 사실 2 × 2 × ⋯ × 2 × 2 크기의 다차원 DFT와 동일하다.^[2]

또 다른 접근 방식은 아다마르 변환을 불 대수군 ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$에 대한 푸리에 변환으로 보는 것이다.^{[3] [4]} 유한 (아벨) 군에 대한 푸리에 변환을 사용하여, 함수 ${\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$의 푸리에 변환은 다음과 같이 정의된 함수 ${\displaystyle {\widehat {f}}}$이다. $${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}$$ 여기서 ${\displaystyle \chi }$는 ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$의 지표이다. 각 지표는 어떤 ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$에 대해 ${\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}$의 형태를 가지며, 여기서 곱셈은 비트 문자열에 대한 불 스칼라곱이다. 따라서 ${\displaystyle {\widehat {f}}}$의 입력을 ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$(폰트랴긴 쌍대성)와 동일시하고, ${\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$를 다음과 같이 정의할 수 있다: $${\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}$$

이는 ${\displaystyle f}$와 ${\displaystyle {\widehat {f}}}$의 입력을 불리언 문자열로 간주할 때 ${\displaystyle f}$의 아다마르 변환이다.

아다마르 변환이 ${\displaystyle 2^{n}}$개의 복소수 벡터 ${\displaystyle v}$에 왼쪽에서 아다마르 행렬 ${\displaystyle H_{n}}$을 곱하는 위의 공식화 측면에서, 이 동등성은 ${\displaystyle f}$를 ${\displaystyle v}$의 요소 인덱스에 해당하는 비트 문자열을 입력으로 받고, ${\displaystyle f}$가 ${\displaystyle v}$의 해당 요소를 출력하도록 취함으로써 확인된다.

이는 벡터 ${\displaystyle v}$에 적용될 때 순환군 ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$의 지표를 사용하는 일반적인 이산 푸리에 변환과 비교된다.

계산 복잡도

고전적인 영역에서, 아다마르 변환은 고속 아다마르 변환 알고리즘을 사용하여 ${\displaystyle n\log n}$ 연산(${\displaystyle n=2^{m}}$)으로 계산할 수 있다.

양자 영역에서, 아다마르 변환은 양자 논리 게이트로서 병렬화될 수 있으므로 ${\displaystyle O(1)}$ 시간에 계산할 수 있다.

양자 컴퓨팅 응용

아다마르 변환은 양자 컴퓨팅에서 광범위하게 사용된다. 2 × 2 아다마르 변환 ${\displaystyle H_{1}}$은 아다마르 게이트로 알려진 양자 논리 게이트이며, ${\displaystyle n}$-큐비트 레지스터의 각 큐비트에 아다마르 게이트를 병렬로 적용하는 것은 아다마르 변환 ${\displaystyle H_{n}}$과 동일하다.

아다마르 게이트

 양자 게이트 § 아다마르 게이트 문서에 이 부분의 추가 정보가 있습니다.

양자 컴퓨팅에서 아다마르 게이트는 하나의 큐비트 회전으로, 큐비트-기저 상태 ${\displaystyle |0\rangle }$와 ${\displaystyle |1\rangle }$를 계산 기저 상태 ${\displaystyle |0\rangle }$와 ${\displaystyle |1\rangle }$의 동일한 가중치를 갖는 두 개의 양자 중첩 상태로 매핑한다. 일반적으로 위상은 다음과 같이 선택된다: $${\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}$$

디랙 표기법에서. 이는 변환행렬 $${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$ 에 해당한다. 이는 ${\displaystyle |0\rangle ,|1\rangle }$ 기저, 즉 계산 기저에서도 알려져 있다. 상태 ${\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}$와 ${\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}$는 각각 ${\displaystyle \left|{\boldsymbol {+}}\right\rangle }$와 ${\displaystyle \left|{\boldsymbol {-}}\right\rangle }$로 알려져 있으며, 함께 양자 컴퓨팅에서 극좌표 기저를 구성한다.

아다마르 게이트 연산

$${\displaystyle {\begin{aligned}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(|+\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(|-\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{aligned}}}$$

0 또는 1 큐비트에 아다마르 게이트를 한 번 적용하면 (처음 두 연산에서 볼 수 있듯이) 관측될 경우 0 또는 1이 동일한 확률로 나올 양자 상태가 생성된다. 이는 표준 확률적 계산 모델에서 공정한 동전을 던지는 것과 정확히 같다. 그러나 아다마르 게이트를 연속으로 두 번 적용하면 (마지막 두 연산에서 효과적으로 수행되는 것처럼), 최종 상태는 항상 초기 상태와 동일하다.

양자 알고리즘의 아다마르 변환

양자 아다마르 변환은 아다마르 변환의 텐서곱 구조 때문에 각 큐비트에 아다마르 게이트를 개별적으로 적용하는 것과 같다. 이 간단한 결과는 양자 아다마르 변환이 ${\displaystyle \log _{2}N}$ 연산을 필요로 하며, 고전적인 경우 ${\displaystyle N\log _{2}N}$ 연산과 비교된다는 것을 의미한다.

${\displaystyle n}$-큐비트 시스템의 경우, 각 ${\displaystyle n}$ 큐비트(각각 ${\displaystyle |0\rangle }$으로 초기화됨)에 작용하는 아다마르 게이트는 ${\displaystyle N=2^{n}}$ 형태일 때 균일한 양자 중첩 상태를 준비하는 데 사용될 수 있다. 이 경우 ${\displaystyle n}$ 큐비트를 사용하면 결합된 아다마르 게이트 ${\displaystyle H_{n}}$은 ${\displaystyle n}$개의 아다마르 게이트의 텐서곱으로 표현된다: ${\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}$

결과적인 균일 양자 중첩 상태는 다음과 같다: ${\displaystyle H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }$ 이는 모든 ${\displaystyle N=2^{n}}$에 대해 아다마르 게이트를 사용하여 균일 양자 상태를 준비하는 것을 일반화한다.^[5]

이 균일 양자 상태의 측정은 ${\displaystyle |0\rangle }$과 ${\displaystyle |N-1\rangle }$ 사이의 무작위 상태를 초래한다.

많은 양자 알고리즘은 아다마르 변환을 초기 단계로 사용한다. 앞서 설명했듯이, 이는 ${\displaystyle |0\rangle }$으로 초기화된 n 큐비트를 ${\displaystyle |0\rangle ,|1\rangle }$ 기저의 모든 2ⁿ 직교 상태의 동일한 가중치를 갖는 중첩으로 매핑하기 때문이다. 예를 들어, 이는 도이치–조사 알고리즘, 사이먼의 알고리즘, 번스타인-바지라니 알고리즘, 그리고 그로버 알고리즘에서 사용된다. 쇼어 알고리즘은 초기 아다마르 변환과 양자 푸리에 변환을 모두 사용하는데, 둘 다 유한군에 대한 푸리에 변환의 일종이다. 첫 번째는 ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$에 대한 것이고 두 번째는 ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$에 대한 것이다.

일반적인 경우 ${\displaystyle N}$ ≠ ${\displaystyle 2^{n}}$일 때 균일 양자 중첩 상태를 준비하는 것은 비자명하며 더 많은 작업이 필요하다. 균일 중첩 상태를 준비하기 위한 효율적이고 결정론적인 접근 방식 $${\displaystyle |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }$$ 는 모든 ${\displaystyle N}$에 대해 게이트 복잡도와 회로 깊이가 ${\displaystyle O(\log _{2}N)}$에 불과하며 최근에 발표되었다.^[6] 이 접근 방식은 오직 ${\displaystyle n=\lceil \log _{2}N\rceil }$ 큐비트만 필요하다. 중요한 점은 이 접근 방식에서 균일 중첩 상태 ${\displaystyle |\Psi \rangle }$를 생성하는 데 보조 큐비트나 다중 제어 양자 게이트가 필요하지 않다는 것이다.

분자 계통학(진화생물학) 응용

아다마르 변환은 분자 데이터를 사용하여 계통수를 추정하는 데 사용될 수 있다.^[7][8][9] 계통학은 유기체 간의 관계를 이해하는 데 초점을 맞춘 진화생물학의 하위 분야이다. DNA 다중서열정렬에서 얻은 위치 패턴 빈도의 벡터(또는 행렬)에 적용된 아다마르 변환은 나무 위상에 대한 정보를 담는 또 다른 벡터를 생성하는 데 사용될 수 있다. 계통 발생학적 아다마르 변환의 가역적 특성은 나무 위상 벡터로부터 위치 가능성을 계산할 수 있게 하여, 아다마르 변환을 최대 가능도 추정에 사용할 수 있도록 한다. 그러나 후자의 응용은 위치 가능성을 계산하는 다른 훨씬 더 효율적인 방법이 있기 때문에 위치 패턴 벡터에서 나무 벡터로의 변환보다 덜 유용하다.^[10][11] 그러나 계통 발생학적 아다마르 변환의 가역적 특성은 수학적 계통 발생학을 위한 우아한 도구를 제공한다.^[12][13]

계통 발생학적 아다마르 변환의 메커니즘은 나무 ${\displaystyle T}$에 대한 위상 및 분지 길이 정보를 제공하는 벡터 ${\displaystyle \gamma (T)}$를 사이트 패턴 벡터 또는 행렬 ${\displaystyle s(T)}$를 사용하여 계산하는 것을 포함한다.

$${\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}$$ 여기서 ${\displaystyle H}$는 적절한 크기의 아다마르 행렬이다. 이 방정식은 해석을 단순화하기 위해 세 개의 방정식 시리즈로 다시 작성될 수 있다:

$${\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}$$

이 방정식의 가역적 특성은 다음과 같이 예상되는 사이트 패턴 벡터(또는 행렬)를 계산할 수 있게 한다:

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

DNA에 대한 Cavender–Farris–Neyman (CFN) 두 상태 치환 모델을 사용하여 뉴클레오타이드를 이진 문자(퓨린 A와 G는 R로, 피리미딘 C와 T는 Y로 인코딩)로 인코딩할 수 있다. 이렇게 하면 다중 서열 정렬을 위 사이트 패턴 벡터 ${\displaystyle s(T)}$로 인코딩할 수 있으며, 이는 다음 예시에서와 같이 나무 벡터 ${\displaystyle \gamma (T)}$로 변환될 수 있다:

특정 나무에 대한 아다마르 변환을 보여주는 예시 (작업 예시에 대한 값은 Waddell et al. 1997^[14]에서 인용)

인덱스	이진 패턴	정렬 패턴	${\displaystyle \gamma (T)}$	${\displaystyle \rho =H^{-1}\gamma (T)}$	${\displaystyle r=\exp(\rho )}$	${\displaystyle s(T)=H^{-1}\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

이 표에 제시된 예시는 간략화된 세 가지 방정식 체계를 사용하며, Newick 형식으로 ((A,B),(C,D))로 작성될 수 있는 4개 분류군 나무에 대한 것이다. 사이트 패턴은 ABCD 순서로 작성된다. 이 특정 나무는 두 개의 긴 말단 가지(사이트당 0.2개의 트랜스버전 치환), 두 개의 짧은 말단 가지(사이트당 0.025개의 트랜스버전 치환), 그리고 짧은 내부 가지(사이트당 0.025개의 트랜스버전 치환)를 가지고 있다. 따라서 Newick 형식으로는 ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2))로 작성될 것이다. 이 나무는 데이터가 최대 단순성 기준으로 분석될 경우 긴 가지 끌림을 나타낼 것이다(분석된 서열이 관찰된 사이트 패턴 빈도가 ${\displaystyle s(T)=H^{-1}\rho }$ 열에 표시된 예상 빈도에 근접할 만큼 충분히 길다고 가정). 긴 가지 끌림은 인덱스 6의 사이트 패턴(나무 ((A,C),(B,D))를 지지하는)의 예상 수가 참 나무(인덱스 4)를 지지하는 예상 사이트 패턴의 수를 초과한다는 사실을 반영한다. 분명히, 계통 발생학적 아다마르 변환의 가역적 특성은 나무 벡터 ${\displaystyle \gamma (T)}$가 정확한 나무에 해당한다는 것을 의미한다. 따라서 변환 후의 단순성 분석은 통계적으로 일치하며,^[15] 올바른 모델(이 경우 CFN 모델)을 사용하는 표준 최대 우도 분석과 동일하다.

0 인덱스의 사이트 패턴은 (뉴클레오타이드를 퓨린 또는 피리미딘으로 인코딩한 후) 변경되지 않은 사이트에 해당한다. 별표가 있는 인덱스(3, 5, 6)는 "parsimony-informative"하며, 나머지 인덱스는 단일 분류군이 다른 세 분류군과 다른 사이트 패턴을 나타낸다(따라서 표준 최대 우도 계통수에서 말단 가지 길이와 동등하다).

RY 데이터 없이 뉴클레오타이드 데이터를 사용하려면(궁극적으로 0과 1로 재코딩), 사이트 패턴을 행렬로 인코딩할 수 있다. 4개 분류군 나무를 고려하면 총 256개의 사이트 패턴(4개의 뉴클레오타이드의 4제곱)이 존재한다. 그러나 기무라 3매개변수(또는 K81) 모델의 대칭성을 통해 DNA에 대한 256개의 가능한 사이트 패턴을 64개 패턴으로 줄일 수 있으며, 이로 인해 4개 분류군 나무에 대한 뉴클레오타이드 데이터를 8 × 8 행렬로 인코딩할 수 있다.^[16] 이는 위에서 전이(RY) 사이트 패턴에 사용된 8개 요소 벡터와 유사하다. 이는 클라인 4원군을 사용하여 데이터를 재코딩함으로써 달성된다:

계통 발생학적 아다마르 변환을 위한 클라인 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)의 예시^[16]를 사용하여 설명할 수 있으며, 이는 네 가지 영장류 헤모글로빈 유사유전자의 다중 서열 정렬을 기반으로 한다:

인코딩된 서열 정렬 예시 (Hendy et al. 1994^[16]에서 발췌) (값은 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열이 전이 차이에 해당하기 때문이며, 이는 거의 모든 유전체 영역 비교에서 트랜스버전 차이보다 더 빠르게 축적된다(그리고 이 예시에 사용된 헤모글로빈 유사유전자에서는 확실히 더 빠르게 축적된다^[17]). AAGG 사이트 패턴을 고려하면 클라인 군 비트 쌍의 두 번째 요소에 대해 이진 패턴 0000이 되고, 첫 번째 요소에 대해 0011이 된다. 이 경우 첫 번째 요소를 기반으로 한 이진 패턴은 인덱스 3(테이블에서 단일 별표로 표시)에 해당한다. GGAA, CCTT, TTCC 사이트 패턴도 정확히 같은 방식으로 인코딩된다. AACT 사이트 패턴은 두 번째 요소에 대해 이진 패턴 0011, 첫 번째 요소에 대해 0001로 인코딩된다. 이는 첫 번째 요소에 대해 인덱스 1, 두 번째 요소에 대해 인덱스 3을 생성한다. 두 번째 클라인 군 비트 쌍을 기반으로 한 인덱스는 8을 곱하여 열 인덱스(이 경우 24열)를 산출한다. AACT 사이트 패턴의 개수가 포함될 셀은 두 개의 별표로 표시되어 있다. 그러나 예시에서 숫자가 없는 것은 서열 정렬에 AACT 사이트 패턴이 없음을 나타낸다(마찬가지로 CCAG, GGTC, TTGA 사이트 패턴도 같은 방식으로 인코딩되며, 이들도 없음).

기타 응용

아다마르 변환은 데이터 암호화, JPEG XR 및 MPEG-4 AVC와 같은 많은 신호 처리 및 데이터 압축 알고리즘에서도 사용된다. 영상 압축 응용 프로그램에서는 일반적으로 변환된 차이의 절대값 합계 형태로 사용된다. 또한 양자 컴퓨팅에서 상당수의 알고리즘의 중요한 부분이다. 아다마르 변환은 핵자기 공명, 질량 분석법 및 결정학과 같은 실험 기술에도 적용된다. 또한 일부 버전의 지역 민감 해싱에서도 의사 난수 행렬 회전을 얻기 위해 사용된다.

같이 보기

• 고속 왈시-아다마르 변환
• 유사-아다마르 변환
• 하르 변환
• 일반화된 분배 법칙

외부 링크

• Ritter, Terry (August 1996). “Walsh–Hadamard Transforms: A Literature Survey”.
• Akansu, Ali N.; Poluri, R. (July 2007). 《Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications》 (PDF). 《IEEE Transactions on Signal Processing》 55. 3800–6쪽. Bibcode:2007ITSP...55.3800A. doi:10.1109/TSP.2007.894229. S2CID 6830633.
• Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (May 28, 2009)
• Lachowicz, Dr. Pawel. Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series (April 7, 2015)
• Beddard, Godfrey; Yorke, Briony A. (January 2011). “Pump-probe Spectroscopy using Hadamard Transforms” (PDF). 2014년 10월 18일에 원본 문서 (PDF)에서 보존된 문서. 2012년 4월 28일에 확인함.
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). 《Time-resolved crystallography using the Hadamard transform》. 《Nature Methods》 11. 1131–1134쪽. doi:10.1038/nmeth.3139. PMC 4216935. PMID 25282611.