离散信道及其编码定理

离散信道及其编码定理演示文稿1现在是1页\一共有75页\编辑于星期日（优选）离散信道及其编码定理现在是2页\一共有75页\编辑于星期日3通信系统模型信道编码：从消息到信道波形或矢量的映射

信道编码的作用：在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）现在是3页\一共有75页\编辑于星期日4什么是信道？信道——信号所通过的通道。信息是抽象的，信道则是具体的。比如：二人对话，二人间的空气就是信道；打电话，电话线就是信道；看电视，听收音机，收、发间的空间就是信道。现在是4页\一共有75页\编辑于星期日5信道的作用

在通信系统中信道主要用于传输。研究信道的目的在通信系统中研究信道，主要是为了描述、度量、分析不同类型信道，计算其容量，即极限传输能力，并分析其特性。现在是5页\一共有75页\编辑于星期日6信道概述转移概率P(y|x)描述发送变量和接收变量之间的关系。现在是6页\一共有75页\编辑于星期日75.1信道分类离散信道：输入输出均为离散事件集连续信道：输入输出空间均为连续事件集半连续信道：输入和输出一个是离散的，一个是连续的时间离散的连续信道：信道输入和输出是连续的时间序列波形信道：输入和输出都是时间的实函数x(t),y(t)根据输入输出空间的连续性划分现在是7页\一共有75页\编辑于星期日8信道分类两端信道：两用户多端信道：多用户平稳(恒参)信道：参数不随时间变化非平稳(随参)信道：参数随时间变化无记忆信道和有记忆信道对称信道和非对称信道根据输入输出集合的个数、对称性划分现在是8页\一共有75页\编辑于星期日9一般信道的数学模型①信道的输入输出关系②一般信道的数学模型现在是9页\一共有75页\编辑于星期日10①信道的输入输出关系信号在信道中传输会引入噪声或干扰，它使信号通过信道后产生错误和失真；信道的输入和输出之间一般不是确定的函数关系，而是统计依赖关系；知道了信道的输入信号、输出信号以及它们之间的依赖关系，信道的全部特性就确定了。现在是10页\一共有75页\编辑于星期日11②一般信道的数学模型数学模型的数学符号表示

{X

P(Y/X)Y}输入和输出信号总可以分解成随机序列来研究。随机序列中每个随机变量的取值可以是可数的离散值，也可以是不可数的连续值。现在是11页\一共有75页\编辑于星期日12第5章离散信道及信道编码定理5.1信道分类5.2离散无记忆信道5.3信道编码和译码5.4信道编码定理5.5信道编码定理的应用5.6信道的组合现在是12页\一共有75页\编辑于星期日135.2离散无记忆信道离散无记忆信道定义(DMC)DMC的信道容量对称DMC的信道容量计算一般DMC的信道容量计算现在是13页\一共有75页\编辑于星期日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)。现在是14页\一共有75页\编辑于星期日15离散无记忆信道定义则称该信道为离散无记忆信道。（DMC）则称该信道为离散无记忆平稳信道。

现在是15页\一共有75页\编辑于星期日16离散无记忆信道定义“离散”的含义是时间离散，事件离散。即：信道的输入、输出时刻是离散的，且输入随机变量和输出随机变量都是离散型的随机变量。“无记忆”的含义是信道响应没有时间延迟，当时的输出只依赖于当时的输入。“平稳”的含义是信道在不同时刻的响应特性是相同的。现在是16页\一共有75页\编辑于星期日17离散无记忆信道定义“离散无记忆平稳信道”是最简单的信道，信道在某一时刻u的响应特性P(yn=j|xn=k)；就能很简单地计算出信道在任意时间段的响应特性。现在是17页\一共有75页\编辑于星期日18二元对称信道,BSC设p=0.1给定一离散无记忆平稳信道1-p1-ppp1100现在是18页\一共有75页\编辑于星期日19有关DMC的容量定理一、有关DMC的容量定理（所说的DMC都是离散无记忆平稳信道）设DMC在某个时刻输入随机变量为X，输出随机变量为Y。信道响应特性为转移概率矩阵[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]，它是一个K×J阶矩阵（其中p(y|x)=P(Y=y|X=x)）。X的概率分布为{x,q(x),x∈{0,1,…,K-1}}。Y的概率分布为{y,w(y),y∈{0,1,…,J-1}}。我们有以下的结论：现在是19页\一共有75页\编辑于星期日20有关DMC的容量定理（1）转移概率矩阵的每一行都是一个概率向量。现在是20页\一共有75页\编辑于星期日21有关DMC的容量定理（2）对任意y∈{0,1,…,J-1}，由全概率公式有。现在是21页\一共有75页\编辑于星期日22有关DMC的容量定理（3）I(X;Y)是概率向量{q(x),x∈{0,1,…,K-1}}和转移概率矩阵[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]的函数现在是22页\一共有75页\编辑于星期日23平均互信息量的凸性互信息是输入分布函数（输入概率密度）和条件概率分布（条件概率密度）的函数。现在是23页\一共有75页\编辑于星期日24平均互信息量的凸性Th.平均互信息量I(X;Y)是输入信源概率分布pX(x)的上凸函数。物理含义.当信道给定时，即条件概率p(y/x)给定下，I(X;Y)为输入概率分布的凸函数就保证了使传送信息量I(X;Y)为最大的最佳输入分布的存在。（信道容量的讨论）现在是24页\一共有75页\编辑于星期日25有关DMC的容量定理（4）设转移概率矩阵[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]确定，希望选择概率向量{q(x),x∈{0,1,…,K-1}}使I(X;Y)达到最大。定义离散无记忆信道的信道容量定义为如下的C。达到信道容量的输入概率分布{x,q(x),x∈{0,1,…,K-1}}称为最佳输入分布。其中现在是25页\一共有75页\编辑于星期日26定理5.2.1定理令Q(x)是DMC的N长输入字母序列的联合分布，XN和YN分别表示长为N的输入输出序列集合，Xn,Yn表示第n个输入和输出，有定理说明对于DMC，N长序列的信息传输问题可以归结为单符号的信息传输问题现在是26页\一共有75页\编辑于星期日27定理5.2.2Q={Q0,Q1,…,QK-1}达到信道容量的充要条件

给定输入分布，若某个输入k与所有输出的平均互信息量最大，就可以加大Qk来增加I(X;Y).不断调整输入可以使I(k;Y)任意接近。现在是27页\一共有75页\编辑于星期日28定理5.2.2解释给定一个DMC信道的响应特性，也就是说给定一个信道的转移概率矩阵[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]，达到信道容量时所对应的最佳输入分布是满足定理5.2.2条件的概率向量{q(x),x∈{0,1,…,K-1}}。其信道容量是每个使得q(k)>0的k所对应的半平均互信息量I(X=k;Y)。现在是28页\一共有75页\编辑于星期日29特殊信道的信道容量①具有一一对应关系的无噪信道②具有扩展性能的无损信道③具有归并性能的无噪信道④准对称信道⑤对称信道现在是29页\一共有75页\编辑于星期日30①具有一一对应关系的无噪信道现在是30页\一共有75页\编辑于星期日31X和Y有确定的对应关系：已知X后Y没有不确定性，噪声熵H(Y/X)=0；收到Y后，X也不存在不确定性，损失熵H(X/Y)=0;故有I(X;Y)=H(X)=H(Y)。接收到符号Y后，平均获得的信息量就是信源发出每个符号所含有的平均信息量，信道中无信息损失，而且噪声熵也等于零，输出端Y的不确定性没有增加。严格地讲，这种输入输出有确定的一一对应关系的信道，应称为无噪无损信道。当信源呈等概率分布时，具有一一对应确定关系的无噪信道达到信道容量现在是31页\一共有75页\编辑于星期日32②具有扩展性能的无损信道n<m，输入X的符号集个数小于输出Y的符号集个数。现在是32页\一共有75页\编辑于星期日33每列中只有一个非零元素：已知Y后，X不再有任何不确定度，损失熵H(X/Y)=0，I(X;Y)=H(X)-H(X/Y)=H(X)。接收到符号Y后，对发送的符号X是完全确定的，损失熵为零，但噪声熵H(Y/X)不为零。这类信道被称为有噪无损信道。信道容量为与一一对应信道不同的是，此时输入端符号熵小于输出端符号熵，H(X)<H(Y)。现在是33页\一共有75页\编辑于星期日34③具有归并性能的无噪信道n>m，输入X的符号集个数大于输出Y的符号集个数。现在是34页\一共有75页\编辑于星期日35每行仅有一个非零元素，但每列的非零元素个数大于1：已知某一个xi后，对应的yj完全确定，信道噪声熵H(Y/X)=0。但是收到某一个yj后，对应的xi不完全确定，信道损失熵H(X/Y)≠0。在这类信道中，接受到符号Y后不能完全消除对X的不确定性，信息有损失。但输出端Y的平均不确定性因噪声熵等于零而没有增加，所以这类信道称为无噪有损信道也称确定信道。现在是35页\一共有75页\编辑于星期日36每行仅有一个非零元素，但每列的非零元素个数大于1：信道容量为这种信道输入端符号熵大于输出端符号熵，H(X)>H(Y)。注意：在求信道容量时，调整的始终是输入端的概率分布p(xi)，尽管信道容量式子中平均互信息I(X;Y)等于输出端符号熵H(Y)，但是在求极大值时调整的仍然是输入端的概率分布p(xi)，而不能用输出端的概率分布p(yj)来代替。现在是36页\一共有75页\编辑于星期日37综合上述三种情况，若严格区分的话，凡损失熵等于零的信道称为无损信道；凡噪声熵等于零的信道称为无噪信道，而一一对应的无噪信道则为无噪无损信道。对于无损信道，其信息传输率R就是输入信源X输出每个符号携带的信息量(信源熵H(X))，因此其信道容量为

式中假设输入信源X的符号共有n个，所以等概率分布时信源熵最大。现在是37页\一共有75页\编辑于星期日38对于无噪信道，其信道容量为

式中假设输出信源Y的符号共有m个，等概率分布时H(Y)最大,而且一定能找到一种输入分布使得输出符号Y达到等概率分布。可见这些信道的信道容量C只决定于信道的输入符号数n，或输出符号数m，与信源无关。现在是38页\一共有75页\编辑于星期日39对称DMC容量的计算定义

设DMC的转移概率矩阵为若P的任一行是第一行的置换，则称信道关于输入为对称的。若P的任一列是第一列的置换，则称信道关于输出为对称的。现在是39页\一共有75页\编辑于星期日40对称DMC容量的计算若P所有行矢量都是第一行的置换，称为关于输入对称。由于{p(y|x)，y=0~J-1}与{p(y|k)，y=0~J-1}互为置换现在是40页\一共有75页\编辑于星期日41对称DMC容量的计算P的所有列都是第一列的一种置换，关于输出是对称的当输入事件等概，Qk=1/K此时{p(y|x)，x=0~K-1}与{p(0|x)，x=0~K-1}互为置换。现在是41页\一共有75页\编辑于星期日42对称DMC的容量计算输出集Y可划为若干个子集,每个子集对应的信道转移概率矩阵P中列所组成的子阵具有下列性质每一行都是第一行的置换每一列都是第一列的置换该信道称为准对称信道准对称信道关于输入对称。Y的划分只有一个时，关于输入输出均对称称为对称信道现在是42页\一共有75页\编辑于星期日43对称DMC的容量计算几个简单的结论：（1）准对称信道一定是关于输入为对称的。（2）对称信道关于输入和输出都对称。（3）对称DMC当输入分布等概时，输出分布等概。（4）准对称DMC当输入分布等概时，输出分布局部等概。（准对称DMC当输入分布等概时，若j和l属于转移概率矩阵的同一个列子集，则wj=wl。）（5）对称信道未必有J=K。现在是43页\一共有75页\编辑于星期日44对称DMC的容量计算准对称信道对称信道现在是44页\一共有75页\编辑于星期日45准对称DMC容量的计算定理

实现准对称DMC信道容量的最佳输入分布为等概分布YS：子阵中每一列都是第一列置换对每个j相同对每个k相同值与k无关现在是45页\一共有75页\编辑于星期日46对称DMC容量的计算结论

实现对称DMC信道容量的输入分布为等概分布关于输入对称的现在是46页\一共有75页\编辑于星期日47K元对称信道容量计算例：K元对称信道容量计算K=2,C=1-H(p)现在是47页\一共有75页\编辑于星期日48准对称信道容量计算例：二元对称删除信道（准对称信道）C=1-q（二元纯删除信道）现在是48页\一共有75页\编辑于星期日49一般DMC的容量计算一般DMC的信道容量与最佳输入分布的计算

若DMC的转移概率矩阵P是可逆方阵（此时K=J，非奇异）。则可以先假设最佳输入分布{q(x),x∈{0,1,…,K-1}}中每个概率q(x)都满足q(x)>0。在这个假设下，求出信道容量C；然后求出最佳输入分布对应的“最佳输出分布”{w(y),y∈{0,1,…,K-1}}；然后求出最佳输入分布{q(x),x∈{0,1,…,K-1}}。现在是49页\一共有75页\编辑于星期日50一般DMC的容量计算此时，现在是50页\一共有75页\编辑于星期日51一般DMC的容量计算这是K个未知量{β0,β1,…,βK-1}={C+logw(0),C+logw(1),…,C+logw(K-1)}的线性方程组，系数矩阵是可逆方阵，因此唯一解出{β0,β1,…,βK-1}现在是51页\一共有75页\编辑于星期日52一般DMC的容量计算另一个等式：

w(0)+w(1)+…+w(K-1)=1。于是βi=C+logw(i)现在是52页\一共有75页\编辑于星期日53一般离散信道容量计算步骤现在是53页\一共有75页\编辑于星期日54一般DMC的容量计算例子例设DMC的输入事件为{0,1}，输出事件为{0,1}，转移概率矩阵为求信道容量和最佳输入分布。先假设最佳输入分布{q(0),q(1)}满足q(0)>0，q(1)>0。因此现在是54页\一共有75页\编辑于星期日55一般DMC的容量计算例子因此现在是55页\一共有75页\编辑于星期日56第5章离散信道及信道编码定理5.1信道分类5.2离散无记忆信道5.3信道编码和译码5.4信道编码定理5.5信道编码定理的应用现在是56页\一共有75页\编辑于星期日57信道编码最简单的检错和纠错单个的字无法检错：扪→？词汇能够检错：我扪的→我扪的词汇能够纠错：我扪的→我们的，我等的，我辈的，我班的，…原因分析：“扪→？”可以有几百个答案，但“我扪的→？”的答案却很少。结论：课文以及词汇的概率分布的稀疏性可以用来检错和纠错。现在是57页\一共有75页\编辑于星期日58信道编码K信息比特N编码比特编码器(n0,k0)卷积码(Convolutionalcodes)：m个分组相关，约束长度为K=(m+1)k0编码速率(N,K)分组码(Blockcodes)：分组之间独立编码速率卷积编码示意现在是58页\一共有75页\编辑于星期日59译码准则信息序列个数：可能的N长二元序列个数：编码：K长信息序列到N长二元序列空间的映射K长二元序列空间N长二元序列空间现在是59页\一共有75页\编辑于星期日60译码准则接收矢量：码字：信道译码编码现在是60页\一共有75页\编辑于星期日61译码准则译码错误概率（误组率）对特定接收序列y的译码错误概率误比特率Biterrorrate第k位出错的概率现在是61页\一共有75页\编辑于星期日62译码准则最小错误概率准则使最小最大后验概率准则最大后验概率准则计算后验概率是困难的，通常针对具体信道（转移概率已知），采用最大似然准则现在是62页\一共有75页\编辑于星期日63离散序列译码根据贝叶斯公式若要求等价于现在是63页\一共有75页\编辑于星期日64离散序列译码若消息序列先验概率相等得最大似然准则最大后验准则现在是64页\一共有75页\编辑于星期日65离散序列译码译码是由YN到UL的映射，将YN划分为M个不相交子集x1x2xMYNY1Y2YM是Ym的补集若消息m的先验概率为Q(m),则平均译码错误概率为现在是65页\一共有75页\编辑于星期日66离散序列译码最大后验概率译码最大似然译码所有消息等概q元对称信道最小汉明距离译码汉明距离：两个码字U、V之间对应码元位上符号取值不同的个数，称为码字U、V之间的汉明距离。例如：两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U和V的距离为4。现在是66页\一共有75页\编辑于星期日67离散序列译码对两种译码准则的评述最大后验概率准则具有很好的直观合理性。收到y的条件下，最可能发送的是哪个码字，就认为发送的是哪个码字”。最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到y，就认为发送的是哪个码字。现在是67页\一共有75页\编辑于星期日68离散序列译码对两种译码准则的评述最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：

前者只需要看哪个码字与y的Hamming距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。现在是68页\一共有75页\编辑于星期日69离散序列译码例

两个消息等概，x1=0000，x2=1111，通过二元对称信道，转移概率p译码规则如下：当(Y1Y2Y3Y4)中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。译码规则显然是最小距离准则。现在是69页\一共有