（应用数学专业论文）具有最优自相关度级数的二元序列.pdf

上海交通大学博士学位论文 具有最优自相关度级数的二元序列 摘要 近年来，二元( o 和1 ) 序列的构造成为了组合设计中的一个比较重要的 问题，有着重要的理论意义和实际应用背景具有较好的自相关度的二元 序列在通信及密码学领域有着广泛的应用到目前为止了，对于二元序列 的构造，已经有了一些很好的结果，但是并不完善在理论上，t w c u s i c k ， c d i n g ，a r e n v a l l 等人证明了与具有最优自相关度的二元序列对等的组合结构 是具有特定参数的差集或是几乎差集因此，在具有最优自相关度或最优 自相关度级数的二元序列的构造中，组合设计方法和代数方法占有极其重 要的地位，其中利用有限域上的分圆类，分圆数来构造二元序列是比较重 要的方法，许多研究者都利用它们来构造二元序列本文在前人的基础上， 对具有最优自相关度和最优自相关度级数的二元序列的结构，性质和构造 方法进行了研究，并构造一些新的具有最优自相关度级数的二元序列 本文的工作共分成五个部分 第一部分，我们主要概述了关于二元序列问题发展的起源，历史和研究 景和研究现状、采用的主要方法、面临的困难，并介绍了本文的主要工 作 第二部分，我们利用二元序列的自相关度函数和其支撑集合的差函数之 间的关系，利用有限域上的四阶分圆类、分圆数等组合设计中常用方法给 出了一些新的具有最优自相关度级数的平衡的二元序列 在第三部分和第四部分，我们利用二元序列的多项式表示对这些得到的 二元序列进行分析，进一步研究它们的多项式性质和它们相应的线性复杂 度 第五部分，我们尝试利用了差集的形式多项式定义和有限域上一类特殊 的分圆类，构造了一些新的几乎差集 中文摘要 数 关键词：差集；几乎差集；二元序列；最优自相关度；最优自相关度级 a b s t r a c t b i n a r ys e q u e n c e sw i t ho p t i m a l a u t o c o r r e l a t i o na n do p t i m a l a u t o c o r r e l a t i o nm a g n i t u d e a b s t r a c t t h ec o n s t r u c t i o no fb i n a r ys e q u e n c e sb e c o m ea ni m p o r t a n tp r o b - l e mw i t hg r e a tt h e o r e t i cs i g n i f i c a n c ea n ds t r o n ga p p l i c a t i o nb a c k g r o u d i nt h ef i e l do fd e s i g nt h e o r yi nr e c e n ty e a r s t h e r ea r es o m eg o o dr e s u l t s o ft h ec o n s t r u c t i o no ft h eb i n a r ys e q u e n c e s ，b u ti ti sn o tp e r f e c t t w c u s i c k ，c d i n g ，a r e n v a l lp r o v e dt h a tab i n a r ys e q u e n c ew i t ho p t i m a l m t o c o r r e l a t i o n 。l u a t o t i f f e r e n c es e to ra nd m o s td i f f e r e n c es e twithautocorrelatlonl se q u a lt oad 1 1 3 e r e n c es e to ra na i m o s td 1 1 i e r e n c es e t s p e c i a lp a r a m e t e r s t h e r e f o r e ，t h ec o m b i n a t o r i a la n da l g e b r a i cm e t h o d s a r ee f f i c i e n tf o rt h ec o n s t r u c t i o no fb i n a r ys e q u e n c e sw i t ho p t i m a la u - t o c o r r e l a t i o na n do p t i m a la u t o c o r r e l a t i o nm a g n i t u d e m a n yr e s e a c h e r s c o n s t r u c tt h eb i n a r ys e q u e n c e sw i t ho p t i m a la u t o c o r r e l a t i o na n do p - t i m a la u t o c o r r e l a t i o nm a g n i t u d eb yc y c l o t o m i cc l a s s e sa n dc y c l o t o m i c n u m b e r so faf i n i t ef i e l d t h i sd e s s e r t a t i o ni n v e s t i g a t e st h es t r u c t u r e ， t h ep r o p e r t ya n dt h ec o n s t r u c t i o nm e t h o do fb i n a r ys e q u e n c e sw i t ho p - t i m a la u t o c o r r e l a t i o na n do p t i m a la u t o c o r r e l a t i o nm a g n i t u d e w ea l s o i n v e s t i g a t eb i n a r ys e q u e n c e sw i t ha n o t h e rd e f i n i t i o n t h i st h e s i si sd e v i d e di n t of i v ec h a p t e r s t h ef i r s tc h a p t e ri sd e v o t e dt ot h es u m m a r i z a t i o no ft h ed i s s e r t a - i i i d o c t o r a ld i s s e r t a t i o no fs h a n g h a jj i a ot o n gu n i v e r s i t y t i o n w ed i s s c u s st h ed e v e l o p m e n to ft h es u b j e c t ，i n c l u d i n gt h eh i s t o r y a n dc u r r e n ts i t u a t i o n so fi t ，m e t h o d su s e da n dd i f f i c u l t i e sf a c i n gu s w e a l s og i v et h em a i nr e s u l t so ft h i st h e s i s i nt h es e c o n dc h a p t e r ，w ec o n s t r u c ts o m ec l a s s e so fb i n a r ys e q u e n c e s w i t ho p t i m a la u t o c o r r e l a t i o nm a g i n a t u d eb yt h ed i f f e r e n c ef u n c t i o no f t h es e ta n dt h ec y c l o t o m i cc l a s s e sa n dt h ec y c l o t o m i cn u m b e r so fo r d e r 4o v e rf i n i t ef i e l d s i nt h et h i r dc h a p t e ra n dt h ef o u r t hc h a p t e r ，w ea n a l y z et h ep o l y n o - m i a lp r o p e r t i e sa n dl i n e a rc o m p l e x i t yb yt h ep o l y n o m i a lr e p r e s e n t a t i o n o ft h es e q u e n c e s i nt h ef i f t hc h a p t e r ，u s i n gas p e c i a lt y p eo fc y c l o t o m i cc l a s s e so v e r f i n i t ef i e l d s ，w ec o n s t r u c t i o ns o m ec l a s s e so fa l m o s td i f f e r e n c ef a m i l i e s k e y w o r d s ：d i f f e r e n c es e t ，a l m o s td i f f e r e n c es e t ，b i n a r ys e q u e n c e ，o p - t i m a la u t o c o r r e l a t i o n ，o p t i m a la u t o c o r r e l a t i o nm a g n i t u d e i v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果除论文中已经注明引用的内容外，本论文不包含 任何其他个人或者集体已经发表或撰写过的作品成果对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本 声明的法律结果由本人承担 学位论文作者签名：孙园 日期：2 0 0 8 年6 月6 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印和电子版，允许论文被查 阅和借阅本人授权上海交通大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和 汇编本学位论文 保密口，在一年解密后适用本授权书 本学位论文属于 不保密阢 ( 请在以上方框内打鬟 并) 学位论文作者签名：孙园指导教师签名：沈灏 日期：2 0 0 8 年6 月6 日日期：2 0 0 8 年6 月6 日 第一章绪论 1 1研究背景 由0 和1 所组成的序列被称为二元序列，二元序列在很多地方有着很重要的应 用，比如说数据通信，雷达和测量等领域早在1 9 7 7 年的时候，l e m p l e ，c o h n 和 e a s t m a n 等人 4 3 】就对二元序列的自相关度进行了研究，并给出了具有最优自相关度 的二元序列的判断准则。近年来，又有很多研究者对具有最优自相关度的二元序列进 行了研究，如 1 3 ，1 4 ，4 9 】等 首先，我们来介绍一些关于二元序列的基本知识 ( 一) 二元序列 设口为一个正整数记一个长为v 的二元序列为 s = s ( o ) ，s ( 1 ) ，s ( 2 ) ，8 ( v 一1 ) 】1 0 ，1 ) 我们用s ( 亡) 表示序列s 的第t + 1 位，其中t = 0 ，1 ，2 ，秒一1 用= s ，s ，s ，表示长为钐的二元序列s 的周期延续 定义1 1 1 记d = 矧s ( 亡) = 1 ，0 t 可一1 ) 为邑的一个子集，称d 为二元序 列的支撑集合， 若移兰0 ( r o o d 2 ) 并且二元序列8 满足 i 芒i s ) = 1 ，0 t 口一1 ) i = i 亡i s ) = 0 ，0 t 口一1 ) i 则称二元序列8 为平衡序列 若移三l ( m o d 2 ) 并且二元序列8 满足 怖( 舌) = 1 ，o 亡移一1 ) i = 孚 则称二元序列s 为几乎平衡序列 口 第一章 绪论 定义1 1 2 二元序列8 的周期自相关度函数( p e r o d i ca u t o c o r r e l a t i o nf u n c t i o n ) 为 t ，一1 ( u ) = ( 一1 ) 8 舢删巾“力 t = o 其中= 0 ，1 ，2 ，口一1 当u = 0 时，妒。( 0 ) = u 二元序列的周期自相关度函数通 常简称为二元序列的自相关度 口 若长为口为- - - 元：序列定义为s = 1 8 ( 0 ) ，s ( 1 ) ，s ( 2 ) ，8 ( v 一1 ) ) 一1 ，1 ) 口，则二 元序列的自相关度函数也相应地更改如下： v - 1 妒。( u ) = s ( 亡+ um o d 移) 木s ( ) t = o 其中u = 0 ，1 ，2 ，钞一1 当u = 0 时，妒。( 0 ) = 钉 通常，长为v 的二元序列定义都是定义在_ o ，1 ) 上为了构造与计算的方便，我 们在下面也采用定义在 o ，1 】上的二元序列 定义1 1 3 二元序列s 的值因子( m e r i tf a c t o r ) 为 m f ：塑 佛( u )- r s 一， u = 1 为了简化具有不同长度的二元序列8 之间的比较，在值因子的基础上，人们又给 出了渐近值因子( a s y m p t o t i cm e r i tf a c t o r ) 的概念 定义1 1 4 二元序列8 的渐近值因子( a s y m p t o t i cm e r i tf a c t o r ) 为 m 凡：可l i m m f u 定义1 1 5 二元序列8 的非负周期自相关度函数( n e g a p e r i o d i ca u t o c o r r e l a t i o n f u n c t i o n ) 为 其中u = 0 ，1 ，2 ，钉一1 2 半 + 0“ 一 删u 蚪 “ d 一 渤 = 只 上海交通大学博士学位论文 2 0 0 1 年，d i n g 等人证明了与具有最优自相关度的二元序列对等的组合设计结构 是具有特殊参数的几乎差集或差集，引发了研究者对几乎差集的极大兴趣 ( 二) 差集与几乎差集 定义1 1 6z v = o ，1 ，2 ，v - l 表示模口的剩余类加群，彩= z a o d 是磊 的一个k 元子集，即l d i = k d 是磊的一个( 口，k ，a ) 差集，若( = - u l x ，y d ，z 可 恰好含有磊中的每个非零元a 次 口 由定义我们很容易得出，若d 是磊的一个( 口，k ，入) 差集，则有下式 k ( k 一1 ) = a ( v 一1 ) 成立 定义1 1 7d 是乙的一个( v ，k ，入，t ) 几乎差集，若 z 一i z ，y d ，x 可) 含有 乙中的t 个非零元恰好入次，磊中的另外剩下的钐一1 一t 个非零元恰好入+ 1 次 口 由定义很容易得出，若d 是磊的一个( v ，k ，a ，t ) 几乎差集，则有下式 k ( k 一1 ) = ( 入+ 1 ) ( 钉一1 一t ) + a t 成立 显然，若在上面几乎差集的定义中取t = 影一1 ，我们可观察到差集只是几乎差集 的特殊情形 定理1 1 1 4 1d 是磊中的参数为( t 7 ，k ，入，t ) 的几乎差集当且仅当它的补d + = 磊d 是参数为( 可，口一k ，口一2 七+ a ，t ) 的几乎差集 关于几乎差集研究已经成为诸多文献研究中的一个中心问题，可以参考文献 1 1 ， 1 3 ，1 4 ，9 0 】 对二元序列的构造问题研究推动了几乎差集的研究我们可以利用二元序列与几 乎差集的等价关系，通过构造差集，几乎差集或另一类型的差集合来构造二元序列 3 第一章绪论 若当u = 1 ，2 ， 一1 时，二元序列8 的自相关度仍) = 0 ，则二元序列8 被 称为完美序列在实际通信过程中 1 6 1 ，当接收方收到信号( 二元序列) 后用自相关度 来提取接收到的二元序列的相关信息通常，接收方都希望二元序列的自相关度为0 但是到目前为止，我们只是找到了一个长为4 的完美序列8 = 0 0 0 1 那么，相对于完 美的序列，人们开始寻找具有最优自相关度的二元序列 1 9 7 7 年，l e m p l e ，c o h n 和e a s t m a n 4 3 】证明了以下结论：对于具有最优自相关 度的二元序列8 的自相关度要满足以下条件s 1 ) s 至少有两个不同的自相关度 2 ) 任意两个自相关度的差值被4 整除 定义1 1 8 对于一个长为v 的二元序列， ( 1 ) 当口三0 ( m o d 4 ) 时，若二元序列8 具有自相关度 可，0 ，4 ) 或_ 口，0 ，一4 ) ，则称 其具有最优自相关度 ( 2 ) 当v 三l ( m o d 4 ) 时，若二元序列8 具有自相关度 ，1 ，一3 ) ，则称其具有最优 自相关度 ( 3 ) 当钉兰2 ( r o o d 4 ) 时，若二元序列8 具有自相关度如，2 ，一2 ) ，则称其具有最优 自相关度 ( 4 ) 当 兰3 ( r o o d 4 ) 时，若二元序列8 具有自相关度 口，- 1 ，则称其具有最优自 相关度 到目前为止，已知的具有最优相关度的偶长的二元序列有如下几类： 1 1 9 7 7 年，l e m p l e ，c o h n 和e a s t m a n 4 3 】构造了一些长为口= 矿一1 的二元序 列，其中p 是一个奇素数，i n 是一个整数 2 2 0 0 1 年，j 一s n o 等人 6 5 】利用多项式( 名+ 1 ) d + a z d + b 给出了一类长为 矿一1 的二元序列，其中p 是一个奇素数，m 是一个整数 3 2 0 0 1 年，d i n g ，h e l l e s e t h 和m a r t i n s e n 1 3 】利用有限域上的分圆类与分圆数对 4 上海交通大学博士学位论文 p 兰5 ( m o d 8 ) 的素数构造了长为劬的二元序列 4 2 0 0 1 年，a r a s u ，d i n g ，h e l l e s e t h ，k u m a r 和m a r t i n s o n 1 4 】对于口三0 ( r o o d 4 ) ， 利用已知的循环差集，构造了四类几乎差集这四类几乎差集对应了四类互不等价的 具有最优自相关度的二元序列 对于移兰0 ( m o d 4 ) ，具有自相关度v ，0 ，4 ) 或 口，0 ，- 4 的二元序列是最优的二 元序列，是源于1 9 7 7 年l e m p l e ，c o h n 和e a s t m a n 在【4 3 】中给出的最优自相关度二 元序列的判断准则对于具有自相关度为 ) o ，士4 ) o ) ，我们从绝对值的观 点来看，这些二元序列也应是级数最优的 到目前为止，已知的长为口三0 ( r o o d4 ) 的具有最优自相关度级数的偶长的二元序 列有以下几类： 1 2 0 0 0 年，由l f i k e 给出长为p m 一1 的二元广义s i d e l n i k o v 序列，其中p 是一 个奇素数，i l l 是一个正整数 2 将一个长为p 3 的l e g e n d r e 序列的第一位置的0 改为1 ，得到的序列通常被记 为己1 ，由长为4 的序列8 = ( 1 ，1 ，1 ，- 1 ) 与它做乘得到一个长为4 船二元序列，其结果 记为n ( l 1 ，4 ) = ( l 1 ，l 1 ，l 1 ，- l 1 ) ，其中p 三3 ( r o o d 4 ) 3 将一个m 一序列m 与8 = ( 1 ，1 ，l ，一1 ) 做乘积得到了长为4 ( 2 m 一1 ) 的二元序 列n ( m ，4 ) = ( m ，m ，m ，一m ) 4 2 0 0 6 年，n a m y u l y u 和g u a n gg o n g s 7 利用g o n g 在 2 8 2 9 】中的构造 序列的迭代方法，给出了长为移= 4 ( 2 m 一1 ) 的序列的迭代构造，其中m 是一个大于 4 的偶数 1 2本文主要结果 在第二章中，当p 三5m o d8 时，我们利用a f ( p ) 上4 阶分圆类和4 阶分圆数， 构造了平衡的长为4 p 的二元序列 5 第一章 绪论 定理2 3 1 令p = 4 f + 1 = x 2 + 4 y 2 为个奇素数，其中，是一个奇数，l y l = 1 若 ( z ，m ，n ，k ) ( o ，1 ，2 ，3 ) ，( 0 ，3 ，2 ，1 ) ，( 2 ，3 ，0 ，1 ) ，( 1 ，o ，3 ，2 ) ，( 1 ，2 ，3 ，o ) ，( 2 ，1 ，o ，3 ) ，( 3 ，o ，1 ，2 ) ， ( 3 ，2 ，1 ，o ) ) ，g o ，2 ) ， 1 ，3 ) ) ，则以 d = o ) x d , u d u i x d , u d k u 2 x d m u d u 3 x d z u d m u g x 0 z 4x 乙 为支撑集的平衡二元序列8 具有最优自相关度级数 - 4 ，0 ，4 ) 然后，我们得到上述几乎平衡的二元序列的渐近值因子为 定理2 3 2 定理2 3 1 中构造的平衡二元序列s 的渐近值因子为m 民= 兰，其 中口= 幼 接下来，在第三章中，我们利用上述二元序列8 的多项式表示将8 的周期延续否 分解成两个不同二元序列之和，得到如下结果。 定理3 2 1 设二元序列8 以 d = _ o ，2 】x o 】u o 】xc ou 1 】xau 2 ) qu 3 ) x 岛 为支撑集合，则= ( s ，8 ，8 ，) 可以分解成为一个周期为2 的二元序列孑= ( i o ) 与一个周期为v = 卸的二元序列= ( 8 ，8 ，8 ，) 之和，其中8 以 o ，x 岛u 1 ) xqu 2 ) x 岛u 3 ) xg 为支撑集合，c o = 彩c o ，岛= 露q 定理3 2 5 设二元序列8 以 d = 1 ，3 ) o ) u o ) xc ou 1 ) xc 1u 2 ) xqu 3 ) x 岛 为支撑集合，则= ( s ，s ，s ，) 可以分解成为一个周期为2 的二元序列孑= ( o i ) 与一个周期为t ，= 卸的二元序列争= ( 8 ，s ，) 之和，其中8 以 o ) xgu 1 ) x 西u _ 2 ) xqu 3 ) x 岛 6 上海交通大学博士学位论文 为支撑集合，西= 忍q ，岛= 彩q 并且我们得到一些新的具有最优相关度级数的二元序列 定理3 2 3 令- p = 4 f + i = x 2 + 4 y 2 为个奇素数，其中i 是个奇数，i y i = 1 若 ( f ，m ，n ，七) = ( o ，1 ，3 ，2 ) ，( o ，3 ，1 ，2 ) ，( 1 ，0 ，2 ，3 ) ，( 1 ，2 ，0 ，3 ) ，( 2 ，1 ，3 ，o ) ，( 2 ，3 ，1 ，o ) ，( 3 ，0 ，2 ，1 ) ， ( 3 ，2 ，0 ，1 ) ) ，则以 d = o ) x d z u d m 】- u 1 ) 现u d n ) u 2 ) d t u d u 3 d , ，u d k ) z 4 磊 为支撑集的长为口= 卸的二元序列8 具有最优自相关度级数 一4 ，0 ，4 ) 上述二元序列的值因子为 定理3 2 4 定理3 2 3 中得到的二元序列8 i t 的渐近值因子为m 如= 蠢 在第四章中，我们计算所构造的上述二元序列8 的线性复杂度，得到如下结果； 定理4 2 1 在定理2 3 1 中所构造的长为口= 4 p 二元序列8 的周期延续极小多 项式为m ( x ) = z 4 p - 2 + z 4 p + - t - z 2 - i - - 1 ，其次数为l = 卸一2 ，且 - 2 s ( 4 p - 2 ) = c i s 渤一2 一i ) ， i = 1 4 p 一2 s ( 4 p - 1 ) = 龟s ( 4 p 一1 一t ) i = l 定理4 2 2 在定理2 4 3 中所构造的长为 = 卸二元序列8 的周期延续极小多 项式为m ( x ) = z 4 p 一2 4 - x 4 p + + z 2 + 1 ，其次数为三= 4 p 一2 ，且 4 p 2 s ( 知一2 ) = c i 8 ( 卸一2 一i ) ， i = l 4 p 一2 8 ( 4 p 1 ) = 龟s 一1 一t ) i = 1 在最后一章中，根据几乎差集的多项式定义，我们利用有限域o f ( q 2 ) 上的一类 特殊的分圆类构造一些o f ( q 2 ) 上的非循环几乎差集 7 第二章具有最优自相关度级数的二元序列 定理5 2 1 设q 是一个奇素数幂，则存在参数为( q 2 ，赳2 ，旦塑4 ，譬) 和参数为 ( 9 2 ，垃q - 广1 ) 2 ，正业4 墨，q 2 + 2 2 q - - 3 ，、的几乎差集 定理5 2 2 设q 是一个奇素数幂，则存在参数为( 口2 ，迎2 ，旦生4 ，华) 和参数为 ( 口2 ，幽兰2 吐，盘兰4 吐，q 2 + 2 2 q - - 3 ，、的几乎差集 8 第二章具有最优自相关度级数的二元序列 在本章中，我们先主要利用组合设计中常用的有限域上的分圆数，分圆类的构造 方法，去构造长为4 p 的具有最优相关度级数的二元序列，其中p 兰5 ( m o d 8 ) 是一个 奇素数然后在第三章和第四章中，我们用这些二元序列多项式表示来分析这些- - - ：元 序列的性质，并且计算线性复杂度 在此之前，我们做一些准备工作 2 1预备知识 设p 为一个奇素数，g f ( p ) 为一个p 阶的有限域g f + ) 是a f ( p ) 中的一个 阶为p 一1 的乘法群设q 为g f + ) 的一个生成元，则 g f ) = q 1 ，q 2 ，扩一，1 p 一1 = e f ，其中e ，都是大于1 的正整数 d 5 e = o r e 1 0 i 厂一1 ) 为g f + 仞) 的一个f 阶子群d 5 e 的陪集类为d 5 e ) = c l i d 5 e ) ，其中0 i e 一1 这 些d ：8 0 i e 一1 被称为g f ) 的e 阶分圆类g f + ) = u e 扛- - 0 1 碰e 对0 i ，歹e 一1 ，令 ( t ，歹) 。= l ( z ，可) l z 厦引，y 巧引，z + 1 = y l = i ( 磋8 + 1 ) n 巧8 i 则称( i ，歹) 。为e 阶分圆数当无需指明e 时，也常将唾。简记为d i ，将( 1 ，歹) 。简记为 ( t ，歹) 对于e 阶分圆数，有如下性质： 引理2 1 1 ( 1 )( i ，歹) = ( e im o de ，歹一ir o o de ) 口 第二章 具有最优自相关度级数的二元序列 c 2 ， c t ，歹，= 。+ ；m 。羔：；。m de ，喜三， ，一1 若，是偶数，蕾= 0 ，一1 若，是奇数，i = ； ，其它 f 一1 若j = 0 f若j 0 。、窖，、i ，一1 若j = 0 ( 5 )( i ，i + 歹) = 。 ” 江o i ，若j 0 特别地，当e = 4 时，p = 4 f + 1 是个奇素数，p 可以写成z 2 + 4 y 2 的形式， 其中z 三l ( m o d 4 ) ，y 的绝对值是唯一确定的，可的符号取决于有限域限g f ( p ) 中的 生成元o z 的选取四阶数至多有1 6 个值 当，为奇数时，四阶分圆数表为 其中 ( i ，j ) 0123 0 ( 0 , 0 )( o ，1 )( 0 , 2 )( 0 , 3 ) 1 ( 1 , 0 )( 1 , 0 )( 0 , 3 )( 0 , 1 ) 2 ( 0 , 0 )( 1 , 0 ) ( 0 , 0 )( 1 , 0 ) 3 ( 1 , 0 )( 0 , 3 )( o ，1 )( 1 , 0 ) ( 0 o ) = 学 ( o ，1 ) = p + 1 + r 2 x - 8 y ( 0 1 2 ) = 岩 ( 0 ，3 ) = 型等业 1 0 ，-_-lj l_l_，ij、-l 伽 铷 上海交通大学博士学位论文 ( 1 ，o ) = p - 面3 - 一2 x 当，为偶数时，四阶分圆数表为 ( i ，j ) 0123 0 ( 0 , 0 )( o ，1 )( 0 , 2 )( 0 , 3 ) 1 ( 0 ，1 )( 0 , 3 )( 1 , 2 )( 1 , 2 ) 2 ( 0 , 2 )( 1 , 2 ) ( 0 , 2 )( 1 , 2 ) 3 ( 0 , 3 )( 1 , 2 )( 1 , 2 )( o ，1 ) 兵甲 ( 0 0 ) _ 学 ( 0 ，1 ) = 坐等业 ( o ，2 ) = p - 面3 + 一2 x ( o ，3 ) = 坐等地 ( 1 ，2 ) = 号 例2 1 1p = 1 7 = 4 木4 + 1 = 1 2 + 4 木2 2 是一个奇素数，= 4 是一个偶数， z = 1 ，l y i = 2 当g f + ( r r ) 的生成元为q = 3 时，有限域c f ( 1 t ) 的分圆类为d o = ( 1 ，1 3 ，1 6 ，4 】- ， d 1 = 3 ，5 ，1 4 ，1 2 ) ，d 2 = 9 ，1 5 ，8 ，2 ) ，d 3 = 1 0 ，1 1 ，7 ，6 ) 由于，= 4 为偶数，由前面 的分类数表有 ( o ，1 ) ：i ( d o + 1 ) nd l l ：2 ：半 则y = 2 当g f ( 1 7 ) 的生成元为q = 6 时，有限域v f ( r r ) 分圆类为d o = 1 ，4 ，1 3 ，1 6 ) ， d l = 6 ，7 ，1 0 ，1 1 ) ，d 2 = 2 ，8 ，9 ，1 5 ，d 3 = 3 ，5 ，1 2 ，1 4 ) 由于，= 4 为偶数，由前面 第二章具有最优自相关度级数的二元序列 的分类数表有 则此时y = 一2 ( o ，1 ) = i ( d o + 1 ) n d 1 l = o = t 2 + y 2 2一个基本引理 我们还是记8 = s ( o ) ，s ( 1 ) ，s ( 2 ) ，s ( u 一1 ) ) o ，1 ) t ，为一个长为v 的二元序 列支撑集d = t l s ( t ) = 1 ，0 t u 一1 ) 为乙的一个子集合集合d 的差函数为 d d ( o j ) = l ( u + d ) nd iu 磊 t w c u s i c k ，c d i n g ，a r e n v a l l 等人证明了二元序列s 的自相关度与它的支撑 集d 的差函数有如下关系： 引理2 2 1 1 0 】对一个长为v 的二元序列s 有 妒。( 叫) = 一4 ( i d l 一如( u ) )u = 0 ，1 ，2 ，v 一1 证明：对于取定的u c 一1 ，8 。+ “，如l o d t ，卜“。2 二1 s s 。( t 亡+ + wm m 。o d d 可v ，) 一- s s ( 。亡t ，) ：- - - 0 1 。m 。d 2 ， l t l s ( t4 - u r o o dv ) 一8 ( t ) = o ) i = i t l s c t + ur o o d 口) = s ( t ) = o ) l4 - i t l s ( t + um o dv ) = 8 ( t ) = 1 ) = l ( d - t - u ) nd i - t - i ( 召d + u ) n ( 露d ) i = d d ( w ) + 秒一2 i d l + d d ( u ) = 秒一2 i d l + 2 如p ) 1 2 上海交通大学博士学位论文 t l s ( t + ur o o d 口) 一s ( t ) = 1 ( r o o d 2 ) = i t i n c t + ur o o d 钞) = 1 ，s 0 ) = o ) i + i t i n c t + u r o o dv ) = 0 ，s ( 亡) = 1 ) = i ( d + u ) n ( 召d ) l + l ( 召d + u ) nd l = 2 1 d i 一2 d n ( w ) 妒。c u ，= i 三三曼、。 d 。c u ，= 三三三曼。 2 3具有最优自相关度级数的二元序列的构造 在下面，我们总是假定p 三5 ( r o o d 8 ) 是一个奇素数，口= 卸由于( 4 ，p ) = 1 ， 我们根据中国剩余定理就有磊笺z 4 名，uh l ，u 2 ) ，其中u 1 兰w ( m o d 4 ) z 4 ， 1 3 j g - - $具有最优自相关度级数的二元序列 0 3 9 _ 三0 3 ( m o d p ) 磊，那么在乙上的构造等价于在z 4 磊我们在乙上的构造主要 基于中国剩余定理( c h i n e s er e m a i n d e rt h e o r e m ) 和有限域上的分圆类 现在，我们就开始构造长为 = 4 p 的具有最优自相关度级数的二元序列8 令 d = ( o ) c o ) u ( 1 ) a ) u ( 2 ) c 乞) u ( 3 ) c 3 ) u ( g o ) ) 邑， 其中g ( o i 3 ) 为任意两个不同的四阶分圆类的并，g 乙，l g l = 2 我们来计算集合d 的差函数如0 ，忱) 当( 0 3 1 ，0 3 2 ) = ( 0 ，0 ) 时， d d ( 0 ，o ) = i c l = i c o l + i g i + l q i + i g l4 - i g l = 8 ：c 字+ 2 = 2 p = 三 因此以d 为支撑集的二元序列8 是一个平衡序列 当u 1 0 ，u 2 = 0 时，d 的差函数为 印031=0 i g na i + l qn q i + i g ng i + i gn g 1 0 3 1 = 1 ，3 ，g = o ，2 ) ， 1 ，3 ) i 岛nq i + i gn 岛i + i q n g l + i 岛n 岛i + 1 0 3 1 = 1 ，3 ，g = o ，1 ) ， 1 ，2 ) ， 2 ，3 ) ， 3 ，o ) 2 1 c onc 2 i + 2 1 c 1nc 3 i + 2 0 3 1 = 2 ，g = o ，2 ) ， 1 ，3 ) 2 i c onc 2 i + 2 1 an 岛1 0 3 1 = 2 ，g = o ，1 ， 1 ，2 ， 2 ，3 ) ， 3 ，o 】l 我们的目标是构造自相关度为 口，0 ，士4 ) 的二元序列，即( 0 3 1 ，0 3 2 ) 【o ，士4 ， ( 0 3 1 ，0 3 2 ) ( 0 ，o ) 1 4 上海交通大学博士学位论文 根据引理2 2 1 ，集合d 差函数 d d ( 0 ) 1 ，w 2 ) 切一1 ，p ，p 4 - 1 ) 由( 1 ) 和( 2 ) 式得，岛，q ，q ，g 有以下几种可能的情形： 1 毋， ， 现，仇 ， ，玩) ， 皿，) ，g = o ，2 ) 或 1 ，3 ) 2 现，】- ，慨，) ， 皿，风) ， ，仇) ，g = o ，2 ) 或 1 ，3 ) 3 慨，队) ， 皿，如) ， 皿，d m ) ， ，仇) ，g = o ，2 ) 或 1 ，3 4 m ，队 ， ，仇) ， 皿， i ， 皿，) ，g = o ，2 ) 或 1 ，3 一 其中( 1 , m ，n ，k ) 是o ，1 ，2 ，3 的一个全排列，( 1 , m ，n ，k ) 通常被称为二元序列的定义集 口 我们在此只考虑情形1 ，其它的三种情形都与情形1 类似 令c o = d zud m ，g = 现u 仇，c 2 = d mud n ，岛= d tud m ，g = o ，2 f 劫一。 当忱= o 时，我们有d d ( 0 - j 1 ，0 ) = p 一1u 1 = 1 ，3 【p + 1 u 。：2 当0 w 2 磊时，w 2 可逆，我们有i ( g + 0 2 2 ) ng i = i p i l q + 1 ) nu i l q i ， 0 i ，歹3 d o ( u 1 ，w 2 ) = i ( c + ( u 1 ，u 2 ) ) nc l = ( i g o ) n ( i + w l ，a + w u ) l + a ) n ( g o ) - 卜l ，忱) ) 1 ) l = o 3 + l z g n t + u 1 ) ( g + 忱) i i - - 0 3 = ( i g o ) n ( i + 0 3 1 ，g + w 2 ) i + i ( z ，g ) n ( g o 】i + ( u 1 ，u 2 ) ) 1 ) l = o 3 + l an ( g u 。r o o d 4 + 忱) l i - - - - - 0 3 = ( 1 g o ) n0 + u 1 ，g + 忱) l + g ) n ( g o 卜卜( 0 2 1 ，忱) ) i ) 我们令 1 5 第二章具有最优自相关度级数的二元序列 3 l d ( 0 , ) 1 ，l 0 2 ) = ( i cx o ) n ( i + u 1 ，a + 忱) l + i ( i ，g ) f l ( gx o ) + ( o j l ，u 2 ) ) i ) i = 0 =i 一u 2 ) i - 1c 0 。i + i 一u 2 】nc 0 。一2 ( m 。d 4 ) i + i u 2 ) nc 0 。i m d ( o j l ，0 3 2 ) = + l u 2 ) nc 0 l + 2 ( m o d4 ) i 3 i 岈1 qn ( 岈1c ：f u 。( d 4 ) + 1 ) i = 0 贝0d d ( u 1 ，忱) = l d ( 0 3 1 ，u 2 ) + m d ( u 1 ，u 2 ) 此时由于忱可逆，假设u i l d h ( o h 3 ) m o ( w 1 ，u 2 ) 等于一些不同的四阶 分圆数的和 m 1 ) ( o ，o j 2 ) m d ( 1 ，u 2 ) m d ( 2 ，u 2 ) i ( d zu 口l 仇) n ( d fud m + u 2 ) i + l ( d lud k ) n ( d tud k + 忱) i i ( d mud n ) n ( d mud k + u 2 ) i + l ( 现ud k ) f l ( d tud i , + u 2 ) i 3 ( f + h ，l + h ) + 2 ( t + 危，m + h ) + ( j + h ，尼+ h ) + 2 ( m + h ，z + h ) + 3 ( m + h ，m + 九) + ( m + h ，钆+ h ) + ( 礼+ h ，m + h ) + ( 佗+ h ，n + h ) + ( 而+ h ，2 + h ) + ( 后+ h ，七+ h ) i ( 玩ud k ) n ( d lud r + u 2 ) l + i ( d mu 巩) u ( 觑ud 岛+ u 2 ) i + l ( d lud i m ) n ( 口i mud k + u 2 ) i + i ( d fud m ) f l ( d lud , n + u 2 ) i 2 ( 2 + h ，l + h ) + 2 ( t 十h ，m + h ) + ( f + h ，礼+ h ) + ( z + h ，七+ h ) + 3 ( m + h ，z + 九) + 2 ( m + h ，m + h ) + ( m + h ，七+ h ) + + h ，f + h ) + ( 佗+ h ，m + h ) + ( 七+ 忍，m + h ) + ( 后+ h ，1 7 , + h ) i ( d zud m )