纠错码原理与方法教学课件

时间反复无常，鼓着翅膀飞逝纠错码原理与方法纠错码原理与方法ppt课件课件State Key Laboratory of Integrated Services Networks State Key Laboratory of Integrated Services Networks 1.1 纠错码的作用纠错码的作用数字通信系统模型数字通信系统模型数字通信系统的简化模型数字通信系统的简化模型信源、信道与信道编码信源、信道与信道编码信源信源：实时性与非实时性，可变速率，多媒体：实时性与非实时性，可变速率，多媒体信道信道：离散与连续，时变与非时变，有记忆与无：离散与连续，时变与非时变，有记忆与无记忆记忆常见信道：模拟基带信道、射频信道、存储器等不同的信源和信道类型所对应的最佳编码方案是不同的信源和信道类型所对应的最佳编码方案是不同的。不同的。信道编码信道编码：从消息到信道波形或矢量的映射复接、代数编码、调制、成形滤波、扩频、上下复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于变频等等都属于广义的信道编码广义的信道编码范畴范畴信道编码：从消息到信道波形或矢量的映射信道编码：从消息到信道波形或矢量的映射信信 道道信道信道实际上也是从上也是从发空空间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)重符号）根据奈奎斯特采样定理，带限的时域连续波形可以用采样序列描述。无记忆信道无记忆信道离散信道离散信道当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）时，可以等效于一个无记忆信道。）时，可以等效于一个无记忆信道。有记忆信道的无记忆化有记忆信道的无记忆化对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信道信道二进制删除信道二进制删除信道二进制删除信道二进制删除信道二进制纯删除信道二进制纯删除信道二进制纯删除信道二进制纯删除信道错误类型错误类型随机错误随机错误随机错误信道：深空信道，卫星信随机错误信道：深空信道，卫星信道等道等突发错误突发错误突发错误信道：无线信道，电缆传突发错误信道：无线信道，电缆传输（开关脉冲噪声，串音），磁记录信道输（开关脉冲噪声，串音），磁记录信道混合错误混合错误混合信道混合信道差错控制系统分类差错控制系统分类可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号State Key Laboratory of Integrated Services Networks 纠错码的基本原理纠错码的基本原理纠错码如何纠正错误？纠错码如何纠正错误？引入信道编码引入信道编码检错和纠错：对付信道引入的差错检错和纠错：对付信道引入的差错直观的译码准则：最小距离译码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=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能够纠正一个错误同时发现两个错误译码正确译码失败译码错误发现三个错误译码失败：译码器根据接收到的信号无法作出明确判断译码错误：译码器根据接收到的信号作出错误判断不完备译码完备译码：根据接收信号，译码器一定能作出是哪 一组信息的判断有编码系统和无编码系统有编码系统和无编码系统调制也是一种编码调制也是一种编码广义地讲，实际系统中都有信道编码，而现实中广义地讲，实际系统中都有信道编码，而现实中常分为编码和调制两块，前者负责离散编码，后常分为编码和调制两块，前者负责离散编码，后者负责将离散符号变成波形，这样才有无编码系者负责将离散符号变成波形，这样才有无编码系统及编码增益等概念统及编码增益等概念M进制正交编码加进制正交编码加BPSK调制的性能与无编码的调制的性能与无编码的M进制正交进制正交FSK是完全一致的。是完全一致的。信道编码的作用信道编码的作用信道编码的作用：信道编码的作用：在资源、可靠性和传信在资源、可靠性和传信量量之间选择一个好的工作点（有时还要考之间选择一个好的工作点（有时还要考虑延时）。虑延时）。资源资源指的提供信息传输所付出的代价指的提供信息传输所付出的代价包括频率、时间、空间、功率等等。但不包括实现复杂度一个好的编码就是要充分利用资源，传递尽可能多的信息三种情形：三种情形：给定资源和可靠性要求，通过信道编码尽量提高传输速率给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销给定资源和传输速率，通过编码提高可靠性编码的实质编码的实质利用冗余降低差错概率利用冗余降低差错概率将所有可能的输入信息（消息）映射将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道个点的集合要小于（包含于）全信道空间中空间中。编码与构造编码编码与构造编码编码编码：针对当前要传的消息，根据映射规：针对当前要传的消息，根据映射规则，确定当前要发哪一个波形（矢量）则，确定当前要发哪一个波形（矢量）构造编码构造编码：寻找并建立映射规则：寻找并建立映射规则编码设计准则编码设计准则最佳译码时的差错概率最佳译码时的差错概率（最佳译码有可能做不到）（最佳译码有可能做不到）自由距最大化准则自由距最大化准则一种最常用的编码一种最常用的编码构造准则构造准则纠错码如何纠正错误？纠错码如何纠正错误？在信息序列之后按照一定的规则添加一定长度在信息序列之后按照一定的规则添加一定长度的保护比特的保护比特(校验比特或监督比特校验比特或监督比特)State Key Laboratory of Integrated Services Networks 几个基本概念几个基本概念许用码组和禁用码组译码错误和译码失败完备译码和不完备译码汉明距离和重量最大似然译码最大后验概率译码错误图样码纠错能力判断编码增益错误图样错误图样Example发送序列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)检测检测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,k0,m)卷积码，若用最大似然卷积码，若用最大似然译码，随着码长的增加其译码错误概率译码，随着码长的增加其译码错误概率p可可以任意小。以任意小。信道容量信道容量在高斯白噪声信道在高斯白噪声信道时，信道容量时，信道容量0E(R)RC1C2C1C2性能的衡量性能的衡量香农限香农限软判决条件下，软判决条件下，BPSK调制，调制，AWGN信道香农限信道香农限各种码的性能比较译码准则译码准则首先说明，译码本身是一种信息处理，肯定会引首先说明，译码本身是一种信息处理，肯定会引入一定的信息损失，但最重要的是尽量正确地恢入一定的信息损失，但最重要的是尽量正确地恢复原始信息。复原始信息。最大后验概率最大后验概率最大似然最大似然序列译码序列译码几种基本的译码方法几种基本的译码方法 问题：问题：MC R 如何根据接收信号如何根据接收信号R估计发送序列估计发送序列C,进而估计信息序列进而估计信息序列M 设计译码算法的原则：使译码错误概率最小设计译码算法的原则：使译码错误概率最小 最大后验概率译码最大后验概率译码最大似然译码最大似然译码信道编码的分类信道编码的分类纠错码的发展概况纠错码的发展概况通信的数学理论，通信的数学理论，Shannon(1948)汉明码，汉明码，Hamming(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,200951、天下之事常成于困约，而败于奢靡。、天下之事常成于困约，而败于奢靡。陆游陆游52、生命不等于是呼吸，生命是活动。、生命不等于是呼吸，生命是活动。卢梭卢梭53、伟大的事业，需要决心，能力，组织和责任感。、伟大的事业，需要决心，能力，组织和责任感。易卜生易卜生54、唯书籍不朽。、唯书籍不朽。乔特乔特55、为中华之崛起而读书。、为中华之崛起而读书。周恩来周恩来谢谢！