[07] Channel Capacity

통신 시스템에서 중요한 개념 중 하나는 "Channel capacity"이다. Channel capacity란 통신 채널을 통해서 안전하게 전달될 수 있는 데이터의 최대 비율을 의미한다.

 

통신이란 A가 B에게 message를 전달하는 행위를 말하며, B가 A가 보낸 message를 정확하게 복원할 수 있으면 통신이 성공했다고 말할 수 있다. 이때 간섭이나 공격에 의해 message는 변조가 될 수 있어, B에서 복원할 수 있음이 중요한 요소로 작용한다.

 

Channel capacity는 이런 에러가 작은 통신에서 최대로 전송할 수 있는 데이터 양이라고 생각하면 된다. Channel codes는 channel capacity만큼의 통신을 가능하게 해주는 code라고 보면 된다.

 

1. Discrete Memoryless Channel (DMC)

본 포스팅에서는 DMC를 가정한다. DMC란 input $X$와 output $Y$가 있을 때, channel transition matrix $p(y|x)$를 가지며 $y$는 같은 시간의 $x$에 대해서만 dependent한 상황이다.

통신 구조

 

이 경우의 Channel capacity는 다음과 같다.

$$ C = max_{p(x)} I(X;Y) $$

 

쉽게 생각해 보면, $I(X;Y)$가 높아야 모든 데이터가 안전하게 전송되었음을 의미함으로 타당하다.

 

Example1. Noiseless Binary Channel

$I(X;Y)$ = 1이다.

 

Example2. Nonoverlapping outputs

Error가 없으므로, 마찬가지로 $I(X;Y)$=1이다.

 

Example3. Noisy typewriter

알파벳에 대해서 A를 눌렀을 때, A가 나올 확률이 1/2이고 B가 나올 확률이 1/2인 타자기를 가정한다. 쉽게 생각해보면, $log \, 13$임을 알 수 있다.

 

$C = max \, I(X;Y) = H(Y) - H(Y|X) = H(Y) - 1 = log26 - 1 = log13$

 

Example3. Binary symmetric channel (BSC)

데이터가 반전될 확률이 $p$인 채널이다. 풀이는 다음과 같다.

 

만약 $p(x)$가 uniform distribution을 가진다면, $H(Y)$는 1이 되므로 위와 같이 $I(X;Y)$를 구할 수 있다. 이 경우 채널 케페시티는 $1-H(p)$이다.

 

Example4. Binary erasure channel (BSC)

결국 $I(X;Y)$를 잘 구하면 된다.

해서 정리하면 $C=1-\alpha$가 된다.

 

아니면 다음처럼 간단하게 구할 수도 있다.

 

다시 전송하면 에러 없이 잘 쓸수 있는거 아닌가 싶지만, data capacity 자체를 높여주지는 못한다. 그러니까 Channal capacity는 이론적 한계인 것이다.

 

Example5. Symmetric channel

Row와 Col이 각각 서로의 permutation인 경우이다. 이 때 channel capacity는 다음과 같다.

$r$은 row of transition matrix이고 $|Y|$는 출력 기호의 수이다.

• $r=\{0.3, 0.2, 0.5\}$
• $|Y|=3$

 

Symmetric channel만의 특징으로는 $p(x)$가 uniform하면 $p(y)$도 uniform하다는 것이다.

 

Example6. Weak symmetric channel

Row는 서로의 permutation이며 col의 합이 1인 채널이다.

• Input: uniform한 경우에 성립
• $C=log|3|-H(1/3,1/6,1/2)$

 

2. Channel code and Error probability

$(M,n)$ code for $(X,p(y|x),Y)$

M: message 수, n: codeword의 길이

 

Error prob.

이 때 Message i가 decode 안될 확률을 다음과 같이 구한다.

 

그리고 최대 error prob.과 average error prob.을 다음처럼 정의한다.

Maximum

Average

 

당연하게도 $P^{(n)}_e \leq \lambda^{(n)}$이니까 작은 평균적인 에러는 작은 maximum error을 의미하게 된다.

 

Code rate

Code rate는 다음처럼 구한다.

$$ R = {log\,M \over n} $$

 

$R$ transmission을 달성하기 위해서는 $M=2^{nR}$이어야 하며 $\lambda^{(n)} \rightarrow$ 0으로 수렴해야 한다.

 

그래서 최종적인 결론은 $R < C$면 에러 발생 확률이 매우 작아, 안정적인 전송이 가능하다.

 

3. Joint Asymptotic Equipartition Property with Jointly Typical Sequences

$X^n(i)$와 $Y^n$이 얼마나 자주 함께 발생하는 가를 참고해서 $i^{th}$ index를 decode하려는 시도이다. Jointly typical sequences는 다음처럼 정의된다.

$$ A^{(n)}_{\in} = \{(x^n,y^n) \in X^n * Y^n\} $$

 

그래서 다음의 특징을 가지고 있다.

 

각각의 특징이 의미하는 바는 다음과 같다.

1. 시퀀스 $(x^n,y^n)$이 충분히 길어지면, 대부분의 경우 전형적인 공동 행동을 보임
2. 전형성 집합에 속하는 시퀀스 수가 $H(X:Y)$에 의해 결정됨
3. 독립적으로 생성되면, $A_{\in}^{(n)}$일 확률이 $2^{-nI(X;Y)}$

 

마지막이 중요하다. 확률이 $2^{-nI(X;Y)}$라면 $2^{nI(X;Y)}$의 distinguishable signal $X^n$이 있음을 의미하게 된다. 즉 $I(X:Y)$을 통해서 얼마만큼의 input을 전송할 수 있는지 알게 되는 것이다.

 

4. Channel Coding Theorm

적은 error rate를 허용하지만, 대수의 법칙으로 통신의 성공을 기대하며, 그렇기에 평가하기 위해서 random하게 codebook을 생성하고 decode해서 error를 평균적으로 측정한다. (Random coding이라 함) Decoding할 때는, jointly typical decoding을 이용해 진행한다.

 

Random coding의 주 목적은 good code의 existence를 보이기 위함이다. 그래서 뭐 이런저런 증명이 있는데, 다 쳐내면 결론은 다음과 같다.

• Achievaility : $R<C$면, 작은 error 확률로 전송할 수 있는 code가 있다.
• Converse : Error 확률이 0인 code는 $R \leq C$를 만족한다.

 

5. Channel coding

• Repetition codes
  그냥 반복, M=2, n=5
  0 $\rightarrow$ 00000
  • 2 bit error까지 수정 가능
• Parity Check Codes
  parity bit을 추가 ( 1의 수를 짝수로 맞춤)
  001 $\rightarrow$ 0011
  • 1의 수를 세고 짝수가 아니면 error가 있음
  • Error-detecting code
• Hamming code (parity check matrix를 사용함)
  Binary에 대해서 1개의 error 수정 가능
  • $Hc = 0$인 $H$ 만들기
  • $Hr = H(c+e_j) = He_j$
• Feedback capacity는 원래 capacity랑 같음 $I(X;Y)$

 

6. Source channel coding problem

Two-stage로 진행된다. 

• Data compression
• Channel code

보통 binary로 많이 한다. 그리고 만능 $H(V) \leq C$면 다 된다.