信道编码1015上课

信道编码,2020/5/26,2,第6章信道编码,目的：了解信道编码的作用与意义掌握几种典型的信道编码、译码方法对信道编码的研究方法和成果有基本认识，为进一步研究打下基础特点：基本概念、物理意义、基本方法为主,2020/5/26,3,主要内容,基本概念和方法线性分组码循环码（实验）BCH卷积码,2020/5/26,4,6.1用于可靠传输和存储数据的编码,信道编码的引入信道编码的基本思想编码系统模型,2020/5/26,5,6.1用于可靠传输和存储数据的编码信道编码的引入,移动通信,通信网,小张,小李,2020/5/26,6,6.1用于可靠传输和存储数据的编码信道编码的引入,通信的目的在于传输信息通信系统主要质量指标是通信的有效性和可靠性在实际信道上传输信号时，由于信道传输特性不理想及噪声的影响，接收端收到的信号不可避免地会发生错误,发送端,接收端,干扰,2020/5/26,7,6.1用于可靠传输和存储数据的编码信道编码的引入,随着差错控制编码理论的完善和数字电路技术的发展，信道编码不仅应用于各种通信系统中，在计算机存储、运算系统以及超大规模集成电路的设计中也得到日益广泛的应用。,2020/5/26,8,6.1用于可靠传输和存储数据的编码信道编码的作用,信道编码是在数据传输/存储中所采用的降低系统差错率，提高系统可靠性的一种数字处理技术。,2020/5/26,9,6.1用于可靠传输和存储数据的编码信道编码的基本思想,通过对信息码元序列作某种变换,即增加一定数量的多余码元，使原来彼此相互独立、没有关联的信息码元,经过变换后,产生某种规律性或相关性,从而在接收端可根据这种规律性来检查、纠正传输序列中的差错。编码的实质利用冗余降低差错概率。,2020/5/26,10,6.1用于可靠传输和存储数据的编码信道编码的基本思想,举例：ASCII码的偶校验过程ASCII码：7bit表示符号，例如“L”的ASCII是0011001偶校验：使得编码后输出的码字中“1”的个数为偶数0011001-00110011接收端验证“1”的个数是否为偶数这一“规律”（关系）是否成立来检验错误是否发生,启示需要增加冗余码元（8，7）监督码元与信息码元建立了一组关系接收端利用这组关系检查和纠正错误,2020/5/26,11,6.1用于可靠传输和存储数据的编码编码系统模型,信源：输出的是信息序列（信息码元）信道：广义信道，也称编码信道,2020/5/26,12,信息序列：mi=mi1,mi2,mik,编码后的发送序列：Ci=Ci1,Ci2,Cin,受到干扰后的接收序列：ri=ri1,ri2,rin,信息序列：mi=mi1,mi2,mik,编码,译码,发送端,接收端,信道（干扰）,编码系统模型下的数字序列变换,2020/5/26,13,6.1用于可靠传输和存储数据的编码编码系统模型,三点说明：1.不可无限的增加冗余码2.尽可能的重现m，即使m尽量接近m3.编译码算法易实现，设备费用尽量低,研究各种编码和译码方法是信道编码所要解决的问题。,噪声干扰,2020/5/26,14,6.2错误类型与信道模型,噪声干扰,输入,输出,转移概率,2020/5/26,15,6.2错误类型与信道模型,随机错误和随机信道突发错误和突发信道混合错误和混合信道,2020/5/26,16,6.2错误类型与信道模型,随机错误和随机信道随机错误：各码元是否出现错误，与前、后码元是否差错没有关系，每个码元独立的按一定的概率发生差错。一般是由加性高斯白噪声引起的。只存在随机错误的信道称为无记忆信道/随机信道，用信道转移概率来描述。比如，二进制对称信道BSC。,2020/5/26,17,二进制对称信道（BinarySymmetricChannel,BSC）,P(1/0)=pP(0/1)=pP(1/1)=1-pP(0/0)=1-p,输入符号取值集合X=0，1,输出符号取值集合Y=0，1,0,1,0,1,X,Y,p,p,1-p,1-p,6.2错误类型与信道模型,2020/5/26,18,6.2错误类型与信道模型,突发错误和突发信道突发错误：噪声对各传输码元的影响不是独立的，从而导致差错是一连串出现的。例如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等。存在突发错误的信道，称之为有记忆信道/突发信道。,2020/5/26,19,6.2错误类型与信道模型,混合错误和混合信道混合错误：既有突发错误又有随机错误。突发错误和随机错误并存的信道称之为混合信道。,2020/5/26,20,错误图样：设发送的是序列C（码元长度为n），通过信道传输后，接收端的序列为R。由于在传输过程中受到信道噪声干扰，R序列中的某些元素和C序列中的对应码元的值可能不同，如果信道中的噪声干扰采用二进制序列e表示，相应有错误的位取值为1，无错的位取值为0，可得e=CR,6.2错误类型与信道模型,2020/5/26,21,例：发送序列C：（1111100000），收到的序列R：（1001010000），第二、三、五、六位产生了错误，因此错误图样e的二、三、五、六位取值为1，即e：(0110110000)对于突发信道，错误图样中，第一个“1”和最后一个“1”之间的码元总个数称为突发长度，其图样称为突发图样。该例中，突发图样是（11011），突发长度为5。,6.2错误类型与信道模型,2020/5/26,22,6.3差错控制的基本方式,反馈重传方式前向纠错方式混合方式,2020/5/26,23,6.3差错控制的基本方式,反馈重传方式(AutomaticRepeatreQuest,ARQ)工作原理：发送端发送的是检错码，通过信道传输到接收端，接收端译码器只需根据编码规则判断是否有错误，并把判决信号通过反馈信道送回发送端。发送端根据判决信号将收端认为有错误的重新发送，直到接收端检查无误为止。,2020/5/26,24,6.3差错控制的基本方式,发端,收端,检错码,判决信号,反馈重传方式(AutomaticRepeatreQuest,ARQ)分为两类：等待式和连续式,2020/5/26,25,6.3差错控制的基本方式,前向纠错方式(ForwardErrorCorrection,FEC)工作原理：发送端发送能纠正错误的码字，在接收端根据接收到的码字和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好。随着纠错能力的提高，编译码设备复杂。,2020/5/26,26,6.3差错控制的基本方式,混合方式(HybridErrorCorrection,HEC)工作原理：结合前向纠错和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。折衷方案。,2020/5/26,27,6.4信道编码的分类,按差错控制编码的不同功能：检错码：发现错误的码纠错码：自动纠正错误的码按信息码元与附加监督码元间检验关系：线性码(LinearCode)：监督码元与信息码元满足线性关系非线性码(NonlinearCode)：监督码元与信息码元不满足线性关系,2020/5/26,28,6.4信道编码的分类,按信息码元与监督码元间约束方式：分组码(BlockCode)：信息序列每k位分成一组，产生r位监督元，输出长度为n=r+k的码字。r位监督元只与本分组的k位信息元有关，记为（n,k）。卷积码(ConvolutionalCode)：编码器给每k0位信息加上r0位监督元得到长度为n0的码字。该码字的运算，不仅与本组k0位信息有关，还与其前面m组k0位信息有关。称这种码为（n0，k0，m）卷积码。,2020/5/26,29,6.4信道编码的分类,按信息码元在编码后是否保持原来的形式：系统码、非系统码按纠正错误的类型：纠正随机错误的码、纠正突发错误的码按每个码元取值：二进制码、多进制码,2020/5/26,30,6.4信道编码的分类,2020/5/26,31,6.5信道编码定理,香农信道编码定理性能指标分组码及相关基本概念,2020/5/26,32,6.5信道编码定理,香农信道编码定理对于一个给定的有扰信道，若信道的容量为C，只要发送端以低于C的速率发送信息，则一定存在一种编码方法，使译码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为这里E(R)称为可靠性函数。,2020/5/26,33,6.5信道编码定理,定理告诉我们：当信息速率小于信道容量时，总存在一种编码方式使差错率低于任一给定值；为减小差错概率，可增大码长n或增大E(R)增大E(R)可：可以增大信道容量；（增大带宽、增大功率、降低噪声）减小码率；,2020/5/26,34,6.6线性分组码,分组码及参数分组码：将信息序列分成k位一组，按照一定的校验关系增加r位校验位，构成n(n=k+r)位码分组，称为码字（Codewords)，所有可能码字构成的集合称为一个分组码，记为(n,k)分组码分组码的校验关系仅限于一个码分组之内,2020/5/26,35,6.6线性分组码,分组码及参数主要参数：信息分组：m=(mk-1mk-2m1m0)码字：C=(cn-1cn-2c1c0)码长n，信息位个数k，校验位个数r=n-k码字个数(二进制)：2k编码效率：R=k/n,2020/5/26,36,6.6线性分组码,许用码组、禁用码组（n，k）码中有2k个n重码字。但是nbit的二进制序列具有2n种不同的组合序列；分组码的编码规则就是从2n种不同序列中选择2k个码字，建立信息序列与码字的对应关系；,这2k个码字组成的集合称为许用码组，剩余的2n-2k个n重向量组成的集合称为禁用码组。,2020/5/26,37,6.6分组码基本概念,码重、码距码重：码字中非0码元的个数，又称汉明重量。例如码字x=(11000)，则码重w(x)=2码距：码字x与码字y对应位取值不同的个数，又称为汉明距离。例如：x=(10111101)，y=(01110101),2020/5/26,38,6.6分组码的基本概念,最小码距（最小汉明距离）最小码距：（n，k）分组码中，任何两个码字之间距离的最小值，称为该分组码的最小汉明距离，简称最小距离，用d表示。最小码距描述分组码特性的重要参量，决定了码的纠错、检错性能。(n,k)分组码通常也记为(n,k,d)分组码。,2020/5/26,39,6.6分组码的基本概念,最小码距（最小汉明距离）例：(2,1)重复码，00,11d=？(3,1)重复码，000,111d=？(4,1)重复码，0000,1111d=？,2020/5/26,40,6.6分组码的基本概念,最小汉明距离译码准则：在许用码组中，判断与接收序列r“最近”的码字为发送码字,2020/5/26,41,分组码的检纠错能力,分组码的检纠错能力码的最小距离为d0=e+1，其检错能力为e。,2020/5/26,42,分组码的检纠错能力,分组码的检纠错能力纠错能力：一个(n,k)分组码，如果能纠正码字内的所有小于或等于t个(位)错误，则称该码的纠错能力为t,2020/5/26,43,分组码的检纠错能力码的最小距离为d0=2t+1，其纠错能力为t。且当d*=2t+1或d*=2t+2时，都不能纠正t+1个错误。,2020/5/26,44,分组码的检纠错能力,分组码的检纠错能力同时纠检错能力：一(n,k)分组码，如果能纠正码字内的所有小于或等于t个(位)错误，同时又能检出所有小于或等于e(et)个(位)错误，则称该码的同时纠检错能力为纠t个错同时检e个错。,2020/5/26,45,分组码的检纠错能力码最小码距d0=e+t+1，其中et，该码能够纠正t个错误，同时检测e个错误。,2020/5/26,46,6.7几种常用的编码方式,奇偶校验(监督)码水平一致监督码水平垂直一致监督码群计数码恒比码（等重码）,2020/5/26,47,6.7几种常用的编码方式,奇偶校验码是(n,n-1)码。假设奇偶校验码的码字表示为偶校验码：加入监督位后，码字中“1”的个数为偶数个，即所有位的模二和为0。（即偶数个1）,2020/5/26,48,6.7几种常用的编码方式,奇偶监督（校验）码奇校验码：加入监督位后码字中“1”的个数为奇数个，即所有位的模二和为1。（即奇数个1）可以检测任意奇数个错误；构造简单，易于实现，在计算机内部数据传送和输入输出设备中经常使用。,2020/5/26,49,6.7几种常用的编码方式,水平一致监督码将原信息序列以适当长度排成一行，如每k位信息为一行，设共有m行。对每行进行偶（奇）校验经，构成(m(k+1),mk)分组码传输时按列传输；译码时排成表，检验每行的校验关系,2020/5/26,50,6.7几种常用的编码方式,水平一致监督码可以发现所有长度bm的单个突发错误,2020/5/26,51,6.7几种常用的编码方式,水平垂直一致监督码经奇偶校验后的若干码字排列成矩阵，每个码字排成一行，然后再按列的方向增加垂直校验位，就构成了二维奇偶校验码(m(k+1)+k,mk)传输时可以按行传输，也可以按列传输。,2020/5/26,52,6.7几种常用的编码方式,水平垂直一致监督码,2020/5/26,53,6.7几种常用的编码方式,水平垂直一致监督码纠检错能力强：可检测每一行中奇数个错和每一列中奇数个错；二维奇偶码适用于检测突发错误。如果采用按照列的顺序传输，可以发现长度tm+2的突发错；如果按照行的顺序传输，可以发现tk+2。应用于穿孔纸带、磁带记录系统中。,2020/5/26,54,6.7几种常用的编码方式,群计数码将码字中“1”的计数值作为监督码元例如，信息组为01011，共3个1，用011表示，得到(8,5)码。群计数码的码字为01011011检错能力很强，除了0错成1和1错成0成对发生的情况外，其它形式的错误都能发现。为了降低发送码元中的冗余度，有时只传送计数码元中最后几位。特别的只传输最后1位监督元，则群计数码变成奇偶校验码,2020/5/26,55,6.7几种常用的编码方式,恒比码码字中“1”和“0”的个数保持相同的比例，即每个码字中1的个数相同。恒比码的译码可以采用查表方法，检错时查1或0的个数。恒比码是一种检错码。恒比码一般用在电报。,2020/5/26,56,6.7几种常用的编码方式,恒比码例：发汉字电报时，每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32中可能的码字中挑出=10个1的个数为3的码字作为阿拉伯数字的编码方式。,2020/5/26,57,6.8信道编码理论的发展历史,1948年香农（Shannon）在其论文通信中的数学理论中提出有扰信道编码定理奠定了信道编码的基石。50年代至60年代初，信道编码从无到有得到了迅速的发展：奠定了线性分组码的理论基础；提出了著名的BCH码编译码方法以及卷积码的序列译码。,2020/5/26,58,6.8信道编码理论的发展历史,60年代至70年代初，信道编码发展最为活跃的时期：提出了门限译码、迭代译码、软判决译码和维特比译码等有效的译码方法，并注重纠错码的实用化；在此期间以代数方法特别以有限域理论为基础的线性分组码理论趋于成熟。,2020/5/26,59,70年代至80年代，