论文部分内容阅读
伪随机序列在通信系统中起着极其重要的作用。所谓伪随机序列是指具有某些随机特性且结构又是可以预先确定,能重复产生和复制的序列。例如,在CDMA(Code Division Multiple Access)系统中,就需要大量具有良好相关性(即:序列集的自相关和互相关值与序列的周期之比越小越好)的序列集。近三十年来,寻找具有良好相关性的序列及序列集一直是通信领域广泛研究的问题之一。如何基于短序列,利用轻量级算法产生这样具有良好相关性的长序列是本文的研究重点。 本文从研究向量深度(复杂度)出发,首先利用循环矩阵讨论了有限域Fq上n维向量s的深度分布,构造了一类终归周期序列{(L?1)i(s)}i≥0(其中,L是向量的循环左移算子);其次通过研究此类序列的终归周期的界以及最小终归周期分布,提出了一个在n维向量空间中以很高的概率,通过循环差分算子,基于n长短序列(即:n维向量)生成长序列的轻量级算法;进而利用交织技术,得到了大量具有良好相关性的序列。主要创新之处有以下三点: 第一,有限域上的向量导数是关于序列运算的一个著名算子,在博弈论、通信理论和密码学中,被广泛用于研究序列的复杂度。Etzion[29,46]利用向量导数研究了序列的线性复杂度,开创性地提出了向量深度的概念,认为一个长度为2r的二元向量的深度等于其对应周期序列的线性复杂度。本文称此深度为“第一类深度”。Luo、Fu和Wei[88]深入研究了线性码的第一类深度分布。文献[46]提到Roth利用序列生成多项式的因式分解也研究了序列的线性复杂度,对于长度为2r的二元向量的深度提出了一个与Etzion的深度概念等价的描述。本文称之为“第二类深度”。随后,Mitchell[92]利用循环差分算子(L?1)将Etzion的向量深度概念推广到无限序列,指出具有有限深度的无限长二元序列之集等于周期形如2i(i为任意非负整数)的序列之集。本文称之为“第三类深度”。对于一个有限域Fq上周期为n的序列来说,当n=pr时,其中p是有限域Fq的特征,此序列的上述三类深度都等于它的线性复杂度[20]。本文给出了有限域上n维向量空间的第二类深度和第三类深度分布,详见第三章。 第二,在通信系统的相关应用中,有两个普遍关心的问题,一是如何利用轻量级计算生成长周期序列,二是如何完成序列盲周期检测同步。首先,生成长周期序列的方法有很多,除了基于LFSR(Left Feedback Shift Register)的构造方法外[63],还有大量基于不同数学理论的构造方法,如基于割园[36,38–40]、有限域[30,54,76,96,103,111]和函数域[124–126,128]等的构造方法。这两类方法各有优缺点。一般来说,前者易于实现但不易分析序列的性质;后者则相反。综合两者的优势构造随机序列的方法是实际应用中所需要的[57–59,62]。本文首次从高概率生成序列的角度,基于有限域上具有无限第三类深度的向量,通过轻量级的循环差分算子,给出了一个生成长周期序列的解决方案。当q=2且n=2r?1时,此解决方案的计算复杂度为Θ(n2),且LFSR的GE(GateEquipments)个数为n。其次,在通信实践中,序列的盲同步是必须的但却不易实现。特别是,周期序列有可能因为设备切换和噪音干扰,变成了终归周期序列,这就更加大了同步的困难。本文给出了一类循环差分序列{(L?1)i(s)}i≥0作为此问题的一个解决方案,不仅详细研究了此类序列的终归周期的上界和最小终归周期的计算公式,而且对于周期为pr?1的基序列s,还给出了基于其循环差分序列最小终归周期的分布。详见第四章。 第三,构造具有良好相关性的序列是通信领域近30年来一直关心的问题之一。许多学者提出了大量基于m-序列及其采样序列的构造方法[78,82,86,112,116]。Gong[57,62]首次利用交织技术基于两个2级自相关序列构造了低相关性的序列及序列集。本文通过刻画循环差分算子(L?1)i(i≥0)的矩阵结构,利用交织技术基于一个2级自相关序列s的循环差分序列{(L?1)i(s)}i≥0构造了一类具有良好相关性的序列。其构造方法只使用了逻辑异或运算XOR,且运算复杂度为Θ(N),其中N是新构造序列的周期,因而是轻量级的。详见第五章。