课程主页:https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页:http://shannon.cm.nctu.edu.tw/

课程视频:https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第十讲,这一讲主要介绍了香农信道编码定理,对应视频17,18。

通过DMC进行数据传输的分组码

定长数据传输码

给定正整数$n$和$M$,以及具有输入字母$\mathcal X$和输出字母$\mathcal Y$的离散信道,此信道的固定长度数据传输码(或块码)的块长为$n$,每个信道符号的速率为$\frac{1}{n} \log _{2} M$比特,块码用$\mathcal{C}_{n}=(n, M)$表示,由如下内容组成:

  1. $M$个用于传输的消息的信息

  2. 编码函数

    生成长度为$n$的码字$f(1), f(2), \cdots, f(M) \in \mathcal{X}^{n}$。这$M$个码字被称为codebook,通常写成$\{f(1), f(2), \cdots, f(M)\}$

  3. 解码函数$g: \mathcal{Y}^{n} \rightarrow\{1,2, \ldots, M\}$

平均误差概率

$\mathcal{C}_{n}=(n, M)$的平均误差为(编码函数为$f(.)$,解码函数为$g(.)$):

其中

是在消息$w$通过信道发送的情况下编码发生解码错误的条件概率。

最大误差概率

显然

根据$\lambda_{w}\left(\mathcal{C}_{n}\right)$从大到小排序,将前一半的对应的码字丢弃,得到$\mathcal{C}_{n}^{\prime}$,那么

从而

其中码率分别为

联合典型集

$n$元组对$\left(x^{n}, y^{n}\right)$关于无记忆分布

的$\delta$联合典型集$\mathcal{F}_{n}(\delta)$定义为

联合AEP

$\left\{\left(X_{i}, Y_{i}\right)\right\}_{i=1}^{\infty}$是DMS的无记忆独立对,那么随着$n\to \infty$,我们有

证明:

利用大数定律即可。

Shannon-McMillan-Breiman定理

$\left\{\left(X_{i}, Y_{i}\right)\right\}_{i=1}^{\infty}$是DMS的无记忆独立对,联合熵为$H(X, Y)$,$\forall \delta >0$,我们可以选择充分大的$n$,使得联合$\delta$典型集$\mathcal{F}_{n}(\delta)$满足如下性质:

  1. 对于充分大的$n$,我们有$P_{X^{n}, Y^{n} }\left(\mathcal{F}_{n}^{c}(\delta)\right)<\delta$

  2. 对于充分大的$n$,$\left|\mathcal{F}_{n}(\delta)\right|>(1-\delta) 2^{n(H(X)-\delta)}$;对于每个$n$,$\left|\mathcal{F}_{n}(\delta)\right| \leq 2^{n(H(X)+\delta)}$

  3. 如果$\left(x^{n}, y^{n}\right) \in \mathcal{F}_{n}(\delta)$,那么

证明:

同Lecture 6 AEP的推论。

操作容量(Operational capacity)

对于离散系统,比率$R$是可达的,如果存在$\left(n, M_{n}\right)$信道编码$\mathcal{C}_{n}$,满足

信道的操作容量$C_{op}$是所有可达比率的上确界:

香农信道编码定理

考虑具有有限输入字母$\mathcal X$,有限输出字母$\mathcal Y$和转移分布概率$P_{Y | X}(y |x)$的DMC。定义信道容量(或信息容量)

那么如下事实成立。

  1. Forward(可达性):对于任意$0<\varepsilon<1$,存在$\gamma>0$以及数据传输分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$,满足

    以及对于充分大的$n$,我们有

    其中$P_{e}\left(\mathcal{C}_{n}\right)$表示关于分块码$\mathcal{C}_{n}$的平均误差概率。

  2. Converse:对于任意$0<\varepsilon<1$,以及满足如下条件的数据传输分块码序列$\left\{\mathcal{C}_{n}=\left(n, M_{n}\right)\right\}_{n=1}^{\infty}$

    对于充分大的$n$,都有

    其中

    令$n\to \infty$,我们有

    这说明对于所有足够大的$n$,编码的错误概率都无法任意趋于$0$。

补充说明:

  1. 注意到

    而$P_{Y|X}$是已知的,上述方法更容易计算信道容量。

  2. 对于固定的$P_{Y | X}$,$I\left(P_{X}, P_{Y | X}\right)$关于$P_X$连续且凹,所以极值可取到。

证明:

Forward

Forward:

当$C=0$时,取$M_n=1$,此时

另一方面

所以结论成立。

当$C>0$时,固定$\varepsilon \in(0,1)$以及满足$0<\gamma<\min \{4 \varepsilon, C\}$的$\gamma$。

注意到存在$N_0$,对于$n>N_0$,我们可以选择整数$M_n$,使其满足(当$n$充分大时总是能成立的)

定义

令$P_{\hat{X} }$为满足如下条件的分布

其中

注意到由DMC的性质,我们可得

步骤1:编码构造

  • 对于分块长$n$,根据分布$P_{\hat{X}^{n} }\left(x^{n}\right)$独立选择$M_{n}$个信道输入。

  • 选择的$M_{n}$个信道输入产生codebook

    定义编码和解码函数$f_n(.),g_n(.)$,其中

    以及

    其中

步骤2:计算条件错误率

第一项表示输出不是联合典型的,第二项表示多于联合典型的元素不止一个。

计算平均误码率可得

其中

步骤3:计算平均错误率

现在对大括号内部的项进行化简

最后一个不等号是因为

因此对于充分大的$n$,我们有

所以必然存在$\mathcal C_n$,满足

Converse

Converse:

回顾第四讲的Fano不等式:

令$X,Y$为两个相关随机变量,$X$取值于$\mathcal X$,$Y$取值于$\mathcal Y$,$\mathcal X$有限,$\mathcal Y$可数无限。假设$\hat{X}:=g(Y)$为通过观测$Y$得到对于$X$的估计,其中$g: \mathcal{Y} \rightarrow \mathcal{X}$是给定的估计函数。定义误差概率

那么如下不等式成立

其中

给定信息$W$($W$关于$\left\{1,2, \cdots, M_{n}\right\}$服从均匀分布),在DMC上通过码字$X^{n}(W)=f_{n}(W)$传输信息,$Y^{n}$是信道输出,在接收端,得到信息$\hat{W}=g_{n}\left(Y^{n}\right)$,那么误差率为

利用Fano不等式可得

回顾下图

所以对于任意$\left(n, M_{n}\right)$分块信道码$\mathcal C_n$,

是马尔可夫链,所以由数据处理不等式,我们有

另一方面

注意$W$服从均匀分布,所以

对其变型可得

如果

即满足定理中的定义

那么对任意$0<\varepsilon<1$,存在$N$,使得$n\ge N$时,都有

这是因为如果上式不成立,那么存在无限多个$n$,满足

所以

这就与

矛盾。

结合该不等式可得

图示:

定义

上述定理实际上是说明