信息与编码信息与编码19-7.doc

东北电力大学 教案封皮 开课单位 理学院信息与 计算教研室 课程名称 信息与编码 授课教师 常志文 授课对象 信息与计算专业121 选用教材 信息论与编码 理论（沈世镒） 总学时 60 （含课内实验10学时） 课次 19 第7章 第3~4节线性码的译码方法，线性码 重量分布 教学目的 及要求 教学目的及要求： 掌握线性码的主要译码方法； 了解线性码重量分布的相关性质。 教学重点 处理安排 教学重点： 线性码的译码方法； 处理安排： 结合实例及原理说明。 教学难点 处理安排 教学难点： 线性码的译码与重量分布； 处理安排： 通过例题及作业题加深对译码方法与重量分布规律的理解。 教学方式、 方法 方式（手段）：多媒体； 方法：讲授法。 教学 内容 及时 间分 配 第一节课： 7.3线性码的译码方法； 45分钟 第二节课： 7.4线性码的重量分布。 45 分钟 例题、练习 题 例题：结合线性码的译码法给出相关例题。 作业、思考 题 P151 页,7.8，7.9，7.11 题。 内 容 7. 3线性码的译码方法 定义7.3.1 设L是一个q元［n,k］线性码，H为它的校验矩阵。对任意 x?V(n,q)，称xH T为x的伴随式，记为S(x)。显然，S(x)=O：= L 设h|,h2,...,hn上为H的行向量，则 S(x) =(x m’x 叽,…,x ?hnjJ 让我们回忆一下前面学习过代数的一些基本结论。 如果L V(n,q)是一个 线性码，则V(n,q)关于L的商空间定义为 V(n ,q)/L 二｛x L |x V(n ,q)｝。集合 x L =｛x c|c L｝称为 L 的倍 集。商空间是Fq上的向量空间，它们的运算定义如下： a(x+L)=ax+L,(x+L)+(y+L)=(x+y)+L. 而且x+L=y+L充分必要条件是 x - y ：= L。 定理7.3.1 设L是一个q元［n,k］线性码，H是它的校验矩阵，则 x,r V(n,q)属于同一个陪集的充分必要条件是它们的伴随式相同。 定理7.3.2 设L是一个线性码，H是它的校验矩阵，则最小极力译码等价 于把收到的字x译成码字c=x-a，其中a是倍集x+L中具有最小重量的字，或 a 是与x具有相同伴随式并且重量最小的字。 上述译码方法可以用列表的形式描述如下： O c2 ... cm a1 G - a1 c2 a1 ...cm a1 a2 G a2 C2 a2 ...cm a2 as G as C2 as ...cm a s 表中的第一行L中的所有码字，在 V(n,q) 选取一个不在第一行且具有最小重 量的字印，与第一行的每一个字相加得到第二行，它们构成 a L。一般 地，选取一个不在前i行中且具有最小重量的字 ai，与第一行的每一个字相 加得到i+1行，它们构成ai L。此过程一直进行到表中包含 V(n,q)中所有 的字。上述列表称为L的标准阵。第一列中的 ai称为陪集头。 如果收到的字X在表中的第j+1列，则X =Cj - ai ,对某个i。由于ai的取法, 因此x译成Cj二x -印，即是包含x的那一列中最上边的码字。这种译码方 法称为标准阵译码。 TOC \o 1-5 \h \z 例7.3.1设L是一个二元［4,2］线性码，它的生成矩阵G = P 1 1 0 e i o 1, 易得L的一个标准型的生成矩阵“011、 易得L的一个标准型的生成矩阵 G= ，则L的校验矩阵为 I。1 0 1 , 「1110、 G = Q 1 0 1, L的标准阵为 0000 1011 0101 1110 1000 0011 1101 0110 0100 1111 0001 1010 0010 1001 0111 1100 如果x=1100是收到的字，查上表可知， 1100译成1110。由陪集头和它们的 伴随式列表如下： 陪集头 伴随式 0000 00 1000 11 0100 01 0010 10 如果收到的字x=0001，计算它的伴随式(0,0,0,1) ? H 丁二(0,1)查上表知，它 的陪集头为0100,因此，x被译为0001-0100=0101。 7.4线性码的重量分布 设L是一个q元［n ,k］ 线性码，A表示L中重量等于i的码字个数，O^i岂n 我们称A0, A1An为L的重量分布，而称多项式 (n) WL(z)八 Az=人 A1z …Anz(n) i ：0 称为L的重量分布多项式。显然， WL(z)二為z (x) X迂 例 741 ⑴ 设L是二元[3,2] 线性码，L={000,011,101,110}. 其对偶码L-={000,111}。L和 L-的重量分布多项式分别为 2 WL(z) =1 3z Wl_(z) =1 - z3 (2)对于二元线性码L={00,11},其对