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

硕士学位论文 m a s t e r st h e s i s 中文摘要 线性码的自同构群是代数编码中的一项基础研究，它对于译码算法的设计，密 码体制的设计和分析都具有重要的基础意义然而一般说来，寻求一个线性码的自 同构群很困难在文献 1 8 和 2 0 中；使用矩阵广义逆理论给出了颇为有效的结论 尽管如此，由于在码论中，一般计算量都非常大，因此很有必要对以上的结论作进 一步研究和简化以减少计算工作量本文在文献c 1 2 、 1 9 、 2 1 的基础上进一步 研究了线性码的自同构群问题，获得了以下结果： 1 利用在二元情况下，线性等重码的自同构群与其对偶码的自同构群相同的 性质，根据线性码检验矩阵的性质，简化了自同构群的计算 2 ，给出了任意有限域上线性等重码的自同构群 3 利用任意线性码等价于系统码，而等价码的自同构群也同构的性质，更加 简化了自同构群的计算 关键词：线性码，系统码，有限域，线性码的自同构群，线性等重码的自同构群 硕士学位论文 m a s t e r s1 1 i b s i s 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 sb a s i ci nc o d i n gt h e o r y i ti sv e r yi m p o r t a n tf o rt h ed e s i g no fd e c o d i n ga l g o r i t h m ，t h ed e s i g na n da n a l y s e so f c r y p t o g r a ms y s t e m b u tg e n e r a l l ys p e a k i n g , f i n d i n gt h ea u t o m o r p h i s mg r o u po fl i n e a r c o d ei sv e r yd i f f i c u l t i nb i b l i o g r a p h y 【1 8 】a n d 【2 0 】，t h r o u g hu s i n gg e n e r a l i z e di n v e r s et o f m dt 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 sam o r ee f f e c t i v em e t h o d b u tt h e c o m p u t a t i o n a lq u a n t i t yi sv e r yh u g e ，s oi t i sn e c e s s a r yt of m dam o r ee f f e c t i v ew a yt o i n d u c et h ec o m p u t a t i o n a lq u a n t i t y b a s e do nt h eb i b l i o g r a p h y 【1 2 ，【1 9 】a n d 【2 a ，i nt h i s t h e s i s ，w ed of u r t h e rr e s e a r c ho nt h ea n t o m o r p h i s mg r o u po fl i n e a rc o d e ，a n do b t a i ns o m e o ft h ef o l l o w i n gr e s u l t s 1 a c c o r d i n gt ot 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 se q u a lt ot h ed u a lc o d e o v e rf m i t ef i e l df 2 ，u s i n gt h ep r o p e r t yo ft h ep a r i t yc h e e km a t r i x ，t h ec o m p u t a t i o no ft h e a u t o m o r p h i s mg r o u po fl i n e a rc o d ei ss i m p l i f i e d 2 t h ea u t o m o r p h i s mg r o u po fl i n e a re q n i w e i g h tc o d eo v e ra n a r b i t r a r yf i n i t ef i e l di s g i v e n 3 a r b i t r a r yl i n e a rc o d ei se q u i v a l e n tt os y s t e m a t i cc o d e ，a n dt h ee q u i v a l e n tc o d e s a u t o m o r p h i s mi sa l s oi s o m o r p h i s m ，s ot h ec o m p u t a t i o ni sa l s os i m p l i f i e d k e yw o r d s ：l i n e a rc o d e ，s y s t e m a t i cc o d e ，f i n i t ef 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 r c o d e ，e q u i w e i g h tl i n e a rc o d e 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：屈o 盟 ， 日期：2 ”7 年，月2 日 ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：屋7 c 7 连 日期：上呻7 年石月2 日 导师签名： 日期：年月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a m s 高校学位论文全文数据库”中全文发布，并可按“章程” 中的规定享受相关权益。回童迨塞趁窑匿澄厦! 旦圭笙；旦= 玺i 旦三生筮鱼! 诈舌签皂：| 毛内遗 日期：细7 年石月z 日 导师鏊名： 日期：年月 8 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景 第1 章引言 编码理论与信息论大约在2 0 世纪4 0 年代后期由g o l o y ，h a m m i n g ，s h a n n o n 等人 的工作( 见文献 6 ， 7 ， 9 ， 1 6 ， 1 7 ) 而创立在最初的时候，编码理论的 数学基础并没有信息论那样完善，而且在很长的时间内也没有得到应有的重视然 而，随着计算机技术和通信技术的迅猛发展，各种数学工具，诸如群论、有限域理 论以至于线性规划等都应用于编码理论，编码理论与数学理论的结合越来越紧密， 许多深奥的数学理论都在编码理论研究中得到了应用，从而使得编码理论也成为通 信领域中的一个研究热点 线性码是一种非常重要的分组码，是讨论各种码的基础，一些特殊的线性码的 编码方案和译码方案都比较简单，并且一些特殊的线性码都具有比较好的性质，绝 大多数的已知好码都是线性码，因此对线性码的研究一直成为编码理论中的中心课 题 作为一种标准化的基础信息技术，有限域上的线性码在各类数字系统( 如通信 网络、存储系统等) 中有着广泛的应用，而线性码的自同构群可用于译码算法和密 码体制的设计。因此如何获得线性码的自同构群成为值得研究的一个问题 1 2 国内外研究现状 线性码的自同构的研究开始于m a c w i l l i a m s 在1 9 7 7 年发表的文章i t 3 ，在这 篇文章中给出了判断一个置换矩阵是否属于自同构群的充分必要条件文章 2 0 讨论了对有限域上的任何一个矩阵，它的钍 一逆的存在及计算问题 2 0 0 0 年，石剑平在文章 1 8 中利用矩阵广义逆理论，给出了两个重要定理， 对理论分析及实际计算一个线性码的自同构群有很大帮助，将求取一个线性码的自 同构群的元素演化成：求取矩阵的 l 一逆、矩阵的乘积、等式判断等 在此基础上，王国栋和石剑平研究了线性码的自同构群问题，在文章“线性码 的自同构群”中( 见文献 2 0 ) ，使用矩阵广义逆理论对线性码的自同构群进行了研 硕士学位论文 m a s t e r st h e s i s 究，得出了一些颇有价值的理论及一些很有效的计算方法，将线性码的自同构群的 研究推进了一步；文章 1 2 、 1 9 中王国栋、陆正福等人对g f ( 2 4 ) 上线性码的自 同构群作了进一步的研究，获得了一些具有理论价值和实际意义的结果，进一步深 化了对码的自同构群的认识：但文献 1 2 、 1 9 的结果还仅限于g f ( 2 ”) 上，为了使 这些结果可用于更多的码类，王国栋等人在单项矩阵理论的基础上，将线性码的自 同构群的一些结论推广到一般的有限域g f 0 ”) 上去，得到了一些结果( 见文献 2 1 ) 1 3 本文主要研究内容 本文在王国栋等人研究工作的基础上对线性码的自同构群作了进一步的研究， 获得了一些新的结论： ( 1 ) 利用在二元情况下线性码的自同构群与其对偶码的自同构群相等的情况， 根据线性码检验矩阵的性质，简化了自同构群的计算 ( 2 ) 给出了任意有限域上线性等重码的自同构群 ( 3 ) 利用任意线性码等价于系统码，而等价码的自构群也同构的性质，更加 简化了自同构群的计算 2 硕士学位论文 m a s t e r st h e s i s 2 1 基本概念 第2 章基本概念及引理 代数学的基本理论是线性码的数学基础，本节主要介绍的代数学和编码中的某 些有关基本知识是下面章节所必需的 2 。1 1 群 定义2 i 【4 1 设a 是一非空集合，任意一个由a x a 到a 的映射称为定义在彳上 的一个代数运算 定义2 2 1 4 1 设g 是一非空集合，如果在g 上定义了一种代数运算，称为乘法， 记作a b ( 或称为加法，记作a + 务) ，而且它适合以下条件，那么称g 为一个群： ( 1 ) 封闭性，即v a ，b e g ，有a b e g ； ( 2 ) 结合律，即讹，b ，c e g ，有a ( b c ) 一( 口6 k ； ( 3 ) 存在一个左单位元e ，即 c a g ，有e a - 口： ( 4 ) g 中每个元素存在一个左逆元，即v a e g ，存在口一e g ，使得口。1 4 ，p ， 这里的a 4 泛指逆元 2 1 2 有限域 定义2 3 t 3 对于至少含有一个非零元素的交换环f ，若每个非零元素都存在 乘法下的逆元，则称该交换环为域 定义2 4 p 1 只含有有限个元素的域称为有限域含有可个元素的有限域通常 记为，或者g f ( q ) 定义2 5 3 1 在有限域g j f 白) 中，每一个非零元素均满足工- 1t 1 ，即都是方程 z 一一1 ；0 的根反之，石州一1 0 的根必在6 f ( 吁) 中 1 硕士学位论文 m a s t e r st h e s i s 定义2 6 研设f 是有限域并设f 的特征是p ，那么f 的元素个数一定是p 的 一个方幂 2 1 3 有限域上的线性空间和线性变换 下面将介绍线性码，为此先介绍有限域上线性空间和线性变换的定义 定义2 7 2 1 设矿是一个非空集合，c 是一个g 元有限域在集合y 的元素之间 定义了一种代数运算，叫做加法；这就是说，给出了一个法则，对于y 中任意两个 元素口与芦，在y 中都有唯一的一个元素y 与它们对应，称为8 与的和，记为 y 一口+ 芦在有限域瓦与集合v 的元素之间还定义了种运算，叫做数量乘法；这 就是说，对于有限域c 中任一元k 与v 中任一元素a ，在矿中都有唯一的一个元素 6 与它们对应，称为七与口的数量乘积，记为6 一k a 如果加法与数量乘法满足下 述规则， ( i ) ( v ，+ ) 是个交换群； ( 2 ) 对任意的a ，卢e v ，七，z e ，有 ( i ) 七( 口+ 声) k a + t 芦； ( i i ) ( k t ) 口- 七o a ) ； ( i i i ) + o a - k a + k ； ( i v ) 】口- a ， 那么y 称为有限域上的线性空间 定义2 8 t 2 1 如果在线性空间v 中有n 个线性无关的向量，但是没有更多数目的 线性无关的向量，那么y 就称为，l 维的 定义2 9 2 l 线性空间y 的一个变换a 称为线性变换，如果对于矿中的任意的元 素口，卢和有限域c 中的任意元七，都有 4 ( 吐+ 卢) 一彳- ) + 彳( 卢) ， 4 硕士学位论文 m a s t e r s1 w e s i s a ( k a ) 一翩仁) 2 ，2 线性码的相关概念及几个引理 下面简单介绍一下码、线性码、系统码及对偶码 定义2 1 0 h 设a 是一个有限集合，称之为字母表由4 中元素构成的有限序列 ( 简称串) 称为字，序列长度称为字长字的全体记作a 任意两个字z ，y 连起来可显 然还是一个字，这就是在a 中定义了一个运算，称为乘法在此运算之下爿成为一 个幺半群设c 是a 的个子集如果下述条件满足( 可识别条件) ： 对于任意c z ，c 2 ，c m ，c ：，c ：，c ：e c ，只要c l c 2 c 。c l ：c ：就必有 棚一履，而且c i - 0 对于i l 2 , ，玎； 则称c 为字母表a 上的一个码码c 中的字称为码字若c 中的所有码字c 的长 度为定值，则称c 为定长码；否则称为变长码若陋l 。筇，则称c 为雄元码 定义2 1 1 卅设f 是含q 个元的有限域，f - k ，屯，毛) l 玉f 是f 上的 露元组构成的向量空闯f 4 的任一个非空子集c 称为f 上的一个0 ，毖) 码，其中 m i c l 为c 的基数，其中的向量称为码字，称长h 的g 元码进一步，若c 是f ? 的 - - + t 维子空间( 从而肼= q ) ，则称c 是f 上的一个k ，七 线性码，其中珂称为c 的 长度，而七称为c 的维数 定义2 1 2 4 1 对任意的x 瓴，屯，) ，。，称吣) - i 0 x , 一o , l s i ，1 ) 为向量 的h a m m i n g 重量，简称重量 定义2 1 3 4 1 对任意的石- “，x 2 ，- - - 9 毛) ，y - 0 1 ，) 2 ，y 。) ，“，称 a ( x ，y ) - w ( x y ) 为向量x ，y 的h a m m i n g 距离，简称距离 定义2 1 4 3 1 设c 是- - + q 元仁，目) 码，y 忙，g ) 是含有q 个元素的有限域，维 5 硕士学位论文 m a s t e r st h e s i s 数为k ，如果存在k 个分量位置，f ：，i k ，使得去掉码c 中的其它n k 个分量后， 所得到的向量全体为v ( k ，可) ，则称码c 为具有七个信息位的口元系统码分量 i l , t ：，f 。位置称为信息位，其余n - k 个分量位置称为校验位这里 1 皇i ls i 2s s i ks 捍 定义2 1 5 慨，y e f 4 ，工- g ，工：，) ，y 一( y l ，) ，2 ，y 。) ，称 x ，y ，l 习7 - x , y 1 + x 2 y 24 - - + y 。为x , y 的内积 定义2 1 6 川设c f “是一个码，其正交子空间 c 1 一 工e f 4j 似c ) - o c 称为c 的对偶码， 定义2 1 7 t 4 1 线性码c 称为线性等重码如果任意两个非零码字的重量相等。 定义2 1 8 【4 1 如果码c 的任意两对码字的距离相等( 从而任意一对码字的距离 等于极小距离d ) ，则c 称为等距码 引理2 1 【习线性码是等距的当且仅当它是等重的 引理2 2 【司设c 是q 元线性码 ( 1 ) c 是等距码当且仅当存在一个鸟元的极大投射码d 及非负整数m ，s 使 c 气南南) 此时码c 的参数是p + 垅q 一i ) ( g 1 ) ，嘉，m q “1 】 ( 2 ) c 是极大等距码当且仅当( i ) 成立且其中s 。0 6 硕士学位论文 m a s t e r st h e s i s 第3 章线性码的自同构群 3 1 单项矩阵及其性质 定义3 1 m 1 称有限域g ，白焰。p 4 ) 上的雄斗阵肘为单项矩阵，若膨的每行每 例有限域g f ( 3 2 ) 一 o ，1 口1 ，口2 ，口7 ( a 8 - 1 ) 上的矩阵j i o oo l i 就 f 口2 0 1 i 00 i 等矩阵置，最，只， 即 m - a b - 1 只一一a 尸 另一方面，若对肼施行行的初等交换将盯的非零元变到主对角线上，则有 b 置m a m - 只b a a 置a 。 例 设材；曙i ； 是e 上的矩阵， 7 硕士学位论文 m a s t e r ，st h e s i s 删 删雕习 - 【| ； 删 _ 性质3 2 设s 是上的所有单项矩阵的集合，贝f j i s l 。白一1 r ，l ! 素，其余元素为零，且这个非零元素有白一1 ) 种选择，位置有一种选择，故第一行 非零元素的选择有( 鼋一1 ) 狂种，类似的，第二行非零元素的选择有奄一1 ) & 一1 ) 种， 第苊行非零元素的选择白一1 ) ，从而m 的可能有 心一1 ) 以q 一1 ) - 0 1 ) 伯一1 ) = q 一1 y 玎! 硕士学位论文 m a s t e r ，s t 脏s 1 s p b ) 一甓7 嚣 这里 口。( 三) 是集合 1 ，2 ，n ) 上的一个置换 口。f 南 规定 p - 叫盏7 嚣 则它们一一对应因为 c o 一k 1 ) ，c 。扣) ) 一( c l ，c 2 ，) p 定义3 2 设c 为线性码，a ：c c 是f 上的一个变换，m 是一个单项矩阵， 且口：c c ，c h c m ，令 a u t ( c ) = a 。f 口。( c ) - c m ，v c e c ， 则a u t ( c ) 在变换合成运算下是一个群，称为码c 的自同构群 性质3 4 设c 为线性码，c 1 为c 的对偶码，则a u t ( c ) = a u t ( c 1 ) ( 二元情况 下) 证明只需证它们相互包含。 设盯a u t ( c ) 且口( c ) 一嘶，从而由a u t ( c ) 是一个群，知 盯。1 ( c ) 。c m e c 故v x e c ，有o ( x ) - x m ，且v c e c 有 埘p - x m c t l x ( c m 1t 1 算( c - m “) t 工c m 4 ) 由于c m e c ，故x c m = 0 亦即x m c 1 ，从而仃g ) c 1 ，这表明 、jv、j 尢0 n g a g lj lf 3 o 3 d 口 、-，、， 2 乜 2 q 口若 g 硕士学位论文 m a s t e r st h e s i s 仃a u t ( c 1 ) ，由仃的任意性，即a u t ( c ) a u t ( c 1 ) 反过来，由于a u t ( c 1 ) a u t ( ( c 1 ) 1 ) a u t ( c ) ，i 玫a u t ( c - ) a u t ( c ) ， 从而a u t ( c ) = a u t ( c 1 1 性质3 5 设c 是k ，豇】线性码，c 1 一长“i t x c o , v c c ，则有 ( 2 ) ( c - 卜c ， 证明( 1 ) 设g 是i n ，k 线性码c 的生成矩阵，则v x e c l ，c e c ，有 工，c 戈( 4 ：g i + + g r - 0 工【( 4 1 吲卜 ( 2 ) 另一方面，显然 c ( c l r ，由于 d i m ( ( c 1 ) 1 ) - n - d 舭 t 一1 - ( n 一七) 一七 故 c 。( c 寸 1 0 硕士学位论文 m a s t e r st h e s i s 3 2 线性码的自同构 a g l k ( f ) ( 七级一般线性群) ，使得伽a g ，且满足g m a g 的彳由m 唯一 证明对任意的c e c ，存在唯一的y e f ，使c - y g ，如果g m a g 那么 c m - = ( y c ) m y ( c m ) - ；y ( a o ) ，( y a ) c , e c 设g 为c 的生成矩阵，g 。( 三 ，那么 缸刖竺 由假设反me c ，从而它们是毋的线性组合，即 g m 。f 。g g k l - m1)。、4a。n。ggx。+-+a。n。ggt。 硕士学位论文 m a s t e r st h e s i s 枷 并且由a 非奇异，且因为m 可逆，r a n k ( g m ) - k ， r a n k 0 g ) = r a n k ( g ) - k ， 这是由于由等价标准型，存在户，q 可逆，使 p g q - 慨，0 ) k r a n k ( a a ) 。r a n k ( a a o ) 。r a n k ( ，铲1 粥q ) 一r a n k p 眩，o ) ) 一r a n k 洳- 1 ，o ) 一r a n k 陋4 ) 一r a n k ( a ) 乜一鳓g 一0 r a n k 汹) 。0 从而 1 2 另一方面，任意一个a e g l 。( ，) 可以作为线性码c 的一个自同构 庐：c c ，y u 卜y d “ 由此有 a u t ( c ) - c - g k f ) ，口f - - ) m 。一以 b i 理3 1 上述对应诱导一个单同态f ：a u t ( c ) - , g l 。( f ) 证明w e a u t ( c ) ，则a 由一个单项矩阵膨。所确定，从而对应唯一一个满足 g m 。- a o g 的以，故这是一个映射进一步，若a ，芦，则j ! i f 。- m ，进而爿。_ a p ， 故上述对应是单射 下面验证其是单同态，v a ，f l e a u t ( c ) ，要证f p ) - f 仁k ( 卢) ， 即 a 胡- 以4 ， 由于v c 。y g e co g x 筇) c 伽) - ( c a 扮- 。驴 = y g m 。冶。g 冶- ( y a o a ) m 口 2 ) “。a $ g 故上述映射将筇映射为4 。a 。，而百仁弦) 就是口和卢的像的合成而另一方 面，f 将筇映射为以口。即如- a a a ，故这是同态 推论3 1 设c 是一个k ，七】线性码，则a u t ( c ) 是g l 。( f ) 的一个子群， 引理3 2 设置换矩阵4 一k 8 f 2 e l , ) ，其中沈是1 2 行的一个排列若排列 中的自然数f 在第七，位置上e - l 2 ，几) ，则 ( 1 ) 么。蚧t t ) = e 屯 o e i 。 ，其中瓦，- ( o 0 1 0 o ) 是单位行向量 硕士学位论文 m a s t e r s1 1 i e s i s ( 2 ) 4 4 。爿7 。g h 8 矿叩) 一 气 气 ： c l 。 ，置- ( o 0 1 0 o ) 证明( 1 ) 若排列中的自然数f 在第七，位置，则在气列的第f 个位置为i ，亦即 在第七，行的第七，列为1 ，因此的第七，行为气从而 ( 2 ) 因为 所以由( 1 ) 知 彳l 气 一 龟， ： 气 f 1 ，i 一， 。t 州 彳( e k i e b e ) 。e 气) 一1 彳一。彳t 。( e k z e k z e k , 1 。 3 2 2 上的投射空间与线性等重码的自同构群 e i e b ： e k 。 设表示有限域上的七维线性空间，上的任何一个非零向量生成一个一 维子空间上的所有一维子空间构成的集合称为c 上的投射空间，记作 p g ( 硭) 1 4 i l虬忏i 气；一 硕士学位论文 m a $ t e r st h e s i s 对任意的，l p g ( 。) ，存在量) ，使得仁) 一工，( ) ，) t 工，且 一当且仅当x q y ，当且仅当存在。一d e f ，使得z - d y 引理3 3 设彳g k 伊) ，则映射b 】：p g ( 曩) 一p g ( ) ，工卜阻 已是双射 这里阻卫一渺) ，其中( y ) 一 证明若l ，即存在o - ) ，工，使工- ( y ) 一) ，因此存在d f + ，使 y 7 - d y ，从而阻t 7 一油) - ( a d y ) - ( a y ) 一队 l ，故上述对应是映射 又若d k ；胁i ，即细) - 协) ，从而存在d f ，使 4 y 一正4 y ， 由4 可逆知， 亦即 因此 这是单射 vl p g ( f ) ， 令工一0 4 y ) ，则 y 一d y ( y ) 一( y ) ， 暑l 不妨设o 。y f 使l - ( y ) 阻蕾一0 a l y ) - ( y ，) 一三 这表明上述映射是满射，因此，它是双射 定理3 2 设c 是上的一个k ，女】线性等重码，则a u t ( c ) = g l 。( f ) 证明对任意e p g ( ) ，由引理2 2 ，存在正整数研，使得l 在f 的生成 矩阵g 的列中恰好出现聊次，即存在o ( f y ，f 一1 ，扰，满足“) 一， 现对勘g k p ) ，考虑 a g 一彳“，o ，0 ) ；，月o ，o ，0 ) 硕士学位论文 m a s t e r st h e s i $ 由引理3 3 ，可逆矩阵4 诱导投射空间p g ( 硭) 上的一个双射 阻】：p g ( ) 一p g ( ) ，卜乜】己 这里阻p 一协) ，对l - ( y ) 特别地 l e 一阻k 一似) - 似，) 。工一工一( ) 一( o ) 这里( ) - l ，( 0 ) - l 设l e p g ( f q ) ，那么爿o ，l - 1 ，_ l ，l 恰好是4 g 中的小列满足 。) * - 卫； 但另一方面，在g 中存在朋列o ，l - 1 ，加，满足( r ，7 ) - b l ，这是由于曲 是 投射空间上的一个双射由此有 ( 4 r ，) 一( 0 7 ) ，l 一1 ，历 从而存在d ，e f ，一1 ，册，使得 知，j ，d f ，z - 1 ，肼 让三跑遍p g ( ) 中的所有元素，那么五，l 和爿，l 的各自的并集就是g 的非 。列的指标集艮2 ，雄，】即 ( ：) 是阻2 ，l ，忍】的一个置换，它对应一个置换矩阵p 设d 是一个甩x 甩对角矩阵，其在 对角位置上的值为矾，而在其它对角位置的 值为1 ，那么m p d 就是一个单项矩阵，而且我们得到 a g 一，l ，一，2 ，4 。，o ，0 ) - g m 从而a 诱导c 的一个自同构 硕士学位论文 m a s t e r sn i e s i s 3 2 3 有关线性码的自同构群的迸一步讨论 引理3 ，4 任意线性码都等价于一个系统码 证明设g = 为某- - n ，k 】线性码的生成矩阵，由于任意矩 阵均可经初等变换化为简化阶梯形矩阵g ，即g 可化为简化阶梯形矩阵因为“的 k 个行向量线性无关且构成这一线性码的基底，r a n k ( g ) 一k ，因初等变换不改变矩 阵的秩，因此r a n k ( g ) 一k ，即g 中没有全零行，于是通过列的变换可以把g 化 为系统矩阵g ”一阢彳】 引理3 5 等价码的自同构群同构，即在同构意义下相同 证明设c l ，c ：为两个不同的码，且有q 与c ：等价，也即对任意的c 。c l ，存 在置换矩阵只使得c 1 p c ：e c ：，分别记c l ，c 2 的自同构群为a u t ( c 1 ) l a u t ( c ：) ， v a l a u t ( c 1 x ( j r z a u t ( c 2 ) 令 伊：a l l t ( c 1 ) 一a u t ( c 2 ) ，吼h p a ，p ， 显然妒为单射，i jv a ：e a u t ( c z ) ，j q - p o r ：p 使 伊( p 1 盯：p ) = p c p 4 盯：p ) p 一一o r ： 即为满射，且易知 v q ，a e a u t ( q ) ，伊p ，一) 一p ( 盯。叫) p 4 - p a 。p 。p a 夕一一伊( 吼k ) 即妒为同构，a u t ( c 。) - a u t ( c ：) 定理3 3 若c 的检验矩阵为日= 随日：l 一。k ( 1 ) 若日。是，l k 阶可逆阵，贝o j 令a ；d 。( 一盯将彳分块成 1 7 硕士学位论文 m a s t e r st h e s i s a m4 】，其中4 是玎o 一七) 阵，贝l j a e a u t ( c ) 一h a ，h ：- 她； ( 2 ) 若日。不可逆，则存在置换矩阵p ，万= m p f f i m 一1 砺】使可 可逆，且这时由万为校验矩阵的码的自同构群与a u t ( c ) 同构 证明( 1 ) 的情况与文献 1 9 中定理4 的证明类似； ( 2 ) 通过置换矩阵p b 吏h 的列置换得到的码记为c 1 ， 从而c 与c l 等价，由引理知，a u t ( c ) 与a u t ( c 1 ) 同构 推论3 2 若日- 【ih 2 】，贝1 a e a u t ( c ) 尊龇日2 - h 4 。 若h - 【h 。i 】，则相应可由文献 1 9 中定理4 的方法， 即此时c 的生成矩阵是肘一 i - h i t 】，a e a u t ( c ) 一毗( _ 日。7 ) 。m 4 因此有时 用校验阵处理反而更方便 更为一般地，我们可以进一步地简化任意线性码的自同构群的计算 定理3 4 若线性码c 的生成矩阵mt 【膨。m ：l 。，将m 作初等变换与列的 交换得到m - 帆m l ，此时由m 生成的线性码记为c ，则c 与c 等价，且 v o e a u t ( c ) 一m 4 m ；膨也，此时a u t ( c7 ) s a u t ( c ) i e n 由引理3 4n 删n c n c 等价，则有a u t ( c ) a u t ( c ) ，再有推 论3 2 显然可得 由定理3 5 ，我们可以同构地给出任意线性码c 的自同构群，从而大大简化了 计算，下面给出算法说明： 算法对于l ，| 】线性码c ，其生成矩阵记为m = m ，m ：】，m ，为七阶可逆矩阵， 令e a g 0 ，0 ，o ) ，岛；( o o ，3 ，0 ) ，巳一( 0 ，o ，1 ) f 1 首先从i 1 个这样的b 中任意挑选t 个互不相同的出来( 记排列顺序) ，不妨记为 4 = ( 气，乞，气) ，一共有群种对群个这样的4 均作如下判断： 硕士学位论文 m a s t e r st h e s i s 2 ( 1 ) 将剩下的g 一七) 个弓作排列，一共有o 一七) ! 种记为4 一魄。，气。，气) ( 2 ) 此时作等式判断：如果满足：m 4 m ：- m 4 ，则这样的4 吖4 4 就满足要求， 然后对下一个这样的4 作同样的判断，直到所有的0 一| | ) ! 全部判断完毕 3 再重复以上的第l ，2 步，直到这样的群种全部判断完毕 4 所有满足这样条件的a 恰好组成了c 的自同构 1 9 硕士学位论文 m a s t e r st h e s i s 参考文献 1 ab e n - i s r e a l ，e g r e v i l l e ，g e n e r a l i z e di n v e r s e s ，t h e o r ya n d a p p l i c a t i o n s n e wy o r k ：j o l m w i l e y & s o n s 1 9 7 4 2 北京大学数学系几何与代数教研室代数小组，蔚穹治魏北京：高等教育出版 社，1 9 8 7 3 陈鲁生，沈世镒，翁厚蛋哲耋i 苏北京：高等教育出版社，2 0 0 2 e 4 3 樊恽，刘宏伟，群与组兮纺4 襄武汉：武汉大学出版社，2 0 0 2 5 樊恽，刘宏伟，线性等距码与极大投射码翅詹号匈职2 0 0 1 年6 月，第2 2 卷，第 6 期 6 m j e g o l y , b i n a r yc o d i n g , i e e et r a n s i n f o r m t h e o r y v 0 1 4 ，p p 2 3 2 8 1 9 5 4 7 m j e g o l y , n o t e so nd i g i t a lc o d i n g ，p r o c i e e e v 0 1 3 7 ，p p 6 5 7 ，1 9 4 9 8 r w h a m m i n 吕c o d i n g a n d i n f o r m a t i o nt h e o r yp r e n t i c e - h a l l 1 9 8 0 9 r w h a m m i n g ，e r r o rd e t e c t i n ga n d 锄rc o r r e c t i n gc o d e s ，& 盯s y s t t e c h j v o l 2 9 ，p p 1 4 7 1 6 0 ，1 9 5 0 【l o 华罗庚，万哲先，典垄留喾上海：上海科学技术出版社。1 9 6 3 1 1 gk a b a t i a n s k i i ，s m e e t s b ，j o h a n s s o n t ，o nt h ee a r d i n a l i t yo f s y s t em a t i c a u t h e n t i c a t i o nc o d e sv i ae r r o r - c o r r e c t i n gc o d e s j e e et r a n s 1 n f o r m t h e o r y , v 0 1 4 2 ( 2 ) ：5 6 6 5 7 8 ，1 9 9 6 1 2 陆正福，李亚东，王国栋，g f ( 2 “j 上线性码自同构群的进一步研究云雳力 学报( 自然科学皈) 2 0 0 1 ，2 3 0 6 、：4 0 1 4 0 4 1 3 f j ，m a c w i l l i a m s ，n j a s l o a n e ，t h et h e o r yo fe r r o r - c o r r e c t i n g c o d e s n e w y o r k ：o x f o r d ，1 9 7 7 1 4 mh p e a d