纠错与编码理论第1章

1、纠错与编码理论纠错与编码理论课程说明 课程性质：学位课课程性质：学位课 前续课程：通信原理、数字通信原理前续课程：通信原理、数字通信原理 考试形式：闭卷考试考试形式：闭卷考试 参考书：参考书：纠错码纠错码-原理与方法原理与方法（西安电（西安电子科技大学出版社）、子科技大学出版社）、通信原理通信原理（国（国防工业出版社）、防工业出版社）、数字通信原理数字通信原理（西（西安电子科技大学出版社）安电子科技大学出版社） 出勤要求出勤要求第一章第一章 纠错码的基本概念纠错码的基本概念 思考：纠错码在通信系统中的作用？思考：纠错码在通信系统中的作用？ 1.1 数字通信系统组成及信道模型数字通信系统组成及信

2、道模型 （1）数字通信系统组成）数字通信系统组成信源信源信宿信宿编编码码信信道道 （2）信道模型）信道模型 例例1.1.1 信号实际传输情况信号实际传输情况 对于第三位的处理方法对于第三位的处理方法 直接作出是直接作出是0还是还是1 输出一个未知或待定信号输出一个未知或待定信号x 输出一种有关该码的信息，例如概率输出一种有关该码的信息，例如概率（硬判决）（硬判决）（删除判决）（删除判决）（软判决）（软判决） 硬判决情况下，信道模型为硬判决情况下，信道模型为 删除判决情况下，信道模型为删除判决情况下，信道模型为101001011110010011ppppppppP信道转移概率矩阵信道转移概率矩阵

3、若若p01=p10=pe（转移概率）（转移概率）,称信道为称信道为二进制对称信道（二进制对称信道（BSC）二进制删除信道（二进制删除信道（BEC）二进制纯删除信道（二进制纯删除信道（BEC）q（删除概率）（删除概率）（忽略（忽略pe）思考：两者的纠错能力？思考：两者的纠错能力？ （3）错误图样）错误图样则，则，R=C+E,或或E=R-C称称E为信道的为信道的错误图样错误图样或者或者干扰矢量干扰矢量例例1.1.2思考：信道中可能产生的错误图样思考：信道中可能产生的错误图样E共有多少种？共有多少种？突发长度突发长度：E中，第一个中，第一个1与最后一个与最后一个1之间的长度。之间的长度。突发图样突发

4、图样：突发长度对应的图样。：突发长度对应的图样。5110111.2 差错控制系统和纠错码分类差错控制系统和纠错码分类 1.差错控制系统分类差错控制系统分类（1）重传反馈系统（）重传反馈系统（ARQ） 优点优点缺点缺点译码设备简单译码设备简单纠错能力强纠错能力强适应能力强适应能力强适合于复杂干扰的信道适合于复杂干扰的信道要求有反馈信道要求有反馈信道控制电路比较复杂控制电路比较复杂连贯性和实时性差连贯性和实时性差（2）前向纠错系统（）前向纠错系统（FEC）优点优点缺点缺点译码设备复杂译码设备复杂纠错码要与信道干扰匹配纠错码要与信道干扰匹配适应性差适应性差码冗余度高码冗余度高编码效率低编码效率低不需

5、要反馈信道不需要反馈信道可一对多传输可一对多传输控制电路简单控制电路简单实时性好实时性好（3）混合纠错系统（）混合纠错系统（HEC）（4）狭义信息反馈系统（）狭义信息反馈系统（IRQ）HEC是是ARQ和和FEC的折中方案，应用较广的折中方案，应用较广 2 纠错码的分类纠错码的分类（1）按照对信息元处理方法的不同，分为）按照对信息元处理方法的不同，分为分组码分组码和和卷积码卷积码（2）按照校验元与信息元间的关系，分为）按照校验元与信息元间的关系，分为线线性码性码和和非线性码非线性码（3）按照纠正错误的类型可分为）按照纠正错误的类型可分为纠正随机错纠正随机错误的码误的码、纠正突发错误的码纠正突发错

6、误的码、纠正同步错误纠正同步错误的码的码等等（4）按照码元取值，分为）按照码元取值，分为二进制码二进制码、q进制码进制码（5）按照对信息元保护能力是否相等，分为）按照对信息元保护能力是否相等，分为等保护纠错码等保护纠错码、不等保护纠错码不等保护纠错码1.3最大似然译码和纠错码的概念最大似然译码和纠错码的概念 1 基本定义基本定义 （1）分组码分组码注意：注意：码率码率R=k/n,表示信息位在码字中所占的比重，表示信息位在码字中所占的比重，R是是码有效性的一个基本参数。码有效性的一个基本参数。（2）卷积码）卷积码码率码率R=k0/n0编码约束长度编码约束长度nc=n0(m+1),表示表示k0个信

7、息元从输入编码个信息元从输入编码器到离开时在码序列中影响的码元数目。器到离开时在码序列中影响的码元数目。 2 最大似然译码最大似然译码)|()|(RCCPREP译码器译码器条件译码错误概率条件译码错误概率：译码器译码器错误译码概率错误译码概率：RERPREPP)()|()|(min)|(minminRCCPREPPRRE最佳译码规则：最佳译码规则：max(|)RP CC R由贝叶斯公式：由贝叶斯公式：(|)iP CR()( )iP C RP R() (|)( )iiP C P R CP R若发送端发送每个码字的概率相同，即若发送端发送每个码字的概率相同，即P(Ci)相同，相同，P(R)与译与译

8、码器无关，因此有码器无关，因此有kkiiiiCRPRCP2, 2, 12, 2, 1)|(max)|(max 3 汉明距离与重量汉明距离与重量汉明距离汉明距离：两个：两个n重重x，y之间对应位取值不同的个数，用之间对应位取值不同的个数，用d(x,y)表示。表示。汉明重量汉明重量：n重重x中非零码元的个数，用中非零码元的个数，用w(x)表示。表示。例例1.3.1 若若x:(111000),y:(101010),则则d(x,y)=? w(x)=? w(y)=?最小汉明距离最小汉明距离： (n,k)分组码中，任两个码字之间距离的最小值，分组码中，任两个码字之间距离的最小值，用用d0表示。表示。例例1

9、.3.2 （3,2）码的码字有（）码的码字有（000）、（）、（011）、（）、（101）、）、（110），则），则d0=？思考：思考：d0有什么作用？有什么作用？),(min),(,0yxddknyx例例1.3.3 重复码重复码即（即（n,1）码，其编码规则是）码，其编码规则是n-1个校验元是信息元的重复。个校验元是信息元的重复。或或称为称为最小汉明距离译码最小汉明距离译码提示：提示：对重复码而言，只需根据对重复码而言，只需根据0、1的多少来判断信息组为的多少来判断信息组为0还是还是1。大数准则译码大数准则译码完备译码完备译码当当n为奇数时，按照此规则总能作出为奇数时，按照此规则总能作出0或

10、或1的判决。的判决。当当n为偶数时，可能出现为偶数时，可能出现0、1个数相等，造成译码失败。个数相等，造成译码失败。不完备译码不完备译码思考：思考：译码失败怎么办？译码失败怎么办？注意：注意：“译码失败译码失败”不等于不等于“译码错误译码错误”！现以重复码为例，说明现以重复码为例，说明R、d0及译码错误间的关系。及译码错误间的关系。思考：思考：一个最小距离为一个最小距离为d的分组码，最多可纠正多少个错误？的分组码，最多可纠正多少个错误？（向下取整）（向下取整）例例1.3.4 奇偶校验码奇偶校验码即只有一个校验元的即只有一个校验元的(n,n-1)码码现以奇偶校验码为例，说明现以奇偶校验码为例，说明R、d0及译码错误间的关系。及译码错误间的关系。1949年，香农