UA MATH636 信息論5 信道編碼定理

• 信道編碼問題
• • 信道容量的正式定義
• 信道編碼定理
• • Joint Typical Set
  • • Joint AEP

上一篇簡介里面介紹了通訊的過程，并用下面的流程圖來表示了這個過程，并且引入了一些基本概念。這一講先對上一篇的例1做一個推廣，然后介紹一下分析信道編碼的工具。

WXYVSourceEncoderNoisy ChannelDecoderReceiver

例1續：Symmetric Channels
假設矩陣$P$表示$p(Y|X)$，其中$P_{ij}=P(Y_j|X_i)$，定義$P_{i.}$表示矩陣$P$的第$i$行，$P_{.j}$表示矩陣$P$的第$j$列。已知$Y=\{Y_1,Y_2,?,Y_{l_Y}\}$，$X=\{X_1,X_2,?,X_{l_X}\}$。之所以提出這類信道是因為它的容量比較簡單好算。對于矩陣$P$而言，它有下面三條性質

${\sum }_{j=1}^{l_y}{P}_{ij}=1$，這條性質就是概率的歸一性

$?i,i^{\prime }$, $?\sigma \in P_{l_y}$, $P_{i^{\prime }.}=\sigma (P_{i.})$

$?j,j^{\prime }$, $?\tau \in P_{l_x}$, $P_{.j}=\tau (P_{.j})$，性質2和3定義了對稱性

其中$P_{l_y}$與$P_{l_x}$分別為$l_y$與$l_x$階的置換運算的集合。這類信道的容量為
$$C={\log }_2{l}_y?H(P_{i.})$$
其中$H(P_{i.})$表示任一行的熵。
證明：
$$I(X;Y)=H(Y)?H(Y|X)$$
先計算$H(Y|X)$，根據性質2
$$H(Y|X)=\sum _{i}p(X=X_i)H(P_{i.})=H(P_{i.})$$
比較直觀地，根據熵的有界性，$H(Y)\le {\log }_2{l}_y$，當且僅當$Y$為均勻分布時成立，要讓$Y$為均勻分布，根據性質1，只需$X$為均勻分布即可。
注意到這個證明不需要性質3，如果定義weakly symmetric channel（只滿足性質1,2），則同樣有
$$C={\log }_2{l}_y?H(P_{i.})$$

在正式定義信道編碼問題之前，先給出可以從$I(X;Y)$直接看出的信道容量的兩個性質：

$0\le C\le \min ({\log }_2{l}_x,{\log }_2{l}_y)$

$C$具有唯一性

事實上找信道容量并不是一個容易的事情，對于更復雜的信道以及網絡信道，找信道容量一般是要做比較復雜的優化的，證明完這個定理后會介紹計算信道容量的Blahut-Arimoto算法，并比較這個算法與EM算法的區別。

信道編碼問題

信道容量的正式定義

假設$W\in \{1,2,?,M\}$，即信源可能發送$M$種可能的信息，編碼器記作${\mathcal{X}}^n:W\to X$，$n$表示使用的信道數目。則信源編碼的codebook可以記作$\mathcal{D}=\{{\mathcal{X}}^n(1),?,{\mathcal{X}}^n(M)\}$，從而$X\in \mathcal{D}$。
信道可以用$p(Y|X)$表示，不妨假設$X$與$Y$是$n$維字符，即$X=(X^1,?,X^n)$，$Y=(Y^1,?,Y^n)$，假設信道是無記憶的，即
$$p(Y|X)=\prod _{i=1}^{n}p(Y^i|X^i)$$
記$Y$的值域為${\mathcal{Y}}^n$。解碼器可以表示為$g:{\mathcal{Y}}^n\to \{1,2,?,M\}$，$g$為解碼函數。信道編碼想要研究的對象之一就是這組通訊編碼（可以記為$(M,n)$-code）的錯誤率${\lambda }_i$：
$$\begin{gathered} {\lambda }_i=p(g(Y)=i|X={\mathcal{X}}^n(i)) \\ =\sum _{Y\in {\mathcal{Y}}^n}p(Y|{\mathcal{X}}^n(i))I(g(Y)=i) \end{gathered}$$
由此可以定義最大錯誤率
$${\lambda }^{(n)}=\underset{i}{\max }{\lambda }_i$$
以及平均錯誤率
$$p_e^{(n)}=\frac{1}{M}\sum _{i=1}^M{\lambda }_i$$
定義$(M,n)$-code的傳輸率為
$$R=\frac{{\log }_{2}M}{n}$$
通常給定一個傳輸率，使用$n$個channel可以傳輸的信號為
$$M=ceiling(2^{nR})$$
實際上是$M=2^{nR}$，但一般要取整數。如果${\lambda }^{(n)}\to 0$，稱傳輸率$R$對于$(M,n)$-code為可實現的（achievable）。現在可以給出信道容量的正式定義：
$$\max \{R:Risachievable\}$$

信道編碼定理

信道編碼定理是通訊理論中一個非常重要的定理，但它的表述非常簡單：所有小于$C$的傳輸率是可實現的。這里的$C$就是我們之前定義的
$$C=\underset{p(X)}{\max }I(X;Y)$$
因此這個表述指的是
$$C=\underset{p(X)}{\max }I(X;Y)=\max \{R:Risachievable\}$$
這個表述的逆命題同樣成立，對于任何$(M,n)$-code，如果${\lambda }^{(n)}\to 0$，則$R\le C$。證明信道編碼定理需要random coding的思想以及Joint typical set，證明逆命題需要Fano不等式以及數據處理不等式，在證明之前先介紹一下需要的工具。

Joint Typical Set

從聯合分布$p(x,y)$中生成隨機樣本$(x^n,y^n)=\{x_i,y_i{\}}_{i=1}^n$，記Joint Typical Set為$A_{?}^{(n)}$，它是$(x^n,y^n)$的一個集合，并且滿足以下性質：

$|?\frac{{\log }_{2}p(x^n)}{n}?H(X)|<?$，Marginal typical on x

$|?\frac{{\log }_{2}p(y^n)}{n}?H(Y)|<?$，Marginal typical on y

$|?\frac{{\log }_{2}p(x^n,y^n)}{n}?H(X,Y)|<?$，Joint typical on (x,y)

Joint AEP

之前講信源編碼的時候就講過AEP了，這里推廣到joint case：記$({\tilde{x}}^n,{\tilde{y}}^n)$是從$p(x)p(y)$中生成的隨機樣本

$P((x^n,y^n)\in A_{?}^{(n)})\to 1,asn\to \infty$

$|A_{?}^{(n)})|\le 2^{n(H(X,Y)+?)}$，當$n$足夠大時，$|A_{?}^{(n)})|\ge (1??)2^{n(H(X,Y)??)}$

$P(({\tilde{x}}^n,{\tilde{y}}^n)\in A_{?}^{(n)})$的上界為$2^{?n(I(X;Y)?3?)}$，下界為$(1??)2^{?n(I(X;Y)+3?)}$，當$n$足夠大時下界成立。

前兩個性質可以用之前的證明直接推廣就可以了，方法比較平凡。第三個性質之前沒有遇到過，這里給一個簡單證明：
$$\begin{gathered} P(({\tilde{x}}^n,{\tilde{y}}^n)\in A_{?}^{(n)})=\sum _{({\tilde{x}}^n,{\tilde{y}}^n)\in A_{?}^{(n)}}p({\tilde{x}}^n,{\tilde{y}}^n)=\sum _{({\tilde{x}}^n,{\tilde{y}}^n)\in A_{?}^{(n)}}p({\tilde{x}}^n)p({\tilde{y}}^n) \\ \le \sum _{({\tilde{x}}^n,{\tilde{y}}^n)\in A_{?}^{(n)}}{2}^{?n(H(X)??)}{2}^{?n(H(Y)??)}=|A_{?}^{(n)}|2^{?n(H(X)+H(Y)?2?)} \end{gathered}$$
將性質2帶入，可以得到上界。類似的過程可以證明下界。

總結

以上是生活随笔為你收集整理的UA MATH636 信息论5 信道编码定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。