电力系统远动原理及技术.ppt

电力系统远动原理及技术,第四章 远动信息的信道编译码,4.1 概 述,在远动系统中，远动装置采集的信息必须通过通信通道传输到调度控制中心才能使用（上行）调度控制中心下达到各厂站端的命令同样也必须通过通信通道才能传送到各厂站端的远动装置（下行）因此通信信道是远动系统中的重要组成部分。,1、信道编码,原因：通信信道各种干扰，使远动信息在传输时，由于干扰而发生差错，从而降低远动信息的可靠性。目的：使要传送的信息有较好的抗干扰能力。信道编码又称为抗干扰编码。措施；在信息进入通信线路之前，对它加以改造、保护形成码字，使码字的内容结构具有一定的规律性和相关性，当信息受到干扰后能根据码字原有的内在规律性和相关性，发现甚至纠正错误，达到恢复原来信息的目的。,2、信道编码的方法,信道编码的一般方法：对信源编码得到的序列，按照某种规律，添加一定数量的监督码元，由信息序列和监督码元构成一个有抗干扰能力的码字，添加监督码元的规律或规则不同，就形成了不同的编码方法。远动信息的信道编码常用编码方法有：奇偶加正反校验码、BCH码、等比码、卷积码等。目前主要采用的是BCH码。,BCH码,名称由来：三个人的名字。优点：有效纠正多个随机错误，具有循环码的优点，编译码容易实现。结果：国际电工委员会和我国的远动标准都要求用此编码方式进行抗干扰的编码。,4.2信道编码的基本原则,数字传输系统模型,1、图4-1数字通信系统模型,信源,信源编码,信道编码,调制器,通信,解调器,信道译码,信源译码,信宿,s,m,c,干扰,r,m*,s*,2、信源,信源：信源就是指各种参数，状态和命令，可以是开关的合闸或跳闸状态，也可以是电压、功率等的数值。信源的输出可以是连续变化的模拟信号，也可以是离散的数字信号。,3、信源编码（有效性编码）,信源编码是将各种形式的信源，经变送器，模数转换电路或其它各种编码电路变成离散的代码。信源编码原则：一是使代表信源s的码元数尽可能少；二是要能能够从信息序列m重构原来的信源s。,3、信源编码（例）,以信源是4个状态为例，如果信源编码采用两位二进制数的信息序列，则00、01、10、11可分别代表信源的四种状态，其二进制数的个数最少，且能重构原来的四种状态。若采用一位或三位二进制数，就不能同时满足上述两点要求。故信源编码又称有效性编码。,4、信道编码的作用,信道编码的作用是根据一定的规则，在信息序列m中添加一些码元，将信息序列m变成较原来长的二进制数字序列c，称为码字。信道编码的目的是提高信息序列m的抗干扰能力。,5、调制器的作用,调制器的作用是将用数字序列表示的码字c，变换成适合于传输的信号形式，送入信道，电力系统远动装置中，常采用数字调频或数字调相的方法，将码字c中的每个码字“0”或“1”，变成不同的两种载波频率或两种载波相位。,6、信道的类型,电力载波微波散射波光纤通道等,7、信道中的干扰源,远动系统中的噪音由雷电、弧光、电火花、天线电台频率干扰、多路通信的跳闸干扰等所引起。任何远动系统环境中，干扰是永远存在的，不同的信道具有不同的干扰源，信道编码就是抗信道干扰的措施之一。,7、信道中的干扰（3）,码字在信道中穿送时受到干扰的情况，可用错误图样e来表示。如果e中的所有位不全为“0”。则按收码字r肯定和发送码字c不完全相同，即信息在信道中受到了干扰。,错误图样,有了错误图样与接收码字就可以得到正确的发送码字了吗？错误图样是我们为了研究信道中的干扰而提出的一个物理模型。错误图样并不真正存在于发送过程中。错误图样是我们通过信道译码纠正了干扰后得到的一个序列，而不是通过错误图样进行译码。（先后顺序）,8、信道译码,信道译码就是根据按收码字r及信道编码规则，检查或纠正按收码字r中的错误码元，产生出发送码字c的估计值c*，并从c*中还原出信息序列m的估计值m*。,9、信源译码,信源译码是根据信源编码规则，将按受到的信息序列m*转变为原信源s的估计值s*，并送给显示系统显示或执行对象执行，这里在显示或执行就是我们所说的“信宿”，也称为“受信者”。,11提高信息传输可靠性的措施,提高信息传输可靠性的措施之一，是设计出性能良好的信道编码器和译码器。1 提高传输率。2 码字的抗干扰能力强。,12、数字传输中的干扰,随机干扰：如果干扰对每个码元的影响是独立的，与前后码元无关，这种干扰称为随机干扰。突发干扰：如果干扰一旦发生，不但影响某一个码元，而且同时引起前后某些码元的错误，错误之间具有相关性，这种干扰称为突发干扰。,13、实际信道中的干扰,实际干扰类型：随机干扰和突发干扰并存的通道称为复合通道。对应措施：对于复合通道，我们应该对它的干扰所产生的错误进行统计分析，掌握其错误出现的规律，以便采用一种有针对性的信道编码方法。,最大似然译码（原理性）,原理性，并非实际采用的译码方式。研究对象载体：信道中受干扰情况与信道的特性有关，最简单而最典型的信道是二进制对称信道，简称BSC信道。,BSC信道的特征,按收码元与发送码元相同的概率，为码元正确按收概率q；（q0.5）按收码元与发送码元相反的概率，为码元错误概率p。(p0.5)P+Q=1(要么正确，要么错误)假设信道对发送码元的影响是独立的。,最大似然译码（原理）,名称理解：最相似（量化就是按位计算条件概率）原理：在按收到码字后，信道译码器对信道编码器可能输出的所有码字c，计算它们的条件概率。若对可能的发送码字条件概率最大，则认为码字就是发送码字，可将收到的译为发送码字，这种译码方案称为最大似然译码。（对于一个编码方案来说，所有的码子是一个有限的集合）,最大似然译码（计算）,条件概率 可表达如下：（4-1）式中，当 时，当 时，,最大似然译码（计算公式改写）,令 为发送码字 与接收码字不同的码元位数，则（4-1）式可改写为：（4-2）注意：不具有实际操作性，只是原理描述,分析,由于二进制对称信道中PQ，所以条件概率随不同码元个数（D）的增大而减小。所以按条件概率最大来寻找发送码字，等效于寻找与按收码字不同的码元位数最少的发送码字。,最大似然译码（实质）,因此，最大似然译码就是判断发端可能发送的所有码字中，哪个码字与接接收码字 最相似。与 最相似的码字，两者之间不同的码元位数 最小，按（4-2）式算出的条件概率必然最大。（例子）,最小距离译码的检纠错能力（1）汉明距离,汉明距离（码距）：是指两个码元位数相同的码字之间，对应码元位不相同码元的数目。计算：按位异或后求和 或者是模2加。,最小距离译码的检纠错能力（2）,知道了码距的概念，我们就知道，对于最大似然译码来说，就是找到与接收到的码字距离最小的码字，并认为此码字就是发送端想要发送的码字。,关于码距在编码中的一个定义,在一种码的所有 码字的集合当中，任意两个码字之间的码距不一 定相同，我们将所有可能的码字之间的码距的最 小值称为这个码字集合的最小值，记为dmin。,最小距离译码的检纠错能力（3）汉明重量,汉明重量（码重）：码字中非零码元的个数，用w表示。在二进制情况下，它就是码字中1码元的个数，若码字则其码重为：（4-4）,最小距离译码的检纠错能力（4）,前提：在一个线性码中任意两个码字v和u相加，得到的码字v+u一定在该线性码中。当v和u中对应位上的码元不同时，在v+u的码字中对应位上的码元是1，否则为0，由此可得出等式：（4-5）该式说明：一个线性码中，任意两个码字之间的汉明距离正好等于这两个码字相加所得到的另一个码字的汉明重量。,重量与距离的联系区别,重量是一个码字的运算距离是两个码字的运算联系是公式4-5,关于线性码的一些结论,一个线性码的所有码字中，如果某两个码字之间的码距最小，则它们之间的码距可以代表该线性码的最小距离。同时，这两个码字的和一定为该线性码字中的另一个码字，这个码字的重量一定最小。因此，一个线性码的最小距离等于它的非零码字的最小重量。,最小距离译码的检纠错能力（7）,一种码的最小距离是衡量这种码抗干扰能力（检纠错能力）的重要参数。对最小距离为dmin的码，它能纠正的码字中的错误码元的个数t和能检出的码字中的错误码元个数l满足如下关系式：,最小距离译码的检纠错能力（8）,纠错能力：（4-6）检错能力：（4-7）同时检错和纠错的能力：（4-8）最小码距与码的检、纠错能力之间的关系，可以用图形作几何解释。,举例:只传输两个信息(断路器分合闸保护动作未动作-开关量),直观上讲，可以只用一位长度的码字即可。选取0，1分别表示合闸、跳闸显然，这个编码方式下，码的最小距离为1。即dmin=1。无检错、纠错能力验证：无论哪个码字受到干扰，都将变为另一个码字，因此接收端无法知道是否受到了干扰。,如果用两位长度的码字即可。选取00，11分别表示合闸、跳闸显然，这个编码方式下，码的最小距离为2。即dmin=2。可检错1位、无纠错能力验证（检错）：发送的码字00，11只受到1位的干扰，即变为01，10，接收端就可以知道此码字受到了干扰，可以检出一位干扰造成的错误。如果受到了2位的干扰，即变为11，00，则接收端无法知道此码字受到了干扰，不能检错。验证（纠错）：发送的码字受到1位的干扰，变为01，10，由于受到干扰的码字与发送的码字（00，11）的相似程度相同，因此接收端无法纠正错误。,如果用三位长度的码字即可。选取000，111分别表示合闸、跳闸显然，这个编码方式下，码的最小距离为3。即dmin=3。可检错2位、纠错1位验证（检错）：（受到1位干扰同前）发送的码字000，111受到2位的干扰，接收端就可以知道此码字受到了干扰，可以检出2位干扰造成的错误。如果受到了3位的干扰，即变为111，000，则接收端无法知道此码字受到了干扰，不能检错。验证（纠错）：发送的码字受到1位的干扰，如001则可以判断是000码字受到了干扰，纠正错误，译码为000,最小距离译码的检纠错能力（17）,抗干扰编码就是对信源编码得到的k位信息序列，按照某种规律添加r位新码元（称为监督元），达到增大码的最小距离的目的。经抗干扰编码后得到的码字，其码元位数（称码长），编码效率。,最小距离译码的检纠错能力（18）,添加监督元的规律或规则不同，便形成不同的码元方法，对编码方法的选择原则：一是：要使新选择的编码方法能够检测出或纠正信道中最可能出现的错误图样（前述根据不同的信道选择不同的编码方式）；二要：提高编码效率，即在保证可靠性的前提下，尽量减少监督元的数目（有侧重性）；三要：使选择的方法易于实现（比如，选择消息序列在前、监督序列在后的编码方式）。,结论,增加码字的距离可以增加码字的抗干扰能力，即增加检错，纠错的能力。但是增加距离就必须增加监督元（附加信息），会使信息编码的效率降低。矛盾：两者是矛盾的，因此，在实践中应当选取适当的编码方式，适合工程需求。（比如，远动应用的4840码4032码等）,4.3信道编码的代数基础,码字中的信息元和监督元之间按一定的代数关系互相约束，这种编码属于代数编码。这里只有介绍我们常用到的一些基本的理论。,元，集的概念（简单介绍）,元，就是元素，可能是数、点、线、面等集，即集合，是一些元素的集体表示。域，一个非空域上的元满足一些特定运算规则，则称此集为域。例如，有理数集中包括的元是所有的有理数，对于加法和乘法运算，结果也在这个集中。则可以说，有理数集对于加法和乘法来说是一个域，有理数域。下面来看伽罗华域,伽罗华域及域上多项式（1）,设F式一个非空集合，在F中定义加法和乘法两种代数差异，若F对这两种运算满足自封，并满足以下运算规则：,伽罗华域及域上多项式（2）,加法：对任意，有 对任意，有；若F中有易个元素位0，任意，有：；对任意，有；,伽罗华域及域上多项式（3）,乘法：对任意，有；对任意，有；，存在易元素，具有性质；，则，有,伽罗华域及域上多项式（4）,在加法与乘法间满足分配规律：，有：，则F对于所规定的加法和乘法运算式是一个域。,伽罗华域及域上多项式（5）,如果域F中的元素个数无限，称F为无限域；元素个数有限，称F为有限域，也称为伽罗华域。具有两个元素0和1，且加法和乘法运算按模2加模2乘法运算的有限域称为二元域，记为GF（2）。后面的分析都在这个域上。,伽罗华域及域上多项式（6）,模2加法运算规则是，模2乘法运算规则是 11=1，00=0，01=0，10=0以后为了书写上的方便，将直接用+和号表示 和。,域上多项式的概念（用来表示信息序列）,假如一个多项式的所有系数 和未知数x是某域上的元素，则称这个多项式是该域上的多项式，域上多项式可表示为：（4-9）在GF（2）上的多项式，系数和未知数x的取值只能是0或1，对 的单项式为，的单项式为。,伽罗华域及域上多项式（8）,在信道编码中，经常用多项式来代表一个信息序列或码字，这种多项式称为消息多项式。注意：多项式种的x不再有未知数的概念，只代表系数 所处的位置，而系数 则代表码元的取值。例如 二进制序列1101101，可用二元域上的多项式 来等效地表示，而可表示为二元域上的多项式,二元域上的矢量空间及矩阵,为何要研究二元域（计算机信息的表示方法）为何要研究其上的矢量空间与矩阵（一种编码中的码字有很多个，每一个码字就是一个序列，序列中的信息是有先后顺序的，我们可以当成一个矢量，研究一个编码就需要研究其中所有码字的集合）,二元域上的矢量空间及矩阵（1）,对于二进制序列，可以是0，也可以是1，取值等于二元域GF（2）中的元素，通常称这个序列为GF（2）上的n重，n位序列可以构成 个不同的n重。所有二进制n重的集合称为GF（2）上的矢量空间，记作，其中的任何一个n重，称为矢量，也称为码矢。,矢量运算法则（加法、乘法按位）,矢量运算法则,一个二进制n重v与GF（2）中任一元素的标乘定义为：由于 取值为0或1，则 的值只有两种：全0n重，或是原来的n重。,正交,如果矢量空间中两个矢量V，U，满足,则称两个矢量正交，反之，称为非正交矢量,子空间定义,由矢量空间 中的部分矢量构成的集合称为 的子集，若子集s中包含全0矢量，并且s中任何两个矢量的和也在s中，则称子集s为矢量空间 的子空间。,矢量的线性相关性,全是矢量空间中的k个矢量，这k个矢量的线性组合构成另一个矢量：（4-10）若只有 为全0时，才能得到 为全0矢量，则称 是线性无关的。反之，则称为线性相关的。,举例（线性相关）,对于4维的一组矢量（1100）（1010）（1011）（1101）如果取各矢量的系数分别为1，1，1，1，则U=（0000），说明这组矢量是线性相关的。,举例（线性无关）,对于4维的一组矢量（1000）（0100）（0010）（0001）无论取得何种不全为0的系数组合，U都不可能为全零矢量（0000），说明这组矢量是线性无关的。,注意：,一组矢量要么是相关的，否则必然是无关的。在研究了矢量的相关性之后，我们来看基底、维数的概念,二元域上的矢量空间及矩阵（6）,前提：是一组线性无关的矢量。（保证唯一性）若一个矢量空间中的每一个矢量，都等于一组矢量的线性组合，则称这组矢量张成这个矢量空间。基底：这组张成矢量称为被张成矢量空间的基底维数：而基底中矢量的个数称为被张成矢量空间的维数。,拓展到矩阵中,一个k行n列的kn矩阵排列如下：（4-11）,行空间,位于阵列中带i行和第i列的元素 若只取GF（2）中的元素（0或1），则称G为域GF（2）上的一个kn矩阵，矩阵G中每一行是一个二进制n 重，每一列是一个二进制k重，若矩阵G的k行 是 中的k个线性无关的n重，则G的所有行的线性组合构成的一个k维子空间，称它为矩阵G的行空间。,零化空间,对于任何具有k个线性无关行的GF（2）上的kn矩阵，总存在一个 距阵H，（4-12）,零化空间,它的n-k行也是线性无关的，而且KH矩阵G的任意行 与（N-K）N矩阵H的任意行都正交，即（4-13）引申:矩阵G的行空间中的任意矢量v与矩阵H的行空间中的任意矢量n都是正交的.结论:我们称为G的行空间是H的零化空间，同样，H的行空间也是G的零化空间。,结论,前提:由于矩阵G和H之间的这种性质 方法:得到了编译码的方法 编码:在线性分组码的编码中，用G的行空间中的 个n重作为许用码字发送出去.译码:以矩阵H为校验矩阵，检查按收码字是否与H的各行正交。,编译码方法提示：,由前述，知道寻找到了G就可以解决便宜码的问题，那么G怎么找？（由定义知道是找到K个线性无关的N重）问题：是否可以检测出所有的干扰？,各个概念之间的关系(N维),矢量空间,K维子空间,基底,矩阵G,张成,线性组合构成,包含,监督码的增加方法有多种多样，不同的方法构成的码的特性各不相同。那么线性分组码的监督元增加的方法是？,4.4 线性分组码的编译码lineal normed code,码字个数,若码字中有K位为消息码元，有R位监督码元，则码长n=k+r。K位消息位可能取 种不同的取值，因此这样的码的码字数目为 个。,按照码字监督元的监督范围分类,卷积码：监督范围超出本码字的消息。分组码：监督范围未超出本码字的消息。,线性分组码定义,若一个分组码中 的个码字，恰好是矢量空间V 的一个K维子空间，称分组码为线性分组码。,包含全0码,码字加法运算自封,问题转换：,寻找线性分组码,寻找K维子空间,寻找行空间矩阵G,寻找K个线性无关的N重,根据线性分组码定义,根据行空间定义,根据G定义,得到线性分组码,与消息位线性组合,注意,如果K个线性无关的N重选择的不同，则生成的线性分组码不同。,生成矩阵G的概念,根据式（414），选择K个线性无关的n重，以消息码元为函数进行组合，便生成一个（n,k）线性分组码，因此有：,4.4.2 线性分组码的生成矩阵(2),写成分相形式,4.4.2 线性分组码的生成矩阵(3),=mG（4-15）,称G为（n,k）线性分组码的生成矩阵,结论（分析4-15）,一旦生成矩阵G选定，（n,k）线性分组码也就唯一地确定了。,举例：,选取N=6，K=3，因此，在64个6重中选择三个线性无关的6重。如：100110，010011，001101。则按照与8个消息组线性组合，可以得到8个码字，这8个码字构成一个（6，3）线性分组码。,系统码定义,生成的码字前k位是消息元，后r(nk)位是监督元，这种形式的码称为系统码，满足系统码形式的线性分组码称为系统线性分组码。,系统线性分组码生成,由前述知道，G一旦确定，则线性分组码便确定了，很显然，如果要找系统码，则需要找到一个特殊的G，这个特定的G可以生成的具有系统码特征的系统线性分组码。,线性分组码,生成矩阵G,唯一确定,特殊生成矩阵G,唯一确定,系统线性分组码,具有特定性质,满足系统码性质,系统线性分组码的生成矩阵,如果生成矩阵G的前部分是k*k的单位阵，由它生成的线性分组码为：,将其计算展开（验证）,前K位，很明显是消息位,后N-K位，很明显是监督位，监督位是消息位的线性组合,满足系统线性分组码的定义,举例前述的例子，我们选取生成矩阵为,001101010011100110,单位阵,4.4.2 线性分组码的生成矩阵(7),另外，任意一位监督元与消息元之间的关系由下面的一致校验方能确定：()(417),4.4.3 线性分组码的一致校验矩阵(1),前述：（对任何矩阵G，总存在矩阵H，使得G的行空间中的任意一个矢量和矩阵H的任一行正交）编码：对于某个生成矩阵G，可以得到码字。译码：对于某个码字，若H与码字正交，认为正确，否则认为受到了干扰。结论：对某一个编码来说，需要知道G和H，Z 这样就可以完成编译码工作了。,一致校验矩阵H的确定,因此在确定了G之后，需要确定H，为正确译码提供依据。其关系是：注意G和H的维数，很显然，由G就可以得到H,由生成矩阵G得到一致校验矩阵H,1 0 0 p11 p12 p1(n-k)0 1 0 p21 p22 p2(n-k).0 0 pn1 pn2 pk(n-k),G=,(4-（18),由生成矩阵G得到一致校验矩阵H,(419),举例：还是（6，3）码,100110010011001101,101100110010011001,G H,4.4.4 接收码字的伴随式,由一致校验矩阵H的定义可以知道，码字和H有下式成立：（0 0 0）（4-22）,定义伴随式（考虑到错误图样）,接收码字R为发送码字e和错误图样e的模之和，即：R=c+e(4-23)我们定义它为接收码字的伴随式S:S=RHT(4-24),4.4.4 接收码字的伴随式（4）,若错误图样e=(00.0),则R=C，S=RHT=CHT=（000）。当E(000)时，S=RHT=(c+e)HT=CHT+eHT=eHT 此时，只要错误图样E不等于线性分组码中的码字总有S=eHT（00.0）。,接收码字的伴随式计算结果分析,当错误图样E和发送端的某一发送码字相同时，会使S=eHT=0，出现错误判断结果。为什么？按照定义e=c 所以，eHT=cHT=0 因此，任何一种编码方法都不可能检测和纠 正所有可能的错误。,4.5 循环码的编译码原理,循环码是线性分组码的一重要子类，在远动装置中被广泛的应用。举例，CDT规约中用的（48，40）码（40，32码）都是循环码。为何多用循环码？（循环码有些便于工程实际的性质）,循环码是线性分组码的子类,如果一个（N，K）线性分组码，它的2K个码字中的任一码字的任何次循环移位，得到的任然是这个线性分组码中的码字，这个线性分组码称为循环码。在工程实际中，移位是很容易实现的，不论怎样的CPU：1、一定有移位指令（软件）2、一定有某个寄存器可以记录溢出位（硬件）,4.5.1 循环码的基本概念（2）,码字C用码多项式表示，如下：（4-25）乘以x并除以（xn+1）求其余式,4.5.1 循环码的基本概念（3）,余式 恰是码字c循环移位一次后码字c（1）对应的码多项式c（1）（x）。可见将循环码的码字c循环左移一位，相当于将该码字的码多项式c（x）乘以x并除以（xn+1）后所得的余式。,加两个CN-1,4.5.1 循环码的基本概念（4）,同理可证，将码字c循环左移i次，相当于将码多项式c（x）乘以xi并除以（xn+1）后所得余式，该余式为：（4-27）由于xn+1=0 mod（xn+1）或xn=1 mod（xn+1）所以用xn+1为模作除法的物理意义就是在首尾相连的n级循环移位寄存器中作循环移位，将最高的溢出（次数=n的位）循环反馈至最低位上。,为什么工程实际中需要？,这些特性使循环码编码的实现伴随式的计算得以简化（译码）。1.在一个（n，k）循环码中，有一个并且只有一个n-k次码的多项式g（x），即（4-28）（n，k）循环码中的每一个码多项式c（x）都是g（x）的倍式，并且每个为g(x)倍式的次数小于或等于（n-1）次的多项式，一定是一个码多项式。(充分必要 等价命题),性质一代数表示,由这一特性可知，（n，k）循环码中的每个码多项式c（x）都可表示成：（4-29）对消息m（x）的编码相当于用消息m（x）乘以g（x）。结论:所以多项式g（x）确定了由2k个消息生成的2k个码字。我们称多项式g（x）为循环码的生成多项式。,与线性分组码对比,生成矩阵,生成多项式,校验矩阵,余式,4.5.1 循环码的基本概念（7）,2.（n，k）循环码的生成多项式g（x）是xn+1的一个因式，即（4-30）3.若g（x）是一个n-k次多项式，且是xn+1的因式，则g（x）生成一个（n，k）循环码。,性质分析,特性1 可以生成一个NK循环码,必须首先找到生成多项式g（x），它的次数为n-k。特性2 给出了寻找g（x）的方法。码字生成:最后以这个n-k次的因式为生成多项式，用它分别乘以2k个不同的消息，便可得到（n，k）循环码的2k个码字。对比一般线性分组码,容易了,例,以（7,4）循环码为例，其生成过程如下：首先分解，找出 次的因式。因为，所以要找的生成多项式。对消息多项式，取m3 m2 m1 m0为十六种不同的序列，完成运算 运算结果即为（7.4）循环码的十六个码字。,(N,K)循环码的不唯一性,当我们从式子xn+1中分解n-k次的因式时，有时分解方法不是唯一的，这时要找的生成多项式也就不是唯一的。如果用不同的生成多项式对2k个消息编码可以得到不同的码字，从而形成码字不同而码长和消息位相同的多个（n，k）循环码。仍以（7.4）循环码为例，由于 若选择 可生成（7.4）循环码。,再引入系统性质,循环码分为非系统循环码和系统循环码。实现非系统循环码的编码只要根据码长n和消息位k选定生成多项式g（x），再完成m（x）g（x）的乘法运算，便得到消息多项式m（x）对应的循环码的码多项式c（x）。在信道译码时，要从非系统循环码的码字中得到消息位，不十分方便。因此，这种码使用较少，一般多采用系统循环码。,其编码方法,（n，k）系统循环码的编码过程是：首先把消息多项式m（x）乘以xn-k，得到 xn-km（x）；然后以生成多项式g（x）去除xn-km（x），如果商为q（x），余式为r（x），则xn-km（x）=q（x）g（x）+r（x）；最后用r（x）模2加xn-km（x），便得到所需的系统循环码码字c（x）=xn-km（x）+r（x）。即系统循环码是一种消息位在前，监督位在后的结构。,其编码方法验证,当我们把m（x）乘以xn-k时，消息多项式的变化是：（4-31）对多项式中的消息位mi，原来是xi的系数，乘xn-k后变成了xi+n-k的系数，x增加了n-k次。由于消息多项式中x的次数代表消息元的位置，这样做等于把k个消息元的位置往前移动了n-k位，且没有改变消息元的取值。同时在消息元的后面空出了n-k个零位，以便补充监督元。,其编码方法验证,用g（x）去除xn-km（x）时，得到等式（4-32）只要在等式两边同时模2加余式r（x）得到：（4-33）,其编码方法验证,明显看出，式（4-33）左边的多项式是生成多项式g的倍式，且次数小于或等于n-1次。根据前面叙述的循环码的特性1，它一定是（n，k）循环码的码多项式。又因为xn-km（x）的最低次项是m0 xn-k，余式r（x）的最高次项是rn-k-1xn-k-1，所以式（4-33）左边的多项式可写成：（4-34）,4.5.2 系统循环码的编译码原理(6),式（4-34）右边的多项式对应的n位序列（mk-1 mk-2 m1 m0 rn-k-1 r1 r0），前k位是消息位，后（n-k）位是余式的系数，于是这n位序列构成系统码结构的码字。因此，我们得到的是一个系统循环码的码字：（4-35）,译码,用生成多项式去除接收码字，检查余式是否为零（也就是检查接受码字是否是生成多项式的倍式）。余式为零，认为接收码字是发送码字；余式不为零，认为接收码字是不发送码字。,编码举例,仍以（7.4）码为例，设生成多项式，对消息 进行系统循环码的编码，其过程如下：,4.5.2 系统循环码的编译码原理(9),由 得：所以=（1 1 1 1 1 1 1）当消息取十六种不同的值时，按同样方法生 成的十六个系统循环码码字。,与循环码相比,编码复杂了些译码简单多了(一致校验、信息提取),4.5.3 缩短循环码(1),生成码长为n，消息位为k的循环码，依靠从中分解出一个n-k次的因式作生成多项式。如果对于我们要求的码长n和消息位k，在因式分解式中，不存在n-k的因式，则可用缩短循环码来产生我们需要的（n，k）码。,（48，40）码,就是缩短循环码，由（127，120）码来，,（127，120）,（127，119）,（48，40）,增余删信,缩短,为了理解缩短循环码，我们先观察一个（7.4）系统循环码的十六个码字：,c=m3 m2 m1 m0 r2 r1 r0 0 0 0 0 x x x 0 0 0 1 x x x 0 0 1 0 x x x 0 0 1 1 x x x 0 1 0 0 x x x 0 1 0 1 x x x 0 1 1 0 x x x 0 1 1 1 x x x,1 0 0 0 x x x1 0 0 1 x x x1 0 1 0 x x x1 0 1 1 x x x1 1 0 0 x x x1 1 0 1 x x x1 1 1 0 x x x1 1 1 1 x x x,4.5.3 缩短循环码(3),在2k=24=16个码字中，有 的码字 消息最高位m3=0。由于对消息编码时，消息中高位的零在计算中不起作用，所以它不影响余式。如果我们删去这8个码字最高位的零，可以得到8个码长为6的码字，构成一个（6.3）码。1、这个码的监督元位数和原来的（7.4）码相同。2、可以用原来（7.4）码的生成多项式g（x），按同样的系统循环码的编码方法来生成。称这个（6.3）码为原来（7.4）系统循环码的缩短循环码。,4.5.3 缩短循环码(4),同理在16个码字中，有1/4的码字（2k-2=4）前两位消息为零。当删去这4个消息的前两位零时，得到4个码长为5的码字，构成一个（5.2）码。也称为原（7.4）系统循环码的缩短循环码。它的码长和消息位同时减少了二位，是（n-2，k-2）码。,一般定义,一般来讲，在任何一个给定的（n，k）系统循环码的2k个码字中，一定存在 个前位为零的码字。如果删去这 个码字中前面位零，可得 个长为（n-）的码字，由他们构成的（n-，k-）线性系统码，称为原（n，k）系统循环码的缩短循环码。,缩短循环码的实质,由于缩短循环码只取了原系统循环码中的部分码字，并删去了码字前面的零，故缩短循环码的码字不再满足任一码字的任何次循环仍是这个码中的码字，所以它已不是循环码。,那为什么还要用缩短循环码？,缩短循环码删去的是原系统循环码码字前面的零，它不影响由消息生成码字时的运算过程和运算结果，所以缩短循环码可采用原系统循环码的编码电路、检纠错译码电路及编译码算法。它的检纠错能力不低于原来的（n，k）系统循环码。,缩短循环码的生成,前面我们要生成的（n，k）码，如果在xn+1中不能分解出（n-k）次的因式，可以另外找出一个n，使nn，并使其在xn+1中存在（n-k）次的因式g（x）。另n=n+，我们可以先用g（x）生成一个码长为n的码。因为g（x）为（n-k）次的因式，它生成的码监督元必为n-k位，故消息位。,生成（n，k）码,不能分解出（n-k）次的因式,找不到g,生成（N，K）码（N=n+）、（K=k+）,增加码长,缩短成（n，k）码,4.6.1 软件表算法一(1),(n,k）系统循环码对消息多项式m(x)的编码就是求m(x)的监督元，即求m(x)除以g(x)所得到的算式，可以表示为(4-36)（4-37）,4.6.1 软件表算法一(2),设消息多项式m(x)，它对应的消息序列为 m=,按长度nk将消息序列分段，有m=(),其中 都是长度等于nk的消息段，最后一个消息段 位，这时消息多项式可以写成 m(x)=(4-38),4.6.1 软件表算法一(3),其中 为第i段消息的多项式，即 必须注意的是每个分段的多项式的次数和原多项式在原消息序列中的多项式的次数相同。,4.6.1 软件表算法一(4),对m(x)编码时，求余式的除法运算是；(4-39),4.6.1 软件表算法一(5),将（4-39）式各开得到的第一项是：=(4-40)其中 运算为求多项式的次数的运算。,4.6.1 软件表算法一(6),将（4-39）式展开的第二项是（4-41）,4.6.1 软件表算法一(7),将（4-40）式中的第二项与（4-41）相加得(4-42),4.6.1 软件表算法一(8),以此类推，（4-39）式的第i项是(4-43),4.6.1 软件表算法一(9),将（4-39）式第（i-1）相中含有余式 的相，同（4-43）式相加得：(4-44),4.6.1 软件表算法一(10),（4-39）式第p项与（p1）项中含有余式 的项相加得：（4-45）,4.6.1 软件表算法一(11),可见，（4-39）式的展开式之和是：,4.6.1 软件表算法一(12),=,(4-46),4.6.1 软件表算法(13),其中,4.6.1 软件表算法一(14),由（4-46）式可以得到，系统循环码编码时，求 除以g(x)的余式可以采用对消息段分段求余式的方法，求消息段的余式时，除第一消息段直接用 乘 除以g(x)外，从第二个消息段起，每个消息段先和前一消息段的余式模之加再乘以，然后除以g(x)的最后余式，故称它们为消息段的部分余式。,4.6.1 软件表算法一(15),当g(x)为nk次多项式时，按算法1消息段分为nk长的序列，求部分余式就是在nk位序列后面添加nk个0（导致于），再除以g(x)求余式。而长为nk位的二进制序列最多只有 个不同取值，这就决定了部分余式也只有 种。,4.6.1 软件表算法一(16),因此，可以把 种nk长位的二进制序列所对应的 种部分余式预先计算出来，在内存中建立一个部分余式存放表，以后对任何长为k位的消息编码时，只需根据各消息段的取值，直接查表找到对应的部分余式即可，这就避免了对每个消息段进行一次求部分余式的计算，这个部分余式表称为软件表，因此，这种算法又称为软件表算法。,4.6.1 软件表算法一(17),综上所述，用nk次生成多项式g(x)对长为k位二进制消息进行（nk）系统循环码的编码时，软件算法1步骤如下：1、将 个长为nk位的二进制序列分别添加nk个0，再分别除以生成多项式对应的二进制序列，将所得 个部分余式存于内存之中，作为以知软件表；2、把消息序列m按nk的长度划分为消息段 若最后一个消息段 不是nk位，将 后面添加零，补足成长nk位的新消息段。,4.6.1 软件表算法一(18),3、由已知软件表对应的部分余式（即 除以g(x)所得的余式）；4、对i=2，计算新消息段，并查找 对应的部分余式；5、对I=3、4、r重复步骤4，直到求出 并查出 对应的部分余式；6、计算，将 后面补0，补零个数等于 的位数，得到；,4.6.1 软件表算法一(19),7、计算 的余式r(x),该余式为最后余式，此时得到消息m(x)编出的系统循环码码字为：当消息序列长正好是nk的整数倍时，即k=p(nk)划分消息段不存在，软件表算法1只要进行到步骤5，便得到最后余式。在软件表算法1中，部分余式的个数和部分余式的长度都于nk有关，当nk太大时，软件表占内存的容量将比较大，因此，软件表算法1一般用在nk比较小的情况。,4.6.1 软件表算法二(1),在nk比较大时，为了减少软件表所占内存单元，可采用软件表算法2。软件表算法2对消息序列的分段按照nk为偶数和nk为奇数两种情况处理。首先讨论nk为偶数时的情况，将消息序列m划分和(nk)/2长的消息段M,最后一个不是(nk)/2长的消息段记为,4.6.1 软件表算法二(2),消息序列 对应的多项式为:因此有：（4-47）,4.6.1 软件表算法二(3),它的展开式中第一项可以写成：=（4-48）,4.6.1 软件表算法二(4),其中,4.6.1 软件表算法二(5),（4-47）式第二项可以写成（4-49）,4.6.1 软件表算法二(6),将（4-48）式第二项同式（4-49）相加得：（4-50）,举例,生成48，40码,G=100000111M=11001011,11100011,10100001,00111101,00000001M1=11001011，查表，余式为01111111与M2求和，查表余式为11011101与M3求和，查表余式为01110011与M4求和，查表余式为11101101与M5求和，查表余式为10001010所以，C=M+r=11001011,11100011,10100001,00111101,00000001，10001010,译码,同样的方法，先将最后的余式求出，与接收到的码子的校验位求和结果为0则正确，否则不正确,