第五章 离散信道及其编码定理

1、1第5章 离散信道及信道编码定理5.1 信道分类信道分类5.2 离散无记忆信道离散无记忆信道5.3 信道编码和译码信道编码和译码5.4 信道编码定理信道编码定理5.5 信道编码定理的应用信道编码定理的应用5.6 信道的组合信道的组合2信源信源信源信源编码器编码器纠错纠错编码器编码器调制器调制器信信道道干扰源干扰源解调器解调器纠错纠错译码器译码器信源信源译码器译码器信宿信宿等效离散信道等效离散信道等效离散等效离散信源信源等效信宿等效信宿信道编码信道编码器器信道译码信道译码器器3通信系统模型通信系统模型信道编码：从消息到信道波形或矢量的映射信道编码：从消息到信道波形或矢量的映射信源编码信道编码信道

2、信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素 信道编码的作用：在信道编码的作用：在资源、可靠性和传信量资源、可靠性和传信量之之间选择一个好的工作点（有时还要考虑间选择一个好的工作点（有时还要考虑延时延时）4什么是信道？什么是信道？信道信道信号所通过的通道。信息信号所通过的通道。信息是抽象的，信道则是具体的。比如：二是抽象的，信道则是具体的。比如：二人对话，二人间的空气就是信道；打电人对话，二人间的空气就是信道；打电话，电话线就是信道；看电视，听收音话，电话线就是信道；看电视，听收音机，收、发间的空间就是信道。机，收

3、、发间的空间就是信道。 5信道的作用信道的作用 研究信道的目的研究信道的目的 极限传输能力极限传输能力6信道概述信道概述CAB21435发送波形集合接收波形集合PA2PA1PA3PA4PA5转移概率转移概率P(y|x)描述发送变量和接描述发送变量和接收变量之间的关系。收变量之间的关系。75.1 信道分类信道分类离散信道：输入输出均为离散事件集离散信道：输入输出均为离散事件集连续信道：输入输出空间均为连续事件集连续信道：输入输出空间均为连续事件集半连续信道：输入和输出一个是离散的，半连续信道：输入和输出一个是离散的，一个是连续的一个是连续的时间离散的连续信道：信道输入和输出是时间离散的连续信道：

4、信道输入和输出是连续的时间序列连续的时间序列波形信道：输入和输出都是时间的实函数波形信道：输入和输出都是时间的实函数x(t), y(t)根据输入输出空间的连续性划分根据输入输出空间的连续性划分8信道分类信道分类两端信道：两用户两端信道：两用户多端信道：多用户多端信道：多用户平稳平稳(恒参恒参)信道：参数不随时间变化信道：参数不随时间变化非平稳非平稳(随参随参)信道：参数随时间变化信道：参数随时间变化无记忆信道和有记忆信道无记忆信道和有记忆信道对称信道和非对称信道对称信道和非对称信道根据输入输出集合的个数、对称性划分根据输入输出集合的个数、对称性划分9一般信道的数学模型一般信道的数学模型 信道的

5、输入输出关系信道的输入输出关系 一般信道的数学模型一般信道的数学模型10 信道的输入输出关系信道的输入输出关系信号在信道中传输会引入噪声或干扰，它使信号在信道中传输会引入噪声或干扰，它使信号通过信道后产生错误和失真；信号通过信道后产生错误和失真；信道的输入和输出之间一般不是确定的函数信道的输入和输出之间一般不是确定的函数关系，而是关系，而是统计依赖关系统计依赖关系；知道了信道的输入信号、输出信号以及它们知道了信道的输入信号、输出信号以及它们之间的依赖关系，信道的全部特性就确定了。之间的依赖关系，信道的全部特性就确定了。11 一般信道的数学模型一般信道的数学模型数学模型的数学符号表示数学模型的数

6、学符号表示 X P(Y/X) Y输入和输出信号总可以分解成随机序列来研究。输入和输出信号总可以分解成随机序列来研究。随机序列中每个随机变量的取值可以是可数的离随机序列中每个随机变量的取值可以是可数的离散值，也可以是不可数的连续值。散值，也可以是不可数的连续值。12第5章 离散信道及信道编码定理5.1 信道分类信道分类5.2 离散无记忆信道离散无记忆信道5.3 信道编码和译码信道编码和译码5.4 信道编码定理信道编码定理5.5 信道编码定理的应用信道编码定理的应用5.6 信道的组合信道的组合135.2 离散无记忆信道离散无记忆信道离散无记忆信道定义离散无记忆信道定义(DMC)(DMC)DMCDM

7、C的信道容量的信道容量对称对称DMCDMC的信道容量计算的信道容量计算一般一般DMCDMC的信道容量计算的信道容量计算14离散无记忆信道定义离散无记忆信道定义Def. 设设(1)信道的输入输出空间信道的输入输出空间X= 0, 1, , K-1, Y= 0, 1, , J-1.( 2 ) 信 道 的 输 入 输 出 序 列 为信 道 的 输 入 输 出 序 列 为x=(x1,x2,xN),y=(y1,y2,yN) 时间序列时间序列( 3 ) 信 道 的 条 件 或 转 移 概 率 为信 道 的 条 件 或 转 移 概 率 为P(y|x)=P(y1,y2,yN|x1,x2,xN)。15离散无记忆信

8、道定义离散无记忆信道定义则 称 该 信 道 为则 称 该 信 道 为 离 散 无 记 忆 信 道 。离 散 无 记 忆 信 道 。（DMC）则称该信道为则称该信道为离散无记忆平稳信道离散无记忆平稳信道。 )|()|(kxjypkxjypmmnnNnnnxypxyP1)|()|(16离散无记忆信道定义离散无记忆信道定义“离散离散”的含义是时间离散，事件离散。的含义是时间离散，事件离散。即：信道的输入、输出时刻是离散的，即：信道的输入、输出时刻是离散的，且输入随机变量和输出随机变量都是离且输入随机变量和输出随机变量都是离散型的随机变量。散型的随机变量。“无记忆无记忆”的含义是信道响应没有时间的含义

9、是信道响应没有时间延迟，当时的输出只依赖于当时的输入。延迟，当时的输出只依赖于当时的输入。“平稳平稳”的含义是信道在不同时刻的响的含义是信道在不同时刻的响应特性是相同的。应特性是相同的。17离散无记忆信道定义离散无记忆信道定义“离散无记忆平稳信道离散无记忆平稳信道”是最简单的信是最简单的信道，信道在某一时刻道，信道在某一时刻u的响应特性的响应特性P(yn=j|xn=k)；就能很简单地计算出就能很简单地计算出信道在任意时间段信道在任意时间段的响应特性。的响应特性。18二元对称信道二元对称信道,BSC设设p=0.1给定一离散无记忆平稳信道给定一离散无记忆平稳信道1-p1-ppp11001 . 0)

10、 1 |0()0| 1 (9 . 0) 1 | 1 ()0|0(PPPP19有关有关DMC的容量定理的容量定理一、有关一、有关DMC的容量定理的容量定理（所说的（所说的DMC都是离散无记忆平稳信道）都是离散无记忆平稳信道）设设DMC在某个时刻输入随机变量为在某个时刻输入随机变量为X，输出随，输出随机变量为机变量为Y。信道响应特性为转移概率矩阵。信道响应特性为转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1，它 是 一 个它 是 一 个 K J 阶 矩 阵 （ 其 中阶 矩 阵 （ 其 中p(y|x)=P(Y=y|X=x)）。）。X 的概率分布为的概率分布为x, q(

11、x), x0, 1, , K-1。Y 的概率分布为的概率分布为y, w(y), y0, 1, , J-1。我们有以下的结论：我们有以下的结论：20有关有关DMC的容量定理的容量定理（1）转移概率矩阵的每一行都是一个概率）转移概率矩阵的每一行都是一个概率向量。向量。) 1| 1() 1| 1 () 1|0() 1 | 1() 1 | 1 () 1 |0() 0| 1() 0| 1 () 0|0(KJpKpKpJpppJppp1)| 1, 1 , 0()|(10 xXJYPxypxJy，对任意21有关有关DMC的容量定理的容量定理（2）对任意）对任意y0, 1, , J-1，由全概率公，由全概率公

12、式有。式有。10)|()()(Kxxypxqyw) 1| 1() 1| 1 () 1| 0() 1 | 1() 1 | 1 () 1 | 0() 0| 1() 0| 1 () 0| 0()1(,),1 (),0()1(,),1 (),0(KJpKpKpJpppJpppKqqqJwww22有关有关DMC的容量定理的容量定理（3）I(X; Y)是概率向量是概率向量q(x), x0, 1, , K-1和转移概率矩阵和转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1的函数的函数1010101010)|()()|(log)|()()()|(log)();(KzKxJyKxJy

13、zypzqxypxypxqywxypxyPYXI)|()()|()();(YXHXHXYHYHYXI23平均互信息量的凸性平均互信息量的凸性2),()()/(log)/()();(RyxdxdyypxypxypxpYXIyxypxypxypxpYXI,)()/(log)/()();(互信息是互信息是输入分布函数输入分布函数（输入概率密度）和（输入概率密度）和条件概率分布条件概率分布（条件概率密度）的函数。（条件概率密度）的函数。24平均互信息量的凸性平均互信息量的凸性Th. 平均互信息量平均互信息量I(X;Y)是输入信是输入信源概率分布源概率分布pX(x)的上凸函数。的上凸函数。. . 当信道

14、给定时，即条件概率当信道给定时，即条件概率p(y/x)给定下，给定下，I(X;Y)为输入概率分布的凸函数就保为输入概率分布的凸函数就保证了使传送信息量证了使传送信息量I(X;Y)为最大的最佳输入分为最大的最佳输入分布的存在。布的存在。（信道容量的讨论）（信道容量的讨论）25有关有关DMC的容量定理的容量定理（4）设转移概率矩阵）设转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1确定，希望选择概率向量确定，希望选择概率向量q(x), x0, 1, , K-1使使I(X; Y) 达到最大。达到最大。定义定义 离散无记忆信道的离散无记忆信道的信道容量信道容量定义为如下的定

15、义为如下的C。达到信道容量的输入概率分布。达到信道容量的输入概率分布x, q(x), x0, 1, , K-1称为称为最佳输入分布最佳输入分布。 其中其中);(max)(YXICxq26定理定理5.2.1NCYXIYXIYXINNNnnnNN);();();(1定理定理 令令Q(x)是是DMC的的N长输入字母序列的长输入字母序列的联合分布，联合分布，XN和和YN分别表示长为分别表示长为N的输入输的输入输出序列集合，出序列集合，Xn ,Yn表示第表示第n个输入和输出，个输入和输出，有有定理定理 说明对于说明对于DMC，N长序列的信息传输长序列的信息传输问题可以归结为单符号的信息传输问题问题可以归

16、结为单符号的信息传输问题27定理定理5.2.2Q=Q0,Q1,QK-1达到信道容量的充要条件达到信道容量的充要条件 0);(0);(kkQCYkxIQCYkxI1010)|()()|(log)|();(JyKzzypzqkypkypYkxI给定输入分布，若某个输入给定输入分布，若某个输入k与所有输出的平与所有输出的平均互信息量最大，就可以加大均互信息量最大，就可以加大Qk来增加来增加I(X;Y).不断调整输入可以使不断调整输入可以使I(k;Y)任意接近。任意接近。28定理定理5.2.2解释解释给定一个给定一个DMC信道的响应特性，也就是说给定一个信道的响应特性，也就是说给定一个信道的转移概率矩

17、阵信道的转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1，达到信道容量时所对应的最佳输入分布是达到信道容量时所对应的最佳输入分布是满足定理满足定理5.2.2条件的概率向量条件的概率向量q(x), x0, 1, , K-1 。其信道容量是每个使得其信道容量是每个使得q(k)0的的k所对应的所对应的半平均互信息量半平均互信息量I(X=k; Y)。29特殊信道的信道容量特殊信道的信道容量 具有一一对应关系的无噪信道具有一一对应关系的无噪信道 具有扩展性能的无损信道具有扩展性能的无损信道 具有归并性能的无噪信道具有归并性能的无噪信道 准对称信道准对称信道 对称信道对称信道3

18、0 具有一一对应关系的无噪信道具有一一对应关系的无噪信道0001001001001000100001000010000131X和和Y有确定的对应关系：有确定的对应关系：已知已知X后后Y没有不确定性，噪声熵没有不确定性，噪声熵 H(Y/X)=0；收到收到Y后，后，X也不存在不确定性，损失熵也不存在不确定性，损失熵 H(X/Y)=0;故有故有 I(X;Y)=H(X)=H(Y)。接收到符号接收到符号Y后，平均获得的信息量就是信源发出后，平均获得的信息量就是信源发出每个符号所含有的平均信息量，信道中无信息损失，每个符号所含有的平均信息量，信道中无信息损失，而且噪声熵也等于零，输出端而且噪声熵也等于零，

19、输出端Y的不确定性没有增加。的不确定性没有增加。严格地讲，这种输入输出有确定的一一对应关系的严格地讲，这种输入输出有确定的一一对应关系的信道，应称为信道，应称为无噪无损信道无噪无损信道。当信源呈等概率分布时，具有一一对应确定关系的当信源呈等概率分布时，具有一一对应确定关系的无噪信道达到信道容量无噪信道达到信道容量nXHYXICiixpxp2)()(log)(max);(max32 具有扩展性能的无损信道具有扩展性能的无损信道nm，输入，输入X的符号集的符号集个数小于输出个数小于输出Y的符号的符号集个数。集个数。)/()/(00000000)/()/()/(00000000)/()/()/(38

20、37262524131211xypxypxypxypxypxypxypxyp33每列中只有一个非零元素：每列中只有一个非零元素：已知已知Y后，后，X不再有任何不确定度，损失熵不再有任何不确定度，损失熵 H(X/Y)=0， I(X;Y)= H(X) -H(X/Y)= H(X) 。接收到符号接收到符号Y后，对发送的符号后，对发送的符号X是完全确定的，是完全确定的，损失熵为零，但噪声熵损失熵为零，但噪声熵H(Y/X)不为零。这类信道被不为零。这类信道被称为称为有噪无损信道有噪无损信道。信道容量为信道容量为与一一对应信道不同的是，此时输入端符号熵小于与一一对应信道不同的是，此时输入端符号熵小于输出端符

21、号熵，输出端符号熵， H(X) m，输入，输入X的符号集个数大于输出的符号集个数大于输出Y的符号集的符号集个数。个数。10001001000100135每行仅有一个非零元素，但每列的非零元素个数每行仅有一个非零元素，但每列的非零元素个数大于大于1：已知某一个已知某一个x xi i后，对应的后，对应的y yj j完全确定，信道噪声完全确定，信道噪声熵熵HH( (Y Y/ /X X)=0)=0。但是收到某一个但是收到某一个y yj j后，对应的后，对应的x xi i不完全确定，信道不完全确定，信道损失熵损失熵 HH( (X X/ /Y Y)0)0。 在这类信道中，接受到符号在这类信道中，接受到符号

22、Y Y后不能完全消除对后不能完全消除对X X的不确定性，信息有损失。但输出端的不确定性，信息有损失。但输出端Y Y的平均不的平均不确定性因噪声熵等于零而没有增加，所以这类信确定性因噪声熵等于零而没有增加，所以这类信道称为道称为无噪有损信道无噪有损信道也称也称确定信道确定信道。36每行仅有一个非零元素，但每列的非零元素个数大于每行仅有一个非零元素，但每列的非零元素个数大于1：信道容量为这 种 信 道 输 入 端 符 号 熵 大 于 输 出 端 符 号 熵 ，H(X)H(Y)。注意：在求信道容量时，调整的始终是输入端的概率分布p(xi) ，尽管信道容量式子中平均互信息I(X;Y)等于输出端符号熵H

23、(Y)，但是在求极大值时调整的仍然是输入端的概率分布p(xi) ，而不能用输出端的概率分布p(yj)来代替。mYHYXICiixpxp2)()(log)(max);(max37综合上述三种情况，若严格区分的话，凡损失熵等综合上述三种情况，若严格区分的话，凡损失熵等于零的信道称为于零的信道称为无损信道无损信道；凡噪声熵等于零的信道；凡噪声熵等于零的信道称为称为无噪信道无噪信道，而一一对应的无噪信道则为，而一一对应的无噪信道则为无噪无无噪无损信道损信道。对于对于无损信道无损信道，其信息传输率，其信息传输率R就是输入信源就是输入信源X输出输出每个符号携带的信息量每个符号携带的信息量(信源熵信源熵H(

24、X)，因此其信道，因此其信道容量为容量为 式中假设输入信源式中假设输入信源X的符号共有的符号共有n个，所以等概率个，所以等概率分布时信源熵最大。分布时信源熵最大。2()m ax()lo gipxCHXn38对于对于无噪信道无噪信道，其信道容量为，其信道容量为 式中假设输出信源式中假设输出信源Y的符号共有的符号共有m个，等概率分布个，等概率分布时时H(Y)最大最大,而且一定能找到一种输入分布使得输出而且一定能找到一种输入分布使得输出符号符号Y达到等概率分布。达到等概率分布。可见这些信道的信道容量可见这些信道的信道容量C只决定于信道的输入符号只决定于信道的输入符号数数n，或输出符号数，或输出符号数

25、m，与信源无关。，与信源无关。2()m ax()lo gipxCHYm39对称对称DMC容量的计算容量的计算定义定义 设设DMC的转移概率矩阵为的转移概率矩阵为 若若P的任一行是第一行的置换，则称信道的任一行是第一行的置换，则称信道关于关于输入为对称输入为对称的。的。若若P的任一列是第一列的置换，则称信道的任一列是第一列的置换，则称信道关于关于输出为对称输出为对称的。的。) 1|1() 1|1 () 1|0() 1 |1() 1 |1 () 1 |0()0|1()0|1 ()0|0(KJpKpKpJpppJpppP40对称对称DMC容量的计算容量的计算若若P所有行矢量都是第一行的置换，称为所有

26、行矢量都是第一行的置换，称为关于关于输入对称输入对称。)|(log)|()|()|(10kjpkjpxYHXYHJj8 . 01 . 01 . 01 . 01 . 08 . 0P10101010101010)|(1log)|()|(1log)|()()|(1log)|()()|(1log)|()()|(JyKxJyKxJyKxJykypkypkypkypxqxypxypxqxypxypxqXYH由于p(y|x)，y=0 J-1与p(y|k)，y=0 J-1互为置换41对称对称DMC容量的计算容量的计算P的所有列都是第一列的一种置换，的所有列都是第一列的一种置换，关于输出是关于输出是对称的对称的

27、当输入事件等概，当输入事件等概，Qk=1/KJjkpKkjpKkjpQjKkKkKkkj1)|0(1)|(1)|(101010无关：输出与8 . 02 . 05 . 05 . 02 . 08 . 0P此时此时p(y|x)，x=0 K-1与与p(0|x)，x=0 K-1互互为置换。为置换。42对称对称DMC的容量计算的容量计算输出集输出集Y可划为若干个子集可划为若干个子集,每个子集对应的信每个子集对应的信道转移概率矩阵道转移概率矩阵P中列所组成的子阵具有下列性中列所组成的子阵具有下列性质质每一行都是第一行的置换每一行都是第一行的置换每一列都是第一列的置换每一列都是第一列的置换 该信道称为该信道称

28、为准对称信道准对称信道准对称信道关于输入对称。准对称信道关于输入对称。Y的划分只有一个时，关于输入输出均对称的划分只有一个时，关于输入输出均对称称为称为对称信道对称信道43对称对称DMC的容量计算的容量计算几个简单的结论：几个简单的结论：（1）准对称信道一定是关于输入为对称的。）准对称信道一定是关于输入为对称的。（2）对称信道关于输入和输出都对称。）对称信道关于输入和输出都对称。（3）对称）对称DMC当输入分布等概时，输出分布等概。当输入分布等概时，输出分布等概。（4）准对称）准对称DMC当输入分布等概时，输出分布局当输入分布等概时，输出分布局部等概。（准对称部等概。（准对称DMC当输入分布等

29、概时，若当输入分布等概时，若j和和l属于转移概率矩阵的同一个列子集，则属于转移概率矩阵的同一个列子集，则wj=wl。）。）（5）对称信道未必有）对称信道未必有J=K。44对称对称DMC的容量计算的容量计算8 . 01 . 01 . 01 . 01 . 08 . 0P1 . 01 . 08 . 01 . 01 . 08 . 08 . 02 . 02 . 08 . 04 . 01 . 04 . 01 . 01 . 04 . 01 . 04 . 0准对称信道准对称信道对称信道对称信道45准对称准对称DMC容量的计算容量的计算定理定理 实现准对称实现准对称DMC信道容量的最佳输信道容量的最佳输入分布为

30、入分布为等概分布等概分布 sYjKiJjKiSijpKkjpkjpijpKkjpkjpYkxI101010)|(1)|(log)|()|(1)|(log)|();(YS：子阵中：子阵中每一列都是每一列都是第一列置换第一列置换对每个对每个j相同相同对每个对每个k相同相同值与值与k无关无关46对称对称DMC容量的计算容量的计算结论结论 实现对称实现对称DMC信道容量的输入分布信道容量的输入分布为为等概分布等概分布10)|(log)|(logJjkjpkjpJC10)|(log)|(logJjkjpkjpJC关于输入对称的关于输入对称的47K元对称信道容量计算元对称信道容量计算例：例：K元对称信道容

31、量计算元对称信道容量计算1, 1, 0,) 1/(,1)|(KjkjkKpjkpkjp当当) 1log()(log1log)1log()1 (logKppHKKppppKCK=2, C =1-H(p)48准对称信道准对称信道容量计算例：例：二元对称删除信道二元对称删除信道（准对称信道）（准对称信道）qpqppqqpP1121log)1 (log)1log()1 (2/ )1 (loglog2/ )1 ()1 (log)1 (qqppqpqpqppqqqqqpqpCqqqqP1001C=1-q （二元纯删除信道）（二元纯删除信道）49一般一般DMC的容量计算的容量计算一般一般DMC的信道容量与最

32、佳输入分布的计算的信道容量与最佳输入分布的计算 若若DMC的转移概率矩阵的转移概率矩阵P是是可逆方阵可逆方阵（此时（此时K=J，非，非奇异）。奇异）。则可以先假设最佳输入分布则可以先假设最佳输入分布q(x), x0, 1, , K-1 中中每个概率每个概率q(x)都满足都满足q(x)0。在这个假设下，。在这个假设下，求出信道容量求出信道容量C；然后求出最佳输入分布对应的然后求出最佳输入分布对应的“最佳输出分布最佳输出分布” w(y), y0, 1, , K-1 ；然后求出最佳输入分布然后求出最佳输入分布q(x), x0, 1, , K-1。50一般一般DMC的容量计算的容量计算此时，此时，10

33、)()|(log)|();(10KkywkypkypYkXICKy；10)|(log)|()(log)|(1010KkkypkypywCkypKyKy；合并：将方程变形，使未知量51一般一般DMC的容量计算的容量计算；101010) 1|(log) 1|() 1 |(log) 1 |() 0|(log) 0|() 1(log) 1 (log) 0 (log) 1| 1() 1| 0 () 1 | 1() 1 | 0 () 0| 1() 0| 0 (KyKyKyKypKypypypypypKwCwCwCKKpKpKppKpp这是这是K个未知量个未知量0, 1, , K-1 =C+logw(0),

34、 C+logw(1), , C+logw(K-1)的线性方程组，系数矩阵是可逆方阵，因此唯的线性方程组，系数矩阵是可逆方阵，因此唯一解出一解出0, 1, , K-1 52一般一般DMC的容量计算的容量计算另一个等式：另一个等式： w(0)+w(1)+w(K-1)=1。于是于是; 1222110CCCK;2222110CKjjKC2log)222log(110i=C+logw(i)53。求由；，求由；，求由；，求由)(, )/()()()(2)(2log)/(log)/()/(112121iniijijjCjmjjmjijijmjjijxpxypxpypypypCCxypxypxypjj一般离散

35、信道容量计算步骤一般离散信道容量计算步骤54一般一般DMC的容量计算例子的容量计算例子例例 设设DMC的输入事件为的输入事件为0, 1，输出事件为，输出事件为0, 1，转移概率矩阵为，转移概率矩阵为求信道容量和最佳输入分布。先假设最佳输入求信道容量和最佳输入分布。先假设最佳输入分布分布q(0), q(1) 满足满足q(0)0，q(1)0。因此。因此75. 025. 05 . 05 . 0) 1 | 1 () 1 | 0() 0| 1 () 0| 0(ppppP811281. 0175. 0log75. 025. 0log25. 05 . 0log5 . 05 . 0log5 . 075. 02

36、5. 05 . 05 . 01055一般一般DMC的容量计算例子的容量计算例子因此因此622562. 0377438. 1811281. 012123811281. 0175. 025. 05 . 05 . 0110)628082. 0 ,371918. 0()2 ,2()1 (),0(10CCww0345. 0034536. 1log)649773. 0384763. 0log()22log(10C)6570205. 0,3429795. 0(75. 025. 05 . 05 . 0)1 (),0()1 (),0(wwqq56第5章 离散信道及信道编码定理5.1 信道分类信道分类5.2 离散

37、无记忆信道离散无记忆信道5.3 信道编码和译码信道编码和译码5.4 信道编码定理信道编码定理5.5 信道编码定理的应用信道编码定理的应用57信道编码信道编码最简单的检错和纠错最简单的检错和纠错单个的字无法检错：扪单个的字无法检错：扪？词汇能够检错：我扪的词汇能够检错：我扪的我我扪扪的的词汇能够纠错：我扪的词汇能够纠错：我扪的我们的，我等的，我我们的，我等的，我辈的，我班的，辈的，我班的，原因分析：原因分析：“扪扪？”可以有几百个答案，但可以有几百个答案，但“我扪的我扪的？”的答案却很少。的答案却很少。结论：结论：课文以及词汇的概率分布的稀疏性可以课文以及词汇的概率分布的稀疏性可以用来检错和纠错

38、。用来检错和纠错。58信道编码信道编码K信息比特信息比特N编码比特编码比特编码器编码器(n0, k0)卷积码卷积码 (Convolutional codes)：m个分组相关，约束长度为个分组相关，约束长度为K=(m+1) k0编码速率编码速率00kRn(N, K)分组码分组码 (Block codes)：分组之间独立分组之间独立编码速率编码速率KRN卷积编码示意卷积编码示意59译码准则译码准则信息序列个数：信息序列个数：2KM可能的可能的N N 长二元序列个数：长二元序列个数：2N编码：编码： K长信息序列到长信息序列到N N 长二元序列空间的映射长二元序列空间的映射K长二元序列长二元序列空间

39、空间N长二元序列空间长二元序列空间60译码准则译码准则12(,),1,2,iiiiNxxxxiM12(,)Nyy yy接收矢量：接收矢量：码字：码字：信道信道12(,)Nyyyy译码译码编码编码12(,)mmmm Nxxxx12(,)mmmmNxxxx12(,)Kuu uu61译码准则译码准则erPP mm译码错误概率（误组率）译码错误概率（误组率）对特定接收序列对特定接收序列y y的译码错误概率的译码错误概率( )| erP yP mm y11KbekkPPK误比特率误比特率Bit error rate第第k位出错的概率位出错的概率62译码准则译码准则最小错误概率准则最小错误概率准则使使(

40、)| 1| errP yP mm yP mm y 最小最小最大后验概率准则最大后验概率准则最大后验概率准则最大后验概率准则| max| rrmP myP m y计算后验概率是困难的，通常针对具体信道（转移计算后验概率是困难的，通常针对具体信道（转移概率已知），采用概率已知），采用最大似然准则最大似然准则63离散序列译码离散序列译码() ( |)(| )( )mQ m P y xP m yy1( )() ( |)MmmyQ m P y x() ( |)() ( |)mmQ m P y xQ m P y xmm根据贝叶斯公式根据贝叶斯公式| max| rrmP myP m y若要求若要求等价于等价

41、于64离散序列译码离散序列译码() ( |)() ( |)mmQ m P y xQ m P y xmm若消息序列先验概率相等若消息序列先验概率相等( |)( |)mmP y xP y xmm得最大似然准则得最大似然准则ln ( |)ln ( |)mmP y xP y xmm最大后验准则最大后验准则| max| rrmP myP m y65离散序列译码离散序列译码译码是由译码是由YN到到UL的映射，将的映射，将YN划分为划分为M个不相交子集个不相交子集x1x2xMYNY1Y2YMCmY是是Ym的补集的补集( |)Cmemmy YPP y x若消息若消息m的先验概率为的先验概率为Q(m),则平均译

42、码错误则平均译码错误概率为概率为MmemePmQP1)(66离散序列译码离散序列译码最大后验最大后验概率译码概率译码最大似然译码最大似然译码所有消息等概所有消息等概q元对称信道元对称信道最小汉明最小汉明距离译码距离译码汉明距离汉明距离：两个码字：两个码字 U U、V V 之间对应码元之间对应码元位上符号取值不同的个数，称为码字位上符号取值不同的个数，称为码字 U U、V V 之间的汉明距离。之间的汉明距离。例如例如：两个码字：两个码字 U U=0011101,=0011101,V V=0100111=0100111，它们之间第它们之间第2 2、3 3、4 4和和6 6位不同。因此，码字位不同。

43、因此，码字 U U 和和 V V 的距离为的距离为4 4。67离散序列译码离散序列译码对两种译码准则的评述对两种译码准则的评述l最大后验概率准则最大后验概率准则具有很好的直观合理性。具有很好的直观合理性。收到收到y的条件下，的条件下，最可能发送的是哪个码字最可能发送的是哪个码字，就认为发送的是哪个码字，就认为发送的是哪个码字”。l最大似然概率准则最大似然概率准则（最小距离准则）所具有（最小距离准则）所具有的直观合理性弱一些。的直观合理性弱一些。发送哪个码字的条件发送哪个码字的条件下，最可能收到下，最可能收到y，就认为发送的是哪个码，就认为发送的是哪个码字字。68离散序列译码离散序列译码对两种译

44、码准则的评述对两种译码准则的评述l最大似然概率准则（最小距离准则）的实现最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：比最大后验概率准则的实现更简单： 前者只需要看哪个码字与前者只需要看哪个码字与y的的Hamming距离距离最小；后者需要知道各码字的概率分布，然最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。后用贝叶斯公式计算并比较后验概率。69离散序列译码离散序列译码例例 两个消息等概，两个消息等概，x1=0000，x2=1111，通过二元对称信道，转移概率通过二元对称信道，转移概率ppppp11译码规则如下：译码规则如下：当当(Y1Y2Y3Y

45、4)中中1的个数为的个数为0或或1时，时，(Y1Y2Y3Y4)(0000)0；当当(Y1Y2Y3Y4)中中1的个数为的个数为3或或4时，时，(Y1Y2Y3Y4)(1111)1；当当(Y1Y2Y3Y4)中中1的个数为的个数为2时，时，(0011)、(1100)、(1001)(0000) 0，(0101)、(1010)、(0110)(1111) 1。译码规则显然是译码规则显然是最小距离准则最小距离准则。 70离散序列译码离散序列译码译码规则是译码规则是最小距离准则最小距离准则。 何时何时检测检测到信道传输错误？当到信道传输错误？当(Y1Y2Y3Y4)不是一个码字不是一个码字时，检测到信道传输错误。

46、时，检测到信道传输错误。换句话说，换句话说，(Y1Y2Y3Y4)与原发码字与原发码字(U1U2U3U4) 的的Hamming距离距离1且且3时，检测到信道传输错误。时，检测到信道传输错误。因此，信道传输有错误但能检测出错误的概率为因此，信道传输有错误但能检测出错误的概率为133422243114)1 ()1 ()1 (ppCppCppC71离散序列译码离散序列译码何时何时正确译码正确译码（正确接收）？（正确接收）？当当(Y1Y2Y3Y4)与原发码字与原发码字(U1U2U3U4) 的的Hamming距距离离1时，正确译码；时，正确译码；当当(Y1Y2Y3Y4)与原发码字与原发码字(U1U2U3U

47、4) 的的Hamming距距离离=2时，一半能正确译码，另一半不能正确译码时，一半能正确译码，另一半不能正确译码；当当(Y1Y2Y3Y4)与原发码字与原发码字(U1U2U3U4) 的的Hamming距距离离3时，不能正确译码。时，不能正确译码。正确译码（正确接收）的概率为正确译码（正确接收）的概率为222431144004)1 (21)1 ()1 (ppCppCppC72第5章 离散信道及信道编码定理5.1 信道分类信道分类5.2 离散无记忆信道离散无记忆信道5.3 信道编码和译码信道编码和译码5.4 信道编码定理信道编码定理5.5 信道编码定理的应用信道编码定理的应用73信道编码定理信道编码

48、定理DMCP(y|x),(21Nxxxx),(21NyyyyNinnxypp1)|()|(xy令编码速率为令编码速率为R R，则各码字的标号集为，则各码字的标号集为1,21,2NRNR 。编码函数编码函数译码函数译码函数:1,2NRNEX:1,2NNRD Y74信道编码定理信道编码定理发送消息发送消息 1,2NRmNYy( )1, 2NRmD y(|)empp mm mmemNRepp21平均误组率平均误组率发送发送m的误组率的误组率对给定离散无记忆信道和任意对给定离散无记忆信道和任意e e 00，若有一种编，若有一种编码速率为码速率为R R 的码，在的码，在N N足够大时，能使足够大时，能使p pe e e e，就，就称称R R 是是可达可达的。的。 75信道编码定理（信道编码定理（ Shannon 第二定理第二定理）定理定理( (ShannonShannon信道编码定理信道编码定理) )，给定容量为，给定容量为C C的离散的离散无记忆信道无记忆信道XX，p(x|y)p(x|y)，YY，若编码速率，若编码速率RCRC，则，则R R是可达的。是可达的。存在性定理，从理论上证明，平均错误译码概率趋存