해밍 거리

틀:위키데이터 속성 추적 틀:Infobox algorithm 블록 부호 이론에서, 해밍 거리(Hamming距離, 틀:Llang)는 곱집합 위에 정의되는 거리 함수이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

정의

다음이 주어졌다고 하자.

그렇다면, 곱집합 $S^{n}$ 위에 다음과 같은 거리 함수를 줄 수 있다.

d_{H} (s, t) = | {i \in {0, 1, \dots, n - 1} : s_{i} \neq t_{i}} | \in {0, 1, \dots, n}

이 거리 함수를 $S^{n}$ 위의 해밍 거리라고 한다.

만약 $(S, +, 0)$ 가 아벨 군(예를 들어, 유한체)이라고 할 때, $s \in S^{n}$ 의 해밍 무게(틀:Llang)는 영벡터와의 해밍 거리이다.

d_{H} (\vec{0}, s) = | {i \in {0, 1, \dots, n - 1} : s_{i} \neq 0} | \in {0, 1, \dots, n}

리처드 해밍이 1950년에 해밍 부호와 함께 도입하였다.^[1]