信息论与编码纠错第7章.pptx
《信息论与编码纠错第7章.pptx》由会员分享,可在线阅读,更多相关《信息论与编码纠错第7章.pptx(59页珍藏版)》请在咨信网上搜索。
1、信息论与编码信息论与编码内容提要内容提要 目前,几乎所有得到实际应用的纠错码都是线性的。本目前,几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念,然后重点论述线性分组章首先介绍有关纠错码的基本概念,然后重点论述线性分组码的定义及其编译码理论。在此基础上,介绍了一种典型的码的定义及其编译码理论。在此基础上,介绍了一种典型的线性分组码:汉明码。线性分组码:汉明码。掌握内容:线性分组码的概念,生成矩阵,校验矩阵,掌握内容:线性分组码的概念,生成矩阵,校验矩阵,最小距离,伴随式,标准阵列等。最小距离,伴随式,标准阵列等。信息论与编码信息论与编码7.1 7.1 7.1 7.1 纠
2、错编码的基本概念纠错编码的基本概念纠错编码的基本概念纠错编码的基本概念一信道纠错编码一信道纠错编码一信道纠错编码一信道纠错编码 近年来,随着计算机、卫星通信及高速数据网的飞速发展,数据的交近年来,随着计算机、卫星通信及高速数据网的飞速发展,数据的交换、处理和存储技术得到了广泛的应用,人们对数据传输和存储系统的可换、处理和存储技术得到了广泛的应用,人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此,如何控制差错、提高数据传输和存储靠性提出了越来越高的要求。因此,如何控制差错、提高数据传输和存储的可靠性,成为现代数字通信系统设计工作者面临的重要课题。的可靠性,成为现代数字通信系统设计工作者
3、面临的重要课题。香农第二定理指出,当信息传输速率低于信道容量时,通过某种编译香农第二定理指出,当信息传输速率低于信道容量时,通过某种编译码方法,就能使错误概率为任意小。目前已有了许多有效的编译码方法,码方法,就能使错误概率为任意小。目前已有了许多有效的编译码方法,并形成了一门新的技术并形成了一门新的技术纠错编码技术。纠错编码技术。这里所讲的纠错编码即信道编码,与信源编码一样都是一种编码,但这里所讲的纠错编码即信道编码,与信源编码一样都是一种编码,但两者的作用是完全不同的。两者的作用是完全不同的。u 信源编码的目的是压缩冗余度,提高信息的传输速率。信源编码的目的是压缩冗余度,提高信息的传输速率。
4、u 信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。靠性。信息论与编码信息论与编码二差错控制系统模型及分类二差错控制系统模型及分类二差错控制系统模型及分类二差错控制系统模型及分类 1差错控制系统模型差错控制系统模型模型突出了以控制差错为目的的纠错码编、译码器,因此也称为模型突出了以控制差错为目的的纠错码编、译码器,因此也称为差错控制系统差错控制系统。2差错控制系统的分类差错控制系统的分类按其纠错能力的不同可分为两种:按其纠错能力的不同可分为两种:检错码检错码和和纠错码纠错码。检错码检错码:能发现错误但不能纠正错误的码
5、;:能发现错误但不能纠正错误的码;纠错码纠错码:不仅能发现错误而且还能纠正错误的码。:不仅能发现错误而且还能纠正错误的码。信息论与编码信息论与编码按差错控制系统类型,可分为按差错控制系统类型,可分为前向纠错前向纠错、重传反馈重传反馈和和混合纠错混合纠错等三种方式。等三种方式。前向纠错前向纠错(FEC)方式方式:FEC(Forward Error Control)方式是发端发送有纠错能力的码(纠错方式是发端发送有纠错能力的码(纠错码),接收端收到这些码后,通过纠错译码器自动地纠正传输中的错误。码),接收端收到这些码后,通过纠错译码器自动地纠正传输中的错误。优点优点:是不需要反馈信道;能进行一个用
6、户对多个用户的同时通信,特:是不需要反馈信道;能进行一个用户对多个用户的同时通信,特别适合于移动通信;译码实时性较好,控制电路也比较简单。别适合于移动通信;译码实时性较好,控制电路也比较简单。缺点缺点:是译码设备较复杂;编码效率较低。:是译码设备较复杂;编码效率较低。重传反馈重传反馈(ARQ)方式方式:ARQ(Automatic Repeat Request)方式是:发端发出能够发现错误的方式是:发端发出能够发现错误的码(检错码),收端译码器收到后,判断在传输中有无错误产生,并通过码(检错码),收端译码器收到后,判断在传输中有无错误产生,并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消
7、息再次传送,直反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送,直到收端认为正确接收为止。到收端认为正确接收为止。信息论与编码信息论与编码优点优点:译码设备简单,在多余度一定的情况下,码的检错能力比纠错能力:译码设备简单,在多余度一定的情况下,码的检错能力比纠错能力要高得多,因而整个系统能获得极低的误码率。要高得多,因而整个系统能获得极低的误码率。缺点缺点:应用:应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制,收、发两端必须互相配合,其控制电生信息的速率可以进行控制,收、发两端必须互相配合,其控
8、制电路比较复杂,传输信息的连贯性和实时性也较差。路比较复杂,传输信息的连贯性和实时性也较差。混合纠错混合纠错(HEC)方式:方式:HEC(Hybrid Error Control)方式是上述两种方式的结合。发端发送方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内,则自动进行纠错;若错误个数超过了码的纠错能力,但能纠错能力以内,则自动进行纠错;若错误个数超过了码的纠错能力,但能检测出来,则通过反馈信道告知发方重发。这种方式在一定程度上避免了检测出来,则通过反馈信道告知发方
9、重发。这种方式在一定程度上避免了 FEC方式译码设备复杂和方式译码设备复杂和 ARQ方式信息连贯性差的缺点。方式信息连贯性差的缺点。信息论与编码信息论与编码 在设计差错控制系统时,选择何种实现方式,应综合考虑各方面的因在设计差错控制系统时,选择何种实现方式,应综合考虑各方面的因素。主要有:素。主要有:满足用户对误码率的要求;满足用户对误码率的要求;有尽可能高的信息传输速率;有尽可能高的信息传输速率;有尽可能简单的编译码算法且易于实现;有尽可能简单的编译码算法且易于实现;(4)可接受的成本。可接受的成本。三纠错码的分类三纠错码的分类三纠错码的分类三纠错码的分类 常用的纠错码按其码字结构形式和对信
10、息序列处理方式的不同可分成常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类:两大类:分组码分组码和和卷积码卷积码。信息论与编码信息论与编码分组码分组码:把信息序列以每:把信息序列以每k个码元分组,编码器将每个信息组按一定规律产个码元分组,编码器将每个信息组按一定规律产 生生r个多余的码元(称为校验元),形成一个长为个多余的码元(称为校验元),形成一个长为n=k+r 的码字。的码字。对于对于k个码元分组,共有个码元分组,共有2k个不同的信息组,编码器输出长个不同的信息组,编码器输出长n的的2k个码个码字,这字,这2k个长为个长为n的码字构成的集合称为一个(的码字构成的集合称为一
11、个(n,k)分组码。)分组码。n:码长码长;k:信息位的数目信息位的数目;R=k/n:分组码码率分组码码率。卷积码卷积码:把信息序列以每:把信息序列以每k个分组,通过编码器输出长为个分组,通过编码器输出长为n(n k)的一个)的一个子码。但是该子码的子码。但是该子码的nk个校验元不仅与本子码的信息元有关,而个校验元不仅与本子码的信息元有关,而且也与其前且也与其前m个子码的信息元有关。个子码的信息元有关。信息论与编码信息论与编码四差错类型四差错类型四差错类型四差错类型 讨论码字序列通过离散信道时发生的情况,信道分为讨论码字序列通过离散信道时发生的情况,信道分为无记忆信道无记忆信道和和有有记忆信道
12、记忆信道。在无记忆信道中,噪声对传输码元的影响是相互独立的,即每一在无记忆信道中,噪声对传输码元的影响是相互独立的,即每一个差错的出现与其前后是否有错无关,如图所示。在无记忆信道中,个差错的出现与其前后是否有错无关,如图所示。在无记忆信道中,错误是随机产生的,因此被称作错误是随机产生的,因此被称作随机错误随机错误,无记忆信道也被称为,无记忆信道也被称为随机随机信道(信道(random channel)。信息论与编码信息论与编码有记忆信道中,各种干扰所造成的错误往往不是单个地,而是成群、成有记忆信道中,各种干扰所造成的错误往往不是单个地,而是成群、成串地出现,表现出错误之间有相关性,称为串地出现
13、,表现出错误之间有相关性,称为突发错误突发错误。下图就是这种信道的。下图就是这种信道的一个模型。一个模型。就实际信道而言,由于其干扰的复杂性,往往是两种错误并存。随就实际信道而言,由于其干扰的复杂性,往往是两种错误并存。随机错误与突发错误并存的信道,称为机错误与突发错误并存的信道,称为组合信道组合信道或或复合信道复合信道。信息论与编码信息论与编码7.2 7.2 7.2 7.2 分组码及检、纠错能力的获得分组码及检、纠错能力的获得分组码及检、纠错能力的获得分组码及检、纠错能力的获得 一分组码定义一分组码定义一分组码定义一分组码定义 设消息或数据以二进制形式表示,并以设消息或数据以二进制形式表示,
14、并以F2=0,1 表示这个二元集。表示这个二元集。消息集:消息集:序列个数:序列个数:2k 设长为设长为n的二元码元序列集为:的二元码元序列集为:序列个数:序列个数:2n 2k 设消息集是长为设消息集是长为k的二元消息序列集,表示如下:的二元消息序列集,表示如下:信息论与编码信息论与编码1分组编码:分组编码:在长为在长为n的二元序列集中的二元序列集中 选出与消息序列数选出与消息序列数2k相同相同数目的码元序列,并使两者一一对应。数目的码元序列,并使两者一一对应。几个概念:几个概念:码字码字:对应于消息的长:对应于消息的长n的的2k个码元序列,用个码元序列,用 表示。表示。选出的选出的2k个码元
15、序列称为个码元序列称为许用码组许用码组,另外的,另外的2n-2k个为个为禁用码组禁用码组。码码:所有码字的集合,用:所有码字的集合,用C表示。表示。字字:所有长为:所有长为n的二元序列。的二元序列。消息消息:长为:长为k的二元码元序列,用的二元码元序列,用 表示。表示。信息论与编码信息论与编码2消息消息 与码字与码字 的映射关系(函数关系)的映射关系(函数关系)的映射关系(函数关系)的映射关系(函数关系)线性分组码线性分组码:与与 呈线性关系(呈线性关系(fi为线性函数)为线性函数)非线性分组码非线性分组码:与与 不呈线性关不呈线性关系(系(fi为非线性函数)为非线性函数)对于消息为对于消息为
16、k位,码长为位,码长为n的线性分组码称(的线性分组码称(n,k)线性分组码。)线性分组码。信息论与编码信息论与编码【例例】一个原始数字消息一个原始数字消息u0 编码规则:编码规则:k=1,故为(,故为(n,1)码,称()码,称(n,1)重复码。码率:)重复码。码率:R=1/n 【例例】编码规则编码规则 构成一个(构成一个(n,n-1)线性分组码:)线性分组码:R=(n-1)/n (加法为模(加法为模2加)加)信息论与编码信息论与编码由最后一个方程:由最后一个方程:(奇)偶校验码(奇)偶校验码:码字中:码字中1的个数为偶数。的个数为偶数。在接收到一个字中在接收到一个字中1的个数不是偶数时,就可以
17、确定接收的不是码的个数不是偶数时,就可以确定接收的不是码字。这种码能检出奇数个错误,但不能发现偶数个错误。字。这种码能检出奇数个错误,但不能发现偶数个错误。比较上面两例编码方案:比较上面两例编码方案:重复码:重复码:R=1/n,编码效率最低,检纠错能力最高。,编码效率最低,检纠错能力最高。奇偶校验码:奇偶校验码:R=(n-1)/n,编码效率最高,检纠错能力最低。(两个极端),编码效率最高,检纠错能力最低。(两个极端)3纠错编码理论的中心任务纠错编码理论的中心任务:在重复码和奇偶校验码之间寻找一些性能良好:在重复码和奇偶校验码之间寻找一些性能良好的码,使编码效率和检、纠错能力得到统一。的码,使编
18、码效率和检、纠错能力得到统一。信息论与编码信息论与编码二分组码检、纠错能力的获得二分组码检、纠错能力的获得二分组码检、纠错能力的获得二分组码检、纠错能力的获得【例例】(2,1)重复码)重复码(2,1)重复码可以检出一个错误,但错误不能纠正。)重复码可以检出一个错误,但错误不能纠正。信息论与编码信息论与编码(3,1)重复码)重复码 (3,1)重复码可以检出最多不超过两个错误(作为检错码使用),)重复码可以检出最多不超过两个错误(作为检错码使用),能纠正一个错误(作为纠错码使用),但不能检出能纠正一个错误(作为纠错码使用),但不能检出3个错误。个错误。信息论与编码信息论与编码三错误图样三错误图样三
19、错误图样三错误图样对应着对应着n为码字,长为为码字,长为n的二元序列的二元序列 u 当当ei=1时,表明码字中第时,表明码字中第i位位ci发生错误;发生错误;u 当当ei=0时,表明码字中第时,表明码字中第i位位ci没有错误。没有错误。称称 为为为为错误图样错误图样错误图样错误图样。中中“1”的个数表示产生错误的个数,称错误图样的的个数表示产生错误的个数,称错误图样的错误重数错误重数(t)。)。设设 为码字在传输过程中发生错误而得到的接收字,则为码字在传输过程中发生错误而得到的接收字,则 信息论与编码信息论与编码【例例】(2,1)重复码)重复码 (3,1)重复码)重复码信息论与编码信息论与编码
20、 作为按照极大似然准则译码的纠错码,可以作为按照极大似然准则译码的纠错码,可以纠正该重错误图样的条件为:纠正该重错误图样的条件为:每个码字对应于该重错误图样的接收字集合中,每个码字对应于该重错误图样的接收字集合中,不可包含发送的码字。不可包含发送的码字。每个码字对应于该重错误图样的接收字集合中,每个码字对应于该重错误图样的接收字集合中,不包含公共元素。不包含公共元素。每个码字对应于该重错误图样的接收字集合,与每个码字对应于该重错误图样的接收字集合,与其它码字的错误重数低的接收字集合中,不包含其它码字的错误重数低的接收字集合中,不包含公共元素。公共元素。信息论与编码信息论与编码7.3 7.3 7
21、.3 7.3 汉明距离和分组码的检、纠错能力汉明距离和分组码的检、纠错能力汉明距离和分组码的检、纠错能力汉明距离和分组码的检、纠错能力 一汉明距离一汉明距离一汉明距离一汉明距离1定义:定义:设设 是集合是集合Vn(F2)()(n维向量空间维向量空间)中的任意两个字,令)中的任意两个字,令 ai,bi取自取自G(F2)(0,1)规定规定 表示字表示字 的各对应码元之间不相同的个数,则的各对应码元之间不相同的个数,则 称称 为为 之间的之间的汉明距离汉明距离,简称,简称距离距离。信息论与编码信息论与编码例如:例如:说明:说明:收到接收字收到接收字 后,通过计算后,通过计算 与各码字与各码字 之间的
22、汉明距离,如之间的汉明距离,如 与某一与某一码字码字 的汉明距离最小,则的汉明距离最小,则 与码字与码字 最像,译码器将最像,译码器将 译成译成 。极大似然译码基础:收到的字是从一个码字经错传尽可能少的位而来的极大似然译码基础:收到的字是从一个码字经错传尽可能少的位而来的可能性较从一个码字经错传较多的位而来的可能性要大。故通过判断汉明可能性较从一个码字经错传较多的位而来的可能性要大。故通过判断汉明距离来译码,符合极大似然译码规则。距离来译码,符合极大似然译码规则。如:如:pe10-5,则错一位的概率:,则错一位的概率:pe10-5,错两位的概率:,错两位的概率:pe10-10信息论与编码信息论
23、与编码【例例】有码字有码字 如接收字:如接收字:判断该接收字最有可能的码字。判断该接收字最有可能的码字。2汉明距离的性质汉明距离的性质 自反性:自反性:对称性:对称性:三角不等式:三角不等式:信息论与编码信息论与编码二分组码的检、纠错能力与最小汉明距离之间的关系二分组码的检、纠错能力与最小汉明距离之间的关系二分组码的检、纠错能力与最小汉明距离之间的关系二分组码的检、纠错能力与最小汉明距离之间的关系1码的最小距离码的最小距离码码C中不同码字之间距离的最小值称码中不同码字之间距离的最小值称码C的最小距离。的最小距离。dmin是衡量码的检、纠错能力的一个重要的参数。是衡量码的检、纠错能力的一个重要的
24、参数。2码的检、纠错能力与码的检、纠错能力与dmin的关系的关系 若若dmin t+1,则码,则码C可以检出所有不多于可以检出所有不多于t重的错误;重的错误;信息论与编码信息论与编码 若若dmin 2t+1,则码,则码C可以纠正所有不多于可以纠正所有不多于t重的错误;重的错误;若若dmin 2t1+t2+1,则码,则码C可以纠正所有不多于可以纠正所有不多于t1重的错误,并能检重的错误,并能检出所有的从出所有的从t1+1到到(t1+t2)重的错误。)重的错误。信息论与编码信息论与编码7.4 7.4 7.4 7.4 线性分组码及其矩阵描述线性分组码及其矩阵描述线性分组码及其矩阵描述线性分组码及其矩
25、阵描述 一基本概念一基本概念一基本概念一基本概念1线性空间线性空间定义定义:如果域:如果域F上的上的n重元素集合重元素集合V满足下述条件时,满足下述条件时,V关于加法构成阿贝尔群;关于加法构成阿贝尔群;对对V中任何元素中任何元素 和和F中的任何元素中的任何元素a,称,称V中元素中元素 为矢为矢量(向量),量(向量),F中元素中元素a称纯量(标量),称乘称纯量(标量),称乘a运算为数乘。运算为数乘。分配律成立:分配律成立:若若 有有 则称则称V是域是域F上的一个上的一个n维线性空间维线性空间(矢量空间),表示为:(矢量空间),表示为:Vn(F)信息论与编码信息论与编码2子空间子空间 线性空间线性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码 纠错
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。