해밍 거리로 데이터 차이와 오류를 판별하는 방법

같은 길이의 데이터가 얼마나 다른지 재는 기준

해밍 거리(Hamming Distance)는 길이가 같은 두 문자열이나 데이터 워드를 비교할 때, 값이 다른 위치의 개수를 나타낸다. 이진 데이터라면 두 값에 XOR 연산을 적용한 뒤 결과에서 1이 몇 개인지 세는 방식으로 구할 수 있다.

리차드 해밍(Richard Hamming)이 1950년대에 개발한 이 개념은 오류 검출과 오류 정정 코드의 기반이 되며, 문자열과 이진 데이터의 유사성을 다루는 여러 문제에도 쓰인다.

1011101과 1001001은 두 위치에서 다르므로 해밍 거리가 2다.

   1011101
   1001001
   -------
XOR 0010100  (1의 개수: 2)

거리 함수로서 만족해야 할 조건

해밍 거리는 단순한 차이 개수이면서 거리 함수의 성질도 갖는다.

• 양수성(Non-negativity): d(x, y) ≥ 0
  • 해밍 거리는 항상 0 이상이다.
• 동일성(Identity): d(x, y) = 0 ⟺ x = y
  • 거리가 0이면 두 문자열은 완전히 같다.
• 대칭성(Symmetry): d(x, y) = d(y, x)
  • 비교 방향을 바꿔도 거리는 변하지 않는다.
• 삼각부등식(Triangle Inequality): d(x, z) ≤ d(x, y) + d(y, z)
  • 두 데이터의 직접 거리는 다른 데이터를 경유한 거리의 합보다 길지 않다.

이 성질 덕분에 해밍 거리는 이진 데이터와 문자열을 비교하는 유사성 지표로 사용할 수 있다.

오류 검출과 정정에 쓰이는 최소 거리

전송 중 발생한 비트 오류를 다루는 코드에서는 코드워드 사이의 최소 해밍 거리가 기준이 된다.

⤢✕

해밍 코드(Hamming Code)는 1비트 오류를 검출하고 정정할 수 있는 코드 체계다. 최소 해밍 거리가 d인 코드는 d-1개 비트 오류까지 검출할 수 있고, 최소 해밍 거리가 2t+1인 코드는 t개 비트 오류까지 정정할 수 있다.

해밍 거리는 다음 영역에서도 비교 기준으로 활용된다.

• 정보 검색과 문서 유사도 측정, 검색 엔진의 철자 오류 교정, 표절 검사
• DNA 서열 비교, 유전자 변이 검출, 진화적 거리 계산
• 데이터 압축 알고리즘의 효율성 측정, 암호 시스템 강도 평가, 해시 함수 충돌 저항성 분석

XOR로 해밍 거리 계산하기

이진 문자열 A와 B의 해밍 거리는 A ⊕ B를 계산한 뒤 결과의 1 개수를 세면 된다.

A = "10101100"
B = "11001010"
A ⊕ B = "01100110" (1의 개수: 4)

따라서 이 두 문자열의 해밍 거리는 4다.

Python에서는 같은 위치의 문자를 순서대로 비교해 구현할 수 있다.

def hamming_distance(str1, str2):
    """두 문자열 간의 해밍 거리를 계산합니다."""
    if len(str1) != len(str2):
        raise ValueError("문자열의 길이가 같아야 합니다.")

    return sum(c1 != c2 for c1, c2 in zip(str1, str2))

# 이진 문자열 예시
binary_str1 = "10101100"
binary_str2 = "11001010"
print(f"해밍 거리: {hamming_distance(binary_str1, binary_str2)}")  # 출력: 4

# 일반 문자열 예시
str1 = "karolin"
str2 = "kathrin"
print(f"해밍 거리: {hamming_distance(str1, str2)}")  # 출력: 3

정수는 XOR 결과를 이진 문자열로 바꾼 뒤 1의 수를 계산할 수 있다.

def hamming_distance_int(x, y):
    """두 정수 간의 해밍 거리를 계산합니다."""
    # XOR 연산 후 1의 개수 계산
    return bin(x ^ y).count('1')

# 예시
print(f"해밍 거리: {hamming_distance_int(25, 30)}")  # 25(11001)와 30(11110) 사이의 해밍 거리: 3

패리티 비트로 오류 위치를 찾는 해밍 코드

해밍 코드는 데이터 비트에 패리티 비트를 추가하고, 수신한 코드워드의 신드롬을 계산해 오류 위치를 찾는다.

⤢✕

패리티 비트는 데이터 비트에 추가되며, 위치는 2^r로 정한다. 여기서 r은 패리티 비트의 인덱스다. 각 패리티 비트는 지정된 데이터 비트 집합의 패리티를 확인한다.

(7,4) 해밍 코드는 4비트 데이터를 7비트 코드워드로 인코딩한다. 데이터 비트는 D₁, D₂, D₃, D₄이고 패리티 비트는 P₁, P₂, P₃이다.

코드워드는 P₁, P₂, D₁, P₃, D₂, D₃, D₄ 순서로 구성한다.

• P₁ = D₁ ⊕ D₂ ⊕ D₄
• P₂ = D₁ ⊕ D₃ ⊕ D₄
• P₃ = D₂ ⊕ D₃ ⊕ D₄

수신 단계에서는 각 패리티 비트를 검사해 오류 위치를 식별한다.

기본 해밍 코드가 다루기 어려운 오류

기본 해밍 코드는 단일 오류 정정에 제약이 있고, 연속된 오류인 버스트 오류에 취약하다. 코드워드가 길어질수록 계산 복잡성도 증가한다.

이 한계를 보완하는 코드로는 다중 오류 정정이 가능한 리드-솔로몬 코드, 여러 비트 오류를 처리할 수 있는 순환 코드인 BCH 코드, 연속 데이터 스트림에 적용하는 콘볼루션 코드가 있다.

데이터 관리와 시스템 비교 작업에서의 의미

해밍 거리는 저장과 전송 과정에서 데이터가 변형됐는지 확인하는 데 쓰인다. 유사 검색과 오타 교정 알고리즘, 분산 시스템 노드 간 데이터 일관성 점검, 데이터베이스의 유사 레코드 식별과 통합에도 적용할 수 있다.

금융 시스템은 트랜잭션 데이터 전송 과정에서 해밍 코드를 적용해 오류를 검출하고 정정함으로써 데이터 무결성을 보장한다. SSD와 HDD의 ECC(Error Correction Code) 구현에서도 해밍 거리 기반 알고리즘을 사용해 저장 매체의 신뢰성을 높인다. 이미지 인식에서는 특징 벡터 사이의 유사도를 해밍 거리로 측정해 패턴 분류 정확도를 높일 수 있다.