版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2022-7-81 第五章第五章 纠错编码原理纠错编码原理有噪声信道编码的主要目的是有噪声信道编码的主要目的是提高传输可靠性提高传输可靠性,增,增加抗干扰能力,因此也称为加抗干扰能力,因此也称为纠错编码纠错编码或或抗干扰编码抗干扰编码。信源编码之后的码字序列抗干扰能力很脆弱,在信信源编码之后的码字序列抗干扰能力很脆弱,在信道噪声的影响下容易产生差错,为了提高通信系统道噪声的影响下容易产生差错,为了提高通信系统的有效性和可靠性,要在信源编码器和信道之间加的有效性和可靠性,要在信源编码器和信道之间加上一个信道编码器。上一个信道编码器。SOURCESOURCECODINGCHANNELCODINGT
2、xCHANNELRxCHANNELDE-CODSOURCEDE-CODSINK2022-7-82 信源编码信源编码-Source Coding Compresses the data to remove redundancy 信道编码信道编码-Channel Coding Adds redundancy to protect against channel errors2022-7-83一个通信系统总是要以一定的速率、可靠地、保证质量的将一个通信系统总是要以一定的速率、可靠地、保证质量的将信息从一端传送到另一端。信息从一端传送到另一端。Example: Rate = 1MbpsError ra
3、te = 10-5;Error-control codingTwo key systems parameters aretransmitted signal power and channel bandwidth.In general, Signal power error rate Bandwidth error rate Both signal power and bandwidth cannot be increased infinitely.2022-7-845.1 译码准则译码准则5.1.1 译码准则的含义译码准则的含义一个例子一个例子影响通信系统可靠性的一个重要问题是译码影响通信系
4、统可靠性的一个重要问题是译码方式,可以通过一个例子看一下;方式,可以通过一个例子看一下;有一个有一个BSC信道,如图所示。信道,如图所示。2022-7-85对于这样一个信道,如果采用对于这样一个信道,如果采用自然的译码准则自然的译码准则,即收,即收0判判0,收,收1判判1;这时可以明显看到,当信源先验概率;这时可以明显看到,当信源先验概率的等概时的等概时p(0)=p(1)=1/2;这时收到;这时收到Y判判X的后验概率等的后验概率等于信道转移概率,系统正确的译码概率为于信道转移概率,系统正确的译码概率为1/4,错误译,错误译码概率为码概率为3/4。但如果采用。但如果采用另一种译码准则另一种译码准
5、则,收,收0判判1,收收1判判0;则系统正确的译码概率为;则系统正确的译码概率为3/4,错误译码概率,错误译码概率为为1/4,通信的可靠性提高了。,通信的可靠性提高了。2022-7-86译码准则译码准则设一个有噪声离散信道,输入符号集设一个有噪声离散信道,输入符号集X X,输出符号集,输出符号集Y Y,信道转移概率为信道转移概率为P(Y/X);P(Y/X);X:x1,x2,.,xn。 Y:y1,y2,ymP(Y/X):p(yj/xi); i=1,2,n; j=1,2,m这时定义一个收到这时定义一个收到yj后判定为后判定为xi的单值函数,的单值函数,即: F(yj)=xi (i=1,2,n; j
6、=1,2,m);这个函数称为译码函数译码函数。它构成一个译码函数组,这些函数的值组成了译码准则译码准则。2022-7-87对于有对于有n个输入,个输入,m个输出的信道来说,可以有个输出的信道来说,可以有nm个个不同的译码准则。不同的译码准则。例如上面例子中有例如上面例子中有4种译码准则分别为:种译码准则分别为:A:F(0)=0;F(1)=0 B:F(0)=0;F(1)=1C:F(0)=1;F(1)=0 D:F(0)=1;F(1)=12022-7-885.1.2 译码错误概率译码错误概率当译码准则确定之后,接收端收到一个yj后,则按译码准则译成F(yj)=xi,这时如果发送的为xi则为正确译码,
7、如果发送的不是xi则为错误译码。所以接收到yj后正确译码的概率就是接收端收到yj后,推测发送端发出xi的后验概率:Prj=PF(yj)=xi/yj而错误译码的概率为收到yj后,推测发出除了xi之外其它符号的概率:Pej=Pe/yj=1-PF(yj)=xi/yj其中e表示除了xi之外的所有其它信源符号的集合。2022-7-89然后对所有的yj取平均,则平均正确译码概率为:PP yPp yp F yxyrjrjjmjjijjm()() ()/11同样可以得到平均错误译码概率为:Pp yP eyp yP F yxyejjjjijjmjm() /()()/111这就是平均错误译码概率的基本表达式,在通
8、信系统设计和分析时,总是希望得到最可能小的平均错误译码概率。因此所有通信系统都将平均译码错误概率作为系统可靠性的一个重要指标。2022-7-8105.1.3 最大后验概率准则最大后验概率准则由平均错误译码概率的表达式可以看出,错误译码概率与信道输出端随机变量Y的概率分布p(yj)有关,也与译码准则有关。当信道转移概率p(yj/xi)确定,而且信源统计特性p(xi)确定之后,信道输出端的p(yj)也就确定了。因为:p(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, ,n)求和得到。因此,在这种情况下,平均错误译码概率只与因此,在这种情况下,平均错误
9、译码概率只与译码准则译码准则有关了。通过选择译码准则可以使平有关了。通过选择译码准则可以使平均译码概率达到最小值。均译码概率达到最小值。2022-7-811当式中的每一项的当式中的每一项的PF(yj)=xi/yj达到最大值时,平均达到最大值时,平均错误译码概率就可以为最小值。错误译码概率就可以为最小值。设信源设信源X的信源空间为:的信源空间为:Pp yP eyp yP F yxyejjjjijjmjm() /()()/111)(.)()(: )(: ,2211nnxpxxpxxpxXPXPX)/(.)/()/(.)/(.)/()/()/(.)/()/(212221212111nmmmnnxyp
10、xypxypxypxypxypxypxypxypP 信道的转移矩阵为:信道的转移矩阵为:2022-7-812收到每一个yj(j=1,2,m)后,推测发送为xi(i=1,2,n)的后验概率共有n个,为:p(x1/yj),p(x2/yj),p(xn/yj)。这其中必有一个为最大的,设其为:p(x*/yj),即有:p(x*/yj)p(xi/yj) (对一切的对一切的i)这表明:收到符号yj后就译为输入符号x*,即译码函数选为:F(yj)=x* (j=1,2,m)这种译码准则称为这种译码准则称为最大后验概率准则最大后验概率准则。2022-7-813利用这种准则就可以使平均译码错误概率公式中的求利用这种
11、准则就可以使平均译码错误概率公式中的求和的每一项和的每一项 达到最小值达到最小值1-F(yj)=x*/yj。这时的平均错误译码概率的最小值为:这时的平均错误译码概率的最小值为:mjjjeyxpypP1min)/*(1)( nimjmjjjiyxpyxp111)*,(),(mjmjjjjyxpypyp11)/*()()( mjimjixiyjpxipyjxip11)/()(),(从表达式中可以看到,这个最小值与信源先验概率和信道转移概率有关,特别从表达式中可以看到,这个最小值与信源先验概率和信道转移概率有关,特别是信道转移概率,如果除了是信道转移概率,如果除了p(yj/x*)外,其它的项都外,其
12、它的项都很小很小,错误译码概率就小。,错误译码概率就小。2022-7-8145.1.4 最大似然准则最大似然准则最大后验概率译码准则需要已知后验概率,但信道的统计特性描述一般是信道转移概率,因此希望 利用信道转移概率的译码准则。 由概率中的贝叶斯定理可有:p xyp xp yxp yjjj(/)() (/)()*这样,如果能够保证对所有的i p(x*)p(yj/x*)p(xi)p(yj/xi) (i=1,2,n)就等于:p(x*/yj)p(xi/yj) (最大后验)(最大后验)则选择译码准则:F(yj)=x* (j=1,2,n)2022-7-815这样,可以看到当信道输入符号集这样,可以看到当
13、信道输入符号集X的先验概率为等的先验概率为等概时概时p(xi)=1/n,最大后验概率可以用最大信道转移,最大后验概率可以用最大信道转移概率来取代。概率来取代。这时,如果这时,如果p(yj/x*)是是yj相应的相应的n个信道转移概率个信道转移概率 p(yj/x1),p(yj/x2),p(yj/xn)中的最大者,则我们就将中的最大者,则我们就将yj译成译成x*,这种译码方法称,这种译码方法称为为“最大似然译码准则最大似然译码准则”。最大似然译码准则利用了最大似然译码准则利用了信道转移概率信道转移概率,而不用后,而不用后验概率,将更方便。验概率,将更方便。p xyp xp yxp yjjj(/)()
14、 (/)()*2022-7-816这时的最小平均错误译码概率为:这时的最小平均错误译码概率为:mjiijmjiijiexypnxypxpP11)/(1)/()( 将信道转移矩阵将信道转移矩阵P P中每一列中的最大元素去掉,中每一列中的最大元素去掉,然后将其它元素相加后除以然后将其它元素相加后除以nn。为了减小错误译码概率,主要方法是改变信道为了减小错误译码概率,主要方法是改变信道转移概率。转移概率。2022-7-817说明说明:q最大后验概率准则也叫做最小错误译码最大后验概率准则也叫做最小错误译码概率准则,是一种最佳准则。概率准则,是一种最佳准则。q当信道的输入符号先验概率为等概时,当信道的输
15、入符号先验概率为等概时,最大似然准则就等于最大后验概率准则。最大似然准则就等于最大后验概率准则。q当信道的输入符号先验概率不等概时,当信道的输入符号先验概率不等概时,最大似然准则就不是最佳准则了。但是最大似然准则就不是最佳准则了。但是由于使用方便通常还是应用的。由于使用方便通常还是应用的。2022-7-818举例:举例:X:x1,x2,x3 Y:y1,y2,y3信道转移矩阵为信道转移矩阵为:4 . 05 . 02 . 03 . 03 . 03 . 03 . 02 . 05 . 0P2022-7-819如果使用最大似然准则如果使用最大似然准则;译码函数为译码函数为:F(y1)=x1F(y2)=x
16、3F(y3)=x2为信道矩阵各列中的最大项为信道矩阵各列中的最大项.计算可知计算可知;当先验等概时平均错误译码概率为当先验等概时平均错误译码概率为:4 . 05 . 02 . 03 . 03 . 03 . 03 . 02 . 05 . 0P567. 0)4 . 02 . 0()3 . 03 . 0()3 . 02 . 0(31eP2022-7-820如果先验不等概时平均错误译码概率为如果先验不等概时平均错误译码概率为:1/4,1/4,1/26 . 0)4 . 02 . 0(21)3 . 03 . 0(41)3 . 02 . 0(41eP2022-7-821Fano不等式不等式可以看到:错误译码
17、概率与译码准则有关,可以看到:错误译码概率与译码准则有关,但是主要是由于信道噪声引起的。也就是由但是主要是由于信道噪声引起的。也就是由信道的疑义度信道的疑义度H(X/Y)的存在引起的。的存在引起的。因此因此Pe与与H(X/Y)一定存在某种关系。一定存在某种关系。称为称为Fano不等式。不等式。) 1log()()/(nPPHYXHee2022-7-822H(Pe)是是Pe的熵。的熵。1. 这个不等式指出疑义度分为两个部分。这个不等式指出疑义度分为两个部分。第一部份是产生错误还是不产生错误的不第一部份是产生错误还是不产生错误的不确定性;第二部分是产生错误后是哪个输确定性;第二部分是产生错误后是哪
18、个输入造成的不确定性。入造成的不确定性。2. 虽然虽然Pe与译码准则有关,但无论什么准则与译码准则有关,但无论什么准则该不等式都成立。该不等式都成立。3. 当信源和信道确定后,信道疑义度给定了当信源和信道确定后,信道疑义度给定了译码错误概率的下限。译码错误概率的下限。) 1log()()/(nPPHYXHee2022-7-823H(X/Y)Pe1(n-1)/nlognlog(n-1)H(Pe)+Pelog(n-1)2022-7-8245.2 信道编码基本概念信道编码基本概念5.2.1 信道编码定理信道编码定理定理定理:有噪声信道编码定理:有噪声信道编码定理(Shannon第二编码定理)第二编码
19、定理)如一个离散有噪声信道有如一个离散有噪声信道有n个输入符号,个输入符号,m个输个输出符号,信道容量为出符号,信道容量为C。当信道的熵速率。当信道的熵速率RC时,只要码长足够长,总可以找到一种时,只要码长足够长,总可以找到一种编码方编码方法法及及译码准则译码准则,使信道输出端的平均错误译码,使信道输出端的平均错误译码概率达到任意小,概率达到任意小,pe=。当。当RC时,则不可时,则不可能找到一种编码方法及译码准则,使信道输出能找到一种编码方法及译码准则,使信道输出端的平均错误译码概率达到任意小。端的平均错误译码概率达到任意小。2022-7-8255.2.2 信道编码的基本概念(分组码)信道编
20、码的基本概念(分组码)码字空间码字空间如果原始信源空间有M个码字,对其进行q元等长码的信道编码,码长为N,信道码字空间的所有码字为qN个,编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个码字,信道编码码字空间的这M个码字称为“许用码字”,而另外的qN-M个码字称为“禁用码字”。为了实现纠错编码,一定有qNM。这M个许用码字也称为一个码组,或称为码字集合。2022-7-826汉明距离:汉明距离:(Hamming distance)在一个码组(码字集合)中,任意两个等长码字之间,如果有d个相对应的码元不同,则称d为这两个码字的汉明距离。例如:和为码组X中的两个不同码字,X为一个长度
21、为N的二元码组,其中:=a1,a2,aN ai0,1=b1,b2,bN bi0,1则与的汉明距离为:dabdNiiiN( ,) 10d=0表明为全同码,d=N表明为全异码,如果用模2加法的概念,有dabiiiN( ,) 12022-7-827最小码距:最小码距:在一个码字集合中,任何两个码字之间的汉明距在一个码字集合中,任何两个码字之间的汉明距离组成一个元素集合,离组成一个元素集合,D(,),这个集合中的最,这个集合中的最小值称为这个码字集合的最小汉明距离,简称最小值称为这个码字集合的最小汉明距离,简称最小码距,记为:小码距,记为:dmin。 dmin=mind(,) ,X 码字重量(汉明重量
22、)码字重量(汉明重量)(Hamming weight)在二元编码的码字集合中,码字中在二元编码的码字集合中,码字中“1”码元的个码元的个数称为这个码字的重量。记为:数称为这个码字的重量。记为:W()。利用码字重量的概念,汉明距离可以表示。利用码字重量的概念,汉明距离可以表示为:为: d(,)=W( )2022-7-828举例举例码A码B码C码D许用码字000111000011101110000001100010000001111码字个数2448最小距离3211传输效率1/32/32/31Pe310-4210-22.310-2310-22022-7-829分组码最小码距与纠检错能力的关系:分组码最小码距与纠检错能力的关系:一个分组码的最小码距为一个分组码的最小码距为dmin,则其纠检错能力为:,则其纠检错能力为:若发现若发现e个错误,则要求个错误,则要求dmine+1;若纠正若纠正t个错误,则要求个错误,则要求dmin2t+1;若纠正若纠正t个错误,同时发现个错误,同时发现e个错误,则要求个错误,则要求dmint+e+1; tC2R2022-7-840降低译码错误概率的途径:降低译码错误概率的途径:(1)增加信道容量,从而使增加信道容量,从而使E(R)增加增加。根据上农公。根据上农公式可知,增加信道容量可以增加带宽或者提高信噪式可知,增加信道容量可以增加带宽或
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025电视机买卖合同范本
- 二零二五年度新材料研发借款协议3篇
- 二零二五年度电子商务散伙协议书3篇
- 二零二五年度公司对公租赁房屋物业管理合同2篇
- 2025年度年度文化旅游股份收购投资合同3篇
- 二零二五年度股东间战略联盟合作协议书3篇
- 2025年度农村合作社农村电商直播培训合同
- 2025年农村环境卫生保洁与农村环境保护法律法规执行合同
- 2025年度全新工业机器人价格保密协议3篇
- 2025年度军人保密协议与军事设施维护保密合同3篇
- GB/T 44890-2024行政许可工作规范
- 军工合作合同范例
- 2025年中国稀土集团总部部分岗位社会公开招聘管理单位笔试遴选500模拟题附带答案详解
- 超市柜台长期出租合同范例
- 广东省广州市2025届高三上学期12月调研测试语文试题(含答案)
- 【8物(科)期末】合肥市第四十五中学2023-2024学年八年级上学期期末物理试题
- 统编版2024-2025学年三年级语文上册期末学业质量监测试卷(含答案)
- 从0 开始运营抖⾳音号sop 文档
- Module7 Unit2 This little girl can't walk(Period 1) (教学实录) -2024-2025学年外研版(三起)英语五年级上册
- 施工临建布置方案
- 2024年01月11190当代中国政治制度期末试题答案
评论
0/150
提交评论