（应用数学专业论文）线性码自同构群的研究.pdf

摘要 摘要 线性码自同构群是代数编码中一项最基础研究，在译码学和密码学中也起着基石的 作用因此对线性码自同构群的研究是很有必要的 本文把群论、有限域、线性规划、矩阵广义逆理论等知识与编码理论相结合，对线 性码自同构群的某些内容进行了研究，主要给出了以下结果： ( 1 ) 给出了线性码自同构群的进一步简化的构造算法 ( 2 ) 在上投射空间的基础上，构造出了线性等重码的自同构群 ( 3 ) 建立了二次剩余码自同构群的判定定理，并用两个实例验证了所给判定定理的 正确性 关键词线性码有限域线性码的自同构群线性等重码二次剩余码 a b s t r a c t a b s t r a c t t h er e s e a r c ha b o u tt h ea u t o m o r p h i s mg r o u po fl i n e a rc o d ei saf o u n d a t i o ni nc o d i n g t h e o r y ni sa l s oac o r n e r s t o n ef o rd e c o d i n ga n dc r y p t o g r a p h y t h e r e f o r e ，t h er e s e a r c ha b o u t t h ea u t o m o r p h i s mg r o u po fl i n e a rc o d ei sv e r yi m p o r t a n t c o m b i n i n gg r o u pt h e o r y , f i n i t ef i e l d ，l i n e a rp r o g r a m m i n g ，t h et h e o r yo fg e n e r a l i z e d i n v e r s e nm a t r i xw i t ht h et h e o r yo f c o d i n g ，t h i sd i s s e r t a t i o no b t a i n st h ef o l l o w i n gr e s u l t s ( 1 ) w e p r o v i d ea nc o n s t r u c t i v ea l g o r i t h mo f t h ea u t o m o r p h i s mg r o u po fl i n e a rc o d e ( 2 ) i nt h ep r o j e c t e ds p a c eo n 只f i e l d ，w ep r e s e n tt h ea u t o m o r p h i s mg r o u po fl i n e a r e q u i w e i g h tc o d eb yac o n s t r u c t i v ew a y ( 3 ) t h et h e o r e m so nt h ea u t o m o r p h i s mp e r m u t a t i o no ft h eq u a d r a t i c r e s i d u ec o d e sa r e e s t a b l i s h e d t h ec o r r e c to f t h e o r e m si sc h e c k e db yt w oe x a m p e s k e yw o r d sl i n e a rc o d e s y s t e m a t i cf i n i t e f i e l d a u t o m o r p h i s mg r o u po fl i n e a rc o d e e q u i w e i g h tl i n e a rc o d eq u a d r a t i cr e s i d u ec o d e i i 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：兰伞牮垡二一 吼珥年上土日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密。 ( 请在以上相应方格内打“ ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 我l 色碣自同枸鼙晚研窘 的学位论文，是我个人在导师() 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：掣量龟整一日期：牟厶月牛日 作者签名：型监 导师签名： 日期：二毕年上月j l 日 日期：砷年上月卫日 第1 幸概论 第1 章概论 1 1 研究背景 信息论与编码理论是一门理论与应用关系十分密切的学科，首先它的应用性很强， 从它的产生背景，发展与应用内容来看，它与电子、通信、计算机技术的发展密切相关， 并得到一系列的重要应用，尤其是与近代网络通信、数据加密域安全技术、多媒体技术 密不可分信息论与编码理论又是一门十分严谨的理论学科，各种数学工具，如群论、 有限域理论以至于线性规划等都在编码理论研究中得到了应用，从而使得编码理论也成 为通信领域中的一个研究热点 线性码是一种非常重要的分组码，是讨论各种码的基础，一些特殊的线性码的编码 方案和译码方案都比较简单，并且一些特殊的线性码都有比较好的性质，绝大多数的已 知好码都是具有比较好的性质，绝大多数的已知好码都是线性码，因此对线性码的研究 一直成为编码理论的中心课题而从目前下一代网络的研究成果可以看出，线性码仍会 在下一代网络中起一定的作用 1 2 国内外研究现状 编码理论与信息论大约在2 0 世纪4 0 年代后期由g o l o y , h a m m i n g ，s h a n n o n 等人的研 究基础上而创立的随着计算机技术和通信技术的发展，以及数学工具的完善，代数编 码理论也迅速发展起来线性码的自同构的研究始于m a c w i l l i a m s 在1 9 7 7 年发表的文献， 在这篇文献中给出了判断一个置换矩阵是否属于自同构群的充分必要条件另外，目前 已有人讨论了对有限域上的任何一个矩阵，它的广义逆的存在及计算问题利用矩阵广 义逆理论，给出了两个重要的定理，对理论分析及实际计算一个线性码的自同构群有很 大的帮助，将求取一个线性码的自同构群的元素演化成：求取矩阵的广义逆、矩阵的乘 积、等式判断等 在此基础上，文献 6 】研究了线性码的自同构群问题，使用矩阵广义逆理论对线性码 的自同构群进行了研究，得出了一些颇有价值的理论及一些很有效的计算方法，将线性 码的自同构群的研究推进了一步；文献 9 】、【l o 】中对g f ( 2 ”) 上线性码的自同构群作了 进一步的研究，获得了一些具有理论价值和实际意义的结果，进一步深化了对码的自同 河北人浮珲学硕十学位论文 构群的认识；但文献 9 】、 1 0 】的结果还仅限于g f ( 2 ) 上，为了使这些结果可用于更多 的码类，又在单项式矩阵理论的基础上，将线性码的自同构群的一些结论推广到一般的 有限域g f ( p ”) 上去，得到了一些结果 尽管如此，关于线性码自同构群还存在许多问题没有解决，如( 1 ) 在二元情况下， 如何更简便地构造线性码自同构群? ( 2 ) 如何解决线性等重码的白同构群问题? ( 3 ) 如何建立二次剩余码自同构群的判定定理，如何用该定理有效地解决实际问题? 等 等本论文将对如上三个问题重点考虑并给出解决办法 1 3 本文主要研究内容 本文主要分三章：第一章概论；第二章预备知识；第三章线性码自同构群的进 一步研究 本文在国内外等人研究基础上对线性码自同构群作了进一步研究，给出了如下结论： ( 1 )给出了线性码自同构群的简化构造算法 ( 2 ) 在c 上投射空间的基础上，构造出了线性等重码的自同构群 ( 3 )建立了二次剩余码自同构群的判定定理，并用两个例子验证了所给判定定理 的正确性 2 第2 章预器知识 第2 章预备知识 本章介绍一些抽象代数及域上的线性代数的基本知识，这些知识在代数学和代数编 码中广泛应用，也是下面章节所必需的 近代数学是代数编码的数学基础，它主要关心代数运算本身的性质和规律，可作为 运算对象一元素，可以是整数、多项式、矩阵等但它们对乘法、加法等运算具有共同 的性质首先介绍一下最基本的概念，代数系统 2 1基本概念 定义2 1 1 【1 1 满足一定规律或定律的系统称作代数系统，且在该系统中有： ( 1 ) 有一群元素以，b ，c 构成一个集合 ( 2 ) 在元素集合中有一等价关系 ( 3 ) 在集合中定义了一个或数个运算，通过运算建立起元素之间的关系 ( 4 ) 有一组假定 下面介绍一下代数系统中一些最基本的知识，以及群、域、有限域上的线性空间和 线性变换等知识 定义2 1 2 n 1 设g 是非空数集，并在g 内定义了一种代数运算，若满足下述公理： ( 1 ) 有封闭性对任意口，b g ，恒有口。b g ( 2 ) 结合律成立对任意口，b g ，有 。b ) 。c = a 。( 6 。c ) ( 3 )g 中有单位元e ，对任意口g ，有以g ，使口oe=eo 口= 口 ( 4 ) 对任意a g ，存在a 的逆元口。1 g ，使口oa = a o 口= e 则称g 构成一个群 上述定义中，g 的运算t o 可以是通常的乘法或加法若为乘法，则恒等元素为单位 元；若为加法，则恒等元记为0 ；g 的逆元记为一口群中元素的个数，称为群中的阶若 群中元素个数有限，称为有限群；否则称为无限群 例2 1 1 整数全体，按通常加法构成群，这是一个无限群但通常的乘法构不成群 例2 1 2 偶数整体，对加法构成群，对乘法不构成群 例2 1 3 实数全体对加法构成群除0 元素以外的实数全体对普通乘法也构成群，此 1 河北人卵。硕十学伊论文 时群的单位元e = 1 ，这两个群为无限群 例2 1 4 所有n 阶矩阵的加法构成群，单位元为0 的矩阵对矩阵乘法，若为满秩矩 阵，则构成群；否则不是 若群g 中，对任何口，b g ，有a 。b = b 。a ，则称g 为交换群、可换群、或阿贝尔 群上述一系列群中，除例2 1 4 中的矩阵在乘法运算下不是可换群外，其余例中都是 可换群 除了上面所述的群外，域在代数编码理论中起着关键作用域是定义了两种代数运 算的系统 定义2 1 3 乜1 非空元素集合f ，若在，中定义了加和群两种运算，且满足下述公理： ( 1 ) f 关于加法构成阿贝尔群其加法恒等元记为0 ( 2 ) f 中非零元素全体对乘法构成阿贝尔群其乘法恒等元( 单位元) 记为1 ( 3 ) 加法和乘法问有如下分配律： a ( b + c ) = a b + 口c ( 6 + c ) a = b a + c a 则称，是一个域 例2 1 5 有理数全体、实数全体、复数全体对加法、乘法都分别构成域，分别称为 有理数域、实数域和复数域且这3 个域中的元素个数有无限多个，所以称它们为无限 域称域中元素的个数为域的阶元素个数有限的域称为有限域，用g f ( q ) 豆t 2 , f q 表示g 阶有限域 例2 1 60 , 1 两个元素按模2 加和模2 乘构成域，该域中只有两个元素，记为g f ( 2 ) 或 e 2 2 有限域上的线性空间和线性变换 下面将介绍线性码，为此先介绍有限域上线性空间和线性变换的定义 定义2 2 1 1 1 设y 是一个非空集合，c 是一个g 元有限域在集合矿的元素之间定 义了种代数元素运算，叫做加法：这就是说，给出了一个法则，对于v 中任意两个元 素口和，在矿中都有唯一的一个元素厂与他们对应，称为口与的和，记为 y = 口+ 在有限域c 与集合y 的元素之间还定义了一种运算，叫做数量乘法：这就 是说，对于有限域中任意一元尼与v 中任一元素口，在v 中都有唯一的一个元素艿与 4 第2 章预符知识 它们对应，称为k 与口的数量乘积，记为万= k c t 如果加法与数量乘法满足下述条件： ( 1 ) ( v ，+ ) 是一个交换群 ( 2 ) 对任意的口，v ，七，c ，有 ( i ) k ( a + ) = k a + 够 ( i i ) ( k t ) a = k ( 1 0 t ) ( i i i ) ( k + i ) o t = k a + l e t ( i v ) l a = 口 n z , v 称为有限域c 上的线性空间，v 中的元素称为向量 定义2 2 2 n 1 设矿是上的线性空间，1 1 ，：v r 是v 中的，个向量，如果存在中 的r 个不全为零的元素c 1c 2 c ，使得c i 。，l + c 2 。v 2 + c ，。v ，= 0 ，则称1 ，l ，v 2 ，y r 为线 性相关的，否则称为线性无关 定义2 2 3 n 3 如果在线性空间y 中有n 个线性无关的向量，但是没有更多数目的线 性无关的向量，那么y 就称为n 维的 定义2 2 4 n 1 线性空间v 的一个变换彳称为线性变换，如果对于y 中的任意的元素 o f ，和有限域f q 中的任意元后，都有 a ( o t + ) = 彳( 口) + 彳( ) a ( k a ) = k a ( a ) 2 3 实数域上的矩阵及性质 定义2 3 1 蚴设为域，口l ，1 i m ，1 刀，称彳= 以l ia 1 2 口2 la 2 2 a ， ia m 2 为c 上的m x ，l 阶矩阵，当m = ，z 时，称为以阶方阵 定义2 3 2 乜1 设么是域f 上的m n 阶矩阵，则 ( 1 ) a 的行向量的极大无关组所含的向量个数，称为彳的行秩，对于彳的列向量有 相同的结论 ( 2 ) a 的行秩等于a 的列秩，称为彳的秩，记为r ( a ) ( 3 ) 下面3 种变换称为a 的初等变换 s 一 疗 m 河北人理。硕十何沦文 ( i ) a 的两行( 列) 交换位置 ( i i ) a 的任意一行( 列) 乘以f 中的一个非零元素 ( i i i ) a 的某一行( 列) 乘以，的元素加到a 的另一行( 列) ( 4 ) 矩阵的初等变换不改变矩阵a 的秩 ( 5 ) 设a 是域f 上的，z 阶方阵，如果存在域f 上的7 l 阶方阵b ，使得a b = b a = i ， 则称a 可逆，召为a 的逆矩阵 2 4 线性码的相关知识 下面介绍分组码、线性码、系统码、对偶码等相关知识 定义2 4 1 口1 如果c 为v ( n ，q ) 中的任意非空的子集，那么称为c 为q 元分组码，称甩 为分组长度，c 中的每一个向量或字母串为一个码字，如果i c i = m ，那么称c 为一个 ( g ，z ，m ) 码或g 元( 刀，m ) 码 定义2 4 2 d 3 v ( n ，g ) 是域上的刀维向量的集合，这样对v ( n ，q ) 可以定义它在域 上的和与数乘运算，所以v ( n ，g ) 是c 域上的玎维线性空间若ccv ( n ，g ) 是一个g 元 ( 刀，k 】线性码其中刀称为c 的长度，而k 称为c 的维数因为线性码是一个向量空间， 所以可以用它的一组基来刻画，当我们把线性码的基向量作为行向量排成一个矩阵时， 此矩阵称为线性码的生成矩阵设c 是一个g 元i n ，k 】线性码，则生成矩阵g 为k xn 阶 的如果g = ( i k ，彳) ，则称其为线性码的标准型的生成矩阵，其中，。为k k 阶单位阵， a 为k ( 以一尼) 阶矩阵线性码的对偶码的生成矩阵日称为线性码的校验矩阵，有 g h r = 0 定义2 4 3 口1 设x , y v ( n ，g ) ，那么石，y 的汉明距d ( x ，少) 是x 和y 中不同的位置个数， 因此d c 石，y ，= 否nd c x ，y ，其中d c 掰，v ，= ? 三：二；：，而“，y 记d ( x ) 是z 的汉明势，这是石中的非零分量个数，也就是码字重量 定义2 4 4 设c 是一个( ，z ，m ) 码，码c 的最小距离定义为 d ( c ) = m i n d ( x ，j ，) i 工，y c ，z y ) 定义2 4 ，5 口1 设c 为g 元( 刀，后) 码，如果存在一个下标集合口= 瓴，i 2 t ) ，使得码c 去 掉其他的n - k 个位置所得字的全体为f q 上长度为k 的所有串的集合似，也就是 6 第2 章预备知识 q = x 。= ( ，x j 2 x ) ，x c ) c 7 ，那么码c 称为具有七个信息位的q 元系统码，集 合 f i ，f ：t ) 称为信息位，其余n k 个位置称为校验位或冗余度 定义2 4 6 圆设z ，y f ”，x = ( x i ，x 2 x n ) ，y = ( 少l ，y 2 y 。) ，称 = x y7 = x i y l + x 2 y 2 + x y 。为x ，y 的内积 定义2 4 7 1 设c 至f ”是一个码，其正交子空i 日jc 上= x f ”i = o ，v c c ) 称 为c 的对偶码 定义2 4 8 口1 如果线性码中任意两个非零码字的重量相等，称为线性等重码 定义2 4 9 口1 如果码c 中任意两对码字的距离相等( 从而任意一对码字的距离等于 最小距离) ，则称码c 为等距码 定理2 4 1 嘲线性码c 是等距的当且仅当它是等重的 证明因为当x 和y 取遍线性码中的所有码字时，z y 也取遍线性码中的所有码字， 所以有d ( c ) = m 1 9 一p ( x ，y ) ) = m ! n 劬( x y ) ) 手r ，r c l 2 。凯m i 脚n 缈( x ) ) = 缈( x ) 定理2 4 2 口1 任意线性码都等价于一个系统码 证明设g = 9 1 19 1 2 9 2 19 2 2 g t l 为某- - n ，k 线性码的生成矩阵，由于任意矩阵均可 经初等变换化为阶梯形矩阵g ，即g 可化为简化阶梯形矩阵，因为g 的k 个行向量线性 无关且构成这一线性码的基底，r a n k ( g ) = k ，因初等变换不改变矩阵的秩，因此 r a n k ( g ) = k ，即g 中没有全零行，于是通过列的变换可以把g 化为系统矩阵 g ”= ，t 彳】 7 疗 疗 一 河，i e 人邢0 0 硕十学何论文 第3 章线性码自同构群的研究 3 1基本知识及线性码自同构群的概念 设甲= 扣，口：口，) 是任意有限集合，则从甲到甲的一个i i 映射仃称为甲i - 的- 个 口。 口： 口。1 置换，置换盯可表示为盯：l 上 山 山 i 【- 仃( 口1 ) 仃( 口2 ) 盯( 口。) j 定义3 1 1 1 关于码的置换有两种，一种是关于下标集合y = 1 , 2 ，n ) 的置换，另 一种是信号字母表c = 0 , i ，z ) 的置换，我们分别记之为 仃。= 仃之，盯支2 2 ，；j 盯 刀， 盯：= 仃曼。，仃支。，；盯2 9 ， ( i ) c l = q ( c ) = p 。( x ) ：x c ) 称之为c 的换位型置换码 ( 2 ) c ：= 仃：( c ) = p ：( x ) ：x c ) 称之为c 的换元型置换码 8 第3 章线。r t | 1 i 一】构群的研究 定义中的g 和c ：码显然仍是q 元( 刀，m ) 码它们与c 都足可逆的，这就存在q 与仃： 型的置换仃l 和仃2 y n 4 $ o i ( c 1 ) = c ，盯2 ( c 2 ) = c 例3 1 1 有限域卵( 3 2 ) = o ，1 ，口1 ，口2 口7 ) ( 口8 = 1 ) 上的矩阵l 0010 0 l 就是一个单 优2 1 卜5 0 0 j 即m = 怛一e = a p 即 m = 只一只_ 人= 鼻人l 例3 2 设m = 匮蚕o 是e 上的矩阵 贝u 三蚕； 三三1 ； = 蚕三； 河北人。理学硕f ? 学位论文 古叟 三 蚕 ； = 三 三 ；三 妻 ； 三暑1 ； 兰蚕詈 = 壹兰； 古殳 兰 蚕 ； = 三 壹 莩圭 三 ； 故 m = p i a l = a p 性质3 1 2 2 设s 是上的所有单项矩阵的集合，贝, j l s l = ( q - 1 ) “刀! 其余选择，位置有以种选择元素为零，且这个非零元素有( q - 1 ) 种选择，故第一行非零元 素的的选择有( q 一1 ) 刀种，类似的，第二行非零元素的选择有( g 1 ) 0 1 ) 种，依次类推， 第，z 行非零元素的选择( q 一1 ) ，从而m 的可能有 p = ( p o ，= 三，嚣 这罩 仃= 雌， 这罩 仃：i 山 上 山i l 仃( 1 ) 仃( 2 ) 仃( 挖) i 是集合 1 , 2 ，n ) 上的一个置换，若 规定 p = ( p o ，= 三暑需力 1 0 第3 章线十牛码白吲构群的研究 3 2 线性码自同构群的简化构造算法 定理3 2 1 设c 是 n ，尼 线性码，c 上= 缸”l = o ，v c c ) ，则有 c = 口l g i + + a k g 女，其中g l g 是c 的一组基，从而 = x ( a l g l + + a k g 女) 7 = 0 即 卜吲。倒= 。 故x c 上z 与每一个g l g t 内积为0 河北人学理硕十何沦文 = x m c 丁= x ( c m r ) r = x ( c m 一1 ) r = x ( c m 一1 ) 由于c m 一1 c ，故x e m = 0 即x m c 上，从而盯( x ) c 上，这就表明盯a u t ( c 上) ，由仃 反过来，由于 a u t ( c 上) a u t ( c 上) 上= a u t ( c ) ，故a u t ( c 上) a u t ( c ) ， 证明 设c l ，c 2 为两个不同的码，且有c l ，c 2 等价，也即对任意的c 。c i ，存在 置换矩阵p ，使得c l p = c 2 c 2 ，分别记c i ，c 2 的自同构群为a u t ( c 1 ) ，a u t ( c 2 ) 令y ：a u t ( c 1 ) 专a u t ( c 2 ) ，仃lh 尸盯l p ， 显然少为单射，n v g 2 a u t ( c 2 ) ，3 c r l = p - 1 仃2 p ， 使 沙( 尸一1 盯2 p ) = p ( p - 1 盯2 一= o r 2 v 盯l ，l a u t ( c i ) ，沙( 盯l ，仃l ) = p ( c r l 盯l ) 尸= p e r l p 一1 尸q p 一= l u ( c r l ) ( 仃l ) 即为同构，a u t ( c 1 ) = a u t ( c 2 ) 定理3 2 4 任取一个单项矩阵m ，则m 是码c 的自同构当且仅当存在a g l 。( f ) ， 证明对任意的c c ，存在唯一的y f ，使c = y g ，如果g m = a g ，那么有 设g 为c 的生成矩阵， g = 三 ， 1 2 第3 章线件码臼l 司构样的研冗 g m = 三2 m = 三2 艺 由假设g ，m c ，从而它们是g ，的线性组合，即 即g m = 。g g 。l m m ，= 三二三：二：3 ：二三二二 = ( 三三：三二 三： = 彳g 并且由a 非奇异，l g n n m 可逆，r a n k ( g m ) = k ， 这是由于等价标准型，存在p ，q 可逆，使p g q = ( 色，0 ) = r a n k ( a p - i , ( 玩，o ) ) = r a n k ( a p - 1 , 0 ) = r a n k ( a p 一) = r a n k ( a ) 注释：由于线形码c 的任意一个单项矩阵m 诱导的自同构对应一个非奇异的k xk 矩 阵彳，使得a g = g m ，故有一个映射 河北人珲。硕十学位论文 另一方向， 任意一个a g l 女( ，) 可以作为线性码c 的一个自同构痧：c - - - cy gh g 由此有 a u t ( c ) cj 皿 ( f ) ，盯hm ，ha ， 引理3 2 1 上述对应诱导一个单同念f ：a u t ( c ) 一g l 女( f ) 证明v 口a u t ( c ) ，则口由一个单项矩阵m 。所确定，从而对应唯一一个满足 g m 口= 彳。g 的a 口，故这是一个影射，进一步，若口，则m 。m 卢，进而以a ， 故上述对应是单射 下面证明其是单同态，v 口，a u t ( c ) ，要证f ( 筇) = r ( a ) r ( p ) 即 a 印= 彳。a ， 由于v c = y g c ( y g ) ( a p ) = c ( 筇) = ( c a ) p = ( c m 口) = ( y g m 。) = ( y a 。g ) p = ( 叫口g ) m p = 儿a g 故上述映射将筇映射为以，如，而r ( a ) r ( f 1 ) 就是口和的象的合成，而另一方面， f 将筇映射为a 筇，即= 以 ， 故这就是同态 结论3 2 1 设c 是k ，尼】线性码，行满秩矩阵q 。是c 的生成矩阵，则有 a a u t c 营b g = g a ，其中b 为k k 阶可逆矩阵 结论3 2 2 设c 是k ，尼】线性码，行满秩矩阵g m 是c 的生成矩阵，则对彳a u t c ， 对a a u t c g a = g a g 。1 g ，其中g 。1 是g 的任何一个广义逆 证明c 是k ，尼】线性码，行满秩矩阵q 。是c 的生成矩阵，则对a a u t c ，对 爿酏f c 船= g ac ：，g a g - i g g a ，其中矩阵a = a i ) - - - ( ) = 三羔，在有解时， 只有唯一解x o = g a g 。 结论3 2 3 设g 是线性码的生成矩阵，其中第f 列与第_ ，列相同，并设置换矩阵 a a u t c ，则将a 的f ，_ ，两列对换所得的置换阵b a u t c 证明由a a u t cjg a = g a g g 显然b a 而g b = g a ， 于是g b g g = g a g 。1 g = g a = g bjb a u t c 第3 章线性码门同j ：j 群的研究 结论3 2 4 定理3 2 4 引入的满同念映射是单射，当且仅当线性码c 的生成矩阵g 的列互异 证明先必要性：若g 中有两列相同，则有彳，b g ，a b ， 而g a = g b ( 彳) = g a g = g b g = ( b ) 充分性：令a 沙( g ) jg a = g a g m g = ，t g = gja = i 。，故y 是单射 上面内容可以用校验矩阵来代替上面的生成矩阵来讨论，可以得到相似的结论 定理3 2 5 设c 是【，z ，后】线性码，行满秩日( 枞m 是c 的校验矩阵，则 a a u t c 铮b h = h a ，其中日为( n 一后) ( n k ) 阶可逆矩阵故有一个映射：y ： a u t c 专g l _ ( - k ) ( f ) ，ah b ，上述少诱导一个同态，当且仅当h 的列互异时该映射为单射 引理3 2 2 设线性码的校验矩阵h 的第i 列和第j 列相同，如置换矩阵a a u t c ， 将a 的f ，两列对换所得的置换矩阵a a u t c 证明a a ，但显然有h a = h a ，又由a a u t c 知存在b 使b h = h a = h a ，由定 理知a a u t c 定理3 2 6 是单射线性码c 的校验矩阵日的列互异 证明j 由上述引理知，如日有两列相同，b h = h a = h a ，此时b 对应了4 ，彳均 属于a u t c ，这与为单射矛盾故日的任意两列互异 仁如不为单射，即对vb g ( a u t ( c ) ) ，存在彳，a 。a u t ( c ) ，使b h = h a = h a ，则 必然至少有两列相同，这与日的任意两列互异矛盾，故y 为单射 下面证明为同态 口，a u t c = a u t ( c 上) 对vc c 上，c = c t h 其中以，a 口为口，所对应的置换矩阵，且由定理知 h a 。= b b h ，h a b = bb h c ( 筇) = ( 优h ) ( 筇) = ( c 口) = ( d 心) = ( a l i a 。) = ( a b 口日) = ( a g 。h ) a 口= a b 口b a h 故将口，映射为吃， 故为同态，c ( 筇) = 胡和 1 5 河北人。学理。学硕十学位论文 出定理3 2 6 知g 为l 司念当且仅当h 的列互异 定理3 2 7 若线性码c 的生成矩阵日= 旧。h ：】( 枞m ， ( 1 ) 若h 。是( 胛一后) 阶可逆矩阵，则将彳分块成a = 【a la ： ，其中4 是n ( ，z - k ) 矩 阵，则a a u t c h a l h l h 2 = h a 2 ( 2 ) 若h 。不可逆，则存在置换矩阵尸，使得h l = h p = h 。h ： ，日。可逆，此时的 码的同构群与a u t ( c ) 同构 证明( 1 ) 此时的情况与文献中的定理4 证明类似 ( 2 ) 通过置换矩阵p 使日的列置换得到的码记为c l ，从而c 与c 。等价，由前 面定理3 2 2 知a u t ( c ) = a u t ( c 上) ，即证 推论( 1 ) 若h = ih 2 】，则盯a u t c 兮h a l h 2 = h a 2 ( 2 ) 若日= h l ，】，即此时c 的生成矩阵是g = ，一h i r 】，盯a u t ( c 上) ，因 此有时用校验矩阵更方便 由上面内容，给出判断自同构的简化算法： 算法：对于【，z ，k 】线性码c ，其生成矩阵记为g = 【g 1g ：】，g 。为k 阶可逆矩阵 e l = ( 1 ，0 ，0 ，o ) ，e f = ( 0 , 0 ，1 , 0 ) e 。= ( o ，0 1 ) ( 1 ) 首先从刀个这样的p ，中任意挑选后个互不相同的出来( 记排列顺序) ，不妨记为 a l = ( p 舯e f 2 e i k ) ，一共有彳。种 ( 2 ) 将剩下的( 珂- k ) 个作排列，一共有( ，l 一忌) ! 种记为a 2 = ( e 州，e 让+ ：e 加) ( 3 ) 此时作等式判断：如果满足：g a l g 2 = g a 2 ，则这样的a = a 。a ：】就满足要求， 然后对下一个这样的4 做同样的判断，直到所有的( n 一尼) ! 全部判断完毕 ( 4 ) 再重复以上的第一、二、三步，直到这样的彳。种全部判断完毕 3 3 c 上的投射空间与线性等重码的自同构群 设。表示有限域上的七维线性空间，上的任何一个非零向量生成一个一维子空 f o - j 上的所有一维子空间构成的集合称为上的投射空间，记作尸g ( ) 对任意的l ，尸g ( ) ，存在x ，y ，使得( 石) = l ，( y ) = ，且l = 当且仅当 1 6 第3 章线性码门同构群的研究 ( x ) = ( y ) 当且仅当存在o d f q ，使得x = 咖 引理3 3 1 设c 是g 元线性码 ( 1 ) c 是等重码当且仅当存在一个g 元的极大投射码d 及非负整数m ，s 使 c 南南 此时码c 的参数是 s + m ( q 一1 ) ( q 一1 ) ，尼，m q h 】 ( 2 ) c 是极大等距码当且仅当( 1 ) 成立且其中s = 0 引理3 3 2 设彳g l t ( f ) ，则映射 彳】：p g ( f q ) 一p g ( f q 。) ，lh 彳 是双射，这罩 彳 l = 彳= ( 砂) ，其中( y ) = 三 证明若三= ，即存在o y ，使- - y ) = ( y ) ，因此存在d f ，使得j ，= d y ， 从而 彳】= ( 砂) = ( 彳咖) = ( 砂) = 么恤，故上述对应是映射 又若 彳 三= 么 ，即( 砂) = ( 砂。) ，从而存在d f + ，使 a y = d a y 由a 可逆知， y = d y 亦即 ( y ) = ( y ) 因此1 5 , = 为单射 v p g ( f 。) ，不妨设o j ，f k 使- - - - 2 ，所以a u t ( q ) 由保持o 不变的所有单项式m = a d 构成 由于q 是线性的，因此若m a u t ( q ) ，则v t g f ( i ) ，有t ( a d ) a u t ( q ) 为方便计算，只考虑，= 1 的情况，并把这样得到的a u t ( q 。) 的元素记为a u t ( q ) + 【1 2 】 定义3 4 2 设p 是形如8 m 1 的素数，则 0 , 1 ，p l ，0 0 ) ( 即一维映射空问) 的一切 形如y 一型等，口，6 ，c ，d g f ( p ) 且耐一b c ：1 洲十口 的置换称为特殊射影线性群，记为尸 钇2 ( 竹，_ 1 1i p s l 2 ( p ) i ：i 1 ( p 2 1 ) p ，p s l ：( p ) 可有3 个 置换 s ：y y + 1 ，v ：y 专p 2 y ，t ：y 专1 y 生成( 其中p 是g f ( p ) 中的本原元) 据g e a n s o n p r a n g e 定型3 1 ，a u t ( q ) + 包含一个与p s l 2 ( p ) 同构的群，此群可由s ，v 及 t 。生成，其中丁是丁的如下单式推广，即对向量c = ( c o ，c l c 川，c 。) ，若c 的分量的脚 标待o o 及i f i ，则将c 乘以1 后，在作用置换t ：f 专一1 i ；若c 的分量的脚标f - 0 及 i r 2 ，则将g 乘以( 一1 ) 后，在作用置换t ：f 一一l f 准上，对于，= 3 ，p = 1 1 时，因 r l = 1 ，3 ，4 ，5 ，9 ) ，r 2 = 2 , 6 ，7 ，8 ，1o ) 于是 ( i ) s = ( o1234 5678 91 0 ) ( i i ) 因2 是g f ( 11 ) 的本原元，所以令v ：y 专4 y ，则得出 0 1 234567891 00 0l y = l l048 1 5 92 61 03 7o ol ( i i i ) 由于丁：l o12345 67 89 1 0 0 。i o o 1 0578 2 934 610 所以据丁的定义 c t 。= ( 2 c o ，c l ，2 c z ，c a c 4 ，c s ，2 c 6 ，2 c 7 ，2 c 8 ，c 9 ，2c l o ，q ) t = ( 2 c o o ，c i o ，2 c s ，c 7 ，c 8 ，c 2 ，2 c 9 ，2 c 3 ，2 c 4 ，c 6 ，2 c l ，c o ) 兹用本文的推论来验i es ，v ，t a u t ( q ) + 经计算6 1 2 阶的行满秩矩阵( g f ( 3 ) 上的) g = 【g lg 2 】= 其中g l 一= 1o o1 0o 20 o 2 0o 22 o2 11 12 o0 2 2 o1 21 o2 1 1 1o 22 ，g i - i g 2 = 2 l 22 o2 22 1o 12 12 o1 2l 12 1l lo 2 2 o o o o o 1 l o 1 1 1 1 o l 1 0 0 1 1 1 1 0 0 1 l 1 o o o 1 l o o 0 l 1 0 0 0 1 0 1 o o 1 o l l 0 1 0 1 1 l l o l 1 0 1 o l l 0 1 1 1 l o 1 1 1 河北人学理：锄贞十。伊论文 的行是q 。的生成矩阵g 的行向量极大无关组，所以q = s p a n g = s p a n ( g ) ( 行生成 空间) 于是由推论知： m = a d r ，m ( a u t q ) + g a l d l g i - i g 2 = g a 2 d 2 ， 其中 。= r 最 为了方便起见，将上面得出的s ，v ，t 及丁作改写：以f + 1 代替f ，i g f ( 1 1 ) ，且以1 2 代替o o ( 即射影直线上的无穷远点) ，并写出了上面置换对应的矩阵，则 s ：f 123456 789 1 01 11 2 ih 置换阵 = ih _ ! 酋：抉阵 234567 891 0 1111 2i a s2 ( e 23456789l o l l i1 2 ) v ：i 12 34567891 01 11 2 ih 置换阵 = llh 首换阵 l1 5 9261 0371l481 2i a y2 ( e l5926i o37l l481 2 ) 丁：l 12345 678 91 01 11 2i ”置换阵 ，t -1 ；l 1 ml ( 7 i1 2 1 168931 045721 i a r2 ( e 1 2i l68931 04572i ) 由t 的定义知，它对应的矩阵是一个单式阵m = d a 7 ，其中d = ( 2 121 11222121 ) 为了利用( 1 ) 式末判断丁。是否属于a u t ( q ) + ，利用命题1 ，将m = d a r = a r d ，其中 d 一- - ( 121222 1 1 1212 ) ，并将彳7 及万做如下分块： 则经计算有 g a 而万l a l - 1 a 2 = o o ll lo l1 o1 11 a r l5 e 1 21 1 6 89 3 ) ，a r 2 = e l o4 5 7 21 ) d l = 121222 ) ，d 2 = 111212 ) ， o 2 o o 1o o0 12 12 02 12 10 02 12 l2 = g a 疋d 2 t a u t ( a ) + ( 由( 1 ) 式得) 第3 章线。r f 码自同构群的研究 类似地可推断s ，矿a u t ( q ) + ( 作m o d 3 运算) ，此时只要令d = ，p 即可 下面来算由s ，y ，丁所生成的群的阶，为此先求丁的阶，即m = 彳，d 的阶因吲= 2 ， 知1 4j = 2 ，由命题2 ，令石= 瓦= l 212221 1 1212 ) ，因4 = 编：1 1 6 。，3 ，：) ，所以， d i = 2121 1 122 2121 ) ，显然d i 哦= 2 1 从而m 2 = ( 4 历) 2 = 4 2 酉d o = 2 1 ， m 3 = 2 m ，m 4 = ，所以阻i = 4 ，因此 v 7 s 7 ( 丁) s 7 a u t ( q ) + ，其中0 i 5 , 0 ， 11 , 0 k 4 例3 4 2 一个更有启发的例子是，= 11 ，p = 7 的二次剩余码 此时i = 1 ，2 ，4 ) ，t 2 = ( 3 ，6 ，5 ) o 的幂等多项式是( x ) = 2 + 4 ( x + x 2 + x 4 ) + l o ( x 3 + x 6 + x 5 ) ，q 的扩展码q 。的生成 矩阵是 。? ， ( q ) 上= o 且行满秩矩阵g = c g q ，= r 季 可作为o 的生成矩阵( g f ( 11 ) 上的矩阵) g ，= 1 1 08 i，g。1g：=i 4 5 7 , c 作m 。d 运算， s = i 三；4 3 ；主7 6 ；耋l 彳s = c 乞。，。，。， y = i ：量三7 4 主三：薹i h 彳，= c p ，：。，c t 议