环Zpl导出Kerdock-code序列的部分周期性质

对环Z_p^l导出的多元Kerdock-code序列的部分周期性质进行了研究,这里p为任意奇素数,l为任意正整数.利用特征为p^l的Galois环上不完全指数和的非平凡上界,对上述p元Kerdock-code序列的非周期自相关性及互相关性进行了估计,同时对序列的部分周期分布和部分周期独立r-样式分布也进行了刻画.结果表明,此类序列具有极低的非周期自相关性及互相关性,同时其部分周期分布和部分周期独立r-样式分布也是渐进均匀的,在密码学和通信领域具有潜在的应用价值.     

New designs for signal sets with low cross correlation, balanceproperty, and large linear span: GF(p) case

New designs for families of sequences over GF(p) with low cross correlation, balance property, and large linear span are presented. The key idea of the new designs is to use short p-ary sequences of period υ with the two-level autocorrelation function together with the interleaved structure to construct a set of long sequences with the desired properties. The resulting sequences are interleaved sequences of period υ². There are υ cyclically shift distinct sequences in each family. The maximal correlation value is 2υ + 3 which is optimal with respect to the Welch bound. Each sequence in the family is balanced and has large linear span. In particular, for binary case, cross/out-of-phase autocorrelation values belong to the set {1, -υ, υ + 2, 2υ + 3, -2υ - 1}, any sequence where the short sequences are quadratic residue sequences achieves the maximal linear span. It is shown that some families of these sequences can be implemented efficiently in both hardware and software     

GMW序列和WG序列及WG序列间的互相关特性

对于奇数n,研究了Gordon-Mills-Welch（GMW）序列与Welch-Gong（WG）序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数。研究表明：GMW序列与WG序列（及其某一采样序列）间的互相关函数以及WG序列间的互相关函数最终均与m-序列与其采样序列间的互相关函数相关;并且在一定条件下,WG序列间的互相关函数可为3-值或5-值的。另外,给出了GMW序列与WG序列间互相关函数的最大峰值。     

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     

p-ary unified sequences: p-ary extended d-form sequences with the ideal autocorrelation property

In this paper, for a prime number p, a construction method to generate p-ary d-form sequences with the ideal autocorrelation property is proposed and using the ternary sequences found by Helleseth, Kumar, and Martinsen (2000), ternary d-form sequences with the ideal autocorrelation property are constructed. By combining the methods for generating p-ary extended sequences (a special case of geometric sequences) and p-ary d-form sequences, a construction method of p-ary unified (extended d-form) sequences which also have the ideal autocorrelation property is proposed. This is a very general class of p-ary sequences including the binary and nonbinary extended sequences and the d-form sequences. From the ternary sequences by Helleseth, Kumar, and Martinsen, ternary unified sequences with the ideal autocorrelation property are also generated.     

On the aperiodic and odd correlations of the binaryShanbhag-Kumar-Helleseth sequences

A previously derived upper bound on hybrid sums over Galois rings is combined with a method due to Vinogradov (1954) to obtain an upper bound for the maximum aperiodic and odd correlations of the binary sequences constructed by Shanbhag, Kumar, and Helleseth (see Proc. 1995 IEEE Int. Symp. on Information Theory, 1995)     

4-phase sequences with near-optimum correlation properties

Two families of four-phase sequences are constructed using irreducible polynomials over Z₄. Family A has period L =2^r-1. size L+2. and maximum nontrivial correlation magnitude C_max⩽1+√(L+1), where r is a positive integer. Family B has period L=2(2^r-1). size (L+2)/4. and C_max for complex-valued sequences. Of particular interest, family A has the same size and period as the family of binary Gold sequences. but its maximum nontrivial correlation is smaller by a factor of √2. Since the Gold family for r odd is optimal with respect to the Welch bound restricted to binary sequences, family A is thus superior to the best possible binary design of the same family size. Unlike the Gold design, families A and B are asymptotically optimal whether r is odd or even. Both families are suitable for achieving code-division multiple-access and are easily, implemented using shift registers. The exact distribution of correlation values is given for both families     

Fast Template Matching Based on Normalized Cross Correlation With Adaptive Multilevel Winner Update

In this paper, we propose a fast pattern matching algorithm based on the normalized cross correlation (NCC) criterion by combining adaptive multilevel partition with the winner update scheme to achieve very efficient search. This winner update scheme is applied in conjunction with an upper bound for the cross correlation derived from Cauchy-Schwarz inequality. To apply the winner update scheme in an efficient way, we partition the summation of cross correlation into different levels with the partition order determined by the gradient energies of the partitioned regions in the template. Thus, this winner update scheme in conjunction with the upper bound for NCC can be employed to skip unnecessary calculation. Experimental results show the proposed algorithm is very efficient for image matching under different lighting conditions.     

Phase normalised m-sequences with the inphase decimation property {m(k)}={m(2k)}

The inphase decimation property of a binary sequence {f(k)} is defined such that f(k)=f(2k) for all k=0, 1, 2,? Given a primitive generator polynomial G(D) of degree r with its even and odd parts Ge(D) and Go(D), it is shown that there is a unique version of the corresponding m-sequence with this inphase decimation property, resulting as Ge(D)/G(D) if r is odd and Go(D)/G(D) if r is even. An m-sequence in such a phase position is termed the phase normalised version.     

Upper bound on one-coincidence sequences of odd length with distance constraints in frequency-hopping spread-spectrum systems

We deal with one-coincidence sequences for the frequency-hopping CDMA systems. We derive an upper bound on the number of one-coincidence sequences of odd length where the distances between all adjacent frequency indices are required to be greater than a specified distance value. It is shown that there exist infinitely many cases in which our bound is tighter than the conventional bound.     

Families of polyphase sequences with near-optimal two-valued auto- and crosscorrelation functions

A construction method is proposed for new families of uniform polyphase sequences with near-optimal correlation. These families consist each of N sequences of length N and energy N with the following unique properties: (a) the sidelobes of the periodic autocorrelation functions have constant, nearly perfect magnitude 1; (b) the sequences are orthogonal; (c) all sidelobes of the periodic crosscorrelation functions have the constant magnitude square root (N+1); and (d) the correlation values asymptotically reach the Sarwate bound.<>     

GF(3)上新型自缩控序列的周期与线性复杂度

Self-Shrinking Control (SSC) sequences are a class of important pseudo-random sequences, and pseudo-random sequences are widely used in many fields, such as communication encryption, recoding technology. In these applications, sequences are usually required to have large periods and high linear complexity. In order to construct pseudo-random sequences with higher period and higher linear complexity, a new SSC sequence model based on the m-sequence in GF (3) is constructed, the period and the linear complexity of the generated sequence are studied by using finite domain theory, this model greatly improves the period and the linear complexity of the generated sequence, and obtains a more accurate upper bound value of the linear complexity of the generated sequence. Thus, the anti-attack ability and security performance of the generated sequence in communication encryption are improved.     

Prime-phase sequences with periodic correlation properties better than binary sequences

For the case where p is an odd prime, n>or=2 is an integer, and omega is a complex primitive pth root of unity, a construction is presented for a family of p/sup n/ p-phase sequences (symbols of the form omega /sup i/), where each sequence has length p/sup n/-1, and where the maximum nontrivial correlation value C/sub max/ does not exceed 1+ square root p/sup n/. A complete distribution of correlation values is provided. As a special case of this construction, a previous construction due to Sidelnikov (1971) is obtained. The family of sequences is asymptotically optimum with respect to its correlation properties, and, in comparison with many previous nonbinary designs, the present design has the additional advantage of not requiring an alphabet of size larger than three. The new sequences are suitable for achieving code-division multiple access and are easily implemented using shift registers. They wee discovered through an application of Deligne's bound (1974) on exponential sums of the Weil type in, several variables. The sequences are also shown to have strong identification with certain bent functions.<>     

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.     

一类具有极低相关性的CDMA序列

 本文利用环Z^p_l上线性递归序列的最高坐标构造了一类序列数目众多的p元序列族,这里p为奇素数且整数l不小于2。对具体可用序列的条数进行了估计。同时利用Galois环上的指数和估计以及Z^p_l的加法群上的谱分析对该序列族的相关性进行了详细分析,得到了其非同步自相关性及互相关性的估计。结果表明,所构造的序列具有极低的相关性,其相关性的模值具有与Welch下界相同的数量级,可以作为CDMA通信系统中的码序列。     

On the nonexistence of Barker arrays and related matters

Evidence is presented to support the conclusion that there exists only one equivalence class of binary two-dimensional arrays (both dimensions greater than 1) of +1's and -1's with all out-of-phase aperiodic autocorrelation values bounded in magnitude by unity. It is proved that no such array exists when either dimension is an odd prime or when one dimension is an odd integer and the other is twice an odd integer. Further constraints on the potentially possible dimensions of these structures are explored by developing their relationship to group difference sets, complementary sequences, and quaternary Barker sequences. The results of a computer search for binary arrays which have the smallest maximum out-of-phase autocorrelation magnitude are presented, and the utility of these arrays in waveform design problems is discussed     

Design of pseudonoise sequences with good odd and even correlationproperties for DS/CDMA

Proposes and investigates a method for designing pseudonoise (PN) sequences having both good odd and even correlation properties, which are important for acquisition and demodulation in spread spectrum (SS) communications. Odd correlation properties of PN sequences should be designed as well as their even or periodic correlation properties so that the cochannel interference can be reduced as small as possible. Polyphase PN sequences with such good correlation properties can be derived from biphase PN sequences with a good aperiodic correlation property under a certain condition. Absolute values of odd and even correlation functions of these sequences are equal at each shift. The authors evaluated their peak correlations properties and bit error rate performance. Numerical evaluations show that the derived polyphase sequences have lower peaks of correlations and lower bit error rate than their original sequences. Furthermore, the authors defined the generalized odd correlation function for polyphase SS systems, and derived a way to improve the generalized odd correlation properties     

Asymptotic bounds on quantum codes from algebraic geometry codes

We generalize a characterization of p-ary (p is a prime) quantum codes given by Feng and Xing to q-ary (q is a prime power) quantum codes. This characterization makes it possible to convert an asymptotic bound of Stichtenoth and Xing for nonlinear algebraic geometry codes to a quantum asymptotic bound. Besides, we also investigate the asymptotic behavior of quantum codes.     

Value Distributions of Exponential Sums From Perfect Nonlinear Functions and Their Applications

In this paper we present a unified way to determine the values and their multiplicities of the exponential sums Sigma_xisinF(q)zeta_p ^Tr(af(x)+bx)(a,bisinF_q,q=p^m,pges3) for all perfect nonlinear functions f which is a Dembowski-Ostrom polynomial or p = 3,f=^x(3(k)+1)/2 where k is odd and (k,m)=1. As applications, we determine (1) the correlation distribution of the m-sequence {a_lambda=Tr(gamma^lambda)}(lambda=0,1,...) and the sequence {b_lambda=Tr(f(gamma^lambda))}(lambda=0,1,...) over F_p where gamma is a primitive element of F_q and (2) the weight distributions of the linear codes over F_p defined by f.     

基于m序列的宽间隔跳频序列的生成

为了克服对偶法生成宽间隔跳频随机序列的缺点,基于m序列,提出非线性模d法,利用非连续抽头模型,生成宽间隔跳频随机序列.比较了对偶法生成的跳频序列和非线性模d法生成的跳频序列的自相关性能和互相关性能等.计算结果表明,非线性模d法是对偶法的明显改进,其生成序列的随机性、抗干扰性都有明显改善,且相关性能接近于最佳跳频序列的相关性能.