자연계열 2번

[가] 사용 가능한 알파벳이 ‘0’과 ‘1’ 밖에 없다고 하자. 가령 ‘적기가 남쪽으로부터 날아오고 있다’와 같은 메시지를 나타내는 1101을 통신로를 통하여 전송하는 경우를 생각해 보기로 한다. 1101을 ‘부호화’ 하지 않고 그대로 보내면 통신로에서 잡음이 들어가서 0이 1로 또는 1이 0으로 바뀔 수 있다. 예컨대 메시지가 0101로 바뀔 수 있으며, 이로 인해 수신자는 아무 의미가 없는 메시지를 받거나, 아니면 잘못된 정보를 받을 수 있다. 이를 극복하기 위하여 메시지에 여분의 자리(0과 1로 된)를 덧붙여서 원래의 메시지 대신 이 부호화된 메시지(부호화된 메시지는 채택된 ‘부호’의 원소이며, 부호는 일정한 길이를 갖는 0, 1 수열의 집합이다)를 전송한다. 그러면 대부분의 경우 오류가 발생하였어도 수정 가능하고 따라서 원래 의도한 메시지로 바르게 복호할 수 있다. 이와 같은 테크닉은 우주선으로부터 지구로의 사진전송, CD 플레이어, 이동통신, 컴퓨터의 데이터 압축 등에 광범위하게 응용되고 있다.

[나] 통신로는 메시지 → 부호기 → 통신로 → 수신된 메시지 → 복호기 → 메시지 와 같은 도식으로 표현할 수 있다. 메시지가 단순히 0과 1이고 부호기에서 0은 000으로, 1은 111로 전환하여 전송하는 경우(즉 이 경우 채택된 부호는 $\displaystyle \{000,111\}$이다)를 생각해 보자. 통신로가 신뢰할 만하여 1개 이하의 오류만 발생 가능하다고 하면, 통신로에서의 잡음으로 인하여 111이 101로 수신되어도 복호기는 이를 111로 바르게 복호하여 원래의 메시지 1을 회복할 수 있을 것이다. 즉 1 → 111 → 잡음 → 101 → 111 → 1의 단계를 거친다. 이 경우 복호 알고리즘은 단순히 “(a) 수신된 메시지에서 0과 1의 개수를 센다. (b) $\displaystyle x$($\displaystyle x$는 0 또는 1)가 더 많이 나타나면 이를 $\displaystyle x$로 복호한다.”일 것이다.

[다] 이제 메시지 집합이 길이가 4인 0, 1 수열 전체(총 16개)인 경우를 생각해 보자. 어떤 부호기를 통해 0과 1로 이루어진 길이가 4인 메시지 $\displaystyle x_1x_2x_3x_4$를 길이가 7인 메시지 $\displaystyle x_1x_2x_3x_4x_5x_6x_7$로 전환하여 전송한다고 하자. 이때 여분의 자리 $\displaystyle x_5,x_6,x_7$을 결정하기 위하여 부호기는 다음과 같은 규칙을 사용한다. 그것은 $\displaystyle A=\{x_1,x_3,x_4,x_5\}$, $\displaystyle B=\{x_1,x_2,x_4,x_6\}$, $\displaystyle C=\{x_1,x_2,x_3,x_7\}$ 세 집합 각각에서 1의 개수가 항상 짝수 개(중복 셈 허용)가 되도록 하는 것이다. 가령 1101은 부호기에서 1101010으로 전환되어 전송된다.