离散信道及其编码定理

离散信道及其编码定理1第1页，课件共77页，创作于2023年2月通信系统的模型细分信源信源编码器纠错编码器调制器信道干扰源解调器纠错译码器信源译码器信宿等效离散信道等效离散信源等效信宿信道编码器信道译码器2第2页，课件共77页，创作于2023年2月通信系统模型信道编码：从消息到信道波形或矢量的映射

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

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

{X

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

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

给定输入分布，若某个输入k与所有输出的平均互信息量最大，就可以加大Qk来增加I(X;Y).不断调整输入可以使I(k;Y)任意接近。27第27页，课件共77页，创作于2023年2月定理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第28页，课件共77页，创作于2023年2月特殊信道的信道容量①具有一一对应关系的无噪信道②具有扩展性能的无损信道③具有归并性能的无噪信道④准对称信道⑤对称信道29第29页，课件共77页，创作于2023年2月①具有一一对应关系的无噪信道30第30页，课件共77页，创作于2023年2月X和Y有确定的对应关系：已知X后Y没有不确定性，噪声熵H(Y/X)=0；收到Y后，X也不存在不确定性，损失熵H(X/Y)=0;故有I(X;Y)=H(X)=H(Y)。接收到符号Y后，平均获得的信息量就是信源发出每个符号所含有的平均信息量，信道中无信息损失，而且噪声熵也等于零，输出端Y的不确定性没有增加。严格地讲，这种输入输出有确定的一一对应关系的信道，应称为无噪无损信道。当信源呈等概率分布时，具有一一对应确定关系的无噪信道达到信道容量31第31页，课件共77页，创作于2023年2月②具有扩展性能的无损信道n<m，输入X的符号集个数小于输出Y的符号集个数。32第32页，课件共77页，创作于2023年2月每列中只有一个非零元素：已知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第33页，课件共77页，创作于2023年2月③具有归并性能的无噪信道n>m，输入X的符号集个数大于输出Y的符号集个数。34第34页，课件共77页，创作于2023年2月每行仅有一个非零元素，但每列的非零元素个数大于1：已知某一个xi后，对应的yj完全确定，信道噪声熵H(Y/X)=0。但是收到某一个yj后，对应的xi不完全确定，信道损失熵H(X/Y)≠0。在这类信道中，接受到符号Y后不能完全消除对X的不确定性，信息有损失。但输出端Y的平均不确定性因噪声熵等于零而没有增加，所以这类信道称为无噪有损信道也称确定信道。35第35页，课件共77页，创作于2023年2月每行仅有一个非零元素，但每列的非零元素个数大于1：信道容量为这种信道输入端符号熵大于输出端符号熵，H(X)>H(Y)。注意：在求信道容量时，调整的始终是输入端的概率分布p(xi)，尽管信道容量式子中平均互信息I(X;Y)等于输出端符号熵H(Y)，但是在求极大值时调整的仍然是输入端的概率分布p(xi)，而不能用输出端的概率分布p(yj)来代替。36第36页，课件共77页，创作于2023年2月综合上述三种情况，若严格区分的话，凡损失熵等于零的信道称为无损信道；凡噪声熵等于零的信道称为无噪信道，而一一对应的无噪信道则为无噪无损信道。对于无损信道，其信息传输率R就是输入信源X输出每个符号携带的信息量(信源熵H(X))，因此其信道容量为

式中假设输入信源X的符号共有n个，所以等概率分布时信源熵最大。37第37页，课件共77页，创作于2023年2月对于无噪信道，其信道容量为

式中假设输出信源Y的符号共有m个，等概率分布时H(Y)最大,而且一定能找到一种输入分布使得输出符号Y达到等概率分布。可见这些信道的信道容量C只决定于信道的输入符号数n，或输出符号数m，与信源无关。38第38页，课件共77页，创作于2023年2月对称DMC容量的计算定义

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

实现准对称DMC信道容量的最佳输入分布为等概分布YS：子阵中每一列都是第一列置换对每个j相同对每个k相同值与k无关45第45页，课件共77页，创作于2023年2月对称DMC容量的计算结论

实现对称DMC信道容量的输入分布为等概分布关于输入对称的46第46页，课件共77页，创作于2023年2月K元对称信道容量计算例：K元对称信道容量计算K=2,C=1-H(p)47第47页，课件共77页，创作于2023年2月准对称信道容量计算例：二元对称删除信道（准对称信道）C=1-q（二元纯删除信道）48第48页，课件共77页，创作于2023年2月一般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第49页，课件共77页，创作于2023年2月一般DMC的容量计算此时，50第50页，课件共77页，创作于2023年2月一般DMC的容量计算这是K个未知量{β0,β1,…,βK-1}={C+logw(0),C+logw(1),…,C+logw(K-1)}的线性方程组，系数矩阵是可逆方阵，因此唯一解出{β0,β1,…,βK-1}51第51页，课件共77页，创作于2023年2月一般DMC的容量计算另一个等式：

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

前者只需要看哪个码字与y的Hamming距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。68第68页，课件共77页，创作于2023年2月离散序列译码例

两个消息等概，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第69页，课件共77页，创作于2023年2月离散序列译码译码规则是最小距离准则。何时检测到信道传输错误？当(Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。换句话说，(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离≥1且≤3时，检测到信道传输错误。因此，信道传输有错误但能检测出错误的概率为70第70页，课件共77页，创作于2023年2月离散序列译码何时正确译码（正确接收）？当(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离≤1时，正确译码；当(Y1Y2Y3Y4)与原发码字