第六章——有躁信道编码定理_费诺不等式

二、错误概率和译码规则

2.1、错误概率

1.1 在有噪信道中传输消息是会发生错误的，为了减少错误，提高可靠性，首先分析错误概率与哪些因素有关。

与错误概率有关的因素：

信道统计特性（p199）
译码的规则

2.2、译码规则

假设输入符号集X={ $x_{1},x_{2},...,x_{r}$ }, 输出符号集Y={ $y_{1},y_{2},...,y_{s}$ }。若每一个输出符号 $y_{j}$ ，都能找到一个特定的函数 $f(y_{j})$ 对应唯一的一个输入符号 $x_{i}$ 。

即： $F(y_{j})=x_{i}$ （j=1,2,3,…,s；i=1,2,3,…,r） (这就是译码规则）

译码规则不同，正确或错误的概率也就不同。

例如：有一个单符号信道，信道矩阵为：

$P=\begin {bmatrix } 0.5 & 0.3&0.2 \\ 0.2& 0.3& 0.5\\ 0.3 & 0.3& 0.4 \end{bmatrix}$ ，矩阵的横表示 $b_{1},b_{2},b_{3}$ ，列表示 $a_{1},a_{2},a_{3}$ 。我设计一个译码规则:

$\left\{\begin{matrix} F(b_{1})=a_{3}& \\ F(b_{2})=a_{1} & \\ F(b_{3})=a_{2} & \end{matrix}\right.$ 意思是，每输入符号 $b_{1}$ ，都能找到一个特定的函数 $f(b_{1})$ 对应唯一的输入符号 $a_{3}$ ；每输入符号 $b_{2}$ ，都能找到一个特定的函数 $f(b_{2})$ 对应唯一的输入符号 $a_{1 }$ ；每输入符号 $b_{3 }$ ，都能找到一个特定的函数 $f(b_{3})$ 对应唯一的输入符号 $a_{2}$ 。

三、最大后验概率准则与最大似然译码准则

译码规则的选择需要根据平均错误概率为最小的选择，那什么是平均错误概率，以及如何计算？

平均错误概率：经过译码后平均接收到一个符号所产生的错误大小。

正确译码概率： $P[f(y_{j})|y_{j}]=P(x_{i}|y_{j})$ （后验概率：在输出已知情况下，输入的概率）

错误译码概率： $P(e|y_{j})=1-P[f(y_{j})|y_{j}]=1-P(x_{i}|y_{j})=\sum_{k\neq i} P(x_{k}|y_{j})$

3.1、最大后验概率准则（MAP）

按照 ${\color{Orange} P({a}^*|b_{j})\geq P(a_{i}|b_{j})}$ 定义的译码规则，叫最大后验概率准则或者叫最小错误概率准则。（考点）

解题步骤：

第一步：转移概率矩阵乘以 $P(x_{i})$ 得到联合概率分布矩阵。

第二步：以每列矩阵的最大概率相对应的输入概率 $x_{i}$ 作为译码准则。

第三步：所有译码结果对应的联合概率之和为正确概率，矩阵中其余元素之和为错误概率。

3.2、最大似然译码准则（ML）

通常情况下，最大后验概率未知，从而介绍极大似然译码准则。

按照 ${\color{Orange} P(b_{j}|{a}^*)\geq P(b_{j}|a_{i})}$ 定义的译码规则，叫最大似然译码准则。（考点）

解题步骤：

第一步：以转移概率矩阵每列中最大的一个元素对应的 $x_{i}$ 作为译码准则。

第二步：假如是等概率输入，所有译码准则所对应的转移概率之和乘以 $\frac{1}{r}$ 为正确概率，其余矩阵元素之和乘以 $\frac{1}{r}$ 为错误概率。（其中 $\frac{1}{r}$ 是等概率分布的概率）假如输入的不是等概率，就是每一行译码准则乘以对应 $x_{i}$ 之和即为正确概率，每一行的其余元素乘以对应的 $x_{i}$ 之和即为错误概率。

看到这里晕了吗？？？？上栗子吧。。。

3.3、举个栗子

第一个栗子：

若信道矩阵 $P=\begin{pmatrix} 0.5 & 0.3 & 0.2\\ 0.2 & 0.3&0.5 \\ 0.3& 0.3 & 0.4 \end{pmatrix}$ ，设输入概率为 $\frac{1}{6},\frac{1}{3},\frac{1}{2}$ ，分别根据最小错误概率准则和最大似然译码准则确定译码规则，求得平均错误概率。（第一个栗子我详细写，其余内容都一样，不再详细，所以你一定要先看懂我第一个栗子。）

不论采用什么译码准则，费诺不等式均成立。
信道疑义度由两部分组成：
- $H(P_{E})$ ：是否发生错误的不确定性。即收到y后产生值为 $P_{E}$ 的平均错误概率的平均不确定度。
- 当错误发生后，确定由（r-1）个输入符号中哪一个引起的错误的不确定，其最大值为 $P_{E}log(r-1)$

物理意义：当信源、信道给定时，信道疑义度就给定了译码错误的下限。

五、错误概率与译码方法

对于给定信道，输入符号概率一定时，选择译码规则可使得 $P_{E}$ 最小。
一般数字通信系统要求平均错误概率 $P_{E}$ 在 $10^{-6}$ 和 $10^{-9}$ 数量级，甚至更低。
费诺不等式表明，要进一步降低 $P_{E}$ ，仅仅制定译码规则已经不够了，需要对信道的输入符号进行编码。

二元信道中，有什么办法使得错误概率降低吗?

在发送端把消息重复发送几遍，也就是增加消息的传输时间，就可使得在接收端接收信息时错误减小，从而提高了通信的可靠性。

简单重复编码：在发送端把消息多重复几遍，可以是接收端接收信息时错误概率减小。（比如说，你妈叫你回家吃饭，你第一遍没听到，那么再来一次，你妈叫你回家吃饭。）

在二元对称信道中，发送消息0和1 ，采用简单重复编码，将长度n=1的两个二元序列变为长度n=3的二元序列，那么我们称这两个长度为3的二元序列为码字，于是信道输入端就有两个码字000和111。但是在输出端，由于信道干扰的作用，码字中各个码元都有可能发生错误，那么就有可能发生 8种可能的输出序列。分别为000,001,010,011,100,101,110,111。这样的一种信道可以将其看成三次无记忆扩展信道。

信道矩阵如下：

信息传输率（码率）： $R=\frac{logM}{n}$ （比特/码符号）

若传输每个码符号平均需要t秒钟，则编码后单位时间传输的信息量： $R=\frac{logM}{nt}$ （比特/秒）

六、码字距离

6.1汉明距离

长度为n的两个符号序列（码字） $\alpha _{i}$ 和 $\beta _{j}$ 之间的距离是指 $\alpha _{i}$ 和 $\beta _{j}$ 之间对应位置上不同码元的个数，用符号D( $\alpha _{i},\beta _{j}$ ）表示，简称 $D_{ij}$ 。
在某一码C中，任意两个码字的汉明距离的最小值称为该码C的最小距离。最小距离 $d_{min}$ 与该码的错误概率有关。

6.2最小距离译码准则

$D_{ij}$ 越大， $P(\beta _{j}|\alpha _{i})$ 越小， $D_{ij}$ 越小， $P(\beta _{j}|\alpha _{i})$ 越大。我们可以将最大似然译码准则与最小距离译码准则联系起来。

最后的解题步骤类似最大似然译码准则。。。。

七、纠错能力与检测能力

编码可以纠正 $\mu$ 个及以内错误的充要条件是： $d_{min}=2\mu +1$

编码可以检测 $t$ 个及以内错误的充要条件是： $d_{min}=t +1$

举个栗子：

八、香农第二定理

内容：设有一离散无记忆平均信源，其信道容量C，若编码信息率R<C，当码长n足够大时，则至少存在一种编码，使得译码错误概率任意小；相反，若信息传输率R>C，则码长无论多大，总也找不到是译码错误概率任意小的编码。

“高效率，高可靠性”的信道编码存在，但未指出具体方法，该定理指出来信道编码的极限性能，为信道编码的研究指明方向。
高效率：信息传输率接近信道容量。
高可靠性：译码差错任意小。
存在这种信道编码的必要条件为：R<C

目录一、前言二、错误概率和译码规则2.1、错误概率2.2、译码规则三、最大后验概率准则与最大似然译码准则3.1、最大后验概率准则（MAP）3.2、最大似然译码准则（ML）3.3、举个栗子四、费诺不等式五、错误概率与译码方法六、码字距离6.1汉明距离6.2最小距离译码准则七、纠错能力与检测能力八、香农第二定理互联网的广大朋友们，大家好！即将迈入期末的坟墓，我们一起走进信息论的知识总结。由于我复习的顺序可能不是按目录走，如果... 信源编码：最原始的信院编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。相对地， 信道编码 是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。 信道编码 ： 1948年Shannon极限理论 →1950..

UA MATH636 信息论5 信道编码 定理 信道编码 问题信道容量的正式定义 信道编码 定理 Joint Typical SetJoint AEP 上一篇简介里面介绍了通讯的过程，并用下面的流程图来表示了这个过程，并且引入了一些基本概念。这一讲先对上一篇的例1做一个推广，然后介绍一下分析 信道编码 的工具。 WXYVSourceEncoderNoisy ChannelDecoderReceiver 例1续：S...

接收端接收到的码字序列{R} 信道的特性可以用信道转移概率矩阵P(R/C)来表示。其中，更为重要的是信道后验概率矩阵P(C/R)，第i行第j列的概率p(cj/ri)表示接收端接收到码字ri时，发送端送的是码字cj的概率译码规则会对其译码性能，即误码率产生影响。具体数学上表示为：PE受信道转移概率矩阵P(R/C)、发送端码字概率P( C )...

第 2 章物理层一、单项选择题 1.在无噪声情况下，若某通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是（）。 A．12kbps B．24kbps C．48kbps D．96kbps 【答案】B 【解析】采用四个相位每个相位有 4 种振幅的 QAM 调制技术后，每个信号可以有 16 种变化，每个信号可以传输 log216＝4bit 的数据。而链路带宽为 3KHz，采样频率为带宽的两倍，即 3kHz＊2＝6kHz，所以最大传输速

信号：数据的电气或电磁表现，数据在传输过程中的存在形式。码元：用一个固定时常的信号波形表示一位k进制数字。数据通信：数字计算机或其他数字终端之间的通信，其主要划分为信源、信宿和信道。信源：产生和发送数据的源头；信宿：接受数据的终点。信道：信号的传输媒介。数据传输方式：串行传输和并行传输。通信双方的交互方式：单工通信、半双工通信和全双工通信。速率(数据率)：指数据的传输速率，表示单位时间内传输的数据量，可用码元传输速率和信息传输速率表示。码元传输速率考虑二元信号（BPSK）的检测问题。当假设H0H_0H0为真时，信源产生−1-1−1，当H1H_1H1为真时，信源产生+1+1+1。信源叠加均值为0、方差为σ2\sigma^2σ2的高斯噪声nnn，成为观测信号yyy。这样，在两个假设下，观测信号模型为 {H0:y=−1+nH1:y=+1+n(1) \left\{\begin{array}{l} H_0:y=-1+n \\ H_{1}:y=+1+n \end{array}\right.\tag{1} {H0:y=−1+nH1:y=+1+n