第一章-纠错码的基本概念...ppt

1、纠错编码技术,第一章纠错码的基本概念,福州大学阳光学院,2020/7/7,纠错编码技术,2,本章主要内容,1.1 编码系统模型 1.2 信道错误类型与信道模型 1.3 差错控制的基本方式 1.4 纠错码的分类 1.5 最大后验与最大似然译码 1.6 纠错码的基本概念,1.7 几种常用的编码方式,2020/7/7,纠错编码技术,3,本章要求,掌握： 差错控制方式 纠错码的基本概念 理解： 最大似然译码 了解： 纠错编码的作用、基本思想和编码系统模型,2020/7/7,纠错编码技术,4,1.1 编码系统模型,2020/7/7,纠错编码技术,5,1.1 编码系统模型,信源编码器：将信源发出的消息如语

2、言、 图像、文字等转换成为二进制(也可转换成为多进制)形式的信息序列。,信源编码器的设计目标： （1）以最低的比特率表示信源的输出消息； （2）信源的输出可由信息序列m准确的重现。,2020/7/7,纠错编码技术,6,1.1 编码系统模型,信道编码器：将信息序列m变换成离散的编码序列C，称之为码字。,本课程的主要内容之一，就是设计和实现信道编码器，以抵抗传输或存储码字所面临的噪声环境的影响。,2020/7/7,纠错编码技术,7,1.1 编码系统模型,调制器或写入单元：将信道编码器输出的每个符号，转换为持续时间为T秒的适合传输（或记录）的波形，这些波形进入信道或存储媒质，并受到噪声的干扰。,解调

3、器或读出单元：处理收到的每个持续时间为T秒的波形，然后产生离散（量化）或连续（非量化）的输出。 解调器的输出序列称为接收序列R。,2020/7/7,纠错编码技术,8,1.1 编码系统模型,信道译码器：将接收序列R变换为二进制序列 ，称之为 估计信息序列。,本课程的另一主要内容，就是设计和实现使译码错误概率最小的信道译码器。,译码策略根据信道编码规则和信道的噪声特性设计。,2020/7/7,纠错编码技术,9,1.1 编码系统模型,编码系统的简化模型,2020/7/7,纠错编码技术,10,1.2 信道错误类型与信道模型,随机错误和随机信道 突发错误和突发信道 混合错误和混合信道,2020/7/7,

4、纠错编码技术,11,1.2 信道错误类型与信道模型,随机错误和随机信道 随机错误：信道传输中，信息序列各码元发生的出错事件彼此独立，即每个码元独立的按一定的概率发生差错。 只存在随机错误的信道称为无记忆信道（随机信道），用信道转移概率来描述。例如，二进制对称信道BSC和离散无记忆信道DMC。,2020/7/7,纠错编码技术,12,二进制对称信道（Binary Symmetric Channel, BSC）,P(0/0)=1-p P(1/0)=p P(1/1)=1-p P(0/1)=p,输入符号取值集合 X=0，1,输出符号取值集合 Y=0，1,0,1,0,1,X,Y,p,p,1-p,1-p,1

5、.2 信道错误类型与信道模型,2020/7/7,纠错编码技术,13,离散无记忆信道（Discrete Memoryless Channel, DMC）,输入符号取值集合 X=x0, x1,xq-1 输出符号取值集合 Y=y0, y1,yQ-1 qQ个条件概率： P(yj/xi)=pij 其中，i=0,1,q-1; j=0,1,Q-1,x0,x1,xq-1,. . .,y0,y1,y2,. . .,yQ-1,P(y0/x0),P(y1/x0),P(y2/x0),P(yQ-1/x0),P(y0/x1),P(y1/x1),P(y2/x1),P(yQ-1/x1),1.2 信道错误类型与信道模型,202

6、0/7/7,纠错编码技术,14,1.2 信道错误类型与信道模型,突发错误和突发信道 突发错误：噪声对各传输码元的影响不是独立的，从而导致差错是一连串出现的。 例如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。 存在突发错误的信道，称之为有记忆信道（突发信道）。,2020/7/7,纠错编码技术,15,1.2 信道错误类型与信道模型,混合错误和混合信道 混合错误：既有突发错误又有随机错误。 突发错误和随机错误并存的信道称之为混合信道。,2020/7/7,纠错编码技术,16,错误图样： 设发送的是序列C（码元长度为n），通过信道传输后，接收端的序列为R。由于信道中存在干扰

7、，R序列中的某些码元和C序列中的对应码元的值可能不同，如果信道中的干扰采用二进制序列e表示，相应有错误的位取值为1，无错的位取值为0，可得e=CR。,1.2 信道错误类型与信道模型,2020/7/7,纠错编码技术,17,例：发送序列C：（1111100000），收到的序列R：（1001010000），第二、三、五、六位产生了错误，因此错误图样e的二、三、五、六位取值为1，即e：(0110110000) 对于突发信道，错误图样中，第一个“1”和最后一个“1”之间的码元总个数称为突发长度，其图样成为突发图样。该例中，突发图样是（11011），突发长度为5。,1.2 信道错误类型与信道模型,2020

8、/7/7,纠错编码技术,18,1.3 差错控制的基本方式,反馈重传方式 前向纠错方式 混合方式,2020/7/7,纠错编码技术,19,1.3 差错控制的基本方式,反馈重传方式(ARQ) 工作原理：发送端发送检错码，通过信道传输到接收端，接收端译码器根据编码规则判断是否有错误，并把判决信号通过反馈信道送回发送端。发送端根据判决信号确定是否重新发送，直到接收端检查无误为止。,2020/7/7,纠错编码技术,20,1.3 差错控制的基本方式,优点： 1.编译码设备简单 2.纠错能力强 3.对信道的适应性强,缺点： 1.需反馈信道 2.控制电路复杂 3.传送信息的实时性、连贯性差,2020/7/7,纠

9、错编码技术,21,前向纠错方式 (FEC) 工作原理：发送端发送能纠正错误的码字，在接收端根据接收到的码字和编码规则，能自动纠正传输中的错误。 不需要反馈信道，实时性好。 随着纠错能力的提高，编译码设备复杂。,1.3 差错控制的基本方式,发端,收端,纠错码,2020/7/7,纠错编码技术,22,1.3 差错控制的基本方式,混合方式 (HEC) 工作原理：结合前向纠错和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。,发端,收端,检纠错码,判决信号,2020/7/7,纠错编码技术,23,1.4 纠错码的分类,按差错控制编码的不同功能： 检错码：发现错误的码 纠错码

10、：自动纠正错误的码 按信息码元与附加监督码元间检验关系： 线性码(Linear Code)：监督码元与信息码元满足线性关系 非线性码(Nonlinear Code)：监督码元与信息元不满足线性关系,2020/7/7,纠错编码技术,24,1.4 纠错编码的分类,按信息码元与监督码元间约束方式： 分组码(Block Code)：信息序列每k位分成一组，产生r位监督元，输出长度为n=r+k的码字。r位监督元只与本分组的k位信息元有关，记为（n,k）。 卷积码(Convolutional Code)：编码器给每k0位信息加上n0- k0位监督元得到长度为n0的码字。该码字的运算，不仅与本段k0位信息有

11、关，还与其前面m组k0位信息有关。称这种码为（n0，k0，m）卷积码。,2020/7/7,纠错编码技术,25,1.4 信道编码的分类,按信息码元在编码后是否保持原来的形式： 系统码、非系统码 按纠正错误的类型： 纠正随机错误的码、纠正突发错误的码 按每个码元取值： 二进制码、多进制码,2020/7/7,纠错编码技术,26,分组码的定义,分组码是对每段k位长的信息组，以一定规则增加r=n-k个校验元，组成长为n的序列： （cn-1，cn-2，.，c2，c1）,称这个序列为码字（码组、码矢）。在二进制情况下，信息组总共有2k个，因此通过编码器后，相应的码字也有2k个，称这个2k个码字集合为（n，k

12、）分组码。,2020/7/7,纠错编码技术,27,分组码将k个比特编成n个比特的码字（Code words）通常记分组码为（n，k）码。（n，k）码中有2k个码字。,（n，k）码中有2k个n重码字。但是n bit的二进制序列具有2n种不同的组合序列； 分组码的编码规则就是从2n种不同序列中选择2k个码字，建立信息序列与码字的对应关系；,分组码的定义,2020/7/7,纠错编码技术,28,许用码组、禁用码组 这2k个码字组成的集合称为许用码组，剩余的2n-2k个n重向量组成的集合称为禁用码组。,码重:码字中非0码元的个数，又称汉明重量。如码字x=(11000)，则码重w(x)=2,码距:码字x与

13、码字y对应位取值不同的个数，又称为汉明距离。 例如: x=(10111101), y=(01110101)，则码距d(x, y)=3,分组码的定义,2020/7/7,纠错编码技术,29,1.5 最大后验与最大似然译码,信源,编码,信道,译码,信宿,m,c,r,m,根据编码规则，在信息序列基础上增加监督码元，生成码字,根据一套译码规则，由接收序列 r 给出与发送序列m最接近（最好是相同）的估值序列m 已知条件： 1）实际接收的码字r （必要条件） 2）发送端采用的编码算法和产生的码集Xn（必要条件） 3）信道模型和信道参数,2020/7/7,纠错编码技术,30,1.5 最大后验与最大似然译码,编

14、码： m=c 译码： r =c=m 由于信息序列与码字之间存在一一对应关系，所以等价于译码器根据r产生一个c的估值序列c。显然当且仅当c=c时，m=m，此时译码器正确译码。,信源,编码,信道,译码,信宿,m,c,r,m,c,2020/7/7,纠错编码技术,31,1.5 最大后验与最大似然译码,最大后验译码 (Maximum APosteriori, MAP) 对于给定接收序列r，译码器的条件译码错误概率为： 译码错误概率最小，有,对于输入r，译码器在2k个码字中选择一个使P(c*/r)最大的码字c*作为c的估值序列c，会使译码输出错误概率最小，这种译码准则为最大后验译码。,2020/7/7,纠

15、错编码技术,32,1.5 最大后验与最大似然译码,最大后验译码 (Maximum APosteriori, MAP) 最优的译码算法，所以也称最佳译码 但是实际译码时，定量地找出后验概率值很困难 通常情况下，可以知道信道的前向（发-收）转移概率，比如BSC信道模型中的p,2020/7/7,纠错编码技术,33,1.如果发送端发送每个码字的概率相同，最大似然 译码等价于最大后验译码。 2.译码器对于输入r，在2k个码字中选择一个使似然 概率 最大的码字c*作为c的估值序列c。,1.5 最大后验与最大似然译码,最大似然译码 (Maximum Likelihood Decoding, MLD) 由贝叶

16、斯公式， 若发送端发送每个码字的概率P(c*)均相同，且由于P(r)与译码方法无关，所以,2020/7/7,纠错编码技术,34,1.5 最大后验与最大似然译码,最大似然译码 (MLD) 对于无记忆信道，码字的似然函数等于组成码字的各码元的似然函数之积，即若r=(r1,r2, rn), c=(c1,c2, ,cn) 码字最大似然函数也就是各码元似然函数之积的最大化,2020/7/7,纠错编码技术,35,1.6 纠错码的基本概念,性能指标 香农信道编码定理 分组码的检纠错能力,2020/7/7,纠错编码技术,36,性能指标 编码效率 分组码（n，k），R表明了信息元在码字中所占的比重，是衡量编码有

17、效性的基本参数。 n-k监督位，监督位越多，纠错能力越强，效率越低。n越大，编、译码延时越大。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,37,性能指标 香农信道编码定理 分组码的检纠错能力,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,38,香农信道编码定理 对于一个给定的有扰信道，若信道的容量为C，只要发送端以低于C的速率发送信息，则一定存在一种编码方法，使译码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为 这里E(R)称为误差指数。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,39,定理说明： 当信息速率小于信道容量时，总存在一种编码

18、方式使差错率低于任一给定值； 为减小差错概率，可增大码长n或增大E(R)。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,40,性能指标 香农信道编码定理 分组码的检纠错能力,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,41,分组码的检纠错能力,最小码距:(n,k)分组码中，任何两个不同码字之间距离的最小值，称为该分组码的最小汉明距离，简称最小距离，用d0表示。最小码距决定了码的纠错、检错性能。 最小汉明距离译码准则:在许用码组中，判断与接收序列r “最近”的码字为发送码字。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,42,分组码的检纠错能力 检错能力

19、：一个(n,k)分组码，如果能检出一个码字内的所有小于或等于e 个(位)错误，则称该码的检错能力为e 纠错能力：一个(n,k)分组码，如果能纠正一个码字内的所有小于或等于t个(位)错误，则称该码的纠错能力为t,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,43,分组码的检纠错能力 同时纠检错能力：一个(n,k)分组码，如果能纠正一个码字内的所有小于或等于t个(位)错误，同时又能检出所有小于或等于e (e t)个(位)错误，则称该码的同时纠检错能力为纠t个错同时检e个错,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,44,分组码的检纠错能力 为了检测e个错误，要求分组码的

20、最小码距d0e+1,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,45,分组码的检纠错能力 为了纠正t个错误，要求分组码的最小码距d02t+1,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,46,分组码的检纠错能力 为了纠正t个错误，同时检测e个错误(e=t)，要求最小码距 d0e+t+1,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,47,分组码的检纠错能力 由此定理可知，一个距离为d的分组码， （1）至多能纠正t(d0 -1)2(x是x的整数部分)个错误。 （2）至多能发现e（d0 -1）个错误。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术

21、,48,分组码的检纠错能力 d0是分组码的一个重要参数，它表明了分组码抗干扰能力的大小。设计码时，要同时考虑d0和R 举例 重复码（校验元是信息元的重复，错误概率P） (2,1)码：d0=2, R=1/2，能检1个错，若与ARQ结合，译码错误概率为p2；不能纠错；,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,49,分组码的检纠错能力 举例 重复码（校验元是信息元的重复，错误概率P） (3,1)码：d0=3, R=1/3， （1）若仅用来检错，能检2个错 ； （2）能够纠1个错。,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,50,举例2 重复码（校验元是信息元的重复）

22、 (4,1)码： d0=4, R=1/4， 若仅用来检错，能检3个错； 若同时纠检错，则能纠1个错同时检2个错,编码的任务： 构造出R一定、d0尽可能大的码，或者d0一定、R尽可能大的码,1.6 纠错码的基本概念,2020/7/7,纠错编码技术,51,1.7 几种常用的编码方式,奇偶校验码 群计数码 恒比码（等重码）,2020/7/7,纠错编码技术,52,1.7 几种常用的编码方式,奇偶校验码 偶校验码：加入监督位后，码字中“1”的个数为偶数个，即所有位的模二和为0。（即偶数个1） 奇校验码：加入监督位后码字中“1”的个数为奇数个，即所有位的模二和为1。 （即奇数个1） 这是一种最简单的检错码，在计算机数据传输中得到广泛应用。,2020/7/7,纠错编码技术,53,1.7 几种常用的编码方式,群计数码 将码字中“1”的计数值作为监督码 例如，信息组为01011，共3个1，用011表示，得到(8,5)码。群计数码的码字为01011011 检错能力很强，除了0错成1和1错成0成对发生的情况外，其它形式的错误都能发现。 为了降低发送码元中的冗余度，有时只传送计数码元中最后几位。特别的只传输最后1位监督元，则群计数码变成奇偶校验