해밍 거리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

정보 이론에서, 해밍 거리(해밍距離 , Hamming distance)를 제안했다. 컴퓨터 통신 등에서 문자열의 전송 도중 몇 글자에서 오류가 났나를 측정하는 방법 중 하나이다.

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

코딩 스킴에서의 해밍 거리[편집]

어떤 하나의 코딩 스킴 C가 C(n,k)로 쓰여질 수 있다고 가정하자. (k크기의 데이터를 n크기의 코드로 변경하는 코딩 스킴을 이야기한다.) 그리고 그 코딩 스킴 C가 모든 경우에 있어서 최대 s 개의 에러를 감지할 수 있다고 하면, 최소 해밍 거리는 다음과 같다.

dmin = s + 1.

또, 그러한 코딩 스킴 C가 모든 경우에 있어서 최대 s개의 에러를 교정할 수 있다고 하면, 최소 해밍 거리는 다음과 같다.

dmin = 2s + 1.

참고문헌[편집]

Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.