信息论与编码 曹雪芹 Chap6

信道编码第6章26.1纠错编译码的基本原理与分析方法6.2线性分组码6.3卷积码内容3•信源编码–提高数字信号有效性•将信源的模拟信号转变为数字信号•降低数码率,压缩传输频带(数据压缩)•信道编码–提高数字通信可靠性•数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。•编码46.1纠错编译码的基本原理与分析方法56.1.1差错和差错控制系统分类•差错率是衡量传输质量的重要指标之一,它有几种不同的定义。•码元差错率/符号差错率–指在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率。–是指信号差错概率•比特差错率/比特误码率：–在传输的比特总数中发生差错的比特数所占比例–是指信息差错概率•对二进制传输系统,符号差错等效于比特差错;对多进制系统,一个符号差错对应多少比特差错却难以确定6差错率•根据不同的应用场合对差错率有不同的要求:–在电报传送时,允许的比特差错率约为:10－4～10－5；–计算机数据传输,一般要求比特差错率小于:10－8～10－9；–在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率7差错图样•为定量地描述信号的差错,定义差错图样EE=C－R(模M)•最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即E=C⊕R或C=R⊕E•设发送的码字C1111111111接收的码字R1001001111差错的图样E0110110000•差错图样中的“1”既是符号差错也是比特差错,差错的个数叫汉明距离。0:传输中无错1:传输中有错8差错图样•随机差错：–差错是相互独立的,不相关–存在这种差错的信道是无记忆信道或随机信道•突发差错：–指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字•E:0010010000001001110000000突发长度=4突发长度=69纠错码分类•从功能角度讲,差错码分为检错码和纠错码–检错码：用于发现差错–纠错码：能自动纠正差错•纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。10纠错码分类•按照对信息序列的处理方法,有分组码和卷积码•分组码：–将k个信息码元分成一组,由这k个码元按照一定规则产生r个监督码元,组成长度n=k+r的码字•卷积码：–先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与前面若干组有关。kk010101010001110010xxxx101xxxx010xxxxrnr11纠错码分类•按照码元与原始信息位的关系,分为–线性码：所有码元均是原始信息元的线性组合,编码器不带反馈回路。–非线性码：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。•由于非线性码的分析比较困难,早期实用的纠错码多为线性码,但当今发现的很多好码恰恰是非线性码。12纠错码分类•按照适用的差错类型,分成:–纠随机差错码:用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。–纠突发差错码:针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量13差错控制系统分类•前向纠错(FEC)：–发送端的信道编码器将信息码组编成具有一定纠错能力的码。–接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。图6.1.8FEC与ARQ纠错应用方式纠错译码纠错编码信道消息m码字C接收向量R消息m’检错译码检错编码信道消息m码字C接收向量R消息m’FECARQ14差错控制系统分类•自动请求重发(ARQ)：–发端发送检错码，–收端译码器判断当前码字传输是否出错；–当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字(全部或部分)。图6.1.8FEC与ARQ纠错应用方式纠错译码纠错编码信道消息m码字C接收向量R消息m’检错译码检错编码信道消息m码字C接收向量R消息m’FECARQ15差错控制系统分类•混合纠错(HEC)：–是FEC与ARQ方式的结合。–发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。–如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。•信息反馈(IRQ)：–收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。16检错与纠错原理•0:晴,1:雨•若1→0,0→1。收端无法发现错误图6.1.4BSC转移概率1－pb00111－pbpbpb00晴1001110011雨能发现一个错误禁用码组•插入1位监督码后具有检出1位错码的能力,但不能予以纠正。17检错与纠错原理000晴010001111000111雨晴•在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检出2位或2位以下的错码。100011101110雨18检错与纠错原理•最大似然译码：–将接收到的码字译码为与它差别最小的许用码字,并且认为这个许用码字就是它所对应的发送码字,从而在码字的纠错能力内实现自动纠错。•纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了监督码。监督码不载信息,只是用来监督信息码在传输中有无差错。•纠错编码所提高的可靠性,是以牺牲信道利用率为代价换取的。•监督码引入越多,检错、纠错能力越强,但信道的传输效率下降也越多。19检错与纠错原理111101110011000010100001t=1t=2t=3图6.1.7纠1位差错的3重复码20(4)等重码/定比码•设计码字中的非0符号个数恒为常数，即C由全体重量恒等于m的n重向量组成。•5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。21(2)最大似然译码•译码过程–由图6.1.2可见：译码器接收到一个接收码字R后，按编码规则对R进行译码后输出信息码组的估值m’；–信息码组与码字C之间是有固定规则的，这相当于信道译码器能给出码字C的估值C’。当C’≠C时就出现了译码错误。因为只有当C’=C时，m’=m。信源编码解调器信源图6.1.2有信道编码的数字通信系统框图调制器传输媒介信宿信源译码信道译码信道编码CRmm'22•最大后验概率译码准则–当译码器收到某一个接收码字R后，根据最大后验概率p(C/R)进行译码判决，一定是译码错误概率最小。–根据贝叶斯原理–似然函数：p(R/C)23–设每个码字长为n，若接收码字R与码字C的距离为d(R,C)，则条件概率p(R│C)可表示为–最大化p(R│C)等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C’距离最小的译码。24•信道编码–在被传输信息中附加一些冗余码,即监督码元,利用附加码元与信息码元间的约束关系加以校验,以检测和纠正错误。•信源编码减少了冗余度–冗余度是随机的、无规律的•信道编码增加了冗余度–冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。信道编码25•传输冗余比特必然要动用冗余的资源。•时间：–比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。•频带：–插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。•功率：–采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。–8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。•设备复杂度：–加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。26信道编码的基本思想•信道编码–按一定规则给数字序列m增加一些多余的码元,使不具有规律性的信息序列m变换为具有某种规律性的数码序列C；–码序列中的信息序列码元与多余码元之间是相关的；–信道译码器利用这种预知的编码规则译码。检验接收到的数字序列R是否符合既定的规则,从而发现R中是否有错,或者纠正其中的差错；–根据相关性来检测/发现和纠正传输过程中产生的差错就是信道编码的基本思想。27码距与检错、纠错能力•纠错编码的检错纠错能力,要取决于码组的码距•码距越大,检错、纠错能力越强。•汉明距离：–二个码组对应码位码元不同的个数。•最小码距dmin：–一个码组的集合中任意二个码组间的最小汉明距离。•码重W：–码组中非0的数目。28码距与检错、纠错能力•定理：若纠错码的最小距离为dmin，⑴可以检测出任意小于等于l=dmin－1个差错⑵可以纠正任意小于等于个差错21mindt⑶可以检测出任意小于等于l同时纠正小于等于t个差错，–其中l、t满足：l+t≤dmin－1t＜l29编码效率•编码效率：–一个组中信息所占的比重nkR–k：信息码元的数目–n：编码组码元的总数目n=k+r–r：监督码元的数目30检错码•奇偶校验码(n，n-1)(k+1，k)•偶校验码字0110pmmmk31(2)偶（或奇）校验方法•一个奇偶校验位–p为偶校验位m0+m1+m2+…+mk－1+p=0(mod2)–则C=(m0,m1,m2,…,mk－1,p)为一个偶校验码字。–C中一定有偶数个“1”–所有可能的C的全体称为一个码率为k/(k+1)的(k+1,k)偶校验码；–确定校验位p的编码方程为p=m0+m1+m2+…+mk－1–当差错图案E中有奇数个“1”，即R中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。–校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。32•多个奇偶校验位–一个校验位可以由信息位的部分或全部按校验方程产生；–例如C是一个对阵列消息进行垂直与水平校验以及总校验的码字；–其码率为当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。33(3)重复消息位方法•n重复码：码率为1/n，仅有两个码字C0和C1，传送1比特(k=1)消息；•C0=(00…0)，C1=(11…1)•n重复码可以检测出任意小于n/2个差错的错误图案–BSC信道：pb≤1/2，n比特传输中发生差错数目越少，概率越大(1－pb)npb(1－pb)n－1…pbt(1－pb)n－t…pbn–总认为发生差错的图案是差错数目较少的图案，当接收到重复码的接收序列R中“1”的个数少于一半时，认为发送的是C0，否则认为是C1。图6.1.7所示纠1个任意差错的3重复码。346.2有噪信道编码定理•6.2.1有噪信道编码定理•定理6.2设有一个离散无记忆平稳信道，其信道容量为C。当信息传输率R＜C，只要码长n足够长，则总存在一种编码，可以使平均译码错误概率任意小。•这个定理称为有噪信道编码定理，又称为香农第二定理。••35通过一个有噪信道可以实现几乎无失真传输，这与人们的直观想象似乎是大相径庭的，而定理的证明也是非常巧妙的。香农巧妙地先，他不去构造理想的好码，而是用随机编码的方法得到所有可能生成的码的集合，然后在码集合中随机选择一个码作为输入码序列，最后计算这样随机选择的一个码在码集合上的平均性能。在译码时，利用了联合典型序列的概念，即将接收序列译成与其联合典型的码字．这种译码方法不是最优译码，但便于理论分析。36•定义6.6设是长为n的随机序列对，且•则在这些随机序列对中同时满足以下条件的序列对称为联合ε典型序列。(,)ijxy1()()nijijkkkppxyxy1log(),ipHXnxix即是X的ε典型序列；(1)(2)1log(),jpHXny即是X的ε典型序列；1log(),ijpHXYnx,yiy(3)ε是任意小的正数。联合ε典型序列的全体构成的集合称为联合ε典型序列集，记作()GXY37按照以上定义可以得到联合渐进等分割性。对于任意小的正数ε≥0,δ≥0,当n足够大时，(1