译码方法最大后验概率译码课件

信道编码信道编码信道编码信道编码 第第6 6章章1信道编码 第6章1信源编码信源编码提高数字信号提高数字信号有效性有效性有效性有效性将信源的模拟信号转变为数字信号将信源的模拟信号转变为数字信号降低冗余度降低冗余度,提高符号的平均信息量；提高符号的平均信息量；信道编码信道编码提高数字通信提高数字通信提高数字通信提高数字通信可靠性可靠性可靠性可靠性 数字信号在信道的传输过程中数字信号在信道的传输过程中数字信号在信道的传输过程中数字信号在信道的传输过程中,由于实际由于实际由于实际由于实际信道信道信道信道的的的的 传输特性不理想传输特性不理想传输特性不理想传输特性不理想以及存在加性以及存在加性以及存在加性以及存在加性噪声噪声噪声噪声,在接收端往在接收端往在接收端往在接收端往 往会产生往会产生往会产生往会产生误码误码误码误码。2信源编码21 1、基本概念基本概念基本概念基本概念差错率及其分类差错率及其分类差错图样及其分类差错图样及其分类纠错码分类纠错码分类差错控制系统分类差错控制系统分类2 2 2 2、检错与纠错的原理、检错与纠错的原理、检错与纠错的原理、检错与纠错的原理3 3 3 3、码距与检错、纠错能力、码距与检错、纠错能力、码距与检错、纠错能力、码距与检错、纠错能力4 4 4 4、译码方法、译码方法、译码方法、译码方法内容内容31、基本概念内容3差错率及其分类差错率及其分类差错率差错率是衡量传输质量的重要指标之一是衡量传输质量的重要指标之一,它有它有几种不同的定义。几种不同的定义。码元差错率码元差错率/符号差错率（符号差错率（P Pe e）指在传输的指在传输的码元码元总数中发生差错的码元数总数中发生差错的码元数 所占的比例所占的比例,简称简称误码率误码率。是指是指信号信号差错概率差错概率 4差错率及其分类差错率是衡量传输质量的重要指标之一,它有几种不 比特差错率比特差错率/比特误码率（比特误码率（P Pb b）在传输的比特总数中发生差错的比在传输的比特总数中发生差错的比 特数所占比例特数所占比例是指信息差错概率是指信息差错概率 对二进制传输系统对二进制传输系统,符号差错等效于比符号差错等效于比 特差错特差错;差错率及其分类差错率及其分类5 比特差错率/比特误码率（Pb）差错率及其分类5差错图样差错图样为定量地描述信号的差错为定量地描述信号的差错,定义定义差错图样差错图样E E E=CR (模M)最常用的二进制码可当作特例来研究最常用的二进制码可当作特例来研究,其差错图其差错图 样等于收码与发码的异或样等于收码与发码的异或,即即 E=CR 或 C=RE设发送的码字设发送的码字C C 1 1 1 1 1 1 1 1 1 1 接收的码字接收的码字R R 1 0 0 1 0 0 1 1 1 1 差错的图样差错的图样E E 0 1 1 0 1 1 0 0 0 0 差错图样中的差错图样中的“1”“1”既是符号差错也是比特差错既是符号差错也是比特差错,差错的个数叫差错的个数叫汉明距离汉明距离。0:0:传输中无错传输中无错1:1:传输中有错传输中有错 6差错图样为定量地描述信号的差错,定义差错图样E0:传输中无错差错图样类型差错图样类型随机差错随机差错：差错是差错是相互独立相互独立的的,不相关不相关存在这种差错的信道是无记忆信道或随机存在这种差错的信道是无记忆信道或随机 信道信道突发差错突发差错：前后相关、成堆出现的差错前后相关、成堆出现的差错已差错码元开头、已差错码元结尾；已差错码元开头、已差错码元结尾；E:0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 突发长度突发长度=4=4突发长度突发长度=6=67差错图样类型随机差错：突发长度=4突发长度=67纠错码分类纠错码分类 从功能角度讲从功能角度讲,差错码分为差错码分为检错码检错码和和纠错码纠错码检错码检错码：用于发现差错：用于发现差错纠错码纠错码：能自动纠正差错：能自动纠正差错纠错码与检错码在理论上没有本质区别纠错码与检错码在理论上没有本质区别,只是应只是应用场合不同用场合不同,而侧重的性能参数也不同。而侧重的性能参数也不同。8纠错码分类 从功能角度讲,差错码分为检错码和纠错码8纠错码分类纠错码分类 按照对信息序列的处理方法按照对信息序列的处理方法,有有分组码分组码和和卷积码卷积码分组码：分组码：分组码：分组码：将将k k个信息码元分成一组个信息码元分成一组,由这由这k k个码元按照一个码元按照一 定规则产生定规则产生r r个监督码元个监督码元,组成长度组成长度n=k+rn=k+r的码的码 字字 卷积码：卷积码：卷积码：卷积码：先将信息序列分组先将信息序列分组,不同的是编译码运算不仅不同的是编译码运算不仅 与本组信息有关与本组信息有关,而且还与而且还与前面若干组有关前面若干组有关。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr9纠错码分类 按照对信息序列的处理方法,有分组码和卷积码卷积码纠错码分类纠错码分类编码效率编码效率：一个组中信息所占的比重一个组中信息所占的比重k k：信息码元的数目：信息码元的数目n n：编码组码元的总数目：编码组码元的总数目n=k+rn=k+rr r：监督码元的数目：监督码元的数目10纠错码分类编码效率：k：信息码元的数目10纠错码分类纠错码分类 按照码元与原始信息位的关系按照码元与原始信息位的关系,分为分为线性码线性码：所有码元均是原始信息元的：所有码元均是原始信息元的线性组线性组 合合,编码器不带反馈回路。编码器不带反馈回路。非线性码非线性码：码元并不都是信息元的线性组合：码元并不都是信息元的线性组合,可能还与前面已编的码元有关可能还与前面已编的码元有关,编码器可能含反馈回路。编码器可能含反馈回路。11纠错码分类 按照码元与原始信息位的关系,分为11纠错码分类纠错码分类 按照适用的差错类型按照适用的差错类型,分成分成:纠随机差错码纠随机差错码:用于随机差错信道用于随机差错信道,其纠错能其纠错能 力用码组内允许的独立差错力用码组内允许的独立差错 的个数来衡量。的个数来衡量。纠突发差错码纠突发差错码:针对突发差错而设计针对突发差错而设计,其纠错其纠错 能力主要用可纠突发差错的能力主要用可纠突发差错的 最大长度来衡量。最大长度来衡量。12纠错码分类 按照适用的差错类型,分成:12差错控制系统分类差错控制系统分类 前向纠错前向纠错(FEC)(FEC)：发送端的信息经过信道编码器将信息编成具发送端的信息经过信道编码器将信息编成具 有一定有一定纠错能力纠错能力的码字。的码字。接收端信道译码器对接收码字进行译码接收端信道译码器对接收码字进行译码,若若 传输中产生的差错数目在码的纠错能力之内传输中产生的差错数目在码的纠错能力之内 时时,译码器对差错进行定位并加以纠正。译码器对差错进行定位并加以纠正。13差错控制系统分类 前向纠错(FEC)：13差错控制系统分类差错控制系统分类前向纠错前向纠错(FEC)(FEC)：优点：优点：不存在反向信道、时延小、实时性好；不存在反向信道、时延小、实时性好；缺点：缺点：前向纠错的能力是有限的，当传递过程前向纠错的能力是有限的，当传递过程 中出现的差错码字的个数超出纠错的能中出现的差错码字的个数超出纠错的能 力时，只能译出错误的信息；力时，只能译出错误的信息；14差错控制系统分类前向纠错(FEC)：14差错控制系统分类差错控制系统分类 自动请求重发自动请求重发自动请求重发自动请求重发(ARQ)(ARQ)(ARQ)(ARQ)或反馈重发：或反馈重发：或反馈重发：或反馈重发：发送消息经过检错编码后得到有发送消息经过检错编码后得到有检错功能的检错功能的 码字；码字；译码器译码器检查判断检查判断当前码字是否传输正确；当前码字是否传输正确；当有错时按某种协议通过一个当有错时按某种协议通过一个反向信道反向信道请求请求 发送端重传已发送的码字发送端重传已发送的码字(全部或部分全部或部分)。15差错控制系统分类 自动请求重发(ARQ)或反馈重发：15差错控制系统分类差错控制系统分类 混合纠错混合纠错(HEC)(HEC)：是是前向纠错前向纠错与与反馈重发反馈重发方式的结合。方式的结合。信息经过发送端编码后同时具有信息经过发送端编码后同时具有自动检测自动检测和和 纠错纠错能力的码字能力的码字,接收端收到码字后接收端收到码字后,检查差检查差 错情况错情况,如果差错在码的纠错能力以内如果差错在码的纠错能力以内,则则自自 动进行纠正动进行纠正。如果信道干扰很严重如果信道干扰很严重,错误很多错误很多,超过了码的超过了码的 纠错能力纠错能力,但能检测出来但能检测出来,则经则经反馈信道请求反馈信道请求 发端重发这组数据发端重发这组数据。16差错控制系统分类 混合纠错(HEC)：16检错与纠错原理检错与纠错原理 0 0:晴晴,1 1:雨雨若若10,0110,01；接收端无法发现错误；接收端无法发现错误00晴晴1001110011雨雨能发现能发现一个一个错误错误禁用码组禁用码组插入插入1 1位监督码位监督码后具有后具有检出检出1 1位错码位错码的能的能 力力,但不能予以纠正。但不能予以纠正。17检错与纠错原理 0:晴,1:雨00晴1001110011雨能检错与纠错原理检错与纠错原理 000晴晴010001111000111雨雨晴晴在只有在只有1 1位错码位错码的情况下的情况下,可以判决哪位是错可以判决哪位是错 码并予以码并予以纠正纠正,可以可以检出检出2 2位位或或2 2位以下位以下的错码。的错码。100011101110雨雨18检错与纠错原理 000晴010001111000111雨晴在检错与纠错原理检错与纠错原理接收端接收到码字后与定义的许用码接收端接收到码字后与定义的许用码字作对比，找与它字作对比，找与它差别最小差别最小的的许用码许用码字字；并且认为这个许用码字就是它所对应并且认为这个许用码字就是它所对应的的发送码字发送码字,从而在码字的纠错能力内从而在码字的纠错能力内实现实现自动纠错自动纠错。19检错与纠错原理接收端接收到码字后与定义的许用码字作对比，找与检错与纠错原理检错与纠错原理纠错编码之所以具有检错、纠错能力纠错编码之所以具有检错、纠错能力,是因是因 为在信息码元之外加入了为在信息码元之外加入了监督码监督码。监督码不。监督码不 载信息载信息,只是用来监督信息码在传输中有无只是用来监督信息码在传输中有无 差错。差错。纠错编码所提高的可靠性纠错编码所提高的可靠性,是以牺牲信道利是以牺牲信道利 用率为代价换取的。用率为代价换取的。监督码监督码引入引入越多越多,检错、纠错检错、纠错能力能力越强越强,但信但信 道的传输效率下降也越快。道的传输效率下降也越快。20检错与纠错原理纠错编码之所以具有检错、纠错能力,是因20码距与检错、纠错能力码距与检错、纠错能力汉明距离：汉明距离：二个码字对应位置码元不同的个数。二个码字对应位置码元不同的个数。最小码距最小码距d dminmin：一个码字的集合中任意二个码字间的一个码字的集合中任意二个码字间的最小汉明距离。最小汉明距离。码重码重W W：码字中非码字中非0 0的数目。的数目。21码距与检错、纠错能力汉明距离：21码距与检错、纠错能力码距与检错、纠错能力定理：若纠错码的最小距离为定理：若纠错码的最小距离为d dminmin，可以检测出任意小于等于可以检测出任意小于等于l=dl=dminmin-1-1个差错个差错 可以纠正任意小于等于可以纠正任意小于等于 个差错个差错 纠错编码的纠错编码的检错纠错能力检错纠错能力,要取决于码组的要取决于码组的码距码距 码距越大码距越大,检错、纠错能力越强。检错、纠错能力越强。22码距与检错、纠错能力定理：若纠错码的最小距离为dmin，纠译码方法译码方法最大后验概率译码（最佳译码）：最大后验概率译码（最佳译码）：最大后验概率译码（最佳译码）：最大后验概率译码（最佳译码）：译码器接收到码字译码器接收到码字R R之后，根据之后，根据后验概率后验概率找找 出可能性最大的出可能性最大的发码发码C Ci i作为译码估值，从而作为译码估值，从而 还原信源信息；还原信源信息；消息组消息组mi 码字码字ci 接收码接收码R 估值估值 消息消息 编码器编码器 信道信道 译码器译码器 消息还原消息还原23译码方法最大后验概率译码（最佳译码）：消息组mi 译码方法译码方法根据贝叶斯原理根据贝叶斯原理:如果构成码集的码字以相同概率发送，满足如果构成码集的码字以相同概率发送，满足P(cP(ci i)是是 等概率出现的等概率出现的；同时同时P(R)P(R)对于任何对于任何R R都有相同的值，即都有相同的值，即等概率出现等概率出现的的则最大的后验概率则最大的后验概率P(Ci/R)P(Ci/R)等效于等效于最大的先验概率最大的先验概率 P(R/Ci)P(R/Ci)，在此前提下，在此前提下最佳译码等效于最大似然译码最佳译码等效于最大似然译码最佳译码等效于最大似然译码最佳译码等效于最大似然译码。24译码方法根据贝叶斯原理:如果构成码集的码字以相同概率发送，满设每个码字长为设每个码字长为n n，若接收码字，若接收码字R R与码字与码字C C的汉明的汉明 距离为距离为d(R,C)d(R,C)，则条件概率，则条件概率p(RC)可表示为：可表示为：最大的最大的最大的最大的p(RC)p(RC)p(RC)p(RC)等价于最小的汉明距离等价于最小的汉明距离等价于最小的汉明距离等价于最小的汉明距离d(R,C)d(R,C)d(R,C)d(R,C)，所，所以需要找到与接收码字以需要找到与接收码字R R汉明距离最小的输出码字汉明距离最小的输出码字 CC作为译码作为译码。BSCBSC信道的最大似然译码信道的最大似然译码25设每个码字长为n，若接收码字R与码字C的汉明BSC信道的最大