纠错码-原理与方法课件

1、纠错码原理与方法有关事项目的：了解信道编码的作用与意义，对信道编码的研究方法和成果有广泛的基本认识，学会应用，为进一步研究打下基础特点：以概念和物理意义为主，数学推导尽量放到课外考核形式：论文/计算机仿真+开卷考试参考书： “纠错码原理与方法”，王新梅，西安电子科技大学出版社，高等学校教材； “差错控制编码（第二版）”, Shu Lin，Daniel J.Costello, 机械工业出版社，电子与电气工程丛书） 其他有关事项课外阅读，以turbo code，LDPC code，喷泉码，polar码为引子论文与编程：五年内的国外期刊，以一两篇为主，结合自己的理解，按电子学报论文形式，有创见更好，

2、可以与编程结合。编程内容在随后的课程中出题目。占50%考试：基本概念，50%联系方式：email: 第1章 纠错码基本概念什么是纠错码？为什么要引入纠错码？纠错码在通信系统中起什么作用？如何实现纠错码？如何衡量纠错码的纠错能力及性能？纠错码的发展概况1.1 纠错码的作用数字通信系统模型数字通信系统的简化模型信源、信道与信道编码信源：实时性与非实时性，可变速率，多媒体信道：离散与连续，时变与非时变，有记忆与无记忆常见信道：模拟基带信道、射频信道、存储器等不同的信源和信道类型所对应的最佳编码方案是不同的。信道编码：从消息到信道波形或矢量的映射复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于

3、广义的信道编码范畴信道编码：从消息到信道波形或矢量的映射信 道信道实际上也是从发空间X到收空间Y一个映射函数发空间的维数n与收空间的维数m可以不等根据收发空间中每一维所取的数域有限或无限可分为离散信道和连续信道这里借用了空间的名称，但只用到了它的集合概念而没有用到空间中的运算信道特性的描述离散信道可用转移概率律描述：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)重符号）根据

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

5、于一个无记忆信道。有记忆信道的无记忆化对A作线性变换使正交化得：A=UTU，其中为A的特征值矩阵。代入得 y= UTUx+n，令x=UTx，y=UTy，n=UTn，则有y=x+n。于是对x和y而言就形成了一个无记忆信道。由于U为正交变换，不会产生信息量丢失，因此可以认为X-Y信道与X-Y信道是等价的。于是我们就可以直接利用有关无记忆信道的编码了。信道模型离散无记忆信道DMC二进制信道二进制信道DMC信道DMC信道二进制删除信道二进制删除信道二进制纯删除信道二进制纯删除信道错误类型随机错误随机错误信道：深空信道，卫星信道等突发错误突发错误信道：无线信道，电缆传输（开关脉冲噪声，串音），磁记录信道

6、混合错误混合信道差错控制系统分类可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号纠错码的基本原理纠错码如何纠正错误？引入信道编码检错和纠错：对付信道引入的差错直观的译码准则：最小距离译码Shannon第二定理当信息速率R小于信道容量C时，总存在一种编码方式使差错率低于任一给定值e接近信道容量重复码00001111若将每个比特重复n次，则构成一个码长为n，信息位长度为1的(n,1)重复码,且编码效率(码率)R=1/n许用码字01010.90.90.10.1BSC信道n=2时许用码组：00，11禁用码组：01，10能够发现一个错误，但不能纠正错误n

7、=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能够纠正一个错误同时发现两个错误译码正确译码失败译码错误发现三个错误译码失败：译码器根据接收到的信号无法作出明确判断译码错误：译码器根据接收到的信号作出错误判断不完备译码完备译码：根据接收信号，译码器一定能作出是哪 一组信息的判断有编码系统和无编码系统调制也是一种

8、编码广义地讲，实际系统中都有信道编码，而现实中常分为编码和调制两块，前者负责离散编码，后者负责将离散符号变成波形，这样才有无编码系统及编码增益等概念M进制正交编码加BPSK调制的性能与无编码的M进制正交FSK是完全一致的。信道编码的作用信道编码的作用：在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）。资源指的提供信息传输所付出的代价包括频率、时间、空间、功率等等。但不包括实现复杂度一个好的编码就是要充分利用资源，传递尽可能多的信息三种情形：给定资源和可靠性要求，通过信道编码尽量提高传输速率给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销给定资源和传输速率，通过编码

9、提高可靠性编码的实质利用冗余降低差错概率将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。编码与构造编码编码：针对当前要传的消息，根据映射规则，确定当前要发哪一个波形（矢量）构造编码：寻找并建立映射规则编码设计准则最佳译码时的差错概率（最佳译码有可能做不到）自由距最大化准则一种最常用的编码构造准则纠错码如何纠正错误？ 在信息序列之后按照一定的规则添加一定长度的保护比特(校验比特或监督比特)几个基本概念许用码组和禁用码组译码错误和译码失败完备译码和不完备译码汉明距离和重量最大似然译码最大后验概率译码错误图样码纠错能力判断编码增益错误图样Exa

10、mple发送序列C: (1111011000)接收序列R: (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定义为该分组码的最小汉明距离 码纠错能力的判断任一(n, k)分组码，若要在码字内： 1)

11、 检测e个随机错误，则要求码的最小汉明距离d0=e+1 2) 纠正t个随机错误，则要求d0=2t+1 3) 纠正t个随机错误，同时检测e (e=t)个错误，则要求d0=e+t+1 4) 纠正t个随机错误和个删除，则要求 d0=2t+1 性能的衡量编码增益在一个码率为R的编码通信系统中，为传输每个信息比特需要传输符号的数目为1/R，若每个传输符号的能量为Es，则每个信息比特对应的能量Eb为：Eb=Es/R编码阈值给定性能前提下， 编码增益=未编码时需要的信噪比(dB) 编码时需要的信噪比(dB)信道编码定理每个信道具有确定的信道容量，对任何小于C的码率R，存在有速率为R码长为n的分组码及(n0,

12、k0,m)卷积码，若用最大似然译码，随着码长的增加其译码错误概率p可以任意小。信道容量在高斯白噪声信道时，信道容量0E(R)RC1C2C1C2性能的衡量香农限软判决条件下，BPSK调制，AWGN信道香农限各种码的性能比较译码准则首先说明，译码本身是一种信息处理，肯定会引入一定的信息损失，但最重要的是尽量正确地恢复原始信息。最大后验概率最大似然序列译码几种基本的译码方法 问题： MC R 如何根据接收信号R估计发送序列C,进而估计信息序列M 设计译码算法的原则：使译码错误概率最小 最大后验概率译码最大似然译码信道编码的分类纠错码的发展概况通信的数学理论，Shannon(1948)汉明码，Hamm

13、ing (1950)级连码，Forney(1966)卷积码及有效译码, (60年代)RS码及BCH码的有效译码(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993) LDPC 码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000)网络编码，纠错码范畴？Polar码，E.Arikan, 2009其实，世上最温暖的语言，“ 不是我爱你，而是在一起。” 所以懂得才是最美的相遇！只有彼此以诚相待，彼此尊重，相互包容，相互懂得，才能走的更远。相遇是缘，相守是爱。缘是多么的妙不可言，而懂得又是多么的难能可贵。

14、否则就会错过一时，错过一世！择一人深爱，陪一人到老。一路相扶相持，一路心手相牵，一路笑对风雨。在平凡的世界，不求爱的轰轰烈烈；不求誓言多么美丽；唯愿简单的相处，真心地付出，平淡地相守，才不负最美的人生；不负善良的自己。人海茫茫，不求人人都能刻骨铭心，但求对人对己问心无愧，无怨无悔足矣。大千世界，与万千人中遇见，只是相识的开始，只有彼此真心付出，以心交心，以情换情，相知相惜，才能相伴美好的一生，一路同行。然而，生活不仅是诗和远方，更要面对现实。如果曾经的拥有，不能天长地久，那么就要学会华丽地转身，学会忘记。忘记该忘记的人，忘记该忘记的事儿，忘记苦乐年华的悲喜交集。人有悲欢离合，月有阴晴圆缺。对于

15、离开的人，不必折磨自己脆弱的生命，虚度了美好的朝夕；不必让心灵痛苦不堪，弄丢了快乐的自己。擦汗眼泪，告诉自己，日子还得继续，谁都不是谁的唯一，相信最美的风景一直在路上。人生，就是一场修行。你路过我，我忘记你；你有情，他无意。谁都希望在正确的时间遇见对的人，然而事与愿违时，你越渴望的东西，也许越是无情无义地弃你而去。所以美好的愿望，就会像肥皂泡一样破灭，只能在错误的时间遇到错的人。岁月匆匆像一阵风，有多少故事留下感动。愿曾经的相遇，无论是锦上添花，还是追悔莫及；无论是青涩年华的懵懂赏识，还是成长岁月无法躲避的经历愿曾经的过往，依然如花芬芳四溢，永远无悔岁月赐予的美好相遇。其实，人生之路的每一段相遇，都是一笔财富，尤其亲情、友情和爱情