제 10 장

SHANNON의 정리

10-1  소스코딩 정리와 채널코딩 정리

C. E. Shannon은 정보공학 분야에 두가지 핵심적인 정리를 발표함으로써 그 이론을 완성시켰다. 우리는 그 중 하나인 소스코딩 정리(source coding theorem)를 제7장에서 입증한 바 있다.

	정보이론

제 10 장 Shannon의 주 정리

□임의의 소스알파벳에 대하여 Entropy 함수에 무한히 접근하는 소스코딩 방식이 존재하며, 우리가 설계할 수 있는 어떠한 소스코드 체계도 그 평균 코드길이가 Entropy 함수 보다 작아질 수 없다.□

우리는 이러한 사실을 식(7-43) 및 식(7-49)로 다음과 같이 표현하였다.

[eqn: H_2`(S`) ~<=~ L_n over n ~＠~ H_2`(S`) ``／`` 1 over n]	(10-1)

[eqn: lim_{n->inf}``L_n over n ~=~ H_2` (S`)]	(10-2)

이는 채널(잡음)을 배제한 상태에서 소스의 정보량을 측정함으로써 유도된 무잡음 코딩정리이며, 소스코드의 확장(code extension)을 이용하여 증명된 사실이다. 이 정리에 따르면, Entropy 함수 H2(S)는 우리가 설계할 수 있는 소스코드 체계의 효율성 한계를 제공한다고 볼 수 있다.

이 장에서는 우리의 논의 속에 채널을 포함시켜, 위에 언급된 소스코딩 정리와 유사한 또 하나의 정리를 마련하고자 한다. 우리는 제9장에서 이산적 채널(discrete channel)과 연속적 채널(continuous channel)의 특성을 검토하였고, 그 채널을 통하여 전송될 수 있는 최대의 정보량인 채널용량(channel capacity) C를 정의한 바 있다. 이산적 채널에 대해서는

[eqn: C ~=`` max atop {p(a_i ) } I`(A ``;`` B) ~~~(bpb)]	(10-3)

와 같은 식으로 주어졌고, 연속적 채널에 대해서는

[eqn: C ~=~ 2`B`C_S ~~ (bps),~ \where ~~C_S ~= max atop {p(x ) } I`(boldX ``;`` boldY)]	(10-4)

와 같이 정의되었다. 특히, 정보통신공학에 흔히 적용되고 있는 AWGN 채널에 대해서는 다음과 같이 표시되는 채널용량을 유도한 바 있다. (Hartley-Shannon 법칙)

[eqn: C ~=`` B ``log_2`` left(1 ``+`` S over N right) ~~(bps)]	(10-5)

이러한 채널용량을 기반으로 하여, 우리는 저 유명한 Shannon의 채널코딩 정리(channel coding theorem)를 마련할 수 있다.

□잡음이 존재하는 상황에서, 임의의 채널에 대하여 그 채널용량에 무한히 접근하는 전송속도를 갖고 임의의 신뢰성(arbitrarily reliable)을 유지하는 채널코딩 방식이 존재하며, 우리가 설계할 수 있는 어떠한 채널코드 체계를 이용하더라도 채널용량을 초과하는 전송속도로 신뢰성이 보장된 전송을 수행할 수는 없다.□

우리는 이 마지막 장을 통하여, 위에 언급된 채널코딩 정리를 입증하고자 하는 것이다.

사실, 이 정리를 일반적인 채널에 대하여 수학적으로 완벽하게 증명한다는 것은 매우 어려운 일이다. 그러므로 여기에서는 다소 용이한 접근방법을 택하기로 한다. 즉, 먼저 가장 간단한 이진대칭채널(BSC)에 대하여 채널코딩 정리를 증명하고, 이를 토대로 실질적인 채널 모델에 접근해 가기로 한다. □BSC□는 디지탈통신의 채널 모델로 널리 적용되면서도 매우 간단한 구조를 가지므로 이에 대한 채널코딩 정리의 증명은 비교적 용이하다. 우리는 이 증명과정을 확장하여 일반적인 채널에 적용하게 될 것이다.

이 정리를 수학적으로 완벽하게 증명하는 것보다 우리에게 더욱 중요한 일은 위와 같은 과정을 통하여 그 정리가 갖고 있는 근본적인 개념을 확실히 파악하는 일이다. 그것은 □더욱 높은 수준의 정보통신공학을 연구하기 위한 기반 확립□이라는 이 책의 목적과도 잘 부합되는 일이라 하겠다.

먼저, 다음 절에서는 수신측의 입장에서 송신심볼을 추정하는 □결정규칙□과 그에 따른 □오류확률(error probability)□의 개념을 소개할 것이다. 이어서 이진대칭채널에 대한 채널코딩 정리를 논하고, 이를 확장하기 위하여 이른바 □랜덤 인코딩(random encoding)□의 개념을 도입하게 된다. 이러한 개념을 근거로 일반적인 채널에 적용되는 □Shannon의 채널코딩 정리□를 입증할 것이다.

10-2  결정규칙과 오류확률

채널의 수신측에서 하나의 심볼 bj를 수신하였다고 가정할 때, 전송된 송신심볼 ai를 예측하는 과정을 심볼추정(symbol estimation)이라 한다. 심볼추정은 여기서 새로이 도입된 개념이 아니라, 이미 제8-2절에서 채널관계식을 논의할 때 소개한 바 있다.

.  제8장의 각주 3을 보라.

주지하는 바와 같이, 심볼추정에 적용되는 결정규칙(decision rule)에는 시스템의 조건에 따르는 여러 가지 방법이 있다. 이를 확인하기 위하여 다음의 예제를 풀어보자.

[예제 1] 다음과 같은 송신알파벳과 수신알파벳을 갖는 채널에 대하여

[eqn: A~=`` \{`a_1 , `a_2 ,` a_3 `\}``,~~ B~=`` \{`b_1 , `b_2 ,` b_3 `\}]

천이행렬(transition matrix)이 아래와 같이 주어졌다.

[eqn: T ~=`` bmatrix {`0.5 &~ 0.3 &~ 0.2`` ## `0.2 &~ 0.3 &~ 0.5`` ## `0.3 &~ 0.3 &~ 0.4 ``}]

송신심볼들이 동일한 발생확률로 인가된다고 가정할 때(uniform input),

(1) 심볼 bj를 수신한 경우, 결정규칙에 따라 얻은 결과를 d(bj)라 표시하기로 하자. 모든 수신심볼에 대하여 오직 □a1□으로만 결정하는 결정규칙을 만들어라. 또한, 모든 수신심볼에 대하여 오직 □a2□, □a3□로만 결정하는 결정규칙을 써라.

(2) 가능한 결정규칙의 종류는 모두 몇가지인가?

(3) MLD(maximum likelihood decision) 규칙에 의한 결과를 구하라.

[풀이]

(1) 문제에 지시된 세가지 결정규칙은 다음과 같다.

결정규칙 1	결정규칙 2	결정규칙 3
d(b1) Ａ a1 d(b2) Ａ a1 d(b3) Ａ a1	d(b1) Ａ a2 d(b2) Ａ a2 d(b3) Ａ a2	d(b1) Ａ a3 d(b2) Ａ a3 d(b3) Ａ a3

(2) 위 (1)에서 보는 바와 같이, 하나의 결정규칙 내에는 s 개(수신심볼의 수)의 결정식이 존재하고 이들 각각에 대하여 q 개(송신심볼의 수)씩 선택할 수 있으므로, 가능한 결정규칙의 종류는

[eqn: q^s ~=~ 3^3 ~=~ 27 ~(가지)]

이다.

(3) 균일입력에 대한 채널관계식 (8-14)를 이용하여, 수신심볼의 발생확률은

[eqn: p(b_j ) ~=`` 1 over 3 `sum_i=1^3` P`(b_j vert a_i )`, ~j`=`1,`2,`3]

와 같이 나타난다. 따라서

[eqn: &p(b_1 ) ``=`` 1 over 3 `(0.5 `+` 0.2 `+` 0.3) ``=`` 1 over 3# &p(b_2 ) ``=`` 1 over 3 `(0.3 `+` 0.3 `+` 0.3) ``=`` 0.9 over 3# &p(b_3 ) ``=`` 1 over 3 `(0.2 `+` 0.5 `+` 0.4) ``=`` 1.1 over 3]

또한, 후향 조건확률은 식(8-15)를 이용하여

[eqn: P`(a_i vert b_j ) ~=`` 1 over 3 ` {P`(b_j vert a_i )} over {p(b_j )}`, ~ i`=`1,`2,`3`,~ j`=`1,`2,`3]

와 같이 주어지므로, 각 수신심볼에 대한 계산결과는 다음과 같다.

[eqn: &P`(a_1 vert b_1 ) ``=``0.5 ~~&P`(a_1 vert b_2 ) ``=`` 0.3/0.9 ~~&P`(a_1 vert b_3 ) ``=``0.2/1.1 # &P`(a_2 vert b_1 ) ``=``0.2 ~~&P`(a_2 vert b_2 ) ``=`` 0.3/0.9 ~~&P`(a_2 vert b_3 ) ``=``0.5/1.1 # &P`(a_3 vert b_1 ) ``=``0.3 ~~&P`(a_3 vert b_2 ) ``=`` 0.3/0.9 ~~&P`(a_3 vert b_3 ) ``=``0.4/1.1]

그러므로 MLD 규칙은 다음과 같이 표현된다.

[eqn: d`(b_1 ) ``=`` a_1 ,~~d`(b_2 ) ``=`` a_1 ( \or`` a_2 ```\or``` a_3 ) ,~~d`(b_3 ) ``=`` a_2]

앞의 예제에서 보는 바와 같이, 심볼추정에는 여러 가지 결정규칙이 적용될 수 있다. 이들 가운데 가장 널리 사용되고 있으며, 채널코딩 정리를 위하여 가장 용이한 확률관계를 부여하는 것이 MLD 규칙이다. 제8-2절에서 설명한 바와 같이, MLD 규칙은 수신된 심볼 bj를 조건으로 하는 송신심볼의 조건확률, 즉 후향 조건확률이 가장 큰 심볼로 추정하는 결정규칙을 말한다. 따라서 MLD 규칙은 다음과 같이 표현된다.

임의의 수신심볼 bj 에 대한 송신심볼의 추정은

[eqn: d`(b_j ) ~=~ a^* ``,~ \when ~ P`(a^* vert b_j ) ``>=`` P`(a_i vert b_j ), ~for ~ \all ~i]	(10-6)

와 같이 결정된다.

여기서 a*는 후향 조건확률이 가장 큰 송신심볼을 표시하고 있다. 즉, 수신심볼 bj가 주어진 상태에서 어떠한 송신심볼 ai의 조건확률도 송신심볼 a*의 조건확률을 넘지 못할 때, 수신측은 심볼 a* 로 결정하는 것이다.

식(10-6)에 표현된 MLD 규칙을 채널확률(전향 조건확률)에 의하여 나타내기 위해서는 식(8-15)로 표현된 Bayes 규칙을 이용한다. 즉,

[eqn: d`(b_j ) ``=`` a^* `,`` \when~ {P`(b_j vert a^* ) `p(a^* )} over {p(b_j )} ``>=`` {P`(b_j vert a_i )`p(a_i )} over {p(b_j )},`for ~\all~ i]

(10-7)

만일, 송신알파벳이 균일분포(uniform distribution)를 갖는다면, 모든 송신심볼에 대하여 p(a*)Ａp(ai)이 성립하므로 MLD 규칙은

[eqn: d`(b_j ) ``=`` a^* `,~ \when ~ P`(b_j vert a^* ) ``>=`` P`(b_j vert a_i )`` ,~ for ~\all~ i]	(10-8)

와 같이 채널확률만의 관계로 표현된다. [예제 1]의 (3)번은 바로 이러한 경우의 일 예이다.

앞에서도 밝힌 바와 같이, 이러한 MLD 규칙이 모든 결정규칙들 중에서 심볼추정에 가장 적당한 것은 아니다. 각 시스템의 조건에 따라 최적의 결정규칙은 엄밀하게 선택되어야 하는 것이다. 위에서 취급하였던 [예제 1]의 경우에도 MLD 규칙이 그리 적당하지 않음을 쉽게 알 수 있다.

그러나 채널코딩 정리를 증명함에 있어서, 우리는 다수의 코드체계에 대한 통계적 평균을 유도하게 될 것이므로, 최적의 결정규칙을 적용하지 않더라도 그 결정규칙이 무한히 적용되는 가운데 우리가 포기하였던 부분이 미치는 영향은 차츰 감소하게 되는 것이다. 따라서 가장 간단한 MLD 규칙을 적용하더라도 우리가 원하는 결과를 도출해 낼 수 있는 것이다. 이러한 사실은 우리가 최종적으로 유도하려는 채널코딩 정리의 강력성을 나타내며, 그것이 수학적으로 미묘한 문제를 다루는 정리가 아니라는 것을 말해준다.

이제, 주어진 채널에 대하여 MLD 규칙을 적용하여 심볼추정을 수행하였을 때 나타나는 오류확률(error probability)에 대하여 고찰하여 보자.

하나의 수신심볼 bj에 대하여 오류가 발생될 확률을 P(E | bj)로 표시하면, 정확한 심볼추정에 의하여 오류가 발생되지 않을 확률은 P(a* | bj)로 표시할 수 있다. 그러므로 수신심볼 bj에 대한 오류확률은

[eqn: P`(E vert b_j ) ~==~ 1 ``-``` P` \{`d`(b_j ) vert b_j \} ~=~ 1 ``-`` P`(a^* vert b_j )]	(10-9)

와 같이 나타낼 수 있다.

따라서 시스템의 오류확률은 모든 수신심볼 bj(jＡ1,2,□,s) 에 대하여 대하여 식(10-9)를 평균하여 다음과 같이 정의할 수 있다.

[eqn: P_E ~==~ sum_j=1^s``p(b_j )`` P`(E vert b_j ) ~=`` sum_j=1^s ``p(b_j )`` left{ 1``-`` P`(a^* vert b_j ) right}]	(10-10)

이를 좀 더 간단히 정리하면

[eqn: P_E ~=``` 1 ``-`` sum_j=1^s `p(b_-j )`` P`(a^* vert b_j )]	(10-11)

와 같이 표시되고, Bayes 규칙을 이용하여 채널확률(전향 조건확률)로 나타내면

[eqn: P_E ~=``` 1`` -`` sum_j=1^s` p(a^*`)``P`(b_j vert a^*`)]	(10-12)

을 얻을 수 있다.

만일, 송신알파벳이 균일분포를 갖는다면

[eqn: p`(a^*`) ~=``` 1 over q]	(10-13)

이 되므로, 이 때의 오류확률은

[eqn: P_E ~=``` 1 ``-`` 1 over q sum_j=1^s` P`(b_j vert a^*`)]	(10-14)

와 같이 표시된다.

[예제 2] 앞의 [예제 1]에서 취급한 시스템에 대하여 MLD 규칙을 적용하여 다음과 같이 추정한다고 가정할 때,

[eqn: d`(b_1 ) ``=`` a_1 ``, ~~ d`(b_2 ) ``=`` a_3``,~~ d`(b_3 ) ``=`` a_2]

시스템의 오류확률 [eqn: P_E]를 구하고, 채널의 품질을 평가하라.

[풀이] 식(10-14)에 의하여 시스템의 오류확률은 다음과 같이 계산된다.

[eqn: P_E &=``` 1 ``-`` 1 over 3` (0.5 ``／`` 0.3``／``0.5`)## &=``` 1 ``-`` 1 over 3` (1.3) ~simeq~ 0.5667]

이 예제에 주어진 채널은 그 오류확률이 너무 커서 실질적으로 사용할 수 없는 매우 열악한 품질을 갖고 있다고 할 수 있다. 실직적인 전송시스템의 채널로 사용되기 위해서는 그 오류확률이 최소한[eqn: 10^-4] 이하가 되어야 한다.

[예제 3] 다음의 천이행렬을 갖는 이진대칭채널(BSC)에 있어서

[eqn: T~=~ bmatrix{P &~ Q``` ## Q &~ P```}]

1-bit 이진수에 대한 오류확률을 [eqn: Q`=`0.01] 이라 하자. 이진수의 3-차 확장(3-bit 코드)을 이용하여 단일오류 정정코드(Hamming)를 적용하였을 때

(1) 가능한 송신심볼과 수신심볼을 모두 밝혀라.

(2) 시스템의 오류확률을 계산하라.

(3) 오류정정코드를 적용하지 않는 경우, 위 (2)에서 계산된 오류확률과 비교되는 오류확률은 얼마인가?

(4) 오류정정코드를 사용함으로써 얻는 효과에 대하여 고찰하라.

[풀이]

(1) 제3장의 표 3-4에 정리된 것처럼, 단일오류 정정코드는 송신심볼의 집합에서 최소거리 □3□을 유지해야 하므로, 가능한 송신심볼은 오직 □000□과 □111□의 두가지만 존재하게 된다. 그러나 수신심볼은 채널 상에서 발생되는 오류에 의하여 임의의 3-bit 코드가 모두 나타날 가능성이 있다. 따라서 다음 표와 같이 정리된다.

송신심볼	송신시 사용되지 않는 심볼	수신심볼
0 0 0 1 1 1	0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0	0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

(2) 3-bit 송신심볼이 채널을 통하여 전송되는 도중, 발생할 수 있는 경우와 그 발생확률을 정리하면 다음 표와 같다. 이 때, 심볼추정은 MLD 규칙으로 하고, 주어진 채널에 단일오류 정정코드를 적용한다고 가정하였다.

경 우	발생확률	오류정정
No error	[eqn: P^3]	정정 불필요
1-bit error	[eqn: 3`P^2 `Q]	정정 가능
2-bit error	[eqn: 3`P `Q^2]	정정 불가능
3-bit error	[eqn: Q^3]	정정 불가능

이 표에 따라, 수신측에서 실질적인 오류로 나타나는 것은 □2-bit error□인 경우와 □3-bit error□인 경우에 해당한다. 그러므로 시스템의 오류확률은 다음과 같이 계산된다.

[eqn: P_E ~=~ 3`P`Q^2 ``+`` Q^3 ~=~ Q^2 `(3`P ``+`` Q) ~=~ 2.98 `TIMES` 10^-4]

(3) 이 시스템에서 사용하고 있는 3-bit 심볼은 1-bit의 정보와 2-bit의 패리티로 구성된다. 따라서 오류정정코드를 사용하지 않는다면, 1-bit 이진수가 송신심볼 한 개에 대응한다. 그러므로 위 (2)에서 구한 시스템의 오류확률과 비교될 수 있는 것은 바로 1-bit 이진수에 대한 오류확률, 즉 □0.01□로 주어지게 된다.

(4) 위 [예제 2]에서 언급한 것처럼, □0.01□ 정도의 오류확률을 갖는 채널을 실질적인 전송시스템의 채널로 수용하기는 매우 어렵다. 한편, 단일오류 정정코드를 적용하여 얻은 시스템의 오류확률은 □0.000298□이므로, 이는 주어진 채널의 신뢰성을 대체로 만족할만한 수준으로 향상시켰다고 볼 수 있다.

이처럼 오류정정코드는 열악한 채널에 적용되어 그 신뢰성을 향상시키는 역할을 담당한다. 그러므로 채널의 특성에 따라 적절한 오류정정코드를 사용한다면 시스템 성능의 향상을 기대할 수 있을 것이다.

10-3  랜덤코드와 그 평균

이제, 우리는 Shannon의 채널코딩 정리를 증명할 준비를 갖추었다. 정리의 내용은

□임의의 채널에 대하여, 채널용량(channel capacity)에 무한히 접근하는 전송속도(효율성)와 임의의 신뢰성을 유지하는 채널코딩 방식이 존재한다.□

는 말로 요약할 수 있다.

먼저, 앞 절의 예제를 통하여 살펴본 이진대칭채널(BSC)에 대하여 이 정리가 성립함을 증명해 보기로 한다. 그것은 □BSC□가 디지탈 전송시스템의 채널 모델로서 가장 보편적으로 도입되며, 그에 대한 증명이 비교적 간단하여 이해하기 쉽기 때문이다. 우리는 이 증명과정을 확장하여 일반적 채널에 접근하는 방식을 취할 것이다.

또한 이진대칭채널에 대하여 n-bit 블록코드(block code)를 적용하기로 한다. 앞 절의 예제에 설명한 바와 같이, n-bit 블록코드는 이진대칭채널의 송신심볼을 n-차 확장(n-th extension)한 상태라 볼 수 있다.(제7-3절 참조)

n-bit 블록코드의 가능한 모든 심볼의 수는

[eqn: N~=~ 2^n ~(개)]	(9-15)

이다. 그러나 채널 상에서 발생하는 오류를 방지하기 위해서는 이들 모두를 송신심볼의 알파벳에 수용할 수 없다. 우리는 각 송신심볼이 Hamming 거리의 관점에서 될 수 있는 한 멀리 떨어지도록 코드체계를 설계해야 한다.

이러한 기본적인 가정을 세우고 채널코딩 정리에 접근하여 보자.

첫째, 정보의 전송속도가 채널용량에 접근하기 위해서는 송신알파벳 내에 몇 개의 심볼이 존재하여야 하는가?

만일, 송신알파벳 내에 M 개의 균일한 발생확률을 갖는 심볼들이 존재한다고 가정하면, 각 심볼의 발생확률은

[eqn: p~=`` 1 over M]	(10-16)

이므로, 각 심볼이 소유하는 정보의 양은

[eqn: I`(a_i ) ~=``` log_2 ``1 over p ~=```log_2``M ~~(bits)]	(10-17)

로 주어진다.

한편, 제9-3절의 식(9-39)로부터 이진대칭채널의 용량은

[eqn: C ~=``` 1 ``-`` Omega_2`(P`) ~=``` 1 ``-`` Omega_2`(Q`) ~~(bpb)]	(10-18)

와 같이 주어지므로, n-bit 블록코드로 이루어진 심볼에 대하여

[eqn: n`C ~=``` n` \{`1 ``-`` Omega_2`(Q`)`\}]	(10-19)

와 같이 표시할 수 있다.

식(10-17)과 식(10-19)에 의하여 심볼의 정보량을 채널용량에 접근시키기 위해서는

[eqn: I`(a_i`) ~=``` log_2``M ~=``` n`(C``-``epsilon_1`)]	(10-20)

을 만족하여야 한다. 여기서 [eqn: epsilon_1]은 극소양수(infinitesimally small positive number)이다. 이 식을 송신심볼의 수 M에 관하여 풀면

[eqn: M ~=``` 2^{n`(C`-`epsilon_1 `)} ~=`` {2^{n`C}} over 2^{n `epsilon_1}]	(10-21)

을 얻는다.

식(10-18)로부터 채널용량 C는 [0, 1] 사이에 존재하는 한정된 값이며, 블록코드의 bit 수 n을 크게 증가시키면 식(10-21)의 분모는 매우 큰 값이 된다. 따라서 송신알파벳의 심볼 수 M은 n-bit 코드로 가능한 [eqn: 2^n] 개의 심볼들 중 극히 일부 만을 택하여야 한다. n이 증가함에 따라 n-차원 공간에는 매우 많은 □Hamming 거리 1□인 점(point)들이 존재하고, 이들 중 극히 일부를 택하여 □될수록 큰 Hamming 거리□를 유지하도록 코드점(code point)을 형성시킨다면, 송신심볼은 채널용량에 접근하는 평균 정보량을 갖게 된다는 것이다. (제3-9절 참조)

둘째, 코드점에 포함되어 있는 모든 송신심볼들이 동일한 발생확률을 가지며, 그들 사이에 □최대의 Hamming 거리□를 유지할 수 있도록 채널코드를 설계하는 방법은 무엇인가?

현 시점에서 이러한 특성을 갖는 실질적인 코드체계를 설계하는 방법은 발견되지 않았다. 따라서 우리는 하나의 이상적인 코드체계를 가정하여, 그것이 □Shannon의 채널코딩 정리□를 만족한다는 사실을 보이므로써, 그 존재성만을 확인할 수 있다. 이를 위하여 도입되는 개념이 이른바 랜덤 인코딩(random encoding)이다.

충분히 큰 n에 대하여, n-차원 공간 내의 각 코드점 사이에 이격된 Hamming 거리는 충분히 크게 유지할 수 있을 것이다. 따라서 코드체계의 각 코드점을 무작위적으로 선택하여 결정한다 하더라도 그들 사이에는 충분한 Hamming 거리가 유지될 것이며, 각 코드점의 발생확률도 균일하게 유지될 수 있을 것이다.

이와 같은 랜덤 인코딩의 코드점을 마련하는 방법을 제시한다면 다음과 같다.

완전한 동전 n 번 던져서 나타나는 □0□과 □1□을 차례로 기록하여 하나의 코드점을 얻고, 이를 코드체계(code book) 내에 포함시킨다. 두번째 심볼에 대한 인코딩도 첫번째 심볼에 대한 과정과 동일하게 수행하여 그 결과로 나타나는 코드점을 코드체계 내에 포함시킨다. 만일, 코드체계 내에 총 M 개의 코드점이 존재하여야 한다면, 이러한 과정을 M 번 수행하여 마련할 수 있을 것이다. 이 때, 완전한 동전을 던진 횟수는 모두 nM 번이므로, 코드체계는 총 2nM 가지 중 극히 일부에 해당하는 M 개의 코드점을 사용하게 되는 것이다. 주지하는 바와 같이, 이와 같은 과정에 의하여 설정된 각 코드점들은 충분히 큰 n에 대하여 랜덤 인코딩의 기본적 조건을 그대로 만족할 것이다.

위의 과정과 궁극적으로 동일한 방법이지만, 랜덤 인코딩의 또 다른 과정을 소개하면 이러하다. 먼저, 가능한 2n 개의 이진코드를 하나씩 카드에 적어 이들을 함에 넣고 잘 흔들어 무작위로 섞이게 한 다음, 한 장의 카드를 뽑아 코드체계의 첫번째 코드점으로 삼는다. 뽑혀진 카드를 도로 함에 넣고 다시 잘 섞이게 한다음, 다시 한 장의 카드를 뽑아 코드체계의 두번째 코드점으로 삼는다. 이러한 과정을 M 번 반복하여 코드체계 내에 M 개의 코드점이 존재하도록 하는 것이다. 이렇게 형성된 코드체계는 위에서 완전한 동전을 던져 형성시킨 코드체계와 개념적으로 동일하며, 랜덤 인코딩의 기본적 조건을 그대로 만족한다.

일반적으로 랜덤 인코딩은 서로 다른 두 개의 심볼에 대하여 동일한 코드점을 부여할 가능성이 있으나, n이 충분히 커진다면 그러한 가능성은 거의 없어지는 것이다. 또한, 이러한 과정을 통하여 형성된 코드체계는 임의의 신뢰성(즉, 무한히 작은 오류확률)을 갖게 된다는 사실을 입증하려 하는 것이다.

셋째, 랜덤 인코딩에 의하여 형성된 코드체계를 채널에 적용하여 전송한다고 할 때, 오류확률은 어떻게 주어지는가?

랜덤 인코딩에 의하여 형성된 코드점들을 n-차원 공간에 표시해 보기로 하자.

채널을 통하여 전송되는 하나의 bit에 대한 오류확률은 Q 이므로, 하나의 n-bit 블록에 대한 오류 bit 수의 기대값은

[eqn: E`(bold r ) &=` sum_r=0^n `r ```Pr \{ r \} ~=` sum_r=0^n ` r ```binom n r Q^r ``(1`-`Q)^{n`-`r} ## &=`sum_r=1^n ` {n``!} over {(r`-`1)`! ``(n`-`r)`! }``Q^r ``(1`-`Q)^{n`-`r}]	(10-22)

와 같이 주어진다. 변수를 [eqn: s `=` r`-`1] 로 치환하여 위 식을 계산하면

[eqn: E`(bold r ) &=` sum_s=0^n-1 ` {n``!} over {s`! ``(n`-`1`-`s)`!}``Q^s+1 ``(1`-`Q)^{n-1-s} ## &=``` n`Q``(P ``+``Q)^n-1 ~=~ n`Q]	(10-23)

을 얻는다.

이제, 하나의 코드점(code point)을 중심으로 하고 반경(radius)이 nQ인 구(sphere)를 생각하여 보자. 이 구의 반경을 미소량 [eqn: n`epsilon_2] 만큼 증가시켜 하나의 송신심볼을 중심으로 하는 n-차원 공간의 구를 그려보면 그림 10-1과 같이 나타난다. 도시된 구의 외곽 반경은

[eqn: r ~=```(Q ``／`` epsilon_2 )``n]	(10-24)

로 주어진다.

그림 10-1  송신측의 개념도

식(10-22), (10-23), (10-24)에 나타난 문자 r은 Radix를 표시하는 것이 아니고, n-차원 공간에 존재하는 구의 반경을 표시한다.

또한, 극소 양수 [eqn: epsilon_2]는

[eqn: Q ``+`` epsilon_2 ~＠~ 1 over 2]	(10-25)

을 만족하도록 설정된 값이다. 식(10-20) 및 식(10-21)에서 사용된 또 하나의 극소 양수 [eqn: epsilon_1]과 여기서 사용된 [eqn: epsilon_2] 사이의 상대적인 크기는 뒤에서 결정하게 될 것이다.

□BSC□의 입력인 하나의 이진심볼을 랜덤변수[eqn: boldX_i] 라 두면, 그 n-차 확장인 n-bit 코드는 동일한 분포를 갖는 n 개의 랜덤변수들을 합한

[eqn: boldX ~=~ boldX_1 ``+`` boldX_2 ``+`` cdots ``+`` boldX_n]	(10-26)

라 할 수 있다. 이 랜덤변수들의 평균을

[eqn: E` left(boldX over n right) ~=`` E` (boldX_i ) ~=`` mu]	(10-27)

라 하면, 다음과 같은 극한식이 성립하는데,

[eqn: lim_{n->inf} ``Pr `left{ LEFT | {boldX_1 `+` boldX_2 `+` cdots `+` boldX_n } over n ``-`` mu `RIGHT | ~>=~ epsilon `right} ~=~ 0]	(10-28)

이를 다수법칙(the law of large number)이라 한다.

.  다수법칙은 동일한 시행을 여러번 반복하여 그 평균을 예측하고자 할 때, 흔히 사용되는 유용한 정리히다. 다수법칙의 결론은 이러하다. □여러번 반복된 시행의 평균을 구해보면, 그 개별적인 시행에서 나타나는 평균과 극한적으로 동일하다.□

다수법칙에 대한 증명을 포함하여 좀 더 상세한 내용을 공부하고자 하는 독자는 다음 문헌을 참고하라.

C. Ash, The Probability Tutoring Book, Ch.9, pp.266-274, 1993, IEEE Press.

이러한 다수법칙을 그림 10-1의 개념도에 적용하면, 구의 원점에 표시된 코드점은 하나의 n-bit 코드를 나타내므로 식(10-26)으로 주어진 랜덤변수의 합에 대응하고, 구의 반경을 표시하는 nQ는 식(10-23)에서 계산된 것처럼 평균에 대응하며, 구각[eqn: epsilon_2]는 그 자체로 극소 양수이다. 그러므로 충분히 큰 n에 대하여, 원하는 수신심볼이 구각을 포함하는 구의 외부에 존재하게 될 확률은 무한히 작아진다.

이 때, 수신측에서 심볼추정을 위하여 MLD 규칙을 사용한다고 가정하고, n-차원 공간 내에서 그림 10-1과 같은 임의의 두 구가 서로 겹치지 않는다고 확신할 수 있다면, 수신측은 전송된 심볼을 언제나 정확히 추정할 수 있을 것이다.(제3-9절 참조)

수신측의 심볼추정을 위해서는, 그림 10-2와 같이 수신심볼 bj를 중심으로 하는 새로운 구로 나타낸 개념도가 적용되어야 한다. 이 개념도는 임의의 수신심볼 bj를 중심으로 하고, 반경과 구각의 뚜께는 송신측의 개념도와 동일한 구를 n-차원 공간에 표시하고 있는 것이다.

따라서 송신심볼 ai가 그림 10-2에 도시된 구의 내부에 존재할 확률은, 수신심볼 bj가 그림 10-1에 도시된 구의 내부에 존재할 확률과 일치한다. 또한, 그림 10-2에 주어진 수신측의 개념도에 있어서, 원하는 송신심볼이 구각을 포함하는 구의 외부에 존재하게 될 확률은 무한히 작아진다.

그림 10-2  수신측의 개념도

이제, 수신측의 개념도를 이용하여 시스템의 오류확률(error probability)을 구해보기로 하자.

그림 10-2에 나타낸 구를 S(r)이라 하고, 수신심볼 bj에 대응하는 정확한 송신심볼은 ai라 가정하자. 수신심볼 bj를 중심으로 사는 구 S(r) 내부에 정확한 송신심볼 ai가 존재하지 않거나, ai 외의 다른 송신심볼이 존재하거나, 두 개 이상의 송신심볼이 존재한다면, 제3-9절에서 설명한 기하학적 코딩의 개념으로 볼 때 수신측은 오류(error)를 발생하게 될 것이다.

다음의 표 10-1은 발생할 수 있는 모든 경우에 대하여 오류여부를 판단하는 기준을 마련하고 있다.

표 10-1  수신측 상황별 오류의 발생

경 우	정확한 심볼 ai in S(r)	다른 심볼 ak in S(r)	오류여부	오류의 원인
1 2 3 4	○ ○ × ×	○ × ○ ×	오류발생 정 확 오류발생 오류발생	구의 반경이 너무 작다. 채널의 잡음이 너무 크다. 채널의 잡음이 너무 크다.

※ ○ : 존재함   × : 존재하지 않음

이 표에서, 경우2 는 오류가 발생되지 않는 상태를 말하며, 경우1 은 설정된 구의 반경이 너무 작아서, 즉 코드점 사이의 Hamming 거리가 너무 짧아서 오류가 발생하는 상태를 말한다. 또한, 경우3 과 경우4 는 채널 상의 잡음신호가 너무 커서 오류가 발생하는 상태를 표현하고 있다.

따라서 시스템의 오류확률 PE는 경우1, 3, 4 가 발생될 확률과 동일하므로 다음과 같이 표현할 수 있다.

[eqn: P_E &=`` Pr left{ a_i `` NOTIN `` S(r) right} ``+`` Pr left{ a_i `` IN `` S(r) right}`` Pr left{ \other `` a `` in `` S(r) right}]	(10-29)

이 식 우변의 첫번째 항은 표 10-1의 경우3, 4 를 나타내며, 두번째 항은 경우1 을 나타내고 있다. 여기서 Pr{ai□S(r)}은 하나의 확률을 표시하므로 1 보다 작거나 같은 값이다. 따라서 이 요소를 식(10-29)로부터 제거하면, 다음과 같은 부등식을 얻는다.

[eqn: P_E ~<=`` Pr left{a_i ``□`` S(r) right} ``／`` Pr left{ \other ``a `` in ``S(r) right}]	(10-30)

우변에 있는 두번째 항을 좀 더 자세히 살펴보자. □다른 심볼이 주어진 구 내에 존재할 확률□은 심볼 ai를 제외한 임의의 심볼이 구 내에 존재할 확률이므로

[eqn: Pr left{ \other ``a `` in ``S(r) right} ~=`` Pr left{ a_1 ``cup`` a_2 ``cup``cdots`` cup`` a_i-1 ``cup`` a_i+1 ``cup `` cdots`` right}]	(10-31)

와 같이 표현할 수 있다. 여기에 제1장의 식(1-4)를 확장하여 적용하면

[eqn: Pr left{ \other``a `` in `` S(r) right} ~<=~ sum from A-a_i Pr left{ a``□``S(r) right}]	(10-32)

와 같은 식을 얻을 수 있다. 이 식의 우변은 송신심볼 M １ 1 개에 대한 확률의 합을 표현한다.

식(10-32)를 식(10-30)에 대입하면, 시스템의 오류확률은 다음과 같이 나타난다.

[eqn: P_E ~<=~ Pr left{a_i ``□`` S(r) right} ``+` SUM from A-a_i `Pr left{a ``□`` S(r) right}]	(10-33)

이 식의 첫 번째 항은 전송된 코드점이 수신심볼을 중심으로 하는 구의 내부에 존재하지 않을 확률을 나타내며, 두 번째 항은 전송되지 않은 다른 코드점들 중 임의의 심볼이 구의 내부에 존재할 확률들의 합을 표시한다.

앞에서 언급한 바와 같이, 랜덤 인코딩에 의하여 형성된 각 코드점들은 충분한 Hamming 거리를 유지하면서 존재하고, 충분히 큰 차원의 공간(large n)에 있어서는 식(10-28)에 표현된 다수법칙에 의하여 식(10-33)의 첫 번째 항은 극소 양수 [eqn: delta]에 의하여 한정시킬 수 있다.

이러한 원리를 근거로 하여 (10-33)은 다음과 같이 표현할 수 있다.

[eqn: P_E ~<=~ delta ``+`` SUM from A-a_i `Pr left{ a ``□`` S(r) right}]	(10-34)

결국, 이 식의 첫 번째 항 [eqn: delta]는 극소 양수로서 전송된 심볼 하나에 기인하는 오류확률을 표시하여, 두 번째 항은 전송된 하나의 심볼을 제외한 나머지 M １ 1 개의 다른 심볼들에 기인하는 오류확률을 표시하고 있다. 따라서 첫 번째 항은 공간의 차원 n을 크게함으로써 무한히 감소시킬 수 있는 양이며, 두 번째 항은 결국 시스템의 신호속도(signaling rate)에 따라 변화하는 양이다.

지금까지의 전개에 있어서, 우리는 랜덤 인코딩을 사용한 기하학적 접근을 시도하여, 채널코드가 형성되는 공간의 차원을 충분히 크게 설정함으로써 오류확률을 임의로 감소시킬 수 있음을 확인하였다. 그러나 이는 개념적으로 확인된 결과라 볼 수 있으며, 좀 더 구체적이고 확실한 결론에 도달하기 위해서는 Shannon에 의하여 제안된 평균 랜덤코드(average random code)의 개념을 도입하여야 한다. 평균 랜덤코드란 주어진 n-차원 공간에 설정될 수 있는 모든 랜덤 코드체계에 대하여 오류확률의 평균을 취하여 예상 오류확률(expected error probability)을 산출함으로써, 이를 랜덤 코드체계가 갖는 대표적 특성으로 삼고자 하는 전략으로서, 이것이 Shannon에 의하여 제시된 수많은 아이디어 중 가장 탁월한 것이라 할 수 있다.

그러므로 이제부터 랜덤 코드체계의 오류확률에 대한 평균을 취하여 예상 오류확률을 구해보기로 하자. 여기서 모든 랜덤 코드체계에 대한 평균을 다른 평균들과 구분하기 위하여 □[eqn: XI `(cdot)]□를 사용하기로 한다.

식(10-21)에 주어진 것처럼, n-차원 공간에는[eqn: M``Ａ``2^{n(C-epsilon_1`)}] 개의 코드점이 존재하며, 이 공간에 설정할 수 있는 랜덤 코드체계의 총 수는

[eqn: 2^nM ~~(가지)]	(10-35)

이다. 또한, 이러한 코드체계들은 무작위적으로 선택될 것이므로, 각 코드체계가 설정될 확률은 모두 동일하며

[eqn: P_S ~=`` 1 OVER 2^nM]	(10-36)

로 주어진다.

바로 이 확률을 가중치로 하여 계산된 오류확률의 평균을 예상 오류확률(expected error probability)이라 하며

[eqn: Xi` (P_E ) ~==~ sum_R_C ``P_S ``P_E ~=`` sum_R_C ``1 over {2^nM }``P_E]	(10-37)

와 같이 정의하기로 한다.

식(10-34)의 첫 번째 항인 [eqn: delta]는 모든 코드체계에 대하여 고정된 상수이다. 따라서 오류확률을 모든 코드체계에 대하여 평균을 취하면 다음과 같이 나타난다.

[eqn: Xi``(P_E ) &<=~ delta ``+`` (M`-`1)``` Xi`` left[ Pr left{a ``□`` S(r) right} right] ## &<=~ delta ``+`` M```Xi`` left[ Pr left{ a ``□`` S(r) right} right], ~a``□`a_i]	(10-38)

여기서 정확한 코드점을 제외한 다른 코드점들(a□ai)은 평균에 대하여 같은 영향을 미치게 된다는 사실을 적용하였다.

랜덤 인코딩에 의하여 생성된 코드점들은 n-차원 공간 내에 균일하게 분포할 것이므로, 임의의 코드점이 구(sphere) S(r) 내에 존재할 확률 Pr{a□S(r)}을 가능한 모든 코드체계에 대하여 평균을 취하면, 그 값은 n-차원 공간의 체적에 대한 구 S(r)의 체적의 비로 주어지게 될 것이다. (제3-9절 참조)

n-차원 공간의 체적은 식(3-27)로부터 2n 이다. 또한, 구 S(r) 의 체적, 즉 S(r) 내에 존재하는 모든 정점의 수를 N(r)이라 하면

[eqn: Xi``[Pr left{a ``□`` S(r) right} ] ~=~ {N`(r)} over 2^n `, ~~a``□`a_i]	(10-39)

와 같은 식을 얻는다. 이 식을 식(10-38)에 대입하면

[eqn: Xi``(P_E ) ~<=~ delta ``+`` M`` {N`(r) } over {2^n } ``, ~~a``□`a_i]	(10-40)

와 같이 나타난다.

현재 우리가 고찰하고 있는 이진대칭채널(BSC)에 있어서, 구 S(r)은 n-차원 이진공간에 존재하는 반경 r 인 구이므로, 그 체적은 제1장 [예제 9]의 결과를 이용하여 다음과 같이 계산된다.

[eqn: N`(r) &=~ 1 ``+`` binom n 1 ``+`` binom n 2 ``+`` cdots ``+`` binom n r ## &=`` sum_k=0^r `binom n k]	(10-41)

또한, 식(10-24), (10-25)로부터 구의 반경은

[eqn: r ~=~ (Q ``+`` epsilon_2`)`n ``, ~~ \where ~ Q``+`` epsilon_2 ``＠` 1 over 2]	(10-42)

와 같이 주어진다.

한편, 일반적으로 식(10-41)에 주어진 이항계수의 부분합은 다음과 같이 표현되는 이항부등식(binomial inequality)에 의하여 한정된다.

.  이항부등식은 이항계수의 성질과 Stirling의 근사식에 의하여 입증될 수 있다. 이에 대한 증명은 다소 복잡하여 본문의 흐름을 방해할 우려가 있으므로 생략하였으나, Shannon의 채널코딩 정리를 입증하기 위해서는 필수적으로 도입되어야 한다. 이 장의 연습문제에 이를 증명하라는 문제를 두었으며, 독자들의 탐구를 위하여 다음의 참고문헌을 제시한다.

R.W.Hamming, Coding and Information Theory, 2nd.ed., Ch.9, pp.164-173, 1986, Prentice-Hall.

[eqn: lim_{n->inf}`` sum_k=0^{lambda`n}` binom n k ~<=~ 2^{n` Omega_2`(lambda)}]	(10-43)

여기서 함수 [eqn: Omega_2` (cdot)]는 제9장의 식(9-21)에 정의된 2-심볼 소스의 Entropy 함수이다.

다시 말해서, 반경 r 인 구의 체적은

[eqn: N`(r) ~<=~ 2^{n`Omega_2`(lambda)}`, ~\where~ lambda``=``Q `+` epsilon_2]	(10-44)

로 한정된다는 것이다.

따라서 식(10-40)의 예상 오류확률은 충분히 큰 n에 대하여 다음과 같이 나타낼 수 있다.

[eqn: Xi` (P_E ) ~<=~ delta ``+`` M□2^{-n \{`1`-`Omega_2`(lambda) \} }]	(10-45)

또한, 이 식의 우변에 나타난 지수 부분은 □BSC□의 채널용량 식(9-39)를 이용하여

[eqn: 1 ``-`` Omega_2`(lambda) &=~ 1 ``-`` Omega_2` (Q `+` epsilon_2 ) ## &=~ 1 ``-`` Omega_2`(Q) ``+`` Omega_2` (Q) ``-`` Omega_2` (Q `+` epsilon_2 ) ## &=~ C ``-`` \{` Omega_2` (Q `+` epsilon_2 ) ``-`` Omega_2`(Q) \}]	(10-46)

와 같이 나타낼 수 있다. 여기서 함수 [eqn: Omega_2` (cdot)]는 제6장의 그림 6-3과 같은 변화를 가지며, 식(10-25)로 주어진 범위에서 단조 증가하는 연속함수이므로 또 하나의 극소 양수에 의하여

[eqn: Omega_2` (Q `+` epsilon_2 ) ``-`` Omega_2` (Q) ~==~ epsilon_3` ,~ \where~ epsilon_3 ``:`` 극소`` 양수]	(10-47)

와 같이 표현할 수 있다.

따라서 식(10-45)는

[eqn: Xi` (P_E ) ~<=~ delta ``+`` M□2^{-n (C `-` epsilon_3 ) }]	(10-48)

로 표현되고, 여기에 식(10-21)을 대입하면

[eqn: Xi`(P_E ) ~<=~ delta ``+`` 2^{n`(C`-`epsilon_1 )} cdot 2^{-n`(C`-`epsilon_3 )} ~=~ delta ``+`` 2^{-n`(epsilon_1 `-` epsilon_3 )}]	(10-49)

와 같이 표시된다.

그러므로 식(10-47)의 극소 양수[eqn: epsilon_2]를 충분히 작게 선택하여, 새로운 극소 양수[eqn: epsilon_3]가

[eqn: epsilon_1 ``-`` epsilon_3 ~Ｂ~ 0]	(10-50)

를 만족하도록 작게 취할 수 있으며, 이에 따라 충분히 큰 n에 대하여 식(10-49)의 예상 오류확률 [eqn: Xi` (P_E )]는 무한히 감소시킬 수 있다. 이는 □BSC□에 대하여 임의의 신뢰성을 보증하는 것이다.

이 절을 통하여, 우리는 평균 랜덤코드(average random code)가 이진대칭채널(BSC)에 대하여 채널코딩 정리의 요구조건을 그대로 만족한다는 사실을 입증하였다. 그러므로 그러한 코드체계가 존재한다는 사실은 자연스럽게 확인된 것이다. 결국, 이진대칭채널에 대하여 Shannon의 채널코딩 정리는 성립한다.

□이진대칭채널(BSC)에 대하여, 채널용량(channel capacity)에 무한히 접근하는 전송속도(efficiency)와 임의의 신뢰성(reliability)을 유지하는 채널코딩 방식은 존재한다.□

위의 증명과정으로부터 유추할 수 있는 몇가지 사실을 정리하면 이러하다.

우선, 충분히 큰 차원의 이진공간을 사용했다는 사실로부터, 전송되는 각 심볼은 채널 상에서 발생되는 오류를 충분히 정정할 수 있도록 매우 긴 코드(long-code)로 인코딩되어야 한다는 것이다. 이는, 효율적인 코드가 임의의 신뢰성을 갖기 위해서는 매우 긴 메시지로 전송되어야 함을 뜻하며, 긴 메시지는 전송이 수행되기 전에 많은 양의 정보를 획득하여야만 형성시킬 수 있는 것이다. 우리가 사용한 코드체계는 랜덤 인코딩에 의하여 형성된 것이며, 원래 □random□이라는 용어 자체가 짧은 코드로는 불가능함을 의미하는 것이다.

다음으로, Shannon의 채널코딩 정리는 실용적 결과가 아니라 이론적 결과라는 사실이다. 다시 말해서 랜덤 인코딩과 같은 방법이 실제적인 전송시스템에 적용될 수는 없는 것이다. 그러나, 이와 같은 사실이 채널코딩 정리를 쓸모없는 것으로 전락시키는 이유가 되지는 않는다. 왜냐하면 우리는 이 정리를 통하여 이른바 □효율적이고 신뢰성 있는 코드체계의 본질□을 파악할 수 있기 때문이다.

요컨대, 주어진 채널을 효율적으로 사용하려면, 송신심볼을 긴 코드로 인코딩해야 하며, 각 코드 내에서 동시에 여러 개의 오류를 정정할 수 있어야만 한다. 이는 우리가 제3장에서 논의한 오류정정코드의 필요성을 입증하는 결론이라 하겠다.

Shannon의 채널코딩 정리는 실용적인 코드체계의 설계방법을 제공하지는 않지만, 이러한 채널코딩의 □한계(bouds)□를 명백히 설정하고 있다. 매우 탁월한 효율성과 신뢰성을 갖는 코드체계는 각 코드의 길이가 매우 길어야 한다. 사실, 이러한 조건을 만족하는 코드는 실현 불가능한 경우가 많다. 그러나 오류정정코드는 오늘날에도 활발히 연구되어 그 효율성과 신뢰성을 향상시키고 있으며, 이들은 모두 Shannon의 채널코딩 정리를 그 한계로 인식하고 있는 것이다.

10-4  일반적 채널에 대한 고찰

일반적인 채널에 대하여 □채널코딩 정리□를 증명하는 과정은 앞 절의 이진대칭채널(BSC)에 대한 증명과는 비교할 수 없을 정도로 복잡하고 어렵다. 그러나 그 증명이 진행되는 순서는 □BSC□의 경우와 동일하다고 볼 수 있으며, 단지 각 단계에서 나타나는 계량(metric)들이 수학적으로 매우 복잡한 양상을 띄게 되는 것이다.

우선, 앞의 증명에서 가정된 백색잡음에 대하여 용이하게 적용되었던 □Hamming 거리□는 일반적 채널의 특성에 따라 정의되는 새로운 거리함수(distance function)로 교환되어야 하며, 이러한 거리함수에 의하여 형성되는 구(sphere)의 개념도 다시 정립되어야 한다.

또한, 이렇게 새로이 정의된 구의 내부에 존재하는 코드점의 수를 산출할 수 있도록 새로운 방법을 발견해야 한다. 마지막으로, 일반적인 채널의 용량(capacity)은 □BSC□에 대하여 적용된 것과 같은 간단한 방정식으로 표현될 수 없을 것이므로, 그 원래의 정의로 돌아가서 새롭게 유도하여 적용해야 한다는 난점 등이 있는 것이다.

더욱이, 채널코딩 정리의 증명을 위하여 필요한 예상 오류확률의 개념도 □BSC□에 비하여 매우 복잡해 질 것으로 사료된다. 일반적 채널에 존재하는 잡음의 형태가 백색잡음이 아닌 경우에는, 앞에서 언급하였던 구(sphere)가 타원구(oval)의 형태를 갖게 될 것이다. 다시 말해서, 오류확률이 높은 방향으로는 장축(long axis)을 가지며, 오류확률이 낮은 방향으로는 단축(short axis)을 갖는 계란형의 입체가 형성된다는 것이다.

일단, 이러한 계량조건들이 모두 발견되면, 하나의 수신심볼을 중심으로 하는 타원구를 형성시키고, 앞에서와 같이 각 반경을 미소량 증가시켜 구각(shell)을 정의한다. 다음으로, 다수법칙(the law of large number)을 이용하여, 충분히 큰 n에 대하여 정확한 송신심볼은 거의 언제나 정의된 타원구의 내부로 들어 오게 된다는 사실을 입증하게 되는 것이다. 이 때, 우리는 채널용량에 무한히 접근하는 효율성을 만족시키기 위하여 송신심볼의 수 M을 선택하며, 충분히 큰 n에 대하여 선택된 타원구들이 서로 겹치게 될 확률은 무한히 작아짐을 보여야 하는 것이다. 그밖의 과정들은 우리가 □BSC□에 대하여 수행했던 과정과 동일하다.

주지하는 바와 같이, 일반적 채널에 대하여 Shannon의 채널코딩 정리를 증명하는 것은 그리 간단하지 않다. 더구나 각 채널의 특성에 따라 그 증명과정에서 나타나는 계량들이 달라지게 되므로, 증명은 각 채널에 대하여 별도로 이루어져야 할 것이다. 따라서 이에 대하여 상세히 논의하는 것은 이 책의 목적과도 부합되지 않으며, 정보공학에 대한 개념의 정립에도 큰 도움을 주지 못할 것으로 판단한다.

그 대신, 여기서는 다음과 같이 표현되는 □채널코딩 정리의 역(converse of channel coding theorem)□을 증명해 보이고자 한다.

□어떠한 채널코드 체계를 사용하더라도, 채널용량 보다 높은 전송속도(efficiency)에서는 무한히 작은 오류확률(reliability)을 가지고 전송할 수 없다□

사실, 제10-1절의 초반에 제시된 □채널코딩 정리□에 대한 표현은 앞의 제10-3절에서 증명된 내용과 여기에 표현된 내용을 결합한 것이다. 따라서 우리가 □채널코딩 정리의 역□을 입증한다면, 이 장을 시작하면서 세운 목표에 그대로 도달하게 될 것이다.

□채널코딩 정리의 역(converse of channel coding theorem)□을 증명하기 위해서는 다음과 같이 표현되는 Fano 부등식(Fano inequality)을 필요로 한다.

정리 1  <Fano 부등식>  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

채널의 후향조건 Entropy와 오류확률 사이에 다음의 부등식이 성립한다.

[eqn: H` (A vert B) ~<=~ H`(P_E ) ``+`` P_E ```log`(q`-`1)]	(10-51)

이를 Fano 부등식이라 하며, 등식은 다음의 두가지 조건이 만족될 때 성립한다.

[eqn: &P`(a vert b) ~=~ P_E over {q``-``1},~ for ~\all~ b,~ a`` !=`a^* ## &P`(a^* vert b) ~=~1 ``-`` P_E ,~ for~ \all ~b]	(10-52)

♠ 증명

정리의 식(10-51)의 좌변에 표시된 후향조건 Entropy는 식(8-37)로부터

[eqn: H`(A vert B ) &=`` sum_i=1^q sum_j=1^s ``P`(a_i ,``b_j )`` log 1 over {P`(a_i vert b_j )} ## &=`` sum_{A-a^*} sum_B ``P`(a,``b)`` log 1 over {P`(a vert b) } ## &~~+`` sum_B ``P`(a^* ,``b`) ``log 1 over {P`(a^* vert b)}]	(10-53)

와 같이 표현되고, 그 우변은 식(10-12)를 이용하여

[eqn: H`(P_E ) `+` P_E` log(q`-`1) &=~P_E`log 1 over P_E `+` bar P_E ``log 1 over {bar P_E} `+` P_E` log(q`-`1) ## &=~P_E`log {q`-`1} over P_E `+` bar P_E ``log 1 over {bar P_E} ## &=`` sum_{A-a^*} sum_B``P`(a,``b)`` log {q`-`1} over P_E # &~~`+` sum_B ``P`(a^* ,``b)`` log 1 over {bar P_E }]

(10-54)

로 표현된다. 식(10-53)과 식(10-54)에서 우리는 다음과 같은 표시방법을 사용하였다.

[eqn: && sum_i=1^q sum_j=1^s ~=`` sum_A sum_B ## & bar P_E &=~ 1 ``-`` P_E ~=~ 1 ``-`` left{ 1 ``-`` sum_j=1^s``P`(a^* ,`` b_j ) right} ## &&=~ 1 ``-`` left{ sum_{A-a*} sum_B ``P`(a, ``b) `right} ## &&=~ sum_B ``P`(a^* , ``b)]	(10-55)

이제, 식(10-53)에서 식(10-54)를 빼면, 다음과 같은 관계식을 얻을 수 있다.

[eqn: &H`(A vert B) ``-`` H`(P_E ) ``-`` P_E ``log`(q`-`1)## &~~=`` sum_{A-a^*} sum_B ``P`(a,``b)``log` P_E over {(q`-`1)`P`(a vert b) } ## &~~~~+`` sum_B`` P`(a^* ,``b) ``log ` {bar P_E} over {P`(a^* vert b) }]	(10-56)

이 식의 우변에 제6장의 정리 1에서 증명된 식(6-46)을 적용하고, 로그함수의 밑수에 의한 상수들을 생략하고 쓰면

[eqn: 우변 &<=` sum_{A-a^*} sum_B`` P`(a,``b) ``left{ P_E OVER {(q`-`1) `P`(a vert b) } ``-`` 1 right} # &~~~+`` sum_B`` P`(a^* , ``b) ``left{ {bar P_E} OVER {P`(a^* vert b) } ``-`` 1 right} ## &=`` P_E OVER {q`-`1} sum_{A-a^*} sum_B ``p`(b) ``-`` P_E ``+`` {bar P_E}` sum_B`p`(b) ``-`` bar P_E ## &=~ P_E ``-`` P_E ``+`` bar P_E ``-`` bar P_E ~=~ 0]	(10-57)

과 같이 계산된다. 그러므로 정리의 식(10-51)은 성립한다.

또한, 식(6-46)으로부터 등식은 로그함수의 파라미터가 □1□일 때 성립하므로

[eqn: &P_E over {(q`-`1)`P`(a vert b)} ``=`` 1 ~~ or ~ P`(a vert b) ``=`` P_E over {q`-`1},~ for~ \all~ b , ~ a``!=`a^* ## &{bar P_E } over {P`(a^* vert b)} ``=``1 ~~~or ~~~ P`(a^* vert b) ``=`` bar P_E ``=`` 1``-``P_E , ~for ~\all~ b]

이 되어, 식(10-52)도 성립한다.	■

이제부터, Fano 부등식을 이용하여 □채널코딩 정리의 역□을 증명하여 보자.

만일, 어떤 코드체계의 신호속도가 채널용량에 도달하게 되면, 식(10-21)로부터 M 개의 균일입력에 대하여

[eqn: M ~``=~ 2^{n`(C`-`epsilon)} `, ~~epsilon``Ｂ``0]	(10-58)

을 만족하여야 한다.

한편, 식(9-2)와 식(9-4)를 n-차 확장에 대하여 적용하면

[eqn: H`(A^n ) ``-`` H`(A^n vert B^n`) ~<=~ n`C]	(10-59)

와 같은 관계식이 항상 성립한다. 또한, 송신심볼의 Entropy는

[eqn: H`(A^n ) ~=`` sum_i=1^M ` 1 over M`` log_2 `M ~=~log_2`M ~=`` n`(C ``+`` epsilon)]	(10-60)

과 같이 계산되므로, 우리는 두 식 (10-59) 및 (10-60)을 이용하여 다음과 같은 부등식을 마련할 수 있다.

[eqn: n`(C ``／`` epsilon) ``-`` n`C ~=~ n`epsilon ~<=~ H`(A^n vert B^n`)]	(10-61)

여기에 식(10-51)로 주어진 Fano 부등식을 적용하면

[eqn: n`epsilon ~<=~ H`(A^n vert B^n`) ~<=~ H`(P_E ) ``／`` P_E ``log_2`(M`-`1)]	(10-62)

와 같이 나타난다.

제6장의 그림 6-3으로부터 H(PE) □ 1 이고, M １ 1 ＠ M 이므로, 식(10-58)을 이용하면

[eqn: n`epsilon ~＠~ 1 ``+`` P_E``(n`C `+` n``epsilon`)]	(10-63)

을 얻는다. 이 식을 오류확률 PE에 대하여 풀면

[eqn: P_E ~Ｂ~{n`epsilon``-``1} OVER {n`C ``／`` n`epsilon} ~=~ {epsilon ``-`` 1/n} over {C ``+``epsilon}]	(10-64)

와 같이 나타난다.

마지막으로, 식(10-64)에 대하여 n→□ 인 극한을 취하면

[eqn: P_E ~Ｂ~ lim_{n->inf} { epsilon ``-`` 1/n} over {C ``／`` epsilon} ```=``` epsilon over {C ``／`` epsilon}]	(10-65)

와 같은 결과를 얻는다. 이는 무한히 큰 차원의 공간에 적용되더라도 오류확률 PE를 임의로 감소시킬 수 없음을 표시하므로, □채널코딩 정리의 역□은 입증된다. 즉, 채널용량을 초과하는 전송속도로 전송하면 그 신뢰성은 보장되지 아니한다.	■

연 습 문 제

10.1	C. E. Shannon이 제시한 두가지 정리, 즉 □소스코딩 정리□(제7-3절)와 □채널코딩 정리□를 각각 설명하고, 그 차이점을 정보공학적 관점에서 비교하여 설명하라.

10.2	송신알파벳과 수신알파벳이 각각 다음과 같이 주어지고,

[eqn: A ~=`` \{` a_1 ,`a_2 ,` a_3 ,` a_4 \}``,~~B ~=`` \{` b_1 ,`b_2 ,` b_3 ,` b_4 \}]

채널의 천이행렬(transition matrix)이

[eqn: T~=~ bmatrix { 3/8 &~ 1/4 &~ 1/4 &~ 1/8``## 1/4 &~ 1/2 &~ 1/8 &~ 1/8``## 1/4 &~ 1/8 &~ 1/2 &~ 1/8`` ## 1/4 &~ 1/8 &~ 1/4 &~ 3/8``}]

로 주어졌다.

(a) 가능한 결정규칙의 종류는 모두 몇가지인가?

(b) 송신알파벳 A가 균일분포(uniform distribution)를 가질 때, MLD 규칙을 이용하여 추정결과 d(bj),(jＡ1,2,3,4)를 구하라. 단, 가능한 모든 경우를 나타내어라.

(c) 송신심볼들의 발생확률이 각각 p(a1)Ａ0.4, p(a2)Ａ0.3, p(a3)Ａ0.2, p(a4)Ａ0.1 로 주어질 때, MLD 규칙에 의한 추정결과 d(bj),(jＡ1,2,3,4)를 구하라.

(d) 위 (2), (3)에 대하여 각각 오류확률(error probability) PE를 구하라.

10.3	채널의 천이행렬이 다음과 같이 주어질 때, 위 문제 10.2의 과정을 반복하라.

[eqn: T~=~ bmatrix { `0.6 & 0.2 & 0.1 & 0.1` # `0.1 & 0.7 & 0.1 & 0.1 # `0.2 & 0.2 & 0.5 & 0.1 # `0.1 & 0.1 & 0.1 & 0.7}]

10.4	이진대칭채널(BSC)에 있어서, 단위 오류확률이 QＡ0.04 이다. 이 채널에 3-bit 단일오류 정정코드(Hamming)를 적용하였다고 할 때,

(a) 시스템의 오류확률 PE를 구하라.

(b) 만일, 오류정정코드를 사용하지 않았다면, 위 (a)에서 구한 오류확률과 비교되는 오류확률은 얼마인가?

(c) 위 (a), (b)의 결과로부터 오류정정코드를 적용하여 얻은 효과를 설명하라.

10.5	n-bit 랜덤 인코딩을 수행하기 위한 방법으로 제10-3절에 제시된 두 가지 과정(완전한 동전을 nM 번 던지는 방법과 M 장의 카드를 선택하는 방법)은 개념적으로 동일하다. 이를 확인하기 위하여 다음 물음에 답하라.

(a) n-bit 코드점 M 개로 형성되는 코드체계는 두 가지 과정에서 모두 몇가지나 가능한가?

(b) n-차원 공간의 체적은 두 가지 과정에서 각각 어떻게 설명될 수 있으며, 얼마로 나타나는가?

(c) 위의 두 가지 방법 이외에 랜덤 인코딩을 수행할 수 있는 방법들을 제시하라.

10.6*	n 개의 랜덤변수[eqn: boldX_1 , `boldX_2 ,` cdots,` boldX_n] 이 서로 독립이며, 동일한 분포를 가진다고 할 때, 식(10-28)로 표현되는 다수법칙(the law of large numbers)을 증명하라.

(※ Hint : 각 랜덤변수의 평균과 분산이 [eqn: mu`, ~sigma^2]으로 주어질 때, 그들의 합으로 나타나는 랜덤변수의 평균과 분산은 각각

[eqn: &E`` left( {boldX_1 `+` boldX_2 `+` cdots `+` boldX_n } over n right) ``=`` mu` ## & Var`` left({boldX_1 `+` boldX_2 `+` cdots `+` boldX_n } over n right) ``=`` sigma^2 over n]

로 주어진다는 사실과 다음과 같은 식으로 주어지는 Chebychev 부등식을 이용하라.

[eqn: Pr \{vert boldX `-` mu vert ``>=``k \} ~<=~ sigma^2 `/`k^2``,~ k``Ｂ``0]  )

10.7*	다음과 같은 순서에 따라, 식(10-43)에 주어진 이항부등식을 증명하라.

(a) Stirling의 부등식 [eqn: n^n` e^-n` sqrt n ``e^{7/8} ~<=~ n`! ~<=~ n^n` e^-n` sqrt n`` e] 를 이용하여, 이항계수는 다음과 같이 주어짐을 보여라.

[eqn: binom n {lambda`n} &=~ {n`!} over {(lambda` n)`! `` (n`-` lambda`n )`! }## &<=~ left{ 1 over {lambda^lambda `(1`-`lambda)^{1`-`lambda}} right}^n ``left{ 1 over {e^3/2 `lambda`(1`-`lambda)` n } right}^1/2``, ## &~~~~ lambda ``＠`` 1 over 2 ,~ lambda`n ``:`` \integer]

(b) 위 (a)에 나타난 식의 우변에서 첫 번째 함수는

[eqn: left{ 1 over {lambda^lambda `(1`-`lambda)^{1`-`lambda}} right}^n ~=~ 2^{n`Omega_2`(lambda)}]

와 같이 계산됨을 보여라.

(c) 충분히 큰 n에 대하여, 다음과 같은 이항부등식이 성립함을 보여라.

[eqn: sum_k=0^{lambda` n}`` binom n k ~<=~ 2^{n`Omega_2 (lambda)}, ~lambda ``＠`` 1 over 2 ,~ lambda`n ~:`` \integer]

10.8	이진대칭채널(BSC)의 용량을 C라 할 때, 그 n-차 확장인 n-bit 코드를 사용하면 채널용량이 nC로 계산되는 이유를 설명하라.

10.9	식(10-53)과 식(10-54)를 식(10-55)의 표시방법을 이용하여 확인하라.

10.10	Shannon의 채널코딩 정리와 그 역(converse)을 비교하여 정보공학적인 차이점을 말하고, 이들을 결합하면 제10-1절의 첫머리에 정리된 것과 같음을 설명하라. 또한, 식(10-4) 및 식(10-5)에 주어진 □Hartley-Shannon 법칙□과 이 장을 통하여 입증된 채널코딩 정리와의 정보공학적 관계를 설명하라.

10.11*	□BSC□의 오류확률이

[eqn: 0 ~<=~ Q ~<=~ 1 over 2]

와 같은 범위 내에 있을 때,

(a) [eqn: d over dQ `left{ Omega_2` (Q) right} ~>=~ 0] 임을 보여라.

(b) 식(10-46)을 이용하여, 식(10-43)에 나타난 두가지 극소 양수 사이에 다음과 같은 관계가 성립함을 보여라.

[eqn: epsilon_3 ~=`` epsilon_2``log_2` left( {1`-`Q} over Q right)]

(c) 위 (a), (b)의 결과로 주어진 식들을 사용하더라도 식(10-48) 및 식(10-49)는 그대로 성립함을 보여라.

10.12* (Markov 부등식과 Chebychev 부등식)

(a)[eqn: boldX]가 음이 아닌 값만을 취하는 연속적 랜덤변수라 하고, 상수 [eqn: k``Ｂ``0] 일 때, 다음과 같이 표현되는 Markov 부등식을 증명하라.

[eqn: Pr \{boldX ``>=`` k \} ~<=~ {E`(boldX )} over k]

(b) 위 (a)에서 증명한 Markov 부등식을 이용하여, 위 문제 10.6의 Hint에 제시된 Chebychev 부등식을 증명하라.

(c) 위 (b)에서 증명한 Chebychev 부등식의 의미를 제1장의 [예제 7]에 주어진 Gaussian 분포의 확률밀도함수를 이용하여 설명하라.