블록 부호 이론에서, 해밍 거리(Hamming距離, 영어: Hamming distance)는 곱집합 위에 정의되는 거리 함수이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

해밍 거리
4-bit binary tesseract
4-bit binary tesseract for finding Hamming distance.
4-bit binary tesseract Hamming distance examples
Two example distances: 0100→1001 has distance 3; 0110→1110 has distance 1
분류문자열 유사성
자료 구조문자열
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도

정의

편집

다음이 주어졌다고 하자.

그렇다면, 곱집합   위에 다음과 같은 거리 함수를 줄 수 있다.

 

거리 함수  위의 해밍 거리라고 한다.

만약  아벨 군(예를 들어, 유한체)이라고 할 때,  해밍 무게(영어: Hamming weight)는 영벡터와의 해밍 거리이다.

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

역사

편집

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

각주

편집
  1. Hamming, Richard W. (1950년 4월). “Error detecting and error correcting codes”. 《Bell Labs Technical Journal》 (영어) 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. ISSN 1089-7089. 

같이 보기

편집

외부 링크

편집