[이산수학]Message Transmission (정보 전송)

컴퓨터에서 정보를 전송할 때는 0과 1로 구성된 코드를 보내게 되므로

노이즈라는 장애를 받아 0을 1로, 1을 0으로 수신하는 경우가 종종 생긴다.

이런 경우를 Transmission Error 라고 부른다.

 

이런 에러를 줄이기 위해 정보를 그대로 보내지 않고 encoding하여 보낸다. 특정한 encoding function을 이용해 b를 e(b)라는 code word로 바꾸어 보내는 것이다.

즉, b라는 word가 B^m에 속할 때,

x = e(b) ∈ B^m 인 encoded word로 바꾸어 보내게 된다.

이 때 B^n이 (m,n) encoding function이며 일대일 함수이다.

만약 이렇게 인코딩된 정보가 에러가 나면 도착 후에 에러를 검출할 수 있다.

 

보낸 정보와 받은 정보가 다르면 틀림없이 에러가 난 것이다. 이 때 한 자리 이상 k자리 이하만큼 다른 경우, k개 이하의 에러로 전송되었다고 말한다.

 

parity check code

e : B^m → B^m+1 와 같은 암호 함수를 parity check code라고 한다.

즉 단어의 끝에 한자리를 더 추가해서 보내는 것이다.

이 때 마지막 자리수는 단어의 1의 개수가 짝수이면 0, 홀수이면 1로 보낸다.

(x에 있는 1의 개수를 x의 무게(weight)라고 부르고 |x|로 표시한다.)

만약 짝수의 무게를 가진 수가 하나의 에러가 났다면 수신되는 단어는 홀수의 무게를 가지게 되므로 에러가 났음을 알 수 있게 된다.

 

(m, 3m) encoding function

m자리의 단어를 3번 반복해서 보낸다.

b = 011이라 가정하면 e(011) = 011011011이다. 만약 여기서 에러를 일으켜

한 개 또는 두 개의 에러가 났다면 검출이 가능하다.

 

Hamming distance

Hamming distance는 x와 y의 mod 2 연산을 한 결과의 무게이다.

mod 2 연산에 의하면 0과 1을 연산할 때만 1이 된다.

결과적으로 x와 y의 자리수가 얼마나 다른지를 알 수 있는 척도가 된다.

 

minimum distance

Hamming distance 중에거 무게가 가장 작은 것을 말한다.

(m,n) encoding function e : B^m → B^n이 k개 이하의 에러를 검출할 수 있는 필요 충분 조건은 minimum distance가 적어도 k+1이 되는 것이다.