信息论与编码信道编码

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/12/13,#,2024/11/15,1,第,6,章信道编码,信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次：,如何正确接收载有信息的信号,如何避免少量差错信号对信息内容的影响,纠错编码,试图克服信道中噪声造成的损害,基本思想：在消息通过一个有噪信道传输前，以多余符号的形式在消息中增添冗余度。,通信原理,THIS IS AN INTRSTNG BOOK,THIS IS AN INT,E,R,E,ST,I,NG BOOK,2024/11/15,2,第,6,章信道编码,m,：输入信息序列的每,k,个信息符号分成一段，称为,信息组,m,i,：信息元,C,：码字,C,i,：码元,r,=,n,-,k,：校验元,分组码,：每个码字中增加的,r,个校验元只由本组的,k,个信息元产生，与其他信息组的信息元无关。记为,(,n,k,),卷积码,：增加的,r,个校验元既与本组信息元有关，还与前面,L,组信息元有关。记为,(,n,k,L,),(,m,1,m,2,m,k,),x,0,x,1,x,q,-1,(,c,1,c,2,c,n,),q,k,q,n,2024/11/15,3,第,6,章信道编码,6.1,有扰离散信道的编码定理,6.2,纠错编译码的基本原理与分析方法,2024/11/15,4,差错和差错控制系统分类,差错符号、差错比特,符号是信息比特的载体。,信号差错与信息差错既有联系又有区别。,符号差错概率（误码元率）指信号差错概率,误比特率指信息差错概率,2024/11/15,5,差错和差错控制系统分类,随机差错,差错始终以相等的概率独立发生于各码字、各码元和各比特之间，与前后位置和时间无关。,如加性高斯白噪声,突发差错,由突发噪声引起的前后相关、成堆出现的差错。,数学模型：双状态一阶马尔可夫链模型,2024/11/15,6,纠错码分类,从功能角度，差错码分为检错码和纠错码,检错码,：用于发现差错的信道码,纠错码,：能自动纠正差错的信道码,例：要发送,A,和,B,可以采用以下三种方法：,不重复,：用,0,代表,A,，,1,代表,B,。,重复一次,：用,00,代表,A,，,11,代表,B,。,增加一位码元，传送效率降低一倍。,重复两次,：用,000,代表,A,，用,111,代表,B,。,增加两位码元，效率降低两倍。,既不检错，又不纠错,检错但不纠错,既检错又纠错,2024/11/15,7,纠错码分类,按照对信息序列的处理方法，有分组码和卷积码两种。,分组码：将信息序列分割成,k,位一组后独立编解码，分组间无关。,卷积码：编解码运算不仅与本组信息有关，还与前面若干组有关。,按照码元与原始信息位的关系，分为线性码和非线性码。,线性码：所有码元均是原始信息元的线性组合，编码器不带反馈回路。,非线性码：码元并不都是信息元的线性组合，可能还与前面的码元有关，编码器可能含反馈回路。,2024/11/15,8,纠错码分类,按照适用的差错类型，分成纠随机差错码和纠突发差错码两种。,随机差错,差错是相互独立的，不相关,存在这种差错的信道是无记忆信道或随机信道,突发差错,指成串出现的错误，错误与错误间有相关性，一个差错往往要影响到后面一串字,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,突发长度,=6,用可纠独立差错的个数来衡量,用可纠突发差错的最大长度来衡量,2024/11/15,9,差错控制系统分类,前向纠错方式,（,FEC,）,发送端的信道编码器将信息码组编成具有一定纠错能力的码。,接收端信道译码器对接收码字进行译码，如果传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。,实时性好，适用于单工通信,2024/11/15,10,检错与纠错方式,自动请求重发方式,（,ARQ,）,发送端发送检错码,接收端译码器判断当前码字传输是否出错,当有错时，按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字,译码设备不复杂，对突发错误特别有效,2024/11/15,11,检错与纠错方式,混合纠错,（,HEC,）,FEC,与,ARQ,方式的结合。,发送端发送同时具有自动纠错和检测能力的码组，收端收到码组后检查差错情况。如果差错在码的纠错能力内，则自动进行纠正。,如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。,检错、纠错能力强，译码设备复杂，应用广泛,2024/11/15,12,与差错控制有关的基本概念,码长,：码字中码元的个数，用,n,表示,汉明重量,（,码重,）：码字中非,0,码元的个数，用,W,表示。对于二进制来说，指码字中码元,1,的数目。,若码字,C,=(,c,1,c,2,c,n,),，则,汉明距离,（,码距,）：两个等长码字之间对应码元不相同的数目，用,D,表示。,设两个二元码字,X,=(,x,1,x,2,x,n,),和,Y,=(,y,1,y,2,y,n,),，则有,两个码字模二相加得到的新码字的重量应是这两个码字之间的汉明距离，即,2024/11/15,13,与差错控制有关的基本概念,码的最小距离,d,min,在某一码集,C,中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即,例：码集,C,=0111100,1011011,1101001,最小码距是衡量该码纠错能力的重要依据,从避免码字受干扰而出错的角度出发，希望码字间有尽可能大的距离，因为最小码距代表着一个码集中最不利的情况。,从安全出发，应使用最小码距来分析码的检错、纠错能力。,d,min,=3,2024/11/15,14,与差错控制有关的基本概念,错误图样,在二元无记忆,N,次扩展信道中，差错的形式也可以用二元序列来描述，称为,错误图样,。,设发送码字为,C,=(,c,1,c,2,c,n,),，接收码字为,R,=(,r,1,r,2,r,n,),，两者的差别为,例：,R,=(1,1,000,0,),，,C,=(1,0,000,1,),E,C,R,=(0,1,000,1,),，表明接收符号系列的第,2,位和第,6,位出现了错误。,2024/11/15,15,检错、纠错能力,差错的产生,码字集合是,N,维矢量空间,X,N,中的一个子集。,若传输无误，接收到的码字应在码字集合内。,若出现差错，有两种可能：,对应到码字集合外的一点上。,对应到码字集合内的另一点上。,检错与纠错能力,纠错码的检、纠错能力是指能够检测、纠正差错的数目。,能够检错,不能检错,2024/11/15,16,检错、纠错能力,检错能力,纠错码的最小距离,d,min,表示从子集中一点偏移到另一点的距离。,若差错数目,e,大于等于,d,min,，将导致一个码字被译成另一个码字，这种错误无法检测。,若差错数目,e,小于,d,min,，则不可能从子集的一个点偏移到另一个点，即可以检测出差错。,d,min,e,e,d,min,1,2024/11/15,17,检错、纠错能力,纠错能力,以每个码字为球心，以汉明距离,t,为半径作,2,k,个球体。,球体之间不相交（且不相切）的条件是：,d,min,=2,t,+1,译码时，所有落在球内的接收码字都被译为位于球心的码字。,纠错能力总是小于检错能力的。,d,min,t,t,=INT(,d,min,-1)/2,2024/11/15,18,检错、纠错能力,检、纠错能力,若将检错和纠错统一考虑，情况会有所变化。,要增加检错能力，必须抑制纠错能力。,如码字,A,、,B,的码距为,7,码字,A,发生,3,个差错时能够纠正；若发生,4,个差错时，将被译成,B,。即：检错和纠错能力都为,3,。,若要提高检错能力为,4,，需将纠错能力减为,2,。,若最小距离,d,min,的码同时能检,e,d,、纠,e,c,个差错，则,e,d,+,e,c,d,min,-1,2024/11/15,19,检错、纠错能力,对纠错编码的基本要求,纠错和检错能力尽量强，编码效率尽量高，码长尽量短，编码规律尽量简单。,在实际系统中，要求检、纠错易于实现，成本尽量低。,信道编码的主要目标,以可靠性为主，即在保证抗干扰能力尽量强的基础上，适当兼顾有效性，寻求和构造最小距离,d,min,比较大的码。,2024/11/15,20,随机编码,随机编码,从,N,维矢量空间,X,N,的,q,N,个点中选取,q,K,个点作为码字，可以借助近世代数理论寻找最佳的方法，也可以随机地选择。,平均差错概率,E,(,R,),：可靠性函数。,R,：码率，表示每码元携带,的信息量，又称为传信率。,临界速率,R,0,2024/11/15,21,随机编码,有扰离散信道编码定理,若有一离散无记忆平稳信道，其容量为,C,，输入符号序列长度为,N,。只要待传送的信息率,R,C,，总可以找到一种编码方法，当,N,足够长时，使译码错误概率,P,e,，,为任意正数。,反之，当,R,C,时，任何编码的,P,e,0,。当,N,时，,P,e,1,。,与信源编码定理类似，香农第二定理只是一个,存在性定理,，它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可以几乎无失真地把信息传送过去。,2024/11/15,22,第,6,章信道编码,6.1,有扰离散信道的编码定理,6.2,纠错编译码的基本原理与分析方法,2024/11/15,23,差错控制,差错控制：从公式和概念两条途径来论述差错控制与信道编码的基本原理。,途径一：信道编码定理的公式,减小差错概率：,增大码长,N,或增大可靠性函数,E,(,R,),增大,E,(,R,),：,加大信道容量,C,或,减小码率（传信率）,R,对于同样的码率，信道容量大者其可靠性函数,E,(,R,),也大。,对于同样的信道容量，码率减小时其可靠性函数,E,(,R,),增大。,增大,C,、减小,R,、增加,N,2024/11/15,24,差错控制,增大信道容量,C,扩展带宽,开发新的宽带媒介：例如从电缆到光纤，从中短波到毫米波、微米波。,采取信道均衡措施。,加大功率,提高发送功率：例如提高天线增益，提高波束的方向系数等。,降低噪声：例如采用低噪声器件、滤波、屏蔽、接地、低温运行等。,在纠错编码技术发展之前，主要依靠增大,C,来提高通信的可靠性。,2024/11/15,25,差错控制,减小码率,R,二进制,(,N,K,),分组码：,R,=,K,/,N,q,进制,(,N,K,),分组码：,R,=,K,log,2,q,/,N,降低码率的方法,q,、,N,不变而,减小,K,：降低信息源速率，每秒少传一些信息。,q,、,K,不变而,增大,N,：提高符号速率，占用更大带宽。,N,、,K,不变而,减小,q,：减小信道的输入、输出符号集。,用增加信道容量的冗余度来换取可靠性,2024/11/15,26,差错控制,增加码长,N,保持码率,R,不变，增加码长,N,的同时应增大信息位,K,。,在,C,和,R,固定的情况下加大,N,，并不增加信道容量的冗余度。,随着,N,增大，矢量空间,X,N,增大，码字间距离加大，从而可靠性提高。,码长,N,越大，实际差错概率就越能符合统计规律。,增加码长,N,的代价是编解码算法复杂，编解码器昂贵。,通过增加码长,N,来提高可靠性已成为纠错编码的主要途径之一,2024/11/15,27,差错控制,途径二：从概念上分析纠错编码的基本原理,利用冗余度,噪声均化,利用冗余度,冗余比特与信息比特之间存在特定的相关性。,若个别信息比特出错，可以利用其他比特推测出错比特，保证信息的可靠性。,传输冗余比特，必然要运用冗余的资源：,时间,频带,功率,设备复杂度,2024/11/15,28,差错控制,噪声均化,基本思想,：设法将危害较大的、较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。,噪声均化的方法：,增加码长,N,：码长越长，平均每个码字中的误码元比例降低，差错概率减小。,卷积码,：将相关