아다마르 변환

섬네일|300px|행렬 곱과 불 함수 및 아다마르 행렬의 월시 스펙트럼:(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)
섬네일|300px|(1, 0, 1, 0, 0, 1, 1, 0)의 월시 스펙트럼을 계산하는 더 빠른 방법인 고속 월시-아다마르 변환
섬네일|300px|원래 함수는 월시 스펙트럼을 통해 산술 다항식으로 표현될 수 있다.
아다마르 변환(, 월시-아다마르 변환(Walsh–Hadamard transform), 아다마르-라데마허-월시 변환(Hadamard–Rademacher–Walsh transform), 월시 변환(Walsh transform), 또는 월시-푸리에 변환(Walsh–Fourier transform)이라고도 함)은 일반화된 푸리에 변환의 한 예시이다. 이는 개의 실수 (또는 복소수 또는 초복소수)에 대해 직교, 대칭, 대합적, 선형 연산을 수행한다 (아다마르 행렬 자체는 순수하게 실수이다).

아다마르 변환은 크기 2의 이산 푸리에 변환(DFT)으로 구성된 것으로 간주될 수 있으며, 실제로는 크기의 다차원 DFT와 동일하다. 이는 임의의 입력 벡터를 월시 함수의 중첩으로 분해한다.

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

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

재귀적으로, 우리는 1 × 1 아다마르 변환 H0를 단위 H0 = 1로 정의하고, m > 0에 대해 Hm을 다음과 같이 정의한다:

여기서 1/는 때때로 생략되는 정규화 요소이다.

m > 1의 경우, Hm은 다음과 같이 정의될 수도 있다:

여기서 는 크로네커 곱을 나타낸다. 따라서, 이 정규화 인자를 제외하면, 아다마르 행렬은 완전히 1과 −1로 구성된다.

동등하게, 아다마르 행렬은 (k, n)-번째 항목을 다음과 같이 정의할 수 있다:

여기서 kj와 nj는 각각 k와 n의 비트 요소(0 또는 1)이다. 왼쪽 상단 모서리의 요소에 대해 으로 정의한다. 이 경우, 다음이 성립한다:

이는 입력과 출력을 각각 nj와 kj로 인덱싱된 다차원 배열로 간주할 때, 정확히 의 다차원 DFT이며, 유니터리가 되도록 정규화되었다.

아다마르 행렬의 몇 가지 예시는 다음과 같다.

여기서 는 i와 j의 이진 표현의 비트 단위 스칼라곱이다. 예를 들어, 인 경우, 이 되며, 이는 위 결과와 일치한다(전체 상수 무시). 행렬의 첫 번째 행, 첫 번째 열 요소는 으로 표시된다.

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

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

 월시-아다마르 변환의 장점 
 실수 
행렬 H의 위 정의에 따르면, 여기서 H = H[m,n]으로 둔다.

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

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

 일부 속성은 DFT와 유사 
월시 변환 행렬에서 각 행과 각 열은 월시 함수이며, 부호 변화의 수가 연속적으로 증가한다. 즉, 첫 번째 행과 첫 번째 열에는 부호 변화가 없다(모든 항목이 1과 같다). 두 번째 행에는 하나의 부호 변화가 있고, 세 번째 행에는 두 개의 부호 변화가 있으며, 이런 식으로 마지막 행까지 이어진다. 이를 이산 푸리에 변환 과 비교하면, 각 행 에는 개의 영점 교차가 포함된다.

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

 푸리에 변환과의 관계 
아다마르 변환은 사실 크기의 다차원 DFT와 동일하다.

또 다른 접근 방식은 아다마르 변환을 불 대수군 에 대한 푸리에 변환으로 보는 것이다.
 유한 (아벨) 군에 대한 푸리에 변환을 사용하여, 함수 의 푸리에 변환은 다음과 같이 정의된 함수 이다.

여기서 는 의 지표이다. 각 지표는 어떤 에 대해 의 형태를 가지며, 여기서 곱셈은 비트 문자열에 대한 불 스칼라곱이다. 따라서 의 입력을 (폰트랴긴 쌍대성)와 동일시하고, 를 다음과 같이 정의할 수 있다:

이는 와 의 입력을 불리언 문자열로 간주할 때 의 아다마르 변환이다.

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

이는 벡터 에 적용될 때 순환군 의 지표를 사용하는 일반적인 이산 푸리에 변환과 비교된다.

 계산 복잡도 
고전적인 영역에서, 아다마르 변환은 고속 아다마르 변환 알고리즘을 사용하여 연산()으로 계산할 수 있다.

양자 영역에서, 아다마르 변환은 양자 논리 게이트로서 병렬화될 수 있으므로 시간에 계산할 수 있다.

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

 아다마르 게이트 

양자 컴퓨팅에서 아다마르 게이트는 하나의 큐비트 회전으로, 큐비트-기저 상태 와 를 계산 기저 상태 와 의 동일한 가중치를 갖는 두 개의 양자 중첩 상태로 매핑한다. 일반적으로 위상은 다음과 같이 선택된다:
 열에 표시된 예상 빈도에 근접할 만큼 충분히 길다고 가정). 긴 가지 끌림은 인덱스 6의 사이트 패턴(나무 ((A,C),(B,D))를 지지하는)의 예상 수가 참 나무(인덱스 4)를 지지하는 예상 사이트 패턴의 수를 초과한다는 사실을 반영한다. 분명히, 계통 발생학적 아다마르 변환의 가역적 특성은 나무 벡터 가 정확한 나무에 해당한다는 것을 의미한다. 따라서 변환 후의 단순성 분석은 통계적으로 일치하며, 올바른 모델(이 경우 CFN 모델)을 사용하는 표준 최대 우도 분석과 동일하다.

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

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

RY 데이터와 마찬가지로, 사이트 패턴은 임의로 선택된 첫 번째 분류군의 염기를 기준으로 색인화되며, 이후 분류군의 염기는 해당 첫 번째 염기를 기준으로 인코딩된다. 따라서 첫 번째 분류군은 비트 쌍 (0,0)을 받는다. 이 비트 쌍을 사용하여 RY 벡터와 유사한 두 개의 벡터를 생성한 다음 해당 벡터를 사용하여 행렬을 채울 수 있다. 이는 Hendy et al. (1994)의 예시를 사용하여 설명할 수 있으며, 이는 네 가지 영장류 헤모글로빈 유사유전자의 다중 서열 정렬을 기반으로 한다:

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

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

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

 외부 링크 

 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)

 각주 

분류:양자 알고리즘
분류:변환 (수학)