信息论课件第6章信道编码2013章节

《信息论课件第6章信道编码2013章节》由会员分享，可在线阅读，更多相关《信息论课件第6章信道编码2013章节（111页珍藏版）》请在金锄头文库上搜索。

1、1,第6章 信道编码,6.1 信道编码的概念 6.2 信道编码定理 6.3 线性分组码,2,第6章 信道编码,信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题： 如何正确接收载有信息的信号 线路编码 如何避免少量差错信号对信息内容的影响 纠错编码,广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现,描述编码 用于对特定数据信号的描述 约束编码 用于对特定信号特性的约束 扩频编码 用于扩展信号频谱为近似白噪声谱并满足某些相关特性 纠错编码 用于检测与纠正信号传输过程中因噪声干扰导致的差错,1,2,3,4,消息,编码信道模型,n-1,当码字C和接受向量R均

2、由二元序列表时，称编码信道为二进制信道 C=(C0,C1,Cn-1) 如果对于任意的n都有： P(r/c)=p(ri/ci) 则称此二进制信道为无记忆二进制信道。 p(0/1)=p(1/0)=p0 则称此信道为无记忆二进制对称信道BSC,i=0,6,6.1 信道编码的概念,进行信道编码是为了提高信号传输的可靠性，改善通信系统的传输质量，研究信道编码的目标是寻找具体构造编码的理论与方法。 从原理上看，构造信道码的基本思路是根据一定的规律在待发送的信息码元中人为地加入一定的多余码元(称为监督码)，以引入最小的多余度为代价来换取最好的抗干扰性能。,7,6.1.1 信道编码的分类,从功能上看，信道编码

3、可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类，纠错码一定能检错，检错码不一定能纠错，平常所说的纠错码是两者的统称。,8,6.1.1 信道编码的分类,根据信息码元与监督码元之间的关系，纠错码分为线性码和非线性码。 线性码信息码元与监督码元之间呈线性关系，它们的关系可用一组线性代数方程联系起来。非线性码信息码元与监督校元之间不存在线性关系。,9,6.1.1 信道编码的分类,按照对信息码元处理的方法的不同，纠错码分为分组码和卷积码。 分组码-把信息序列以每k个码元分组，然后把每组k个信息元按一定规律产生r个多余的监督码元，输出序列每组长为n=k+r，则每一码字的r个校验元只与

4、本码字的k个信息位有关，与别的码字的信息位无关，通常记分组码为(n,k)。,10,6.1.1 信道编码的分类,其中分组码又可分循环码和非循环码：对循环码而言，其码书的特点是，若将其全部码字分成若干组，则每组中任一码字中码元循环移位后仍是这组的码字；对非循环码来说，任一码字中的码元循环移位后不一定再是该码书中的码字。,11,6.1.1 信道编码的分类,卷积码-把信息序列以每k0(通常较小)个码元分段，编码器输出该段的监督码元r=n- k0 不但与本段的k0个信息元有关，而且还与其前面L段的信息码元有关，故记卷积码为(n, k0,L)。 按照每个码元的取值来分，可有二元码和多元码。由于目前的传输或

5、存储系统大都采用二进制的数字系统，所以一般提到的纠错码都是指二元码。,12,6.1.1 信道编码的分类,13,6.1.2与纠错编码有关的基本概念,在通信系统的接收端，若接收到的消息序列R和发送的码符号序列C不一样，例如R=(11000)，而C=(10001)，R与C中有两位不同，即出现两个错误，这种错误是由信道中的噪声干扰所引起的。,在通信系统的接收端，若接收到的消息序列R和发送的码符号序列C不一样，例如R=(11000)，而C=(10001)，R与C中有两位不同，即出现两个错误，这种错误是由信道中的噪声干扰所引起的。,差错图案：随机序列 或 ，,14,6.1.2与纠错编码有关的基本概念,1.

6、码长、码重和码距 码字中码元的个数称为码字的长度，简称码长，用n表示。码字中非“0”码元的个数称为码字的汉明重量(简称码重，记作W)。对二进制码来说，码重W就是码字中所含码元“1”的数目，例如码字“110000”，其码长n=6，码重W=2。 两个等长码字之间对应码元不相同的数目称为这两个码组的汉明距离(简称码距)。例如码字“110000”与“100001”，它们的汉明距离D=2。,15,6.1.2与纠错编码有关的基本概念,在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离dmin，即： 例如：码组C=0111100，1011011，1101001的最小码距dmin=3。 从避免

7、码字受干扰而出错的角度出发，总是希望码字间有尽可能大的距离，因为最小码距代表着一个码组中最不利的情况。,16,6.1.2与纠错编码有关的基本概念,2.错误图样 为了定量地描述信号的差错，定义收、发码之“差”为差错图样。 差错图样E发码C- 收码R （模M）。 例：8进制(M=8)码元， 若发码 ：C=（0,2,5,4,7,5,2） 收码变为：R=（0,1,5,4,7,5,4） 差错图样 E=C-R=（0,1,0,0,0,0,6）（模8） 二进制码：E=C R 或 C = R E。,17,6.1.3 错误的种类,1、随机错误：由随机干扰引起。(前后位置无关，时间无关，差错以等概率发生) 特点：因

8、为干扰是随机的，所以各码元是否发生错误是相互独立的，不会成片出错。 2、突发错误：由突发干扰引起（前后相关，成堆出现）。 特点：因为突发干扰是突然出现的，且能持续一段时间，同时相对功率较大，所以错误往往成片出现。,常见错误有两种：随机错误和突发错误,（在一个突发错误持续长度内，开头和末尾的码元总是错的，中间一些码元不一定都错，但错的码元数较多）如闪电和开关瞬态往往引起突发错误。,18,6.1.2与纠错编码有关的基本概念,3.重复码和奇偶校验码 1)重复码 构成重复码的方法是当发送某个信源符号ai时，不是只发一个，而是连续重发多个，连续重发的个数越多，重复码的抗干扰能力就越强，当然效率也越低。,

9、19,6.1.2与纠错编码有关的基本概念,不重复时为(1，1)重复码，如图所示： 重复一次时为(2，1)重复码，如图所示：,20,6.1.2与纠错编码有关的基本概念,重复二次时为(3，1)重复码，如图所示：,21,6.1.2与纠错编码有关的基本概念,2)奇偶检验码 奇偶校验是一种最基本的校验方法。构成奇偶检验码的方法是在每k个二进制信息位后加上一个奇(偶)监督位(或称校验位)，使码长n=k+r，同时使码中“1”的个数恒为奇数(或偶数)，如图所示。在奇偶校验码中，监督位r=1，它是一种码重W为奇数(或偶数)的系统分组码。,22,6.1.2与纠错编码有关的基本概念,奇校验-如果信息码元中“1”值的

10、个数为奇数个，则校验码元值为“0”；如果信息码元中“1”值的个数为偶数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“1”。 偶校验-如果信息码元中“1”值的个数为偶数个，则校验码元值为“0”；如果信息码元中“1”值的个数为奇数个，则校验码元值为“1”。 即所有信息码元与校验码元的模二和等于“0”。,23,6.1.3 检错与纠错原理,要纠正传输差错，首先必须检测出错误。而要检测出错误，常用的方法是将发送端要传送的信息序列(常为二进制序列)中截取出长度相等的码元进行分组，每组长度为k，组成k位码元信息序列M，并根据某种编码算法以一定的规则在每个信息组的后面产生r个冗余码元，由冗余

11、码元和信息码元一起形成“ n位编码序列”，即信号码字C，n位的码字比信息码长(有n=k+r个码元)，因而纠错编码是冗余编码。,冗余编码：码字 的长度 一定大于消息 的长度,24,6.1.3 检错与纠错原理,译码就是利用校验关系进行检错、纠错的，在接收端收到的位码字中，信息码元与冗余码元之间也应符合上述编码规则，并根据这一规则进行检验，从而确定是否有错误。这就是差错控制的基本思想。,25,6.1.3 检错与纠错原理,分组码一般用符号(n,k)表示，其中k是每组二进制信息码元的数目，n是编码组的长度(简称码长)，即编码组的总位数，n-k=r为每码组中的校验码元(或称监督位)数目。 通常，将分组码规

12、定为具有如图所示的结构。图中前面k位为信息位，后面附加r个校验位。,26,奇偶校验方法。增加偶(或奇)校验位使得对消息序列而言校验方程成立，当校验位数增加时，可以检测到差错图样的种类数也增加，但同时码率减小。 n重复码方法。重复消息位使之可以检测出任意小于n个差错的错误图样。 等重码方法。设计码字中的非“0”符号个数(若是二进制码则为“1”的个数)恒为常数，使码集C由全体重量恒等的n长矢量组成。,6.1.3 检错与纠错原理,27,6.1.3 检错与纠错原理,表所示为一种用于表示数字“0”到“9”的五中取三等重码(所有码字的码重都等于“3”)的例子。,28,6.1.4 检错与纠错方式和能力,1.

13、检错与纠错方式 自动请求重发方式-用于检错的纠错码在译码器输出端给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的全部或部分码字，这种纠错码的应用方式称为自动请求重发方式(ARQ，Automatic-Repeat-reQuest)。 前向纠错方式-用于纠错的纠错码在译码器输出端总要输出一个码字或是否出错的标志，这种纠错码的应用方式称为前向纠错方式(FEC，Forward-error control)。 另外用于检错与纠错的方式还有混合纠错(HEC，Hybrid Error Correction),29,ARQ方式：发送端用编码器对发送数据进行差错编码，

14、通过正向信道送到接收端，而接收端经译码器处理后只是检测有无差错，不作自动纠正。如检测到差错，则利用反向信道反馈信号，请求发送端重发有错的数据单元，直到接收端检测不到差错为止。,6.1.4 检错与纠错方式和能力,30,FEC方式：发送端用编码器对发送数据进行差错编码，在接收端用译码器对接收到的数据进行译码后检测有无差错，通过按预定规则的运算，如检测到差错，则确定差错的具体位置和性质，自动加以纠正，故称为“前向纠错”。,6.1.4 检错与纠错方式和能力,31,HEC方式：是检错重发和前向纠错两种方式的混合。发送端用编码器对发送数据进行便于检错和纠错的编码，通过正向信道送到接收端，接收端对少量的接收

15、差错进行自动前向纠正，而对超出纠正能力的差错则通过反馈重发方式加以纠正，所以是一种纠检结合的混合方式。,6.1.4 检错与纠错方式和能力,32,2.检错与纠错能力 一个纠错码的每个码字都可以形成一个汉明球，因此要能够纠正所有不多于t位的差错，纠错码的所有汉明球均应不相交，判定纠错码的检、纠错能力可根据任意两个汉明球不相交的要求，由码的最小距离dmin来决定。,6.1.4 检错与纠错方式和能力,33,定理1 若纠错码的最小距离为dmin，那么如下三个结论的任何一个结论独立成立： 若要发现e个独立差错，则要求最小码距 若要纠正t个独立差错，则要求最小码距 若要求发现e个同时又纠正t个独立差错，则,

16、6.1.4 检错与纠错方式和能力,34,6.1.4 检错与纠错方式和能力,35,定理说明，码的最小距离dmin越大，码的纠(检)错误的能力越强。但是，随着多余码元的增多，信息传输速率会降低得越多。 通常用=k/n来表示码字中信息码元所占的比例，称为编码效率，它是衡量码性能的又一个重要参数。码率越高，信息传输率就越高，但此时纠错能力要降低，若=1时就没有纠错能力了。可见，码率与纠错能力之间是有矛盾。,6.1.4 检错与纠错方式和能力,36,正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。 逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。,6.1.7 信道编码定理,37,6.3 线性分组码,码集C能否构成n维n重矢量空间的一个k维n重子空间？ 如何寻找最佳的码空间？ qk个信息元组以什么算法一一对应映射到码空间 码率编码效率：Rc =k/n,码失