第五章 差错控制与信道编码 数据通信原理课件.ppt

《第五章 差错控制与信道编码 数据通信原理课件.ppt》由会员分享，可在线阅读，更多相关《第五章 差错控制与信道编码 数据通信原理课件.ppt（89页珍藏版）》请在三一办公上搜索。

1、第五章 差错控制与信道编码,结束放映,学习目录,学习要求,内容简介,主讲教师：刘兴顺,内容简介,差错控制就是通过某种方法，发现并纠正数据传输中出现的错误。差错控制技术是提高数据传输可靠性的重要手段之一，现代数据通信中使用的差错控制方式大都是基于信道编码技术来实现的，本章对差错控制的基本概念以及常用的信道编码方案作了比较详细的理论述。,返回,结束,学习要求,1. 理解差错控制的基本概念及其原理等；2. 掌握信道编码的基本原理；3. 了解常用检错码的特性；4. 掌握线性分组码的一般特性；5. 掌握汉明码以及循环码的编译码及其实现原理；6. 了解卷积码的基本概念。,返回,结束,学习目录,返回,5.1

2、 概述5.2 常用的简单信道编码5.3 线性分组码5.4 卷积码,结束,5.1 概 述,差错控制是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施 。本节将介绍差错控制和信道编码的基本原理、差错控制的实现方式等内容。,5.1.1 差错控制 5.1.2 信道编码 5.1.3 基于信道编码的差错控制方式,本节内容提要：,5.1.1 差错控制,差错控制通过某种方法，发现并纠正传输中出现的错误。 香农信道编码定理在具有确定信道容量的有扰信道中，若以低于信道容量的速率传输数据，则存在某种编码方案，可以使传输的误码率足够小。,基于信道编码的差错控制在发送端根据一定的规则，在数据序列中按照一定的规

3、则附加一些监督信息，接收端根据监督信息进行检错或者纠错。,5.1.1 差错控制,随机错误 主要由起伏噪声引起，错误码元分布比较分散且彼此统计独立； 突发错误主要由脉冲噪声引起，错误码元分布集中且彼此具有某种相关性。,错误图样,差错分析,E中，“0”表示正确，“1”表示错误,随机错误错误图样,5.1.1 差错控制,突发错误错误图样,5.1.2 信道编码,在不采用信道编码的时候，进入信道的数据码元相互独立，一旦发生错误，将无法发现。例如气象台向电视台传输气象信息。,不可靠数据传输系统,5.1.2 信道编码,将信息序列按照k位码元的长度分成若干个信息码组M，再将信息码组输入到信道编码器，信道编码器按

4、照一定的算法，产生一个新的n位码字A输出，nk；收端根据A中的相关性判断接收是否正确，并将其恢复成M。编码效率为k/n，即所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比 。,信道编码的基本思想,5.1.2 信道编码,信道编码的冗余,信息码组M由k个二进制码元（即比特）组成，所以就有2k个M；A长度为n，n位长度的码字共有2n个，信道编码实质是通过一定 的规则，从2n个长度为n的码字中选择了其中的2k个，每个被选 中的码字称为许用码字；未被选中的2n-2k个n长的码字称为禁用码字，反映冗余大小 。,5.1.2 信道编码,对本节开始时的例子采用(2，1)重复码: 11”- 晴,

5、“00” - 雨 许用码组为:“11”和“00”,禁用码组为：“01”和“10” 此时接收端可以发现单个错误，但不能纠正错误 也不能发现2位错误，如下图所示：,实例分析 I,5.1.2 信道编码,对本节开始时的例子采用(3，1)重复码: 111”- 晴,“000” - 雨 许用码组为: 111和000 禁用码组为： 001、010、011、100、101、110 将这种编码用来检错时，可以发现两位以内的错误 将这种编码用来纠错，可以纠正一位错误，如下图所示：,实例分析 II,5.1.2 信道编码,如此译码的原因是信道中错一位的概率远远大于错多位的概率,例如要把该（3，1）重复码在有一条误码率为

6、10-5的信道传输，则： 错一位的概率为：P1 = C31 Pe (1Pe)2 = 310-5 错二位的概率为：P2 = C32 Pe2 (1Pe) = 310-10 错三位的概率为：P3 = Pe3 = 10-15,这种译码方法称为极大似然译码法,其基本原理为:构造一个极大似 然函数L,从2k个许用码组中找到一个码字Ci，当R = Ci时,函数L可以 取得最大值,则认为C = Ci 。,5.1.2 信道编码,线性码和非线性码 若f()是线性函数称为线性码若f()是非线性函数则称为非线性编码,信道编码的分类,信道编码器函数关系式为：,分组码和卷积码 分组码：每个信息码组M通过运算产生对应的A

7、，记作(n，k),卷积码：每个A是由m (m2k)个M联合运算得到，记作(n，k，m),5.1.2 信道编码,系统码和非系统码,检错码、纠错码和纠检错码,若A中的前k位或者后k位就是信息码组M，则称这种编码为系统 码，否则称为非系统码。,5.1.2 信道编码,几个概念,码长 码字的码元数目，例如(n，k)分组码的码长为n,码重 指码字中“1”的数目，记作W(A)。例如W(110110)=4,码距（汉明距） 两个等长码对应位不同的数目，记作d(A，B)， 例如A=110110，B=101011，则d(A，B)=4,码距与码重的关系 d(A，B)=W (A+B),5.1.2 信道编码,最小码距（最

8、小汉明距）,一个(n，k)分组码的纠检错能力由其最小码距决定 ：,当最小码距d0e+1时，能够发现e个错误码元 当最小码距d02t+1时，能够纠正t个错误码元当最小码距d0t +e +1时，能够纠正t个错误码元， 同时发现e个错误码元(et),(n，k)分组码总共有2k个码字，记作Ai（i=0,1,2k-1）,则这些码字两两之间都有一个码距，定义该(n，k)分组码的最小码距为 ：,5.1.3 基于信道编码的差错控制方式,反馈纠错（ARQ）方式,原理采用检错码，接收端发现错误后，给发送端一个反馈信号，要求重新发送，直到正确为止。,特点编码效率比较高，对信道的适应能力强重发导致信道的有效利用率较低

9、，通信的实时性较差,应用数据通信系统,5.1.3 基于信道编码的差错控制方式,前向纠错（FEC）方式,原理采用纠错码,收端发现错误后自动纠正。,特点无需重发，实时性好编码效率较低，译码设备比较复杂若错误超出纠错码纠错能力,只好将其抛弃,应用移动通信系统,5.1.3 基于信道编码的差错控制方式,混合纠错（HEC）方式,原理采用纠检错码，是ARQ和FEC方式的折衷方案,特点集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性,应用移动通信系统 ，数据传输系统,5.2 常用的简单信道编码,本节内容提要：,检错码在ARQ系统中使用，其生成方式简单，易于实现，检错效果较

10、好，因此得到广泛的应用，本节将介绍奇偶校验码、行列监督码、恒比码 、正反码的编译码规则、特性以及应用情况。,5.2.1 奇偶监督码 5.2.2 行列监督码 5.2.3 恒比码 5.2.4 重复码 5.2.5 正反码,5.2.1 奇偶监督码,奇偶监督码码重为奇数或偶数的(n , n-1)系统分组码,ITU-T建议同步数据传输使用偶监督异步数据传输使用奇监督,监督关系假设将（n，n-1）的奇偶监督码的码字记作：an-1,an-2,a1,a0， 其中a0为监督码元，其余为信息码元，则各码元满足：,5.2.2 行列监督码,行列监督码对水平方向(共L行)和垂直方向(共M列) ,同时进行奇偶监督的码， 记

11、作（LM+L+M+1 , LM）。,(66，50)行列监督码的一个码字,该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比 较严重的通信中。,5.2.3 恒比码,恒比码该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。,目前我国电传通信中普遍采用3：2码，又称5中取3码，如下所示,国际上通用的ARQ电报通信系统中，采用7中取3码。,5.2.4 重复码, (3，1)重复码两个码字为000和111，其最小码距为3； (n，1)重复码也只有全0码和全1码两个码字，其最小码距为n， 却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大； 该码随码长增加，具有很强的纠检错能力， 但其编

12、码效率的急剧下降；重复码并不是一种优秀的编码方案， 仅用于速率很低的数据通信系统中。,重复码重复码只有一位信息码元，监督码元是信息码元的重复， 所以仅有两个码字；,5.2.5 正反码,正反码该码型多用于10单位码的前向纠错设备中，可以纠正一位错误， 发现全部两个以下的错误，以及大部分两个以上的错误，其本质 就是五单位码的重复；,编码规则信息码组中1的数目为奇数时，监督码是信息码的重复即正码； 信息码组中1的数目为偶数时，监督码是信息码的反码。,译码方法首先将收到的码字重的信息位和监督位按对应位作模2运算， 得到一个5位码组，若该码字中有奇数个1，则将其作为校验码 组，若有偶数个1，则取其反码作

13、为校验码组。然后，按照下表 进行纠检错译码,5.2.5 正反码,正反码错误判决表,5.3 线性分组码,本节内容提要：,本节将对线性分组码的特点、编译码规则以及应用情况作介绍，主要包括以下四方面内容。,5.3.1 基本概念 5.3.2 线性分组码编码 5.3.3 汉明码 5.3.4 循环码,5.3.1 基本概念,1有限域,定义了加法“+”和乘法“”两种运算的有限集合；q个元素的有限域又称为伽罗瓦域，记作GF(q)；对域的逆元操作又演绎出了减法“”和除法运算“”，,域具有封闭特性,域中总包含惟一的加法恒等元“0”和乘法恒等元“1”,5.3.1 基本概念,域中任意元素存在惟一的加法逆元 域中任意非零

14、元都存在惟一的乘法逆元 于是减法和除法运算可定义为：,域中元素满足交换律、结合律和分配律运算规则：,5.3.1 基本概念,GF(q)中定义的是模q的加法和乘法，例如GF(2)的运算表如表所示：,加法运算表,乘法运算表,5.3.1 基本概念,2矢量空间, 所有n维矢量组成的集合就构成了n维矢量空间Vn；,矢量对矢量的加法构成一个加法交换群， 即满足封闭性、结合律和交换律，有恒等元和逆元。, 满足分配律,满足结合律,矢量空间的性质,8PSK调制时给出的信号点矢量图， 就是定义在GF(2)上的3维矢量空间V3,V3=000，001，010，011，100，101，110，111,5.3.1 基本概念

15、,集合S中存在全零矢量（0,0,0），即零元； 集合S中任何两个矢量和仍在该集合中，即满足封闭性。,子空间如果n维矢量空间Vn的一个子集S，满足以下条件， 则称其为Vn的一个子空间：,矢量与码字的关系 一个码长为n的码字可以看成是一个有n个元素的矢量； 所有2n个n长码字就构成了定义在GF(2)上的n维矢量空间Vn ；,对于一个(n，k)线性分组码，其编码过程是从GF(2)上的n维矢 量空间Vn中，寻找其中遵循某种编码规则的一个子空间，而这 个字空间中的所有码字正好构成了一个加法交换群，所以线性 分组码又称为群码 。,5.3.1 基本概念,3线性分组码性质,封闭性,具有零元 即具有全零码，记作

16、A0 。,具有负元若Ai+ Aj =A0则称其互为码元，（n , k）中Ai是它本身的负元。,满足结合率和交换率,5.3.2 线性分组码编码,1生成距阵,矢量的线性无关 若Vn中k个矢量A1,A2,Ak，当且仅当 ，i=1,2,k时下式成立,空间的基,在任意一个矢量空间或者子空间中，至少存在一组线性无关的矢量，可以张成这个空间, 这一组矢量称为该空间的基，基中矢量的数目称为空间的维数。,5.3.2 线性分组码编码,实例分析,v1=(1000)，v2=(0100)，v3=(0010)，v4=(0001) 线性无关的，作为基，张成一个4维矢量空间V4：,5.3.2 线性分组码编码,生成矩阵,矩阵G

17、的每行矢量是基中的矢量，故称之为生成矩阵；有其可以得到矢量空间中的全部矢量；上例中选取的基得到的生成矩阵恰好是4阶单位矩阵，实际上线性无关的行矢量都可以作为生成矩阵的行矢量 。,2编码原理,线性分组码标记,（n，k）线性分组码，其码字通常记作： A=an-1 an-2 a0 1n信息码组M记作： M=mk-1 mk-2 m1 m0 1k,5.3.2 线性分组码编码,生成矩阵G记作 ：,编码过程,5.3.2 线性分组码编码,实例,假设一个(6，3)分组生成矩阵为：,编码过程为：,5.3.2 线性分组码编码,该(6，3)码是非系统码，信息元m2、m0、m1分别出现在码字A的第 1、3、5位，而2、

18、4、6位是编码器产生的监督码元其码表为：,5.3.2 线性分组码编码, 生成矩阵典型化,实例分析,3系统码编码原理, 编码过程,5.3.2 线性分组码编码, (6，3)系统分组码表,监督元与信息元之间的一般关系,5.3.2 线性分组码编码,注意到系统码中前k位即信息元，将其写成线性方程组的形式,监督关系,5.3.2 线性分组码编码, 监督矩阵,监督关系一般表达,或,生成矩阵典型阵一般形式,5.3.2 线性分组码编码,(n，k)分组码码字可表示为 ：,(n，k)码的一般编码过程,A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0,对上式两

19、边同时进行矩阵转置得：,5.3.2 线性分组码编码,也即,此时的系数矩阵，即监督矩阵为,5.3.2 线性分组码编码,生成矩阵和监督距阵的关系, (n，k)码的一般编码过程,根据需要选定一监督关系确定H阵； 求由H距阵和阵的关系确定G阵； 由A=MG生成所有码字。,5.3.2 线性分组码编码,伴随式S和错误图样E的关系,伴随式,二者并不是一一对应的关系，因为错误图样有2n种表现形 式，而伴随式仅有2r种表现形式，（注意r=n-kn），且其中 S=0说明传输无错，这在该(n，k)分组码用于检错时已足够。 但发生了错误却不能检出是完全有可能的，例如封闭性 错误。,4伴随式与检错原理,5.3.2 线性

20、分组码编码, (6，3)分组码的监督矩阵为：,实例分析,伴随式,5.3.2 线性分组码编码, (6，3)分组码伴随式计算电路,5.3.3 汉明码,将监督矩阵记成列矢量的形式，H=h0 h1 hn-2 hn-1，则,汉明码定义,伴随式和错误图样的关系,单个错误时的伴随式恰好与H的一个列矢量对应，只要H的各个 列矢量不为0矢量，且各不相同，则可以纠正单个错误。,5.3.3 汉明码,汉明码的另一种描述方式 ：对于任何的整数，必存在一个(n，k) 汉明码，码长n和监督元数目r=n-k满足 n=2r-1,汉明码特点, 可以纠正一位传输错误，且d0=3， 码长和监督员的关系：n=2r-1,实例分析(7，4

21、)汉明码,首先其监督矩阵，此时监督矩阵为H37， 3位二进制码元的组合有8种： 000、001、010、011、100、101、110、111 其中不全为零的7个正好可用作监督矩阵的列,可得到监督矩阵：,5.3.3 汉明码,任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵G,由A=MG得到其所有的码字，如下表所示：,5.3.3 汉明码,假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 此时对应的伴随式为：,5.3.3 汉明码,下表给出了该（7，4）汉明码单个错误的错误图样与其对应的伴 随式，可

22、以发现伴随式正是监督矩阵的每一列，且该列的位置恰 好是码元出错的位置。,由于S不时全零，可判断传输出错，而ST=0 1 1T，是监督矩阵H的第4列,这正是错误码元发生的位置,因此可以得到错误图样为E=0001000，进而按B+E即可纠错。,5.3.3 汉明码,完备性定义,汉明码完备码 性,5.3.4 循环码,一个(7，3)系统循环码 码表如下所示：,1基本概念,一类具有循环移位特性的线性分组码， 即其中的一个码字经过循环移位后仍然是该分组码的码字,定义,5.3.4 循环码,例如A4=0111001，对应的码多项式为 ：,码多项式,(n，k)循环码中，为了便于描述与计算，经常使用n-1次码多项式

23、 来表示码字，码字A =an-1 an-2 a1 a0 ，它对应的码多项式为：,A4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，即,5.3.4 循环码,对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该 问题的办法是对上式作模x7+1运算 ：,A7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为,其计算过程如下 ：,5.3.4 循环码,2生成多项式和生成矩阵,(n，k)循环码中的r=n-k次码多项式，其次数最低（0元除外）；其它所有的码多项式都能被g(x)整除；并且g(x)是xn+1的一个因式 。,生成多项式 g(x),例如本节前面给出的

24、(7，3)循环码，其生成多项式为：,5.3.4 循环码,若g(x)含有(x+1)因式，对应的(n，k)系统循环码， 能够检出所有奇数个错误；,(n，k)系统循环码检错能力与g(x)的关系,若g(x)含有常数项1因式，且不能整除xe+1， 则对应的(n，k)系统循环码，能够检出所有的两位错误；,若g(x)含有常数项1因式，对应的(n，k)系统循环码， 能够检出所有突发长度r的突发错误， 并且对突发长度等于r+1的突发错误的漏检率为2-(r-1)， 对突发长度大于r+1的突发错误的漏检率为2-r。,5.3.4 循环码,CRC-12：,标准生成多项式,CRC-16：,CRC-CCITT ：,CRC-

25、32：,5.3.4 循环码,g(x) 、x g(x)、x2 g(x)、xk-1 g(x)是(n，k)循环码的k个线性无 关的码字，所以可得其上乘距阵G，用码多项式表示G的各行：,生成矩阵G,若信息码组M= mk-1 mk-2 m0，则：,5.3.4 循环码,上式同时提供了循环码的一种编码方法，但由其得到的循环码 是非系统码，因为此时生成矩阵不是典型阵。,例如本节前面给出的(7，3)循环码，,将该矩阵典型化之后，再按照A=MG编码才能得到表本节前面 给出的系统(7，3)循环码；实际应用中，系统循环码的编译码通常是由g(x)经过简单的代数 运算来实现。,5.3.4 循环码,系统 (n，k)循环码码

26、字：,编码原理,用码多项式来表示为：,3编码,A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0,5.3.4 循环码,式中M(x)是信息码组码多项式，所以只需要确定r(x) 已知循环码的所有码字都能够被g(x)整除，r(x)可由下式确定：,(n，k)循环码的生成多项式为：,编码器,其中r=n-k，则该(n，k)系统循环码的编码电路如下图所示：,5.3.4 循环码,r级线性移位寄存器的初始状态为全零，所有开关均向下连通 ；,在寄存器时钟的控制下进行k次移位，输出M(x)的系数(即信息 码组)，同时实现除法电路的功能；,编码器工作过程,5.

27、3.4 循环码,所有开关向下连通，输入下一组信息重复上述过程。,实例分析,所有开关均倒向上方连通，在寄存器时钟的控制下再经过r=n-k 次移位，将监督元输出到信道；,本节前面给出的(7，3)循环码生成多项式：g(x)=x4+x2+x+1 由其可得编码电路如下图所示：,5.3.4 循环码,假设M=110，编码器工作过程如下表所示,5.3.4 循环码,现在检验上表编码结果，因为M=110，所以,即所得的码字为A=1100101 。,5.3.4 循环码,系统循环码的每一个码字都能够被生成多项式g(x)整除 ：,检错译码原理,发送端发送的码字为,3译码,接收的码字为,错误图样,伴随式,5.3.4 循环

28、码,可以证明：,若S等于0判定传输无错，否则判定传输出错 。,检错译码原理图 ：,5.3.4 循环码,寄存器置零，开关S向下连通；,在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即伴随式,(n，k)循环码伴随式计算电路,其工作过程如下：,将开关向上打开，经r=n-k次移位读出伴随式。,5.3.4 循环码,纠错译码原理,确定循环码的纠错能力;,根据 模g(x)计算伴随式，若S(x)则判定传输出错。,根据 模g(x)找到伴随式对应的错误图样,由A(x)=B(x)+E(x)纠错。,5.4 卷积码,本节内容提要：,卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编 译码原理。

29、,5.4.1 卷积编码器 5.4.2 卷积码的解析描述 5.4.3 卷积码的图解描述 5.4.4 维特比译码原理,5.4.1 卷积编码器,卷积码通常记作(n，k，m)， 其中k为一次移入编码器的比特数目， n为对应于k比特输入的编码输出， m为约束长度。,卷积码,定义卷积码的编码效率为k/n， 可以将其理解为同一时刻，编码器有k位比特信息输入， 有n位编码比特输出,卷积码有记忆的特性： 卷积编码器的输出不仅和当前输入的k比特信息有关， 而且还依赖于之前输入的m-1组k比特信息。,5.4.1 卷积编码器,(n，k，m)卷积编码器结构,5.4.1 卷积编码器,可以发现上图中mk级寄存器中第一级是多

30、余的，事实上只需要 m(k-1)级即可，所以可以得到卷积码编码器的另一种形式,5.4.1 卷积编码器,(3，1，3)卷积码的两种等效编码器,实例分析,3级编码器,2级编码器,5.4.2 卷积码的解析描述,仍然以上图中的(3，1，3)卷积码为例， 由其单位冲击响应可构造生成矩阵为：,生成矩阵法,其中未写出的元素为0。和分组码不同，卷积码并不以块的形式出现， 即其码字可能无限长，故5-68式所示的矩阵称为半无限矩阵,此时卷积码可由C=MG得到，例如M=11101时,5.4.2 卷积码的解析描述,卷积编码器也可以用n个生成多项式来描述， 分别对应n个输出支路。,生成多项式法, (3，1，3)卷积码编

31、码器,上图所示的卷积编码器可以用以下所示的3个生成多项式描述,5.4.2 卷积码的解析描述,则对应的码多项式为,所以对应的码字是：C=111 110 101 010 100 001 011,输入信息为M=11101，对应的多项式为 则各支路码多项式分别为：,5.4.2 卷积码的解析描述,5.4.3 卷积码的图解描述,实例分析以下图所示的(2，1，3)卷积码器,假设初始状态为a，输入序列为M=110100， 则有状态图很容易得到编码序列为C=100100011111。,状态图法,5.4.3 卷积码的图解描述,树图法,输入为110100时，编码输出为100100011111，如图中虚线所示,5.4.3 卷积码的图解描述,网格图法,5.4.4 维特比译码原理,END,返回,结束,