UA MATH636 信息論5 信道編碼定理的證明

• Random Coding Scheme
• • 平均錯誤率
  • 最大錯誤率
• 逆命題的證明

信道編碼定理說的是所有小于 $C$的傳輸率是可實現的。這里的 $C$就是我們之前定義的
$$C=\underset{p(X)}{\max }I(X;Y)$$
因此這個表述指的是
$$C=\underset{p(X)}{\max }I(X;Y)=\max \{R:Risachievable\}$$
這一篇主要就證明一下這個定理和它的逆命題。

先簡單描述一下符號和設定：
因為$M=2^{nR}$，記codebook為$\mathcal{C}=\{{\mathcal{X}}^n(i){\}}_{i=1}^{2^{nR}}$，注意這個codebook是從總體$p(X)$中隨機生成的。假設信號是$\{1,2,?,M\}$上的均勻分布，假設某一次信源發出的信號為$w$，則信源編碼器傳送到噪聲信道上的碼為${\mathcal{X}}^n(w)$。經過噪聲信道傳輸到接收端的解碼器上的碼為$y^n$，
$$p(y^n|{\mathcal{X}}^n(w))=\prod _{i=1}^{n}p(y^i|{\mathcal{X}}^n(w))$$
經過解碼后得到信號$w$的估計量$\hat{w}$，它滿足${\mathcal{X}}^n(\hat{w})$是唯一能與$y^n$構成joint typical的碼。
上面這個系統叫做一個random coding scheme。

Random Coding Scheme

平均錯誤率

記事件$\hat{w}=w$為$\mathrm{E}$，則
$$p(\mathrm{E})=\sum _{?\mathcal{C}}p(\mathcal{C})p_e^{(n)}(\mathcal{C})$$
因為平均錯誤率比最大錯誤率更好分析，所以先從平均錯誤率開始。
$$p(\mathrm{E})=\sum _{?\mathcal{C}}p(\mathcal{C})?\frac{1}{2^{nR}}\sum _{w=1}^{2^{nR}}{\lambda }_w(\mathcal{C})?=\frac{1}{2^{nR}}\sum _{w=1}^{2^{nR}}\left[\sum _{?\mathcal{C}}p(\mathcal{C}){\lambda }_w(\mathcal{C})\right]$$
因為中括號里面的求和式對所有可能的codebook的，所以實際上這個量會與$w$無關，不失一般性可以將上式寫成
$$p(\mathrm{E})=\sum _{?\mathcal{C}}p(\mathcal{C}){\lambda }_1(\mathcal{C})=p(?|w=1)$$
當$({\mathcal{X}}^n(i),y^n)\in /A_{?}^{(n)}$時，錯誤會發生。記事件$E_i=\{({\mathcal{X}}^n(i),y^n)\in A_{?}^{(n)}\}$，則根據Bonferroni不等式
$$\begin{gathered} p(\mathrm{E}|w=1)=p(E_1^C\cup E_2\cup ?E_{2^{nR}}) \\ \le p(E_1^C|w=1)+\sum _{i=2}^{2^{nR}}p(E_i|w=1) \end{gathered}$$
根據Joint AEP的性質1：
$$p(E_1^C|w=1)=p({\mathcal{X}}^n(i),y^n)\in /A_{?}^{(n)})\le ?$$
考慮$$p(E_i|w=1)=p({\mathcal{X}}^n(i),y^n)\in /A_{?}^{(n)})$$
因為$y^n$是碼${\mathcal{X}}^n(1)$經過噪聲信道傳輸到接收端的解碼器的，并且${\mathcal{X}}^n(1)$與${\mathcal{X}}^n(i)$是獨立的，因此${\mathcal{X}}^n(i),y^n$是獨立的，所以根據Joint AEP性質3：
$$p(E_i|w=1)\le 2^{?n(I(X;Y)?3?)}$$
帶入到錯誤率中
$$p(E_1^C|w=1)\le ?+2^{nR}{2}^{?n(I(X;Y)?3?)}=?+2^{?n(I(X;Y)?R?3?)}$$
要讓這個上界收斂，需要$2^{?n(I(X;Y)?R?3?)}$被$?$控制，從而
$$R<I(X;Y)?3?$$
這里就可以看出信道容量的形式了，錯誤率也被控制住了。下面再從平均錯誤率到最大錯誤率，看看結論會不會變。

最大錯誤率

已經證明了$p(\mathrm{E})\le 2?$，因此
$$p(\mathrm{E})=\sum _{?\mathcal{C}}p(\mathcal{C})p(E|\mathcal{C})\le 2?$$
$?{\mathcal{C}}^{?}$，$p(\mathrm{E}|{\mathcal{C}}^{?})\le 2?$。其中
$$p(\mathrm{E}|{\mathcal{C}}^{?})=\frac{1}{2^{nR}}\sum _{i=1}^{2^{nR}}{\lambda }_i({\mathcal{C}}^{?})$$
根據這個表達式我們可以判斷，在這$2^{nR}$個錯誤率${\lambda }_i({\mathcal{C}}^{?})$中，至少有一半是比$4?$更小的。將更小的這一半作為一個新的codebook，則新的codebook共有$2^{nR?1}$個code，最大錯誤率會比$4?$小。注意到此時的傳輸率為
$${\log }_2{2}^{nR?1}/n=R?\frac{1}{n}\to R$$
即傳輸率不會受到影響，定理結果不變。

逆命題的證明

考慮$w\to {\mathcal{X}}^n(w)\to y^n\to \hat{w}$這個數據過程是一個Markov Chain。根據Fano不等式：
$$\begin{gathered} H(E)\le h(p(E))+p(E){\log }_2(M) \\ =h(p(E))+nRp(E)\le 1+nRp(E) \end{gathered}$$
因為信號是$\{1,2,?,M\}$上的均勻分布，根據數據處理不等式
$$\begin{gathered} H(w)=nR=H(w)?H(w|\hat{w})+H(w|\hat{w}) \\ =I(w;\hat{w})+H(w|\hat{w})\le I(w;\hat{w})+1+nRp(E) \\ \le I({\mathcal{X}}^n(w);y^n)+1+nRp(E) \end{gathered}$$
其中
$$\begin{gathered} I({\mathcal{X}}^n(w);y^n)=H(y^n)?H(y^n|{\mathcal{X}}^n(w)) \\ =H(y^n)?\sum _{i=1}^{n}H(y^i|{\mathcal{X}}^n(w),y^{i?1}) \end{gathered}$$
根據噪聲信道的無記憶性，如果${\mathcal{X}}^n(w)=(x^1,?,x^n)$，
$$\begin{gathered} I({\mathcal{X}}^n(w);y^n)=H(y^n)?\sum _{i=1}^{n}H(y^i|x^i) \\ \le \sum _{i=1}^{n}H(y^i)?\sum _{i=1}^{n}H(y^i|x^i)=\sum _{i=1}^{n}I(x_i;y_i) \\ \le \sum _{i=1}^n\max I(X;Y)=nC \end{gathered}$$
因此
$$nR\le nC+1+nRp(E)?R\le C+Rp(E)+\frac{1}{n}$$
假設$R$是可實現的，則$n\to \infty$時，
$$\frac{1}{n}\to 0,p(E)\to 0$$
則$R\le C$

總結

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

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