信息与编码信息与编码15

东北电力大学教案封皮开课单位理学院信息与计算教研室课程名称信息与编码授课教师常志文授课对象信息与计算专业121选用教材信息论与编码理论（沈世镒）总学时60（含课内实验10学时）课次15第6章第13节代数码理论的基本特点，码的定义与纠错检错能力。教学目的及要求教学目的及要求：掌握代数码的基本概念；掌握代数码的纠错与检错能力。教学重点处理安排教学重点：代数码的基本概念与纠错检错能力；处理安排：通过代数码的实例与相关理论来说明。教学难点处理安排教学难点：码的汉明距离、重量与最小距离的计算；处理安排：通过例题及练习题来巩固相关知识。教学方式、方法方式（手段）：多媒体；方法：讲授法。教学内容及时间分配第一节课：6.1代数码理论的基本特点；45分钟第二节课：6.2码的基本定义与纠错检错能力。35分钟6.3编码理论的基本问题。10分钟例题、练习题例题：结合相关概念给出例题。作业、思考题P140页6.1,6.2题内容备注第六章编码理论的基本知识6.1代数码理论的基本特点编码理论中具有以下特点。(1) 充分利用代数工具，把码的结构与编、译码算法用代数方法给以表达与计算。(2) 这里评价码好坏的标准与第一部分不冋，第一部分信道编码定理的要求是消息传递误差要非常小。而第二部分对码好坏的评价只是纠错或检错能力。因此，代数码只能起到降低通信中的误差概率的作用，如果信道对信号传输本身的误差概率就很小，那么通过代数码理论就可实现优质通信。(3) 代数码理论与通信工程密切结合，在有限域中的运算都可通过逻辑电路实现且编、译码运算还要求与通信实时、冋步完成。因此，我们在学习代数码理论时不仅要注意它的袋鼠结构，还要注意它的计算复杂度。6.2码的基本定义与纠错、检错能力码的基本定义定义如果C为V(n,q)中的任一非空子集，那么称C为q兀分组码，称n为分组长度，C中的每一个向量(或字串)为一个码字，如果|C|-M，那么称logqMC为一个(q,n,M)码或q为元(n,M)码，该码的码率定义为R=qn定义设x,yV(n,q)，那么x和y的汉明距离d(x,y)为x和y中不同n0如果uv的位置个数，因此d(x,y)d(Xj,yj)其中d(u,v)=才而j二否则u,vFq。由此看来，汉明距离函数d(x,y)是V(n,q)汉V(n,q)TN的映射，其中N为全体非负整数。我们以下记d(x)为x的汉明势，这是x中非另分量的个数。定理如果d(x,y)是V(n,q)上的汉明距离函数，那么对任意x,y,z(n,q),满足下列性质：(1) 非负性：d(x,y)王O.d(x,y)=0的充分必要条件为x=y;(2) 对称性：d(x,y)=d(y,x);(3) 三角不等式：d(x,y)兰d(x,z)+d(y,x)。因此，具有汉明距离d(x,y)定义的V(n,q)是一个距离空间，又称为汉明空间。结合实际应用结合实例计算结合实例计算对任何yV(n,q)，就有一个xC使d(x,y)乞d(x,y)，对任何结合实例说明最小距离译码方法xC,这时有p(y|x)_p(y|x),对任何x-C成立，我们称xC是y最大似然译码或最小汉明距离译码。定义设C是q元(n,qk)码，如果存在一个下标集合二hl-ik，使得码C去掉其他的n-k个位置所得字的全体为Fq上长度为k的所有串的集合Fq(k)，也就是5；=3广(0,丸.礼)风CFq(k)。那么码C称为具有k个信息位的q元系统码。集合i1,i2.ik称为信息位，其余n-k个位置称为校验位或冗余度。如果信源信息可以表示成Fq上长度为k的所有串的集合Fq，则一个具有k个信息位的q元系统码可以把每一个信源信息在保持不变的条件下嵌入一个码字，下面举例说明。系统码与检错码关系。例二元码C=0000,0110,1001,1010是系统码。上例中的编码方法称为系统编码，它的译码过程很简单，我们可以直接从码字的信息位上中读出信源字符。例二元码C=000.100.010.001不是系统码。码的检错和纠错能力检测码和纠错码就是一个码在信息传递时可以自动发现与纠正差错。这种检测和纠错能力与码的最小距离有关，我们在下文中详细叙述。定义设C是一个(n,M)码，码C的最小距离定义为d(C)二mind(x,y)|x,yC,x=y。我们用(n,M,d)表示码长为n,大小为M,最小距离为d的码。纠错能力好坏直接关系到码的实用性。定义如果对码C中每一个码字，当发生至多t个(至少一个)错误时，所产生的字表示码字，则称码C为可检查码；如果能检查t个错误而不能检查t+1个错误，则称码C为恰好可检查t个错误的检错码。由码的检错性定义可得对任何C，与任何yJ(n)，如果d(x,y)乞t那么y必不在C中，因此有以下定理成立。定理码C恰好可检查t个错误的充分必要条件为d(C)=t+1。定义如果对码C采用最小距离译码时，它可以纠正码C中任何一个与码字x距离小于或等于t个错误，则称码C为可纠正t个错误的纠错码；如果C能纠正t个错误而不能纠正t+1个错误，则称码C为恰好可纠正t个错误的纠错码。根据定义，恰好可纠正t个错误的纠错码可以纠正不多于t的个错误，码给出实例计算。的最小距离与纠错性能有如下关系。定理码C恰好可纠正t个错误的充分必要条件为d(C)=2t+1或2t+2。n1推论6.2.1d(C)=d的充分必要条件是码C恰好可纠正D个错误。纠错码进步结论。-2一例624我们称以下类型的码为码长n的q元重复码，如C=000,111,(q-1)(q-1)(q-1)因为d(C)=n，所以码C既是一个恰好可以纠正个错误的纠错码，同时又是一个恰好可以检出n-1个错误的检错码。