해밍 거리 (Hamming Distance)

해밍 거리(Hamming Distance)는 같은 길이의 두 이진 수열 간의 차이 또는 “거리”를 측정하는 값으로, 특히 두 수열에서 서로 다른 비트의 개수를 의미합니다. 이는 두 수열의 배타적 논리합(XOR) 결과에서 1인 비트의 개수(해밍 가중치)와 같습니다.

작동 방식:

기본적으로 해밍 거리는 두 이진 수열이 일치하지 않는 위치의 개수를 계산합니다.

• 비트 단위 비교: 두 이진 수열을 정렬하고 각 대응 비트 쌍을 비교합니다.
• 차이 계산: 쌍의 비트가 일치하면 계속 진행합니다. 비트가 다르면(하나는 0이고 다른 하나는 1) 계산값을 증가시킵니다.
• 결과: 다른 비트의 총 개수가 해밍 거리입니다. 이 숫자는 한 수열을 다른 수열로 바꾸기 위해 뒤집어야 하는 비트의 개수를 나타냅니다.

예를 들어 다음 두 수열을 비교해 보겠습니다.

• 수열 1: 10101
• 수열 2: 11001

두 수열을 비트 단위로 비교하면 두 번째와 세 번째 위치에서 다르다는 것을 알 수 있습니다. 따라서 두 수열 간의 해밍 거리는 2입니다.

왜 중요합니까?

• 오류 감지: 해밍 거리는 데이터 전송 중 발생할 수 있는 오류를 식별하는 데 도움이 됩니다. 보낸 데이터와 받은 데이터 사이의 거리는 손상된 비트의 개수를 뜻합니다.
• 유사도 판단: 해밍 거리가 작을수록 두 수열이 비슷하며, 코드워드 설계와 암호 알고리즘 평가의 기준이 됩니다(아래 ‘실제 해밍 거리’ 참고).

장점:

• 단순성: 이해하고 구현하기 쉬우며 계산 효율이 높습니다.
• 다양성: 코딩 이론, 암호화, 심지어 유전학과 같은 다양한 분야에 적용 가능합니다.
• 오류 감지 및 수정: 데이터 전송에서 오류를 식별하고 수정하는 데 효과적입니다.

단점:

• 범위 제한: 길이가 같은 수열에만 적용할 수 있습니다(이진 수열뿐 아니라 같은 길이의 문자열에도 쓰입니다). 길이가 다르거나 문자가 삽입·삭제된 경우에는 편집 거리(레벤슈타인 거리) 같은 다른 척도가 필요합니다.
• 수열 길이에 대한 민감도: 같은 거리라도 수열 길이에 따라 의미가 달라지므로, 길이에 대한 비율로 해석해야 할 때가 있습니다.

실제 해밍 거리:

다양한 분야에서 해밍 거리가 쓰이는 방식을 간략하게 살펴보겠습니다.

1. 코딩 이론: 오류 수정 코드를 설계할 때 기준이 됩니다. 코드워드 사이의 최소 해밍 거리가 d이면 최대 d−1개의 비트 오류를 감지하고, 최대 ⌊(d−1)/2⌋개의 오류를 수정할 수 있습니다.
2. 암호화: 암호화 알고리즘이나 해시 함수의 애벌랜치 효과를 측정하는 데 쓰입니다. 잘 설계된 알고리즘에서는 입력의 1비트만 바꿔도 출력 비트의 약 절반이 바뀝니다. 다만 두 수열의 해밍 거리가 크다고 해서 암호의 보안이 강하다는 뜻은 아닙니다.
3. 유전학: DNA 서열을 기반으로 개인 간의 유전적 차이를 정량화합니다.

해밍 거리는 이진 데이터의 차이를 측정하는 간단한 방법으로, 코딩 이론·암호학·생물정보학 등 여러 분야에서 쓰입니다.