데이터 간의 거리 측정 방법, 해밍 거리(2022, 고3, 10월)

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

 

 

일반적으로 거리는 두 개의 지점이 공간적으로 ⓐ 떨어진 정도를 나타내는 물리적 개념이다. 2차원 평면에 두 지점이 (0, 0)과 (1, 1)에 있다면 두 지점 사이의 최단 거리는 두 점을 잇는 직선의 길이 √2가 된다. 한편 거리는 추상적인 성질이나 가치에 대한 차이를 나타내는 척도로도 사용될 수 있다. 이럴 경우 떨어진 정도를 나타내는 기능은 유지되지만, 기준이나 관점에 따라 거리를 계산하는 방법이 달라진다.

 

거리의 개념은 디지털 데이터에도 적용될 수 있다. 데이터 간의 거리는 추상적 거리의 개념으로, 데이터가 표현하려는 정보에 따라 측정 방법이 다르다. 00, 11과 같은 2비트의 데이터가 2진수로 표현된 수치를 가리킨다면 00과 11의 거리는 두 수치의 차인 | ( 0 × 2¹ + 0 × 2⁰ ) - ( 1 × 2¹ + 1 × 2⁰ ) | = 3 이 된다.

 

그런데 2비트의 데이터 00이나 11이 어떤 상태를 나타내는 부호라면 거리는 두 부호가 구별되는 정도라 할 수 있다. 해밍 거리는 부호의 관점에서 부호들 간의 거리를 표현하는 방법 중 하나이다. 해밍 거리는 길이가 같은 두 부호를 비교하였을 때 두 부호의 같은 자리에 있는 서로 다른 문자의 개수로 나타낸다. 예를 들어 세 개의 부호 00, 01, 11이 있다면 00과 01의 해밍 거리는 1이고, 00과 11의 해밍 거리는 2이다. 이때 부호들 간의 최소 해밍 거리는 1이고, 최대 해밍 거리는 2이다.

 

부호들 간의 최소 해밍 거리를 충분히 멀게 한다면 통신이나 저장 과정에서 발생하는 오류를 검출하여 수정할 수 있다. 예를 들어 전송하려는 1비트의 원시 부호 0과 1이 있고 부호 단위로 송수신한다고 가정해 보자. 송신자가 1을 보낸다면 수신자는 0이나 1 중 하나를 받게 될 것이고, 송신자가 어떤 데이터를 보냈는지 알 수 없기 때문에 오류가 발생하더라도 오류가 있는지 알 수 없다. 이 경우 부호들 간의 최소 해밍 거리는 1이다. 0이나 1을 송수신하는 대신 원시 부호(x) 뒤에 확인 부호(p)를 덧붙여 x p에 해당하는 2비트 단위의 전송 부호를 만들어 보자. ㉠ 전송 부호는 고정된 원시 부호에 확인 부호를 덧붙이고, 확인 부호는 원시 부호에 대한 1의 개수가 짝수가 되도록 만든다는 규칙을 정한다면 전송 부호는 0 0과 1 1 이 된다. 만일 수신자가 0 1이나 1 0 중 하나를 받은 경우 전송 부호에 오류가 있음을 알 수 있다. 하지만 어느 자리에서 오류가 났는지 알 수 없기 때문에 오류를 수정할 수는 없다.

 

0 0이나 1 1을 송수신하는 대신 p와 동일한 규칙의 확인 부호(q)를 한 번 더 덧붙여 x p q에 해당하는 3비트 단위의 전송 부호 0 0 0과 1 1 1 중 하나를 송수신한다고 가정해 보자. 한 자리의 오류만 있다고 가정하면 수신자가 0 0 1, 0 1 0, 1 0 0, 0 1 1, 1 0 1, 1 1 0 중 하나를 받은 경우 오류 발생 자리를 검출하여 수정할 수 있다. 예를 들어 1 1 0의 경우 x인 1에 대해 p와 q는 각각 1이 되어야 1의 개수가 짝수가 되지만 q가 0이므로 1의 개수가 홀수이다. 따라서 오류 발생 자리를 검출하여 1 1 0을 1 1 1로 수정할 수 있다. 이 경우 전송 부호 간의 최소 해밍 거리가 3이어서 한 자리의 오류를 검출하여 수정할 수 있는 것이다.

 

원시 부호에 확인 부호를 충분히 덧붙이면 전송 부호의 길이는 길어지지만 전송 부호들 간의 최소 해밍 거리도 함께 멀어져 오류가 많이 발생하더라도 오류를 검출하여 수정하는 것이 가능하다. 하지만 동일한 정보를 보낼 때 덧붙이는 확인 부호의 개수가 늘어나면 보내야 하는 데이터의 양이 늘어나 전송 효율이 낮아진다.

 

 

@ 2022학년도 10월 고3 전국연합학력평가 14~17번^[각주:1]

(출전) Behrouz A. Forouzan, ‘데이터 통신과 네트워킹’

 

 

 

1. 지문은 맥락 없이 뜬금없이 시작되는 글이지만, 해설지를 보면 어떤 맥락에서 필요한 지식인지 다소 알 수 있게 해 주는 해설이 있어 아래에 인용한다.

   ❝

   우주를 탐사하는 우주선에서 지구로 데이터를 보내는 경우를 상상해 보자. 전송되는 과정 중 다양한 이유로 데이터에 오류가 발생하여 데이터가 왜곡될 수 있다. 우주선과의 통신이 자유로운 경우라면 데이터를 재전송하여 데이터 왜곡의 문제를 해결할 수 있지만 재전송이 불가능한 경우라면 왜곡된 데이터에서 오류를 검출하여 복구해야 할 것이다. 이때 데이터 간의 해밍 거리를 멀게 하면 데이터의 오류를 검출하여 복구할 수 있다. 해밍 거리는 길이가 같은 두 부호를 비교하였을 때 두 부호의 같은 자리에 있는 서로 다른 문자의 개수로, 데이터들이 서로 구별되는 정도를 나타낸다. 별을 관측할 때 서로 가까이 있는 두 별을 구별하는 것보다 멀리 떨어진 두 별을 구별하는 것이 더 쉬운 것과 마찬가지로, 비슷한 데이터를 구별하는 것보다 전혀 다른 데이터를 구별하는 것이 더 쉬울 것이다. 이런 원리에 의해 해밍 거리가 1인 0과 1을 구별할 때와 달리, 해밍 거리가 3인 000과 111을 구별할 때는 한 자리의 오류를 검출하여 수정할 수 있다. 하지만 해밍 거리를 멀게 하면 전송해야 하는 데이터의 양도 많아지는 단점이 있다. [본문으로]