管理信息学-信息编码.ppt

《管理信息学-信息编码.ppt》由会员分享，可在线阅读，更多相关《管理信息学-信息编码.ppt（83页珍藏版）》请在三一办公上搜索。

1、信 息 编 码,信息编码的目的：（1）为了信息在通信传输(空间上的转移)、存储(时间上的转移)等过程中的高效、准确而进行的编码。保持数据的正确性仅依赖于器件与设备的可靠运算是不行的，应该对信息进行编码使其具有纠错能力，这种编码也称为语法信息编码。（2）为了信息在收集、处理、表示上的方便、规范而进行的编码，一般表示一定的实际含义，也称为语义信息编码。,4.1 语法信息编码概念,二元数字信息：是用二元数域F2=0,1中的数字0与1组成的数组或向量 F2中的加法运算：0+0=1+1=0，0+1=1+0=1 F2中的乘法运算：11=1，10=01=00=0 通常用同样长度的二元数组代表一个信息集合中的

2、信息。例如，可用32个长为5的二元数组代表26个英文字母与6个标点符号，这样任何一篇英文文章便可以用长为5的二元数字信息表示。,4.1 语法信息编码概念,抗干扰编码：数字信息在传送过程中会受到各种可能的干扰而出现错误，这样收到的信息可能就不是传送的原信息。抗干扰的有效做法是在采用种种技术措施的同时，在信息传送前进行一次抗干扰编码，再传送抗干扰编码后的数字信息。抗干扰编码有检错编码与纠错编码，检错编码是检查有无错误发生的编码，纠错编码是能纠正已发生错误的编码。,4.1 语法信息编码概念,例(奇偶校验码)：设原信息是长为5的二元向量,c=(c0,c1,c2,c3,c4),在传送前编码(含纠错码)如

3、下：显然有(c)的6个分量之和为0。传送(c)，设收到的向量是r=(r0,r1,r2,r3,r4,r5)，则：若，则在传送过程中一定发生了错误，且有奇数个分量发生了错误；否则传送过程可能没有发生错误，也可能发生了偶数个错误。,4.1 语法信息编码概念,定义4.1 设原信息集合是F2上k维向量组成的向量空间Vk，是Vk到Vn的一个单射(nk)，则称Vk的全体象C=(Vk)为码，C中的每一个n维向量为码字，码字的分量称为码元。如果任一码字在传送过程中有t个错误发生，而收信方可以检查出有无错误发生，则称这个码C可以检查t个差错的检错码，并称为检错编码；如果收信方可以从收到的字正确译出发送方发送的码字

4、，则称码C是可以纠正t个差错的纠错码，并称为纠错编码。称k为信息长度，n为码长，k/n为码C的信息率。,4.2 极大似然译码法,如果在传送过程中，传送任何一个信息是否发生错误与前面已传送的信息是否发生了错误无关，则称这种传送为无记忆传送。在无记忆传送过程中，如果发送1收到0的概率与发送0收到1的概率都是p，且发送1收到1的概率与发送0收到0的概率都是1-p，即错误传送的概率为p，正确传送概率为1-p，则称这种传送为二元对称传送。一般p远小于1/2。,二元对称传送,4.2 极大似然译码法,定义4.2 在二元对称传送中，若收到字，则称发送码字 而收到A的概率为前向传送概率。如果发送码字CA收到A的

5、前向传送概率达到最大值，即则将A译为CA，称这种译码方法为极大似然译码法（Maximum Likelihood Decoding）。如果收到字A，而满足上述条件的CA不惟一，若将A译为任一满足条件的CA，则称这种译码方法为完全极大似然译码法；若发现CA不惟一，则不译此码字，要求发送方重新发送一次的译码方法称为不完全极大似然译码法。,在二元对称传送中，如果收到字，则对任何码字，其前向传送概率为其中e是传送码字c时发生错误的分量个数，因为p1/2，故当e最小时，前向传送概率达到最大。从而极大似然译码法是将A译为与A对应分量不同的分量个数最少的码字。,4.2 极大似然译码法,定义4.3 设称X与Y对

6、应分量不相等的分量个数为X与Y的汉明(Hamming)距离，记为d(X,Y)。若记 则,4.2 极大似然译码法,汉明距离性质：(1)(非负且有界性)0d(X,Y)n；(2)(自反性)d(X,Y)=0当且仅当X=Y；(3)(对称性)d(X,Y)=d(Y,X)；(4)(三角不等式)d(X,Z)d(X,Y)+d(Y,Z)设收到字A，在所有码字中，如果c是与A的汉明距离最小的码字，即c是发生传送错误分量个数最少的码字而成为A的，从而在所有码字中，c是前向传送概率最大而成为A的码字，因此应将A译为c，从而等价于将A译成与A的汉明距离最小的码字。,4.2 极大似然译码法,例1 设码C=0000，0011，

7、1000，1100，0001，1001，在二元对称传送中，如果收到A=0111，试问根据极大似然译码法，应将A译为哪一个码字?解：先计算汉明距离，再判断。在码字个数较少，码长较小的情况下，译码是容易实现的；而当码字数量很大(如军事通信中码字一般多达2100个)，上述译码方法几乎不可能实现，因此编码的任务之一是要找出有很好数学结构的码，以便译码方便。,4.2 极大似然译码法,码C的极小距离 定义4.4 设C是至少包含2个码字的码，称为码C的极小距离。若码长为n极小距离为d的码C含有M个码字，则称C是(n,M,d)码。例：在码长为5的码C=00000，00011，00111，11111中，由于d(

8、00011，00111)=1，而其他任何两个不同码字的汉明距离都2，故d(C)=1，从而C是(5，4，1)码。,4.2 极大似然译码法,定理4.1 设C是码长为n的二元码。(1)若d(C)t+1，则C是可以检查t个差错的检错码；若d(C)=t+1，则C是不能检查t+1个差错的检错码。(2)若d(C)2t+1，则C是可以纠正t个差错的纠错码；若d(C)=2t+1，则C是不能纠正t+1个差错的纠错码。证明(略),4.2 极大似然译码法,极大似然译码法要将接收到的字A与码C中的每一个码字结合计算前向传送概率或汉明距离，当n较大或码字较多时，译码工作量十分巨大。因此研究并构造具有很好数学结构的码具有非

9、常重要的意义。线性码是最基础的也是最重要的码。1.有限域上的线性空间称是F2上的n维线性空间 定义4.5 设C是F2上线性空间V的非空子集，如果C也是F2上线性空间，则称C是V的子空间。,4.3 二元线性码,容易证明，F2上线性空间V的非空子集是子空间的充要条件是：对，恒有 若，容易证明是V的子空间，并称S是由 生成的子空间，记为S=span。,4.3 二元线性码,定义4.6 设则称为X与Y的内积；如果XY=0，则称X与Y正交。定理4.2 设C是F2上线性空间 的子空间，令则 是 的子空间，且。证明(略)。,4.3 二元线性码,2.线性码的生成矩阵与校验矩阵 定义4.7 称 的任一子空间C是长

10、为n的线性码，并称子空间C的维数为线性码C的维数，仍记为dim C。并记长为n维数为k的线性码为n，k线性码。设 是线性空间 的子空间C的正交补子空间，则 也是长为n的线性码，称 是线性码C的对偶码；当 时，称C是自对偶码。定理4.3 设C是长为n的二元线性码，则(1)C恰好含有 个码字；(2)当C是自对偶码时，。,4.3 二元线性码,4.3 二元线性码,4.3 二元线性码,4.3 二元线性码,3.线性码的汉明重量 定义4.10 设X F2n，称X的非零分量个数为X的汉明重量，记为wt(X)，并称wt(C)=minwt(X)|X C,X0为线性码C的汉明重量。定理4.5 设C是二元线性码，则C

11、的汉明重量等于C的汉明距离，即d(C)=wt(C)。(证明略)定理4.6 设H是二元n，k线性码C的校验矩阵，如果H的任意t列都线性无关，且H有t+1列线性相关，则(1)d(C)=wt(C)=t+1(2)C是可检t个错误的检错码，且C是可纠t/2个错误的纠错码,4.3 二元线性码,4.系统码 设C是二元n,k线性码，则两个kn矩阵G与G1都是C的生成矩阵，当且仅当G1与G的行向量组都是线性空间C在F2上的基，当且仅当G1与G的行向量组等价，当且仅当G与G1行等价。设C1与C2是两个二元n,k线性码，如果当且仅当其中 是1，2，n的一个全排列，则称线性码C1与C2等价。显然，线性码之间的等价是等

12、价关系。,4.3 二元线性码,定义4.11 称以如下形式矩阵为生成矩阵的n,k线性码为系统码。若C是一个系统码，G0为其生成矩阵，则对任何原信息：其对应的码字为其中前k个分量为原始信息，后n-k个分量是校验信息。定理4.7 任一线性码都等价于一个系统码。,4.3 二元线性码,4.4 线性码的编码与译码,1.线性码的编码 设C是n,k线性码，则C恰好含有2k个码字。设 G=1,2,kT是C的生成矩阵，对，则存在惟一一组常数使另一方面，对任意一组常数则即 惟一决定一个码字。,4.4 线性码的编码与译码,因此，对若令则是对原始信息集合F2n的一个编码。2.线性码的译码在实际问题中当n较大或码字个数巨

13、大时，译码工作非常困难，甚至无法实现。下面利用线性码的特点，降低译码的计算量及难度。,4.4 线性码的编码与译码,设是C的校验矩阵；设是收到的字。如果，则X是C中一个码字，否则X不是C中码字，传送中出现了错误。利用陪集概念引入校验子，简化译码过程。,4.4 线性码的编码与译码,定义4.12 设C是F2上线性码，对XF2n，称集合为X所在的陪集，有时也记为X+C。定理4.8 设C是二元n，k线性码，则(1)F2n中每个向量一定在C的某个陪集中，且两个不同的陪集不相交，所有陪集的并为F2n；(2)对X、YF2n，则X与Y属于C的同一个陪集，当且仅当X-Y C；(3)对XF2n，则 恰好含有2k个向

14、量，且F2n关于C恰好有2n-k个不同陪集。,定义4.13 设 是二元n,k线性码的生成矩阵，对，称为字X的校验子。显然，即S(X)是 维向量。定理4.9 设C是n,k线性码，则对 有(1)S(X+Y)=S(X)+S(Y)(2)XC当且仅当S(X)=0(3)S(X)=S(Y)当且仅当X与Y在C的同一个陪集中，即(4)共有 个不同的校验子 称一个陪集中汉明重量最小的向量为该陪集的陪集头。,4.4 线性码的编码与译码,利用校验子的译码过程（1）构造n，k线性码C的译码表：将F2n中2n个向量排成2n-k行2k列的一个表，表中有一条虚线将2n-k行分成上下两个部分；F2n关于C的每一个陪集中2k个向

15、量排在同一行，将C中的向量排在第1行，将零码字排在第1行的第1列，并将C中的2k-1个非零码字任意排在第1行的第2列一直到第2k列；将F2n关于C的其余2n-k-1个不同陪集排成2n-k-1行，并将每个陪集的校验子放在此行的最左边，作为标记；若某个陪集中，有惟一的陪集头X，则将此行排在译码表中虚线的上方部分，将陪集头,4.4 线性码的编码与译码,X 排在这一行的第1列，并将 排在码字c同一列；若某一陪集中有多个陪集头，则将该行排在译码表中虚线下方部分，且任取一个陪集头X排在该行的第一列，也将 排在码字c的同一列。（2）根据译码表译码：当收到字为A时，先计算A的校验子S(A)=A，如果S(A)=

16、0，则将A译为A；否则检查校验子S(A)是否在虚线上方，若在虚线上方，则将A译为第一行中与A同列的码字c；如果校验子S(A)在虚线下方，则无法译码。定理4.10 上述译码方法符合极大似然译码原理。,4.4 线性码的编码与译码,例2 设C是二元6，3线性码，其校验矩阵为（1）该列码C的译码表；（2）设收到的字A1=110110,A2=111111，试译A1,A2。解：（1）由HX=0得线性方程组,4.4 线性码的编码与译码,解得该方程组的基础解系为则C的生成矩阵为当 取 中每一个向量时，由 可得C的所有码字为,4.4 线性码的编码与译码,按线性码译码表的列法，将上述码字排在第一行，其中码字000

17、000排在第一列，其它码字可按任意顺序排。将F26关于C的其余26-3-1=7个陪集在虚线上方或下方按其校验子从小到大的顺序排成7行，即可得C的译码表,4.4 线性码的编码与译码,（2）对收到的字A1=110110，计算A1的校验子：在校验子所在的列找到S(A1)=101，由于101在虚线上方，因此在101所在的行找到字A1=110110。由译码表知，字A1=110110所在列对应的第一行的码字为110100。由译码原理知，应将A1译为110100。类似地，A2=111111的校验子为111，由于(111)在虚线下方，故无法译码。,4.4 线性码的编码与译码,由于线性码的数学结构太简单，因此译

18、码依然很困难，如译100，80线性码时，必须从2100-80=220个校验子中找到S(A)，再从280个字中找到A，这样工作量依然很大。循环码比线性码有更多的代数结构。循环码是使用最为广泛的一种编码。下面介绍的相关数学知识，证明都省略了。1.代数基础知识,4.5 循 环 码,定义4.15 设G是一个非空集合，在G内定义了一个二元运算“”，对，恒有惟一确定的cG使，如果此二元运算满足(1)(结合律)有。(2)(幺元存在性)存在eG，对 有。(3)(逆元存在性)对 都存在bG使，并称b是a的逆元素，记为，则称 是一个群。如果对，有，则称群G为交换群。如果G的非空子集S在G的二元运算下也构成群，则称

19、S是G的子群。,4.5 循 环 码,定义4.16 设在非空集合R中定义了加法和乘法两种二元运算，如果(1)R在加法运算下为群；(2)对a,b,cR，有(ab)c=a(bc)，(a+b)c=ac+bc，a(b+c)=ab+ac则称(R,+,)为一个环。若对a,bR有ab=ba，则称R为交换环。若a0，b0满足ab=0，则称a与b为零因子。称没有零因子的交换环为整环。,4.5 循 环 码,定义4.17 设S是环R的非空子集，如果：(1)，则；(2)有。则称S是环R的一个理想。当R是有幺元的交换环时，容易证明是R的一个理想，其中。称这个理想是由元素a生成的主理想，记为S=(a)。若S是R的理想，对，

20、记，容易证明，对，则 或 与 没有公共元素，即不相交，且 的充要条件是。,4.5 循 环 码,定理4.11 设S是环R的一个理想，令 则是一个环，称R/S是R关于理想S的剩余类环或商环，记为 记 则易证F2x是有幺元的交换环，且F2x的理想都是主理想。对 则 是 关于理想(f(x)的剩余类环，经常将 简记为。,4.5 循 环 码,2.循环码及其生成多项式 定义4.18 设C是二元n，k线性码，如果对 都有则称C是循环码。如3，2线性码000，110，101，011是循环码。定理4.12 循环码C的对偶码C是循环码。,4.5 循 环 码,定理4.13 设C是码长为n的循环码，令设 是I(C)中次

21、数最低的多项式，其中，则(1)，且 是由生成的 的主理想，即(2)C是以矩阵为生成矩阵的n，k线性码。,4.5 循 环 码,例如，C=000,110,101,011是循环码，则 I(C)=0,1+x,1+x2,x+x2由于1+x是I(C)中次数最低的多项式，故g(x)=(1+x)，故C的生成矩阵为由定理4.13知，任意一个循环码可以惟一确定一个多项式，任给一个多项式，能否惟一确定一个循环码？,4.5 循 环 码,定理4.14 设 满足，令 是 在 中生成的理想，即，则是一个二元 的循环码。其中 为g(x)的次数。定义4.19 设C是循环码，如果g(x)是F2(x)中满足 的次数最低的多项式，则

22、g(x)称是C的生成多项式。显然，C的生成多项式是惟一的。,4.5 循 环 码,4.5 循 环 码,长度从1到10的二元循环码的个数,3.循环码的校验多项式定义4.20 设，则称为f(x)的互反多项式。故。易证 的充要条件是。定理4.16 设g(x)是二元n,k循环码C的生成多项式，令，则 是循环码 的生成多项式。,4.5 循 环 码,设 是二元 循环码C的基，则C的生成矩阵为 设 是 的生成多项式，则是 的基，对应的码字分别记为，令则H是码C的生成矩阵，且。由于循环码一定是线性码，因此 为码C的码字的充要条件是。,4.5 循 环 码,定义4.21 称 循环码的生成多项式 为循环码C的校验多项

23、式，并称 为C的校验矩阵。例3 求以 为生成多项式的7,4循环码C的生成矩阵及校验矩阵，并判断 与 是否是C中码字。解 由于dim C=4，故g(x),xg(x),x2g(x),x3g(x)是C的基，故C的生成矩阵为,4.5 循 环 码,4.5 循 环 码,循环码是线性码，可按线性码的方式进行信息编码与译码；循环码的数学结构更特殊，其编码与译码更加简单。在实际工程中，循环码的编码与译码可以用电子设备直接实现。1、循环码的除法电路编码法设C是二元n,k循环码，g(x)=g0+g1x+gn-kxn-k是C的生成多项式，其中gn-k=1,g0=1，则C的生成矩阵G一定是行等价于如下形式的矩阵G1也是

24、C的生成矩阵,4.6 循环码的编码与译码,由于对有因此可以把C中码字的后k位看做是信息位，而前n-k位看做是校验位。假设给定了信息位的值，即给定了原始信息，如何惟一地确定出 使令则存在唯一的多项式q(x)及r(x)使,4.6 循环码的编码与译码,其中，则即设则故因此给定原始信息后，可由多项式除法惟一决定使因此，循环码的编码可用多项式的除法电路实现。,4.6 循环码的编码与译码,以为除式的除法电路的框图每个方框代表一个寄存器，一共n-k个寄存器，从左向右分别叫第一级，第二级，第n-k级；每个寄存器可以取值0或1；每个代表加法器，进行模2的加法运算；每个代表乘法器，进行模2的乘法运算,4.6 循环

25、码的编码与译码,经过的数都乘以某个gi,i=0,1,n-k；每个寄存器开始时数值全为0，从最右边的输入端每输入一个数，每个寄存器中的数向左边移出；寄存器D1中的数移出后，输出的同时，经过每个乘法器进入对应加法器；其余各寄存器的数移出后经过加法器运算后，进入其各自的左边的寄存器，Dn-k中的数变为D1中的数乘上g0加上输入的数。,4.6 循环码的编码与译码,若从左方输入端依次输入n个F2中的元素an-1,an-2,a0，当a0输入以后，则n-k个寄存器中的数就是用g(x)除 所得的余式 的系数，从左往右依次为rn-k-1,rn-k-2,r1,r0；且从第n-k+1个数输入后，直到第n个数输入为止

26、，输出端的输出就依次为是用g(x)去除a(x)所得的商的k-1次项系数，k-2项系数，零次项系数。,4.6 循环码的编码与译码,特别，当给定以g(x)为生成多项式的循环码C的k个信息位的值cn-k,cn-k+1,cn-1以后，从输入端依次输入下面n个元素当最后一个0输入后，设n-k个寄存器里的数从左向右依次为cn-k-1,cn-k-2,c1,c0，则c=c0,c1,cn-k-1,cn-k,cn-1就是对原始信息（cn-k,cn-k+1,cn-1）的编码。,4.6 循环码的编码与译码,例4 求以g(x)=x3+x+1为生成多项式的7,4循环码的编码器，并对原信息1001进行编码，并说明编码器每一

27、步的运算情况。解 由于g(x)=x3+x+1，即g0=g1=g3=1,g2=0。又任何数乘1其结果不变，此时乘法器可用直通线路代替，而乘上0的乘法器可用断开的线路（即没有线路）表示。,4.6 循环码的编码与译码,除法电路运算情况如下：在输入前，D1=D2=D3=0 第一步，输入1，则D1=D2=0，D3=1第二步，输入0，则D1=0，D2=1，D3=0第三步，输入0，则D1=1，D2=D3=0第四步，输入1，则输出1，且D1=0，D2=1，D3=0第五步，输入0，则输出0，且D1=1，D2=D3=0第六步，输入0，则输出1，且D1=0，D2=D3=1第七步，输入0，则输出0，且 D1=D2=1

28、，D3=0,4.6 循环码的编码与译码,则c0=0,c1=c2=1又(c3 c4 c5 c6)=(1001)，因此对信息（1001）的编码是(c0,c1,c6)=(0111001)。显然，编码器的输出（1010）是用g(x)除x6+x3所得商的系数。由于C的生成矩阵为则对应信息（1001）的码字为(1001)G=(0111001)，即除法电路运算结果正确。,4.6 循环码的编码与译码,2.乘法电路编码法设g(x)是n,k循环码C的生成多项式，则g(x),xg(x),xk-1g(x)是I(C)的一组基，从而c(x)I(C)当且仅当存在m0,m1,mk-1F2使即c(x)对应的码字是原信息(m0,

29、m1,mk-1)的编码，因此求原信息编码等价于求原信息对应的多项式m(x)=m0+m1x+mk-1xk-1与C的生成多项式g(x)的乘积的结果c(x)=m(x)g(x)，因此循环码可以用由g(x)确定的乘法电路完成。,4.6 循环码的编码与译码,设其中则由g(x)确定的乘法电路图是：例5 求以g(x)=x3+x+1为生成多项式的7,4循环码的乘法编码器，并对原信息1001编码。,4.6 循环码的编码与译码,解 由于n=7,k=4,则n-k=3，因此所求编码器是3级的乘法电路编码器，又g1=1,g2=0,故乘法编码器图为其中，D2到D1之间加法器省略，因为没有加法运算。对原信息1001编码自动运

30、算如下：,4.6 循环码的编码与译码,在输入前，D1=D2=D3=0 第一步，输入1，输出0+1=1，D1=0，D2=0+1=1，D3=1第二步，输入0，输出0+0=0，D1=D2=1，D3=0第三步，输入0，输出1+0=1，D1=1，D2=D3=0第四步，输入1，输出1+1=0，D1=0，D2=D3=1第五步，输入0，输出0+0=0，D1=D2=1，D3=0第六步，输入0，输出0+1=1，D1=1，D2=D3=0第七步，输入0，输出0+1=1，D1=D2=D3=0,4.6 循环码的编码与译码,输出的数字依次是1,0,1,0,0,1,1，对应的多项式为x6+x4+x+1，从而对应的码字为（11

31、00101），恰好是输出的反顺序。由于C的生成矩阵为则对应信息（1001）的码字为(1001)G=(1100101)，即乘法电路运算结果正确。,4.6 循环码的编码与译码,3.循环码的译码 由于循环码一定是线性码，因此线性码的译码方法对循环码当然有效。故循环码的译码也分为以下三步：(1)计算收到的字=(0,1,k-1)的校验子S()；(2)根据校验子S()找出错误模式E()；(3)将A译为码字+E()。设C是二元n,k循环码，则C有惟一的如下形式的校验矩阵则下面定理给出了译码器计算收到的字A的校验子的方法。,4.6 循环码的编码与译码,定理4.17 设 是二元 循环码C的校验矩阵，是C的生成多

32、项式，则对 的校验子 满足其中，。对=(0,1,k-1)F2n，的校验子是g(x)除(x)所得的余式对应的向量，因此求的校验子可以用g(x)确定的除法电路自动完成。,4.6 循环码的编码与译码,根据校验子进行循环码译码 定理4.18 设g(x)是二元n,k,d的循环码C的生成多项式，若收到的字满足wt(s()(d-1)/2，则应译为(x)+S(x)所对应的码字。其中S()是S()的校验子。例6 设C是以g(x)=x3+x+1为生成多项式的7,4,3循环码，试译收到的字=(0110110)解 由于则即S()=(010),4.6 循环码的编码与译码,又wt(S()=1=(3-1)/2，则(x)应译

33、为则译为（0010110）下面不加证明地给出不满足上述定理条件循环码通用译码方法 定理4.19（循环码的译码算法）g(x)是二元n,k,d的循环码的生成多项式，若收到的字(x)满足,4.6 循环码的编码与译码,(1)至多有(d-1)/2个错误发生；(2)至少有连续k位码元没有发生错误。记sixi(x)(mod g(x),i=1,2,，找到m使对应字的汉明重量(d-1)/2，设xn-msm(x)E(x)(mod xn-1)，则将(x)译为(x)+E(x)对应的码字。例7 设C是以g(x)=x3+x+1为生成多项式的7,4,3循环码，试译=(1011100)解(x)=(1011100)=1+x2+

34、x3+x4，由于d=3,则(d-1)/2=1,4.6 循环码的编码与译码,故要找m使sm(x)对应的字的汉明重量1，由sixi(x)(mod g(x)得：由于s1(x)、s2(x)、s3(x)对应的字的汉明重量都大于1，而s3(x)对应的字的汉明重量为 1，故m=3。,4.6 循环码的编码与译码,故错误模式E(x)为则应译为对应的码字为（1011000）,4.6 循环码的编码与译码,例8 设是15,7,5循环码，若收到的字都至多发生2个错误，且至少连续7位没有发生错误，试译解(xx+x4+x5+x6+x8+x9+x13，由于d=5,则(d-1)/2=2，故要找m使sm(x)对应的字的汉明重量2

35、，由sixi(x)(mod g(x)得：,4.6 循环码的编码与译码,则m=7，故从而应译为对应的码字c,4.6 循环码的编码与译码,语义信息编码是一个科学管理问题，设计出一个好的编码方案对于信息的采集、加工、利用和管理等都有十分重要的意义，它可以使上述工作变得更加方便，使信息表述更规范、科学。1.语义编码的原则所谓语义编码就是用一组数字或字符描述客观实体或实体的属性。信息编码的目的主要是使信息描述惟一、规范、系统，因此应遵循以下三个原则：,4.7 语义信息编码的概念与编码方法,惟一性原则：相同的语义编码只能描述相同的客体或客体属性。从系统的角度讲，惟一性原则提高了数据的全局一致性规范性原则：

36、惟一性原则限制了不同客体或客体属性的语义编码不能重复，规范化原则防止信息表述变得杂乱无章。例 在学生管理中，“学号”编码的规范：,4.7 语义信息编码的概念与编码方法,标准化原则：在实际应用中，实体的大部分编码都有国家或行业标准。对信息进行编码应尽量标准化，以便信息的交流和使用。2.语义编码与信息分类 语义编码的关键在于分类，科学、合理的分类是信息编码规范化、标准化的基础，简单介绍一下分类的基本原则以及人们在日常管理中的常用分类方法。分类原则,4.7 语义信息编码的概念与编码方法,(1)系统化原则：应全面分析客观实体的各种具体属性，系统地确定分类属性，并遵循相关的分类标准。(2)柔性化原则：所

37、谓柔性是指在一定情况下分类结构对于增设或变更处理对象的可容纳程度。柔性使得信息可以扩展和延伸，但柔性往往会带来信息冗余，这在分类时应加以综合考虑。(3)协调性原则：任何工作都是从原有的基础上发展起来的，因此分类时一定要注意新老分类的协调性。,4.7 语义信息编码的概念与编码方法,层次分类法 层次分类法是按照某个属性或属性集的取值所覆盖的实体范围进行逐层分类，直至具体对象。,4.7 语义信息编码的概念与编码方法,3.语义编码方法 语义编码是对分类结果的一种形式化描述。顺序编码：顺序编码是一种用连续数字代表编码对象的码，如01-教授，02-副教授，03-讲师，04-助教，05-未定职等 分段编码：

38、分段编码是将数据项分成若干组，每段代表一个组，码中数字的值和位置都代表一定意义。前述的学号编码就是一种分段编码。助记编码：助记编码是用文字、数字或文字数字相结合对对象进行描述，可通过对码的联想进行记忆。,4.7 语义信息编码的概念与编码方法,4.语义编码的校验 编码的正确性直接影响到整个处理工作的质量，特别是在信息手工复制过程中，如抄写、手工输入计算机，发生错误的可能性更大。因此为了保证信息在交流过程中正确，在编码时往往引入校验位，使其对码值进行校验。语法信息编码的校验思想也适用于语义信息编码。错误种类：误记(如把1记成7)；易位(如把1436变成1346)；双易(如把34567变成36547

39、)；随机(包括上述两种或三种错误或其他错误)。,4.7 语义信息编码的概念与编码方法,校验方法(模11校验位)(1)算术级数法：,4.7 语义信息编码的概念与编码方法,(2)几何级数法,(3)质数法例9 设原代码为6341，试应用模11法确定校验位。解 模11法的权重有多种选择方法，因此校验位确定也有多种方法。,4.7 语义信息编码的概念与编码方法,(1)算术级数法 对应权重为5、4、3、2，故S=56+43+34+21=56校验码a=56(mod11)=1，所以含校验位的编码为63411。(2)几何级数法 取m=2，则对应权重为16、8、4、2，故S=166+83+44+21=138校验码a=138(mod11)=6，所以含校验位的编码为63416。,4.7 语义信息编码的概念与编码方法,(3)质数法取质数序列为13,7,5,3，则S=136+73+54+31=122校验码a=122(mod11)=1，所以含校验位的编码为63411。在应用模11法确定校验码时，若余数为10，则将校验码取为0。,4.7 语义信息编码的概念与编码方法,