（应用数学专业论文）环z4上duadic码的存在性.pdf

内容提要 y7 6 9 0 5 0 在纠错码理论中，d u a d i c 码是一类重要的线性码它是由l c o n 等人( 1 9 8 4 ) 作为二元域上二次剩余码的推广而提出的；r u s h a n a n ( 1 9 9 1 ) 把它推广到d u a d i c 阿 贝尔码；朱烈( 1 9 9 6 ) 进一步推广到d u a d i c 群代数码这些推广均保持了二次剩余 码的一些特性，如最小重量的平方根界以及它与射影平面的关系张胜元( 1 9 9 7 ) 又进一步推广到中一l - d u a d i c 群代数码对d u a d i c 群代数码的存在性问题，w a r d 和朱烈( 1 9 9 4 ) 解决了域上d u a d i c 阿贝尔码存在性；张胜元( 1 9 9 7 ) 年用参数形式 给出更具体的判定条件和中心d u a d i c 群代数码存在的充分必要条件l a n g e v i n 和s o l d ( 2 0 0 0 ) 首次提出环上d u a d i c 阿贝尔码的定义，对于环上d u a d i c 阿贝尔码 存在性问题仍未被解决 、 本文解决了尻上d u a d i c 阿贝尔码存栏 生问题文中首先综述d u a d i c 码；其 次给出了五上存在非平凡d u a d i c 阿贝尔码的充分必要条件；最后给出了五上 劈分为p 一1 的非平凡d u a d i c 阿贝尔码存在的充分必要条件，这些条件也是存在 函上非平凡自偶阿贝尔码的充分必要条件 关键词阿贝尔码， 自偶码，d u a d i c 码，轨道 a b s t r a c t d u a d i cc o d e sf o r ma ni m p o r t a n tc l a s so fl i n e a rc o d e sf o rb o t ht h e o r e t i c a la n dp r a c - t i c a le e a s o n si ne r r o r - c o r r e c t i n gc o d e s t h e yw e r ef i r s ti n t r o d u c e db yl e o ne t “( 1 9 “) a sg e n e r a l i z e dq u a d r a t i cr e s i d u ec y c l i cc o d e so v e rf i e l d s b u s h a n a n ( 1 9 9 1 ) g e n e r a l i z e d t h e mt od u a d i ca b e l i a nc o d e sa n dz h u ( 1 9 9 6 ) f u r t h e rg e n e r a l i z e dt h e mt od u a d i cg r o u p a i g c b r ac o d e s m a n yp r o p e r t i e so fq u a d r a t i cr e s i d u ec o d e sc a nb ep e r s e r v e db yt h e s e g e n e r a l i z a t i o n s ，f o re x a m p l e ，t h es q u a r er o o tb o u n da n dc o n n e c t i o nw i t hp r o j e c t i v e p l a n e s z h a n g ( 1 9 9 7 ) f u r t h e rg e n e r a l i z e dt h e mt oc e n t r a ld u a d i cg r o u pa i g e b r ac o d e s a b o u tt h ee x i s t e n c eo fd u a d i cc o d e s ，w a r da n dz h u ( 1 9 9 4 ) o b t a i n e dn e c e s s a r ya n ds u f - f i c i e n tc o n d i t i o n sf o re x i s t e n c eo fd u a d i ca b e l i a nc o d e s ，z h a n g ( 1 9 9 7 ) g a v et h ee x i s t e n t c o n d i t i o n sf o rs u c hc o d e sb ys o m ep a r a m e t e r sa n do b t a i n e dn e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sf o re x i s t e n c eo fc e n t r a ld u a d i cg r o u pa l g e b r ac o d e s r e c e n t l y , d u a d i cc o d e s o v e r 蜀a r ep r e s e n t e db yl a n g c v i na n ds o l d ( 2 0 0 0 ) ，b u tt h ee x i s t e n tp r o b l c mo fd u a d i c a b e l i a nc o d e so v e r 五h a s h tb e e ns o l v e dy e t t h i st h e s i ss o l v e st h ee x i s t e n tp r o b l e mo fd u a d i ca b e l i a nc o d e so v e rz 4 as u r v e y o fd u a d i cc o d e si sp r e s e n t e df i r s t l y 】n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c e o fn o n t r i v i a ld u a d i ca b e l i a nc o d e so v a rz 4a r ep r e s e n t e ds e c o n d l y f i n a l l y , n e c e s s a r y a n ds u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c eo fn o n t r i v i a id u a d i ea b e l i a nc o d e so v e rz 4 w i t hs p l i t t i n gp 一1a r ep r e s e n t e d ，t h e s ec o n d i t i o n sa r ea l s on e c e s s a r ya n ds u f f i c i e n tf o r t h ee x i s t e n c eo fn o n t r i v i a ls e l f - d u a la b e l i a nc o d e so v e rz 4 k e yw o r d s ：a b e l i a nc o d e ，s e l f - d u a lc o d e ，d u a d i cc o d e ，o r b i t 引言 1 9 4 8 年仙农( s h a n n o n ) 在他开刨性的论文“am a t h e m a t i c a lt h e o r yo fc o i n - m u n i t i o n ”【1 】中首次阐明了有扰信道中实现可靠性通信的方法，提出了著名的 有扰信道编码理论。奠定了纠错码的基石由于编码理论在计算机科学和现代数 字通讯技术中的广泛应用，它一直是一个十分迷人的数学研究领域它的魅力还 在于人们发现可以用许多数学工具来解决码论中的实际问题特别是线性码，由 于它所具有的代数结构而使快速简便的编码译码得以实现。以及它与组合数学的 密切关系，已经引起了许多代数和组合数学工作者的关注 纠错码理论中有两个基本问题t1 、构作性能良好的纠错码，即希望有高的 传输效率和强纠错能力的纠错码；2 、研制工程上实用的译码算法，自1 9 4 8 年以 后，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 2 】首先提出二次剩余码，它是一类重 要的循环码( 具有较高的最小距离，较好的编码译码算法) ，实际中有着广泛的应 用l e o n 3 】给出了d u a d i c 码的定义，它是二次剩余码的推广此后，r u s h a n a n 4 1 把它推广到d u a d i c 阿贝尔码。p l e s s 5 1 的综述文章中总结了有关进展；朱烈【6 】 进一步推广到d u a d i c 群代数码这些推广均保持t - - 次剩余码的一些特性，如 最小重量的平方根界以及它与射影平面的关系张胜元 9 】又进一步推广到中心 d u a d i c 群代数码 对域上d u a d i c 码的存在性问题，s t a i d 7 1 解决了d u a d i e 循环码的存在性； w a r d 和朱烈f 8 】解决了d u a d i c 阿贝尔码的存在性；张胜元【9 】给出了中心d u a d i c 群代数码存在的充分必要条件 2 0 0 0 年，l a n g e v i n 和s o l d 1 0 1 首次提出环z 4 上d u a d i c 阿贝尔码的定义。随 后l i n g 和s o l d 1 1 】给出了环z 扣为素数，m 为正整数) 和z 2 ( k 为正整数) 上 d u a d i c 码的定义而环z 4 或如上d u a d i e 码存在性问题尚未解决 本文研究环盈上d u a d i c 码存在性问题，给出了其存在的充分必要条件由 于盈上自偶阿贝尔码和劈分为# - 1 的d u a d i e 码有着密切的关系，故文中也给出 了存在劈分为卢一1 的d u a d i c 码和存在非平凡的自偶阿贝尔码的充分必要条件 1预备知识 本节给出了一些基本概念及结论 1 1 域上编码理论的基本概念 设f 是个q 元域，其特征为p 设y 是f 上n 维向量空间y 中的k 维 子空间就是个线性码，记为c 称n 为码的字长，为其维数 ( n ，) 一码c 中的个向量叫做c 的码字向量中的分量称为码元码字c = ( c 1 c 2 ，) 的 汉明重量定义为 w t ( c ) = i i 1si5 n ，c t o ) i 码c 的最小重量”t ( c ) 定义为 埘( g ) = m i n w t ( c ) ic g c o ) 最小重量与码的纠错和检错能力有关，即最小重量为d 的线性码可以纠正码字中 的t = f 等 个或更少个码元错误，可以检查出码字中d 一1 个或更少个码元的错 误 y 中两个向量u = ( “l ，“2 ，) 和“= ( “1 ，“2 ，u 。) 的内积定义为 n = e u i u l 7 码g 的对偶码g 1 定义如下 c 上= v i = 0 ，v c c 易见码c 1 也是线性码如果c c 1 ，称码c 是自正交的如果c = 伊，称码 c 是自偶的对一个自偶码，k = n 2 ，故n 必为偶数 1 2 环上编码理论的基本概念 设4 为整数系z 模r 的剩余类环，4 上n 长的线性码c 是刃的子模 类似于域上的线性码，可以定义耳上线性码c 的汉明重量，最小重量，内积 对偶码，自偶码等概念 磊上的阿贝尔码定义如下： 设g 为n 阶阿贝尔群，运算为加法，且n 与r 互素群环z r g 定义为 4 g = a # y 9 ia g 磊) 9 e g 2 它的加法和乘法运算为通常的加法和多项式卷积乘法磊g 中的理想称为4 上 n 长阿贝尔码当g 为循环群时，阿贝尔码即为循环码记g = 9 l ，9 2 ，鲰 ， 对于口= 冬1 a i y g i z ，g ，每个n 对应于一个码字( 叫，a 2 ，n 。) 邵反之亦 然通过该对应法则可以把历g 中的一个理想( 阿贝尔码) 看成刁的一个子模 ( 线性码) ，从而可以定义自偶阿贝尔码本文主要研究环磊m 上的阿贝尔码( 其中 p 为素数，m 为正整数) 关于以上两部分更详细的内容可参见文献 2 ，1 2 1 1 3 几个代数结论 定理1 3 1 【m 】( 有限阿贝尔群的基本定理) n 阶阿贝尔群g 可分解为一些 阶为素数幂的诸循环群的直积，且这样的分解方法是唯一的 具体地，设n = p ：t p i 2 p ；为n 的素因子分解，其中a 0 ；1 ，2 ，s ) 为两 两不同的素数，九0 = 1 ，2 ，8 ) 为正整数，则g = 品，岛：5 k ，其中 是g 的唯一个p t s y l o w 子群，且每个& 可以进一步分解为阶为p 的方幂的 循环群的直积 g a l o i s 环在讨论群环的结构中起到重要的作用这里仅给出其定义及2 个基 本性质，有关g a l o i s 环的详细内容参见【1 4 】 定义1 , 3 1 设p 为素数，m 为正整数，g a l o i s 环是商环磊m 吲( ( z ) ) 其中 磊m 是磊m 上的多项式环，曲( 。) 耳m m 是次数为d 的首1 基本不可约多项 式把这个g a l o i s 环记为g r ( 矿，d ) 通常也称g r ( p “，回为环磊m 的d 次g a l o i s 扩张 g r 0 m ，d ) 的基本性质； ( 1 ) g r ( p ，d ) 同构于域g f ( p 4 ) ；g r ( p m ，1 ) 同构于环z 矿； ( 2 ) g r o p ，d ) 中的每个理想都是由p t ( o 墨i 曼m ) 生成，即g r ( 矿，d ) 是主理 想环更一般地，它只有一个极大理想0 ) ，且有如下链关系： ( o c m - 1 ) c ( p ”一2 ) c c ( p 2 ) c ) c ( 1 ) = g r ( p ”，d ) 也就是说，g r o ，m ，d ) 是局部环 3 2d u a d i c 码综述 本节综述d u a d i c 码的定义和其存在性的有关内容 2 1 域上的d u a d i c 码 2 1 1 域上阿贝尔码 设f = g f ( q ) 是一个q 元域，g 为n 阶阿贝尔群，运算为加法，且( 啊q ) 。1 f g 是f 上g 的群代数，f g 中的元素c 可写成：c = 。gc g y g ，q f ，其加 法和乘法运算与通常的多项式环的相同易知f g 也是有单位元的交换环，仍用 1 表示f g 中单位元如果。gc g ；0 ，那么c 就称是偶性的( e v e n l i k e ) ；否则称 是奇性的( o l d u k c ) 设g = g o = 0 ，g l ，g n 一1 ) ，f g 中的每一个理想按如下线性映射同构于p 中的一个子空间 n 一1 c i y 9 h 湎，c 1 ，c n 一1 ) ( 1 ) i = 0 则群代数f g 是以g o ，g l - ，蜘一l 为一组基的f 上的n 维向量空间f g 中的一 个理想c 就是f g 中的一个阿贝尔码如果一个阿贝尔码c 作为向量空间f g 的线性子空间的维数为k ，则c 是一个线性( n ，k ) 码当g 为循环群时，f g 中的阿贝尔码即为熟知的f 上的循环码由同构关系( 1 ) 就可以给出f g 中阿贝 尔码的维数、c 汉明) 重量、对偶码以及自偶码等的定义上述详细内容可参见 1 1 5 ，1 6 ，1 7 】 当g 为一般群( 可以非交换) 时，相应的可以定义群代数码，它是阿贝尔码 的进一步推广本文只涉及阿贝尔码。关于群代数码的内容可参见m 2 1 2d u a d i e 码的第一定义 由于( q ，n ) = 1 ，所以f g 是半单的故f g 中的理想均由幂等元( 0 ee f g ， e 2 = e ) 生成设c 为f g 中的个阿贝尔码，则c = ，其中e 为幂等元令 1 e o = 土y g( 2 ) n 口o 称e o 为平凡本原幂等元如果c 中所有向量均是偶性的，则称码c 是偶性的 否则称码c 是奇性的 4 群g 中的所有自同构组成一个群，记为a u t ( g ) 对整数a ，记p “g 一“g ， 砌g 易知，芦一l h u t ( g ) 对任意p a u t ( g ) ，可以自然地定义f g 中的自同 构 p ( c g y 9 ) = 勺y ” ( 3 ) g e g g e g 以下用f g 中幂等元的形式给出域上d u a d i c 码的第一定义 定义2 1 11 4 】设置和岛是群代数月口中的两个幂等元，如果它们满足以 下两个条件 1 ) 、e 1 + 马= l + 8 0 ； 2 ) ，马= p ( e 1 ) ，且e 1 = 肛( 岛) ，其中p a u t ( g ) 那么称a = ，伤= ，岛= 和c 4 = 是由幂 等元e 1 和易决定的d u a d i c 阿贝尔码简称为d u a d i c 码称p 为d u a d i c 码的 个劈分( s p l i t t i n g ) 易知d u a d i c 码是偶性的( 或奇性的) 当且仅当其幂等生成元是 偶性的( 或奇性的) 以下对上述定义做几点说明： 说明2 11 ) 、当口= 2 ，即f 为二元域，g 为循环群时，定义2 1 1 中的 d u a d i c 码即为文【3 1 中最早所定义的d u a d i c 码； 2 ) 、当q = 4 ，即f 为四元域，g 为循环群时，定义2 1 1 中的d u a d i c 码即 为文【1 8 】中所定义的q 码； 3 ) 、当f = g f ( q ) ，g 为循环群时，定义2 1 1 中的d u a d i c 码即为文f 7 】中所 定义的d u a d i c 码； 4 ) 、当f = v f ( q ) ，g 为一般的群时，文【6 】中类似于定义2 1 1 定义了d u a d i c 群代数码； 5 ) 、文 6 1 中证明了d u a d i c 码的这些推广保持了平方根界的性质； 6 ) 、文 4 】中描述了d u a d i c 阿贝尔码和差集的关系； 7 ) 、文【9 】9 中对极值自偶码和d u a d i c 群代数码进行深入的研究 2 1 3 域上d u a d i c 码的存在性 讨论域f 上的d u a d i c 码的一个重要的内容是d u a d i c 码的存在性已有许多 相关的研究结果t l e o n 解决了2 元域上d u a d i c 循环码的存在性： 5 定理2 1 1i 】存在2 元的m 为奇数) 长d u a d i c 循环码当且仅当2 是模n 的平方剩余 s m i d 解决了q 元域上d u a d i c 循环码的存在性： 定理2 1 2 【，】存在q 元的n 为奇数) 长d u a d i c 循环码当且仅当q 是模 的平方剩余 当g 为阿贝尔群时，w a r d 和朱烈解决了d u a d i c 阿贝尔码的存在性； 定理2 1 3 f g 中存在d u a d i c 阿贝尔码当且仅当对每个整除n 的素因子 p ，g 是p - 齐性的 张胜元对定理2 1 3 用参数的形式给出更具体的判定条件： 定理2 1 4 嗍对每一个素数p n ，以n p 记g 的等于p 的初等因子的个 数，则f g 中存在d u a d i c 码当且仅当对每一个素数p i 仉如果n 。为奇数，那么 q 是模p 的二次剩余 当g 为一般群时，文【9 用中心本原幂等元或k 共轭类给出了中心d u a d i c 码存在的充分必要条件，且对一些特殊的类的中心d u a d i c 码用参数形式给出了 具体判定其存在性的充分必要条件t 定理2 1 5 【跏f g 中存在劈分为肛的中心d u a d i c 码当且仅当“在非平凡的 本原幂等元集合上导出的置换的循环分解中只合偶长的循环 定理2 1 61 9 f g 中存在劈分为p 的中心d u a d i c 码当且仅当肛在非平凡胙 共轭类集合上导出的置换的循环分解中只含偶长的循环 定理2 1 7mf g 中存在劈分为肛一l 的中心d u a d i c 码当且仅当q 模n 的阶 为奇数 定理2 1 8 【切设f = g f ( 4 ) ，如果p 一2 a u t ( g ) ，则f g 中存在劈分为i t 2 的中心d u a d i c 码当且仅当对任意 0 = l ，2 ，) ，( n ，2 2 。1 ) = 1 ， 文【9 】9 中还给出了扩展自偶码和d u a d i c 码的关系； 定理2 1 9f g 中可以扩展为自偶码的中心群代数码是一个劈分为# - 1 的奇 性中心d u a d i c 码 2 1 4d u a d i c 码的第二定义 在2 0 0 0 年，丁存生和k o h e l 1 9 对l c o n 等人提出的d u a d i c 码以有限群的域 上特征标理论为研究工具对d u a d i c 码做了进一步的推广首先介绍几个基本概 念 设f = g f ( q ) ，g 为n 阶阿贝尔群，运算为加法，( 吼n ) = 1 设为g 的指 6 数。是f 中包含次单位根最小的域扩张记c 为k 中的一个次本原单 位根由定理1 3 1 可设 g = z 几lx 磊2x 磊： 其中啦o = 1 ，2 ，t ) 为等于或大于2 的正整数，则g 中的每个元素g 可写成 g = ( g l ，9 2 ，m ) ，其中历磊。0 = 1 ，2 ，t ) 对给定h = ( h 1 ，h 2 ，h t ) g ，g 到上的特征标h 定义为 h ( 9 ) = ( tm “0 v , , 4 对任意给定h g ，c = e 口g c g y 9 f g ，定义 h ( c ) ；白h ( 9 ) 口g 对g 中的任意一个子集x ，定义 i x = ( c f g l k ( c ) = o ，对任意z x )( 5 ) 显然，& o ) = 蚱a c g y g f gi g e g 勺= o ) 易见对g 的任意子集x ，i x 是 f g 中的理想，从而也是f 上线性码 定义2 1 2 对g 中的任意一个非空的子集x ，g ( 在x 上) 的劈分是一个三 元组( x ， ，b ) ，且满足以下条件 1 ) 、x ，a ，b 均为g 中的某些q 一轨道的并； 2 ) 、x ，a ，b 是对g 的一个划分； 3 ) 、存在卢a u t ( a ) 使得p ) = x ，卢( a ) = b 和p ) = a 说明2 21 ) 、当a = b = 0 时，劈分( g ，o ，0 ) 称为平凡的； 2 ) 、0 总是属于x 的，记x ，_ x o i 3 ) 、有时也把满足上述定义的p 称为g 的一个劈分 以下给出d u a d i c 码的第二定义； 定义2 1 3 设( x ，a ，b ) 是g 的一个劈分，p 为相应的自同构，则劈分为“ 的d u a d i c 码( 或劈分群码) 定义为如下的4 个理想ti a ，咕，i x u 和“u b 说明2 31 ) 、当x = o ) 时，上述定义中的4 个码为第一定义中的4 类 d u a d i c 码； 7 2 ) 、当a = b ；0 时，劈分为( g ，d ，0 ) 的d u a d i c 码称为平凡的d u a d i c 码； 3 ) 、由定义2 1 3 可见，d u 8 ( 1 i c 码的存在性等价于g 的劈分存在性； 4 ) 、1 9 7 8 由j h v i n t 和f j m a c w i l l i a m s 2 1 】借助于特征标理论给出的广 义的二次剩余码定义，在他们的定义中就采用对群g 进行劈分的思想，这是劈 分群码最早的模型； 5 ) 、虽然对g 进行劈分构造码的思想在文【1 9 1 中首次提出，但是在文【2 2 ，2 3 中已经含有了这一思想文中提出分圆d u a d i c 码，主要是以分圆类( 也就是q 轨道) 这一数学工具对p ( p 为奇素数) 阶循环群进行了划分，进而定义分圆 d u a d i c 码 2 2 环上的d u a d i c 码 在环上讨论码的论文早在1 9 7 2 年开始已陆续发表 2 4 ，2 5 ，2 6 ，2 7 ，2 8 】1 9 9 4 年，h a m m o n s 等人【2 9 】发表了”t h e 蜀一l i n e a r i t yo fk e r d o c k ，p r e p a r a t a ，g o e t h a l s ， a n dr e l a t e dc o d e s 一文，再一次激起了人们对环上码的研究的兴趣，在这篇论文 中指出：一些最优的非线性二元码是蜀上的些线性码在格雷映射( g r a ym a p ) 作用下的象从此，在环上讨论线性码的论文大量发表，这其中包括在环上讨论 d u a d i e 码的论文最初，文【1 0 】给出环盈上d u a d i e 码的定义；随后，文【1 1 1 给出 了环忍k ( k 为正整数) 上的d u a d i c 码定义同年，文1 3 0 】还给出了4 元环f 2 + u f 2 上d u a d i c 码的定义从这些论文中可以看出t 群在环上的特征标理论以及群环 的分解结构定理在研究环上的d u a d i c 码起到关键的作用同时，他们延续了对 g 的劈分思想下面将主要给出磊m 上d u a d i c 码的概念。对于磊k 上的d u a d i c 码用中国剩余定理可以容易给出其定义( 参见文献【1 1 】) 设g 为n 阶阿贝尔码，运算为加法，n ) = 1 记o o ，0 l ，0 。为群g 在 映射z p x 作用下所有的轨道，称为p 一轨道有时也用0 。表示g 中元索z 所在的轨道，即以= 毛p x ，p 2 ) 记凼= 1 0 ，由于o o = o ) ，即d o = 1 ，所以 g l t ( p m ，d o ) = - n 用。表示g 上的自同构p 一1 作用在轨道o o ，0 l ，o 。上导出 的集合 o ，1 ，s 的置换关于群环磊m g 的结构有以下结论： 定理2 2 1 【1u 】( 1 ) 环知“g 和环z p m x 咖( p ”，d 1 ) o r ( p ”，d 。) 同构 ( 2 ) 名m g 中的每个理想，可以表示为i o xi l l ，其中l j ( 0 j 曼s ) 是g r ( p m ，d j ) 中所有理想( 1 ) ，( p ) ，( p 2 ) ，( p ”- 1 ) ，( 0 ) 中的某一个 ( 3 ) 理想i = 如1 1x xl 的对偶p = 譬( 0 ) xg ( 1 ) x 弓其中 ( o ) 。= ( 1 ) ，( 1 ) 。= ( o ) ，( p 。r = ( p ) ( 1 t n 一1 ) 8 以下给出环磊m 上的d u a d i c 阿贝尔码的定义t 定义2 2 1 1 1 】设( x ，a ，b ) 是g 的一个劈分，卢为相应的自同构，r 为p 的导出置换，则邑m 上的劈分为p 的d u a d i c 码定义为昂m g 中满足如下条件的 理想i = i o 厶： 1 ) 、如果0 j u b ，那么= ) 当且仅当( ，) = ( p ) i 2 ) 、如果0 j x ，那么= ( p m 2 ) 称( g ，瓯o ) 为g 的平凡劈分，相应的d u a d i c 码为平凡的d u a d i c 码为简单起 见，下文中对某个阿贝尔群g ，4 m g 中的d u a d i e 阿贝尔码简称为名m 上d u a d i c 码由定义可知，只有当m 为偶数时，如上定义的磊m 上的d u a d i c 码才有可能 存在 对z 口。上劈分为p l 的d u a d i c 码与环上的自偶码有着密切关系： 定理2 2 2 1 1 】设m 为偶数，则乙m 上每个自偶阿贝尔码是劈分为p 一1 的 d u a d i c 码反之，z p 上劈夯为灿一1 的d u a d i e 码是自偶阿贝尔码 作为特例，盈上的d u a d i c 码与五上的自偶码的关系在文【l o 】中给出 然而，对环上d u a d i c 码的存在性问题到目前为止尚未有好的结果p l e s s 等 人给出了如下结论t 定理2 2 31 3 1 】存在五上n 为奇数) 长非平凡的自偶循环码当且仅当对 任意正整数i ，- 1 2 ( m o dn ) 定理2 2 3 仅相当于解决了劈分为肛一1 的非平凡的d u a d i c 循环码存在性问 题劈分为“的非平凡的d u a d i c 阿贝尔码的存在性仍然是个未解决的问题 本文首先给出了z 4 上劈分为p 的非平凡d u a d i c 码存在的充分必要条件；其 后讨论劈分为p - l 的情形，即给出五上的非平凡自偶阿贝尔码存在的充分必要 条件，从而推广了定理2 2 3 9 3五上d u a d i c 存在性 本节给出了蜀上劈分为肛的非平凡d u a d i c 码存在的充分必要条件 3 1 充分必要条件 首先把文【9 】9 中的偶自同构进行推广，给出弱偶自同构的概念仍设g 为n 阶阿贝尔群，运算为加法，( p ，n ) = 1 ，g 的轨道为p 一轨道 o 是g 的一个轨 道，称为零轨道，g 的其它轨道称为非零轨道 定义3 , 1 1 设p a u t ( g ) ，如果肛作用在g 的所有轨道上的导出置换r 的 循环分解中至少有一个偶数长的循环，那么称这个自同构p 是弱偶的；如果弘作 用在g 的所有非零轨道上的导出置换的循环分解中只合偶数长的循环，那么称 这个自同构“是偶的 显然偶的自同构必然是弱偶的；反之则未必文【9 】中引入偶自同构是为了研究 域上d u a d i c 码( 按定义2 , 1 1 ) 的存在性，本文用弱偶自同构研究环上d u a d i c 码 ( 按定义2 2 1 ) 的存在性 定理3 1 1 设g 为n 阶阿贝尔群，( n ，p ) = 1 ，p a u t ( g ) 则环z p 。上存在 n 长的劈分为的非平凡d u a d i c 码当且仅当肛是弱偶的 证明设p a u t ( g ) ，且肛是弱偶的g 的p 一轨道为o o = o ) ，o o 。设 卢作用在g 的p - 轨道上导出 o ，1 ， 占) 上的置换r 的循环分解为 r = ( 0 ) ( e n - e l h ) ( 8 d 1 e d 妇) ， 其中e i j f 1 ，2 ，咕由弱偶自同构的定义知，在f 的p + 1 ) 个循环分解中至 少有一个循环是偶数长的，即至少存在k l ，d 使得“是偶数则对g 中 相对应的p 一轨道取： a = 0 e lu o c h u uo e ic ”1 ) b = 0 u 仉t iu u 0 。m x = g 似u b ) 此时有，p 似) 一b ，i z ( b ) = a ，u ( x ) = x 故( x ，a ，b ) 为g 的一个劈分依 d u a d i c 码的定义，即得z p m 上存在n 长的劈分为肛的非平凡d u a d i c 码 反之，设乃m 上存在n 长的劈分为p 非平凡的d u a d i c 码，即存在g 的劈分 ( x ，a ，b ) ，且a ，b 均g 中非零轨道的并，肛( ) = b ，“旧) = a 不妨设o j ， 则肛( o j ) = o ，u ) b ，p ( 阱( j ) ) = o ) a ，所以在p 的导出置换r 的循环分解 中，j 所在的循环( r ( j ) ，7 - 2 ( j ) ，) 必为偶数长，故肛是弱偶的 1 0 推论3 1 2 设g 为n 阶阿贝尔群，( n ，p ) = 1 ，磊t n 上存在劈分为# - t 的非 平凡d u a d i e 码当且仅当“一l 是弱偶的 通过以上定理，对于阿贝尔群g ，磊。上非平凡d u “t i e 码的存在性问题就转 化g 的弱偶自同构的存在性问题 本节主要讨论环五上d u a d i c 码的存在性此时g 的轨道为2 一轨道，且g 为奇数阶阿贝尔群 一个熟知的数论中的结论： 命题3 1 3 设p 是奇素数，则2 是模p 的二次剩余当且仅当p i4 - 1 ( r o o d8 ) ， 即p = 8 r4 - 1 ( 其中r 为正整数) 称满足2 7 1 ( r o o d n ) 的最小的正整数7 为2 模n 的阶，记为o r d 。( 2 ) o r d 。( 2 ) 与五上d u a d i c 码的存在性有重要关系。首先给出有关o r d 。( 2 ) 的一些性质 引理3 1 4 3 2 如果n = p m ，p 为奇素数，m 为正整数，o r d p ( 2 ) = s ，则 o r d 。( 2 ) = ，i 0 ，1 ，m 一1 ) 引理3 1 5 设p 为奇素数，则s = i 墨丽- 1 为奇数当且仅当p = 土3 ( r o o d8 ) 证明设p = 8 r 4 - 3 ( r 为正整数) 首先，证明o r d ，( 2 ) 为偶数，即o r d p ( 2 ) = 2 a ( a 为正整数) 事实上，若o r d p ( 2 ) 为奇数，则p 一1 = o r d p ( 2 ) 6 ( 6 为偶数) 因为 p ；4 - 3 ( r o o d8 ) ，所以2 是模p 的非二次剩余，即2 如_ 1 ) 2i 一1 ( r o o d p ) 而 2 ( p 一1 ) 2 = 2 0 r d p ( 2 ) 6 2 = ( 2 0 r d p ( 2 ) ) 6 2 ；1 ( r o o dp ) ，故矛盾从而。r d p ( 2 ) 为偶数 其次，证明s 为奇数如果p = 8 r + 3 ，那么p 一1 = 2 ( 4 r + 1 ) ，从而s = 赫- - 1 = ! 生2 a 卫= 4 学，即3 为奇数 如果p = 8 r 一3 ，那么p 一1 = 4 ( 2 r 一1 ) 由于o r d p ( 2 ) l p 一1 ，所以o r d p ( 2 ) = 4 t 或者2 t ，其中t l2 r 1 若o r d p ( 2 ) = 2 t ，则2 2 。= l ( r o o d p ) 因为模p 存在个本原元( ，所以2 ( f ( r o o d p ) 其中j 为正整数于是2 2 = ( ( f ) 2 ! e 2 i1 ( r o o d p ) 又有( 一l1 1 ( r o o d p ) ，所以p 一1 2 l t ，即可尝= 互i i 譬可为整数因为t 为奇数，所以f 为偶 数从而2 是模p 的二次剩余，即pi 士l ( r o o d8 ) ，这与p = 8 r 一3 矛盾故 o r d p ( 2 ) = 4 t ，则s = 齑南= 掣= 学，即s 为奇数 反之，假设p ! 士1 ( r o o d8 ) 此时，2 是模p 的二次剩余则2 ( p 一1 ) 2 ；1 ( m o dp ) ，即有o r d p ( 2 ) i 譬从而s = ；墨南为偶数，这与巴知s 为奇数相矛盾 故p = 4 - 3 ( r o o d8 ) 证毕 若p 为奇素数，则p j 土1 ( r o o d8 ) 或p = 4 - 3 ( r o o d8 ) 于是由引理3 1 5 直 接可以得到如下推论t 推论3 1 6 设p 为奇素数，则s = 焉- 丽1 为偶数当且仅当p i4 - 1 ( m o d8 ) 推论3 1 7 设p 为奇素数，且p = 土3 ( m o d8 ) ，则o r d p ( 2 ) = 2 t 或4 ，其中 为奇数 在推论3 1 7 中，当o r d p ( 2 ) = 2 t 时，称o r d p ( 2 ) 为单偶；当o r d p ( 2 ) = 4 t 时， 称o r d ，( 2 ) 为双偶 若g 为p 阶循环群，即g 中非零元的阶均为p 由轨道的生成方式易知g 中每个非零轨道的元索个数均相等，且均等于o r d v ( 2 ) 故g 中非零轨道的个数 为s = i 赫- 1 引理3 1 8 设g 为v ( p 为奇素数) 阶循环群，如果存在“。a u t ( g ) ，它的 导出置换r 的循环分解中有一个k 长的循环( 1 k s ) ，那么r 的其它循环长度 也必为 证明记t = o r d p ( 2 ) 设作用在g 的非零轨道0 1 ，以上导出置换f 有 一个长的循环，则相应地有k 个轨道在作用下完成一次循环，即 0 口 肛。( d 。) p 。( ( ) 口t 一：。) ( o 一。) = a ，2 a ，2 2 a ，2 t - 1 0 ) ， =d 0 口= n n ，2 a a ，2 2 。口，一，2 t - 1 n ) =o q d = ( 一1 n ，2 a 一1 口，2 2 舻一1 n ，2 t - l c l 一1 n = o 计。= 以 从而存在i ，0 t l 使得a n = 2 i 。，即矿12 ( m o d p ) ，k 是满足上式最小 的正整数 取b g o 。u o 。u - u o 一一。，且b 0 ，贝0 o b = b ，2 b ，2 2 b ，2 t - 16 ) ， ( 0 6 ) = o 口b = a 6 ，2 a b ，2 2 a b ，2 t - 1 a 6 ， p a ( 0 d 女一2 b ) = o a 一1 6 = a 一1 b ，2 a 一1 b ，2 2 a 一1 b ，一，2 t - l c e 一1 b ) p 。( 0 一一1 6 ) =o 一6 = 0 6 因此得到导出置换r 的另一个长为的循环于是得到如下等式， 1 2 s = k r 或p 一1 = o r d 口( 2 ) k r ( 6 ) 证毕 以下考虑g 为p 8 阶循环群情形，其中p 为奇素数，e 为正整数 由于g 为矿阶循环群，对任意i ( 1 i e ) ，g 中必有唯一的p 阶子群，且 g 中所有p l 阶元均在这个p 阶子群中记c 0 为p 。阶循环群g 中元素的阶为 p i 的所有元索组成的集合易知lc 0i = ) = p l 。0 1 ) ( ( n ) 为欧拉函数) 取 。g ，使得o ( z ) = p ，则z g t 因为( 2 ，p ) = 1 ，所以轨道o 。中的每个元素的阶 均为p d ，即o 。印取口c 0 ，但g 掣o 。轨道仉和o 中元素的阶均相等， 即为p 依轨道生成方式可知： o ；i = io vl = o r d p t ( 2 ) 设包含在q 中不同轨道 个数有s 个，则这s t 个不同轨道构成q 的一个划分，即 = 。r d p l l 2 ) s i 或驴器 ( 7 ) 引理3 1 9 设g 为矿阶循环群，对于1 i e ，记q 。为g 中元素的阶为p l 的所有元素组成的集合，如为包含在c 0 中不同轨道个数如果存在a u t ( g ) ， 它的导出置换r 的循环分解中有一个长的循环，那么存在一个i o ( 1 i o 茎e ) ， 使得k ls o 证明因为是一个自同构，所以每个轨道在p 。作用下保持长度及轨道中 元素的阶不变设0 。是作用在轨道上产生的长循环中的一个轨道，并设 o ( z ) ；一o ，贝4 七8 l 。 若k = ，则命题得证若 ，需证l5 沁事实上，依引理3 1 8 的证明 思路，需考虑g 中所有矿阶元素组成的集合亿，。类似地，设q 。中所有非零 轨遭在自同柯加作用下导出置换的循环分解有r o 个女长的循环，则 s i o = k r o ( 8 ) 从而k i8 o 证毕 引理3 1 1 0 设g 为p 。阶循环群，则g 中存在一个弱偶的自同构当且仅当 pi4 - 1 ( m o d8 ) 证明设g 中存在一个弱偶的自同构p ，即p 的导出置换r 的循环分解中至 少存在一个偶长的循环，记这个循环长为c ，则z 为偶数因为g 为循环群，必存 在正整数a 使得p = 肛。由引理3 1 9 知，存在某个正整数s 。使得s 。= ，即8 “ 为偶数由( 7 )