월시-아다마르 변환 (Walsh–Hadamard Transform, WHT)

월시-아다마르 변환(Walsh–Hadamard Transform, WHT)은 일반화된 푸리에 변환 클래스의 한 예로, 2^m개의 실수에 대해 직교, 대칭, 대합(정규화했을 때), 선형인 연산을 수행합니다. 사인·코사인 대신 값이 +1과 −1뿐인 월시 함수로 데이터를 분해하며, 행렬로는 성분이 모두 ±1인 아다마르 행렬을 곱하는 것과 같습니다. 이 변환은 프랑스 수학자 자크 아다마르, 독일계 미국인 수학자 한스 라데마허, 미국 수학자 조셉 L. 월시의 이름을 따서 명명되었습니다.

아다마르 행렬로 정의하기

크기 2^m의 아다마르 행렬 H_m은 재귀적으로 만들어집니다. H₀ = [1]이고, H_m은 H_m−1을 네 칸에 배치하되 오른쪽 아래 칸에만 −1을 곱한 블록 행렬 [[H_m−1, H_m−1], [H_m−1, −H_m−1]]입니다. 예를 들어 H₁ = [[1, 1], [1, −1]]입니다. 길이 2^m인 벡터 x의 WHT는 H_m·x입니다.

• 직교성: 행렬의 서로 다른 행은 서로 직교합니다. H_m·H_m^T = 2^m·I입니다.
• 대칭성: 행렬이 자기 자신의 전치 행렬과 같습니다(H_m = H_m^T).
• 대합성: 2^−m/2로 정규화한 변환은 두 번 적용하면 원래 벡터로 돌아갑니다. 즉 이 변환은 자기 자신의 역변환입니다.
• 선형성: 덧셈과 스칼라 곱셈을 보존합니다.

빠른 계산

고속 푸리에 변환(FFT)과 같은 나비(butterfly) 구조를 쓰면 곱셈 없이 덧셈과 뺄셈만으로 m·2^m번의 연산에 계산할 수 있습니다. 이를 고속 월시-아다마르 변환이라고 합니다.

암호에서의 쓰임: 불리언 함수 분석

m비트 입력의 불리언 함수 f에 대해 월시 스펙트럼은 W_f(w) = Σ_x (−1)^{f(x) ⊕ w·x}로 정의되며, 이는 (−1)^f(x) 값들의 벡터에 WHT를 적용한 것과 같습니다. 각 값은 f가 선형 함수 w·x와 얼마나 일치하는지(상관)를 나타냅니다.

• 비선형성: f의 비선형성은 2^m−1 − max|W_f(w)|/2로 계산됩니다. 값이 클수록 f를 선형 함수로 근사하기 어렵습니다.
• 선형 암호 분석: 블록 암호의 S-box가 선형 근사에 얼마나 취약한지 평가하는 데 쓰입니다.
• 상관 면역성과 균형성: 스트림 암호의 결합 함수가 입력 일부와 상관되지 않는지, 출력에 0과 1이 고르게 나오는지(W_f(0) = 0)를 확인하는 데 쓰입니다.

장점과 한계

• 단순성: 곱셈 없이 덧셈과 뺄셈만 쓰므로 FFT보다 계산이 간단합니다.
• 이진 구조와의 적합성: 비트와 불리언 함수를 다루는 문제에 자연스럽게 맞습니다.
• 주파수 해석의 한계: FFT와 달리 결과가 물리적 주파수에 직접 대응하지 않으므로 일부 신호 처리 응용에는 덜 적합합니다.

다른 응용 분야

신호 처리, 이미지 압축, 부호 이론(예: 리드-뮬러 부호의 복호), 양자 컴퓨팅의 아다마르 게이트 등 여러 계산 분야에서 활용됩니다.

이름의 유래

1. 자크 아다마르: 행렬 이론과 행렬식 연구로 알려진 프랑스 수학자.
2. 한스 라데마허: 수론과 해석학 연구로 알려진 독일계 미국인 수학자.
3. 조셉 L. 월시: 근사 이론과 직교 함수 연구로 알려진 미국 수학자.