（基础数学专业论文）基于m序列的低相关序列集和常权码的构造.pdf

中文摘要 于两要 伪随机序列在数据加密，编码理论和码分多址通信系统中有着重要的应用 通过组合m 序列可得到随机性较好的伪随机序列，而m 序列可由线性反馈移位 寄存器来生成相关函数是衡量序列伪随机特性的一个重要指标m 序列具有理 想两值自相关性，但关于它的互相关性，已知的研究成果并不多此外，序列集的 构造与m 序列的相关性也有紧密的联系g o l d 序列集与小集合的k a s a m i 序列集的 相关分布就主要依赖于m 序列及其采样的互相关性因此，研究m 序列的相关性 具有十分重要的意义 本文基于m 序列的性质，讨论了与之相关的以下几个问题首先，对于不同周 期长度的m 序列的互相关性，本文发现了一类新的仇序列的d - 采样，证明了它的 互相关函数取值为四值，并完全确定了其相关分布其次，在奇特征域上，本文构 造了一类矿元序列集，并借助二次型理论将序列集的集合容量和相关值分布完全 确定与已知的序列集相比，本文所构造的序列集在具有较低相关性的同时还具 有较大的集合容量最后，本文利用循环差集构造出了一类二元常权码，这种方法 推广了以前基于m 一序列构造常权码的方法，并从中得到了一类新的最优二元常权 码 关键词：m 序列；d - 采样；相关分布；集合容量；循环差集；常权码；极小距离 湖北大学硕士学位论文 a bs t r a c t p s e u d o r a n d o ms e q u e n c e sh a v es i g n i f i c a n ta p p l i c a t i o n si nd a t ae n c r y p t i o n ，c o d - i n gt h e o r ya n dc d m ac o m m u n i c a t i o ns y s t e m t h es e q u e n c e sw i t hg o o dr a n d o m n e s s p r o p e r t i e sc a nb eo b t a i n e db yc o m b i n i n gm s e q u e n c e s w h i c hc a nb eg e n e r a t e db yl i n e a rs h i f tf e e d b a c kr e g i s t e r t h ec o r r e l a t i o no fs e q u e n c e sa r ea ni m p o r t a n tc r i t e r i o nt o e v a l u a t et h er a n d o m n e s sp r o p e r t i e so fs e q u e n c e s m s e q u e n c e sh a v ei d e a l l e v e la u t o - c o r r e l a t i o n ，b u tf o rt h e i rc r o s s c o r r e l a t i o n ，t h e r ea r eo n l yaf e wr e s u l t so b t a i n e d b e s i d e s ，t h ec o n s t r u c t i o n so ff a m i l yo fs e q u e n c e sh a v ec l o s er e l a t i o n s h i pw i t ht h ec r o s s - c o r r e l a t i o no fm s e q u e n c e s t h ed i s t r i b u t i o n so fc o r r e l a t i o n so ft h eg o l ds e q u e n c e s a n dt h es m a l ls e to fk a s a m is e q u e n c e sa r em a i n l yd e p e n d e n to nt h ec r o s s - c o r r e l a t i o n b e t w e e nm s e q u e n c e sa n dt h e i rd - d e c i m a t i o n s t h u s ，i t sv e r ym e a n i n g f u lt os t u d yt h e c o r r e l a t i o no fm s e q u e n c e s i nt h i sp a p e r , b a s e do nt h ep r o p e r t i e so fm s e q u e n c e s ，w ed i s c u s ss o m ep r o b l e m s a sb e l o w f i r s t l y , f o rt h ec r o s s c o r r e l a t i o no f 丌t s e q u e n c e so fd i f f e r e n tl e n g t h si nt h e f i n i t ef i e l d sw i t hc h a r a c t e r i s t i c2 ，w ef i n dan e wd - d e c i m a t i o no fm s e q u e n c ea n dp r o v e t h a tt h ec r o s s c o r r e l a t i o nf u n c t i o nt a k e sf o u rv a l u e s 。a n dt h ed i s t r i b u t i o no fc o r r e l a t i o n i sc o m p l e t e l yd e t e r m i n e d s e c o n d l y , i nt h ef i n i t ef i e l d so fo d dc h a r a c t e r i s t i c ，w ec o n - s t r u c tan e wf a m i l yo fp - a r ys e q u e n c e sa n dd e t e r m i n et h ed i s t r i b u t i o no fc o r r e l a t i o nb y t h et h e o r yo fq u a d r a t i cf o r m so v e rf i n i t ef i e l d s c o m p a r i n gw i t hs o i i l eo t h e rk n o w nr a m - i l i e so fs e q u e n c e s ，t h ef a m i l yo fs e q u e n c e sc o n s t r u c t e di nt h i sp a p e rh a sn o to n l yl o w c o r r e l a t i o nb u ta l s ol a r g e rf a m i l ys i z e a tl a s t , w ec o n s t r u c tac l a s so fb i n a r yc o n s t a n t w e i g h tc o d e sb ya p p l y i n gc y c l i cd i f f e r e n c es e t s t h i sm e t h o dg e n e r a l i z e st h e c o n s t r u e t i o no fc o n s t a n tw e i g h tc o d e sb a s e do nm s e q u e n c e s a n df r o mw h i c hw ec a no b t a i na n e wc l a s so fo p t i m a lb i n a r yc o n s t a n tw e i g h tc o d e s k e yw o r d s ：m s e q u e n c e ；d - d e c i m a t i o n ；d i s t r i b u t i o no fc o r r e l a t i o n ；f a m i l ys i z e ； c y c l i cd i f f e r e n c es e t ；c o n s t a n tw e i g h tc o d e ；m i n i m u md i s t a n c e 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 论文作者签名：夸念 签名日期：埘年5 月矸日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本：学校有权保存并向国家有 关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目 的的前提下，学校可以公开学位论文的部分或全部内容( 保密论文在解密后遵守 此规定) 作者签名： 夸念 指导教师签名：讶；莩匀 日期：唧5 ，珥 日期：1 5 矸 1 引言 1引言 随着信息时代的到来，信息安全越来越受到人们的重视，而密码技术作为 保证信息安全的一个重要手段亦显得更加重要1 9 4 9 年s h a n n o n 发表的“保密系 统的信息理论”【1 】为对称密码体制建立了理论基础，密码学从此成为一门科学 1 9 7 6 年，d i f f e 和h e l l m a n 在“密码学的新方向”【2 】中首次证明了在发送者和接收者 之间实现双钥密码系统是可能的，开创了公钥密码学的新纪元序列密码作为对 称密码体制的基本方式之一，是现代密码学的一个重要研究分支在序列密码体 制中，加密和解密实现方式简单，速度快，而且由于可以有效地运用数学工具来研 究它，序列密码理论相对比较成熟，因而受到广泛重视序列密码算法的安全强度 取决于相应的密钥流的质量，因而产生好的密钥流是序列密码体制的关键问题 s h n a n o n 证明了如果密钥流序列是随机的，那么相应的序列密码体制将是无条件 安全的序列密码因其易于实现、加解密快速、无错误传播、应用协议简单等优 点，仍然在政府、军事、外交等重要部门的保密通信中广泛被使用因此，序列密 码一直是争相研究的热门课题 1 1 伪随机序列的研究背景 1 1 1 伪随机序列的随机性指标 如果一个序列，一方面它是可以预先确定的，并且是可以重复地产生和复 制的；一方面它又具有某种随机序列的随机统计特性，我们便称这种序列为伪 随机序列简单地讲，伪随机序列是具有某种随机特性的确定的序列对于二 元 0 ，1 ) 序列，g o l o m b 提出了三个随机性假设： 1 平衡性：在二元序列的一个周期中，0 与1 的个数相差要尽量小一条不平衡 的伪随机序列在实际应用中存在安全隐患。 2 良好的游程性质：在二元序列的一个周期中。0 游程与1 一游程的个数应基 本相等，即具有良好的统计特性 3 两值自相关性：在序列的一个周期中，它的周期自相关函数应该是两值的， 从而可应用于更多实际领域中 大部分密钥流序列都是使用线性反馈移位寄存器( l f s r ) 生成的，这是因 为l f s r 易于硬件实现，而且它可以产生具有较好统计特性的序列另外，基 于l f s r 的结构，由它所生成的序列易于使用代数工具进行研究然而，正如以上 所述，序列密码的安全性主要依赖于密钥序列，而破译序列密码的关键也是需要 求解出所使用的密钥序列同时，为了抵抗对序列密码的攻击如相关攻击等，采用 湖北大学硕士学位论文 的伪随机密钥序列仅满足g o l o m b 提出的三个随机性假设是不够的，它们还需具 备其它一些特性评价序列伪随机性的常用指标还有： 周期：设8 。0 = s o s l s 七是任一序列，如果存在正整数仡使得s 件竹= s ( i 0 ) 成立，称n 为该序列的周期所有可能周期的最小值称为序列的最小周期， 通常所指的序列的周期都是最小周期要想获得好的随机性，序列周期应该尽量 大 o 线性复杂度：一条序列的线性复杂度定义为生成该序列的最短 线性反馈移位寄存器的长度如果用l 表示所考虑序列的线性复杂度，使 用b e r l e k a m p - - m a s s e y 算法【3 1 只需连续的2 比特就可以恢复整条序列，故而 低线性复杂度的序列做为密钥流是很不安全的 序列的集合容量：即要求可供使用的序列数量应足够多 因此，随着信息技术的快速发展，如何使得我们使用的伪随机序列更加安全 也就显得越来越重要故而，如何设计和选择具有优良特性的伪随机序列已成为 序列密码研究的关键问题之一 1 1 2 伪随机序列的应用 伪随机序列的应用非常广泛，它可在软件设计中用于模拟实践环境；工程中 用于模拟自然环境、模拟干扰、模拟噪声等；在通信中用于扩频通信的关键技 术，例如码分多址( c d m a ) 技术；在其他专业领域如测量测距、雷达导航、气象、 空间探测、军事和密码学中都有应用 伪随机序列系列具有良好的随机性，并且有预先的可确定性和可重复性。这 些特性使得伪随机序列得到了广泛的应用，特别是在c d m a 系统中作为扩频码已 成为c d m a 技术中的关键问题下面介绍伪随机序列在扩频通信的c d m a 技术中 的应用c d m a ( c o d e d i v i s i o nm u l t i p l ea c c e s s ) ，码分多址，是近年来在数字移动 通信进程中出现的一种先进的无线扩频通信技术c d m a 的基本技术之一是扩 频，因此这一多址技术具有很强的保密性。在c d m a 系统中，用户数的增加相当于 背景噪声的增加，将造成话音质量的下降但系统对用户数也有限制，实际操作者 可在容量和话音质量之间折衷考虑如果能控制住用户的信号强度，在保持高质 量通话的同时，系统能容纳的用户越多当然越好因此，在c d m a 系统中采用的伪 随机序列必需具备以下随机指标： 0 大的集合容量：在c d m a 系统中，每个用户使用一条序列，为了使系统可以 容纳更多的用户使用，所采用的伪随机序列集的集合容量应该尽量大 o 低的相关特性：在c d m a 系统中，每个用户使用一条序列，为了能够成功地 降低来自同一信道中不同用户之间的相互干扰程度，所采用伪随机序列集中的序 列必需具有低值相关特性 2 1 引言 由以上介绍可以知道，容量较大和相关性较低的伪随机序列集是保证通信 具有较好的抗干扰性和隐蔽性的重要因素降8 1 人们在评价序列随机性和构造 具有良好伪随机性的序列方面做了很多的探索，并提出很多评价序列和序列 集随机性和相关性等性质的指标和构造较好性质的随机序列以及序列集的方 法 9 - 3 0 。寻找更多更好的实用的伪随机序列一直是人们追求的目标到目前为止， 人们已经找到了许多具有较好性质的序列，比如g o l d 序列【4 】、b e n t 序列 6 1 、n o 序 列t 7 l 、t n 序列【9 1 、小集合的k a s a m i 序列【捌、广义的大集合k a s a m i 序列f l l 】等等 由w e l c h 界【8 】可以知道，对于一个序列集而言，序列的周期，相关值和集合容量之 间存在着一定的制约关系，这种制约关系主要体现在序列集相关值的最大边峰值 和集合容量之间，一般情况下，在增加序列集的集合容量的同时，势必会增大相关 值的最大边峰值因此，不论是在理论上与实际应用中，构造具有低相关特性和较 大集合容量的序列集一直是一个研究的热点和难点问题 1 2 纠错码理论在密码学中的应用 随着密码学在各行各业的应用越来越广泛，在具体的应用中也伴随着需要解 决的一些问题比如，在密码传输过程中，由于所要处理的数据量特别大，往往会 出现一些误差，而这些误差会给用户带来一定的麻烦和损失或许正是社会的这 一巨大需求促进了纠错码理论及其工程应用的迅速发展，各种纠错编码以其自动 纠正或检测出数据传输中的误差这一特点，深受各界的青睐 1 9 4 8 - 1 9 4 9 年s h a n n o n 提出著名的信道编码定理。奠定了现代通信特别是纠错 码的理论基础在计算机中和数据通信中，经常需要将二进制数字信号进行传递 在传递信息过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即 在传递过程中二进制信号0 - i 能会变成1 ，或l 可能会变成0 由于在计算机和数 据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得 相当重要了解决这个问题的主要途径之一就是采用纠错码的方法提高抗干扰能 力这种方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收 端的纠错码装置就能立刻发现错误，并将其纠正 1 - 2 _ 1 线性码基本参数介绍 分组码和卷积码是两类较重要的纠错码，其中分组码在数字通信和数据存储 系统中已被广泛应用基于代数群这一数学工具，分组码中线性分组码的研究理 论相对成熟，它主要包括汉明码和循环码一个k ，纠线性码是指码中的各个码字 之间具有一定的线性关系，即这些码字总体构成了n 维线性空间的一个k 维子空 间，其中n 为码长，惫为子空间的维数，具体可参见文献【3 1 】 人们在构造具有良好性能的线性码方面做了很多的探索，并提出很多关于评 3 湖北大学硕士学位论文 价一个码的“好坏”的标准对于一个给定的h ，纠线性码，人们主要关注它的如下 几个参数： o 码字的长度：即上述定义中的参数佗； o 码字的个数：它与维数k 密切有关； o 码字的权重：指的是一个码字中非零元的个数； 码字汉明距离：给定两个不同的码字，它们对应位置取值不同的个数，即为 这两个码字之间的汉明距离； 码的极小汉明距离：一个码中所有不同码字之问的汉明距离的极小值称 为码的极小汉明距离，简称码的极小距离 码的极小距离是一个非常重要的参数，它与码的纠错能力紧密相关对于任 意一个h 纠分组码，若要在码字内检测出e 个随机错误，则要求码的极小距离至少 为e + 1 ：若要在码字内纠正t 个随机错误，则要求码的极小距离至少为2 t + 1 【3 1 1 故 而确定一个码的极小距离具有十分重要意义对于一个线性码，由于它的极小距 离就是各个码字权重的极小值，所以确定了线性码的权重分布即可确定码的极小 距离不仅如此，码的权重分布在保密通信和检错码等方面也有重要应用确定码 的权重分布这一基本问题没有系统的方法，在一般情况下，解决这一问题的复杂 性比较大而且随着维数的增大，问题的复杂性与计算量急剧增加至今为止，已 知的完全确定了权重分布的码为数并不多因此，一般来说，确定一个码的权重分 布是一个比较困难且十分有意义的问题 1 2 2 二元常权码研究背景简介 常权码，顾名思义，指的就是具有码字权重都相等这一特性的码二元常权 码不仅在纠错码理论中占有重要的地位，而且在理论和应用上都具有重要意义 二元常权码是一种分组码，而且它是一种检测码，并在计算机和通信系统中有 着很多的应用，如差错控制系统( a r q ) 3 2 , 3 3 在检测中，只要检测接收到的码组 中“1 ”的数目是否对就可以知道传输是否正确它的主要优点是简单，适于传输电 传机等 一个参数为( 佗，魈d ，彬) 的常权码指的是一类码字的长度为礼，所含码字的个 数为m 。码字之间的极小汉明距离为d 且每个码字的权重均为w 的码关于常权 码的研究，通常有两种情形：一是构造常权码并且设法确定码的各个参数；另 一种情况是，给定常权码的参数n ，d 和w ，考虑满足条件的码字个数是多少其 中，记满足条件的码字个数值的最大值为a ( 几，d ，叫) 因此，如何确定a ( n ，d ，叫) 的 值就是另一个主要研究内容在理论上，已经可以找到m 的一些理论上界，可 参见文献【3 4 ，3 5 等，但是如何确定m 的具体值仍然是一个棘手的问题称一 1 引言 个( 礼，m ，d ，叫) 码是最优的，如果m = a ( n ，d ，叫) 借助于不同的数学工具和方法， 许多常权码已经构造出来 3 1 , 3 6 , 3 7 , 3 8 ，3 9 , 4 0 1 ，而且其中还包括一些最优常权码 1 3 论文的研究内容和组织结构 本文从m 序列的相关性出发，简述了m 序列相关性的研究现状，并给出了一 类具有四值相关的m 序列的d 采样基于m 序列的相关性与序列集的构造间的 联系和文献【1 1 】中的做法，并借助有限域上的二次型理论，本文构造了一类p 元序 列集，而且完全确定了序列集的集合容量和相关分布另外，本文利用循环差集的 性质将文献 4 0 中利用仇序列构造常权码的方法进行了推广，并得到了一类新的 最优常权码 论文结构如下： 第一章介绍了伪随机序列的相关背景知识及其随机性指标，简要阐述了纠错 码理论在密码学中的应用，介绍了关于线性码的一些基本参数，并论述了构造性 能较好的码以及确定码的权重分布和极小距离的必要性 第二章介绍了有关有限域和伪随机序列的一些基本概念，主要给出了有限域 上关于二次型的一些基本结论 第三章给出了关于仇序列的一些概念和结论，并概述了m 序列互相关性的 已知结果对于不同周期长度仇序列及其采样的互相关性，找到了一类新的具有 四值相关的采样因子，而且确定了其相关分布 第四章首先考察了有限域上一类方程的解的性质，并结合二次型理论讨论了 域上一类指数和的分布最终利用上述讨论的结果构造出了一类非二元序列集， 而且确定了序列集的集合容量和相关值分布 第五章是首先介绍了文献【4 0 中用m 序列构造常权码的方法，基于t t 序列 与循环差集的关系，讨论了循环差集的一些基本性质，并利用循环差集构造了一 类新的二元常权码，而且其中存在最优常权码 第六章是对本文工作的总结和展望 5 湖北大学硕士学位论文 2预备知识 2 1 有限域上一些基本概念与结论 定义2 1 若域f 含有有限个元素，则称f 为有限域或g a l o i s 域 最简单而又最基本的有限域是整数环z 模素数p 的剩余类域，简记为f p 域中 元素的个数称为有限域的阶，而域中单位元对于加法的阶称为域的特征有限域 的特征是一个素数一般地，若f 为有限域，则f 中含有矿个元素，其中素数p 为域的 特征，礼是域f 在它的素域r 上的扩张次数另一方面，给定一个素数p 和正整数n ， 唯一存在一个含有矿个元素的有限域含有矿个元素的有限域是多项式一z 在 素域砸p 上的分裂域，因此，有限域可以表示成f 矿= z ：矿= z ) 具体细节可参 见文献【4 1 】 定义2 2 有限域n 的的乘法群f ；。= o 中的生成元叫做跏的的本原元， 而本原元在h 上的极小多项式叫做f 矿的上的一个本原多项式 下面介绍有限域上的迹函数及其相关性质 定义2 3 设正整数t , = e m ，对于任意的z 勋，称 为域砸 矿到f p m 的迹函数 迹函数有如下性质，可参见文献【3 1 ，4 l 】： ( 1 ) t 螺( z ) = t 蠕( 妒) ； ( 2 ) t r 象a x + b y ) = a t r 象( z ) + b t r 象( y ) ，其中z ，y 砸，a ，b 砸； ( 3 ) t r ( z ) = t r ，( t r n ( z ) ) 下面介绍有限域b 上函数的迹变换，具体细节可参考文献【6 】 设厂( z ) 是f 矿上的一个函数，它的迹变换定义为 氕a ) = u ，( z ) + n ( 妇) ， x e f p ” 其中入f p n 且u 是p 次本原复单位根 6 一 m 妒 刀 州瑚 = z 嘿 r 2 预备知识 设q = 矿有限域f g 是f p 上的佗一维向量空间对于给定的上的一组 基 q 1 ，a 2 ，q n ，每个元素z f q 就可以唯一的表示成z = x l c t l + x 2 0 e 2 + + z n a n ，其中鼢f p ，1 i n 在这种表示下，域与一向量空间叼同构 称n 上的函数，( z ) 是一个二次型，如果在睇上它可以写成如下形式 ，( z 1 ，z n ) = a i j x i x j ，a i j 1 i s j n 令矩阵a = ( o 巧) n x n ，其中啦t = 0 关于有限域峰上二次型的讨论，需分素数p 是奇数还是偶数两种情况分别进 行具体细节参见文献【4 1 】下面我们仅作些简要论述 在有限域f 2 n 上，二次函数，( z ) 迹变换的值完全由矩阵a m 秩决定从另一方 面讲，也可说是由关于变量x 的方程 b s ( x ，z ) = f ( x ) + f ( z ) + f ( x + 2 ) = 0 ，v z f 2 n 的解的个数决定矩阵a 的秩称为，( z ) 的秩，记为r a n k ( ，) ，它是一个偶数 4 2 1 对于有限域f 2 n 上的二次型，扛) ，它的迹变换有下面的结论： 引理2 4 【4 2 】设， ) 是f 2 ，l 上一个秩为2 枷| 勺二次函数，其中1 h n 2 那 么，( z ) 迹变换的值有如下分布： 衲= 的周期自相关函数； 当i j 时，g j ( 7 ) 即为序列 s i ( t ) ) 和 s j ( t ) ) 的周期互相关函数 称序列集厂中两条序列 & ( 亡) ) 和 勺( t ) ) 是循环不等价的，如果对于任意的7 - 均 有i g ，j ( 7 ) l 2 有 刚吐矿圳= 1 五如果嚣奇数 1 0 n + 町 一 0乳 渤 i | rg 3 一类新的不同周期长度m 序列的d 采样 3一类新的不同周期长度m 序列的d 一采样 仇一序列最初是由g o l o m b 于1 9 5 4 年从线性移位寄存器序列中发现的，它具有 良好的伪随机性质并满足g o l o m b 提出的三个随机性假设，即矾序列具有平衡性， 良好的游程性质和理想两值自相关性在序列密码中，m 序列因其良好的伪随机 特性而占有非常重要的地位人们常利用m 序列或其它伪随机特性较好的基本 序列通过非线性变换来构造伪随机特性好的伪随机序列序列的相关函数则是衡 量一条序列伪随机特性的重要指标之一，然而，m 序列的互相关函数至今没有得 到一个比较完善的结果本章首先介绍关于蹶序列的一些基本概念，并概述了关 于m 序列相关函数的研究现状，而且给出了一类新的m 序列及其d 一采样的互相关 函数，具有一定的理论意义 3 1 基本概念介绍 首先给出与m 一序列相关性有关的一些概念关于m 序列的概念，可以从序列 的周期，联结多项式等不同角度去刻画在此，我们只给出其中一种刻画方式 定义3 1 设堡= a o a l a n 是一个g 元t , 级线性移位寄存器序列，它适合递归 关系 鲰+ c l a k 一1 + + c n a k n = 0 ，k 扎， 其中c ，l 0 如果堡的周期是g n 一1 ，则称鱼是最长q 元礼级线性移位寄存器序列，简 称m 序列 命题3 2 设鱼= a o a l a n 是f g 上f l o n 级r n - 序列，则f 口n 中必存在某个本原 元o t 和非零元p ，使得 a i = t r 7 ( 触4 ) ，i = 0 ，l ，2 ， 上述命题即说明m 序列可以用迹函数表示，从而使人们可以利用迹函数的性 质和有限域上的其它工具对m 序列进行深入的研究 定义3 3 设a q = a o a l a 。是一个f 口上的一个周期序列，对任意整整是反称 a o a d a 2 d 。a n d 。 为a 的一个采样序列，简称为堡的d 采样，其中称d 为采样因子 湖北大学硕士学位论文 3 2 关于m 一序列互相关性的已知结果 在这一节中我们讨论m 序列的相关性首先根据第二章中的定义2 7 以 及m 序列的迹表示可以知道，r t t 序列具有理想两值自相关性，即自相关函数为 ，= 巍到( m o d ) ， 其中嘞是一周期为n = p - 一1 的m 序列 除了理想两值自相关性外，m 序列的互相关性质也被广泛的研究但关于 它的互相关函数至今还没有给出一个完整的描述，仅能确定在某些特定条件下 的互相关函数值事实上，基于m 序列能用迹函数表示这一事实，对于周期相同 的m 序列互相关函数的研究，可以归结为m 序列与其d 采样序列互相关函数的研 究，其中要求采样因子d 与序列的周期互素 近几年来，m 序列的互相关性质被广泛的研究以用来构造低相关序列集经 过不断的探索与研究，许多具有低相关特性的序列集已经被构造出来，其中有两 个比较经典的例子：g o l d 序列集和小集合的k a s a m i 序列集g o l d 序列集是将两个 相同周期长度的m 序列组合在一起进行研究，它的出现进一步促使具有相同周期 长度的m 序列的互相关性被广泛地研究，且至今已得到部分较好的结果参见文 献【4 5 ( 一) 具有相相同周期长度m 序列的互相关函数 ( i ) 相关值函数为三值的d 采样因子 d = 2 知+ 1 ，其中n g c d ( n ，忌) 是奇数，见文献【4 ； d = 矿奄一p 岛+ 1 ，其中p 是素数r n g c d ( n ，庇) 是奇数对于p = 2 见文献 4 6 】， 对于p 2 见文献【4 7 ，4 8 ； d = 2 他2 + 2 ( n + 2 ) 4 + 1 ，其中珏三2 ( m o d 4 ) ，见文献【4 9 】； od = 2 n 2 + 1 + 3 ，其中n 兰2 ( m o d 4 ) ，见文献【4 9 】； d = 2 ( n - 1 ) 2 + 3 ，其中佗是奇数，见文献【5 0 】； od = 2 ( n 一1 ) 2 + 2 ( - 1 ) 4 1 ，其中n 兰1 ( m o d4 ) 是奇数，见文献 5 1 ，5 2 】； d = 2 ( n 一1 ) 2 + 2 ( 3 n 一1 ) 4 1 ，其中n 三3 ( m o d 4 ) 是奇数，见文献 5 1 ，5 2 】； od = 铲南+ 1 ) 2 ，其中p 是奇素数 qn g c d ( n ，克) 是奇数，见文献【4 7 ，4 8 od = 2 3 ( n - 1 ) 2 + 1 ，其中n 是奇数，见文献【5 3 ( i i ) 相关值函数为四值的出采样因子 d = 2 竹2 “一1 ，其中n 兰0 ( m o d4 ) ，见文献【5 1 】； 一1 2 3 一类新的不同周期长度m 序列的d 一采样 d = ( 2 “2 + 1 ) ( 2 竹4 1 ) + 2 ，其中钆兰2 ( m o d4 ) ，见文献【5 1 】； n 2 d = 2 肌，其中n 三0 ( m o d4 ) ，0 m 2 ，见文献【4 8 】； d = 2 靠2 2 n 4 + 1 ，其中n 兰0 ( m o d4 ) 且礼4 是奇数，见文献【5 4 1 ； od = p - 一i ) 2 + ，其中0 i n 且矿三1 ( m o d 4 ) ，见文献【4 8 】； ( i v ) 相关值函数为六值的d 采样因子 od = ( 2 n 一1 ) 3 + 2 5 ，其中n 是偶数，8 n ，r 2 5 ( 2 n 一1 ) 3 2 ( m o d 3 ) ，见 文献【4 8 ，5 5 】； d = 2 ”2 2 n 4 + 1 ，其中n 三0 ( r o o d 8 ) ，见文献【4 8 ，5 5 】； d = p - - 1 ) 3 + p ，其中o i 佗，n 是偶数，p 三2 ( m o d 3 ) n p 一( 矿一1 ) 3 2 ( m o d3 ) ，见文献【4 8 】； d = 矿2 一矿4 + 1 ，其中n 三o ( m d d 4 ) 且矿4 2 ( m o d 3 ) ，见文献【4 8 】； ( 二) 具有不同周期长度m 序列的互相关函数 与g o l d 序列集不同，小集合的k a s a m i 序列集是通过将一个m 序列与另一个 短周期的m 序列的所有循环移位相加而构造出来，这种序列集的相关性主要 依赖于不同周期长度的m 序列的互相关性，从而激发n e s s 和h e l l e s e t h 着手研究 不同周期长度的仇一序列的互相关性2 0 0 6 年4 月，他们给出了第一类二元m 序 列的采样( 短周期的m 序y u ) 使得其互相关函数取值为三值随后由h e l l e s e t h ， k h o l o s h a 和n e s s 给出了一个总结性的结果，并且他们猜想没有其它三值相关的 采样。2 0 0 7 年1 1 月，n e s s 和h e u e s e t h 又给出了第一类具有四值互相关的二元m 序 列的d 采样，同时他们指出，还存在一些采样，它们的互相关函数取值个数较少， 如四值至六值等，有待从理论上给予证明 对于整数n = 2 m ，关于周期长度为2 n 一1 与2 m l g j m 序列之间的互相关函 数的研究成果主要如下： od = 牮，相关函数取值为三值，见文献【5 6 】； od ( 2 蠡+ 1 ) 兰2 i ( m o d2 m 一1 ) ，其中m 是奇数，且( 后，m ) = 1 此时相关函数取 值为三值，上一采样因子包含在其中，见文献【5 7 】； d = 喾等，其中n = 6 k ，相关函数取值为四值，见文献 5 8 1 ； d = 豢昔，其中n = 2 k r ，后为奇数这是上一采样因子的推广情况它的相 关函数取值为四值，见文献【5 9 1 。1 3 湖北大学硕士学位论文 3 3 一类新的具有四值相关的m 序列采样 在这一节中，对于正整数n = 2 m ，我们讨论特征2 上周期长度分别为2 ”一 1 与2 m 一1 的m 序列的互相关性在计算机的帮助下，对于这类m 序列的相关性， 我们找到了一类新的采样因子d = ( 2 m + 1 ) 5 ，并证明了它们的互相关函数取值 为四值，而且完全确定了其相关值分布 令f 2 。是含有2 n 个元素的有限域，且f ；。= 醍n o ) 设n = 2 m 并且o t 是f 2 n 的 一个本原元，其中仇是一个正整数于是，p = a 2 “+ 1 是砸2 。的一个本原元 设f s t 】- 是一个周期为2 n 一1 的m 序列， 锄 是一个周期为2 m l 的m 序列， 由命题3 2 可知， s 。) 和【毗 可分别定义为如下： 8 t = t r ? ( a 。) ，0 t 2 n 一1 ， u t = n ? ( p ) ，0st 2 ”一1 于是由定义2 7 可知，两个m 序列 s t ) 和 仇) = 乱出) 在移位r 处的互相关 函数为 q ( r ) = ( 一1 ) 聃”， ( 3 1 ) t = 0 其d f l g c d ( d ，2 m 一1 ) = 1 且0 r 2 m 一1 【5 6 1 利用m 一序列的迹函数表示，n e s s 和h e l l e s e t h 【5 6 】已经证明了 q ( 7 ) + 1 ：0 丁 1 ，相关函 数g 么( 7 ) 取值为四值，并且它们的相关分布也完全确定下来具体细节见参见文 献 1 5 1 紧随其后，h e l l e s e t h 和k h o l o s h a 也得到部分相关结果，但它们的证明比较 复杂，见文献 6 2 1 2 3 一 斗尥 0 严尸 n百翌2 卜q q 矗+ + “尬尬 ，、【 l ，m 一 2 h 一，少5 1 ： ： 蚴讹啦 + 一 池 似m 必 + + + 螈尥尥 一 + 一 尥 湖北大学硕士学位论文 4 一类p - 元低相关序列集的构造 利用m 序列的相关性是构造序列集的一个比较常用的方法在上一章对m 序列的相关性的讨论中我们已经提到，m 序列的相关性与k a s a m i 序列集和g o l d 序 列集之间存在着紧密的联系基于m 序列的相关性以及对其它一些非线性函数 的研究 6 3 - 7 3 ，序列集的构造都有所发展小集合的k a s a m i 序列是推广较为成功 的一类序列集之一小集合的k a s a m i 序列集相对于w e l c h 界【8 】具有最优的低相关 性，但是它的集合容量相对较小为了增加序列集的集合容量，人们将小集合 的k a s a m i 序列集进行推广，构造出了大集合的k a s a m i 序列集，这种推广在增加 序列集的集合容量的同时使得序列集的相关性稍微偏离了最优更进一步地， 2 0 0 7 年7 月，曾祥勇，l i u 和胡磊将大集合的k a s a m i 序列集推广到一般，构造出了广 义的大集合的k a s a m i 序列集 i l l ，并且它与大集合的k a s a m i 序列集具有相同的集 合容量和互相关值分布 相对于小集合的二元k a s a m i 序列集，非二元的小集合k a s a m i 序列集已经构 造出来 7 4 】那么，对于广义的或者大集合的二元k a s a m i 序列集，与之对应的非 二元的序列集是否对于某些参数而存在? 由于在奇特征域上，对于任意的奇素 数p 和非负整数k ，始终有2i 矿+ 1 因此，我们不能如同特征2 上那样去研究奇特征 域上不同周期长度的非二元m 序列的互相关性否则，我们便不能直接利用二次 型理论这一工具基于此，在这一章中，我们仍然利用二次型理论的相关工具，考 虑广义的或者大集合的二元k a s a m i 序列集对应在奇特征域上的情形即考虑非线 性函数 ，y ，6 ( z ) = t r ? 2 ( ，y z p 7 2 + 1 ) - i - t r ( 6 x p k + 1 ) ， ( 4 一1 ) 其中7 b z ，6 f 矿，1 k 礼且七n 2 对于不同的参数p 和k ，与等 式( 4 1 ) 中的二次型，y ，6 ( z ) 相关的研究见文献【1 l ，3 0 ，7 5 ，7 6 ，7 7 ，7 8 在这一章中，我们始终假设素数p 是奇数，且礼= 2 m 4 通过计算机搜索，我 们可寻得一类参数后的值，具体条件如下 g c d ( n 2 ，k ) = g c d ( n 2 一k ，2 k ) = d 是奇数 ( 4 2 ) 对于满足这一条件的七，我们通过二次型1 ，6 ( z ) - i 构造出较好性质的序列集 注意到当石取遍时，矿 也取遍跏，并且有 丁r ? ( 6 z 矿+ 1 ) = t r ? ( 5 f “矿山+ 1 ) ， 不失般性，不妨设整数k 满足条件1 k n 2 2 4 4 一类p 一元低相关序列集的构造 4 1 一类二次型的秩分布 在这一节中我们讨论由式子( 4 1 ) 所定义的二次型1 ，6 ( z ) 的秩分布，其中7 0 或者5 0 二次型的秩在第二章中已作简单的介绍，要确定奇特征上- - 次 型7 ，6 0 ) 的秩，通过分析关于变量z 的方程n 7 ，6 0 + z ) = 1 1 7 ，6 ( z ) ，问题最终归结为 有限域上一类方程的解的问题 4 1 1 关于有限域上