\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{color}
\renewcommand{\baselinestretch}{1}
\renewcommand{\arraystretch}{1.3}
%you may inactive the following four commands, then it will become appearance of book pages
\setlength{\topmargin}{-0.1in}
\setlength{\textheight}{8.3in}
\setlength{\oddsidemargin}{0.1 in}
\setlength{\textwidth}{6.2 in}
%%%%%%%%%
%%%%%%%%%%%%%
\newtheorem{fact}{Fact}
\newtheorem{algorithm}{Algorithm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{property}{Property}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newcommand{\notsim}{{\, \not \sim \,}}
\newcommand{\F}{\ensuremath{\mathbb F}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\Q}{\ensuremath{\mathbb Q}}
\newcommand{\R}{\ensuremath{\mathbb R}}
\newcommand{\C}{\ensuremath{\mathbb C}}
\newcommand{\done}{\hfill $\Box$ }
\newcommand{\rmap}{\stackrel{\rho}{\leftrightarrow}}
\newcommand{\mys}{\vspace{0.15in}}
\newcommand{\ebu}{{\bf{e}}}
\newcommand{\Abu}{{\bf{A}}}
\newcommand{\Bbu}{{\bf{B}}}
\newcommand{\abu}{{\bf{a}}}
\newcommand{\abuj}{{\bf{a_j}}}
\newcommand{\bbu}{{\bf{b}}}
\newcommand{\vbu}{{\bf{v}}}
\newcommand{\ubu}{{\bf{u}}}
\newcommand{\dbu}{{\bf{d}}}
\newcommand{\tbu}{{\bf{t}}}
\newcommand{\cbu}{{\bf{c}}}
\newcommand{\kbu}{{\bf{k}}}
\newcommand{\hbu}{{\bf{h}}}
\newcommand{\sbu}{{\bf{s}}}
\newcommand{\wbu}{{\bf{w}}}
\newcommand{\xbu}{{\bf{x}}}
\newcommand{\ybu}{{\bf{y}}}
\newcommand{\zbu}{{\bf{z}}}
\newcommand{\corres}{\leftrightarrow}
\newcommand{\zero}{{\bf{0}}}
\newcommand{\one}{{\bf{1}}}
\newcommand{\nodiv}{{\, \not| \,}}
\newcommand{\notequiv}{{\,\not\equiv\, }}
%%%%%%%%%%%%%%
\def\comb#1#2{{#1 \choose #2}}
\newcommand{\ls}[1]
{\dimen0=\fontdimen6\the\font\lineskip=#1\dimen0
\advance\lineskip.5\fontdimen5\the\font
\advance\lineskip-\dimen0
\lineskiplimit=0.9\lineskip
\baselineskip=\lineskip
\advance\baselineskip\dimen0
\normallineskip\lineskip\normallineskiplimit\lineskiplimit
\normalbaselineskip\baselineskip
\ignorespaces}
\def\stir#1#2{\left\{#1 \atop #2 \right\}}
\def\dsum#1#2{#1 \atop #2 }
\def\defn{\stackrel{\triangle}{=}}
%%%%%%%%
\begin{document}
\bibliographystyle{abbrv}
\title{Correlation of Multiple Bent Function Signal Sets }
\author{Guang Gong\\
Department of Electrical and Computer Engineering \\
University of Waterloo \\
Waterloo, Ontario N2L 3G1, CANADA \\
Email. ggong@calliope.uwaterloo.ca\\
}
\date{}
\maketitle
\thispagestyle{plain}
\setcounter{page}{1}
\begin{abstract}
Observing a phenomenon that the pre-image set of nonzero Hadamard spectra of the composition of a function and a trace function is independent of the function, a construction of multiple bent function signal sets using different bent functions is given. Their correlation and high-order shift-distinct property are discussed.
As a by-product, the union of the multiple bent function signal sets produces a signal set with low correlation zone and much larger size of the other known constructions.
{\bf Index Terms.} Multiple signal sets, maximum correlation, bent functions,
high-order shift-distinct property, CDMA.
\end{abstract}
\ls{1.5}
\section{Introduction}
Pseudorandom sequences with good correlation have wide applications in communications and cryptography. Communications over networking environments bring up many new problems in sequence design. For example, interference in detect of code division multiple access (CDMA)
signals is not only from signals within one signal set,
but also from several different signal sets when users
roam to different geographical areas. (For detection of CDMA signals, the reader is
referred to \cite{Viterbi}\cite{Scholtz}\cite{Pursley}.)
This type of interference
is referred to as {\em intraference} among these signal sets in the engineering content,
i.e., correlation among multiple signal sets. In this paper, we consider correlation and high-order shift-distinct property of multiple signal sets constructed from bent function signal sets.
\section{ The Basic Definitions and Properties }
A {\em crosscorrelation function} between two binary
sequences $\abu=\{a_i\}$ and $\bbu=\{b_i\}$ with
period $N$ is defined by
\[
C_{\abu, \bbu}(\tau)=\sum_{i=0}^{N-1} (-1)^{a_{i+\tau}+b_i},
\tau=0, 1, \cdots
\]
When $\abu=\bbu$, the crosscorrelation between $\abu$ and $\bbu$
becomes the autocorrelation of $\abu$.
The shift operator is defined by $L\abu=a_1, a_{2},
\cdots$ for $\abu=a_0, a_1, \cdots$, and $L^r\abu=a_r, a_{r+1},
\cdots$. For two sequences,
if one can be obtained from the other by performing the shift
operator, then we say that they are {\em shift equivalent}.
Otherwise, they are said to be {\em shift distinct}. Let $S$ be a set consisting of $r$ shift-distinct binary sequences of period $N$. The maximum correlation of $S$ is defined by
\[
\delta = \max\{|C_{\abu, \bbu}(\tau)| \,|\, \abu, \bbu \in S, | \tau| < N, \mbox{ and } \tau\not = 0 \mbox{ if } \abu=\bbu\}.
\]
$S$ is called an {\em $(N, r, \delta)$ signal set}, and $S$ is called an {\em $(N, r, \delta, d)$ low correlation zone signal set} if $|\tau| \le d$ where $d2$. The high-order shift-distinct property also directly connects with the high-order correlation of sequences \cite{NamGong}.
\begin{definition}
Let $k$ multiple signal sets $ S_1, \cdots, S_k$, each with parameters $(N, r, \delta)$, be $m$th-order ($m\ge 2$) shift distinct. The maximum correlation of $k$ multiple signal sets $S_1, \cdots, S_k$ is defined by
\[
\Delta=\max\{|C_{\abu, \bbu}(\tau)| \,|\, \abu\in S_i, \bbu \in S_j, 1\le i, j \le k, |\tau |< N\}
\]
where $\tau\not = 0$ if $\abu=\bbu$. $ S_1, \cdots, S_k$ are said to be {\em $(v, r, k, \Delta)$ multiple signal sets}. If $|\tau|\le d$ where $d1$ where $H(i)$ is the Hamming weight of the integer $i$.
Together with (\ref{eq-f2}), from one of those $i$'s, by applying
Lemma \ref{le-eq}, we have
\[
h_ix^i=h_i\cdot (\delta x)^i \Longrightarrow \delta =1. \]
Substituting $\delta=1$ into (\ref{eq-f2}), we obtain
\[
Tr_1^n((\lambda+ \mu
\sigma_0)x)=Tr_1^n((\eta+\theta\sigma_0)(x)\Longrightarrow
\lambda+ \mu \sigma_0=\eta+\theta\sigma_0.
\]
Since $\{1, \sigma_0\}$ is a basis of $\F_{q^2}$ over $\F_q$, the
above identity implies that $\lambda=\eta$ and $\mu=\theta$ which
contradicts with $\mu \ne \theta$. Thus $S_{i}$ and
$S_{j}$ are shift distinct as long as $\mu\ne \theta \Longrightarrow i\not = j$.
\done
\begin{theorem}\label{th-3sd}
The signal sets $S_i, 0\le i3$ monomial bent functions $Tr_1^n(\beta_i x^{r_i}), \beta_i \in \F_q$ such that $\sum_{i=1}^m r_i>q$, we may choose $f_v$s as follows. Let $f_v(x) = Tr_1^n(\beta_i \omega^j x^{r_i})$ where $v=r_1+r_2+\cdots +r_i +j, v=0, 1, \cdots, q-2$. Then $S_i, 0\le i3$. High-order shift-distinct property directly connects with high-order correlation of sequences. It is not easy to compute high-order correlation of the sequences, although this is the case in real communication systems.
\begin{thebibliography}{1}
\bibitem{Kim} S.-H. Kim, J.-W. Jang, J.-S. No, and H. Chung, New constructions of quaternary low correlation zone sequences, {\em IEEE Trans. Inform. Theory}, vol. 51, No. 4, pp. 1469-1477, April 2005.
\bibitem{JNCT} J.W. Jang, J.S. No, H.B. Chung, and X.H. Tang, New sets of optimal $p$-ary low correlation zone sequences, {\em IEEE Trans. Inform. Theory}, vol. 53, No. 2, pp. 815-821, February 2007.
\bibitem{Golomb-book} S.W. Golomb, {\it Shift Register Sequences,}
Holden-Day, Inc., San Francisco, 1967, revised edition, Aegean
Park Press, Laguna Hills, CA, (1982).
\bibitem{Golomb-Gong} S.W. Golomb and G. Gong, {\em Signal Design
with Good Correlation: for Wireless Communications, Cryptography
and Radar Applications}, Cambridge University Press, 2005.
\bibitem{gong-isit07} G. Gong, Constructions of multiple shift-distinct signal sets with low correlation, accepted by {\em 2007 IEEE International Symposium on Information Theory (ISIT2007)},
24th - 29th June 2007, Nice, France.
\bibitem{GGS} G. Gong, S. W. Golomb, and H.Y. Song, A note on low correlation zone signal sets, {\em 40the Annual Conference of Information Sciences and Systems (CISS 2006)}, March 22-24, 2006, Princeton University, Technical Co-Sponsorship With IEEE Information Theory Society. Technical Report, CACR 2006-06, University of Waterloo, January 2006. Submitted to {\em IEEE Trans. Inform. Theory}, and revised in April 2007.
\bibitem{GongAMS} G. Gong, Correlation among signal sets, presented at the Special
Session on {\em Coding Theory and Cryptography}, organized by
Horacio Tapia-Recillas and Neal Koblitz, at {\em VI Joint Meeting
of American Mathematical Society and Sociedad Matematica Mexicana
(AMS-SMM)}, May 12-15, 2004, Huston.
\bibitem{GongIS95} G. Gong, Theory and applications of $q$-ary interleaved sequences,
{\em IEEE Trans. on Inform. Theory}, Vol. 41, No. 2, March 1995,
pp. 400-411.
\bibitem{GongIS02} G. Gong, New Designs for signal sets with low cross-correlation,
balance property and large linear span: $GF(p)$ Case, {\em IEEE
Trans. on Inform. Theory}, Vol. 48, No.11, November 2002, pp.
2847-2867.
\bibitem{Klapper-Chan-Goresky2} A. Klapper, A.H. Chan, and M. Goresky, Cross-correlations of
linearly and quadratically related geometric sequences and GMW
sequences, {\em Discrete Appl. Math.} {\bf 46}, No. 1, (1993), pp.
1-20.
\bibitem{KumarDis} P.V. Kumar, On bent sequences and generalized bent functions, Ph. D. Thesis,
University of Southern California, Los Angeles, 1983.
\bibitem{KumarHelleseth} T. Helleseth and P.V. Kumar, Sequences with low correlation, a
chapter in {\em Handbook of Coding Theory}, edited by V. Pless
and C. Huffman, Elsevier Science Publishers, 1998, pp. 1765-1853.
\bibitem{LidlNiederreiter} R. Lidl and H. Niederreiter,
{\em Finite Fields}, Encyclopedia of Mathematics and its
Applications, Volume 20, Addison-Wesley, (1983). (Revised version,
Cambridge University Press, 1997.)
\bibitem{McEliece} R.J. McEliece, {\em Finite Fields for Computer Scientists and
Engineers}, The Knuwer International Series in Engineering and
Compute Science, Vol. 23, Kluwer Academic Publishers, Boston,
(1986).
\bibitem{NamGong} N. Y. Yu and G. Gong, Higher order autocorrelation of binary sequences with ideal two-level autocorrelation, {\em Proceedings of Canadian Workshop on Information Theory (CWIT'05)}, pp. 391 - 394, Montreal, Canada, June 5-8, 2005.
\bibitem{Osenz-Scholtl-Welch} J.D. Olsen, R.A. Scholtz and L.R. Welch, Bent-function
sequences, {\em IEEE Trans. Inform. Theory}, Vol. 28, No. 6,
November 1982, pp. 858-864.
\bibitem{Paterson} K.G. Paterson, Binary sequence sets with
favorable correlations from difference sets and MDS codes, {\em
IEEE Trans. Inform. Theory}, Vol. 44, No. 1, January 1998, pp.
172-180.
\bibitem{Pursley} M.B. Pursley, {\em Introduction to Digital
Communications}, Pearson Prentice Hall, 2005.
\bibitem{Scholtz} M.K. Simon, J.K. Omura, R.A. Scholtz, and B.K.
Levitt, {\em Spread Sprectrum Communications Handbook},
McGraw-Hill Companies, Inc., 2002.
\bibitem{Viterbi} A.J. Viterbi, {\em CDMA $-$ Principles of Spread Spectrum Communication}, Reading, MASS., Addison-Wesley, 1995.
\bibitem{Tang} X. H. Tang and P. Z. Fan, A class of pseudonoise sequences over GF($p$) with low correlation zone, {\em IEEE Trans. Inform. Theory}, vol. 47, no. 4, pp. 1644-1649, May 2001.
\bibitem{Tang1} X. H. Tang, P. Z. Fan and S. matsufuji, Lower bounds on correlation of spreading sequence sets with low or zero correlation zone, {\em Electronic Letters}, vol. 36, No. 6, pp. 551-552, March, 2000.
\bibitem{Zierler} N. Zierler, Linear recurring sequences, {\em J. Soc. Indust. Appl. Math.}
{\bf 7} , (1959), pp. 31-48.
\end{thebibliography}
\end{document}