Information Theory, Inference and Learning Algorithms Lecture 8

课程主页:http://www.inference.org.uk/mackay/itprnn/,http://www.inference.org.uk/itprnn_lectures/

课程视频:https://www.bilibili.com/video/BV14b411G7wn?from=search&seid=1786094286746981315,https://www.youtube.com/watch?v=BCiZc0n6COY&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6

课程书籍:https://book.douban.com/subject/1893050/

这次回顾第八讲,第八讲介绍了噪声信道编码定理。

备注:笔记参考了中文书籍。

噪声信道编码定理

  1. 对于每个离散的无记忆信道,信道容量

    具有如下性质。对于任意 $\varepsilon>0$ 和 $R<C,$ 当 $N$ 足够大时,存在一个长度为 $N$ 的码 $,$ 码率 $\geqslant R$ 和一个译码算法,使得最大分组差错概率 $<\varepsilon$。

  2. 如果误码率$p_{\mathrm{b} }$是可接受的,则不高于 $R\left(p_{\mathrm{b} }\right)$的码率是可达的,其中

  3. 对于任意 $p_{\mathrm{b} },$ 高于$R\left(p_{\mathrm{b} }\right)$的码率是不可达的:

    在 $R, p_{\mathrm{b} }$平面上,可证明区域(1,2)可达,而区域(3)不可达。

备注:

特定码$\mathscr B$的分组差错概率为

误码率 $p_{\mathrm{b} }$的定义为

最大分组差错概率定义为

联合典型序列

基本概念

联合典型性:一对长度为$N$的序列$\boldsymbol{x}$和$\boldsymbol{y}$, 被定义为关于分布 $P(x, y)$ 是联合典型的(容差为 $\beta),$ 如果满足

联合典型集:$J_{N \beta}$ 是长度为$N$的所有联合典型序列对的集合。

联合典型性定理

总体$(XY)^N$定义为

从总体$(X Y)^{N}$中选择$\boldsymbol{x}$和$\boldsymbol{y}$,则有

  1. 当 $N \rightarrow \infty$ 时,$\boldsymbol{x}$和$\boldsymbol{y}$是联合典型序列 (容差$\beta$)的概率趋向于 $1_{\circ}$

  2. 联合典型序列的数量$|J_{N\beta}|$接近 $2^{N H(X, Y)}$,精确地有

  3. 如果 $\boldsymbol{x}^{\prime} \sim X^{N}$ 和 $\boldsymbol{y}^{\prime} \sim Y^{N}$,即 $\boldsymbol{x}^{\prime}$ 和 $\boldsymbol{y}^{\prime}$ 是与 $P(\boldsymbol{x}, \boldsymbol{y})$ 具有相同边缘分布的独立样本,则$(\boldsymbol{x}^{\prime}, \boldsymbol{y}^{\prime})$ 属于联合典型集的概率约为 $2^{-N I\left(X; Y\right)}$ 。更精确的表示为

证明:

第一部分:

类似Lecture 3的思路即可:

首先定义:

利用弱大数定律,我们有

注意到我们有

所以

第二部分:

将Lecture 3的$P(x)$替换为$P(x,y)$即可

第三部分:

典型集的图示如下:

两个独立的典型向量是联合典型的概率为

因为独立典型对的总数是虚线矩形的面积 $2^{N H(X)} 2^{N H(Y)}$,联合典型对的数量约为$2^{NH(X,Y)}$,所以出现一个典型对的概率约为

噪声信道编码定理的证明

随机编码和典型集译码

考虑如下译码系统:

  1. 固定$P(x)$,并按照如下概率随机地产生$\left(N, N R^{\prime}\right)=(N, K)$码$\mathscr{B}$ 中的$S=2^{N{R}^{\prime} }$个码字(即均匀分布):

  2. 发送方和接收方都知道该码字。

  3. 从 $\{1,2, \cdots, 2^{N R}\}$ 中选择消息$s$,并传输$\boldsymbol{x}^{(s)}$。接收信号为 $\boldsymbol{y}$,满足:

  4. 信号由典型集译码法来译码:

    如果 $\left(\boldsymbol{x}^{(\hat s)}, \boldsymbol{y}\right)$ 是联合典型的且没有其他 $s^{\prime}$ 使得 $\left(\boldsymbol{x}^{\left(s^{\prime}\right)}, \boldsymbol{y}\right)$ 是联合典型的,则$y$被译码为$\hat s$;否则认为译码失败($\hat s=0$)

  5. 如果$\hat s\neq s$,则出现一个译码错误。

证明的第一部分

在上译码系统的基础上进行证明,即我们希望证明

不失一般性,假设$s=1$。

我们首先证明误码率

可以任意小,这里注意译码一共有两种错误:

  • (a)输出$y$和输入$x^{(s)}$不是联合典型的
  • (b)$\mathscr{B}$有其他码字与$y$是联合典型的

(a)令输入$x^{(1)}$和输出$y$不是联合典型的概率为$\delta$,那么根据联合典型定理的第一部分,当$N\to \infty$时$\delta \to 0$,所以对于任意$\delta $,都存在$N(\delta)$,使得

(b)根据联合典型定理的第三部分,对于$s’\neq 1$,$x^{(s’)}$和$y$是联合典型的概率$\le 2^{-N(I(X ; Y)-3 \boldsymbol{\beta})}$,注意到$s’$一共有$2^{NR’}-1$个值可以考虑。

综合上述两点,误码率 $p_{\mathrm{b} }$满足

所以如果

那么随着$N$增加,$p_{\mathrm{B} }$必然小于$2\delta$。

现在进行三个改动:

  1. 选择输入$P(x)$为最优输入分布。于是$R’ < I(X;Y)-3\beta$变成$R’<C-3\beta$(注意$\beta$是任意值,所以$R’$可以和$C$任意逼近)

  2. 因为

    所以必然存在一个码,使得

  3. 为了证明最大差错概率$p_{\text{BM} }$也可以很小,现在对码进行修改:将$P(\hat{s} \neq s | \mathscr{P}) $从大到小排列,记为$P_1\le P_2\le \ldots \le P_{2^{NR’} }$,对应的先验概率为记为$P^{(i)}$,那么由于先验是均匀分布(我们的假设),所以

    注意$p_{\text{B} }<2\delta$,所以

    现在删除$P_{i}, i> 2^{NR’-1}$的码字,用剩下的码字定义一个新码,该新码有$2^{NR’-1}$个码字,最大分组差错概率$<4\delta$,码率为$(NR’-1)/N= R’-1/N$。

定理的第二第三部分暂时还没吃透,这部分的笔记后续补充。

本文标题:Information Theory, Inference and Learning Algorithms Lecture 8

文章作者:Doraemonzzz

发布时间:2020年06月22日 - 19:59:00

最后更新:2020年06月28日 - 14:48:11

原始链接:http://doraemonzzz.com/2020/06/22/Information Theory, Inference and Learning Algorithms Lecture 8/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。