New classes of sequence families with low correlation by using multiplicative and additive characters

Abstract

For an odd prime p, a new sequence family of period p^m-\mathrm{1}, size \left(M-\mathrm{1}\right)p^{mr} is proposed using multiplicative and additive characters. The upper bound for the maximum magnitude of nontrivial correlations of the sequence family is derived using well-known character sums. The upper bound is shown to be \left(r+\mathrm{1}\right)\sqrt{p^m}+\mathrm{3}, which meets the Welch bound asymptotically.

Keywords

finite field / character sum / correlation / polyphase sequence / Welch bound

Introduction

In wireless communications, sequences with low correlation are widely used to distinguish multiple users or channels with low mutual-access interference (MAI) [1]. To maximize the achievable data rate, polyphase sequence sets with a variety of lengths and alphabet sizes are more desirable than binary sequence sets for most wireless mobile communication systems employing adaptive modulation schemes. In addition, a large number of distinct sequences may be needed for supporting user requirements that rapidly increase.

A sequence S=\{s(t)\} is called a polyphase sequence with alphabet q if s(t) is a qth root of unity for all t. Let F=\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_M\} be a set of M cyclically distinct polyphase sequence with period N, where s_i=\{s_i(t)\} for \mathrm{1}\le i\le M. The periodic cross correlation function between sequence s_i and s_j at the shift phase τ is given by

R_{s_i,s_j}(\tau )={\displaystyle \sum _{t=\mathrm{0}}^{N-\mathrm{1}}{s}_i}(t)\overline{s_j(t+\tau )}.

If s_i=s_j, we call it the periodic autocorrelation function of sequence s_i at the shift phase \tau, and it is denoted as R_{s_i}(\tau ). Let R_{\max }(F) be the maximal correlation of F, i.e.,

R_{\max }(F)=\max \left|R_{s_i,s_j}(\tau )\right|

for any \mathrm{0}\le \tau \le N-\mathrm{1} if \mathrm{1}\le i\ne j\le M and if i=j. The sequence family F is said to have low correlation if R_{\max }(F)\le v\sqrt{N} for a small constant v. There exist many designs of sequence families that meet this asymptotic bound with equality. Readers may refer to Refs. [1,2] for an overview on this topic.

In Ref. [3], polyphase sequence families with low correlation were constructed from the shift and addition of the power residue sequence (Sidelnikov sequence, respectively) and its constant multiple sequences, whose maximum correlation were shown to be upper bounded by \mathrm{2}\sqrt{L}+\mathrm{5} or \mathrm{3}\sqrt{L}+\mathrm{4} (\mathrm{2}\sqrt{L}+\mathrm{6} or \mathrm{3}\sqrt{L}+\mathrm{5} for sequence families from Sidelnikov sequence, respectively), where L is the period of the constructed sequences. In Ref. [4], more generalized constructions were considered by the addition of multiple cyclic shifts of power residue and Sidelnikov sequences, which can be represented by multiplicative character. Recently, sequence family of prime period p, family size (p-\mathrm{2})p^r, and maximum correlation at most (r+\mathrm{1})\sqrt{p}+\mathrm{2} was obtained by using multiplicative and additive characters in Ref. [5].

In this paper, we generalize the constructions in Ref. [5] to the general finite field. Our constructions are also based on multiplicative character and additive character. However, instead of using the traditional multiplicative character directly, we use it in a way similar to the one use in the construction of Sidelnikov sequence. Before presenting our constructions, we review some related definitions and properties of finite field.

Let p be a prime and q=p^m, where m is a positive integer. Let F_q be a finite field containing q elements. Given a\in F_q, an additive character of F_q is a homomorphism mapping from additive group (F_q,+) to (C^{*},\cdot ) defined by

{\varphi }_a(x)=e^{\frac{\mathrm{2}\mathrm{\pi }\sqrt{-\mathrm{1}}}{p}Tr(ax)},

where \text{Tr} is the trace function of F_q over F_p, i.e.,

\mathrm{T}\mathrm{r}(x)=x+x^p+\cdots +x^{p^{m-\mathrm{1}}}.

In the case a=\mathrm{0}, we call {\varphi }_{\mathrm{0}} trivial additive character; otherwise, we call it nontrivial. Multiplicative character of F_q is another useful tool in this paper. Let \xi be a generator for the cyclic group (F_q^{*},\cdot ), where F_q^{*}=F_q\backslash \left\{0\right\}. For an integer a, a multiplicative character of F_q is a homomorphism mapping from cyclic group (F_q^{*},\cdot ) to (C^{*},\cdot ) defined by

{\chi }_a({\xi }^t)=e^{\frac{\mathrm{2}\pi \sqrt{-\mathrm{1}}}{q-\mathrm{1}}at}.

It is convenient to assume that {\chi }_a(\mathrm{0})=\mathrm{0}. Given two characters {\chi }_a and {\chi }_b, one can form the product {\chi }_a{\chi }_b by setting

{\chi }_a{\chi }_b(g)={\chi }_a(g){\chi }_b(g)

for all g\in F_q^{*}. It is well known that the set of characters of (F_q^{*},\cdot ) forms a cyclic group under the multiplication of characters. The order of a multiplicative character {\chi }_a is thus defined to be the least positive integer d such that {\chi }_a^d(g)=\mathrm{1} for any g\in F_q^{*}.

Following bounds on character sums will be useful in the estimation of the correlation function of sequence families.

Lemma 1 [6] let \chi be a nontrivial multiplicative character of F_q of order M, and \varphi be a nontrivial additive character of F_q. Suppose that f\in F_q[x] is not, up to a nonzero multiplicative constant, an M th power in F_q[x]. Then, for any polynomial g\in F_q(x), we have

\left|{\displaystyle \sum _{x\in F_q}\chi (f(x))\varphi (g(x))}\right|\le (\mathrm{deg}(g)+d-\mathrm{1})\sqrt{q},

where d is the number of distinct roots of f in its splitting field over F_q.

Lemma 2 [7] Let \varphi be a nontrivial additive character of F_q, and let f\in F_q[x] be of degree n\ge \mathrm{1} with \text{gcd}(n,p)=\mathrm{1}. Then,

\left|{\displaystyle \sum _{x\in F_q}\varphi (f(x))}\right|\le (n-\mathrm{1})\sqrt{q}.

New constructions

Let F_q be a finite field with q elements, where q=p^m, p is an odd prime and m is a positive integer. Assume M is a positive integer satisfying M|(q-\mathrm{1}), let \chi be a multiplicative character of F_q^{*} with order M. Let \varphi be a nontrivial additive character of F_q and ξ be a generator of (F_q^{*},\cdot ). Given integer r, \mathrm{0}\le r\le p-\mathrm{2}, denote

C^r=\{(a;b_r,b_{r-\mathrm{1}},\dots ,b_{\mathrm{1}})|\mathrm{1}\le a\le M-\mathrm{1},and{b}_i\in F_{q}for\mathrm{1}\le i\le r\}.

Let c=(a;b_r,b_{r-\mathrm{1}},\dots ,b_{\mathrm{1}})\in C^r, the sequence s^c is then given by

s^c(t)={\chi }^a({\xi }^t+\mathrm{1})\varphi \left({\displaystyle \sum _{i=\mathrm{1}}^r{b}_i}{({\xi }^t)}^i\right)

for \mathrm{0}\le t\le q-\mathrm{2}. For r=\mathrm{0},\mathrm{1},\dots ,p-\mathrm{2}, define the sequence family {\Gamma }_r^{*} to be

{\Gamma }_r^{*}=\{s^c|c\in C^r\}.

It is obvious that each sequence in {\Gamma }_r^{*} has period q-\mathrm{1} and takes on values that are Mpth roots of unity except for one element per period. In the following, we will determine its maximum nontrivial correlation and its family size, which turns out to be approximately good with respect to Welch bound.

Theorem 1 Let {\Gamma }_r^{*} be the sequence family defined above. Then, we have

R_{\max }({\Gamma }_r^{*})\le (r+\mathrm{1})\sqrt{q}+\mathrm{1.}

Proof. Given two sequences s^c and s^{c^{\prime }} in {\Gamma }_r^{*}, by assuming that c=(a;b_r,b_{r-\mathrm{1}},\dots ,b_{\mathrm{1}}) and c^{\prime }=(a^{\prime };b_{r^{\prime }},b_{r-{\mathrm{1}}^{\prime }},\dots ,b_{{\mathrm{1}}^{\prime }}), we have

s^c\left(t\right)={\chi }^a\left({\xi }^t+1\right)\varphi \left({\displaystyle \sum _{i=1}^r{b}_i{\left({\xi }^t\right)}^i}\right),

s^{c^{\prime }}\left(t\right)={\chi }^{a^{\prime }}\left({\xi }^t+1\right)\varphi \left({\displaystyle \sum _{i=1}^r{b}_{i^{\prime }}{\left({\xi }^t\right)}^i}\right).

Let b(x)={\displaystyle {\sum }_{i=\mathrm{1}}^r{b}_i{x}^i} and b^{\prime }(x)={\displaystyle {\sum }_{i=\mathrm{1}}^r{b}_{i^{\prime }}{x}^i}. For \tau, \mathrm{0}\le \tau \le q-\mathrm{2},

(1)\begin{array}{l}{R}_{s^c,s^{c^{\prime }}}\left(\tau \right)\\ ={\displaystyle \sum _{t=0}^{q-2}{\chi }^a}\left({\xi }^t+1\right)\varphi \left(b\left({\xi }^t\right)\right)\overline{{\chi }^{a^{\prime }}\left({\xi }^{t+\tau }+1\right)\varphi \left(b^{\prime }\left({\xi }^{t+\tau }\right)\right)}\\ ={\displaystyle \sum _{x\in F_q^{*}}\chi }\left({\left(x+1\right)}^a\cdot {\left(\theta x+1\right)}^{M-a^{\prime }}\right)\varphi \left(b\left(x\right)-b^{\prime }\left(\theta x\right)\right)\\ ={\displaystyle \sum _{x\in F_q^{*}}\chi }\left(f\left(x\right)\right)\varphi \left(g\left(x\right)\right),\end{array}

where \theta ={\xi }^{\tau }, f(x)={(x+\mathrm{1})}^a\cdot {(\theta x+\mathrm{1})}^{M-a^{\prime }}, and g(x)=b(x)-b^{\prime }(\theta x). To estimate the correlation between s^c and s^{c^{\prime }} at \tau, we divide it into following cases.

1) If c=c^{\prime }, only nontrivial autocorrelation of s^c need to be considered, that is, \theta \ne \mathrm{1}. Then, f(x) has two distinct roots. Thus, f(x) cannot be a Mth power. Moreover, g(x) has degree at most r. By Lemma 1,

\begin{array}{l}\left|R_{s^c}(\tau )\right|=\left|{\displaystyle \sum _{x\in F_q}\chi }(f(x))\varphi (g(x))-\mathrm{1}\right|\\ \le (r+\mathrm{1})\sqrt{q}+\mathrm{1.}\end{array}

2) If c\ne c^{\prime } and f(x)=h{(x)}^M for some h(x)\in F_q[x], we have a=a^{\prime } and \theta =\mathrm{1}. By c\ne c^{\prime } and a=a^{\prime }, we have (b_r,\dots ,b_{\mathrm{1}})\ne (b_{r^{\prime }},\dots ,b_{{\mathrm{1}}^{\prime }}). Hence, g(x)=b(x)-b^{\prime }(x) is a polynomial with degree at least 1 and at most r. Furthermore, by assumption r\le p-\mathrm{2}, we have gcd(deg(g(x),q)=\mathrm{1}. By applying Lemma 2, we have

\begin{array}{l}\left|R_{s^c,s^{c^{\prime }}}(\tau )\right|=\left|{\displaystyle \sum _{x\in F_q}\varphi }(g(x))-\mathrm{1}\right|\\ \le (r-\mathrm{1})\sqrt{q}+\mathrm{1.}\end{array}

3) If c\ne c^{\prime } and f(x)\ne h{(x)}^M for any h(x)\in F_q[x], then, f(x) has at most two distinct roots and g(x) has degree at most r. By applying Lemma 2 again, we have

\begin{array}{l}\left|R_{s^c,s^{c^{\prime }}}(\tau )\right|=\left|{\displaystyle \sum _{x\in F_q}\chi }(f(x))\varphi (g(x))-\mathrm{1}\right|\\ \le (r+\mathrm{1})\sqrt{q}+\mathrm{1.}\end{array}

Combining above cases, the proof is thus completed.□

By Theorem 1, sequences in {\Gamma }_r^{*} are cyclically distinct. Hence, the family size of {\Gamma }_r^{*} is (M-\mathrm{1})q^r. Note that each sequence in {\Gamma }_r^{*} has one 0 per period. Similar to Ref. [5], we can modify sequences in {\Gamma }_r^{*} to be polyphase sequences by changing these zeros. Technologically, we can define \chi (\mathrm{0})=\mathrm{1} instead of \chi (\mathrm{0})=\mathrm{0}. Let us denote the new sequence as {\widehat{s}}^c and the corresponding sequence family as {\Gamma }_r. It is easily seen from Eq. (1) that for all {\widehat{s}}^c and {\widehat{s}}^{c^{\prime }} in {\Gamma }_r,

R_{{\widehat{s}}^c,{\widehat{s}}^{c^{\prime }}}\left(\tau \right)=R_{s^c,s^{c^{\prime }}}\left(\tau \right)+\varphi \left(b\left(-1\right)\right)\overline{{\chi }^{a^{\prime }}\left(-\theta +1\right)\varphi \left(b^{\prime }\left(-\theta \right)\right)}+{\chi }^a\left(-{\theta }^{-1}+1\right)\varphi \left(b\left(-{\theta }^{-1}\right)\right)\overline{\varphi \left(b^{\prime }\left(-1\right)\right)}.

Therefore,

\left|R_{{\widehat{s}}^c,{\widehat{s}}^{c^{\prime }}}(\tau )\right|\le \left|R_{s^c,s^{c^{\prime }}}(\tau )\right|+\mathrm{2.}

Corollary 1 Let {\Gamma }_r be the sequence family defined above. Then we have

R_{\max }({\Gamma }_r)\le (r+\mathrm{1})\sqrt{q}+\mathrm{3.}

Several known classes of sequence families with low correlation and large family size are compared in Table 1. In Table 1, the alphabet size M is a factor of period L or L-\mathrm{1}. When we compare it with the sequence families given in Refs. [3,4,8], new constructed sequence family possesses the same period and maximum correlation magnitude, a larger family size if we let r equal to 1 or 2, but a larger alphabet size. Similarly, compared with the sequence family in Ref. [9], new sequence family has a lower maximum correlation magnitude, but a lager alphabet size. Hence, for the new construction, the increase of the family size is at the cost of faster increase of the alphabet size in general. However, in applications, the alphabet size M is often required to be much smaller than the period L of the sequence, that is, M\ll L. Thus, the proper increase of the alphabet size may be acceptable for the gaining of a larger family size by taking small integer M, small prime p, and large integer m. Finally, we have to acknowledge that the individual sequences in the new sequence family may behave not well in balanceness and autocorrelation, which has been verified for several cases.

Conclusion

Just as it was pointed out in Ref. [5] that there is a tradeoff between the sequence family size and its maximum correlation, which also serves as a motivation of the constructions presented in this paper. Our constructions can be regarded as a generalization of the constructions in Ref. [5]. By Theorem 1 and Corollary 1, the correlation of the new sequence family meets the Welch bound asymptotically.

References

[1] Golomb S W, Gong G. Signal Design for Good Correlation — For Wireless Communication, Cryptography and Radar. Cambridge, U.K.: Cambridge University Press, 2005

[2] Helleseth T, Kumar P V, Pless V S, Huffman W C. Sequences with low correlation. In: Handbook of Coding Theory. Amsterdam, Netherlands: Elsevier, 1998

[3] Han Y K, Yang K. New M-ary sequence families with low correlation and large size. IEEE Transactions on Information Theory, 2009, 55(4): 1815-1823

[4] Yu N Y, Gong G. New construction of M-ary sequence families with low correlation from the structure of Sidelnikov sequences. IEEE Transactions on Information Theory, 2010, 56(8): 4061-4070

[5] Schmidt K U. Sequence families with low correlation derived from multiplicative and additive characters. IEEE Transactions on Information Theory, 2011, 57(4): 2291-2294

[6] Niederreiter H, Winterhof A. Incomplete character sums and polynomial interpolation of the discrete logarithm. Finite Fields and Their Applications, 2002, 8(2): 184-192

[7] Lidl R, Niederreiter H. Finite Fields (Encyclopedia of Mathematics and Its Applications. vol. 20). 2nd ed. New York, NY: Cambridge University Press, 1997

[8] Kim Y S, Chung J S, No J S, Chung H. New families of M-ary sequences with low correlation constructed from Sidelnikov sequences. IEEE Transactions on Information Theory, 2008, 54(8): 3768-3774

[9] Zhou Z C, Tang X H. New nonbinary sequence families with low correlation, large size, and large linear span. Applied Mathematics Letters, 2011, 24(7): 1105-1110

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg