정의
해밍 가중치(Hamming weight)는 이진 문자열(또는 이진 벡터)에서 1의 개수를 셈으로써 구해지는 값이다. 동일한 개념은 영문으로 population count 혹은 bit count라 불리며, 코드 이론·암호학·통신·컴퓨터 과학 등 다양한 분야에서 활용된다.
주요 특성 및 관련 개념
| 특성 | 설명 |
|---|---|
| 수학적 정의 | 𝑤(𝑥) = Σᵢ xᵢ (단, xᵢ ∈ {0,1}) |
| 해밍 거리와의 관계 | 두 이진 문자열 a, b 사이의 해밍 거리 d(a,b) = 𝑤(a ⊕ b) (⊕는 XOR) |
| 응용 분야 | * 오류 정정 코드(예: 해밍 코드) * 암호학(예: 선형 코드, 해시 함수) * 알고리즘 최적화(비트 연산, POPCNT 명령) |
| 계산 방법 | 소프트웨어: 루프, 테이블 기반, 비트 트릭(예: x = x - ((x >> 1) & 0x5555…) 등) 하드웨어: 전용 POPCNT 연산(인텔·AMD) |
| 다른 이름 | population count, bit count, weight (in coding theory) |
어원
‘해밍’은 미국의 전기공학자 리처드 해밍(Richard Hamming, 1915‑1998)의 이름에서 온 것으로, 해밍 코드와 해밍 거리 등 그의 연구와 관련된 여러 개념에 사용된다. ‘가중치’는 한국어로 ‘weight’를 의미하며, 해당 비트들의 합산을 나타내는 의미로 쓰인다. 따라서 “해밍 가중치”는 “Hamming weight”를 직역한 용어이다.
사용 예시
- 예시 문자열
- 문자열
1011010의 해밍 가중치: 1 + 0 + 1 + 1 + 0 + 1 + 0 = 4
- 문자열
- 오류 검출
- 전송된 코드워드와 수신된 코드워드의 XOR 결과가
0000011이면 해밍 가중치가 2이므로, 두 비트가 오류가 있음을 의미한다.
- 전송된 코드워드와 수신된 코드워드의 XOR 결과가
- 암호학
- 선형 블록 암호에서 키와 평문 사이의 Hamming weight 차이는 암호 강도 분석에 활용된다.
관련 문헌 및 참고 자료
- R. W. Hamming, Error Detecting and Error Correcting Codes, Bell System Technical Journal, 1950.
- F. J. MacWilliams & N. J. A. Sloane, The Theory of Error‑Correcting Codes, 1977.
- Intel® 64 and IA‑32 Architectures Software Developer’s Manual – POPCNT instruction description.
요약
해밍 가중치는 이진 데이터에서 1의 개수를 나타내는 기본적인 측정값으로, 해밍 거리와 밀접히 연결되어 있다. 오류 정정, 암호 설계, 비트 연산 최적화 등 다양한 기술 분야에서 핵심적인 역할을 수행한다.
