《通信原理精品课第八章差错控制编码课件.ppt》由会员分享,可在线阅读,更多相关《通信原理精品课第八章差错控制编码课件.ppt(68页珍藏版)》请在三一办公上搜索。
1、通信原理,主讲人:吴海涛 副教授TEL: 15819300159Email:,第1页,共61页,第8章 差错控制编码,8.1 概述8.2 常用的几种简单分组码8.3 线性分组码8.4 循环码8.5 小结,第2页,共68页,8.1 概述,8.1.1 信道编码,在数字通信中,根据不同的目的,编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率, 提高数字通信的可靠性而采取的编码。数字信号在传输过程中,加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能,可以加大发射功率,降低接收设备本身的噪声,以及合理选择调制、解调方
2、法等。此外,还可以采用信道编码技术。,第3页,共68页,8.1 概述,8.1.1 信道编码,另外,按照噪声或干扰的变化规律,可把信道分为三类:随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道,其中差错的出现是随机的,而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道, 错误是成串成群出现的,即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子,随机错误和成串错误都占有相当比例。对于不同类型的信道,应采用不同的差错控制方式。,第4页,共68页,8.1 概述,8.1.2 差错控制方式,图8-1 差错控制方式,第5页,共68页,8.1 概述,8.1.2 差
3、错控制方式,1. 前向纠错方式(80年代) 前向纠错方式记作FEC (Forward Error Correction)。发端发送能够纠正错误的码,收端收到信码后自动地纠正传输中的错误。在二进制码元的情况下,能够确定错码的位置,就相当于能够纠正错码。将错码“0”改为“1”或“1”改为“0”即可。其特点是单向传输,实时性好,但译码设备较复杂。,第6页,共68页,8.1 概述,8.1.2 差错控制方式,2. 检错重发方式(书上3种方式) 检错重发又称自动请求重传方式,记作ARQ(Automatic Repeat reQuest)。 由发端送出能够发现错误的码,由收端判决传输中有无错误产生,如果发现
4、错误,则通过反向信道把这一判决结果反馈给发端,然后,发端把收端认为错误的信息再次重发,从而达到正确传输的目的。其特点是需要反馈信道,译码设备简单,对突发错误和信道干扰较严重时有效, 但实时性差,主要在计算机数据通信与深空通信中得到应用。,第7页,共68页,8.1 概述,8.1.2 差错控制方式,图8-2 CFDP协议ARQ-延迟NAK模式,第8页,共68页,8.1 概述,8.1.2 差错控制方式,3. 混合纠错方式 混合纠错方式记作HEC(Hybrid Error Correction)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后,检查差错情况,如果错误
5、在码的纠错能力范围以内,则自动纠错,如果超过了码的纠错能力, 但能检测出来,则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点,可达到较低的误码率,因此, 近年来得到广泛应用。,第9页,共68页,8.1 概述,8.1.3 纠错码的分类,(1) 根据纠错码各码组信息元和监督元的函数关系,可分为线性码和非线性码。如果函数关系是线性的,即满足一组线性方程式,则称为线性码,否则为非线性码。(2) 根据上述关系涉及的范围,可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关;卷积码中的码元不仅与本组的信息元有关,而且还与前面若干组的信息元有关。(3) 根据码的用途,可分为检错码和纠错码
6、。检错码以检错为目的,不一定能纠错;而纠错码以纠错为目的,一定能检错。,第10页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,无论是具有检错能力还是纠错功能的编码,统称为纠错编码。现在用一个例子说明其原理。设有一种由3 个二进制码元构成的编码,共有8种不同的可能码组。若将其全部用来表示天气,则可以表示8种不同的天气。例如(1): 000晴 001云 010阴 011雨 100雪 101霜 110雾 111雹这时,若一个码组在传输中发生错码,则因接收端无法发现错码,而将收到错误信息。,第11页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,假设在此8种码组中仅允许使用4种来
7、传送天气。例如(2):000晴 011云 101阴 110雨为许用码组,其它4种为禁用码组。这时,接收端有可能发现(检测到)码组中的一个错码。例如:若000中有一个错码,则它可能错成100、010或001。但是这3种码组都是禁用码组,所以能够发现错码。不难验证,上面这4个码组的任一码元出错都将变成禁用码组,所以这种编码能发现一个错码。,第12页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,当000有3个错码时,它变成111,也是禁用码组,其它3个码组情况也是如此。所以这种编码也能发现3个错码。但是它不能发现2个错码,因为发生2个错码后得到的仍是许用码组。这种编码只能检错不能纠错。例
8、如,若接收到的码组为100,它是禁用码组,可以判断其中有错码。若这时只有1个错码,则000、110、101这3种许用码错了1个码元后都可能变成100。所以不能判断其中哪个码组是原发送码组,即不能纠正错误。要想纠正错误还要增大冗余度。,000晴 011云 101阴 110雨,第13页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,例如(3)规定 只许用两个码组:000晴 111雨其它都是禁用码组。这种编码能检测出两个以下的错码,或纠正一个错码。例如当收到“100”时,若采用的是纠错技术,则认为它是由“000(晴)”中第一位出错造成的,故纠正为“000(晴)”;若采用的是检错技术,它可以
9、发现两个以下的错码,即“000”错一位,或“111”错两位都可能变成“100”,故能发现此码组有错,但是不能纠错。从上面的例子可以建立“分组码”的概念。,第14页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,用例(2)的例子,由于4种信息用2比特就能代表,现在为了纠错用了3比特,加了一位监督位构成可一个具有纠错功能的独立码组,并且监督位仅监督本组中的信息码元,则称这种编码为分组码。,第15页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,1. 分组码分组码一般可用(n,k)表示。其中,k是每组二进制信息码元的数目,n是编码码组的码元总位数,又称为码组长度,简称码长。n-k
10、=r为每个码组中的监督码元数目。简单地说,分组码是对每段k位长的信息组以一定的规则增加r个监督元,组成长为n的码字。在二进制情况下,共有2k个不同的信息组,相应地可得到2k个不同的码字,称为许用码组。其余 2n-2k个码字未被选用,称为禁用码组。,第16页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,1. 分组码在分组码中,非零码元的数目称为码字的汉明重量, 简称码重。例如,码字 10110,码重w=3。两个等长码组之间对应位取值不同的数目称为这两个码组的汉明(Hamming)距离, 简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称
11、为码的最小距离,用d0表示。最小码距是码的一个重要参数, 它是衡量码检错、纠错能力的依据。,第17页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,2. 检错和纠错能力若分组码码字中的监督元在信息元之后,而且是信息元的简单重复,则称该分组码为重复码。它是一种简单实用的检错码, 并有一定的纠错能力。例如(2,1)重复码,两个许用码组是 00 与 11,d0=2,收端译码,出现 01、10 禁用码组时,可以发现传输中的一位错误。如果是(3,1)重复码,两个许用码组是 000 与111, d0=3; 当收端出现两个或三个 1 时,判为 1,否则判为 0。此时,可以纠正单个错误,或者该码可以
12、检出两个错误。,第18页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,3.码距的几何意义,一般而言,码距是 n 维空间中单位正多面体顶点间的汉明距离。,第19页,共68页,3位码组3维空间顶点坐标(a0,a1,a2 )各顶点之间沿立方体各边行走的几何距离。,8.1 概述,8.1.4 纠错编码的基本原理,4. 纠检错能力一种编码的纠检错能力:决定于最小码距d0的值。为了能检测e个错码,要求最小码距,设有一个码组A,它位于0点,若A中发生一个错码,则A的位置将移动到以0为中心,以1为半径的圆上。若A中发生2个错码,则。因此,若最小码距不小于3,例如图中B点为最小码距的码组,则当发生不多
13、于两个错码时,码组A的位置就不会移动到另一个许用码组B的位置上。P332,第20页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,4. 纠检错能力一种编码的纠检错能力:决定于最小码距d0的值。为了能纠正 t 个错码,要求最小码距,若A和B中的错码不多于两个,其位置均不会超出以2为半径的圆,因而不会错到另一个码组的范围内。若此编码中任意两个码组之间的码距都不小于5,则只要错码不超过两个就能够纠正。,判决规则为:若接收码组落于以A为圆心的圆上就判决收到的是码组A,若落于以B为圆心的圆上就判决为码组B。这样,就能够纠正两位错码。,第21页,共68页,8.1 概述,8.1.4 纠错编码的基本
14、原理,4. 纠检错能力一种编码的纠检错能力:决定于最小码距d0的值。为了能纠正t个错码,同时检测e个错码,要求最小码距 在解释公式之前,先来分析上图所示的例子。,第22页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,4. 纠检错能力,图中码组A和B之间距离为5。按照检错能力公式,最多能检测4个错码,即e = d0 1 = 5 1 = 4,按照纠错能力公式纠错时,能纠正2个错码。但是,不能同时做到两者,因为当错码位数超过纠错能力时,该码组立即进入另一码组的圆内而被错误地“纠正”了。例如,码组A若错了3位,就会被误认为码组B错了2位造成的结果,从而被错“纠”为B。这就说,检错和纠错公式
15、不能同时成立或同时运用。,第23页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,4. 纠检错能力,所以,为了在可以纠正t个错码的同时,能检测e个错码,需要码组A发生e个错码的位置与码组B的纠错范围至少距离为1,否则落在该纠错范围内就会被错误地“纠正”。纠检结合工作方式:当错码数量少时,系统按前向纠错方式工作,以节省重发时间,提高传输效率;当错码数量多时,系统按反馈重发的纠错方式工作,以降低系统的总误码率。,第24页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,纠检错能力总结:码的最小距离d0直接关系着码的检错和纠错能力;任一(n,k)分组码,若要在码字内: (1) 检测
16、e个随机错误,则要求码的最小距离d0e+1; (2) 纠正t个随机错误,则要求码的最小距离d02t+1; (3) 纠正t个同时检测e(t)个随机错误,则要求码的最小 距离d0t+e+1。,第25页,共68页,8.1 概述,8.1.4 纠错编码的基本原理,5.编码效率用差错控制编码提高通信系统的可靠性,是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中, k是信息元的个数,n为码长。对纠错码的基本要求是: 检错和纠错能力尽量强;编码效率尽量高;编码规律尽量简单。实际中要根据具体指标要求,保证有一定纠、检错能力和编码效率,并且易于实现。,第26页,共68页,8.2 常用的几
17、种简单分组码,8.2.1 奇偶监督码,奇偶监督码是在原信息码后面附加一个监督元,使得码组中“1”的个数是奇数或偶数。或者说,它是含一个监督元,码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。,第27页,共68页,8.2 常用的几种简单分组码,8.2.1 奇偶监督码,设码字A=an-1,an-2,a1,a0,对于偶监督码有式中,a0为监督码,其它为信息码。奇监督码情况相似,只是码组中“1”的数目为奇数,即满足 而检错能力与偶监督码相同。 奇偶监督码的编码效率R为,检奇数个错码,第28页,共68页,8.2 常用的几种简单分组码,8.2.2 行列监督码,图8-2 (6
18、6,50)行列监督码,又叫方阵码或矩形码,它的构造方法是先将若干奇偶监督码组按行排列成矩阵,再按列增加第二维监督位。,第29页,共68页,8.2 常用的几种简单分组码,8.2.3 恒比码,码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中,每个码组均含有相同数目的 1 和 0,因此恒比码又称等重码,定 1 码。这种码在检测时,只要计算接收码元中 1 的数目是否正确,就知道有无错误。,第30页,共68页,8.2 常用的几种简单分组码,8.2.3 恒比码,目前我国电传通信中普遍采用 3:2 码,又称“5 中取 3”的恒比码,即每个码组的长度为 5,其中 3 个“1”。这时可
19、能编成的不同码组数目等于从 5 中取 3 的组合数 10,这 10 个许用码组恰好可表示 10 个阿拉伯数字,如表 8-1 所示。而每个汉字(区位码)又是以四位十进制数来代表的(吴 4666 海 2603 涛 4446 )。实践证明,采用这种码后,我国汉字电报的差错率大为降低。,四码电报,第31页,共68页,表8-1 32 恒比码,8.2 常用的几种简单分组码,8.2.3 恒比码,由于汉字结构复杂,字型繁多,一字一“面孔”,拍电报不直接用电码来表示。因此,采用由四个阿拉伯数字代表一个汉字的方法,简称“四码电报”,中国汉字多达6万字,常用的汉字只有一万个,所以用10的4次方(10,000)来表示
20、。1873年,法国驻华人员威基杰(SAViguer)参照康熙字典的部首排列方法,挑选了常用汉字6800多个,编成了第一部汉字电码本,名为电报新书。后来,由我国的郑观应将其改编成为中国电报新编,这是中国最早的汉字电码本。,第32页,共68页,8.3 线性分组码,8.3.1 定义及性质,如果信息码元与监督码元之间的关系可以用一组线性方程来表示,且监督码元仅由本码组的信息码元来确定,而与其他码组的码元无关,则称该编码为线性分组码。线性分组码中信息码元和监督码元是用线性方程联系起来的。线性码建立在代数学群论基础上,线性码各许用码组的集合构成代数学中的群,因此又称群码。在群中只存在一种运算,即模2和,通
21、常四则运算中的加、减法在这里都是模2和的关系。所以后面将简化运算符号为“+”。,第33页,共68页,8.3 线性分组码,8.3.1 定义及性质,性质:封闭性:任意两个许用码组相加后(按位进行模2和,所得编码仍是许用码组)最小码距等于非零码的最小码重(除全0码外),第34页,共68页,8.3 线性分组码,8.3.1 定义及性质,现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0,其中前 4 位是信息元,后 3 位是监督元, 可用下列线性方程组来描述该分组码,产生监督元。,注意:+表示模2和,第35页,共68页,8.3 线性分组码,表 8-2 (
22、7,4)码的码字表,最小码距d0=?,第36页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,8-1,第37页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,并简记为 H AT = 0T 或A HT = 0A = a6 a5 a4 a3 a2 a1 a00 = 000右上标“T”表示将矩阵转置。将H称为监督矩阵。只要监督矩阵H给定,编码时监督位和信息位的关系就完全确定了。,第38页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,H矩阵的性质:(1) H的行数就是监督关系式的数目,它等于监督位的数目r。H的每行中“1”的位置表示相应码元
23、之间存在的监督关系。例如,H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分,例如,第39页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,其中,P为rk阶矩阵,Ir为rr阶单位矩阵。可以写成H =P Ir形式的矩阵称为典型监督矩阵。HAT=0T,说明H矩阵与码字的转置乘积必为零,可以用来作为判断接收码字A是否出错的依据。,第40页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,H矩阵的性质:(2) 由代数理论可知,H矩阵的各行应该是线性无关的,否则将得不到 r个线性无关的监督关系式,从而也得不到 r个独立的监督位
24、。若一矩阵能写成典型阵形式P Ir,则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的,故P Ir的各行也是线性无关的。,第41页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,若把监督方程补充为下列方程,第42页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,可改写为矩阵形式,第43页,共68页,8.3 线性分组码,8.3.2 监督矩阵H和生成矩阵G,G为生成矩阵,由它可以产生整个码组,具有Ik Q形式的生成矩阵称为典型生成矩阵。各行仍线性无关!,由典型生成矩阵得出的码组A中,信息位的位置不变,监督位附加于其后。这种形式的码称为系统码。,第4
25、4页,共68页,8.3 线性分组码,8.3.3伴随式(校正子)S,设发送码组A=an-1,an-2,a1,a0,在传输过程中可能发生误码。接收码组B=bn-1,bn-2,b1,b0,则收发码组之差定义为错误图样E, 也称为误差矢量, 即其中E=en-1,en-2,e1,e0,且,(8 - 2),当bi=ai,当biai,码元未错,码元有错,第45页,共68页,8.3 线性分组码,8.3.3伴随式(校正子)S,式(8 - 2)也可写作令S=BHT,称为伴随式或校正子。当H确定后,S只与E有关,而与A无关。这意味着S和错码E之间有确定的线性变换关系。若S和E有一一对应关系,则S将能代表错码位置。,
26、表示发送码组A与错码矩阵之和等于接收码组B,第46页,共68页,8.3 线性分组码,8.3.3伴随式(校正子)S,线性码有一个重要性质,就是它的封闭性。封闭性是指一种线性码中任意两个码组之和仍为这种编码 中的一个码组。也就是说,若A1和A2是一种线性码中的两个码组,则(A1+A2)仍是其中的一个码组。(证明),第47页,共68页,8.3 线性分组码,8.3.3伴随式(校正子)S,表 8-3 (7,4)码S与E的对应关系,第48页,共68页,检错能力?能纠错两个及以上?,8.4 循环码,8.4.1 定义,循环性是指任一码组循环(左移或右移)一位后仍然是该编码中的一个码组。(仍属于线性分组码),表
27、 8-4 一种(7, 3)循环码的全部码组,表中第4码组向右移一位即得到第2码组;第7码组向左移一位即得到第6码组。,第49页,共68页,8.4 循环码,8.4.1 定义,循环码的定义:如果 (n,k) 线性分组码的任意码矢A=(an1, an2, a0) 的 i 次循环移位,所得矢量A(i)=(an1i, an2i, , a0, an1, , ani) 仍是一个码矢,则称此线性码为 (n,k) 循环码。,第50页,共68页,8.4 循环码,8.4.1 定义,在代数理论中,为了便于计算,常用码多项式表示码字。(n,k)循环码的码字,其码多项式(以降幂顺序排列)为:注意:上式中x的值没有任何意义
28、,仅用它的幂代表码元的位置。例:码组1 1 0 0 1 0 1可以表示为,第51页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,如果一种码的所有码多项式都是多项式g(x)的倍式,则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表 8-4 的(7,3)循环码中,,第52页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,其它码多项式都是g(x)的倍式, 即,第53页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,循环码的生成矩阵常用多项式的形式来表示,在循环码中,一个(n, k)码有2k个不同的码组。若
29、用g(x)表示其中前(k-1)位皆为“0”的码组,则g(x),x g(x),x2 g(x),xk-1 g(x)都是码组,而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,若前k位为0会怎样?,由于G是k行n列的矩阵,因此若能找到k个线性无关的已知码组,就能构成矩阵G。,为什么?,第54页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,在循环码中除全“0”码组外,再没有连续k位均为“0”的码组,即连“0”的长度最多只能有(k-1)位。否则,在经过若干次循环移位后将得到一个k位信息位全为“0”,但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此,g
30、(x)必须是一个常数项不为“0”的(n-k)次多项式,而且这个g(x)还是这种(n, k)码中次数为(nk)的唯一多项式。,为什么常数项不为0?(n-1)-(k-1)=n-k=r,第55页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,因为如果有两个,则由码的封闭性,把这两个相加也应该是一个码组,且此码组多项式的次数将小于(n k),即连续“0”的个数多于(k 1)。显然,这是与前面的结论矛盾的,故是不可能的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x),则整个(n, k)循环码就被确定了。,第56页,共68页,8.4 循环码,8.4.2 生成多项
31、式及生成矩阵,例如(7,3)循环码,n=7, k=3, r=4, 其生成多项式及生成矩阵分别为,不同于P341表5,右式不符合G = Ik Q形式,所以它不是典型生成矩阵。但它经过线性变换后,不难化成典型阵。,第57页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,如何寻找任一(n, k)循环码的生成多项式 ?由上式可知,任一循环码多项式A(x)都是g(x)的倍式,故它可以写成A(x) = h(x)g(x)而生成多项式g(x)本身也是一个码组,即有 A(x) = g(x)由于码组A (x)是一个(n k)次多项式,故xk A (x)是一个n次多项式。由下式,第58页,共68页,8
32、.4 循环码,8.4.2 生成多项式及生成矩阵,如何寻找任一(n, k)循环码的生成多项式 ?可知,xk A (x)在模(xn + 1)运算下也是一个码组,故可以写成,在循环码中,若A(x)是一个长为n的许用码组,则xiA(x)在模xn+1运算下,所得到码组也是该编码中的一个许用码组。P342,且一个长为n的循环码必定为按模(xn+1)运算的一个余式。 P343说明,第59页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,上式左端分子和分母都是n次多项式,故商式Q(x) = 1。因此,上式可以化成将A(x)和A(x)表示式代入上式,经过化简后得到上式表明,生成多项式g(x)应该是
33、(xn + 1)的一个因子。,第60页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,这一结论为我们寻找循环码的生成多项式指出了一条道路,即循环码的生成多项式应该是(xn +1)的一个(n k)次因式。例如,(x7 + 1)可以分解为为了求(7, 3)循环码的生成多项式g(x),需要从上式中找到一个(n k) = 4次的因子。不难看出,这样的因子有两个,即,第61页,共68页,8.4 循环码,8.4.2 生成多项式及生成矩阵,以上两式都可作为生成多项式。不过,选用的生成多项式不同,产生出的循环码码组也不同。结论:生成多项式g(x)是一个常数项为1,最高次数为(n-k)次,且是xn
34、+1的一个因式。,第62页,共68页,8.4 循环码,8.4.3 循环码的编码方法,1、由信息码与生成矩阵G(x)相乘产生,一般此法得到的是非系统码,如将G(x)化为典型阵,它是系统码。2、 A(x) = xn - k m(x) + r(x),属于系统码。循环码的编码原则:在编码时,首先要根据给定的(n, k)值选定生成多项式g(x),即从(xn + 1)的因子中选一个(n - k)次多项式作为g(x)。由于所有码多项式T(x)都可以被g(x)整除。根据这条原则,就可以对给定的信息位进行编码:,第63页,共68页,8.4 循环码,8.4.3 循环码的编码方法,循环码的编码原则:设m(x)为信息
35、码多项式,其次数小于k。用xn - k乘m(x),得到的xn-k m(x)的次数必定小于n。用g(x)除xn - k m(x),得到余式r(x),r(x)的次数必定小于g(x)的次数,即小于(n k)。将此余式r(x)加于信息位之后作为监督位,即将r(x)和xn - k m(x)相加,得到的多项式必定是一个码多项式。因为它必须能被g(x)整除,且商的次数不大于(k 1)。,第64页,共68页,8.4 循环码,8.4.3 循环码的编码方法,循环码的编码步骤:(1)用xn - k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如,信息码为110,它相当于m(x) = x2 + x
36、。当n k = 7 3 = 4时,xn - k m(x) = x4 (x2 + x) = x6 + x5,它相当于1100000。(2)用g(x)除xn - k m(x),得到商Q(x)和余式r(x),即,第65页,共68页,8.4 循环码,8.4.3 循环码的编码方法,例如,若选定g(x) = x4 + x2 + x + 1,则 上式相当于(3)编出的码组为A(x) = xn - k m(x) + r(x) 在上例中,A(x) = 1100000 + 101 = 1100101,它就是P341表5中的第7码组。可见,编码的核心是如何确定余式r(x)。,第66页,共68页,8.5 小结,作业:习题:P371 3、6 、7、8,第67页,共68页,下课,再见!,第68页,共68页,