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

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

## 아다마르 행렬로 정의하기

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

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

## 빠른 계산

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

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

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

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

## 장점과 한계

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

## 다른 응용 분야

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

## 이름의 유래

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

---
출처: https://achivx.kr/glossary/walsh-hadamard-transform-wht-%EC%99%88%EC%8B%9C-%ED%95%98%EB%8B%A4%EB%A7%88%EB%93%9C-%EB%B3%80%ED%99%98/ · ACHIVX 용어 사전 · 수정일 2026-10-20