一种具有大线性复杂度伪随机序列的构造

 本文提出了一种具有大线性复杂度、低相关性能和序列数目多的新伪随机序列构造方案.这种设计的关键之处在于利用移位序列分析法在理论上对相控序列进行改进,使用交织序列做基础序列代替原来的理想自相关序列,再利用具有理想自相关性的序列和相应的移位序列一起得到新伪随机序列.本文对其相关性能进行了分析,其最大值满足Welch界的要求;新序列的线性复杂度比现有的任意序列都要大;得到的新序列族中的序列有些是平衡的,族的数目和每一族中序列的数目都要多于现有的任意序列.     

A new family of binary pseudorandom sequences having optimalperiodic correlation properties and larger linear span

A collection of families of binary {0,1} pseudorandom sequences is introduced. Each sequence within a family has period N=2"-1, where n=2m is an even integer. There are 2^m sequences within a family, and the maximum overall (nontrivial) auto- and cross-correlation values equals 2^m+1. Thus, these sequences are optimal with respect to the Welch bound on the maximum correlation value. Each family contains a Gordon-Mills-Welch (GMW) sequence, and the collection of families includes as a special case the small set of Kasami sequences. The linear span of these sequences varies within a family but is always greater than or equal to the linear span of the GMW sequence contained within the family. Exact closed-form expressions for the linear span of each sequence are given. The balance properties of such families are evaluated, and a count of the number of distinct families of given period N that can be constructed is provided     

Optimal biphase sequences with large linear complexity derived fromsequences over Z4

New families of biphase sequences of size 2^r-1+1, r being a positive integer, are derived from families of interleaved maximal-length sequences over Z₄ of period 2(2^r-1). These sequences have applications in code-division spread-spectrum multiuser communication systems. The families satisfy the Sidelnikov bound with equality on &thetas;_max, which denotes the maximum magnitude of the periodic cross-correlation and out-of-phase autocorrelation values. One of the families satisfies the Welch bound on &thetas;_max with equality. The linear complexity and the period of all sequences are equal to r(r+3)/2 and 2(2 ^r-1), respectively, with an exception of the single m-sequence which has linear complexity r and period 2^r-1. Sequence imbalance and correlation distributions are also computed     

Bent-function sequences

In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parameternwithn=0 pmod{4}, the period of the sequences is2^{n}-1, the number of sequences in the set is2^{n/2}, and the cross/auto correlation function has three values with magnitudesleq 2^{n/2}+1. The equivalent linear span of the codes is bound above bysum_{i=1}^{n/4}left(stackrel{n}{i} right). These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing.     

一类由交织方式构造的二元ZCZ序列簇

2000年, Tang, Fan和Matsufuji给出(L,M,Zcz)-ZCZ序列簇的理论界为ZczL/M-1 。给定正整数n和L,本文给出一个交织ZCZ序列簇的构造算法,该算法由L条周期为L的正交序列簇生成一类(2n+1L,2L,2n-1)-ZCZ序列簇。若n2且4 |, 该类ZCZ序列簇中编号为奇数的序列与编号为偶数的序列在移位为时相关值为零。此外,选择不同的正交序列簇或不同的移位序列, 经构造算法可以生成不同的ZCZ序列簇。     

相控序列的改进——采用级连GMW序列 构造相控序列

本文介绍了一种新型伪随机序列－相控序列,相控序列具有线性复杂度很大,相关性好,序列平衡的优点.本文提出了对相控序列的改进,使用级连GMW序列代替原始定义中生成相控序列所需的GMW序列,并证明了这种改进的可行性.改进后的相控序列的线性复杂度进一步增大,族数增多但相关性和平衡性不变.     

Aperiodic correlation constraints on large binary sequence sets

The existence of binary sequences with specific aperiodic autocorrelation and cross correlation properties is investigated. Relationships are determined among the size of a sequence set, the length of the sequences n, the maximum autocorrelation sidelobe magnitudealpha, and the maximum cross correlation magnitudebeta. The principal result is the proof of the existence of sequence sets characterized by certain combinations ofn, alpha, andbeta. The proof makes use of a new lower bound to the expected size of sequence sets constructed according to an explicit "random coding" procedure. For largen, the sequence set size is controlled primarily by the cross correlation constraintbeta. Two consequences of the existence theorem are 1) a demonstration that large sequence sets exist for which the maximum autocorrelation sidelobe and cross correlation magnitudes vanish almost as fast as the inverse square root of the sequence length(l/sqrt{n}); 2)a new proof of the Gilbert bound of coding theory.     

Frequency-hopping code sequence designs having large linear span

In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p², p) and (p ⁿ, p^n/2+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p, whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method     

自相关性和线性复杂度的关系

自相关性和线性复杂度是衡量序列伪随机性质的两个独立的指标.针对周期为2^<em>n的伪随机序列,本文首次指出了自相关性和线性复杂度之间存在的一个关系.该关系可应用于以下两个方面:(1)由序列的线性复杂度来估计/确定序列的自相关函数值;(2)通过线性复杂度来检验给定序列族的互相关性质.进一步的,针对一类周期为2^<em>n的伪随机序列,我们指出这类序列的自相关函数值和线性复杂度以及k-错线性复杂度存在着关系.     

Low-correlation, large linear span sequences from function fields

A general method of generating families of binary sequences with low correlation as well as large linear span is presented. The lower bound on the linear span is on the order of the square root of the period of each sequence within the family. The design makes use of the theory of function fields. Two example applications of this method are presented in which the underlying function fields are the rational and elliptic function fields respectively.     

Optical orthogonal codes: design, analysis and applications

An optical orthogonal code (OOC) is a family of (0,1) sequences with good auto- and cross-correlation properties, i.e the autocorrelation of each sequence exhibits the `thumbtack' shape and the cross correlation between any two sequences remains low throughout. The use of optical orthogonal codes enables a large number of asynchronous users to transmit information efficiently and reliably. The thumbtack-shaped autocorrelation facilitates the detection of the desired signal, and low-profile cross correlation reduces interference from unwanted signals. Theoretical upper and lower bounds on the maximum possible size of OOCs are derived. Methods for the design and analysis of OOCs, using tools from projective geometry, the greedy algorithm, iterative constructions, algebraic coding theory, block design, and various other combinational disciplines, are discussed     

新的具有大线性复杂度的4值低相关序列集

设正整数n、m和r满足n=4m,r=2m-1 -1,基于Niho序列集和d型函数构造了一类4值低相关序列集S(r).该序列集中序列的数目为2n,相关函数的最大边峰值2(n+2)/2+1,序列的周期为2n-1.通过Key的方法,证明了该序列集中序列线性复杂度的F界为n(2n/2-3+2).该序列集与江文峰等人构造的序列集具有相同的相关函数值和序列数目,但拥有更大的线性复杂度.     

New construction for families of binary sequences with optimalcorrelation properties

We present a construction, in a closed form, for an optimal family of 2^m binary sequences of period 2^2m-1 with respect to Welch's (1974) bound, whenever there exists a balanced binary sequence of period 2^m-1 with ideal autocorrelation property using the trace function. This construction enables us to reinterpret a small set of Kasami and No (1988) sequences as a family constructed from m-sequences. New optimal families of binary sequences are constructed from the Legendre sequences of Mersenne prime period, Hall's sextic residue sequences, and miscellaneous sequences of unknown type. In addition, we enumerate the number of distinct families of binary sequences, which are constructed from a given binary sequence by this method     

Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences

Frequency hopping (FH) sequences have found wide applications in various modern FH spread-spectrum communications and radar systems. In FH spread-spectrum communications, the interference occurs when two distinct transmitters use the same frequency simultaneously. In order to evaluate the goodness of FH sequence design, the Hamming correlation function is used as an important measure. In this correspondence, by considering separately the maximum Hamming autocorrelation sidelobe H/sub a/, and the maximum Hamming cross correlation H/sub c/, several new lower bounds on the size p of the frequency slot set F, the sequence length L, the family size M, and correlation properties are established. The new periodic bounds include the known Lempel-Greenberger bounds as special case when M=2, and are tighter than the Seay bounds under certain conditions when M>2. Furthermore, the new bounds disclose more information on the relationship between the maximum autocorrelation sidelobe and the maximum cross correlation compared with the Lempel-Greenberger bounds and Seay bounds. Besides, the aperiodic FH bounds which have not yet been previously reported are also presented and discussed in this correspondence.     

具有几乎最优自相关幅度二元序列的构造

该文提出具有几乎最优自相关幅度二元序列的5种构造方案。第1种构造是利用任意理想2-值自相关序列来构造的,其余4种构造是基于某些序列及其修正版序列,且给出新序列周期自相关函数值的分布。利用2N2交织序列构造的二元序列,其周期自相关函数值除了一个点外均达到最优。这将为CDMA通信系统及其他应用提供更多的选择。     

Large families of quaternary sequences with low correlation

A family of quaternary (Z₄-alphabet) sequences of length L=2^r-1, size M⩾L²+3L+2, and maximum nontrivial correlation parameter C_max⩽2√(L+1)+1 is presented. The sequence family always contains the four-phase family 𝒜. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z₄-linear versions of the Delsarte-Goethals codes     

Cryptographic properties of the Welch-Gong transformation sequencegenerators

Welch-Gong (WG) transformation sequences are binary sequences of period 2ⁿ - 1 with two-level autocorrelation. These sequences were discovered by Golomb, Gong, and Gaal (1998) and they verified the validity of their construction for 5 ⩽ n ⩽ 20. Later, No, Chung, and Yun (1998) found another way to construct the WG sequences and verified their result for 5 ⩽ n ⩽ 20. Dillon (1998) first proved this result for odd n, and, finally, Dobbertin and Dillon (1999) proved it for even n. In this paper, we investigate a two-faced property of the WG transformation sequences for application in stream ciphers and pseudorandom number generators. One is to present the randomness or unpredictability of the WG transformation sequences. The other is to exhibit the security properties of the WG transformations regarded as Boolean functions. In particular, we prove that the WG transformation sequences, in addition to the known two-level autocorrelation and three-level cross correlation with m-sequences, have the ideal 2-tuple distribution, and large linear span increasing exponentially with n. Moreover, it can be implemented efficiently. This is the first type of pseudorandom sequences with good correlation, statistic properties, large linear span, and efficient implementation. When WG transformations are regarded as Boolean functions, they have high nonlinearity. We derive a criterion for the Boolean representation of WG transformations to be r-resilient and show that they are at least 1-resilient under some basis of the finite field GF (2ⁿ). An algorithm to find such bases is given. The degree and linear span of WG transformations are presented as well     

一类零相关区序列偶集的研究

在准同步CDMA系统中,使用零相关区(ZCZ)序列能够避免共信道冲突和多址干扰。通过应用序列偶理论,基于交织技术和一类最优ZCZ序列集中的移位序列,成功构造出了具有良好自相关和互相关性能的ZCZ序列偶集,不但可以生成不同的零相关区,而且使得序列偶集中的所有序列都循环移位不等价。仿真结果表明,它的性能优良,适于作准同步CDMA系统的扩频序列。     

Generalized Kasami Sequences: The Large Set

In this correspondence, new binary sequence families F^k of period 2ⁿ-1 are constructed for even n and any k with gcd(k,n)=2 if n/2 is odd or gcd(k,n)=1 if n/2 is even. The distribution of their correlation values is completely determined. These families have maximum correlation 2^n/2+1 and family size 2^3n/2 + 2^n/2 for odd n/2 or 2^3n/2+2^n/2-1 for even n/2. The proposed families include the large set of Kasami sequences, where the k is taken as k=n/2+1.     

Decimations of the Frank-Heimiller Sequences

The Frank-Heimiller sequence of period N²withNphases is constructed by writing theNbyNdiscrete Fourier transform matrix by rows. The periodic autocorrelation sidelobes for such a sequence are all zero. Small families ofN-phase sequences, with optimal periodic cross correlations, can be formed by judicious selection of decimations of the Frank-Heimiller sequence.