第一章 绪论
第二章 离散信源及信息测度
第三章 离散信道及其信道容量
第四章 连续信源和波形信道
第五章 无失真信源编码定理
第六章 有噪信道编码
第七章 限失真信源编码
第八章 无失真信源编码
第九章 纠错编码

第六章 有噪信道编码

6.1 信道编码概述

• 目标：提高信道的可靠性；
• 信道编码：按照一定的规则给信源编码后的码符号序列增加些冗余信息，使其变成具有一定数学规律的码符号序列。
• 信道译码：接收到码符号序列后，按照与信道编码器相同的数学规律，去掉符号序列中的冗余符号。
• 模型：

• 信道编码的基本思想：利用相关性来检测和纠正传输过程中产生的差错。

6.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~~~(i=1,2,...,r~~,j=1,2,..,s)

• 共有r^s种译码规则。

错误概率

设译码规则为：

F(y_j)=x_i\begin{cases} 当输入符号是x_i时，&译码正确\\ 当输入符号为除x_i以外的(r-1)种符号时,&译码错误 \end{cases}

正确译码的概率（条件正确概率）：

p[F(y_j)|y_j]=p(x_i|y_j)

错误译码的概率（条件错误概率）：

p(e|y_j)=1-p(x_i|y_j)=1-p[F(y_j)|y_j]

平均错误译码概率P_E：

P_E=\sum_{j=1}^s p(y_j)p(e|y_j)=\sum_{j=1}^s p(y_j)\{1-p[F(y_j)|y_j]\}

平均正确译码概率\overline P_E：

\begin{aligned} \\ \overline{P}_E& =\sum ^s_{j=1}p(y_j)p[F(y_j)|y_j]\end{aligned}

译码规则的选择原则

• 选择原则：使平均错误译码概率P_E最小。
• 两个重要的译码准则：

1. 最大后验概率译码规则
2. 极大似然译码规则

最大后验概率译码规则

令F(y_j)=x^_,x^_\in X，而x^*应满足条件：

p(x^*|y_j)\ge p(x_i|y_j)~~i=1,2,...,r

称满足上述条件的译码函数对应的译码规则为最大后验概率译码。

• 译码方法：

1. 转移概率矩阵每行乘p(x_i)，得联合概率矩阵；
2. 以每列中最大概率对应的x_i作为译码结果；
3. 所有译码结果所对应的联合概率的和为正确概率，矩阵中其他元素的和为错误概率。

极大似然译码规则

令F(y_j)=x^*,x^*{\in X}，而x^*应满足条件：

p(y_j|x^*)\ge p(y_j|x_i)~~i=1,2,...,r

称满足上述条件的译码函数对应的译码规则为极大似然译码规则。

• 译码方法：

1. 当输入符号等概分布或先验概率未知时，采用极大似然译码准则；
2. 以转移概率矩阵中每列中最大的一个元素对应的x_i作为译码结果；
3. 所有译码结果所对应的转移概率的和再乘以1/r为正确概率，其他矩阵元素的和再乘以1/r为错误概率。

Fano不等式

平均错误概率与信道疑义度H(X|Y)满足不等式：

H(X|Y)\le H(P_E)+P_E\log(r-1)

• 不论采用什么译码准则，该不等式都成立。
• 信道疑义度H(X|Y)由两部分构成：
  1. 是否发生错误的不确定性：收到y后产生值为P_E的平均错误概率的平均不确定度H(P_E)；
  2. 当错误发生后，确定由(r-1)个输入符号中哪一个引起错误的不确定性。这个不确定性的最大值为P_E\log(r-1)。

6.3 错误概率与编码方法

• 对于给定信道（统计特性确定)，在输入符号概率分布一定时，选择译码规则可使P达到最小值。
• 一般数字通信系统要求平均错译概率P_E在10^{-6}到10^{-9}数量级，甚至更低。
• 要找到进一步降低P_E的方法，仅仅通过制定译码规则已不够，需要对信道的输入符号进行某种形式的编码。

简单重复编码

在发送端把消息多重复发几遍，可以使接收端接受消息时错误减少。

• 在输入符号集（M个符号）等概的条件下，每个符号平均携带的最大信息量是\log M；

• 当用n个码元符号来传输M个信源符号时，每个码符号携带的平均信息量，即信道信息传输率为：

  R=\frac{\log M}n

• 随着重复次数n的增加，可使P_E减小很多，但信息传输率R也减少很多。

汉明距离

设\alpha_i=x_{i_{1}}x_{i_{2}}...x_{i_{n}}和\beta_j=y_{j_1}y_{j_2}...y_{j_n}表示两个长度为n的码符号序列，定义

D(\alpha_i,\beta_j)=\sum\limits_{k=1}^n x_{i_k}\oplus y_{j_k}

称D(\alpha_i,\beta_j)为码字\alpha_i和\beta_j之间的汉明距离。

• 最小汉明距离：在二元码C中，任意两个码字之间的汉明距离的最小值，被称为码C的最小汉明距离：

  D_{\min}=\min[D(w_i,w_j)]~~（w_i\neq w_j,~~w_i,w_j\in C）

• 最小汉明距离与极大似然译码准则：

  设\alpha_i=x_{i_1}x_{i_2}...x_{i_n}和\beta_j=y_{j_1}y_{j_2}...y_{j_n}表示两个长度为n的码符号序列，\alpha_i为信道的输入，\beta_j为信道的输出，\alpha_i和\beta_j的汉明距离为D。

  对于离散平稳无记忆二元信道，有：

  p(\beta_j\mid\alpha_i)=p(y_{j_1}y_{j_2}\dots y_{j_n}\mid x_{i_1}x_{i_2}\dots x_{i_n})=\prod\limits_{k=1}^n p(y_{j_k}\mid x_{i_k})=p^D\overline{p}^{n-D}

  通常情况下：p<0.5,\overline p>0.5，D越小，p(\beta_j|\alpha_i)就越大。

  D(\alpha^*,\beta_j)=D_{\min}(\alpha_i,\beta_j)

• 编码方法：使M个许用码字中的任何两个不同码字之间的汉明距离尽量大。

6.4 有噪信道编码定理

联合\epsilon典型序列

设(x,y)是一对长度为n的随机序列，联合概率分布满足：

p(xy)=\prod\limits_{i=1}^n p(x_i y_i)

满足下列条件的序列称为联合\epsilon序列：

1. x是\epsilon典型序列，即对于任意小的正数\epsilon，存在n使：

   \begin{vmatrix}\frac{1}{n}\text{log}\frac{1}{p(x)}-H(X)\end{vmatrix}<\varepsilon

2. y是\epsilon典型序列，即对于任意小的正数\epsilon，存在n使：

   \begin{vmatrix}\frac{1}{n}\text{log}\frac{1}{p(y)}-H(Y)\end{vmatrix}<\varepsilon

3. 对于任意小的正数\epsilon，存在n使：

   \begin{vmatrix}\frac{1}{n}\text{log}\frac{1}{p(xy)}-H(XY)\end{vmatrix}<\varepsilon

以G_{\epsilon n}(x)表示X^n中x的典型序列集，以G_{\epsilon n}(y)表示Y^n中y的典型序列集，以G_{\epsilon n}(xy)表示X^nY^n中xy的典型序列集，即：

G_{\epsilon n}(x)=\{(x,y)\in X^n\times Y^n\}

联合\varepsilon典型序列是那些平均联合自信息以\varepsilon任意小地接近联合熵的n长序列对的集合。

联合渐进等分割性

• 第一个性质：

  对于任意小的正数\varepsilon\ge0,\delta\ge0，当n足够大时，则有：

  \begin{gathered} {P(G}_{\varepsilon n}(x))\geq1-\delta \\ \textit{P}(G_{sn}(y))\geq1-\delta \\ \textit{P}(G_{_{\partial n}}({xy}))\geq1-\delta \end{gathered}

  当n足够大时，联合\epsilon典型序列出现的概率大于1-\delta。

• 第二个性质：

  \begin{aligned} &2^{-{n}[H(X)+\varepsilon]}<{P}({x})<2^{-{n}[H(X)-\varepsilon]} \\ &2^{-n[H(Y)+\varepsilon]}<{P}({y})<2^{-n[H(Y)-\varepsilon]} \\ &2^{-n[H(XY)+\varepsilon]}<{P}({xy})<2^{-n[H(XY)-\varepsilon]} \end{aligned}

  所有联合\varepsilon典型序列出现的概率近似相等，即典型序列为渐进等概序列，可粗略的认为典型序列出现的概率都等于2^{-NH(XY)}。

• 第三个性质：

  \begin{gathered} (1-\delta)2^{n[H(X)-\varepsilon]}\leq\left\|{G}_{cn}({x})\right\|\leq2^{n[{H}(X)+\varepsilon]} \\ (1-\delta)2^{n[H(Y)-\varepsilon]}\leq\left\|{G}_{\varepsilon n}({y})\right\|\leq2^{n[H(Y)+\varepsilon]} \\ (1-\delta)2^{n[H(XY)-\varepsilon]}\leq\left\|{G}_{\varepsilon n}({xy})\right\|\leq2^{n[H(XY)+\varepsilon]} \end{gathered}

  所有联合\varepsilon典型序列虽然都是高概率集，但它含有的序列数常常比非典型序列数要少很多。

上述性质说明：在两个随机变量的情况下，X^n,Y^n和X^nY^n都具有渐进等分割性。

联合ε典型序列对(x,y)是联合空间中经常出现的高概率序列对。这些高概率序列对的出现概率接近相等，并且所有联合典型序列对(x,y)的概率和趋于1。

联合\varepsilon典型序列对(x,y)是那些信道输入和输出之间密切关联、经常出现的序列对。

有噪信道编码定理（香农第二定理）

设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率R<C，当码长n足够大时，则至少存在一种编码，使译码错误概率任意小。

• 输入符号的序列长度为n，则共有r^n个序列可供选择。

• 从其中找到M\le2^{n(C-\varepsilon)}个码字组成一组码，这样编码后获得的信息传输率：

  R=\frac{\log M}{n}=\frac{\log 2^{n(C-\varepsilon)}}{n}=C-\varepsilon

• 说明

1. 信息传输速率R=\frac {\log{M}}n为每个码符号所携带的信息量（单位：比特/码符号）
2. 香农第二定理仅指出了满足这种要求的信道编码的存在性，没有给出具体的编码方法。
3. 该定理给出了信道编码的极限性能，为信道编码的研究指明方向，是信道编码理论的基础。
4. 信道容量是进行可靠传输的最大信息传输速率。

有噪信道编码逆定理

设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率R>C，即M>2^{nC}，则无论码长n取多大，也不可能使译码错误概率任意小。

习题

判断对错：

1. 信道编码的目标是提高信道的可靠性。
2. 信道编码是将信源编码后的码符号序列变成具有一定数学规律的序列。
3. 信道译码是根据接收到的码符号序列去掉冗余符号。
4. 最大后验概率译码规则是选择联合概率矩阵中每列中最大概率对应的符号作为译码结果。
5. 信道编码的基本思想是利用相关性来检测和纠正传输过程中的差错。
6. 有噪信道编码定理是指只要待传送的信息传输率小于信道容量，就至少存在一种编码方案。
7. 极大似然译码规则是选择输出符号集中与接收到的符号最接近的符号作为译码结果。
8. 有噪信道编码是为了提高信道效率。
9. 信道编码的核心思想是利用冗余信息来检测和纠正传输过程中的错误
10. 信道编码的目标是增加冗余信息以提高信道的可靠性。
11. 信道译码是在接收到码符号序列后，按照与信道编码器相同的数学规律添加冗余符号。
12. 最大后验概率译码规则是利用相关性来检测和纠正传输过程中的差错。
13. 极大似然译码规则是在输入符号等概分布或先验概率未知的情况下使用的译码准则。
14. 有噪信道编码定理是在离散无记忆平稳信道的情况下成立的。
15. 有噪信道编码定理是信道编码理论的基础。
16. 信息论和编码是完全不同的领域，不需要相互结合讨论。
17. 在有噪信道编码中，编码方法的目标是使许用码字的汉明距离尽量小。
18. 最大后验概率译码规则在错误发生后可以使错误概率最小化。

• 答案

  1-对、2-对、3-对、4-对、5-对、6-对、7-对、8-错、9-对、10-对、11-错、12-对、13-对、14-对、15-对、16-错、17-错、18-对