（应用数学专业论文）环f2uf2上的循环码.pdf

内容提要 在纠错码理论中，p o l y a d i c 码是一类重要的码。最初，域g f ( q ) 上p o l y a d i c 循环码首次是由b r u a l d i 和p l e s s ( 1 9 8 9 ) 作为d u a d i c 、t r i a d i c 循环码的推广而提出 的，并给出了g f ( q ) 上p o l y a d i c 码存在性的判定条件；最近，l i n g 和x i n g ( 2 0 0 4 ) 给出域g f ( q ) 上p o l y a d i c 阿贝尔码的定义、性质及其存在性的判定条件对于环 上p o l y a d i c 码至今未见讨论本文讨论环上p o l y a d i c 码 本文由以下四个部分组成：第一部分给出必要的定义和综述；第二部分给出 z p r 上p o l y a d i c 码的定义、性质及存在的条件；第三部分利用模2 的二次剩余和 兰次剩余，给出z 2 r 上d u a d i c ，t r i a d i c 码存在性的判定条件；第四部分利用模3 的 二次剩余和三次剩余，绘出z 3 - 上d u a d i c ，t r i a d i c 码存在性的判定条件 关键词：循环码，阿贝尔码，d u a d i c 码。t r i a d i c 码，p o l y a d i c 码 a b s t r a c t i nt h et h e o r yo fe r r o r - c o r r e c t i n gc o d e s p o l y a d i cc o d e s eo n ei m p o r t a n tc l a s s o fc o d e s f i r s t l y b r u a l d ia n dp l e s s ( 1 9 8 9 ) p r e s e n t e dt h ed e f i n i t i o no fp o l y a d i cc y c l i c c o d e so v e rf i e l dc f ( q ) ，w h i c hg e n e r a l i z e dt h ed u a d i ca n dt r i a d i cc y c l i cc o d e s ，a n d a l s op r e s e n t e dt h ee x i s t e n tc o n d i t i o n sf o rp o l y a d i cc y c l i cc o d e so v e rg f ( q ) r e c e n t l y , l i n ga n dx i n g ( 2 0 0 4 ) p r e s e n t e dt h ed e f i n i t i o no fp o l y a d i ca b e l i a nc o d e so v e rg f ( q ) ， a n dp r e s e n t e dp r o p e r t i e sa n de x i s t e n tc o n d i t i o n sf o rp o l y a d i ca b e l i a nc o d e so v e rf i e l d g f ( q ) n od i s c u s s i o nh a sb e e nm a d eo np o l y a d i cc o d e so v e rr i n g sy e t i nt h i st h e s i s w ec o n s i d e rp o l y a d i cc o d e so v e rr i n g s t h i st h e s i si sc o m p o s e do f4s e c t i o n s ：i ns e c t i o n1 ，w cp r e s e n ts o m en e e d e dd e f i n i - t i o n sa n dg i v eas u r v c yo fp o l y a d i cc o d e s ；i ns e c t i o n2 ，w ep r e s e n tt h ed e f i n i t i o n ，s o m e p r o p e r t i e sa n de x i s t e n tc o n d i t i o n sf o rp o l y a d i cc o d e so v c rt h er i n gz p r ；i ns e c t i o n3 ，w e p r e s e n tt h ee x i s t e n tc o n d i t i o n sf o rd u a d i cc o d e sa n dt r i a d i cc o d e so v e rt h er i n gz 2 rb y m e a n so fq u a d r a t i cr e s i d u e sa n dc u b i cr e s i d u e sm o d u l o2 ；i ns e c t i o n4 ，w ep r e s e n tt h e e x i s t e n tc o n d i t i o n sf o rd u a d i cc o d e sa n dt r i a d i cc o d e so v e rt h er i n gz 3 ru s i n gq u a d r a t i c r e s i d u e sa n dc u b i cr e s i d u e sr o o d u l o3 k e yw o r d s ：c y c l i cc o d e ，a b e l i a nc o d e ，d u a d i cc o d e ，t r i a d i cc o d e ，p o l y a d i cc o d e 引言 1 9 4 8 年香农( s h a n n o n ) 在他开创性的论文“am a t h e m i t i c a lt h e o r yo fc o m - m u n i t i o n ” 1 1 中首次阐明了有扰信道中实现可靠性通信的方利二，提出了著名的 有扰信道编码理论，奠定了纠错码的基石自此以后，汉明( h a m m i n g ) 、斯列宾 ( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代初根据香农的思想给出了一系列设计 好的码和有效的译码方法 g l e a s o n ( 1 9 6 4 ) 首先提出二次剩余码，它是一类重要的循环码( 具有较高的最 小距离、较好的编码译码算法) ，在实际当中有着广泛的应用最初的d u a d i c 循环 码是由l e o n 弘1 ( 1 9 8 4 ) 作为二元二次剩余玛的推广而提出的；此后经过s m i d 3 1 ( 1 9 8 7 ) 和r u s h a n a n 4 ( 1 9 9 1 ) 等人的工作把它推广到d u a d i c 阿贝尔码；l a n g e v i n 和s o l d l 5 1 ( 2 0 0 0 ) 首次提出环五上d u a d i c 阿9 1 尔码定义；随后l i n g 和s o l d l 6 】( 2 0 0 1 ) 给出了乃n 和 z 2 k ( k 为正整数) 上d u a d i c 码的定义另一方面的推广是，p l e s s 和r u s h a n a n ，】 ( 1 9 8 8 ) 给出了域g f ( q ) 上t r i a d i c 循环码的定义；b l u a l d i 和p l e s s f 8 j ( 1 9 s 9 ) 又进一 步把它推广到域g f ( q ) 上p o l y a d i c 循环码最近l i n g 和x i n g l 9 ( 2 0 0 4 ) 又给出了 域g f ( q ) 上p o l y a d i c 阿贝尔码的新的定义 对于这些码的存在性，w a r d 和朱烈1 1 0 1 ( 1 9 9 4 ) 共同解决了域上d u a d i c 码 存在性；并由张胜元【l l 】( 1 9 9 7 ) 用参数形式给出更具体的判定条件；p l c s s 和 k u s h a n a n 7 1 ( 1 9 8 8 ) 给出了域g f ( q ) 上t r i a d i c 循环码存在的判定条件； b r u a l d i 和p l e s s 8 1 ( 1 9 8 9 ) 给出了域g f ( q ) 上p o l y a d i c 循环码存在的判定条件l i n g 和 x i n g 9 1 ( 2 0 0 4 ) 给出了域g f ( q ) 上p o l y a d i c 阿贝尔码存在的判定条件 对于环上p o l y a d i c 码至今未见讨论本文讨论环乙r 上p o l y a d i c 码 本文由以下四个部分组成：第一部分给出必要的定义和综述；第二部分给出 乙，上p o l y a d i c 码的定义、性质及存在的条件；第三部分利用模2 的二次剩余和 三次剩余，给出忍，上d u a d i c ，t r i a d i c 码存在性的判定条件；第四部分利用模3 的 二次剩余和三次剩余，给出z 3 r 上d u a d i c ，t r i a d i c 码存在性的判定条件 1预备知识 本节主要给出与p o l y a d i c 码有关的一些基本概念，并讨论它们之间的关系 同时介绍p o l y a d i c 码已有的结果 设r 为环( 本文中的环均指有单位元的交换环) ， r “= ( ( z 1 ，z 2 ，一，z 。) f z i r ，i = 1 ，2 ，一，n ， 则舻构成r - 模 定义1 _ 1 【1 2 】模j p 的子模c 称为r 上n 长线性码，码c 中的元素c 称为 码字 定义1 2 码字c ；( c 1 ，c 2 ，c f l ) 的汉明重量定义为 w t ( c ) = l a l ls t sn ，q o ) c 的最小重量t o t ( c ) 定义为 w t ( c ) = m i n w t ( c ) fc ac o 最小重量与码的纠错和检错能力有关，即最小重量为d 的线性码可以纠正码 字中的t = 4 手】个或更少个码元错误，可以检查出码字中d 一1 个或更少个码元 的错误( 孚 表示不大于掣的最大整数) 定义1 3r “中两个元素c = ( c 1 ，c 2 ，c n ) 和d = ( 。1 7 ，c 2 ，) 的内积定 义为 n = _ c q t 墨l 码g 的对偶码g 1 定义如下t c 上= 茹r “i = o ，v c c ) 易见c 1 也是个线性码如果c c 1 ，称码c 是自正交的如果c = c 1 称码c 是自偶的 设r 是有单位元的交换环，g 是n 阶阿贝尔群，运算为加法 2 定义1 4 【1 3 】群环r 定义为 r 【g 1 = 芝二n ，y ，i 2 9 r ) f g 它的加法和乘法定义如下：对任意o ，b 兄【q n 。y 。+ b y 9 = ( + b g ) y 9 9 e 0目g g e g ( y 。) ( 6 h p ) = ( a ，h b h ) y 9 9 e g h e gg e gb e g 易见当r 是有单位元的交换环时。r 【g 】也是有单位元的交换环通常不加 区别都用1 表示r 和r 【q 的单位元 r o g l 中的理想称为r 上n 长的阿贝尔 码当g 是循环群时。阿贝尔码为循环码；若r = g f ( q ) ，r v l 是群代数。对于 c = g e gc g y g g f ( g ) 【g 】，如果e 9 6 gc 9 = 0 ，那么c 就称为偶性的( c v c n - l i k c ) ，否 则称为奇性的( o d d - l i k e ) 特别地，g f ( q ) 上的码口称为是偶性的，如果托c ， c 是偶性的；否则称c 是奇性的 设g ； g l , ，鲰) ，r 【g 】中的每一个理想可按如下的线性映射同构于r “ 中的一个子模： n 一1 c i p 一( c o , c 1 1 一，1 ) i = 0 通过上述关系可以把r 【g 】中的一个理想看成r ”上的子模( 线性码) 在下文中，冗是g f ( q ) 或磊( 五表示整数系z 模r 的剩余类环) 3 1 1 域上的p o y a d l c 码 为保证群代数g f ( q ) c 】是半单代数，总假设( q ，n ) = 1 设0 ec g f ( q ) g ， 如果e 2 = e ，e 称为幂等元当( q ，n ) = 1 时，g f ( q ) g i 中的任一理想c 均可由一 个幂等元e 生成，记为c = 令e 0 = i 1 。g y 9 ，称e 0 为平凡幂等元 以h u c ( g ) 记g 中所有的自同构组成的群若( q ，n ) = 1 ，映射地：g q x 作用在群g 上产生的轨道称为g 的g 一轨道对于任意pe a u t ( c ) 按如下的方 式，可以定义g f ( 口) f g 】的一个自同构弘： 定义1 5 【8 】设g = ( i = 1 ，2 ，m ) 是偶性码，其中e 。是g h q ) 【g 】上 的幂等元，如果它们满足以下三个条件： 1 ) 、。, f i ：t l q 一( m 1 ) i i i m = 1 e i = 1 一e o ； 2 ) 、e l e j ( i j ) 两两相等； 3 ) 、p ( e t ) = e i + l ( i = 1 ，2 ，m 1 ) ，且肛( e 。) = e l ，其中p a u t ( g ) 称o ，岛，g k 是偶性p o l y a d i c 码，口为p o l y a d i c 码的一个劈分( s p l i t t i n g ) 定义1 , 6 8 1 设g = ( 江l ，2 ，m ) 是奇性码，其中e 是g f ( q ) g i 上 的幂等元，如果它们满足以下三个条件： 1 ) 、i 巧竺1 = e 0 ； 2 ) 、e i + 勺一e l e j ( i j ) 两两相等； 3 ) 、肛( e ) = e t + 1 ( i = 1 ，2 ，一，m 一1 ) ，且p ( e m ) = e l ，其中“h u t ( g ) 称g l ，国，c 。是奇性p o l y a d i c 码，“为p o l y a d i c 码的一个劈分 由上面的定义直接可知p o l y a d i c 码是偶性( 奇性) 的当且仅当它的幂等生成 元是偶性( 奇性) 的 说明1 , l 1 ) 、文【3 ，4 】中的偶性d u a d i c 码即为m = 2 且e l e 2 = 0 时的偶性p o l y a d i c 码，对应的奇性p o l y a d i c 码为文i 3 ，4 】中的奇性d u a d i c 码如果c l ： ， 岛= 是偶性的d u a d i c 码，则 ， 是奇性的d u a d i c 码； 反之亦然 2 ) 、当m = 3 且g 为循环群时，p o l y a d i c 码即为文【7 l 中的t r i a d i c 码 4 g yo 。 | l 口 yd 。 3 ) 、如果m 3 且g 为循环群时，如上的定义的p o l y a d i c 码与文中的 p o l y a d i c 码相同如果g 为一般的阿贝尔群时，p o | y a d i c 码的定义被l i n g 和x i n g 在文m 中作了推广该定义在下文给出( 参见定义1 1 1 ) 在给出新的p o l y a d i c 码定义之前，首先引入几个基本概念和结论 引理1 1 1 【l4 】( 有限阿贝尔群的基本定理) n 阶阿贝尔群g 可分解成一些 阶等于素数方幂的诸循环群的直积，且这样的分解方法是唯一的 以下内容引自文叭设g 为n 阶阿贝尔群，运算为加法，指数为设m 是p 模的阶并记为m = o r d n ( p ) 记f = g f ( q ) ，k 为f 的包含所有i v 次单位 根的扩域记为中的次本原单位根由引理1 1 1 知，g 可以设为 g = 磊l 磊2x - t 磊 其中他( 1 i t ) 为等于或大干2 的整数且g 中的每个元素g 可写成9 = 0 l ，啦，乳) ，g l z k ( i = 1 ，t ) 定义1 7 剐给定h = ( h i ，h 2 ，h t ) g ，对任意g = ( g l ，9 2 ，9 ) g ，g 到 k 的特征标定义为x h ( g ) = f 2 ：= 删“t ( n “” 定义1 8 给定c = 。e g c g y 9 f g 】，它的离散f o u r i e r 变换定义为e = k a 5 u y “，其中h = 口a x h ( 9 ) 定义1 9 9 1 对g 自任意子集x ，定义： i x = c f 【q = o ，地x ) 易知h 是f g 】的理想 若把加群g 按分量乘积之和定义乘法。g 可看成一个交换环用r g 表示 这个环兄苦表示兄g 中所有可逆元构成的群对任意s ，设s 。为作用在g 上的映射 z s z 该映射可以自然导出f g 】上的一个映射s + 定义1 1 01 9 】满足以下条件酊( ，硒，x l ，置。一1 ) 称为g 的一个m 一劈 分： ( 1 ) x 裔，x 1 ，、一l 为g 的一些q 一轨道的并； ( 2 ) x o o ，x 1 ，x i 为g 的一个划分，即g = x o o u x o t 3 x 1 u u 并m 一1 且x 。，x o ，x l ，x ，。1 两两不变； ( 3 ) 存在8 使得s 。( x 裔) = k 。，且& ( 托) = x t + l ( 0 i m 一1 ) 下标按 模m 运算 5 易见o 墨。，记戤= o ，x 。表示x 在群g 中的补集 以下给出当g 为n 阶阿贝尔群时，域上p o l y a d i c 码的另一种定义 定义1 1 11 9 1 对0 茎ism 一1 ，以下四类码均称为p o l y a d i c 码： ( 1 ) a = i ( x - u x , ) c i ( 2 ) g = i x - u x ti ( 3 ) _ d = i x 。u x 。i ( 4 ) b t = 丑x 。u x ) e 有时也把上述p o l y a d i e 码称为m - a d i c 码 当g 是循环群时，以上定义的p o l y a d i c 码为文 8 1 中的p o l y a d i c 码i 当m = 2 时，以上定义的码为文 2 5 1 中的劈分群码( s p l i tg r o u pc o d e s ) 下面给出已知的关于域上p o l y a d i e 码的存在性结论 ( 1 ) 1 9 8 4 年l e o n 【2 】等人给出了f = g f ( 2 ) ，g 为阶循环群，m = 2 时的存 在性结论， 定理1 1 2 设n = p ：1 疗蜱r 为n 的标准分解，其中p i 为奇素数( i = 1 ，2 ，r ) 则g f ( 2 ) 上存在n 长d u a d i c 码当且仅当p l = ：t ：l ( m o d8 ) 0 = 1 ，2 ，r ) ( 2 ) 1 9 8 4 年s t a i d 3 1 给出了f ；g f ( 口) ，g 为l 阶循环群，m = 2 时的存在性 结论t 定理1 1 3 设n = p ：1 p 字p d r 为n 的标准分解，其中0 ，q ) = i ( i = 1 ，2 ，r ) 则g f ( q ) 上存在n 长d u a d i c 码当且仅当q 是模a 的二次剩余( i = 1 ，2 ，r ) ( 3 ) 1 9 8 8 年p l e s s 7 1 等人给出了f = c f ( q ) ，g 是p 阶循环群，m = 3 时的存 在性结论； 定理1 1 4 设( p ，q ) = 1 ，g f ( q ) 上素数p 长t r i a d i c 码存在当且仅当q 是模p 的三次剩余，当且仅当p = z 2 + 2 7 y 2 , z ，ye z ( 4 ) 1 9 8 9 年b r u a l d i 8 等人给出了f = g f ( q ) ，g 是p 阶循环群，一般的m 时 的存在性结论： 定理1 1 5 如果m i p 1 ，且口是模p 的m ；1 5 , 1 余，则g f ( q ) 上素数p 长 p o l y a d i c 码存在 ( 5 ) 1 9 8 9 年w a r d 1 0 等人引入p 一齐性的概念，给出了f = g f ( g ) ，g 是n 阶 阿贝尔群，m = 2 时的存在性结论： 定理1 1 6g f ( q ) 上存在n 长的d u a d i c 码当且仅当对每个整除n 的素因子 p ，g 是p 一齐性的 ( 6 ) 2 0 0 4 年l i n g 9 等人引入可行的( f e a s i b l e ) 和非退化的概念( 参见本文中 2 2 ) ，给出了f = c f ( q ) ，g 是阿贝尔群，一般的m 时的存在性结论； 定理1 1 7 设g = 丌名l 戗，其中g i = 乙c 。0 = 1 ，2 ，) ，肌为素数，e t 0 则c f ( q ) 上存在非退化的p o l y a d i c 码当且仅当存在某个i 使得0 “ 乜 p i 一1 且( f i ，轨) 是可行的( f e a s i b l e ) 以上对于域上已有p o l y a d i c 码的定义、性质以及它们存在性的判定做了简略 综述而对于环上p o l y a d i c 码的相关研究还很有限，目前只有2 0 0 0 年l a n g e v i n 和s o l d 5 1 研究了环z 4 上的d u a d i c 码，以及随后l i n g 和s o l d 等人对环邑k 和 毋+ u f 2 上的d u a d i c 码的研究【6 ，1 6 】而以上文献中对于环上的d u a d i c 码的存在 性问题，还没有展开充分的探讨 本文给出环磊r 上p o l y a d i c 码的定义，并研究它的性质以及存在性问题 7 2磊，上p o l y a d i c 码的性质及其存在性 本节给出了磊r 上p o l y a d i c 码的定义及性质。以及非退化p o l y a d i c 码存在的 充分必要条件 2 1乙，上p o l y a d i c 码的定义及性质 首先引入一些相关定义 定义2 1 【1 5 】设p 为素数，r 为正整数。g a l o i s 环是商环磊r i x 其中z p r 旧是知上的多项式环，垂( 。) 是耷嘲上次数为d 的首1 基本不可约多 项式 z n r 上的d 次g a l o i s 扩张是唯一的通常把这个g a l o i s 环记为g r ( v ，d ) 设g 为n 阶阿贝尔群，运算为加法，n ) = 1 设g 的指数为，肼是p 模 v 的阶并记为m = o r d ( 9 ) 则g r 抄，m ) 是包含次单位根最小的g a l o i s 环 记f 为g r ，m ) 中的一个次单位根仍设g = 互。磊。，瓦。 定义2 2 剐给定h ；( h i ，h 2 ，h t ) g ，对任意9 = ( 9 1 9 2 ，y t ) g ，g 到 g r ( p r ，m ) 的特征标定义为肌( 9 ) = f 2 ：= 1 9 i “( n ，n ” 定义2 3 5 1 给定c = 。g y g 磊r 【g 】，它的离散f o u r i e r 变换定义为e = e e g c h y “，其中“= 口g 勺舰( 9 ) 沿用前面的记号；用r g 表示由g 按分量乘积之和定义乘法后得到的交换 环，兄各表示船中所有可逆元构成的群对任意se ，设s 。为作用在g 上 的映射： z s z 该映射可以自然导出昂r 【g 】上的一个映射矿：c = 。g y g ， ，( c ) = e g e g 勺y ”它对应酌离散f o u r i e r 变换为矿( c ) = g c s h y “由于 ( p ，n ) = 1 p 8 自，把p 。在g 上的作用得到的轨道称为p 一轨道有时也把s 在 g 上的作用称为s 作用在g 上 对于g 的任意子集x ，令b = c z p r f g 岛= o ，妇e x ) 引理2 1 1 如是知【g j 的一个理想 证明设c = g e g c g y 9 , d = g e g 南y 9 i x ，则妇x ，岛= 0 ，五= 0 加法封闭：记o = c + d = 。g o 口y 9 ，则= 勺+ 如v 。x ，乱= 如+ a ；= 0 ， 即c + d h 乘法吸收，v c = 口e g 勺p i x ，d = e 9 g 如 耷【g 】 则c a = ( 9 l e ge g l p l ) ( 9 l e g d 口a y a 2 ) = e ，g ( 口l g 勺i d y 咄) y ， 8 从而；五= f a g ( g 。e gc 9 。o ，) ( ，) 另一方面，岛= 9 e gc g x z ( 9 ) ，五= g e g 南地( g ) ，则 屯玉= ( c a x 。( 9 ) ) ( 南x 。( 9 ) ) = ( 勺，d 9 2 ) x z ( 9 l + 9 2 ) g e g9 e g 口1 e g9 2 e g = ，g ( g l e g 勺- d f 吲) x 。( ，) = 砒， 而v 。x ，屯= o ，从而a 。= 屯五= 0 故h 是磊r 【q 的一个理想证毕 作为一个理想，h 也是磊r 上的一个线性码 定义2 4 称满足以下条件的( x 。，粕，x l ，x 。一1 ) 是群g 的一个m 一劈 分： ( 1 ) x 。，x o ，x 1 ，葺。一1 为g 的一些p 一轨道的并； ( 2 ) x ，x o ，x l ，x m 一1 为g 的一个划分，即g = x u 硒u x l u u x m 一1 且如，j ，0 ，x 1 ，j ，m 一1 两两不交； ( 3 ) 存在8 r 使得s 。( j ) = x 。o ，且& ( 甄) = x i + 1 ( o i m 1 ) 下标按 模m 运算 有时为了强调上述定义中的群作用也把8 。称为g 的一个m 一劈分 定义2 5 设群g 的一个m 一劈分为( 托。，x 1 ，五。一1 ) 对于0 兰is m 一1 ，以下四类码均称为z 0 【g 】中p o l y a d i c 码t ( 1 ) q = u 噩) c ； ( 2 ) a = i x - u 咒； ( 3 ) d 。= i x 。u x ，； ( 4 ) d t = x 。u 墨1 c 上述的p o l y a d i c 码也称为m a d i c 码 由定义2 5 可知，磊r 上n 长m a d i c 码的存在性问题就是n 阶阿贝尔群g 中的m 一劈分的存在性问题 设g 的所有p 一轨道为o o ，0 1 ，- 一0 由【5 】知，磊r g 1 同构于环磊r g r ( 矿，d 1 ) x xg r ( p 7 ，如) ，其中d i = l n l ( i = 1 ，”) 进一步地，若x g 是 一些p 一轨道的并，记x = l h e z ( x ) o i ，则i x = 兀诞 o ，l m 。) v ( x ) g r ( p ld d 定理2 1 2 设x 1 ，恐是g 的某些p 一轨道的并，则h l + = i x l n x 。， 如ln i x 2 = i x l u 尥= i x l 如2 9 证明 设x 1 = u t 引x t ) o i ，x a = u i z ( x 2 ) o i ，则x ln 地= u i e z ( x l n x 2 ) o i 又 o ，1 ，2 ，u ) z ( x l n x 2 ) = o ，1 ，2 ，”) z ( x 1 ) u o ，1 ，2 ， z ( x 2 ) ， 贝0 i x l 二n 姬( o 1 ，2 。i ( x i ) g r ( ，d i ) ，如2 = 兀。 o 1 2r ，u ) t ( x 2 ) g r ( p ”，d ) ， i x l n x ：= 兀哐，2 小z ( x l n 恐) g r ( p ，也) ，则h 1 + 取2 = h l t a x 2 同理可证，取。n 忱= i x l u x 2 = h 。证毕 以下几个定理，阐述p o l y a d i c 码的性质 定理2 1 3 ( 1 ) q n q = 乜c 0 j ) ，c o + o + + c k 一1 = n f a + g j = x - ( i j ) ，c o n c ln - n 一1 = i 0 1 c d 。+ d s = i x ( i j ) ，d o n d l n n d r n 一1 = i a = 0 1 ， 西，n 岛= x 。c “j ) ，d o + 西1 + + 氏一1 = 如= 昂r g 1 ( 2 ) 对于任意的0s i m 一1 ，c i + q = 乙r 【g 1 = d 。+ d ； ( 3 ) 对于任意的0s i m 一1 ，d i = i ( 0 1 gc g = d i + i ( 0 1 c 且c i = i ( 0 1 d ic d i = c i + i ( 0 1 c ( 4 ) 每个类中的m 个码等价 证明( 1 ) ，( 2 ) ，( 3 ) 可以直接由定义和定理2 1 2 得到 ( 4 ) 对于g ，存在s r 各中，使得目( x i ) = s x i = 五+ 1 ( i = 0 ，i ，m 1 ) ，下标 按模m 运算则矿( c d = c i l “= 0 ，1 ，m 一1 ) 从而c 。中的m 个码是等价的 同理其余各类码也是等价的证毕 定义2 6 设c 是磊r 【g 】中的理想，c 的维数d i m ( c ) 定义为l o g v r i c l 定理2 1 4 ( 1 ) 设i x 毛i = f ，且l x o i = l x l i = i x 。一t i 一一c 则对 任意0 i m 一1 ，有d i m ( c i ) 一k ，d i m ( a ) = n k ，d i m ( d 。) = n k 一1 ，且 d i m ( ： ；) = + 1 ( 2 ) 对任一个m a d i c 码c ，令0 = 饥c ，则反= 西。，b = 反= 一 ：= 一 d i ，d i m ( g ) = d i m ( d i ) = k z ，d i m g - - d i m d ，：= d i m d = n k 一1 证明( 1 ) a = 心u 置) c ；n ，z ( x k u 置) g r ( p r , 而) ，盼f = 0 ) ，e 2 f 。k “施j 畔= ( p 7 ) i x k u 墨l ，贝0d i m ( c i ) = i x - u 嚣i = ( 七一f ) + f = 南 同理可证，d i m ( 反) = l ( 戤u x d 。i = n k ，d i m ( d i ) = l ( 墨。u 五) c l = n k 一1 ， 且d i m ( d i ) = i x o 。u x i l = 女+ 1 ( 2 ) 由g 的定义及定理2 1 2 得，岛= i x 。i ( x - u x 。) c = i x 。c ，西f = i x 。- i ( x 。u x d c = x c ，则& = d i ，d i m ( c i ) = d i m ( 鱼) = i x d 一一f 同理可证，a = 反= d l ，a i m o = d i m 反= d i m d i _ ”一一1 证毕 对于磊r 上的任意一个线性码g ，按通常的内积的定义可以定义它的对偶 码g 1 下面考虑p o l y a d i c 码的对偶码 记p 一1 ：z 一一z ，z g 一1 作用在g 上是g 的自同构p l 导 出p 一轨道o o ，o l ，o 。上的一个置换d r ，但是p l 未必导出g 的m 一劈分 ( x 。，j ，0 ，x 1 ，蜀。一i ) 上的一个置换 定理2 , 1 5 【5 j ( 1 ) 互p r 【g 】中的每个理想，可以表示为矗i lz l ，其中 弓是g r ( v ，由) 中所有理想( 1 ) ，妇) ，( p 2 ) ，铲_ 1 ) ，( 0 ) 中的某一个 ( 2 ) 理想j = i o x xl 的对偶p = 露( 0 ) 露( 1 ) e ，其中 ( o ) 。= ( 1 ) ，( 1 ) 。= ( 0 ) ，( ) 。= ( p m 一) ( i i m 一1 ) 定理2 1 6 如果弘一1 作用在g 上导出m 一劈分( 扎。，x l i ，五。一1 ) 上的 一个置换口。，且口( j ) = x 啬，记以( 五) = 玛( 1 ) 则a 1 = 岛( ，) ，皿1 = d a 证明i x = n 讵m 孙“) 怛( x ) g r 铲，血) ，由定理2 1 5 ( 2 ) 及h 的定义得， 醛= 兀i e m 孙一) 忸x ) ( g r ，d 。( i ) ) ) 。= n z ( x ) g r ，如( t ) ) = 兀锄( i ( x ) ) g r 铲，d i ) 而g = x 矗嘣) c ，g 上= k ( x 毛u x ) = 魄。u x 眯) = 岛( 1 ) 同理，d 1 = d 孙、证毕 1 1 2 2 磊，i - p o l y a d i c 码的存在性 为了讨论z 口r 上p o l y a d i c 码的存在性，引入文【9 】中的一个概念 定义2 7 旧设m 2 ，p 是素数，不整除p ，且，j 满足0 兰l 1 ，( n n ) = 1 ，若2 三n ( m o dp ) 有解，则n 叫做模p 的 二次剩余；否则n 叫做模p 的非二次剩余 定义3 2 【1 7 】设p 为奇素数，( p ，n ) = 1 ，令 ，n 、f 1 若n 是模数p 的二次剩余 、p 【一i 若n 是模数p 的非二次剩余 函数( ；) 叫做勒让德符号 定理3 1 11 1 7 对于每一个素数，有 c ；) = ( 叫钒 一1 。喜：三嚣品 由上面的定理可得， 定理3 1 2 1 7 】设p 是奇素数，则2 是摸p 的二次剩余当且仅当p i 士l ( m o d8 ) 当且仅当2 孚三l ( m o d p ) 引理3 1 3 1 8 】设p ii l ( m 。d8 ) ，则s = 击南为偶数 定理3 1 4 设g = z p ，其中p 是奇素数则存在g 的一个非平凡2 一劈分 ( x 。o ，x b ，x i ) 当且仅当pi 土l ( m o d8 ) 证明记 = o r 站( 2 ) g = 磊构成p 元域记为且r = 名构成p 一1 阶 乘法群( 循环群) 令m 是r ；中的二次剩余组成的群，则m 为的2 手阶 循环子群令o = 1 ，2 ，2 2 ，2 u - 1 ) ，o 为磁的u 阶循环子群，商群o 为 s = 等阶循环群则存在z 兄占，使得o = z 0 0 = 0 ，1 ，s 1 ) 为r ；的一个 陪集分解，丽且f o ) ，o o = 0 ，0 l ，0 8 一l 为加群g = 磊的所有2 一轨道 充分性：当p ；：l l ( m o d8 ) 时，由引理3 1 3 知，g 的非零轨道个数s 为偶 数令 x o = o o u 0 2u u o 。一2 ， 1 3 x i = 0 1 u o au - - 一u o 1 x o o = 0 则。( x o ) = x 1 ，z 。( x 1 ) = x o ( x 。，x o ，x 1 ) 是g 的一个非平凡的劈分 必要性t 假设( x 。，x o ，x 1 ) 是g 的在群作用。下的一个非平凡的劈分， z 兄玉且，x l 都是某些非零2 一轨道的并，且有z + ( x o ) = x l ，z 。( x 1 ) = x o 如果非零轨道个数s 为奇数则存在非负整数t ，使得8 = 2 t + 1 一方面， 由于商群d 为s = 辱阶循环群，可得x ：( o i ) = o d i =