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)$


  • 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