差错控制与信道编码.ppt

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

2、.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)重复码: 1

5、1”- 晴,“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，当 = Ci时,函数L可以取得最大值,则认为C = Ci 。,5.1.2 信道编码,线性码和非线性码 若f()是线性函数称为线性码 若f()是非线性函数则称为非线性编码,信道编码的分类,信道编码器函数关系式为：,分组码和卷积码 分组码：每个信息码组M通过运算产生

7、对应的A ，记作(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 基于信道编码的差错控制方式,前向纠错（FEC: Forward Error Correction）方式,原理 采用纠错码,收端发现错误后自动纠正。,特点 无需重发，解码延迟固定，实时性好 无需

9、反馈信道，能用于单向传输信道，特别适用于单点向多点同时传送的方式 编码效率较低，需较大的冗余度（通常约25-50%）,译码设备比较复杂 纠错码须与信道特性相匹配，对信道变化的适应性较差 若错误超出纠错码纠错能力,只好将其抛弃,应用 移动通信系统,5.1.3 基于信道编码的差错控制方式,反馈重传（ARQ: Automatic Repeat Request）方式,原理 采用检错码，接收端发现错误后，给发送端一个反馈信号，要求重新发送，直到正确为止。,特点 编码效率比较高，只需少量的冗余码（约5-20%）就能获得极低的传输误码率；对信道的适应能力强 必须有反馈信道，故不能用于单向传输系统和同播系统

10、控制规程和过程比较复杂 重发导致信道的有效利用率较低，通信的实时性较差 由于反馈重传的随机性，故不适于实时传输系统,5.1.3 基于信道编码的差错控制方式,反馈重传（ARQ: Automatic Repeat Request）方式,工作方式 发送等待 连续工作方式 混合方式,应用 数据通信系统,5.1.3 基于信道编码的差错控制方式,混合纠错（HEC: Hybrid Error Correction）方式,原理 采用纠检错码，是ARQ和FEC方式的折衷方案,特点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性,应用 移动通信系统 ，数据传输系统（特别是在

11、使用卫星信道等高时延、大容量的信道传输数据信号时更具优势）,5.1.3 基于信道编码的差错控制方式,信息反馈（IRQ: Information Repeat Request ）方式,原理 也称回程校验方式，在发端来检测错误。,特点 无需采用纠检错编码，故设备和控制由于规程较简单； 需一条与前向信道相同的反馈信道； 由于采用发端检错，相当于信息传输距离增加一倍，可能导致额外的差错和重传； 可能使整个通信系统的传信率很低； 收发两端需较大容量的存储器来存储传输信息。,5.2 常用的简单信道编码,本节内容提要：,检错码在ARQ系统中使用，其生成方式简单，易于实现，检错效果较好，因此得到广泛的应用，本

12、节将介绍奇偶校验码、行列监督码、恒比码 、正反码的编译码规则、特性以及应用情况。,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行)

13、和垂直方向(共M列) ,同时进行奇偶监督的码， 记作（LM+L+M+1 , LM）。,(66，50)行列监督码的一个码字,该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比 较严重的通信中。,5.2.2 行列监督码,行列监督码（水平垂直一致校验码或g方阵码） 根据按列或按行的次序传输，分别能发现小于等于M+1或L+1长度的突发性错误；,可以检出某些偶数个随机误差； 当传输差错数正好为4的倍数，而且构成矩形的四个角，则不能发现这类差错。,5.2.3 恒比码,恒比码（等比码，定比码，等重码） 从所有一定长度的二进制序列中选取“1”数目相同的序列作为码字； 该码的特点是码字中1，0数目恒定，亦

14、即1，0数目之比恒定。,目前我国电传通信中普遍采用3：2码，又称5中取3码，如下所示,国际上通用的ARQ电报通信系统中，采用7中取3码。 可以检测所有奇数个错误和部分偶数个错误。 主要优点是简单易实现。,5.2.4 重复码, (3，1)重复码两个码字为000和111，其最小码距为3； (n，1)重复码也只有全0码和全1码两个码字，其最小码距为n， 却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大； 该码随码长增加，具有很强的纠检错能力，但其编码效率的急 剧下降； 重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。,重复码 重复码只有一位信息码元，监督码元是信息码元的重复，

15、 所以仅有两个码字；,5.2.5 正反码,正反码 该码型多用于10单位码的前向纠错设备中，可以纠正一位错误， 发现全部两个以下的错误，以及大部分两个以上的错误，其本质 就是五单位码的重复；,编码规则 信息码组中1的数目为奇数时，监督码是信息码的重复即正码； 信息码组中1的数目为偶数时，监督码是信息码的反码。,译码方法 首先将收到的码字中的信息位和监督位按对应位作模2运算， 得到一个5位码组，若该码字中有奇数个1，则将其作为校验码 组，若有偶数个1，则取其反码作为校验码组。然后，按照下表 进行纠检错译码,5.2.5 正反码,正反码错误判决表,5.3 线性分组码,本节内容提要：,本节将对线性分组码

16、的特点、编译码规则以及应用情况作介绍，主要包括以下四方面内容。,5.3.1 基本概念 5.3.2 线性分组码编码 5.3.3 汉明码 5.3.4 循环码,5.3.1 基本概念,1有限域,定义了加法“+”和乘法“”两种运算的有限集合； q个元素的有限域又称为伽罗瓦域，记作GF(q)； 对域的逆元操作又演绎出了减法“”和除法运算“”，,域具有封闭特性,域中总包含惟一的加法恒等元“0”和乘法恒等元“1”,5.3.1 基本概念,域中任意元素存在惟一的加法逆元 域中任意非零元都存在惟一的乘法逆元 于是减法和除法运算可定义为：,域中元素满足交换律、结合律和分配律运算规则：,5.3.1 基本概念,GF(q)

17、中定义的是模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 基本概念,集合S中存在全零矢量（0,0,0），即零元； 集合S中任何两个矢量和仍在该集合中，即满足封闭性。,子空间 如果n维矢量空间Vn的一

18、个子集S，满足以下条件，则称其为Vn的一个子空间：,矢量与码字的关系 一个码长为n的码字可以看成是一个有n个元素的矢量； 所有2n个n长码字就构成了定义在GF(2)(两个元素：0、1的伽罗瓦域)上的n维矢量空间Vn ；,对于一个(n，k)线性分组码，其编码过程是从GF(2)上的n维矢 量空间Vn中，寻找其中遵循某种编码规则的一个子空间，而这 个子空间中的所有码字正好构成了一个加法交换群，所以线性 分组码又称为群码 。,5.3.1 基本概念,3线性分组码性质,封闭性,具有零元 即具有全零码，记作A0 。,具有负元 若Ai+ Aj =A0则称其互为负元，（n , k）中Ai是它本身的负元。,满足结

19、合率和交换率,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的每行矢量是基中的矢量，故称之为生成矩阵； 由其可以得到矢量空间中的全部矢量； 上例中选取的基得到的

20、生成矩阵恰好是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、4、6位是编码器产生的监督码元，其码表为：,5.3.2 线性分组码编码, 生成矩阵典型化,实例

21、分析,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,对上式两边同时进行矩阵转置得：,5.3.2 线性分组码编码,也即,此时的系数矩阵，即监督矩阵为,5.

22、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 线性分组码编码, (6，3)分组码的监督矩阵为：,实例分析,伴随式,5.3.2 线性分组码编码, (6

23、，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)汉明码,首先构造其监督矩阵，此时监督矩阵为H37， 3位二进制码元的组合有8种

24、： 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）汉明码单个错误的错误图样与其对应的伴 随式，可以发现伴随式正是监督矩阵的每一列，且该列的位置恰 好是码元出错的位置。,

25、由于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次码多项式 来表示码字，码字A =an-1 an-2 a1 a0 ，它对应的码多

26、项式为：,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),例如本节前面给出的(7，3)循环码，其生成多项式为：,5.3.4 循环码,若g(x)

27、含有(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-32：,5.3.4 循环码,g(x) 、x g(x)、x2 g(x

28、)、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)循环码码字：,编码原理,用码多项式来表示为：,3编码,A =an-1 a

29、n-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.3.4 循环码,所有开关向下连通，输入下一组信息重复上述过程。,

30、实例分析,所有开关均倒向上方连通，在寄存器时钟的控制下再经过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 循环码,可以证明：,若S等于0判定传输无错，否则判定传输出错 。,检错译码原理图 ：,5.3.4 循环码,寄存器置零，开关S向下连通；,在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即伴随式,(n，k)循环码伴随式计算电路,其工作过程如下：,将开关向上打开，经r=n-k次移位读出伴随式。,5.3.4 循环码,纠错译码原理,确定循环码的纠错能力;,根据 模g(x)计算伴随式，若S(x)不为零则判定传输出错。,根据 模g(x)找到