《有扰离散信道的编码定理课件.pptx》由会员分享，可在线阅读，更多相关《有扰离散信道的编码定理课件.pptx（43页珍藏版）》请在三一办公上搜索。
1、2019-6-26,1,编码调制的设计有两条基本途径 是什么? 一条是代数途径，即运用编, 解码技术来设计特定种类的码，比如分组码、卷积码等。 第二条途径是采用概率方法，在给定信道特性的条件下对编码信号的性能作统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率的上界，称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。,5.2 有扰离散信道的编码定理,谢谢观赏,2019-6-26,2,码空间,消息k长 (n , k) 码字n长,qk 种 分组编码器 qn种 k维k重矢量
2、 n维n重矢量,通常qn qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。,谢谢观赏,2019-6-26,3,分组编码的任务,选择一个维n重子空间作为码空间。确定由k维k重信息空间到维n重码空间的映射方法。 码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。,谢谢观赏,2019-6-26,4,5.2.1随机编码,(N,K)分组编码器,DMC信道,图5-2-1 分组编码与随机编码,谢谢观赏,2019-6-26,5,在(N,K)分组编码器中随机选定的码集有qNM种码集点数M=qK占N维矢量空间总点数qN的
3、比例是F =qK / qN = q-(N-K) 当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率 将变小。 当F0 即(N-K)时，能否让平均差错概率 ？,谢谢观赏,2019-6-26,6,在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm )被随机选中的概率是设与这种选择相对应的条件差错概率是Pe(cm)全部码集的平均差错概率是,谢谢观赏,2019-6-26,7,必定存在某些码集某些码集若 ，就必然存在一批码集 即差错概率趋于零的好码一定存在,谢谢观赏,2019-6-26,8,Gallager在1965年推导了
4、的上边界，并证明这个上边界是按指数规律收敛的。,谢谢观赏,2019-6-26,9,码率：R =( lnM) / N M是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit / symbol）,5.2.2信道编码定理,谢谢观赏,2019-6-26,10,E(R)为可靠性函数，也叫误差指数E(R)定义为,谢谢观赏,2019-6-26,11,0,1,图5-2-2,0,1,C,R,R0,谢谢观赏,2019-6-26,12,谢谢观赏,2019-6-26,13,R在0,R0区间时E(R)R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)
5、=0即可靠性为零。,谢谢观赏,2019-6-26,14,正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。,信道编码定理,谢谢观赏,2019-6-26,15,5.3差错控制与信道编译码的基本原理,差错和差错系统分类差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底
6、对应多少比特差错却难以确定。因为一个符号由多个比特组成。,谢谢观赏,2019-6-26,16,差错图样（error pattern）,定量地描述信号的差错，收、发码之“差” ：差错图样E发码C 收码R （模M） 例：8进制(M=8)码元，若发码 C=（0,2,5,4,7,5,2）收码变为 R=（0,1,5,4,7,5,4）差错图样E=CR=（0,1,0,0,0,0,6）（模8）二进制码：E=C R 或 C = R E ，差错图样中的“”既是符号差错也是比特差错，差错的个数叫汉明距离。,谢谢观赏,2019-6-26,17,差错图样类型,随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无
7、关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。,谢谢观赏,2019-6-26,18,纠错码分类,从功能角度：检错码 、纠错码 对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等,谢谢观赏,2019-6-26,19,差错控制系统分类,前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中
8、的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力,谢谢观赏,2019-6-26,20,5.3.1差错控制的途径,1、途径一从信道编码定理的公式出发，可知减小差错概率应增大码长N或增大可靠性函数E(R)。增大E(R）就要增大信道容量或减小码率R。R不变，信道容量大者其可靠性函数E(R)也大；C不变，码率减小时其可靠性函数E(R)增大,谢谢观赏,2019-6-26,21,（1）增大信道容量C 扩展带宽比如开发新的宽带媒体，有线通信从明线（150kHz
9、）、对称电缆（600kHz）、同轴电缆（1GHz）到光纤（25THz），无线由中波、短波、超短波到毫米波、微米波。又比如采取信道均衡措施，如加感时/频域的自适应均衡器。加大功率如提高发送功率、提高天线增益、将无方向性的漫射改为方向性强的波束或点波束、分集接收等。降低噪声如采用低噪声器件、滤波、屏蔽、接地、低温运行等。在纠错编码技术发展之前，通信系统设计者传统上主要就是靠增大C来提高通信可靠性。,谢谢观赏,2019-6-26,22,（2）减小码率R 对于二进制（N，K）分组码，码率R=K/N比特/符号；对于q进制（N，K）分组码，码率 比特/符号.q、N不变而减小K 即降低信息源速率，每秒少传一
10、些信息。q、K不变而增大N即提高符号速率，占用更大带宽。N、K不变而减小q即减小信道的输入输出符号集，在发送功率固定时提高信号间的区分度，从而提高可靠性。在一定通信容量下减小R,等效于拉大C和R之差，因此说这是用增加信道容量的冗余度来换取可靠性。从50年代到70年代，主要的纠错编码方法都是以这种冗余度为基础的。,谢谢观赏,2019-6-26,23,（3）增大码长N 如果要保持码率R不变，增加码长N的同时应增大信息位K，以保持K/N之比不变。在C和R固定的情况下加大N并没有增加信道容量的冗余度，它是利用了随机编码的特点：随着N增大，矢量空间 以指数级增加，从统计角度而言码字间距离也将加大，从而可
11、靠性提高。另外码长N越大，其实际差错概率就越能符合统计规律。增加码长N所带来的好处，付出的代价是码长越长，编码算法就越复杂，编码解码器也就越昂贵。当前，通过增加码长N来提高可靠性已成为纠错编码技术的主要途径之一，它实际上是以设备的复杂性换取可靠性，从这个意义上讲，妨碍数字通信系统系能提高的真正限制因素是设备的复杂性。,谢谢观赏,2019-6-26,24,2、从概念上分析纠错编码原理从概念上分析纠错编码原理，可以把纠错能力的获取归为两条，一条是利用冗余度，另一条是噪声均化（随机化）。（1）利用冗余度根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规
12、则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。 纠错码为了传输这些冗余比特，必须要动用冗余的资源。这些资源可以是：时间比如一个比特重发几次，或一段消息重发几遍，或者根据收端的反馈重发受损信息组，如ARQ系统。,谢谢观赏,2019-6-26,25,频带插入冗余比特后传输效率下降，若要保持有用信息的速率不变，最直接的方法就是增大符号传递速率，结果就占用了更大的带宽。比如采用二进制码（1比特/符号）,编成（8，4）分组码后使符号速率增大一倍，所占带宽也增大一倍。功率采用多进制符号，
13、比如用一个八进制ASK符号代替一个四进制ASK符号来传输2比特信息，可腾出位置另传1比特冗余。但为了维持信号集各点之间的距离不变，八进制ASK符号的平均功率可定比四进制时要大，这就是动用冗余的资源来传输冗余比特。设备复杂度加大码长N，采用网格编码调制(TCM)，是在功率、带宽受限信道中实施纠错编码的有效方法，代价是算法复杂度的提高，需动用设备资源。,谢谢观赏,2019-6-26,26,（2）噪声均化噪声均化的基本思想是设法将危害较大的、较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。这是因为噪声干扰的危害不仅与噪声总量有关，而且与它们的分布有关。集中的噪声干扰（称之为突发差错）的危害甚于
14、分散的噪声干扰（称之为随机差错）。噪声均化正是将差错均匀分摊给各码字，达到提高总体差错控制能力的目的。噪声均化的方法有三种：增加码长N增加码长可使译码差错小的原因在于：码长越大，具体每个码字中误码元的比例就越接近统计平均值，换言之，噪声按平均数被均摊到各码字上。而如果真的均摊了，译码就不会发生任何差错，因为信道的差错概率（Pe=1%）远远小于编码后的纠错能力10%。,谢谢观赏,2019-6-26,27,如图5-1-2所示的某BSC信道误码概率Pe=0.01,假如编码后的纠错能力是10%，即长度N的码字中，只要差错码元个数少于等于N的10%，就可以通过译码加以纠正。若码长N=10,则码字中多余一
15、个码元出错时就会产生译码差错，差错概率为如果保持码率R不变，将码长增加N=40,那么当码字中多余4个码元出错时就会产生译码差错，差错的概率为,谢谢观赏,2019-6-26,28,卷积上面的例子是把信息流分割成K位一组，每组在编成N长的码字，也就是相关性仅限于加在各个码字内，而各个码字之间是彼此无关的。卷积码在一定约束长度内的若干码字之间也加进了相关性，译码时不是根据单个码字而是一串码字来做判决。如果再加上适当的编译码方法，就能够使噪声分摊到码字序列而不是一个码字上，达到噪声均化的目的。交错（或称交织）是对付突发差错的有效措施。突发噪声使码流产生集中的、不可纠的差错，若能采取某种措施，对编码器输
16、出的码流与信道上的符号流做顺序上的变换，则信道噪声造成的符号流中的突发差错，有可能被均化而转化为码流上随机的、可纠正的差错。加了交错器的传输系统如图5-3-2所示。,谢谢观赏,2019-6-26,29,编码器,交错器,去交错,信道,交错的效果取决于信道噪声的特点和交织方式。最简单的交错器是nm的存储阵列，码流按行输入后按列输出。图5-3-3是一个适用于码长N=7的57行列交错器的示意图。从图中看到，码流的顺序1，2，37，8，经交错器后变为1，8，15，22，29，2，9。先假设信道中产生5个连续的差错，如果不交错，这5个差错集中在1个或2个码字上，很可能就不可纠。如果采用交错方法，去交错后差
17、错分摊给5个码字上，每码字仅1个。,译码器,数据入,数据出,图5-3-2 带交错器的传输系统,谢谢观赏,2019-6-26,30,入,出,交错器,去交错器,出,入,信道中5个连续的突发差错,信道,图5-3-3 5 7行列交错器工作原理示意图,谢谢观赏,2019-6-26,31,5.3.2码距、纠错能力,N重码矢c = (cn-1,c n-2,c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集 ，该子集所包含的点只是全部N维空间点的一部分。发码一定在这个子集里，传输无误时的收码也一定位于该子集 当出现差错时，接收的N重矢量:对应到子集外空间某一点 （能判断
18、出有差错）对应到该子集，却对应到该子集的另一点上 （不能判断出有差错）,谢谢观赏,2019-6-26,32,子集的任意两点间存在一定的距离，设子集两点间的最小距离是 ，那么一个能使空间点位置便宜 的差错组合（称之为重量 的差错图案）有可能把接收矢量所对应的空间点位置从子集的一个点偏移到另一个点，导致从一个码字译成另一个码字。这种情况下，就是说产生了一个“不可检的差错”。另一方面，如果差错数小于 ，就不可能从子集一点偏移到子集另一个点，就可以检错出差错的存在。显然，对于（n,k）分组码而言，我们有能力检测出 -1个差错。,谢谢观赏,2019-6-26,33,码的纠错能力也同样取决于最小距离。为了
19、确定（n,k）分组码的纠错能力，一种方便的办法是个码字看作是位于n维空间的点。如果以每个码字为球心，以汉明距离t为半径做 个球体，那么使他们之中任意一对球体两两不相交（包括不相切）的t的最大取值是这里INT .表示取整。在每一个球内含有与该码字距离小于等于t的所有可能接收码字。译码时，所有落在球内的接收码字都被译为位于球心的那个码字。图5-3-4是码字和球的两维示意图。,谢谢观赏,2019-6-26,34,t,d=7,dmin=3,d=5,C1,C2,C3,C4,C5,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin分组码若单独考虑检错或单独考虑纠错，则可检dmin-
20、1 个差错或纠t=INT（ dmin-1 ）/2个差错。这里dmin=3，纠错能力是1，检错能力是2,5.3.2码距、纠错能力,谢谢观赏,2019-6-26,35,一般性的结论是若最小距离dmin的码同时能检ed 个、纠ec个差错，则必有ed + ec dmin -1及ec ed对于线性码来说，码距的特性也就是码的重量特性（码重可视为该码与全零码的距离）。如果有 个码字，就存在 个距离，这些距离是大小不一的，码的总体性能取决于这些距离的分布特性（重量谱）， 而纠错能力取决于其中的最小者dmin。正如各符号等概时熵最大一样，从概念上可以联想到：当所有码距相等时码的性能最好，或者退后一步，当各码距
21、相差不大时性能应该较好。,谢谢观赏,2019-6-26,36,对于转移概率为p的BSC信道，由于无记忆，各比特差错的发生是独立的，如果不加纠错编码，k位信息组出错的概率是如果采用纠错能力为t的（n,k）分组码，当差错个数在（t+1）到n之间时该码可能出错，因此差错概率的上限为,谢谢观赏,2019-6-26,37,5.3.3最优译码与最大似然译码,译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列r, r=(r1,r2,rN)发端所采用的编码算法和该算法产生的码集XN, 满足 信道模型及信道参数。,谢谢观赏,2019-6-26,38,最佳译码，也
22、叫最大后验概率译码(MAP)最大似然译码( MLD),5.3.3最优译码与最大似然译码,消息组mi 码字ci 接收码r 估值 消息,（N,K）编码器 信道 译码 消息还原,谢谢观赏,2019-6-26,39,如果构成码集的2K个码字以相同概率发送，满足P(ci ) = 1/2K ， i=1,2,2K P(r)对于任何r都有相同的值，满足P(r) = 1/2K 则P(ci /r)最大等效于P(r / ci)的最大，在此前提下最佳译码等效于最大似然译码。,5.3.3最优译码与最大似然译码,谢谢观赏,2019-6-26,40,5.3.3最优译码与最大似然译码,对于无记忆信道，码字的似然函数p(r/c
23、i)等于组成该码字的各码元的似然函数之积（联合概率），码字的 最大似然也就是各码元似然函数之积的最大化为了将乘法运算简化为加法运算，取似然函数的对数，称作对数似然函数。由于对数的单调性，似然函数最大时对数似然函数也最大。于是码字对数似然函数最大化等效于各码元对数似然函数之和的最大化，即,谢谢观赏,2019-6-26,41,例：BSC信道的最大似然译码可以简化为最小汉明距离译码。当逐比特地比较发码和收码时，仅存在两种可能性：相同或不同，两种情况发生的概率分别是如果r中有d个码元与ci的码元不同，我们说r与ci的汉明距离是d。显然d代表ci在BSC信道传输过程中的码元差错个数，也就是r与ci模2后的重量,谢谢观赏,2019-6-26,42,此时的似然函数是 是常数而 ，d越大则似然函数P(r/ci)越小，因此求最大似然函数maxp(r/ci)的问题转化成求最小汉明距离的问题。汉明距离译码是一种硬判决译码。只要在接收端将收码r与发码ci的各个码元逐一做比较，选择其中汉明距离最小的码字作为译码估值ci。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。,谢谢观赏,2019-6-26,43,谢谢观赏,
