구독상품안내
디지털 통신에서는 모든 신호를 이진수로 바꾼 다음 그 부호를 통신선이나 전파에 실어 전송한다. 무선 통신 환경은 유선 통신에 비해 매우 불안하므로 전송 과정에서 오류가 발생할 수 있다. 이번호에서는 그 오류를 발견하고 수정하는 방법을 살펴보겠다.
Q1 다음 제시문을 읽고 물음에 답하라.
(가) 모든 n자리 이진수 문자열의 집합을 W라고 하자. 여기서 n자리 이진수 문자열이란 각 자리의 숫자가 위치에 관계없이 0이거나 1인 경우를 모두 포함한다. 다시 말해 000…000과 같이 0으로 시작하는 이진수 문자열도 포함하는 것으로 한다. n개의 자리가 있고 각 자리에 0 또는 1이 올 수 있으므로 W의 원소의 개수는 2n개다.
W의 두 원소 a와 b에 대해 H(a, b)를 ‘a와 b의 n개의 자리의 값을 가장 앞 자리부터 차례대로 하나씩 비교할 때 값이 서로 다른 자리의 개수’로 정의하고 이것을 a와 b의 해밍거리(Hamming distance)라고 부른다. 예를 들면 H(101011, 111000)=3, H(001000, 010011)=4이다.
(나) 집합 S에 대해 정의된 거리함수 d는 S×S={(a, b) a∈S, b∈S}를 정의역으로 하고 실수의 집합을 공역으로 하며 다음의 네 가지 조건을 만족하는 함수다.
(a) d(x, y)≥0
(b) d(x, y)=0이기 위한 필요충분조건은 x=y이다.
(c) d(x, y)=d(y, x)
(d) d(x, y)+d(y, z)≥d(x, z)
(다) 디지털 통신에서는 전송하려는 메시지를 이진수 문자열로 변환한 다음 전송한다. 전송하는 과정에서 오류가 없다면 문자열을 해독하는 데 문제가 없지만 실제로는 전송 과정에서 오류가 발생할 수도 있다. 즉 1을 보냈을 때 0을 받거나, 0을 보냈을 때 1을 받게 될 수도 있다. 어느 문자열의 한 자리를 바꿨을 때 이것이 또 다른 의미 있는 메시지를 표현하는 문자열이 된다면 받은 사람은 오류를 발견하지 못하고 엉뚱하게 해독할 수도 있을 것이다. 이러한 현상이 심각한 문제를 일으킬 수도 있으므로 통신이론 연구자들은 메시지를 문자열로 바꾸는 방식을 개선해 수신자가 스스로 전송 오류를 발견해내고 수정할 수 있는 방법을 발명해냈다. 이러한 방식을 오류 정정 부호화(Error correction coding)라고 부른다.
(라) 4자리의 이진수 문자열 d=d1d2d3d4가 있을 때 여기에 대해 3자리의 이진수 p1p2p3를 붙여d^=d1d2d3d4p1p2p3를 만들자. 이때 d1+d3+d4+p1, d1+d2+d4+p2, d2+d3+d4+p3가 모두 짝수가 되도록 p1, p2, p3를 0 또는 1로 정한다. 즉 <그림 1>에서 세 개의 원으로 둘러싸인 부분의 숫자의 합이 각각 짝수가 되게 한다.
예를 들어 이진수 문자열이 d=1101이라면 <그림 2>와 같다.
이때 원으로 둘러싸인 수의 합이 각각 짝수가 되려면 p1=0, p2=1, p3=0으로 정하면 된다. 즉 d로부터 d^=1101010을 만들어낸다. 이러한 방식을 해밍 부호화라고 부른다.
1) [난이도 하] 모든 n자리 이진수 문자열의 집합 W의 원소 가운데 하나를 p라고 하고, 이 p에 대해 Vp, k={x∈W|H(x, p)=k}라고 정의하자(단, k≤n). 이때 Vp, k의 원소의 개수를 n과 k에 대한 식으로 구하시오.
2) [난이도 중] W에 대해 정의된 해밍거리가 제시문 (나)의 거리함수의 조건을 만족함을 보이시오.
3) [난이도 상] 제시문 (라)의 방식으로 만들어진 모든 7자리 문자열의 집합을 Y라고 하자. Y의 임의의 서로 다른 두 원소 사이의 해밍거리는 3 이상임을 보이시오.
4) [난이도 상] 4자리 이진수 문자열 d를 제시문 (라)의 방식에 따라 7자리로 바꾼 것을 d^라고 하고 전송과정에서 오류가 발생해 문자열 d^에서 한 자리만 바뀐 것을 f^라고 하자. 이때 다음을 보이시오.
(a) f^∉Y
(b) f^와의 해밍거리가 가장 작은 Y의 원소는 d^뿐이다.
전문가 클리닉
지난 수십 년간 디지털 통신 기술은 비약적으로 발전했습니다. 요즘은 무선 환경을 통해서도 고속 데이터 통신을 할 수 있고 디지털 TV 방송을 시청할 수도 있습니다. 데이터를 전송할 때 발생하는 전송 오류를 해결하는 일은 통신 기술에서 아주 중요한 요소입니다. 따라서 전송 오류가 발생하는 것은 어쩔 수 없다고 하더라도 발생한 오류가 미치는 피해를 줄이는 방법이 필요합니다.
예를 들어, 학교 강당에 네 명의 학생이 모여 있습니다. ‘오영수’라는 학생을 찾으려고 이름을 불렀더니 모든 학생이 “예”하고 답했습니다. 그 학생들의 이름은 ‘오영수’, ‘우영수’, ‘오형수’, ‘오영주’였습니다. 이렇게 비슷하게 들릴 수 있는 이름을 가진 학생이 함께 있다면 다른 학생들이 자신의 이름으로 착각할 수도 있습니다. 만약 그곳에 있는 학생들의 이름이 ‘오영수’, ‘김철규’, ‘정병기’, ‘이 혁’이었다면 그런 일이 발생하지 않을 것입니다. 즉 메시지가 서로 비슷한지 아닌지에 따라 전송 오류가 미치는 영향력이 다릅니다. 이렇게 메시지의 비슷한 정도를 재는 방식으로 미국의 수학자 리처드 해밍이 고안해낸 것이 해밍거리입니다. 이번호에는 해밍거리의 원리와 응용에 대한 문제를 풀어보겠습니다.
1) 제시문의 정의와 수식 표현을 정확히 이해할 수 있는지를 평가하려는 문제입니다. Vp, k는 W의 원소 가운데 p와 k개의 자리의 값이 다른 것의 개수를 말하므로 이러한 원소를 어떻게 만들 수 있는가를 생각해보면 해결할 수 있습니다.
2) 거리함수의 정의를 정확히 이해하고 이것을 해밍거리에 적용할 수 있는지를 평가하려는 문제입니다. 제시문의 d(x, y)를 H(x, y)로 놓고 x, y를 두 개의 문자열로 생각해 풀어봅니다. (a)~(d)의 네 조건을 모두 검토해야 합니다.
3) 서로 다른 4자리 문자열 d, e를 제시문 (라)의 방식에 따라 7자리로 만든 것을 각각 d^, e^라고 할 때 H(d^, e^)가 항상 3 이상임을 보여야 합니다. H(d, e)가 1, 2, 3, 4인 경우로 나눠 H(d^, e^)가 어떻게 될까를 생각해봅니다.
4) 문제 3)의 결과를 사용해 문제 4)를 해결합니다. 원래 전송한 문자열 중 한 자리가 바뀐다면 그러한 문자열은 수신 가능한 문자열에 포함되지 않음을 보입니다. 또한 그렇게 변형된 문자열이 있다면 수신 가능한 문자열에는 그 문자열과 한 자리만 다른 문자열이 유일함을 보입니다.
예시답안
1) 집합 Vp, k는 W의 특정한 원소 p와 비교할 때 k개의 자리의 값이 다른 W의 원소들로 이뤄진 집합이다. 즉 Vp, k의 원소는 p의 n자리 중 k자리를 골라 그 자리의 값이 0이면 1로, 1이면 0으로 바꾼 것이다. 결국 n자리 중 k자리만 고르면 그 원소가 유일하게 결정되므로 Vp, k의 원소 개수는 nCk이다.
2) 해밍거리가 제시문(나)의 거리함수의 조건 네 가지를 만족하는 함수인지 다음과 같이 보일 수 있다.
(a) H(x, y)≥0
해밍거리는 문자열 x와 y의 n개의 자리 중 값이 서로 다른 자리의 개수이므로 음의 값이 될 수 없다.
(b) H(x, y)=0이기 위한 필요충분조건은 x=y이다.
x=y일때, 즉 문자열이 동일하면 모든 자리의 값이 서로 같으므로 H(x, y)=0이다.
H(x, y)=0이라면 x와 y의 각 자리의 값이 모두같다는 것을 의미한다. 즉 x=y이다.
(c) H(x, y)=H(y, x)
문자열 x와 y의 n개의 자리 중 값이 서로 다른 자리의 개수는 문자열 y와 x의 n개의 자리 중 값이 서로 다른 자리의 개수와 같다.
(d) H(x, y)+H(y, z)≥H(x, z)
세 문자열 x, y, z를 생각하자.
문자열 x와 z의 각 자리의 값을 비교할 때 서로 다른 것이 있을 때마다 H(x, z)가 1씩 늘어난다. 이렇게 어느 자리에서 문자열 x와 z의 값이 서로 다르다면 그 자리에서 x와 y의 값이 다르거나 y와 z의 값이 달라야 한다. 즉 H(x, z)가 1만큼 늘어나려면 반드시 H(x, y)가 1만큼 늘어나거나 H(y, z)가 1만큼 늘어나므로 H(x, y)+H(y, z)≥H(x, z)인 것을 알 수 있다.
3) 원래 전송할 메시지에 해당하는 4자리 문자열을 d=d1d2d3d4, 이것으로부터 만들어낸 7자리 문자열을 d^=d1d2d3d4p1p2p3라고 하자. d와는 다른 또 다른 문자열을 e=e1e2e3e4라고 하고 이것으로부터 만들어낸 7자리 문자열을 e^=e1e2e3e4q1q2q3라고 하자. d와 e는 서로 다른 문자열이므로 H(d, e)=0일 수는 없다. 만약 H(d, e)≥3이라면 d^와 e^의 첫 네 자리 중 적어도 세 자리 이상이 다르므로 H(d^, e^)≥3이다. 따라서 H(d, e)=1인 경우와 H(d, e)=2인 경우에도 H(d^, e^)≥3임을 보이면 된다.
(i) H(d, e)=1인 경우
두 문자열의 첫 자리가 다른 경우 d1≠e1이고 나머지 세 자리는 모두 같다. 제시문 (라)의 첫번째 그림에서 d1을 e1으로 바꿔 써보면 다음 그림과 같다.
이때 각각의 원에 포함된 수의 합이 짝수로 유지되는지를 조사해 p1, p2, p3의 값 중 바꿔줘야 할 것을 조사한다.
먼저 d1과 e1의 홀짝이 다르므로 e1을 포함한 두 원의 수의 합이 각각 홀수가 된다. 따라서 p1과 p2의 값을 바꿔줘야 한다. 즉 d1≠e1인 경우 q1≠p1, q2≠p2, q3=p3이다.
따라서 d^와 e^의 1, 5, 6번째 자리의 값이 다르므로 H(d^, e^)=3이다. 문자열 d와 e의 둘째 자리 또는 세 번째 자리가 다른 경우에도 첫 번째 자리가 다른 경우와 같은 방식으로 H(d^, e^)=3임을 보일 수 있다.
네 번째 자리가 다른 경우, 즉 d4≠e4인 경우 d4를 e4로 바꾼 그림은 다음과 같다.
e4는 모든 원에 포함되어 있으므로 세 개의 원 각각에 포함된 수의 합이 모두 홀수가 된다. 따라서 p1, p2, p3를 모두 바꿔야 한다. 즉 q1≠p1, q2≠p2, q3≠p3이다. d^와 e^의 4, 5, 6, 7번째 자리가 다르므로 H(d^, e^)=4이다.
(ii) H(d, e)=2인 경우
d의 네 자리 중 원의 중심에 쓰인 d4가 e4와 같은 경우와 서로 다른 경우로 나눠 생각하자.
㉠ e4=d4이면 H(d, e)=2이므로 d의 1, 2, 3번째 자리 중 두 개가 e와 달라야 한다. 먼저 e1≠d1, e2≠d2인 경우를 생각하자.
p1을 포함한 원에서는 e1의 홀짝이 d1과 다르고 수의 합이 홀이므로, q1≠p1이어야 한다. 마찬가지로 생각하면 q3≠p3이고 p2를 포함한 원에서는 e1의 홀짝이 d1과 다르고 e3의 홀짝이 d3와 다르므로 수의 합이 짝이다. 따라서 q2=p2이다. 즉 q1≠p1, q2=p2, q3≠p3이다. d^와 e^의 1, 2, 5, 7번째 자리가 다르므로 H(d^, e^)=4이다.
e1≠d1, e3≠d3인 경우와 e2≠d2, e3≠d3인 경우도 e1≠d1, e2≠d2인 경우와 같이 생각하면 H(d^, e^)=4가 됨을 알 수 있다.
㉡ e4≠d4이면 H(d, e)=2이므로 d의 1, 2, 3번째 자리 중 하나가 e와 달라야 한다. 먼저 e1≠d1인 경우를 생각하자.
p3를 포함한 원에서는 e4의 홀짝이 d4와 다르므로 수의 합이 홀이다. 따라서 q3≠p3이어야 한다. 한편 p1을 포함한 원에서는 e1의 홀짝이 d1과 다르고 e4의 홀짝이 d3와 다르므로 수의 합이 짝이다. 따라서 q1=p1이다. 마찬가지로 생각하면 q2=p2이다. d^와 e^의 1, 4, 7번째 자리가 다르므로 H(d^, e^)=3이다. e4≠d4이면서 e2≠d2이거나 e3≠d3인 경우도 e1≠d1인 경우와 같이 생각하면 H(d^, e^)=3임을 알 수 있다.
결국 (i), (ii)의 어느 경우든 H(d^, e^)≥3이 성립한다.
4) 다음과 같이 두 명제를 보일 수 있다.
(a) f^∉Y
먼저 d^는 4자리의 문자열을 제시문 (라)의 방식에 따라 7자리로 바꾼 것이므로 Y의 원소이다.
f^는 d^와 한 자리만 다른 문자열이므로 H(d^, f^)=1인데 논제 3)에 따라 Y의 두 원소의 해밍거리는 3 이상이어야 한다. 따라서 f^∉Y이다.
(b) f^와의 해밍거리가 가장 작은 Y의 원소는 d^뿐이다.
H(d^, f^)=1이므로 f^가 아닌 문자열 중 d^보다 더 가까운 것은 있을 수 없다. f^∉Y이므로 Y의 원소 중 d^보다 더 가까운 것은 없다.
이제 d^ 이외에 f^와의 해밍거리가 1인 Y의 원소가 없음을 보이자. 만약 해밍거리가 1인 d^가 아닌 원소가 있다면 그것을 e^라고 하자. 제시문 (나)의 (d)에 따라 H(d^, e^)≤H(d^, f^)+H(f^, e^)=1+1=2이므로 H(d^, e^)는 2 이하의 값이다. 하지만 Y의 서로 다른 두 원소의 거리는 3 이상이므로 이것은 모순이다. 1
Q1 다음 제시문을 읽고 물음에 답하라.
(가) 모든 n자리 이진수 문자열의 집합을 W라고 하자. 여기서 n자리 이진수 문자열이란 각 자리의 숫자가 위치에 관계없이 0이거나 1인 경우를 모두 포함한다. 다시 말해 000…000과 같이 0으로 시작하는 이진수 문자열도 포함하는 것으로 한다. n개의 자리가 있고 각 자리에 0 또는 1이 올 수 있으므로 W의 원소의 개수는 2n개다.
W의 두 원소 a와 b에 대해 H(a, b)를 ‘a와 b의 n개의 자리의 값을 가장 앞 자리부터 차례대로 하나씩 비교할 때 값이 서로 다른 자리의 개수’로 정의하고 이것을 a와 b의 해밍거리(Hamming distance)라고 부른다. 예를 들면 H(101011, 111000)=3, H(001000, 010011)=4이다.
(나) 집합 S에 대해 정의된 거리함수 d는 S×S={(a, b) a∈S, b∈S}를 정의역으로 하고 실수의 집합을 공역으로 하며 다음의 네 가지 조건을 만족하는 함수다.
(a) d(x, y)≥0
(b) d(x, y)=0이기 위한 필요충분조건은 x=y이다.
(c) d(x, y)=d(y, x)
(d) d(x, y)+d(y, z)≥d(x, z)
(다) 디지털 통신에서는 전송하려는 메시지를 이진수 문자열로 변환한 다음 전송한다. 전송하는 과정에서 오류가 없다면 문자열을 해독하는 데 문제가 없지만 실제로는 전송 과정에서 오류가 발생할 수도 있다. 즉 1을 보냈을 때 0을 받거나, 0을 보냈을 때 1을 받게 될 수도 있다. 어느 문자열의 한 자리를 바꿨을 때 이것이 또 다른 의미 있는 메시지를 표현하는 문자열이 된다면 받은 사람은 오류를 발견하지 못하고 엉뚱하게 해독할 수도 있을 것이다. 이러한 현상이 심각한 문제를 일으킬 수도 있으므로 통신이론 연구자들은 메시지를 문자열로 바꾸는 방식을 개선해 수신자가 스스로 전송 오류를 발견해내고 수정할 수 있는 방법을 발명해냈다. 이러한 방식을 오류 정정 부호화(Error correction coding)라고 부른다.
(라) 4자리의 이진수 문자열 d=d1d2d3d4가 있을 때 여기에 대해 3자리의 이진수 p1p2p3를 붙여d^=d1d2d3d4p1p2p3를 만들자. 이때 d1+d3+d4+p1, d1+d2+d4+p2, d2+d3+d4+p3가 모두 짝수가 되도록 p1, p2, p3를 0 또는 1로 정한다. 즉 <그림 1>에서 세 개의 원으로 둘러싸인 부분의 숫자의 합이 각각 짝수가 되게 한다.
예를 들어 이진수 문자열이 d=1101이라면 <그림 2>와 같다.
이때 원으로 둘러싸인 수의 합이 각각 짝수가 되려면 p1=0, p2=1, p3=0으로 정하면 된다. 즉 d로부터 d^=1101010을 만들어낸다. 이러한 방식을 해밍 부호화라고 부른다.
1) [난이도 하] 모든 n자리 이진수 문자열의 집합 W의 원소 가운데 하나를 p라고 하고, 이 p에 대해 Vp, k={x∈W|H(x, p)=k}라고 정의하자(단, k≤n). 이때 Vp, k의 원소의 개수를 n과 k에 대한 식으로 구하시오.2) [난이도 중] W에 대해 정의된 해밍거리가 제시문 (나)의 거리함수의 조건을 만족함을 보이시오.
3) [난이도 상] 제시문 (라)의 방식으로 만들어진 모든 7자리 문자열의 집합을 Y라고 하자. Y의 임의의 서로 다른 두 원소 사이의 해밍거리는 3 이상임을 보이시오.
4) [난이도 상] 4자리 이진수 문자열 d를 제시문 (라)의 방식에 따라 7자리로 바꾼 것을 d^라고 하고 전송과정에서 오류가 발생해 문자열 d^에서 한 자리만 바뀐 것을 f^라고 하자. 이때 다음을 보이시오.
(a) f^∉Y
(b) f^와의 해밍거리가 가장 작은 Y의 원소는 d^뿐이다.
전문가 클리닉
지난 수십 년간 디지털 통신 기술은 비약적으로 발전했습니다. 요즘은 무선 환경을 통해서도 고속 데이터 통신을 할 수 있고 디지털 TV 방송을 시청할 수도 있습니다. 데이터를 전송할 때 발생하는 전송 오류를 해결하는 일은 통신 기술에서 아주 중요한 요소입니다. 따라서 전송 오류가 발생하는 것은 어쩔 수 없다고 하더라도 발생한 오류가 미치는 피해를 줄이는 방법이 필요합니다.
예를 들어, 학교 강당에 네 명의 학생이 모여 있습니다. ‘오영수’라는 학생을 찾으려고 이름을 불렀더니 모든 학생이 “예”하고 답했습니다. 그 학생들의 이름은 ‘오영수’, ‘우영수’, ‘오형수’, ‘오영주’였습니다. 이렇게 비슷하게 들릴 수 있는 이름을 가진 학생이 함께 있다면 다른 학생들이 자신의 이름으로 착각할 수도 있습니다. 만약 그곳에 있는 학생들의 이름이 ‘오영수’, ‘김철규’, ‘정병기’, ‘이 혁’이었다면 그런 일이 발생하지 않을 것입니다. 즉 메시지가 서로 비슷한지 아닌지에 따라 전송 오류가 미치는 영향력이 다릅니다. 이렇게 메시지의 비슷한 정도를 재는 방식으로 미국의 수학자 리처드 해밍이 고안해낸 것이 해밍거리입니다. 이번호에는 해밍거리의 원리와 응용에 대한 문제를 풀어보겠습니다.
1) 제시문의 정의와 수식 표현을 정확히 이해할 수 있는지를 평가하려는 문제입니다. Vp, k는 W의 원소 가운데 p와 k개의 자리의 값이 다른 것의 개수를 말하므로 이러한 원소를 어떻게 만들 수 있는가를 생각해보면 해결할 수 있습니다.
2) 거리함수의 정의를 정확히 이해하고 이것을 해밍거리에 적용할 수 있는지를 평가하려는 문제입니다. 제시문의 d(x, y)를 H(x, y)로 놓고 x, y를 두 개의 문자열로 생각해 풀어봅니다. (a)~(d)의 네 조건을 모두 검토해야 합니다.
3) 서로 다른 4자리 문자열 d, e를 제시문 (라)의 방식에 따라 7자리로 만든 것을 각각 d^, e^라고 할 때 H(d^, e^)가 항상 3 이상임을 보여야 합니다. H(d, e)가 1, 2, 3, 4인 경우로 나눠 H(d^, e^)가 어떻게 될까를 생각해봅니다.
4) 문제 3)의 결과를 사용해 문제 4)를 해결합니다. 원래 전송한 문자열 중 한 자리가 바뀐다면 그러한 문자열은 수신 가능한 문자열에 포함되지 않음을 보입니다. 또한 그렇게 변형된 문자열이 있다면 수신 가능한 문자열에는 그 문자열과 한 자리만 다른 문자열이 유일함을 보입니다.
예시답안
1) 집합 Vp, k는 W의 특정한 원소 p와 비교할 때 k개의 자리의 값이 다른 W의 원소들로 이뤄진 집합이다. 즉 Vp, k의 원소는 p의 n자리 중 k자리를 골라 그 자리의 값이 0이면 1로, 1이면 0으로 바꾼 것이다. 결국 n자리 중 k자리만 고르면 그 원소가 유일하게 결정되므로 Vp, k의 원소 개수는 nCk이다.
2) 해밍거리가 제시문(나)의 거리함수의 조건 네 가지를 만족하는 함수인지 다음과 같이 보일 수 있다.
(a) H(x, y)≥0
해밍거리는 문자열 x와 y의 n개의 자리 중 값이 서로 다른 자리의 개수이므로 음의 값이 될 수 없다.
(b) H(x, y)=0이기 위한 필요충분조건은 x=y이다.
x=y일때, 즉 문자열이 동일하면 모든 자리의 값이 서로 같으므로 H(x, y)=0이다.
H(x, y)=0이라면 x와 y의 각 자리의 값이 모두같다는 것을 의미한다. 즉 x=y이다.
(c) H(x, y)=H(y, x)
문자열 x와 y의 n개의 자리 중 값이 서로 다른 자리의 개수는 문자열 y와 x의 n개의 자리 중 값이 서로 다른 자리의 개수와 같다.
(d) H(x, y)+H(y, z)≥H(x, z)
세 문자열 x, y, z를 생각하자.
문자열 x와 z의 각 자리의 값을 비교할 때 서로 다른 것이 있을 때마다 H(x, z)가 1씩 늘어난다. 이렇게 어느 자리에서 문자열 x와 z의 값이 서로 다르다면 그 자리에서 x와 y의 값이 다르거나 y와 z의 값이 달라야 한다. 즉 H(x, z)가 1만큼 늘어나려면 반드시 H(x, y)가 1만큼 늘어나거나 H(y, z)가 1만큼 늘어나므로 H(x, y)+H(y, z)≥H(x, z)인 것을 알 수 있다.
3) 원래 전송할 메시지에 해당하는 4자리 문자열을 d=d1d2d3d4, 이것으로부터 만들어낸 7자리 문자열을 d^=d1d2d3d4p1p2p3라고 하자. d와는 다른 또 다른 문자열을 e=e1e2e3e4라고 하고 이것으로부터 만들어낸 7자리 문자열을 e^=e1e2e3e4q1q2q3라고 하자. d와 e는 서로 다른 문자열이므로 H(d, e)=0일 수는 없다. 만약 H(d, e)≥3이라면 d^와 e^의 첫 네 자리 중 적어도 세 자리 이상이 다르므로 H(d^, e^)≥3이다. 따라서 H(d, e)=1인 경우와 H(d, e)=2인 경우에도 H(d^, e^)≥3임을 보이면 된다.
(i) H(d, e)=1인 경우
두 문자열의 첫 자리가 다른 경우 d1≠e1이고 나머지 세 자리는 모두 같다. 제시문 (라)의 첫번째 그림에서 d1을 e1으로 바꿔 써보면 다음 그림과 같다.이때 각각의 원에 포함된 수의 합이 짝수로 유지되는지를 조사해 p1, p2, p3의 값 중 바꿔줘야 할 것을 조사한다.
먼저 d1과 e1의 홀짝이 다르므로 e1을 포함한 두 원의 수의 합이 각각 홀수가 된다. 따라서 p1과 p2의 값을 바꿔줘야 한다. 즉 d1≠e1인 경우 q1≠p1, q2≠p2, q3=p3이다.
따라서 d^와 e^의 1, 5, 6번째 자리의 값이 다르므로 H(d^, e^)=3이다. 문자열 d와 e의 둘째 자리 또는 세 번째 자리가 다른 경우에도 첫 번째 자리가 다른 경우와 같은 방식으로 H(d^, e^)=3임을 보일 수 있다.
네 번째 자리가 다른 경우, 즉 d4≠e4인 경우 d4를 e4로 바꾼 그림은 다음과 같다.
e4는 모든 원에 포함되어 있으므로 세 개의 원 각각에 포함된 수의 합이 모두 홀수가 된다. 따라서 p1, p2, p3를 모두 바꿔야 한다. 즉 q1≠p1, q2≠p2, q3≠p3이다. d^와 e^의 4, 5, 6, 7번째 자리가 다르므로 H(d^, e^)=4이다.(ii) H(d, e)=2인 경우
d의 네 자리 중 원의 중심에 쓰인 d4가 e4와 같은 경우와 서로 다른 경우로 나눠 생각하자.
㉠ e4=d4이면 H(d, e)=2이므로 d의 1, 2, 3번째 자리 중 두 개가 e와 달라야 한다. 먼저 e1≠d1, e2≠d2인 경우를 생각하자.
p1을 포함한 원에서는 e1의 홀짝이 d1과 다르고 수의 합이 홀이므로, q1≠p1이어야 한다. 마찬가지로 생각하면 q3≠p3이고 p2를 포함한 원에서는 e1의 홀짝이 d1과 다르고 e3의 홀짝이 d3와 다르므로 수의 합이 짝이다. 따라서 q2=p2이다. 즉 q1≠p1, q2=p2, q3≠p3이다. d^와 e^의 1, 2, 5, 7번째 자리가 다르므로 H(d^, e^)=4이다.
e1≠d1, e3≠d3인 경우와 e2≠d2, e3≠d3인 경우도 e1≠d1, e2≠d2인 경우와 같이 생각하면 H(d^, e^)=4가 됨을 알 수 있다.
㉡ e4≠d4이면 H(d, e)=2이므로 d의 1, 2, 3번째 자리 중 하나가 e와 달라야 한다. 먼저 e1≠d1인 경우를 생각하자.
p3를 포함한 원에서는 e4의 홀짝이 d4와 다르므로 수의 합이 홀이다. 따라서 q3≠p3이어야 한다. 한편 p1을 포함한 원에서는 e1의 홀짝이 d1과 다르고 e4의 홀짝이 d3와 다르므로 수의 합이 짝이다. 따라서 q1=p1이다. 마찬가지로 생각하면 q2=p2이다. d^와 e^의 1, 4, 7번째 자리가 다르므로 H(d^, e^)=3이다. e4≠d4이면서 e2≠d2이거나 e3≠d3인 경우도 e1≠d1인 경우와 같이 생각하면 H(d^, e^)=3임을 알 수 있다.결국 (i), (ii)의 어느 경우든 H(d^, e^)≥3이 성립한다.
4) 다음과 같이 두 명제를 보일 수 있다.
(a) f^∉Y
먼저 d^는 4자리의 문자열을 제시문 (라)의 방식에 따라 7자리로 바꾼 것이므로 Y의 원소이다.
f^는 d^와 한 자리만 다른 문자열이므로 H(d^, f^)=1인데 논제 3)에 따라 Y의 두 원소의 해밍거리는 3 이상이어야 한다. 따라서 f^∉Y이다.
(b) f^와의 해밍거리가 가장 작은 Y의 원소는 d^뿐이다.
H(d^, f^)=1이므로 f^가 아닌 문자열 중 d^보다 더 가까운 것은 있을 수 없다. f^∉Y이므로 Y의 원소 중 d^보다 더 가까운 것은 없다.
이제 d^ 이외에 f^와의 해밍거리가 1인 Y의 원소가 없음을 보이자. 만약 해밍거리가 1인 d^가 아닌 원소가 있다면 그것을 e^라고 하자. 제시문 (나)의 (d)에 따라 H(d^, e^)≤H(d^, f^)+H(f^, e^)=1+1=2이므로 H(d^, e^)는 2 이하의 값이다. 하지만 Y의 서로 다른 두 원소의 거리는 3 이상이므로 이것은 모순이다. 1
