第一章-纠错码的基本概念资料课件

纠错码的基本概念纠错码的基本概念 第一章第一章纠错编码技术纠错编码技术第一章第一章纠错码的基本概念纠错码的基本概念福州大学阳光学院福州大学阳光学院 纠错码的基本概念纠错码的基本概念 第一章第一章本章主要内容本章主要内容1.1 1.1 编码系统模型编码系统模型1.2 1.2 信道错误类型与信道模型信道错误类型与信道模型 1.3 1.3 差错控制的基本方式差错控制的基本方式1.4 1.4 纠错码的分类纠错码的分类1.5 1.5 最大后验与最大似然译码最大后验与最大似然译码1.6 1.6 纠错码的基本概念纠错码的基本概念1.7 1.7 几种常用的编码方式几种常用的编码方式7/13/20242纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章本章要求本章要求p掌握：掌握：n差错控制方式差错控制方式n纠错码的基本概念纠错码的基本概念p理解：理解：n最大似然译码最大似然译码p了解：了解：n纠错编码的作用、基本思想和编码系统纠错编码的作用、基本思想和编码系统模型模型7/13/20243纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型7/13/20244纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型信源编码器：信源编码器：将信源发出的消息如语言、将信源发出的消息如语言、图像、图像、文字等转换成为二进制文字等转换成为二进制(也可转换成为多进制也可转换成为多进制)形形式的信息序列。式的信息序列。信源编码器的设计目标：信源编码器的设计目标：（1 1）以最低的比特率表示信源的输出消息；）以最低的比特率表示信源的输出消息；（2 2）信源的输出可由信息序列）信源的输出可由信息序列mm准确的重现。准确的重现。7/13/20245纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型信道编码器：信道编码器：将信息序列将信息序列mm变换成离散的编码序变换成离散的编码序列列CC，称之为码字。，称之为码字。本课程的主要内容之一，就是本课程的主要内容之一，就是设计和实现信道设计和实现信道编码器编码器，以抵抗传输或存储码字所面临的噪声，以抵抗传输或存储码字所面临的噪声环境的影响。环境的影响。7/13/20246纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型调制器或写入单元：调制器或写入单元：将信道编码器输出的每个符将信道编码器输出的每个符号，转换为持续时间为号，转换为持续时间为T T秒的适合传输（或记录）秒的适合传输（或记录）的波形，这些波形进入信道或存储媒质，并受到的波形，这些波形进入信道或存储媒质，并受到噪声的干扰。噪声的干扰。解调器或读出单元：解调器或读出单元：处理收到的每个持续时处理收到的每个持续时间为间为T T秒的波形，然后产生离散（量化）或连秒的波形，然后产生离散（量化）或连续（非量化）的输出。续（非量化）的输出。解调器的输出序列称为解调器的输出序列称为接收序列接收序列RR。7/13/20247纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型信道译码器：信道译码器：将接收序列将接收序列RR变换为二进制序列变换为二进制序列 ，称之为，称之为 估计信息序列。估计信息序列。本课程的另一主要内容，就是设计和实现使译码本课程的另一主要内容，就是设计和实现使译码错误概率最小错误概率最小的信道译码器。的信道译码器。译码策略根据信道编码规则和信道的噪声特性设译码策略根据信道编码规则和信道的噪声特性设计。计。7/13/20248纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1 编码系统模型编码系统模型编码系统的简化模型编码系统的简化模型编码系统的简化模型编码系统的简化模型7/13/20249纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.2 信道错误类型与信道模型信道错误类型与信道模型p随机错误和随机信道随机错误和随机信道p突发错误和突发信道突发错误和突发信道p混合错误和混合信道混合错误和混合信道7/13/202410纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.2 信道错误类型与信道模型信道错误类型与信道模型p随机错误和随机信道随机错误和随机信道n随机错误：信道传输中，信息序列各码随机错误：信道传输中，信息序列各码元发生的出错事件彼此独立，即每个码元发生的出错事件彼此独立，即每个码元独立的按一定的概率发生差错。元独立的按一定的概率发生差错。n只存在随机错误的信道称为无记忆信道只存在随机错误的信道称为无记忆信道（随机信道），用信道转移概率来描述。（随机信道），用信道转移概率来描述。例如，二进制对称信道例如，二进制对称信道BSCBSC和离散无记忆和离散无记忆信道信道DMCDMC。7/13/202411纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章二进制对称信道二进制对称信道（Binary Symmetric Channel,BSCBinary Symmetric Channel,BSCBinary Symmetric Channel,BSCBinary Symmetric Channel,BSC）P(0/0)=1-p P(0/0)=1-p P(1/0)=pP(1/0)=pP(1/1)=1-pP(1/1)=1-pP(0/1)=pP(0/1)=p输入符号取值集合输入符号取值集合输入符号取值集合输入符号取值集合 X=0 X=0，11输出符号取值集合输出符号取值集合输出符号取值集合输出符号取值集合 Y=0 Y=0，110 01 10 01 1XXY Yp pp p1-p1-p1-p1-p1.2 信道错误类型与信道模型信道错误类型与信道模型7/13/202412纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章离散无记忆信道离散无记忆信道（Discrete Memoryless Channel,DMCDiscrete Memoryless Channel,DMCDiscrete Memoryless Channel,DMCDiscrete Memoryless Channel,DMC）输入符号取值集合输入符号取值集合输入符号取值集合输入符号取值集合X=xX=x0 0,x,x1 1,x,xq-1q-1 输出符号取值集合输出符号取值集合输出符号取值集合输出符号取值集合Y=yY=y0 0,y,y1 1,y,yQ-1Q-1 qQqQ个条件概率：个条件概率：个条件概率：个条件概率：P(yP(yj j/x/xi i)=p)=pij ij其中，其中，其中，其中，i=0,1,q-1;j=0,1,Q-1i=0,1,q-1;j=0,1,Q-1x x0 0 x x1 1x xq-1q-1.y y0 0y y1 1y y2 2.y yQ-1Q-1P(yP(y0 0/x/x0 0)P(yP(y1 1/x/x0 0)P(yP(y2 2/x/x0 0)P(yP(yQ-1Q-1/x/x0 0)P(yP(y0 0/x/x1 1)P(yP(y1 1/x/x1 1)P(yP(y2 2/x/x1 1)P(yP(yQ-1Q-1/x/x1 1)1.2 信道错误类型与信道模型信道错误类型与信道模型7/13/202413纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.2 信道错误类型与信道模型信道错误类型与信道模型p突发错误和突发信道突发错误和突发信道n突发错误：噪声对各传输码元的影响不是独突发错误：噪声对各传输码元的影响不是独立的，从而导致差错是一连串出现的。立的，从而导致差错是一连串出现的。例如移动通信中信号在某一段时间内发例如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划生衰落，造成一串差错；光盘上的一条划痕等等。痕等等。n存在突发错误的信道，称之为有记忆信道存在突发错误的信道，称之为有记忆信道（突发信道）。（突发信道）。7/13/202414纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.2 信道错误类型与信道模型信道错误类型与信道模型p混合错误和混合信道混合错误和混合信道n混合错误：混合错误：既有突发错误又有随机错误。既有突发错误又有随机错误。n突发错误和随机错误并存的信道称之为突发错误和随机错误并存的信道称之为混合混合信道信道。7/13/202415纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章错误图样：错误图样：设发送的是序列设发送的是序列设发送的是序列设发送的是序列C C C C（码元长度为（码元长度为（码元长度为（码元长度为n n n n），通过信道传），通过信道传），通过信道传），通过信道传输后，接收端的序列为输后，接收端的序列为输后，接收端的序列为输后，接收端的序列为R R R R。由于信道中存在干扰，。由于信道中存在干扰，。由于信道中存在干扰，。由于信道中存在干扰，R R R R序列中的某些码元和序列中的某些码元和序列中的某些码元和序列中的某些码元和C C C C序列中的对应码元的值可序列中的对应码元的值可序列中的对应码元的值可序列中的对应码元的值可能不同，如果信道中的干扰采用二进制序列能不同，如果信道中的干扰采用二进制序列能不同，如果信道中的干扰采用二进制序列能不同，如果信道中的干扰采用二进制序列e e e e表示，表示，表示，表示，相应有错误的位取值为相应有错误的位取值为相应有错误的位取值为相应有错误的位取值为1 1 1 1，无错的位取值为，无错的位取值为，无错的位取值为，无错的位取值为0 0 0 0，可，可，可，可得得得得e=CRe=CRe=CRe=CR。1.2 信道错误类型与信道模型信道错误类型与信道模型7/13/202416纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p例：发送序列例：发送序列C C：（：（11111000001111100000），收到的），收到的序列序列R R：（：（10010100001001010000），第二、三、五、），第二、三、五、六位产生了错误，因此错误图样六位产生了错误，因此错误图样e e的二、三、的二、三、五、六位取值为五、六位取值为1 1，即，即e e：(0110110000)(0110110000)p对于突发信道，错误图样中，第一个对于突发信道，错误图样中，第一个“1”“1”和最后一个和最后一个“1”“1”之间的码元总个数称为之间的码元总个数称为突突发长度发长度，其图样成为突发图样。该例中，其图样成为突发图样。该例中，突发图样是（突发图样是（1101111011），突发长度为），突发长度为5 5。1.2 信道错误类型与信道模型信道错误类型与信道模型7/13/202417纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.3 差错控制的基本方式差错控制的基本方式p反馈重传方式反馈重传方式 p前向纠错方式前向纠错方式 p混合方式混合方式7/13/202418纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.3 差错控制的基本方式差错控制的基本方式p反馈重传方式反馈重传方式(ARQARQ)n工作原理：发送端发送检错码，通过信道传输工作原理：发送端发送检错码，通过信道传输工作原理：发送端发送检错码，通过信道传输工作原理：发送端发送检错码，通过信道传输到接收端，接收端译码器根据编码规则判断是到接收端，接收端译码器根据编码规则判断是到接收端，接收端译码器根据编码规则判断是到接收端，接收端译码器根据编码规则判断是否有错误，并把判决信号通过反馈信道送回发否有错误，并把判决信号通过反馈信道送回发否有错误，并把判决信号通过反馈信道送回发否有错误，并把判决信号通过反馈信道送回发送端。发送端根据判决信号确定是否重新发送，送端。发送端根据判决信号确定是否重新发送，送端。发送端根据判决信号确定是否重新发送，送端。发送端根据判决信号确定是否重新发送，直到接收端检查无误为止。直到接收端检查无误为止。直到接收端检查无误为止。直到接收端检查无误为止。7/13/202419纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.3 差错控制的基本方式差错控制的基本方式优点：优点：优点：优点：1.1.1.1.编译码设备简单编译码设备简单编译码设备简单编译码设备简单2.2.2.2.纠纠纠纠错能力强错能力强错能力强错能力强3.3.3.3.对信道的适应性强对信道的适应性强对信道的适应性强对信道的适应性强缺点：缺点：缺点：缺点：1.1.1.1.需反馈信道需反馈信道需反馈信道需反馈信道2.2.2.2.控制电路复杂控制电路复杂控制电路复杂控制电路复杂3.3.3.3.传送信息的实时性、连贯性差传送信息的实时性、连贯性差传送信息的实时性、连贯性差传送信息的实时性、连贯性差信源信源信源信源编码器和缓存器编码器和缓存器编码器和缓存器编码器和缓存器重发控制重发控制重发控制重发控制双双双双向向向向信信信信道道道道反馈控制器反馈控制器反馈控制器反馈控制器检错码检错码检错码检错码译码器译码器译码器译码器信宿信宿信宿信宿缓存器缓存器缓存器缓存器ARQARQ通信系统组成通信系统组成通信系统组成通信系统组成7/13/202420纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p前向纠错方式前向纠错方式(FEC)(FEC)n工作原理：发送端发送能纠正错误的码字，在接工作原理：发送端发送能纠正错误的码字，在接工作原理：发送端发送能纠正错误的码字，在接工作原理：发送端发送能纠正错误的码字，在接收端根据接收到的码字和编码规则，能自动纠正收端根据接收到的码字和编码规则，能自动纠正收端根据接收到的码字和编码规则，能自动纠正收端根据接收到的码字和编码规则，能自动纠正传输中的错误。传输中的错误。传输中的错误。传输中的错误。n不需要反馈信道，实时性好。不需要反馈信道，实时性好。不需要反馈信道，实时性好。不需要反馈信道，实时性好。n随着纠错能力的提高，编译码设备复杂。随着纠错能力的提高，编译码设备复杂。随着纠错能力的提高，编译码设备复杂。随着纠错能力的提高，编译码设备复杂。1.3 差错控制的基本方式差错控制的基本方式发端发端收端收端纠错码纠错码7/13/202421纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.3 差错控制的基本方式差错控制的基本方式p混合方式混合方式(HEC)(HEC)n工作原理：结合前向纠错和工作原理：结合前向纠错和工作原理：结合前向纠错和工作原理：结合前向纠错和ARQARQARQARQ的系统，在纠错的系统，在纠错的系统，在纠错的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则能力范围内，自动纠正错误，超出纠错范围则能力范围内，自动纠正错误，超出纠错范围则能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。要求发送端重新发送。要求发送端重新发送。要求发送端重新发送。发端发端收端收端检纠错码检纠错码判决信号判决信号7/13/202422纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.4 纠错码的分类纠错码的分类p按差错控制编码的不同功能：按差错控制编码的不同功能：n检错码：发现错误的码检错码：发现错误的码检错码：发现错误的码检错码：发现错误的码n纠错码：自动纠正错误的码纠错码：自动纠正错误的码纠错码：自动纠正错误的码纠错码：自动纠正错误的码p按信息码元与附加监督码元间检验关系：按信息码元与附加监督码元间检验关系：n线性码线性码线性码线性码(Linear Code)(Linear Code)(Linear Code)(Linear Code)：监督码元与信息码元：监督码元与信息码元：监督码元与信息码元：监督码元与信息码元满足线性关系满足线性关系满足线性关系满足线性关系n非线性码非线性码非线性码非线性码(Nonlinear Code)(Nonlinear Code)(Nonlinear Code)(Nonlinear Code)：监督码元与信息：监督码元与信息：监督码元与信息：监督码元与信息元不满足线性关系元不满足线性关系元不满足线性关系元不满足线性关系7/13/202423纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.4 纠错编码的分类纠错编码的分类p按信息码元与监督码元间约束方式：按信息码元与监督码元间约束方式：n n分组码分组码分组码分组码(Block Code)(Block Code)(Block Code)(Block Code)：信息序列每：信息序列每：信息序列每：信息序列每k k k k位分成一组，产生位分成一组，产生位分成一组，产生位分成一组，产生r r r r位位位位监督元，输出长度为监督元，输出长度为监督元，输出长度为监督元，输出长度为n=r+kn=r+kn=r+kn=r+k的码字。的码字。的码字。的码字。r r r r位监督元只与位监督元只与位监督元只与位监督元只与本分组的本分组的本分组的本分组的k k k k位信息元有关，记为（位信息元有关，记为（位信息元有关，记为（位信息元有关，记为（n,kn,kn,kn,k）。）。）。）。n n卷积码卷积码卷积码卷积码(Convolutional Code)(Convolutional Code)(Convolutional Code)(Convolutional Code)：编码器给每：编码器给每：编码器给每：编码器给每k k k k0 0 0 0位信息加上位信息加上位信息加上位信息加上n n n n0 0 0 0-k k k k0 0 0 0位监督元得到长度为位监督元得到长度为位监督元得到长度为位监督元得到长度为n n n n0 0 0 0的码字。该码字的运算，不的码字。该码字的运算，不的码字。该码字的运算，不的码字。该码字的运算，不仅与本段仅与本段仅与本段仅与本段k k k k0 0 0 0位信息有关，还与其前面位信息有关，还与其前面位信息有关，还与其前面位信息有关，还与其前面m m m m组组组组k k k k0 0 0 0位信息有位信息有位信息有位信息有关。称这种码为（关。称这种码为（关。称这种码为（关。称这种码为（n n n n0 0 0 0，k k k k0 0 0 0，m m m m）卷积码。）卷积码。）卷积码。）卷积码。7/13/202424纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.4 信道编码的分类信道编码的分类p按信息码元在编码后是否保持原来的形式：按信息码元在编码后是否保持原来的形式：n系统码、非系统码系统码、非系统码系统码、非系统码系统码、非系统码p按纠正错误的类型：按纠正错误的类型：n纠正随机错误的码、纠正突发错误的码纠正随机错误的码、纠正突发错误的码纠正随机错误的码、纠正突发错误的码纠正随机错误的码、纠正突发错误的码p按每个码元取值：按每个码元取值：n二进制码、多进制码二进制码、多进制码二进制码、多进制码二进制码、多进制码7/13/202425纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章分组码的定义分组码是对每段分组码是对每段k位长的信息组，以一定规则增加位长的信息组，以一定规则增加r=n-k个校验元，组成长为个校验元，组成长为n的序列：的序列：（cn-1，cn-2，.，c2，c1）,称这个序列为称这个序列为码字码字（码组、码矢）（码组、码矢）。在二进制情况下，信息组总共。在二进制情况下，信息组总共有有2k个，因此通过编码器后，相应的码字也有个，因此通过编码器后，相应的码字也有2k个，称这个个，称这个2k个码字集合为个码字集合为（n，k）分组码）分组码。7/13/202426纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章分组码将分组码将k k个比特编成个比特编成n n个比特的码字个比特的码字（Code wordsCode wordsCode wordsCode words）通通常记分组码为（常记分组码为（n n，k k）码。（）码。（n n，k k）码中有）码中有2 2k k个码字。个码字。p（n n，k k）码中有）码中有2 2k k个个n n重码字。但是重码字。但是n bitn bit的二进制序列具有的二进制序列具有2 2n n种不同的组合序列；种不同的组合序列；p分组码的编码规则就是从分组码的编码规则就是从2 2n n种不同序列中种不同序列中选择选择2 2k k个码字，建立信息序列与码字的对个码字，建立信息序列与码字的对应关系；应关系；分组码的定义7/13/202427纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章n许用码组、禁用码组许用码组、禁用码组这这2 2k k个码字组成的集合称为许用码组，个码字组成的集合称为许用码组，剩余的剩余的2 2n n-2-2k k个个n n重向量组成的集合称为禁重向量组成的集合称为禁用码组。用码组。n码重码重:码字中非码字中非0 0码元的个数，又称码元的个数，又称汉明重汉明重量量。如码字。如码字x=(11000)x=(11000)，则码重，则码重w(x)=2w(x)=2n码距码距:码字码字码字码字x x x x与码字与码字与码字与码字y y y y对应位取值不同的个数，又称为汉明对应位取值不同的个数，又称为汉明对应位取值不同的个数，又称为汉明对应位取值不同的个数，又称为汉明距离。距离。距离。距离。n n例如例如例如例如:x=(10111101),:x=(10111101),:x=(10111101),:x=(10111101),y=(01110101)y=(01110101)y=(01110101)y=(01110101)，则码距，则码距，则码距，则码距d(x,y)=3d(x,y)=3d(x,y)=3d(x,y)=3分组码的定义7/13/202428纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.5 最大后验与最大似然译码最大后验与最大似然译码信源信源编码编码信道信道译码译码信宿信宿mcrm根据编码规则，在信息根据编码规则，在信息根据编码规则，在信息根据编码规则，在信息序列基础上增加监督码序列基础上增加监督码序列基础上增加监督码序列基础上增加监督码元，生成码字元，生成码字元，生成码字元，生成码字根据一套译码规则，由接收序列根据一套译码规则，由接收序列根据一套译码规则，由接收序列根据一套译码规则，由接收序列 r r r r 给出与发送序列给出与发送序列给出与发送序列给出与发送序列m m m m最接近最接近最接近最接近（最好是相同）的估值序列（最好是相同）的估值序列（最好是相同）的估值序列（最好是相同）的估值序列mmmm已知条件：已知条件：已知条件：已知条件：1 1 1 1）实际接收的码字）实际接收的码字）实际接收的码字）实际接收的码字r r r r（必要条件）（必要条件）（必要条件）（必要条件）2 2 2 2）发送端采用的编码算法和产生的码集）发送端采用的编码算法和产生的码集）发送端采用的编码算法和产生的码集）发送端采用的编码算法和产生的码集X X X Xn n n n（必要条件）（必要条件）（必要条件）（必要条件）3 3 3 3）信道模型和信道参数）信道模型和信道参数）信道模型和信道参数）信道模型和信道参数7/13/202429纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.5 最大后验与最大似然译码最大后验与最大似然译码p编码：编码：m=c m=cp译码：译码：r=c=m r=c=mp由于信息序列与码字之间存在一一对应关由于信息序列与码字之间存在一一对应关系，所以等价于译码器根据系，所以等价于译码器根据r r产生一个产生一个c c的的估值序列估值序列cc。显然当且仅当。显然当且仅当c=cc=c时，时，m=mm=m，此时译码器正确译码。，此时译码器正确译码。信源信源编码编码信道信道译码译码信宿信宿mcrmc7/13/202430纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.5 最大后验与最大似然译码最大后验与最大似然译码p最大后验译码最大后验译码最大后验译码最大后验译码(Maximum APosteriori,MAP)(Maximum APosteriori,MAP)(Maximum APosteriori,MAP)(Maximum APosteriori,MAP)对于给定接收序列对于给定接收序列对于给定接收序列对于给定接收序列r r r r，译码器的条件译码错误概率，译码器的条件译码错误概率，译码器的条件译码错误概率，译码器的条件译码错误概率为：为：为：为：译码错误概率最小，有译码错误概率最小，有译码错误概率最小，有译码错误概率最小，有对于输入对于输入对于输入对于输入r r r r，译码器在，译码器在，译码器在，译码器在2 2 2 2k k k k个码字中选择一个使个码字中选择一个使个码字中选择一个使个码字中选择一个使P(cP(cP(cP(c*/r)/r)/r)/r)最大的码字最大的码字最大的码字最大的码字c c c c*作为作为作为作为c c c c的估值序列的估值序列的估值序列的估值序列cccc，会使，会使，会使，会使译码输出错误概率最小，这种译码准则为最大后译码输出错误概率最小，这种译码准则为最大后译码输出错误概率最小，这种译码准则为最大后译码输出错误概率最小，这种译码准则为最大后验译码。验译码。验译码。验译码。7/13/202431纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.5 最大后验与最大似然译码最大后验与最大似然译码p最大后验译码最大后验译码(Maximum APosteriori,(Maximum APosteriori,MAP)MAP)n最优的译码算法，所以也称最佳译码最优的译码算法，所以也称最佳译码n但是实际译码时，定量地找出后验概率值但是实际译码时，定量地找出后验概率值很困难很困难n通常情况下，可以知道信道的前向（发通常情况下，可以知道信道的前向（发-收）转移概率，比如收）转移概率，比如BSCBSC信道模型中的信道模型中的p p7/13/202432纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.1.如果发送端发送每个码字的概率相同，最大似然如果发送端发送每个码字的概率相同，最大似然如果发送端发送每个码字的概率相同，最大似然如果发送端发送每个码字的概率相同，最大似然译码等价于最大后验译码。译码等价于最大后验译码。译码等价于最大后验译码。译码等价于最大后验译码。2.2.译码器对于输入译码器对于输入译码器对于输入译码器对于输入r r，在，在，在，在2 2k k个码字中选择一个使似然个码字中选择一个使似然个码字中选择一个使似然个码字中选择一个使似然概率概率概率概率 最大的码字最大的码字最大的码字最大的码字c*c*作为作为作为作为c c的估值序列的估值序列的估值序列的估值序列cc。1.5 最大后验与最大似然译码最大后验与最大似然译码p最大似然译码最大似然译码最大似然译码最大似然译码 (Maximum Likelihood Decoding,MLD)(Maximum Likelihood Decoding,MLD)由贝叶斯公式，由贝叶斯公式，由贝叶斯公式，由贝叶斯公式，若发送端发送每个码字的概率若发送端发送每个码字的概率若发送端发送每个码字的概率若发送端发送每个码字的概率P(c*)P(c*)均相同，且由于均相同，且由于均相同，且由于均相同，且由于P(r)P(r)与译码方法无关，所以与译码方法无关，所以与译码方法无关，所以与译码方法无关，所以 7/13/202433纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.5 最大后验与最大似然译码最大后验与最大似然译码p最大似然译码最大似然译码最大似然译码最大似然译码(MLD)(MLD)对于无记忆信道，码字的似然函数等于组成码字对于无记忆信道，码字的似然函数等于组成码字对于无记忆信道，码字的似然函数等于组成码字对于无记忆信道，码字的似然函数等于组成码字的各码元的似然函数之积，即若的各码元的似然函数之积，即若的各码元的似然函数之积，即若的各码元的似然函数之积，即若r=(rr=(r1 1,r,r2 2,r rn n),c=(c),c=(c1 1,c,c2 2,c,cn n)码字最大似然函数也就是各码元似然函数之积的码字最大似然函数也就是各码元似然函数之积的码字最大似然函数也就是各码元似然函数之积的码字最大似然函数也就是各码元似然函数之积的最大化最大化最大化最大化 7/13/202434纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.6 纠错码的基本概念纠错码的基本概念p性能指标性能指标p香农信道编码定理香农信道编码定理p分组码的检纠错能力分组码的检纠错能力7/13/202435纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p性能指标性能指标n编码效率编码效率 分组码分组码（n n n n，k k k k），），），），R R表明了信息元在码字中所表明了信息元在码字中所占的比重，是衡量编码有效性的基本参数。占的比重，是衡量编码有效性的基本参数。n-kn-k监督位，监督位越多，纠错能力越强，监督位，监督位越多，纠错能力越强，效率越低。效率越低。n n越大，编、译码延时越大。越大，编、译码延时越大。1.6 纠错码的基本概念纠错码的基本概念7/13/202436纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p性能指标性能指标p香农信道编码定理香农信道编码定理p分组码的检纠错能力分组码的检纠错能力1.6 纠错码的基本概念纠错码的基本概念7/13/202437纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p香农信道编码定理香农信道编码定理 对于一个给定的有扰信道，若信道的容对于一个给定的有扰信道，若信道的容量为量为C C，只要发送端以低于，只要发送端以低于C C的速率发送信的速率发送信息，则一定存在一种编码方法，使译码错息，则一定存在一种编码方法，使译码错误概率误概率P P随着码长随着码长n n的增加，按指数下降到的增加，按指数下降到任意小的值，表示为任意小的值，表示为 这里这里E(R)E(R)称为误差指数。称为误差指数。1.6 纠错码的基本概念纠错码的基本概念7/13/202438纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章定理说明：定理说明：p当信息速率小于信道容量时，总存在一种当信息速率小于信道容量时，总存在一种编码方式使差错率低于任一给定值编码方式使差错率低于任一给定值；p为减小差错概率，可增大码长为减小差错概率，可增大码长n n或增大或增大E(R)E(R)。1.6 纠错码的基本概念纠错码的基本概念7/13/202439纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p性能指标性能指标p香农信道编码定理香农信道编码定理p分组码的检纠错能力分组码的检纠错能力1.6 纠错码的基本概念纠错码的基本概念7/13/202440纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n最小码距最小码距:(n,k)(n,k)分组码中，任何两个不同码分组码中，任何两个不同码字之间距离的最小值，称为该分组码的最小汉字之间距离的最小值，称为该分组码的最小汉明距离，简称最小距离，用明距离，简称最小距离，用d d0 0表示。最小码距表示。最小码距决定了码的纠错、检错性能。决定了码的纠错、检错性能。n最小汉明距离译码准则最小汉明距离译码准则:在许用码组中，判断在许用码组中，判断与接收序列与接收序列r“r“最近最近”的码字为发送码字。的码字为发送码字。1.6 纠错码的基本概念纠错码的基本概念7/13/202441纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n检错能力：一个检错能力：一个(n,k)(n,k)分组码，如果能检分组码，如果能检出一个码字内的所有小于或等于出一个码字内的所有小于或等于e e 个个(位位)错误，则称该码的检错能力为错误，则称该码的检错能力为e en纠错能力：一个纠错能力：一个(n,k)(n,k)分组码，如果能纠分组码，如果能纠正一个码字内的所有小于或等于正一个码字内的所有小于或等于t t个个(位位)错误，则称该码的纠错能力为错误，则称该码的纠错能力为t t1.6 纠错码的基本概念纠错码的基本概念7/13/202442纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n同时纠检错能力：一个同时纠检错能力：一个(n,k)(n,k)分组码，如分组码，如果能纠正一个码字内的所有小于或等于果能纠正一个码字内的所有小于或等于t t个个(位位)错误，同时又能检出所有小于或等错误，同时又能检出所有小于或等于于e(e t)e(e t)个个(位位)错误，则称该码的同时错误，则称该码的同时纠检错能力为纠纠检错能力为纠t t个错同时检个错同时检e e个错个错1.6 纠错码的基本概念纠错码的基本概念7/13/202443纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n为了检测为了检测为了检测为了检测e e e e个错误，要求分组码的最小码距个错误，要求分组码的最小码距个错误，要求分组码的最小码距个错误，要求分组码的最小码距d d d d0 0 0 0e+1e+1e+1e+11.6 纠错码的基本概念纠错码的基本概念7/13/202444纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n为了为了为了为了纠正纠正纠正纠正t t t t个个个个错误，要求分组码的最小码距错误，要求分组码的最小码距错误，要求分组码的最小码距错误，要求分组码的最小码距d d d d0 0 0 02t+12t+12t+12t+11.6 纠错码的基本概念纠错码的基本概念7/13/202445纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n为了纠正为了纠正为了纠正为了纠正t t t t个错误，同时检测个错误，同时检测个错误，同时检测个错误，同时检测e e e e个错误个错误个错误个错误(e=t)(e=t)(e=t)(e=t)，要求最小码距要求最小码距要求最小码距要求最小码距 d d d d0 0 0 0e+t+1e+t+1e+t+1e+t+11.6 纠错码的基本概念纠错码的基本概念7/13/202446纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n由此定理可知，一个距离为由此定理可知，一个距离为d d的分组码，的分组码，（1 1）至多能纠正）至多能纠正t t(d(d0 0-1)-1)2 2(x x是是x x的整数部分的整数部分)个错误。个错误。（2 2）至多能发现）至多能发现e e（d d0 0-1-1）个错误。）个错误。1.6 纠错码的基本概念纠错码的基本概念7/13/202447纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力nd d0 0是分组码的一个重要参数，它表明了分是分组码的一个重要参数，它表明了分组码抗干扰能力的大小。设计码时，要同组码抗干扰能力的大小。设计码时，要同时考虑时考虑d d0 0和和R Rn举例举例 重复码重复码（校验元是信息元的重复，错误（校验元是信息元的重复，错误（校验元是信息元的重复，错误（校验元是信息元的重复，错误概率概率概率概率P P P P）(2,1)码：码：d0=2,R=1/2，能检，能检1个错，若与个错，若与ARQ结合，译码错误概率为结合，译码错误概率为p2；不能纠错；不能纠错；1.6 纠错码的基本概念纠错码的基本概念7/13/202448纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p分组码的检纠错能力分组码的检纠错能力n举例举例 重复码（校验元是信息元的重复，重复码（校验元是信息元的重复，错误概率错误概率P P）(3,1)码：码：d0=3,R=1/3，（1）若仅用来检错，能检若仅用来检错，能检2个错个错；（2）能够纠能够纠1个错个错。1.6 纠错码的基本概念纠错码的基本概念7/13/202449纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章p举例2 重复码（校验元是信息元的重复）(4,1)(4,1)码：码：d d0 0=4,R=1/4=4,R=1/4，若仅用来检错，能检若仅用来检错，能检3 3个错；个错；若同时纠检错，则能纠若同时纠检错，则能纠1 1个错同时检个错同时检2 2个错个错 编码的任务：编码的任务：构造出构造出R R一定、一定、d d0 0尽可能大的码，尽可能大的码，或者或者d d0 0一定、一定、R R尽可能大的码尽可能大的码1.6 纠错码的基本概念纠错码的基本概念7/13/202450纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.7 几种常用的编码方式几种常用的编码方式p奇偶校验码奇偶校验码p群计数码群计数码p恒比码（等重码）恒比码（等重码）7/13/202451纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.7 几种常用的编码方式几种常用的编码方式p奇偶校验码奇偶校验码n偶校验码：加入监督位后，码字中偶校验码：加入监督位后，码字中“1”“1”的个数为偶数个，即所有位的模二和为的个数为偶数个，即所有位的模二和为0 0。（即偶数个（即偶数个1 1）n奇校验码：加入监督位后码字中奇校验码：加入监督位后码字中“1”“1”的的个数为奇数个，即所有位的模二和为个数为奇数个，即所有位的模二和为1 1。（即奇数个（即奇数个1 1）n这是一种最简单的检错码，在计算机数这是一种最简单的检错码，在计算机数据传输中得到广泛应用。据传输中得到广泛应用。7/13/202452纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.7 几种常用的编码方式几种常用的编码方式p群计数码群计数码n将码字中将码字中将码字中将码字中“1”“1”“1”“1”的计数值作为监督码的计数值作为监督码的计数值作为监督码的计数值作为监督码例如，信息组为例如，信息组为例如，信息组为例如，信息组为01011010110101101011，共，共，共，共3 3 3 3个个个个1 1 1 1，用，用，用，用011011011011表示，得到表示，得到表示，得到表示，得到(8,5)(8,5)(8,5)(8,5)码。群计数码的码字为码。群计数码的码字为码。群计数码的码字为码。群计数码的码字为01011011010110110101101101011011n检错能力很强，除了检错能力很强，除了检错能力很强，除了检错能力很强，除了0 0 0 0错成错成错成错成1 1 1 1和和和和1 1 1 1错成错成错成错成0 0 0 0成对发生成对发生成对发生成对发生的情况外，其它形式的错误都能发现。的情况外，其它形式的错误都能发现。的情况外，其它形式的错误都能发现。的情况外，其它形式的错误都能发现。n为了降低发送码元中的冗余度，有时只传送计为了降低发送码元中的冗余度，有时只传送计为了降低发送码元中的冗余度，有时只传送计为了降低发送码元中的冗余度，有时只传送计数码元中最后几位。特别的只传输最后数码元中最后几位。特别的只传输最后数码元中最后几位。特别的只传输最后数码元中最后几位。特别的只传输最后1 1 1 1位监督位监督位监督位监督元，则群计数码变成奇偶校验码元，则群计数码变成奇偶校验码元，则群计数码变成奇偶校验码元，则群计数码变成奇偶校验码7/13/202453纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.7 几种常用的编码方式几种常用的编码方式p恒比码恒比码n码字中码字中“1”“1”和和“0”“0”的个数保持相同的的个数保持相同的比例，即每个码字中比例，即每个码字中1 1的个数相同。的个数相同。n恒比码的译码可以采用查表方法，检错恒比码的译码可以采用查表方法，检错时查时查1 1或或0 0的个数。的个数。n恒比码是一种检错码。恒比码是一种检错码。n恒比码一般用在电报恒比码一般用在电报7/13/202454纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1.7 几种常用的编码方式几种常用的编码方式p恒比码恒比码n例：我国电传机传输汉字时每个汉字用例：我国电传机传输汉字时每个汉字用4 4位阿拉伯数字位阿拉伯数字表示，每个阿拉伯数字用表示，每个阿拉伯数字用5 5个比特的码字表示。由于阿个比特的码字表示。由于阿拉伯数字只有拉伯数字只有1010个，因此从个，因此从3232中可能的码字中挑出中可能的码字中挑出 =10=10个个1 1的个数为的个数为3 3的码字作为阿拉伯数字的编码方式。的码字作为阿拉伯数字的编码方式。阿拉伯数字阿拉伯数字编码阿拉伯数字阿拉伯数字编码1010116101012110017111003101108011104110109100115001110011017/13/202455纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章作业作业1.1.描述基本的点对点通信系统模型描述基本的点对点通信系统模型2.2.描述信道编码的作用、基本思想和编码系统描述信道编码的作用、基本思想和编码系统模型。模型。3.3.发送端发送的码字为（发送端发送的码字为（100100100100），经信道传），经信道传输后，接收端接收到的信息序列为输后，接收端接收到的信息序列为（000101000101），求错误图样。），求错误图样。4.4.简要介绍几种差错控制方式。简要介绍几种差错控制方式。5.5.若一分组码最小距离为若一分组码最小距离为d d0 08 8，判断该码检，判断该码检错能力、纠错能力。错能力、纠错能力。7/13/202456纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章1、描述基本的点对点通信系统模型描述基本的点对点通信系统模型描述基本的点对点通信系统模型描述基本的点对点通信系统模型7/13/202457纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章2、描述信道编码的作用、基本思想和编码系统模型。描述信道编码的作用、基本思想和编码系统模型。描述信道编码的作用、基本思想和编码系统模型。描述信道编码的作用、基本思想和编码系统模型。答：作用：提高通信的可靠性。答：作用：提高通信的可靠性。答：作用：提高通信的可靠性。答：作用：提高通信的可靠性。基本思想：基本思想：基本思想：基本思想：利用冗余降低差错概率。利用冗余降低差错概率。利用冗余降低差错概率。利用冗余降低差错概率。系统模型：系统模型：系统模型：系统模型：7/13/202458纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章3 3 3 3、发送端发送的码字为（发送端发送的码字为（发送端发送的码字为（发送端发送的码字为（100100100100100100100100），经信道传输后，），经信道传输后，），经信道传输后，），经信道传输后，接收端接收到的信息序列为（接收端接收到的信息序列为（接收端接收到的信息序列为（接收端接收到的信息序列为（000101000101000101000101），求错误），求错误），求错误），求错误图样。图样。图样。图样。答：答：答：答：100100100100100100100100+000101000101000101000101=1000011000011000011000017/13/202459纠错编码技术纠错编码技术 纠错码的基本概念纠错码的基本概念 第一章第一章5 5 5 5、若一分组码最小距离为若一分组码最小距离为若一分组码最小距离为若一分组码最小距离为d d d d0 0 0 08 8 8 8，判断该码检错能，判断该码检错能，判断该码检错能，判断该码检错能力、纠错能力。力、纠错能力。力、纠错能力。力、纠错能力。解：解：解：解：（1 1 1 1）检测检测检测检测7 7 7 7个错误个错误个错误个错误（2 2 2 2）纠正）纠正）纠正）纠正3 3 3 3个错误个错误个错误个错误（3 3 3 3）检测检测检测检测6 6 6 6个错误个错误个错误个错误同时同时同时同时纠正纠正纠正纠正1 1 1 1个错误个错误个错误个错误（4 4 4 4）检测检测检测检测5 5 5 5个错误个错误个错误个错误同时同时同时同时纠正纠正纠正纠正2 2 2 2个错误个错误个错误个错误（5 5 5 5）检测检测检测检测4 4 4 4个错误个错误个错误个错误同时同时同时同时纠正纠正纠正纠正3 3 3 3个错误个错误个错误个错误7/13/202460纠错编码技术纠错编码技术