7-1. CHANNEL CAPACITY

6장은 Gambling theory니까 Pass

5장 데이터 압축은 정리해야하는데 나중에, 그 전에 5장의 Data compression과 Channel capacity와의 공통점? 차이점?이 있다면, Data compression은 얼마나 불필요한 것을 버릴까 이고, 이 7장에서 보는 data transmission은 redundancy를 더한다는 것이다. ex) x를 보낼 때, x를 3번 보내고 검사하면 틀린거 찾기 쉬움. 

2장도 정리해야하는데 나중에.. 

일단 바쁘다 바빠 7장부터 정리하고 다시 역순으로 와야지.

 

우선 A와 B가 의사 소통하는 것을 A의 물리적인 행동을 B에게 전달 하는 것이다. 이러한 정보 전달은 B에서 잘 받았다고, A에서는 전송 끝났다고 둘 다 전달을 받으면 성공적으로 통신을 한 것이다.

 

이번 7장에서는 n개의 채널을 바탕으로 maximum distinguishable signals가 n이 되는 것을 목표로 한다.

비트 n이 커지면 커질 수록 Capacity는 exponential하게 증가한다.

 그리고 앞으로 Mutual information을 활용해서 이를 해결하고자 함.

 

Source Symbol (입력 심볼) -> finte한 Alphabet으로 구성. => channel symbol로 바꿔 Encoding 진행 -> 그 다음 복구 시도

1. 입력 및 출력 심볼이 유한하기에, 이를 probability transition matrix라고도 불리며 Xn이 row, Yn이 column이 되어 matrix로 취급한다. 따라서 이 Matrix를 기반으로 Noise를 찾을 수 있으며, Xn과 Yn의 관계를 효과적으로 mapping 할 수 있다.

2. Encoder를 사용하는 이유는 W를 조금 더 효율적으로 보내기 위해서.

3. 그리고 여기서는 Memoryless라는 말을 사용하는데, 이는 신호를 보낼 때, 이전에 보낸 신호를 기억하지 않는다는 것을 의미한다. 따라서 현재 신호 x는 y에만 의존한다. 다른 신호는 다 독립이다. 따라서 아래와 같은 수식이 가능하다.

아래의 probability에 관한 수식에서 x1부터 xn까지 신호를 보내서 y1부터 yn까지 받았을 때, 이들이 각각 독립이면, 우측과 같이 product? pi? 형태로 전개할 수 있으며, Markov chain에 의해 제일 우측과 같은 수식이 완성된다. 

7.1의 정의는 다음과 같다. channel의 용량 capacity는 아래와 같의 정의된다. 둘 사이의 Mutual information을 maximize하는 p(x)가 C이다.

7.2와 같이 Noiseless한 binary channel은 다음과 같다. 이 때 C=1이다. 조금 더 구체적으로 설명하자면, 위의 C가 I(X;Y)를 maximize할 때 이므로,  p(x) = (1/2, 1/2)이다. 이 p(x)의 Entropy = 1이며,  따라서 Mutual information을 계산하였을 때, p(x,y) log p(x,y)/p(x)p(y) = 1/2 x log( 1/2  / ((1/2) x (1/2)) + 1/2 x log( 1/2  / ((1/2) x (1/2))  =  1/2 x log 2 + 1/2 x log 2  = 1

아 그리고 p(x,y) = 1/2 이다. 그 이유는, p(x) = p(y) = 1/2이고, x가 주어져야 y를 알 수 있기에 p(x,y)또한 1/2이다.

그리고 Mutual information이 두번으로 갈라지는 이유는, x 0->0, 1->1과, 0->1, 1-> 0 두가지 경우의 수가 있기 때문이다.

 

p(x,y) log p(x,y)/p(x)p(y)  = p(0,0) log p(x,y)/p(x)p(y) +  p(1,1) log p(x,y)/p(x)p(y) 이다.

- 이번에는 Noisy한 channel을 가지고 분석을 한다. 

- 하지만, 어디서 왔는지 알 수 있으므로 p(x)  = (1/2, 1/2)로 똑같다. 즉, 출력이 겹치지 않아서 괜찮다.

Noisy Typewriter

이번엔 출력이 겹치는 Noisy한 입력이 있다고 할 때, Source code를 완전히 복구하는 것은 어렵다. 따라서 이럴 경우에는 A,C .. 와 같이 홀수번째 알파벳만 보내 Noise를 없앤다. 이렇게 하면 완전하게 통신을 하지는 못하지만, 절반만큼 보낼 수 있다. 따라서 log 13bit가 capacity가 된다. 최소한 13비트는 오류 없이 보낼 수 있다. 

- 이전에는 98%의 전송률 이렇게 신경을 썼는데, 애초에 오류 없이 보낼 수 있다는 것을 깨닫고는 이에 집중하기 시작함.

수식으로 보면 max I(X;Y) = max (H(Y) - H(Y|X)) 로 mutual information을 전개시킨다. H(Y|X)=1이다. (H(Y|X=x)꼴로 만들고, x=A, x=C, x=E, ... 해서 전개하면 H(Y|X)는 1이 된다. 왜냐하면 오류없이 보낼 수 있기 때문. ) , max H(Y) - 1 에서 H(Y)는 이론상 log 26 이므로 (26비트를 받을 수 있기에) log 26 - 1 = log 13이 된다.

Binary Symmetric channel

이번에는 Binary Symmetric channel이다.  (BSC)

1. output이 deterministic하게 나눠져 있지 않다.

2. 그럼에도 우리는 최대 Capacity를 계산할 수 있다.

우측의 수식만 보면 간단하게 정리한 것 같지만, 좀 많은 테크닉이 들어간다.

7.2 mutual information의 수식을 전개.

7.3 p(x) H(Y|X) = p(x) H(Y|X=x) = p(x) H(Y|X=0) + p(x) H(Y|X=1) = 1-p or p, 따라서  

7.4 - 7.5 H(Y|X) 수식 전개해서 H(p)로 p에 대한 Entropy로 변경. 

7.6 H(Y)에 대한 Upper bound를 설정하면, H(Y)=log2=1이다. 이상적으로 Noise없이 전송한다면 최대 Entropy=1이 된다. 따라서 다음과 같은 부등식이 성립한다. 이는 모든 H(p)에 대해서 이 조건을 만족하는 upper bound가 되겠다. 

 

하지만 여기서 한가지 테크닉이 더 추가가 되는데, I(X;Y) <= 1 - H(p)였으며, 우리가 구하고자 하는 C = max I(X;Y) 이므로, 

1. C = max I(X;Y) <= 1-H(p) 이다.

2. I(X;Y) <= max I(X;Y) <= 1-H(p)가 성립한다.  (max I(X;Y)) 보다 작은 I(X;Y)는 항상 존재하기에,

3. 근데 여기서 max I(X;Y)인 경우는 p(x)가 uniform 할 때 이므로, 왼쪽의 Lower bound의 X또한 다음과 같이 된다.  (X_uniform;Y) <= max I(X;Y) <= 1-H(p)

4. 근데 I(X_uniform;Y) = 1-H(p) 이므로 샌드위치가 되서 I(X_uniform;Y) = 1-H(p)  <= max I(X_uniform;Y) <= 1-H(p) 이므로 C = 1-H(p)가 된다. 

 

따라서 우리의 capacity는 1-H(p)이다.

Binary Erasure channel

- 이번에는 특정 비트가 지워지는 경우이다. 즉, 0,1의 두가지 비트를 입력했을 때, 0,1,e의 3가지 경우가 나오는 경우다. 앞선 경우와 마찬가지로 오류로 갈 확률 (Noise)가 될 확률이 alpha이고, 1-alpha가 정상적으로 전송될 확률이다.

- 위와 마찬가지로 H(Y|X) = H(a)로 a에 대한 entropy가 된다.

- 그리고 H(Y)는 다음과 같이 변환할 수 있는데, H(Y=y) = H(Y=0, E=0) + H(Y=0, E=1) + H(Y=0, E=e) + H(Y=1) + H(Y=e)와 같이 전개할 수 있으므로 H(Y) = H(Y, E)라고 할 수 있다. 

- 정보이론에서의 chain rule이라고도 불린다나..? 정확하게는 모르겠다.

- 그리고 H(Y)는 다음과 같이 전개할 수 있다. pi는 0~1 사이의 값이다.

- 최종적으로는 다음과 같이 수식이 전개됨을 볼 수 있다. 

- 따라서 우리의 Capacity는 alpha인데, 이 alpha를 제외하고, feedback을 강하게 줘서 bit가 틀릴 때마다 끊고 다시 바꿔서 재전송을 할 수 있다면 우리의 Capacity는 1-a이다. 왜냐하면 틀릴 때마다 바로잡아서 보내는 비용이 1-a이니까.