5. Channel Capacity

Channel Capacity

• $(\mathcal{X},p(y|x),\mathcal{Y})$: send $x$, with probability $p(y|x)$, receiver get $y$
• Channel capacity: $C=\max_{p(x)}I(X;Y)$
• Strategy to calculate $C$
  • $I(X;Y)=H(Y)-H(Y|X)$
  • convex sets: $d_{\min}=\min_{a\in A,b\in B}d(a,b)$
• Examples:
  • Noiseless Binary Channel: $C=1,p(x)=(\frac{1}{2},\frac{1}{2})$
  • Noisy Channel with nonoverlapping Outputs: in fact not noisy
  • Noisy Typewriter: $\log13$
  • Binary Symmetric Channel: $C=1-H(p)$
  • Binary Erasure Channel: $\max_{p(x)}H(Y)-H(\alpha)=1-P_e$
• symmetric channel: channel transition matrix row and columnr are permutations of each other $C=\log|\mathcal{Y}|-H(r)$
• weakly symmetric: rows

Channel Coding Theorem

• Message $W$ (Encoder) $X^n$ (Channel) $Y^n$ (Decoder) $\hat W$
• $\max \frac{H(W)}{n}$
• Message: can be ordered and denoted by index, $\log M$ symbols
• discrete memoryless channel (DMC): $p(y_k|x^k,y^{k-1})=p(y_k|x_k)$
• without feedback: $p(x_k|x^{k-1},y^{k-1})=p(x_k|x^{k-1})$
• memoryless + no feedback: $H(Y^n|X^n)=\sum_{i=1}^nH(Y_i|X_i)$
• Markov chain: $W\rightarrow X^n\rightarrow Y^n\rightarrow\hat W$
• DMC: $C=\max I(X;Y)$

DMC

• codebook ($f(w)=x^n$) shared between sender and receiver
• $(M,n)$ code
  • index set $\{1,2,\cdots, M\}$
  • encoding function $f(x):\{1,2,\cdots,M\}\rightarrow\mathcal{X}^n$, yielding codewords $x^n(1),\cdots,x^n(M)$
  • decoding function $g(x)$
• Conditional probability of error: $\lambda_i=\sum_{y^n}p(y^n|x^n(i))[g(y^n\neq i)]$
  • maximal probability of error: $\lambda^{(n)}=\max \lambda_i$
  • average: $P_e^{(n)}=\frac{1}{M}\sum\lambda_i$
• rate $R$ of $(M, n)$ code: $R=\frac{\log M}{n}$ bits per transmission
  • achievable $R$: sequence $(2^{nR}, n)$ codes such that the maximal probability of error $\lambda(n)\rightarrow 0$ when $n\rightarrow\infty$
• capacity: supremum of all achievable rates
• Channel coding theorem: $C=\max_{p(x)}I(X;Y)$
  • Achievability: For any $r<C,\exists (2^{nr},n)$ code
  • Converse: For any $r>C,\lambda_e>0$

Intuition for Channel Capacity: $2^{nI(X;Y)}=2^{n(H(Y)-H(Y|X))}$ （手电筒）

Proof: $R\leq C$; $\forall R<C$, achievable

Feedback Capacity

• $(2^{nR}, n)$ feedback code: sequence of mappings $x_i(W,Y^{i-1})$
• $C_{FB}=C=\max_{p(x)}I(X;Y)$ (Feedback cannot increase capacity)

Source-Channel Separation

• data compression: $R>H$
• data transmission: $R<C$
• Source-channel coding theorem
  • if $V_1,V_2,\cdots,V_n$ is a finite alphabet stochastic process that satisfies the AEP and $H(\mathcal{V})<C$, exists source-channel code with probability of error $\rightarrow 0$
  • if $H(\mathcal{V})>C$, probability of error is bounded away from zero

Error Correction Code

• Repetition code
• Parity check code
• Hamming code (n,k,d)
• BCH code
• Convolutional code
• LDPC code
• Polar code