7.2 7.3 SYMMETRIC CHANNELS, PROPERTIES OF CHANNEL CAPACITY

 

앞서 7-1에서 channel 부분이 transition matrix로 구성되어있다고 말했는데, 이젠 다음과 같은 binary symmetric channel을 고려한다. binary symmetric channel: 오류 확률이 모두 동일한 matrix.

++ (앞선 7-1에서 본건 binary symmetric channel의 capacity는 1-H(p). 
+++ Erasure된 channel은 1-a bit만큼의 capacity.

그리고 여기 보이는 7.17이 binary symmetric transition matrix이다.

symmetric transition matrix의 정의는 모든 row나 column이 permutation해서 같아지는 경우이다.

또 다른 예시의 symmetric transition matrix로는, 위와 같은 나눗셈 연산이 존재한다. 우리가 비트를 보낼 때 (X) Decoding된 Y는 X가 보낸 정보를 완벽하게 Decoding할 수 있어야 한다. 이를 검증하기 위한 수단으로 다음과 같이 Z를 더해서 (X와 같은 알파벳) 나눗셈 연산과정을 통해 이 비트가 제대로 전송이 됐는지 검증할 수 있다. 

7.20 -  r이 transition matrix의 row일 때, symmetric하므로, 각 행은 같다. 같은 입력 각 row를 입력 X로 넣었을 때, 출력 분포 Y가 항상 같으므로, H(Y|X) = H(r) 이다. 

7.21 - 그리고 Y의 entropy는 bit 수를 따라가므로, log |Y|가 된다. 

 

그리고 7-1에서 본 샌드위치 방식을 여기에도 적용할 순 있지만, 이번엔 다른 방식으로 전개를 해보자면, Capacity를 구하는 공식은 max I(X;Y) 이고 I(X;Y)는 위에서 전개했다. 그리고 위에서 I(X;Y) = H(Y) - H(r) 에서, uniform 일 때, 이 값이 maximize되며, 이는 아래에서 증명할 수 있다. p(y) = p(y,x) = Sigma p(y|x)p(x) = c x 1/|X| = 1/|Y|이다.

여기서 c는 모든 열의 합으로, symmetic matrix에서 이는 항상 같다. 우리의 예제에서 c=1이고, |X| = |Y| = 3이다.

열의 합을 X의 크기로 나눈 것은 y의 크기와 동일하기에 p(y) = 1/|Y|가 되며, H(y) = -Sigma p(y) log p(y) 이므로, -|Y| x 1/|Y| x log 1/|Y| = log |Y| 이다.

따라서 다음과 같다.

 

weakly symmetric

- 그리고 이번에는 weakly symmetic한 함수를 가져왔다. row, column 모두가 permutaiton 되어있는 것이 아닌, row에 대해서만 permutation이 되어있을 경우이다.

- 그리고 우리의 Transition matrix는 다음과 같이 weakly symmetric일 때, row에 대해서 entropy를 전개하였으므로, 똑같이 Weakly symmetric한 matrix에 대해서 row entropy를 계산한다.

 

7.3 PROPERTIES OF CHANNEL CAPACITY

- Channel Capacity의 특성은 다음과 같이 5개가 있다. 

1번 - 4번 자명함

5번 - I(X;Y)가 p(x)에 대해서 concave하다는 것인데, y=x**2 와 같은 함수는 함수 y에서 x에 대해 Convex하다는 것을 알 수 있지만, 우리의 p(x)는 p(X=x1) + p(X=x2) .. 인 linear combination한 구조이다. 따라서 I(X;Y)또한 p(x)에 대해서 concave하다는 것은, 어떤 p(x)를 고르던, I(X;Y)가 같거나 더 크다는 것이고, 최대값을 찾기 위한 확률 분포 p(x)가 존재한다는 것을 보장한다.