Large families of sequences for CDMA, frequency hopping, and UWB

Abstract

This paper generalizes three constructions of families of sequences with bounded off peak correlation with application to Code Division Multiple Access (CDMA), frequency hopping, and Ultra Wide Band (UWB). These new families present flexible family sizes and sequence lengths, making them well suited to wireless communications and Multiple Input Multiple Output (MIMO) radar. In particular, we show that the generalized Kamaletdinov I construction offers the lowest off-peak correlation for a given family size. For the two smallest family sizes, this construction asymptotically matches the performance of the small Kasami set and Gold codes, respectively. Among other properties, it has one of the slowest off-peak correlation growth of all known constructions, increasing proportionally to the logarithm of the family size and generates frequency and time hopping sequences.

1 Introduction

Families of sequences with low off-peak auto-correlation and cross-correlation are essential in multiuser wireless communications [6]. They are required in countless applications like Code-Division Multiple Access (CDMA), frequency hopping, and Ultra Wide Band (UWB) [14].

Binary sequences are preferred for CDMA because of their easy implementation and their full efficiency (highest peak autocorrelation) and resistance to channel noise and hardware imperfections. As previously stated, this concept relies on a family of binary sequences with low off-peak auto-correlation and cross-correlation, also referred as off-peak correlation for short.

Another important area of application is multiple-input multiple-output (MIMO) radar. Such radars are now being considered as future replacements for classical beamforming radars and mechanically scanned radars [1].

MIMO radar consists of arrays of transmitter and receiver elements. Each transmitter element sends out a signal encoded with a unique signature sequence. Then, each receiver element processes each transmitted sequence. In the far field this generates a virtual array of transceivers with better resolution and lower range and cross-range sidelobes (aliasing artefacts) than physical arrays. The far field is radiation from all array elements, considering an error within the phase less than say one degree [24].

In order to select an appropriate family of sequences for a MIMO radar, the average and peak correlation must comply with a figure of merit and provide good discrimination between sequences and shifts of other sequences of the family. For this, it is necessary to correctly select the parameters of the family, i.e. sequence length and family size. The sequence length is determined by the maximum unambiguous radar range and signal to noise ratio considerations. The family size must match or exceed the number of transmitter elements, that may be determined by cost, power consumption, layout complexity, or local oscillator feed distribution. Usually, the desirable family size is a power of 2, 3 or a product of these for one-dimensional arrays; or a power of 4 in the case of two-dimensional arrays. Detailed requirements of the sequence families, and signal waveforms for MIMO radars are analysed in [11, 20]. The absence of suitable sequences has resulted in practical implementations which deploy time domain multiplexing instead of CDMA [8]. This requires sequential pulsing of each transmitter. The low duty cycle of each transmitter reduces the SNR, and the sequential pulsing of transmitters requires the target to be stationary during an image acquisition. This limits the applications to short range, slow moving targets, such as imaging for security screening. By contrast, CDMA permits 100% duty cycle, and removes these restrictions.

In order to meet these competing requirements, one straightforward solution is to generate families of random binary sequences. Recently, Mérai [12] has studied the off-peak correlation of families of random binary sequences taking only into account the family size and sequence length. Despite being of theoretical interest, the bound on the off-peak correlation provides only a probabilistic estimate and checking is required after the family has been generated. Random sequences in general do not have useable bounds on the off peak correlation, which can result in ambiguous detection, false detection or erroneous decoding in applications such as radar.

By contrast, the algebraic constructions presented in this work present an average off peak correlation similar to random sequences but a fixed bound is proven for the off peak correlation. In fact, for one of the families, the bound is close to the lowest possible or lowest known value for a given sequence length and family size. Important measures in applications are the ratio between the peak correlation and the largest off peak value, which is known as the discrimination factor and the ratio of the peak correlation to the average off peak value, called a figure of merit [13]. Only algebraic instructions deliver guaranteed high discrimination factors, therefore are preferred in applications.

Classical constructions, such as Kasami sets and Gold codes, provide a relatively big family size with small off peak correlation bound, approximately equal to the square root of the sequence length. Tone et al. [26] proposed also the use of families of GMW sequences, which is very plausible, but one of the major drawbacks to using GMW is again the family parameters. For a nice compendium of these constructions and properties, see the book by Golomb and Gong [3]. While these constructions are optimal with respect to the off-peak correlation, they may not meet the design requirements of MIMO radar, because of the strong restrictions on the family size and sequence length. Similarly, in wireless communications the number of active subscribers and desired sequence length may forbid their use. This has led authors like Yu and Gong [29], Zhou and Tang [30], Parampalli [18] and Tirkel [9, 17] among others to investigate new families for certain lengths and family sizes.

Sequence designs with larger and flexible family size for a fixed sequence length have been described by Gong and Yu [29] and have all been found to be sub-optimal with respect to the Sidelnikov bound [22], diverging further from the bound as the family size increases. Also the sequence length is restricted to, approximately, powers of two. Although, Parampalli, Tang and Botzas [18] showed bigger families, which include those found by Gong and Yu, sequence length has to be 2^m − 1. This is too restrictive in the design of CDMA systems.

The method of composition, that generates families of sequences, has proven to be flexible in terms of family parameters. The idea behind this strategy starts with two input sequences, referred to as base sequence and shift sequence, and outputs an array, constructed by copying shifted version of the base sequence. The method of composition was first sucessfully applied by Tirkel, Osborne and Hall [25] and generalized later by Moreno and Tirkel [16]. Also, two near-optimal constructions of families of sequences found by Kamaletdinov [7] are naturally explained using the method of composition [16] and classical finite field theory. In this case, the shift sequences are based on fractional functions and trace maps.

We remark that the method of composition is far more general and can compose arrays in the dimension of the desired output. For simplicity, in this article we focus on sequences, i.e. one-dimensional arrays.

It is known that the best shift selection and order is provided by Costas-like arrays of commensurate size, i.e. those with the lowest number of auto- and cross-hits. These are usable in their own right as frequency hopping or time hopping patterns. There are also some known sequence families which, when converted into arrays are also composed of shifts of the same pseudo-noise sequence or blanks. The small Kasami set is an example. Similarly, the selected shifts to generate the small Kasami set can also be converted into frequency hopping and time hopping sequences.

In this paper, we propose three new families of shift sequences, that combining the method of composition with the Legendre sequence, yield new families of binary sequences. The new constructions are based on adding new sequences to certain known families, so they can be seen as generalizations of the Kamaletdinov and Extended Rational Cycle Constructions [9]. The resulting binary families are available for sequence lengths of N(N + 1) and N(N − 1) where N is a prime of the type 4k − 1, consequently these constructions provide many more suitable sequence lengths than powers of two. For primes of the type 4k + 1, the result is almost binary sequences with N zeros in arrays of size order N², thus becoming less efficient .

There are two other advantages of these new constructions. First, they can also be interpreted as families of arrays as explained for the parent constructions by Moreno and Tirkel [17]. Consequently, they provide frequency hopping or UWB families.

Second, as families of two and three dimensional binary arrays with good correlation, they are also useful in watermarking of images and video respectively. Such family should meet the criteria standardized by the Society of Motion Picture / Television Engineers (SMPTE) watermarking standard [23].

From the three constructions studied, we show that the one extending Kamaletdinov I family has the lowest off-peak correlation for a given family size. We also show that for the two smallest family sizes asymptotically matches the small Kasami set and the Gold codes and begins to diverge from the Sidelnikov bound when the family size approaches of the large Kasami set.

For larger family size, the families have lower off-peak correlation than the best construction of Gong and Yu [29] and Parampalli, Tang and Botzas [18].

Finally the family size is dependent on the factorization of N − 1 so, in general, this has to be calculated when the correlation bound is given. However, for selected primes, we give the exact family size and the distribution of such primes.

The paper is organized as follows: In Section 2, we introduce the necessary preliminaries to understand the paper. Section 3 presents the main theorem for generating new sequence families and then, apply it to three known constructions. These new families are compared with other families in Section 4 and the properties of the underlying shift sequences are studied in Section 5. We finish with the conclusions in Section 6.

2 Preliminaries

For a prime N, let $\mathbb {F}_{N^{s}}$ denote the finite field of N^s elements. In the case s = 1, we identify the elements of $\mathbb {F}_{N}$ with the integers in the range {0, … , N − 1}. $\mathbb {F}_{N}[X]$ and $\mathbb {F}_{N}[X,Y]$ denote the rings of univariate and bivariate polynomials with coefficients in $\mathbb {F}_{N}$.

In this work, sequences are either finite lists of zeros and ones or elements of $\mathbb {F}_{N}$. In the first case, the sequences are binary sequences, while in the second case the sequences are N-ary sequences. Although a sequence u(k) is a finite list of length L, it can be extended periodically for all indexes, i.e. u(k + L) = u(k).

The cross-correlation function with shift d of two binary sequences (u and v) of length L is defined by

$$ C_{d}(u,v) = \sum\limits_{k=0}^{L-1}(-1)^{u(k)-v(k+d)}. $$

For a set of sequences, u₀, … , u_{M− 1}, the off-peak correlation is the maximum of the cross-correlation function among pairs of family sequences with non-trivial shifts, i.e.

$$ C_{\max} = \{ \max |C_{d}(u_{i},u_{j})|\ :\ 0 \leq i < M,\quad 0 \leq j < M,\quad 0\le d < L\}, $$

where d ≠ 0 if i = j.

The method of composition builds on two sequences: a binary sequence s of length N and a shift sequence y with elements in {0, … , N − 1} and of length L, coprime with N. The composition of s and y is the sequence of length NL defined by

$$ S(k) = s(k+ y(k) ),\ k = 0,\ldots, NL-1. $$

Example 1

Consider the binary sequence s = [0, 1, 1] (with length N = 3) and the shift sequence y = [2, 1]. The composition of both is defined in the following way:

$$ \begin{array}{@{}rcl@{}} S(0)& =& s(0 + y(0)) = s(2) = 1,\\ S(1)& =& s(1 + y(1)) = s(2) = 1,\\ S(2)& =& s(2 + y(0)) = s(1) = 1,\\ S(3)& =& s(3 + y(1)) = s(1) = 1,\\ S(4)& =& s(4 + y(0)) = s(0) = 0,\\ S(5)& =& s(5 + y(1)) = s(0) = 0.\\ \end{array} $$

Figure 1 contains the graphical representation of the shift and base sequence with the result of the method of composition.

Fig. 1

Graphical representation of the arrays involved in Example 1. White squares represent 0, while 1 is represented as black squares. The indexing on s(k) is from k = 0 (bottom) to 2 (top). For y(k), each column represents an element of the shift sequence, the first column represents the first value and so on. Finally, on S(k) the values are arranged diagonally, that is starting from the lower left and wrapping around as if on a torus, i.e. identifying oposite sides. In the case of the shift sequence y(k) the position of the black squares represents the shifts of the base sequence

Moreno and Tirkel [17] applied this method to the binary Legendre sequence with N prime of the type 4k − 1 to define several families of sequences. To prove properties on the correlation of these families of sequences, we need to recall the following definition.

Definition 1

The difference function of two N-ary sequences (y₁ and y₂) of length L is given by

$$ (y_{2}{\varDelta} y_{1})(k:t,d) =y_{2}(k+t) + d - y_{1}(k)\quad\text{for } 0\le k < L. $$

This function associates a sequence to a pair of parameters (t, d) with 0 ≤ t < L and 0 ≤ d < N, named the vertical and horizontal shifts, respectively. The hit array of two sequences y₁ and y₂ is an L × N array whose entry with index (t, d) is the number of values k such that (y₂Δy₁)(k : t, d) = 0. The hit array is called auto-hit array if y₁ = y₂ and cross-hit array otherwise. The maximum element in the hit array is an important parameter called number of hits.

Example 2

Take N = 3 and these two sequences y₁ = [1, 2] and y₂ = [2, 0], In this case, (y₂Δy₁)(k : 0, 0) = [1, 1], the 2 × 3 hit array is

$$ \left( \begin{array}{lll} 0 & 0 & 2\\ 1 & 1 & 0 \end{array} \right) $$

and the number of hits is 2. Figure 2 gives the graphical representation of both arrays and the superposition for different values of (t, d).

Fig. 2

Graphical representation of N-ary sequences y₁ and y₂ in the left most column. Indexing of the shift arrays are as in Fig. 2, i.e. horizontal position indicates position in the sequence (input) and vertical position indicates the value (output). The rest of arrays represent the superposition of different shifted versions of the array y₂ with array y₁, where the hits are represented by black squares. Both of the shifts, (t, d), are applied on array y₂

The average number of hits determines the average interference whilst the peak number of hits determines the discrimination. The maximum cross-correlation of two sequences generated by the composition of the Legendre sequence of length N and shift sequences y₁ and y₂ of length L is max{DN − (L − D), L}, where

$$ D = \max\limits_{t,d} \# \lbrace k | (y_{2}{\varDelta} y_{1})(k:t,d) = 0 \rbrace, $$

excluding (t, d) = (0, 0) when y₁ = y₂. From now on, we will refer to D as the maximum number of hits between any two sequences in a family of sequences. This equals to the maximum number of auto-hits and cross-hits amongst the family.

Therefore to construct a family of binary sequences., the first step is to select a binary sequence of length N with off-peak auto-correlation equal to − 1. This role is typically played by Legendre’s sequence. Next, a family of shift sequences of length L with a maximum of D hits is chosen in order to use the method of composition. The correlation of the resulting family is ND − L + D [25].

3 Generating sequence families

In this section, we describe a method to generate new families of sequences with low number of hits and we provide an upper an upper bound for both the number of cross-hits and auto-hits of the family.

Take a family of N-ary shift sequences y₁, … , y_M, where N is a prime number and L is the length of sequences. For a family of polynomials $\mathcal {F}$, consider

$$ \{f(y_{i}(k))\}_{f\in\mathcal{F}, i = 1,\ldots, M}. $$

Setting approppiate conditions on $\mathcal {F}$ will result in families with bounded maximum number of hits.

Example 3

Take N = 5 and the set of polynomials $\mathcal {F} = \{X, X^{2}+X\}$, for the sequence y₁ = [1, 3, 4, 2], for M = 1, we have:

$$ \{f(y_{1}(k))\}_{f\in\mathcal{F}} = \{[1,3,4,2],[2,2,0,1]\}, $$

i.e. we have generated a family of frequency hopping sequences with size 2. Similarly to Example 2, the maximum number of hits of this family is 2. A property of y₁(k) is that,

$$ y_{1}(k+t) = 3^{t} y_{1}(k),\quad 0\le k < N, $$

or equivalently, if F_t(X, Y ) = X − 3^tY,

$$ F_{t}((y_{1}(k+t) , y_{1}(k))=0,\quad 0\le k < N. $$

Theorem 1

Let N be a prime number and y₁, … , y_Ma family of N-ary shift sequences such that each sequence element occurs at most Htimes within a sequence. Suppose there exists a bivariate polynomial$F_{t,i,j}(X,Y)\in \mathbb {F}_{N}[X,Y]$for each 1 ≤ t < N and 1 ≤ i, j ≤ M satisfying

$$ F_{t,i,j}(y_{i}(k),y_{j}(k+t)) = 0,\quad 0\le k < N. $$

Let$\mathcal {F}\subset \mathbb {F}_{N}[X]$be a family of polynomials and D be the number of solutions of

$$ F_{t,i,j}(X, Y) = 0,\quad f_{2}(Y) +d -f_{1}(X) = 0, $$

where$f_{1}, f_{2}\in \mathcal {F}$and (t, d) ≠ (0, 0) if f₁ = f₂. Under these conditions, the maximum number of hits of the family of sequences

$$ \{f(y_{i}(k))\}_{f\in\mathcal{F}, i = 1,\ldots, M} $$

is at most DH.

Proof

For fixed i, j and shift (t, d), with (t, d) ≠ (0, 0) if i = j, we take two sequences in the family: z₁(k) = f₁(y_i(k)) and z₂(k) = f₂(y_j(k)). The number of hits for (t, d) is the number of zeros of the following equation:

$$ f_{2}(y_{j}(k+t)) + d - f_{1}(y_{i}(k)) = 0,\quad \text{ for }0\le k < N, $$

(1)

where $f_{1}, f_{2}\in \mathcal {F}$. Additionally, we know that

$$ F_{t,j,i}(y_{i}(k), y_{j}(k+t)) = 0,\quad \text{ for }0\le k < N. $$

Writing X = y_i(k) and Y = y_j(k + t), we get a solution to the following system:

$$ F_{t,j,i}(X, Y) = 0,\quad f_{2}(Y) +d -f_{1}(X) = 0. $$

By hypothesis, the latter has D solutions. For each of these, there are at most H solutions of (1), which finishes the proof. □

To generalize several known families, we additionally need the following lemma due to D. R. Heath-Brown [5, Lemma 1].

Lemma 1

For ε > 0 and integers E and D with E ≥ D^4+ε, the set

$$ {\varPsi}(E,D) = \{N \le E: N \text{ prime},\ \left( q\mid (N-1)/2\implies q > D\right)\} $$

(2)

has cardinality #Ψ(E, D) ≫ E(logE)⁻², where the implied constant depends on ε.

We define Ψ(D) as the union of Ψ(E, D), for every E ≥ 0.

Theorem 2

Let D be a positive integer and N ∈ Ψ(D). Let g be a generator of the multiplicative group of$\mathbb {F}_{N}$and y(k) = g^k (k = 0, … , N − 2). Then, the family of sequences

$$ \{f(y(k))\}_{f\in\mathcal{F}}, $$

where

$$ \begin{array}{@{}rcl@{}} \mathcal{F} = \{A_{D}X^{D}+ {\ldots} + A_{2}X^{2} + A_{1}X | A_{1},A_{2},\ldots, A_{D}\in\mathbb{F}_{N} \\ \text{ and, for some } i\ge 0,\ A_{1}=\cdots= A_{2i-1} = 0,\ A_{2i+1} = 1 \}, \end{array} $$

has maximum cross-hit number equal to D. The size of the family is greater than N^{D− 1}and if D is odd then is equal to

$$(N^{D}-N^{\lfloor D/2 \rfloor})/(N-1).$$

Proof

For the number of cross-hits, by Theorem 1 and taking F_t instead of F_t,1,1, notice that

$$ y(k+t) = g^{t} y(k)\implies F_{t}(X,Y) = X - g^{t} Y. $$

Each value of the sequence y occurs only once, so H = 1. For any (t, d) and $f_{1},f_{2}\in \mathcal {F}$, we define the system

$$ X - g^{t} Y = 0,\quad f_{2}(Y) +d -f_{1}(X) = 0. $$

It is equivalent to

$$ f_{2}(Y) + d - f_{1}(g^{t} Y) = 0, $$

which is a polynomial system in one variable. It is a nonzero polynomial by the definition of $\mathcal {F}$ and, by Lagrange’s theorem, has at most D solutions.

The family size is easily determined by counting the number of polynomials. □

We would like to remark that Family A defined by Moreno and Tirkel [17] coincides with the case D = 2. As studied by Leukhin and Tirkel [9], Family A and family Kamaletdinov I share the same correlation bound and sequence length. Kamaletdinov constructed these sequences using field theory whilst Moreno and Tirkel [17] constructed them as arrays using the method of composition. The family Kamaletdinov I (whose size is N + 1) is defined from rational functions of degree one:

$$ \mathcal{F} = \{ AX^{-1} + X | A\in\mathbb{F}_{N} \}\cup \{X^{-1}\}. $$

Family A has one member fewer but is still good for most practical purposes. We leave as an open problem the generalization of this construction for rational functions, although, at first sight, it is not easy to find families larger than those given by the proposed construction.

Note that the resulting family from Theorem 2 requires N ∈Ψ(D), which implies that all monomials whose degree is odd and smaller than D are permutations. This makes possible to prove that f(Y ) and f(g^tY ) are different polynomials. That is not very restrictive because the cardinality of Ψ(E, D) is quite big when E is sufficiently large, so it is possible to fix D and find N ∈Ψ(E, D).

When N ∉ Ψ(D), it is also possible to define a family of sequences of size N^{D− 1} − 1. In this case, it is only necessary to consider the family of polynomials with coefficient one in the term of degree one.

Another popular shift sequence is the extended rational cycle. The elements of this sequence are elements of the projective line with coefficients $\mathbb {F}_{N}$. The next theorem shows how to generalize it using higher-degree polynomials. Sequences in the next family include $\infty$ among their members, which is an element of the projective line. Theorem 1 can be extended in to this case. For the composition method, when the shift infinity appear, we define $S(k+ \infty )= 0$.

Theorem 3

Let$\alpha \in \mathbb {F}_{N}$such that X² + X + αis a primitive polynomial. Then, defining the sequence of length N + 1

$$ y(0) = 0,\quad y(k) = \frac{-\alpha}{y(k-1)+1},\quad y(N) = \infty, $$

the maximum number of cross-hits and auto-hits of the family of sequences

$$ \{f(y(k))\}_{f\in\mathcal{F}},\quad \mathcal{F} = \{f\in\mathbb{F}_{N}[X] | \deg f\le D, f(0)=0 \}, $$

is equal to 2D.

Proof

It follows from the study of y(k) by Moreno and Maric [15] that the sequence runs through every value in the finite field, i.e. it is a full cycle.

Let us check the second hypothesis in Theorem 1, writing F_t for F_t,1,1. As shown in a proof from the reference above [15, Theorem 2], the corresponding polynomials F_t such that F_t(y(k), y(k + t)) = 0 have degree two and are irreducible bivariate quadratic forms. Hence, the number of solutions of

$$ F_{t}(X, Y) = 0,\quad f_{2}(Y) +d -f_{1}(X) = 0 $$

is less than 2D, by Bézout’s theorem. □

The last considered family of sequences is Kamaletdinov II. The general shift sequences defined in this case are a little different. We start with the original set of sequences, but with an alternative definition:

$$ S = \left\{y_{j}(k) = \alpha^{(N-1)k + j} + \frac{\alpha^{Nj }}{\alpha^{(N-1)k}} \right\}, $$

where α is a generator of the multiplicative group of $\mathbb {F}_{N^{2}}$. Because $\alpha ^{N^{2}} =\alpha$, it is obvious that (α^{(N− 1)k+j})^N = α^(1−N)k+Nj, so y_j(k)^N = y_j(k), which is equivalent to saying that that $y_{j}(k)\in \mathbb {F}_{N}$ for all k and j.

Theorem 4

Take$\alpha \in \mathbb {F}_{N^{2}}$a primitive element, then defining the set of sequences

$$ y_{i}(k) = \alpha^{(N-1)k + i} + \frac{\alpha^{Ni }}{\alpha^{(N-1)k}},\quad 1\le i < N $$

of period N + 1, the maximum number of cross-hits and auto-hits of the family of sequences

$$ \{f(y_{i}(k))\}_{f\in\mathcal{F}, i = 1,\ldots, M},\quad \mathcal{F} = \{f\in\mathbb{F}_{N}[X] | \deg f\le D,\ f(0)=0 \} $$

is equal to 4D.

Proof

Sequences in S satisfy the polynomial equation F_{t, i, j}(X, Y ), where

$$ \begin{array}{@{}rcl@{}} F_{t,i,j}(X,Y) = X^{2} \alpha^{(N+1)i} - X Y \alpha^{i+Nj} - X Y \alpha^{Ni+j+t(N-1)} +\\ Y^{2} \alpha^{j(N+1)+t(N-1)} + \alpha^{2(Nj+i)} - 2 \alpha^{(N+1)(i+j)+t(N-1)} + \alpha^{2(Ni+j+t(N-1)}. \end{array} $$

The explicit representation of this polynomial is not important. We check that:

• it has degree two and

• it is irreducible if i ≠ j or (t, d) ≠  0.

It is also easy to see that each value in the sequence appears at most two times. By Bézout’s theorem, the maximum number number of solutions of

$$ F_{t,i,j}(X, Y) = 0,\quad f_{2}(Y) +d -f_{1}(X) = 0 $$

is 2D. □

4 Off-peak correlation vs family size

In order to measure the good properties of the generated families, we compare their maximum correlation with several classical constructions and known lower bounds for the maximum correlation of binary families. There are three such lower bounds:

• Welch bound [28], recently improved by Waldron [27]

• Sidelnikov bound [22]

• Levenshtein bound [10]

Figure 3 shows the relation between these bounds and different families of binary sequences (see Table 1) and the proposed generalizations using polynomials. The x-axis represents the logarithm of the family size in base L (the sequence length) and the y-axis displays the maximum correlation between family sequences divided by the square root of L.

Fig. 3

Representation of the maximum cross-correlation of families from Table 1 for different D and N = 33. Solid blue lines represent Welch, Sidelnikov and Levenshtein Bound in blue, red and black respectively. The following families are represented small Kasami and Gold (red points), large Kasami (green star), Yu and Gong for ρ = 1,2,3,4 (crosses), Shanbhag (yellow diamonds) and Parampalli (grey dots). Finally families presented in this work: Kamaletdinov 1 (inverted triangles) and ERC (pink triangles) are plotted for comparison, varying D between 2 and 10

Table 1 Families present in Fig. 3

The figure displays three theoretical bounds via solid lines. The blue line represents the minimum possible cross-correlation that a family of that size can have according to the Welch bound. The red line represents the Sidelnikov bound and the black line the Levenshtein bound.

Although the sequence lengths are not the same, it is possible to compare these constructions for some parameters. We have selected m = 11, 12 and p = 33, depending on the construction to make a fair comparison of the family sizes and maximum correlations.

In Fig. 3, the small Kasami family clusters around the point (0.5, 1.0). It is plotted as a red point, over the Sidelnikov bound. The Gold family is plotted in the point (1,2) with another red point and the large Kasami family is represented by a green star in the point (1.5, 2).

The crosses represent the different families defined by Yu and Gong [29] for ρ = 1, 2, 3, 4, the yellow diamonds are the families defined by Shanbhag [21], and the grey dots are the families by Parampalli, Tang and Botzas [18]. Under these two families, the inverted triangles represent the generalized Kamaletdinov I. Finally Extended Rational Cycle (ERC) is represented by pink triangles for polynomials of varying degree D between 2 and 10. We decided not to plot Kamaletdinov II family because it is clearly inferior. Notice that the generalized families extend the original families, that are defined for particular values of D.

From the plotted results in Fig. 3, the generalized Kamaletdinov I families are superior in terms of correlation for small values of D. Over them is the Extended Rational Cycle which is clearly inferior.

5 Shift sequences as frequency hopping sequences

As has already been noticed, the new families of shift sequences present a small number of hits that makes the members of these families interesting as frequency hopping sequences. In communication, a low bit error rate is required, which can be guaranteed by the figure of merit, whereas discrimination factor is the quality measure for radar (See [13]).

We start with a result regarding the average number of hits, which we do not have found proven in the literature.

Lemma 2

Let y₁and y₂be two frequency hopping N-ary sequences with period L. The average number of solutions for

$$ (y_{2}{\varDelta} y_{1})(k:t,d) =y_{2}(k+t\bmod L) + d - y_{1}(k)\quad\text{for } 0\le k < L, $$

over tand d(i.e. the average number of hits when the horizontal and vertical shifts are taken at random) is L/N.

Proof

Each frequency hopping is a pattern of L dots in a grid of L columns and N rows and can be graphically represented similarly to Fig. 2 . There are L² different possible hits and LN different choices for (t, d). So, the average is L/N hits for a random choice of t and d. □

As shown in previous sections, the family which extends Kamaletdinov I is the one that delivers the largest family for a given sequence length and correlation bound of the three presented here. For that family, L = N − 1, so the ideal hit distribution for two sequences is at most one hit for each (t, d). However, the number of hits depends on the degree of the polynomials of the family.

The next theorem describes the frequency of hits when the family of polynomials has degree two or three.

Theorem 5

Let N be a prime number and D an odd integer. Let g be a generator of the multiplicative group of$\mathbb {F}_{N}$and y(k) = g^k (k = 0, … N − 2) be the exponential function. The hits of two sequences from the family

$$ y_{2}(k) = A_{2} g^{2k} + g^{k},\quad y_{1}(k) = B_{2} g^{2k} + g^{k}, $$

satisfies one of the following mutually exclusive conditions:

• if A₂B₂is not a quadratic residue of$\mathbb {F}_{N}$, then there are exactly (N − 1)²/2 pairs (t, d) with two hits, (N − 1) pairs with one hit, and (N − 1)²/2 with no hits;

• if A₂B₂is a quadratic residue of$\mathbb {F}_{N}$, then there are exactly (N − 1)(N − 2)/2 pairs (t, d) with two hits, 2N − 2 pairs with one hit, and (N − 1)(N − 2)/2 with no hits;

Proof

Take any two sequences

$$ y_{2}(k+t) = A_{2} g^{2(k+t)} + g^{k+t},\quad y_{1}(k) = B_{2} g^{2k} + g^{k}. $$

Substituting X = g^k in the difference function, we get

$$ 0 = (y_{2}{\varDelta} y_{1})(k:t,d) =(A_{2}g^{2t}-B_{2})X^{2} + (g^{t}-1)X + d \pmod N, $$

which is a polynomial of degree two. The number of roots of this polynomial depends on the discriminant, which is

$$ (g^{t}-1)^{2} - 4(A_{2}g^{2t}-B_{2})d. $$

• If A₂B₂ is not a quadratic residue of $\mathbb {F}_{N}$ then (A₂g^2t − B₂)≠ 0. This means that, fixed any t, there are (N − 1)/2 values of d such that the discriminant is a quadratic residue, (N − 1)/2 values such that it is not and only one that it is zero.

• otherwise, if A₂B₂ is a quadratic residue of $\mathbb {F}_{N}$, then there exists one value of t such that (A₂g^2t − B₂) = 0. For all these values, the difference function is a linear polynomial, so there is only one hit. For the other value of t, the distribution is the same as before.

This finishes the proof. □

Using properties of the discriminant of polynomials of degree three and the distribution of irreducible polynomials, we can prove some properties of the hit distribution.

Theorem 6

Let N be a prime number and D an odd integer such that N ∈ Ψ(3). Let g be a generator of the multiplicative group of$\mathbb {F}_{N}$and y(k) = g^k (k = 0, … N − 2) be the exponential function. The hit distribution of two sequences from the family

$$ \begin{array}{@{}rcl@{}} \{f(y(k))\}_{f\in\mathcal{F}},\ \mathcal{F} = \{f\in\mathbb{F}_{N}[X] | f(X) = A_{3}X^{3} + A_{2} X^{2}+X \}\\ \cup \{f\in\mathbb{F}_{N}[X] | f(X) = X^{3} + A_{2} X^{2} \}, \end{array} $$

satisfies the following properties:

• there are at most (N − 1)N/3 + N^3/2pairs (t, d) with no hits,

• there are at most (N − 1)N/2 + N^3/2pairs (t, d) with one or two hits.

Theorem 6 is given without a formal proof, but the idea behind is that the first item is a direct consequence of results by Pollack [19] and the second item relies on properties of the discriminant which can be found in a paper by Ostafe et al. [4].

6 Conclusions

This paper analyses the performance of three constructions of sequence families for CDMA, frequency hopping, and UWB. These are generalizations of the Kamaletdinov I and II and the Extended Rational Cycle parent constructions. We remark that are constructed as sequences but can be folded into arrays with similar good properties.

The generalization delivers larger family sizes at the expense of the off-peak correlation. This is achieved by selecting a family of polynomials of higher degree in the conditions of the theorems in this paper. We have found that the generalized Kamaletdinov I sequences have the lowest off-peak correlation for a given family size. In fact, for degree 2 this construction matches (asymptotically) the correlation performance of the small Kasami set and Gold codes. For higher degrees, the extension of the family Kamaletdinov I depart from optimality at a slower rate than the best constructions of Gong, and the families are available for sequence length N(N − 1), where N is a prime number. Also, they are comparable with the constructions of Shanbhag et al., but they are available for many more lengths and parameters.

For the family resulting from Theorem 2, we find that the largest family size occurs for certain primes and this permits many more lengths than known constructions, whose lengths are constrained to be near powers of 2. Consequently, the generalized Kamaletdinov I construction is suitable for applications that require specific sequence length and family size. Such applications include wireless communications and MIMO radar. This construction and the two others described here are based on the method of composition, which means that sequences are available in CDMA, frequency hopping, or UWB format and also as two- or higher-dimensional arrays for watermarking [2].