纠错码-原理与方法课件.ppt

1、State Key Laboratory of Integrated Services Networks 纠错码纠错码原理与方法原理与方法有关事项有关事项目的：了解信道编码的目的：了解信道编码的作用与意义作用与意义，对信道编码，对信道编码的研究方法和成果有广泛的基本认识，学会的研究方法和成果有广泛的基本认识，学会应用应用，为进一步研究打下基础为进一步研究打下基础特点：以概念和物理意义为主，数学推导尽量放特点：以概念和物理意义为主，数学推导尽量放到课外到课外考核形式：论文考核形式：论文/计算机仿真计算机仿真+开卷考试开卷考试参考书：参考书：“纠错码纠错码原理与方法原理与方法”，王新梅，王新梅，西

2、安电西安电子科技大学出版社子科技大学出版社，高等学校教材；，高等学校教材；“差错控制编码差错控制编码（第二版）（第二版）”,Shu Lin，Daniel J.Costello,机械工业出机械工业出版社版社，电子与电气工程丛书），电子与电气工程丛书）其他有关事项其他有关事项课外阅读课外阅读，以，以turbo code，LDPC code，喷泉码，喷泉码，polar码码为引子为引子论文与编程论文与编程：五年内的国外期刊，以一两篇为主，：五年内的国外期刊，以一两篇为主，结合自己的理解，按电子学报论文形式，有创见结合自己的理解，按电子学报论文形式，有创见更好，可以与编程结合。编程内容在随后的课程更好，

3、可以与编程结合。编程内容在随后的课程中出题目。占中出题目。占50%考试考试：基本概念，：基本概念，50%联系方式：联系方式：email: 第第1章章 纠错码基本概念纠错码基本概念什么是纠错码？为什么要引入纠错码？纠错码在什么是纠错码？为什么要引入纠错码？纠错码在通信系统中起什么作用？通信系统中起什么作用？如何实现纠错码？如何实现纠错码？如何衡量纠错码的纠错能力及性能？如何衡量纠错码的纠错能力及性能？纠错码的发展概况纠错码的发展概况State Key Laboratory of Integrated Services Networks 1.1 纠错码的作用纠错码的作用数字通信系统模型数字通信系统

4、模型数字通信系统的简化模型数字通信系统的简化模型信源、信道与信道编码信源、信道与信道编码信源信源：实时性与非实时性，可变速率，多媒体：实时性与非实时性，可变速率，多媒体信道信道：离散与连续，时变与非时变，有记忆与无：离散与连续，时变与非时变，有记忆与无记忆记忆常见信道：模拟基带信道、射频信道、存储器等不同的信源和信道类型所对应的最佳编码方案是不同的信源和信道类型所对应的最佳编码方案是不同的。不同的。信道编码信道编码：从消息到信道波形或矢量的映射复接、代数编码、调制、成形滤波、扩频、上下复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于变频等等都属于广义的信道编码广义的信道编码范畴范畴信道

5、编码：从消息到信道波形或矢量的映射信道编码：从消息到信道波形或矢量的映射信源编码信道编码信道信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素信信 道道信道实际上也是从发空间信道实际上也是从发空间X到收空间到收空间Y一一个映射函数个映射函数发空间的维数发空间的维数n与收空间的维数与收空间的维数m可以不可以不等等根据收发空间中每一维所取的数域有限根据收发空间中每一维所取的数域有限或无限可分为离散信道和连续信道或无限可分为离散信道和连续信道这里借用了空间的名称，但只用到了它这里借用了空间的名称，但只用到了它的集合概念而没有用

6、到空间中的运算的集合概念而没有用到空间中的运算信道特性的描述信道特性的描述离散信道离散信道可用转移概率律描述：P(y=b|x=a),a=(a1,a2,.an)X,b=(b1,b2,.bm)Y,均为矢量（或n(m)重符号）信道特性的描述信道特性的描述连续信道连续信道可用转移概率密度函数描述：p(y=b|x=a),a=(a1,a2,.an)X,b=(b1,b2,.bm)Y,均为矢量（或n(m)重符号）根据奈奎斯特采样定理，带限的时域连续波形可以用采样序列描述。无记忆信道无记忆信道离散信道离散信道当m=n，且P(y=b|x=a)=P(y1|x1)P(y2|x2).P(yn|xn)时，各维的收符号只与

7、相应的发符号有关，称为无记忆离散信道，简写为DMC连续信道连续信道当m=n，且p(y=b|x=a)=p(y1|x1)p(y2|x2).p(yn|xn)时，各维的收符号只与相应的发符号有关（无符号间串扰），称为无记忆连续信道非时变信道非时变信道当各因子具有相同的转移概率形式时有记忆信道有记忆信道实际的连续信道通常会有符号间串扰（实际的连续信道通常会有符号间串扰（ISI），），因此是有记忆的，但在一种较常见的特殊情况因此是有记忆的，但在一种较常见的特殊情况下，即在加性平稳白高斯噪声下的线性信道下，即在加性平稳白高斯噪声下的线性信道（y=Ax+n）时，可以等效于一个无记忆信道。）时，可以等效于一个无

8、记忆信道。有记忆信道的无记忆化有记忆信道的无记忆化对对A作线性变换使正交化得：作线性变换使正交化得：A=UTU，其中，其中为为A的特征值矩阵。代入得的特征值矩阵。代入得 y=UTUx+n，令，令x=UTx，y=UTy，n=UTn，则有，则有y=x+n。于。于是对是对x和和y而言就形成了一个无记忆信道。由于而言就形成了一个无记忆信道。由于U为正交变换，不会产生信息量丢失，因此可为正交变换，不会产生信息量丢失，因此可以认为以认为X-Y信道与信道与X-Y信道是等价的。于是我信道是等价的。于是我们就可以直接利用有关无记忆信道的编码了。们就可以直接利用有关无记忆信道的编码了。信道模型信道模型离散无记忆信

9、道离散无记忆信道DMC)1|1()1|1()1|0()0|1()0|1()0|0(qpppqpppP二进制信道二进制信道二进制信道二进制信道DMC信道信道DMC信道信道二进制删除信道二进制删除信道二进制删除信道二进制删除信道二进制纯删除信道二进制纯删除信道二进制纯删除信道二进制纯删除信道错误类型错误类型随机错误随机错误随机错误信道：深空信道，卫星信随机错误信道：深空信道，卫星信道等道等突发错误突发错误突发错误信道：无线信道，电缆传突发错误信道：无线信道，电缆传输（开关脉冲噪声，串音），磁记录信道输（开关脉冲噪声，串音），磁记录信道混合错误混合错误混合信道混合信道差错控制系统分类差错控制系统分类

10、可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号State Key Laboratory of Integrated Services Networks 纠错码的基本原理纠错码的基本原理纠错码如何纠正错误？纠错码如何纠正错误？引入信道编码引入信道编码检错和纠错：对付信道引入的差错检错和纠错：对付信道引入的差错直观的译码准则：最小距离译码Shannon第二定理第二定理当信息速率R小于信道容量C时，总存在一种编码方式使差错率低于任一给定值e接近信道容量接近信道容量重复码重复码00001111若将每个比特重复若将每个比特重复n次，则构成一个码长为次，

11、则构成一个码长为n，信息位长度为，信息位长度为1的的(n,1)重复码重复码,且编码效且编码效率率(码率码率)R=1/n许用码字01010.90.90.10.1BSC信道n=2时许用码组：00，11禁用码组：01，10能够发现一个错误，但不能纠正错误n=3时许用码组：000，111禁用码组：001,010,100,011,101,110能够纠正一个错误，发现两个错误n=4时许用码组：0000，1111禁用码组：0001,0010,0100,1000,0011,0101,0110,1100,1001,1010,0111,1101,1110,1011能够纠正一个错误同时发现两个错误译码正确译码失败译

12、码错误发现三个错误译码失败：译码器根据接收到的信号无法作出明确判断译码错误：译码器根据接收到的信号作出错误判断不完备译码完备译码：根据接收信号，译码器一定能作出是哪 一组信息的判断有编码系统和无编码系统有编码系统和无编码系统调制也是一种编码调制也是一种编码广义地讲，实际系统中都有信道编码，而现实中广义地讲，实际系统中都有信道编码，而现实中常分为编码和调制两块，前者负责离散编码，后常分为编码和调制两块，前者负责离散编码，后者负责将离散符号变成波形，这样才有无编码系者负责将离散符号变成波形，这样才有无编码系统及编码增益等概念统及编码增益等概念M进制正交编码加进制正交编码加BPSK调制的性能与无编码

13、的调制的性能与无编码的M进制正交进制正交FSK是完全一致的。是完全一致的。信道编码的作用信道编码的作用信道编码的作用：信道编码的作用：在资源、可靠性和传信在资源、可靠性和传信量量之间选择一个好的工作点（有时还要考之间选择一个好的工作点（有时还要考虑延时）。虑延时）。资源资源指的提供信息传输所付出的代价指的提供信息传输所付出的代价包括频率、时间、空间、功率等等。但不包括实现复杂度一个好的编码就是要充分利用资源，传递尽可能多的信息三种情形：三种情形：给定资源和可靠性要求，通过信道编码尽量提高传输速率给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销给定资源和传输速率，通过编码提高可靠性

14、编码的实质编码的实质利用冗余降低差错概率利用冗余降低差错概率将所有可能的输入信息（消息）映射将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道个点的集合要小于（包含于）全信道空间中空间中。编码与构造编码编码与构造编码编码编码：针对当前要传的消息，根据映射规：针对当前要传的消息，根据映射规则，确定当前要发哪一个波形（矢量）则，确定当前要发哪一个波形（矢量）构造编码构造编码：寻找并建立映射规则：寻找并建立映射规则编码设计准则编码设计准则最佳译码时的差错概率最佳译码时的差错概率（最佳译码有可能做不到）（最佳译码有可能做不到

15、）自由距最大化准则自由距最大化准则一种最常用的编码一种最常用的编码构造准则构造准则纠错码如何纠正错误？纠错码如何纠正错误？在信息序列之后按照一定的规则添加一定长度在信息序列之后按照一定的规则添加一定长度的保护比特的保护比特(校验比特或监督比特校验比特或监督比特)State Key Laboratory of Integrated Services Networks 几个基本概念几个基本概念许用码组和禁用码组译码错误和译码失败完备译码和不完备译码汉明距离和重量最大似然译码最大后验概率译码错误图样码纠错能力判断编码增益错误图样错误图样Example发送序列C:(1111011000)接收序列R:(

16、0110010110)比较C和R，可写出另一个序列E：1001001110R=C+E 序列E定义为错误图样(Error Pattern)汉明距离和重量汉明距离和重量汉明距离：给定两个序列汉明距离：给定两个序列C1和和C2，它们对应位取，它们对应位取值不同的个数称为值不同的个数称为C1和和C2的汉明距离。的汉明距离。C1=10101,C2=01111,d(C1,C2)=3汉明重量：序列汉明重量：序列C中非零码元的个数中非零码元的个数 w(C1)=3,w(C2)=4最小汉明距离最小汉明距离：(n,k)分组码中，设任意两个码字分组码中，设任意两个码字之间距离的最小值为之间距离的最小值为d0，则则d0

17、定义为该分组码的定义为该分组码的最小汉明距离最小汉明距离 码纠错能力的判断码纠错能力的判断任一任一(n,k)分组码，若要在码字内：分组码，若要在码字内：1)检测检测e个随机错误，则要求码的最小汉明个随机错误，则要求码的最小汉明距离距离d0=e+1 2)纠正纠正t个随机错误，则要求个随机错误，则要求d0=2t+1 3)纠正纠正t个随机错误，同时检测个随机错误，同时检测e(e=t)个个错误，则要求错误，则要求d0=e+t+1 4)纠正纠正t个随机错误和个随机错误和个删除，则要求个删除，则要求 d0=2t+1 性能的衡量性能的衡量编码增益编码增益在一个码率为在一个码率为R的编码通信系统中，为传输每个

18、的编码通信系统中，为传输每个信息比特需要传输符号的数目为信息比特需要传输符号的数目为1/R，若每个传输，若每个传输符号的能量为符号的能量为Es，则每个信息比特对应的能量，则每个信息比特对应的能量Eb为：为：Eb=Es/R编码阈值编码阈值给定性能前提下，给定性能前提下，编码增益编码增益=未编码时需要的信噪比未编码时需要的信噪比(dB)编码时需编码时需要的信噪比要的信噪比(dB)信道编码定理信道编码定理每个信道具有确定的信道容量，对任何小每个信道具有确定的信道容量，对任何小于于C的码率的码率R，存在有速率为，存在有速率为R码长为码长为n的的分组码及分组码及(n0,k0,m)卷积码，若用最大似然卷积

19、码，若用最大似然译码，随着码长的增加其译码错误概率译码，随着码长的增加其译码错误概率p可以任意小。可以任意小。()bnERbpA e0c(1)()()ccmn E Rn E RccpAeAe信道容量信道容量在高斯白噪声信道在高斯白噪声信道时，信道容量时，信道容量20log(1)(bits/s)sPCWWN0E(R)RC1C2C1C2性能的衡量性能的衡量香农限香农限软判决条件下，软判决条件下，BPSK调制，调制，AWGN信道香农限信道香农限各种码的性能比较译码准则译码准则首先说明，译码本身是一种信息处理，肯定会引首先说明，译码本身是一种信息处理，肯定会引入一定的信息损失，但最重要的是尽量正确地恢

20、入一定的信息损失，但最重要的是尽量正确地恢复原始信息。复原始信息。最大后验概率最大后验概率最大似然最大似然序列译码序列译码几种基本的译码方法几种基本的译码方法 问题：问题：MC R 如何根据接收信号如何根据接收信号R估计发送序列估计发送序列C,进而估计信息序列进而估计信息序列M 设计译码算法的原则：使译码错误概率最小设计译码算法的原则：使译码错误概率最小 RERPREPPRCCPREPRCCMinPREMinPMinPE)1(RCCPMinRCCMinPRCCMaxP最大后验概率译码最大后验概率译码最大似然译码最大似然译码)()()(),(RPCRPCPRPRCPRCPiiiiiiCRMaxP

21、RCMaxP信道编码的分类信道编码的分类汉明码循环码线性分组码非线性分组码分组码线性卷积码非线性卷积码卷积码信道编码纠错码的发展概况纠错码的发展概况通信的数学理论，通信的数学理论，Shannon(1948)汉明码，汉明码，Hamming(1950)级连码，级连码，Forney(1966)卷积码及有效译码卷积码及有效译码,(60年代年代)RS码及码及BCH码的有效译码码的有效译码(60年代年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，码，Berrou(1993)LDPC 码，码，Gallager(1963),Macky(1996)空时编码空时编码,Taro

22、kh(2000)网络编码，纠错码范畴？网络编码，纠错码范畴？Polar码，码，E.Arikan,2009State Key Laboratory of Integrated Services Networks State Key Laboratory of Integrated Services Networks State Key Laboratory of Integrated Services Networks 其实，世上最温暖的语言，其实，世上最温暖的语言，“不是我爱你，而是在一起。不是我爱你，而是在一起。”所以懂得才是最美的相遇！只有彼此以诚相待，彼此尊所以懂得才是最美的相遇！只有彼

23、此以诚相待，彼此尊重，相互包容，相互懂得，才能走的更远。重，相互包容，相互懂得，才能走的更远。相遇是缘，相守是爱。缘是多么的妙不可言，而懂得又是多么的难能可贵。否则就会错过一时，错过一世！相遇是缘，相守是爱。缘是多么的妙不可言，而懂得又是多么的难能可贵。否则就会错过一时，错过一世！择一人深爱，陪一人到老。一路相扶相持，一路心手相牵，一路笑对风雨。在平凡的世界，不求爱的轰轰烈烈；不求誓择一人深爱，陪一人到老。一路相扶相持，一路心手相牵，一路笑对风雨。在平凡的世界，不求爱的轰轰烈烈；不求誓言多么美丽；唯愿简单的相处，真心地付出，平淡地相守，才不负最美的人生；不负善良的自己。言多么美丽；唯愿简单的相

24、处，真心地付出，平淡地相守，才不负最美的人生；不负善良的自己。人海茫茫，不求人人都能刻骨铭心，但求对人对己问心无愧，无怨无悔足矣。大千世界，与万千人中遇见，只是相识的人海茫茫，不求人人都能刻骨铭心，但求对人对己问心无愧，无怨无悔足矣。大千世界，与万千人中遇见，只是相识的开始，只有彼此真心付出，以心交心，以情换情，相知相惜，才能相伴美好的一生，一路同行。开始，只有彼此真心付出，以心交心，以情换情，相知相惜，才能相伴美好的一生，一路同行。然而，生活不仅是诗和远方，更要面对现实。如果曾经的拥有，不能天长地久，那么就要学会华丽地转身，学会忘记。然而，生活不仅是诗和远方，更要面对现实。如果曾经的拥有，不

25、能天长地久，那么就要学会华丽地转身，学会忘记。忘记该忘记的人，忘记该忘记的事儿，忘记苦乐年华的悲喜交集。忘记该忘记的人，忘记该忘记的事儿，忘记苦乐年华的悲喜交集。人有悲欢离合，月有阴晴圆缺。对于离开的人，不必折磨自己脆弱的生命，虚度了美好的朝夕；不必让心灵痛苦不堪，人有悲欢离合，月有阴晴圆缺。对于离开的人，不必折磨自己脆弱的生命，虚度了美好的朝夕；不必让心灵痛苦不堪，弄丢了快乐的自己。擦汗眼泪，告诉自己，日子还得继续，谁都不是谁的唯一，相信最美的风景一直在路上。弄丢了快乐的自己。擦汗眼泪，告诉自己，日子还得继续，谁都不是谁的唯一，相信最美的风景一直在路上。人生，就是一场修行。你路过我，我忘记你

26、；你有情，他无意。谁都希望在正确的时间遇见对的人，然而事与愿违时，人生，就是一场修行。你路过我，我忘记你；你有情，他无意。谁都希望在正确的时间遇见对的人，然而事与愿违时，你越渴望的东西，也许越是无情无义地弃你而去。所以美好的愿望，就会像肥皂泡一样破灭，只能在错误的时间遇到错的人。你越渴望的东西，也许越是无情无义地弃你而去。所以美好的愿望，就会像肥皂泡一样破灭，只能在错误的时间遇到错的人。岁月匆匆像一阵风，有多少故事留下感动。愿曾经的相遇，无论是锦上添花，还是追悔莫及；无论是青涩年华的懵懂赏岁月匆匆像一阵风，有多少故事留下感动。愿曾经的相遇，无论是锦上添花，还是追悔莫及；无论是青涩年华的懵懂赏识

27、，还是成长岁月无法躲避的经历识，还是成长岁月无法躲避的经历愿曾经的过往，依然如花芬芳四溢，永远无悔岁月赐予的美好相遇。愿曾经的过往，依然如花芬芳四溢，永远无悔岁月赐予的美好相遇。其实，人生之路的每一段相遇，都是一笔财富，尤其亲情、友情和爱情。在漫长的旅途上，他们都会丰富你的生命，使其实，人生之路的每一段相遇，都是一笔财富，尤其亲情、友情和爱情。在漫长的旅途上，他们都会丰富你的生命，使你的生命更充实，更真实；丰盈你的内心，使你的内心更慈悲，更善良。所以生活的美好，缘于一颗善良的心，愿我们都能你的生命更充实，更真实；丰盈你的内心，使你的内心更慈悲，更善良。所以生活的美好，缘于一颗善良的心，愿我们都

28、能善待自己和他人。善待自己和他人。一路走来，愿相亲相爱的人，相濡以沫，同甘共苦，百年好合。愿有情有意的人，不离不弃，相惜相守，共度人生的每一路走来，愿相亲相爱的人，相濡以沫，同甘共苦，百年好合。愿有情有意的人，不离不弃，相惜相守，共度人生的每一个朝夕一个朝夕直到老得哪也去不了，依然是彼此手心里的宝，感恩一路有你！直到老得哪也去不了，依然是彼此手心里的宝，感恩一路有你！感谢您对文章的阅读跟下载，希望本感谢您对文章的阅读跟下载，希望本篇文章能帮助到您，建议您下载后自篇文章能帮助到您，建议您下载后自己先查看一遍，把用不上的部分页面己先查看一遍，把用不上的部分页面删掉哦，当然包括最后一页，最后祝删掉哦，当然包括最后一页，最后祝您生活愉快您生活愉快!