严格达到Welch界的最优三元序列集_叶智钒.pdf

中国科学:数学2023年第53卷第2期:395406SCIENTIA SINICA Mathematica论文英文引用格式:Ye Z F,Zhou Z C,Zhang S Y,et al.Optimal ternary sequence sets rigorously achieving the Welch bound(inChinese).Sci Sin Math,2023,53:395406,doi:10.1360/SSM-2022-0077c 2022中国科学 杂志社严格达到Welch界的最优三元序列集献给朱烈教授80华诞叶智钒1,周正春1,张胜元2,唐小虎31.西南交通大学数学学院,成都 611756;2.福建师范大学数学与统计学院,福州 350117;3.西南交通大学信息科学与技术学院,成都 611756E-mail:,,,收稿日期:2022-04-29;接受日期:2022-06-24;网络出版日期:2022-08-23;*通信作者国家自然科学基金(批准号:62071397 和 62131016)资助项目摘要序列是复数域上的有限维离散信号,因其抗干扰、稳定和易实现等特点,被广泛应用于通信、雷达、声呐和信息安全中,用于实现同步、多址随机接入、信道估计、测距、抗干扰和数字水印等需求.序列与循环Hadamard矩阵、差集(族)、紧框架、无偏基和循环码等数学对象之间存在密切的联系.构造相关性达到或逼近理论界的序列一直是序列编码领域关注的核心问题.本文基于semi-bent函数和差集,构造一类具有最优相关性的三元序列集(序列元素取值为0和1).这是自1974年Welch界提出以来,第一类严格达到Welch界的最优序列集.相比二元序列集(序列元素取值为1),新序列集更适用于超宽带通信、数字水印和频谱受限等应用场景;相比已有基于bent函数的三元序列集(相关性渐近达到2倍Welch界),新序列集具有更好的相关性.关键词最优三元序列集Welch 界semi-bent 函数超宽带通信数字水印频谱受限MSC(2020)主题分类11B50,62H20,68P30,94A551引言低相关序列(也称为离散信号)已被广泛应用于无线通信、雷达探测和信息安全等众多领域(参见文献8,11).例如,在5G大规模随机接入中,为使基站能正确地检测接入用户和估计同步时间,所使用的前导序列应具有较低的自相关和互相关特性24.在雷达探测中,基于低相关特性序列的低旁瓣相位编码类波形,在显著提升雷达对弱小目标探测能力的同时,兼具良好的抗干扰能力27.在信息安全中,低相关序列可用于设计流密码中的伪随机密钥流11和实现数字水印技术33.低相关序列与循环Hadamard矩阵、差集(族)、紧框架、无偏基和循环码等数学对象之间存在密切的联系(参见文献11).低相关序列的探索起始于20世纪50年代Golomb10和Zierler38关于最大长度线性反馈移叶智钒等:严格达到 Welch 界的最优三元序列集位寄存器序列(m-序列)的研究.在理想情况下,每个序列的自相关函数应该是一个冲激函数,即除零时延外,其值应处处为0;序列集中每对序列的互相关函数值应该处处为0.然而,著名的Welch界35表明这样的理想序列集是不存在的.该理论界以序列的长度、数目和能量为参数给出了序列集最大相关值的理论下界.构造相关性达到或逼近理论界的序列集一直是序列编码领域关注的核心课题之一.基于m序列及其采样序列,Kasami16构造了首类渐近达到Welch界的二元序列集(序列元素取值为1).Olsen等23利用bent函数改进了Kasami序列集的平衡性,设计了渐近达到Welch界的平衡二元序列集.之后,No和Kumar22基于有限域的扩域理论提升了Kasami序列集的线性复杂度,设计了具有高线性复杂度且渐近达到Welch界的二元序列集.这3类序列具有相同的长度(长度为2n1,n为偶数)、序列数目和相关性.1996年,Udaya和Siddiqi34构造了具有偶数长度的渐近达到Welch界的二元序列集,序列长度为2(2n 1),n为奇数.2007年,Tang等32对Udaya和Siddiqi的构造进行了改进,在保持相关性的前提下,成倍增加了序列集的容量.除了二元序列集,学术界还构造了一批渐近达到Welch界的多相序列集(序列中的元素在复平面单位圆盘上取值),如Kumar-Moreno序列集19、Family A,D,U3,29,31、Jang-Kim-No-Helleseth序列集15等.上述序列集均只能渐近达到Welch界.据作者所知,目前还没有严格达到Welch界的最优序列集.此外,上述序列集均为幺模序列集,即序列中每个元素都是模长为1的复数.在传统的无线通信和雷达感知系统中,幺模序列有利于提升发射端功率放大器的效率37.然而,随着现代无线通信和雷达的不断演进,传统的幺模序列集已不适用于一些新型应用场景.例如,目前的无线电频谱(特别是6 GHz以下的频段)正变得越来越碎片化.在这种非连续频谱的场景中,需要设计含零(零表示当前子载波位置不可用)的低相关序列完成通信或感知的任务36.在数字水印中,需要在使用的序列中加入一些随机字符生成水印序列.文献28中的结果表明,通过选取二元序列的某些位置进行“打孔”(即将相应位置的元素设置为0),然后再在打孔的地方植入伪随机序列,可生成检测性能优良的水印序列,其核心是要确保对二元序列进行打孔后的三元序列具有低相关性.超宽带系统对设备的功耗和波形的发射功率有着极高的要求,为了能够实现一定距离的数据传输和目标探测,超宽带设备通常在一段连续的工作时间内间隔发射集中的脉冲波形.在现行的超宽带通信标准中,已将含零(零表示当前时刻不发射波形)的低相关序列作为超宽带设备的同步序列以及唤醒序列20.三元序列与组合设计中的常重矩阵具有紧密的联系.一个阶数为n、权重为k的常重矩阵W(n,k)=W是指集合1,0,1上满足WWH=kIn的n阶方阵,其中,In是n阶单位矩阵,WH是W的共轭转置1.特别地,若矩阵W的每一行都为第一行的循环移位,则称W是循环常重矩阵,记为CW(n,k).由循环常重矩阵的定义可知,一个循环的常重矩阵等价于一个完美(周期自相关函数旁瓣为0)的三元序列.1942年,Bose2利用仿射差集设计了一类(n,k)=(q2d+1 1q 1,q2d)的循环常重矩阵,其中q为奇素数幂,d为任意的正整数.1979年,Ipatov14利用m序列设计了长度为q2d+11q1、能量为q2d的完美三元序列.同年,Shedd和Sarwate26基于m序列及其采样序列设计了长度为22d+1、能量为22d的完美三元序列.1983年,Hoholdt和Justesen13基于差集推广了Shedd和Sarwate26的工作,即将q=2的情形推广到q=2a的情形,其中a为任意正整数.完美三元序列和循环常重矩阵的相关工作可参见文献1,18.在实际工程中,单条序列无法同时满足众多用户的需求,因此需要设计低相关三元序列集.Song等28通过对文献23中基于bent函数的二元序列进行打孔,构造了一类三元序列集,该序列集合的相关性只能渐近达到2倍Welch界.受Song等的工396中国科学:数学第 53 卷第 2 期作启发,本文基于semi-bent函数和差集,构造一类具有最优相关性的三元序列集(序列元素取值为0和1),这是自1974年Welch界提出以来,第一类严格达到Welch界的最优序列集.相比传统的二元序列集(序列元素取值为1),新序列集更适用于超宽带通信、数字水印和频谱受限等应用场景;相比Song等28构造的三元序列集,新序列集具有更好的相关性.本文余下内容结构如下:第2节介绍序列、布尔函数、差集的基本概念和性质.第3节提出基于布尔函数和差集构造三元序列集的一个一般化方法,并证明当布尔函数为满足一定条件的semi-bent函数时,构造方法可生成严格达到Welch界的最优三元序列集.最后,第4节对本文工作进行总结.2预备知识本节简要介绍序列的周期相关函数及其理论界、semi-bent函数和差集等概念.2.1序列的周期相关函数及Welch界设a=(a(0),a(1),.,a(N 1)和b=(b(0),b(1),.,b(N 1)是复数域上两条长度为N的序列(也称为离散信号),它们的(周期)互相关函数定义为Ra,b()=N1t=0a(t)b(t+),0 6 N,(2.1)其中,t+为模N加,表示复数的共轭.特别地,当a=b时,Ra,b()表示序列a的自相关函数,简记为Ra().序列a的能量定义为E=N1t=0|a(t)|2.设S是由K条长度为N、能量为E的复数序列组成的序列集,S的最大自相关函数值max(S)定义为max(S)=maxA(S),C(S),其中A(S)=max|Ra()|:a S,0|N,C(S)=max|Ra,b()|:a=b S,0 6|EK 1NK 1.(2.2)在一些实际应用中,为了工程实现简单,希望使用二元序列(序列元素取值为1)和三元序列(序列元素取值为0和1).由于二元(或三元)序列集的自相关和互相关函数值都为整数,所以(2.2)中的Welch界等价于max(S)EK 1NK 1.(2.3)若(2.2)或(2.3)中的等号成立,则称S为(严格)达到Welch界的最优序列集;若等号不成立而limNmax(S)opt=1,则称S为渐近达到Welch界的序列集,其中opt表示(2.2)中右边的理论下界.397叶智钒等:严格达到 Welch 界的最优三元序列集2.2Walsh谱与semi-bent函数设F2m表示包含2m个元素的有限域.设m=e,有限域F2m到其子域F2e的迹函数定义为Trme(x)=1i=0 x2ei,x F2m.设f(x)是有限域F2m的布尔函数(即从F2m到F2的函数),f(x)在点处的Walsh谱定义为f()=12m/2xF2m(1)f(x)+Trm1(x),F2m.若对于任意 F2m,有f()1,则称f为bent函数;若对于任意 F2m,f()0,2,则称f为semi-bent函数.Bent函数是一类具有最大非线性度的布尔函数,由Rothaus25于1976年提出.由于bent函数只有当变元为偶数时才存在,Canteaut等5对bent函数的概念进行了推广,提出了semi-bent函数的概念.Bent函数和semi-bent函数在组合设计、信息安全和编码理论中具有重要应用.有关这两类函数的更多信息,可参见布尔函数的专著21.2.3差集设(G,+)是阶为v的有限Abel群,H是G的k阶子群,若对于G中任意一个非零元g,都有个有序对(h1,h2)(h1,h2 H)使得g=h1 h2,则称H是G中参数为(v,k,)的差集7.设N=2n 1,ZN表示模N整数剩余类环,利用迹函数定义H=t ZN:Trn1(t)=0,(2.4)其中为有限域F2n的本原元.容易验证H是群(ZN,+)中参数为(2n 1,2n1 1,2n2 1)的差集12.3最优三元序列集本节将基于semi-bent函数和差集构造一类三元序列集,并证明构造的序列集严格达到Welch界.首先,固定后面要用到的一些符号:n=2m,其中m为正整数;N=2n 1,T=2m+1;为有限域F2n的本原元;=T mini,j:Ti+Tj=1,1 6 i,j 6 2m 2 0;F2n F2m.下面给出基于布尔函数构造三元序列集的一个一般化方法.构造3.1构造包括以下3步:步骤1选取F2n上的布尔函数f,生成函数集F=f:,其中f(x)=f(Trnm(x)+Trn1(+)x),x F2n.(3.1)398中国科学:数学第 53 卷第 2 期步骤2基于函数集F,构造二元序列集Uf=uf=(uf(0),uf(1),.,uf(N 1):,其中uf(t)=(1)f(t),0 6 t 6 N 1.(3.2)步骤3利用(2.4)中的差集H对Uf中的序列进行“打孔”,生成三元序列集Sf=sf=(sf(0),sf(1),.,sf(N 1