信息与编码信息与编码17-6.doc

东北电力大学 教案封皮 开课单位 理学院信息与 计算教研室 课程名称 信息编码与密码学 授课教师 常志文 授课对象 信息与计算专业121 选用教材 信息论与编码 理论（沈世镒） 总学时 62（含课内实验10学时） 课次 17 第6章 第3节编码理论的基本问题 教学目的 及要求 教学目的及要求： 要求学生掌握编码理论的基本问题； 掌握置换的等价性及完备码的性质。 教学重点 处理安排 教学重点： 掌握编码理论的基本问题； 处理安排： 结合实际应用说明。 教学难点 处理安排 教学难点： 置换变换及完备码的判断； 处理安排： 结合转换变换的应用与等价性说明， 对完备码通过例题说明完备码的最小 距离与个数的关系。 教学方式、 方法 方式（手段）：多媒体+板书； 方法：讲授。 教学 内容 及时 间分 配 第一节课： 6.3编码理论的基本问题（1）。 45分钟 第二节课： 6.3编码理论的基本问题（2）。 45分钟 例题、练习 题 例题：置换码与完备码给出相关例题。 作业、思考 题 P140 页 6.3，6.8 题  内 容 备注 第6章编码理论的基本知识 6.3 编码理论的基本问题 编码理论的基本问题是在以下条件下构造 q元的(n,M,d) 码： ⑴ 在码率R固定的条件下，使最小距离 d尽量大。 ⑵ 在最小距离d固定的条件下，使码率 R尽量大。 如果码长n固定， 那么以上编码问题就化为： 结合实际应 ⑶ 在码兀数M固定的条件下，使最小距离 d尽量大。 用说明。 ⑷ 在最小距离d固定的条件下，使码元数 M尽量大。 定理 6.3.1 对于任意 n 1, Aq (n,1) =q(n), Aq(n, n) =q. 定义6.3.1关于码的置换有两种，一种是关于下标集合 N ={1,2,.. n｝的置 换，另- 一种是关于信号字母表 Fq ={0,1,..? q -1｝的置换。我们分别记之为 结合实例 [ 1 2 ... an 1 [ 0 1 . q -1 1 W = J ... V O~2 = J J i ^(1)6(2 )..q(n)_ i i 貯2(0 )^2(1 ). Q2(q -1)_ 1 我们分别称这两种类型的置换为 6与▽ 2 型的置换，或简称换位型与换元型 置换。 定义632 由换位型与换兀型的置换可产生换位型与换兀型的码，这就是 对一个q兀的(n,M)的码C,对它可产生换位型与换兀型的置换码： 引理 6.3.1 如果 0 E 4 ,贝0 卩上任意一个q兀(n,M,d)码等价于一个包含零 结合实例 码字0=0…0的q元(n,M,d)码。 定义 6.3.3 设 x € V(n, q) x的汉明势又称重量，这时记为 B(x), 它们是 x中非零位置的个数。码 C 匚 V ( n , q )的最小重量 (简称为重量)定义 为 0 (c) = min{ b (x) | x 乏 C, x式0} 定义 6.3.4 设 = x.|x2 ...xn 和 y=%y2 ...y^V( n,2) x和y的交定义为 xy (X1y1,X2y2,...Xnyn)因此，y中第i位置是非零的充分必要条件是 x和y在第i个位置都是非零的。 定理632 设d为奇数，则二元( n,m,d )码存在充分必要条件是二元 (n + 1,M ,d+ 1)码存在。 可以设计检错码推论6.3.1如果d是奇数，则 A2(n 1,d A2(n,d) 可以设计检 错码 果d是偶数，则 A2(n,d)=A2(n-1,d-1)。 定义6.3.5 设V(n,q) , r为一非负整数，则中心在x、半径为r的球定义 为 Sq(x,r) ={ y V(n,q) |d(x, y) _ r}。 定理6.3.3 (汉明界)q元(n,M,2t+1)码满足 M{;nn (q-1)十…+J. M{ ;n n (q-1)十…+ J.丿 n (q-1)r} z (n) 完备码性质定义6.3.6 设C是一个q元(n,M,2t+1)码，如果 完备码性质 n G 巾、 t (n) M［门 + jq-1)+..?+ + 戸-们 4 J丿 乜丿 则称C为完备码。 例如，二元重复码(n,2,n)码C={00…0,11…1}，当n为奇数，C是完备的，另 外，只含一个码字的码以及由 V(n,q)构成的(n,qn,2)码都是完备的。这三种 码称为平凡的完备码。 定理 6.3.4 (Gilbert-Varshamov界)存在 定理 6.3.4 (Gilbert-Varshamov 界)存在M q(n) d」 (n\ 的 (n,M,d)码, q q(n) n 因此 AJn,d) — M 二 d」 —fi.. 瓦.(q-1) ◎ li丿 定理6.3.5 (Singleton 界)Aq(n,d)—qn1 证明 设C是一个q元(n,M,d)