해밍 거리

3. 성질

고정된 길이 ''n''에 대해 해밍 거리는 길이 ''n''의 단어 집합(해밍 공간이라고도 함)에 대한 거리이며, 비음수성, 대칭성, 두 단어의 해밍 거리가 두 단어가 동일할 때만 0이 된다는 조건과 삼각 부등식을 충족한다.^[2] 실제로 세 단어 ''a'', ''b'', ''c''를 고정하면, ''a''의 ''i''번째 글자와 ''c''의 ''i''번째 글자 사이에 차이가 있을 때마다, ''a''의 ''i''번째 글자와 ''b''의 ''i''번째 글자 사이에 차이가 있거나, ''b''의 ''i''번째 글자와 ''c''의 ''i''번째 글자 사이에 차이가 있어야 한다. 따라서 ''a''와 ''c'' 사이의 해밍 거리는 ''a''와 ''b'' 사이의 해밍 거리와 ''b''와 ''c'' 사이의 해밍 거리의 합보다 크지 않다. 두 단어 ''a''와 ''b'' 사이의 해밍 거리는 적절한 − 연산자를 선택했을 때 ''a'' − ''b''의 해밍 가중치로 볼 수도 있으며, 이는 두 정수의 차이가 수직선에서 0으로부터의 거리로 볼 수 있는 것과 유사하다.

이진 문자열 ''a''와 ''b''의 경우, 해밍 거리는 ''a'' XOR ''b''의 1의 개수(개체수)와 같다. 해밍 거리가 있는 길이 ''n'' 이진 문자열의 거리 공간은 ''해밍 큐브''로 알려져 있다. 이는 하이퍼큐브 그래프에서 정점 간의 거리 집합과 거리 공간으로서 동일하다. 또한 길이 ''n''의 이진 문자열을 문자열의 각 기호를 실수 좌표로 취급하여 $\backslash mathbb\{R\}^\{n\}$의 벡터로 볼 수 있다. 이러한 임베딩을 사용하면 문자열은 ''n''차원 하이퍼큐브의 정점을 형성하며, 문자열의 해밍 거리는 정점 사이의 맨해튼 거리와 동일하다.

4. 예

• '''1011101'''과 '''1001001''' 사이의 해밍 거리는 2이다.
• '''2143896'''과 '''2233796''' 사이의 해밍 거리는 3이다.
• '''toned'''와 '''roses''' 사이의 해밍 거리는 3이다.

• '''karolin'''과 '''kathrin''' 사이는 3이다.
• '''karolin'''과 '''kerstin''' 사이는 3이다.
• '''kathrin'''과 '''kerstin''' 사이는 4이다.
• '''0000'''과 '''1111''' 사이는 4이다.
• '''2173896'''과 '''2233796''' 사이는 3이다.

5. 오류 검출 및 정정

부호 이론에서 최소 해밍 거리(''d_min''으로 표시)는 오류 검출 및 오류 정정 부호와 같은 몇 가지 필수 개념을 정의하는 데 사용된다. 특히, 부호 ''C''의 임의의 두 부호어 간의 최소 해밍 거리가 ''k''+1 이상인 경우에만 이 부호는 ''k'' 오류 검출 부호라고 한다.^[2]

예를 들어, "000"과 "111"의 두 부호어로 구성된 부호를 생각해 보자. 이 두 단어 간의 해밍 거리는 3이므로, 이 부호는 ''k''=2 오류 검출 부호이다. 이는 1비트 또는 2비트가 뒤집히면 오류를 감지할 수 있음을 의미한다. 3비트가 뒤집히면 "000"은 "111"이 되고 오류를 감지할 수 없다.

부호 ''C''는 기본 해밍 공간 ''H''의 모든 단어 ''w''에 대해, ''w''와 ''c'' 간의 해밍 거리가 최대 ''k''인 부호어 ''c'' (''C''에서)가 최대 하나 존재하는 경우 ''k-오류 정정'' 부호라고 한다. 즉, 임의의 두 부호어 간의 최소 해밍 거리가 2''k''+1 이상인 경우 부호는 ''k''-오류 정정 부호이다. 이는 또한 서로 다른 부호어를 중심으로 하는 반경 ''k''의 모든 닫힌 구가 서로 소라는 기하학적 의미로 이해된다.^[2] 이 맥락에서 이러한 구는 ''해밍 구''라고도 한다.^[3]

예를 들어, 두 부호어 "000"과 "111"로 구성된 동일한 3비트 부호를 생각해 보자. 해밍 공간은 000, 001, 010, 011, 100, 101, 110 및 111의 8개 단어로 구성된다. 부호어 "000"과 단일 비트 오류 단어 "001", "010", "100"은 모두 "000"에 대한 해밍 거리가 1 이하이다. 마찬가지로, 부호어 "111"과 단일 비트 오류 단어 "110", "101" 및 "011"은 모두 원래의 "111"에서 1 해밍 거리 내에 있다. 이 부호에서 단일 비트 오류는 항상 원래 부호에서 1 해밍 거리 내에 있으며, 부호는 ''1-오류 정정''이 가능합니다. 즉, ''k=1''이다. "000"과 "111" 간의 해밍 거리가 3이고, 이들이 부호의 전체 부호어 집합을 구성하므로 최소 해밍 거리는 3이며, 이는 ''2k+1 = 3''을 만족한다.

따라서 부호어 간의 최소 해밍 거리 ''d''를 가진 부호는 최대 ''d''-1개의 오류를 감지할 수 있으며 ⌊(''d''-1)/2⌋개의 오류를 정정할 수 있다.^[2] 후자는 부호의 ''포장 반경'' 또는 ''오류 정정 능력''이라고도 한다.^[3]

6. 응용

해밍 거리는 1950년 리처드 해밍이 ''오류 감지 및 오류 정정 코드''라는 논문에서 소개한 개념이다.^[4] 해밍 가중치 분석은 정보 이론, 부호 이론, 암호학 등 여러 분야에서 사용된다.^[5]

해밍 거리는 통신에서 고정 길이 이진 단어에서 뒤집힌 비트 수를 세어 오류를 추정하는 데 사용되며, '''신호 거리'''라고도 불린다.^[6] 크기가 ''q'' ≥ 2 인 알파벳에 대한 ''q''-ary 문자열의 경우, 해밍 거리는 q-ary 대칭 채널에 적용된다. 반면 리 거리는 위상 편이 변조처럼 ±1의 오류를 고려하여 동기화 오류에 취약한 채널에 사용된다.^[7] $q\; =\; 2$ 또는 $q\; =\; 3$일 때는 $\backslash mathbb\{Z\}/2\backslash mathbb\{Z\}$ 또는 $\backslash mathbb\{Z\}/3\backslash mathbb\{Z\}$의 모든 요소 쌍이 1만큼 차이가 나기 때문에 두 거리가 일치하지만, $q$가 더 크면 거리가 달라진다.

해밍 거리는 계통학에서 유전적 거리를 측정하는 데에도 사용된다.^[8]

그러나 길이가 다른 문자열을 비교하거나, 단순한 글자 대치뿐 아니라 삽입, 삭제까지 고려해야 할 때는 레벤슈타인 거리와 같이 더 정교한 지표가 적합하다.

7. 역사

해밍 거리는 1950년 리처드 해밍이 그의 논문 《오류 감지 및 오류 정정 코드》에서 해밍 부호와 함께 도입하였다.^[9][4] 해밍 가중치 분석은 정보 이론, 부호 이론, 암호학을 포함한 여러 분야에서 사용된다.^[5]

통신에서 고정 길이 이진 단어에서 반전된 비트 수를 오류 추정치로 계산하는 데 사용되며, 때때로 '''신호 거리'''라고도 불린다.^[6] 크기가 ''q'' ≥ 2인 알파벳에 대한 ''q''-ary 문자열의 경우, 해밍 거리는 q-ary 대칭 채널의 경우에 적용되는 반면, 리 거리는 위상 편이 변조 또는 일반적으로 ±1의 오류를 고려하기 때문에 동기화 오류에 취약한 채널에 사용된다.^[7] q = 2 또는 q = 3인 경우, \mathbb{Z}/2\mathbb{Z} 또는 \mathbb{Z}/3\mathbb{Z}의 모든 요소 쌍은 1만큼 다르기 때문에 두 거리가 일치하지만, 더 큰 q에서는 거리가 다르다.

해밍 거리는 계통학에서 유전적 거리를 측정하는 데에도 사용된다.^[8]

그러나 길이가 다른 문자열을 비교하거나, 단순한 대치뿐만 아니라 삽입 또는 삭제도 예상되는 문자열을 비교하려면 레벤슈타인 거리와 같은 더 정교한 지표가 더 적합하다.

8. 알고리즘 예제 (Python)

python

def hamming_distance(string1: str, string2: str) -> int:

"""두 문자열 간의 해밍 거리를 반환한다."""

if len(string1) != len(string2):

raise ValueError("문자열의 길이가 같아야 한다.")

dist_counter = 0

for n in range(len(string1)):

if string1[n] != string2[n]:

dist_counter += 1

return dist_counter

```

더 짧은 표현:

```python

sum(char1 != char2 for char1, char2 in zip(string1, string2, strict=True))

```

파이썬 3으로 구현된 함수 `hamming_distance()`는 두 개의 길이가 같은 문자열(또는 다른 반복 가능한 객체) 간의 해밍 거리를 계산한다. 이는 두 입력의 해당 위치 간의 불일치 및 일치를 나타내는 부울 값의 시퀀스를 생성한 다음, 각각 1과 0으로 해석되는 True 및 False 값의 시퀀스를 합산하여 수행된다.

```python

def hamming_distance(s1: str, s2: str) -> int:

"""길이가 같은 시퀀스 간의 해밍 거리를 반환한다."""

if len(s1) != len(s2):

raise ValueError("길이가 다른 시퀀스에는 정의되지 않는다.")

return sum(char1 != char2 for char1, char2 in zip(s1, s2))

```

[https://docs.python.org/3/library/functions.html#zip zip()] 함수는 두 개의 길이가 같은 컬렉션을 쌍으로 병합한다.

9. 알고리즘 예제 (C)

c

int hamming_distance(unsigned x, unsigned y)

{

int dist = 0;

// ^ 연산자는 다른 비트만 1로 설정합니다.

for (unsigned val = x ^ y; val > 0; ++dist)

{

// 그런 다음 피터 베그너 방식으로 1로 설정된 비트를 계산합니다.

val = val & (val - 1); // val의 최하위 1을 0으로 설정합니다.

}

// 다른 비트의 수를 반환합니다.

return dist;

}

```

이 C 함수는 두 정수 간의 해밍 거리를 계산한다. (이진 값, 즉 비트 시퀀스로 간주). 이 함수의 실행 시간은 입력에 있는 비트 수가 아닌 해밍 거리에 비례한다. 두 입력의 비트 XOR 연산을 한 뒤, 베그너(Wegner)의 알고리즘<sup>[1]</sup>을 사용하여 결과의 해밍 가중치(0이 아닌 비트 수)를 찾는다. 이 알고리즘은 최하위 0이 아닌 비트를 반복적으로 찾아 지운다. 일부 컴파일러는 사용 가능한 경우 특수 프로세서 하드웨어를 사용하여 이를 계산할 수 있는 `__builtin_popcount` 함수를 지원한다.

더 빠른 방법은 모집단 수 (''popcount'') 어셈블리 명령을 사용하는 것이다. GCC 및 Clang과 같은 특정 컴파일러는 내장 함수를 통해 이를 사용할 수 있다.

```c

// 32비트 정수의 해밍 거리

int hamming_distance32(unsigned int x, unsigned int y)

{

return __builtin_popcount(x ^ y);

}

// 64비트 정수의 해밍 거리

int hamming_distance64(unsigned long long x, unsigned long long y)

{

return __builtin_popcountll(x ^ y);

}

```

참조

_[1] 서적 Pulse Code Modulation Techniques https://books.google[...] Springer 2020-06-13
_[2] 서적 An Introduction to Abstract Algebra Walter de Gruyter 2003
_[3] 서적 Covering Codes Elsevier 1997
_[4] 저널 Error detecting and error correcting codes https://calhoun.nps.[...] 1950-04
_[5] 서적 Applied Cryptography and Network Security Springer 2009
_[6] 서적 Integrated Circuit and System Design Springer Science+Business Media 2012
_[7] 서적 Introduction to Coding Theory Cambridge University Press 2006
_[8] 저널 Inferring HIV Transmission Dynamics from Phylogenetic Sequence Relationships 2008-03-18
_[9] 저널 Error detecting and error correcting codes 1950-04