Almost balanced and uncorrelated quaternary sequence pairs of even length

1.   Introduction

Sequences and sequence pairs that are optimally autocorrelated, largely complex, and balanced are important in many applications, such as measurement, digital communication, and continuous-wave radar^[1-3]. In recent years, owing to their simple implementation, they have an amount of attention. Sequences and sequence pairs with low correlation can be generalized to quasi-complementary sequence sets and a few weight codes. Luo et al. proposed three new constructions of asymptotically optimal periodic quasi-complementary sequence sets using new parameters and small alphabet sizes^[4]. Shi et al. obtained a family of abelian binary five-weight codes using a Gray map^[5]. Several studies have been conducted on binary sequence pairs^[6-9]. In this study, we focus on quaternary sequence pairs.

Li et al. constructed quaternary sequences and sequence pairs using binary complete sequences and sequence pairs^[10]. Peng et al. proposed quaternary sequence pairs with an even length and three-level correlation using inverse Gray mapping and two difference set pairs of the same modulus^[11]. Yang et al. presented two lower bounds on the maximum cross-correlation magnitude of balanced quaternary sequence pairs with (almost) optimal autocorrelation, and constructed a balanced quaternary sequence pair whose autocorrelation and cross-correlation achieve the lower bound^[12]. Zhou et al. presented two generic constructions of quaternary periodic complementary pairs^[13]: first, using the known binary odd periodic complementary pairs and Gray mapping; and second, based on the product sequences of a known quaternary sequence and a perfect quaternary sequence.

The remainder of this paper is organized as follows. In Section 2, we introduce quaternary sequences and their correlations, partitions of $\mathbb{Z}_p$ by cyclotomic classes, and permutations of $\mathbb{Z}_4$. In Section 3, we describe the construction of an uncorrelated quaternary sequence pair. In Section 4, we present almost balanced and uncorrelated sequence pairs with low autocorrelation, except at a few positions, and provide some examples to illustrate this. Finally, we summarize this study in Section 5.

2.   Preliminaries

2.1   Quaternary sequences and their correlations

Let $\mathbb{Z}_4=\{0,1,2,3\}$. A quaternary sequence is a sequence with the alphabet $\mathbb{Z}_4$. The periodic cross-correlation function between two quaternary sequences $a=(a(0),\;a(1),\;\cdots,\; a(N-1))$ and $b=(b(0),\;b(1),\;\cdots,\;b(N-1))$ of period $N$ is the complex function:

where $\omega=\sqrt{-1}$, and after the addition, $t+\tau$ is taken as modulo $N$. We say that the sequence pair $(a,b)$ is uncorrelated if $R_{a,\;b}(\tau)=0$ for $0\leqslant\tau < N$.

Suppose $G_i=\{i:a(t)=i\},0\leqslant i\leqslant3$. For $i\neq j$, $a$ is called balanced if $|G_i|-|G_j|=0$ and $4\mid N$, or $|G_i|-|G_j|=1$ and $4\nmid N$. $a$ is called almost balanced if $|G_i|-|G_j|\leqslant2$ for $i\neq j$.

Let $\{\alpha_0,\alpha_1,\cdots,\alpha_{M-1}\}$ be a sequence set that consists of $M$ sequences of length $N$. An $N\times M$ matrix $R$ is formed by placing the sequence $\alpha_i$ in the $i$th column, $0\leqslant i < M$, that is, $R=[\alpha_0, \alpha_1, \cdots, \alpha_{M-1}]$. The interleaved sequence $u$ is the sequence concatenating the successive rows of matrix $R$, denoted as

$I$ is called the interleaving operator, and $\alpha_0,\alpha_1,\cdots,\alpha_{M-1}$ are called the column sequences of $u$.

Lemma 2.1. Suppose $u=I(\alpha_0,\;\alpha_1,\;\cdots,\;\alpha_{M-1})$ and $v= I(\beta_0,\;\beta_1,\;\cdots,\;\beta_{M-1})$. For $0\leqslant \tau < MN$, we write $\tau=\tau'M+\tau''$, where $0\leqslant\tau' < N$ and $0\leqslant\tau'' < M$. The cross-correlation function between $u$ and $v$ is given by:

2.2   Partitions of $\mathbb{Z}_{p}$ by cyclotomic classes

Recall that for a set $X$, a partition of $X$ is a family of subsets $\{X_i\}_{i\in I}$ such that $\bigcup_i X_i=X$ and $X_i\cap X_j=\emptyset$ if $i\neq j$. Cyclotomic classes are typically used to obtain the partitions of $\mathbb{Z}_N$.

We first recall the definition^[3] of cyclotomic classes over $\mathbb{Z}_p$.

Definition 2.1. Let $p$ be an odd prime, $p-1=ef$, and $\gamma$ a generator of $\mathbb{Z}_p^*$. For $0\leqslant l < e$, $D_l^{(e,p)}=\{\gamma^{l+ek}:0\leqslant k < f\}$ is the set of cyclotomic classes of order $e$ over $\mathbb{Z}_p$. For $0\leqslant l\neq l' < e$, the cyclotomic number

We drop $e$ and $p$ from the notation when they are implied by the context. We let $D_e=D_e^{(e,p)}=\{0\}$.

Cyclotomic classes give partitions of $\mathbb{Z}_p^*$ and $\mathbb{Z}_p$:

Lemma 2.2. ^[3] Suppose $p-1=ef$, $0\leqslant l\neq l' < e$, then

We need the following information about cyclotomic numbers^[3]:

(i) If $e=4$, then $p=4f+1=x^2+4y^2$ where $x\equiv1\pmod4$ is unique and $y$ is unique up to a certain point depending on the choice of $\gamma$. Table 1 lists the cyclotomic numbers of order four.

Table  1.  Cyclotomic numbers of order 4.

	$f$ is even	$f$ is odd
$16\times (0,0)$	$p-11-6x$	$p-7+2x$
$16\times (0,1)$	$p-3+2x+8y$	$p+1+2x-8y$
$16\times (0,2)$	$p-3+2x$	$p+1-6x$
$16\times (0,3)$	$p-3+2x-8y$	$p+1+2x+8y$
$16\times (1,1)$	$p-3+2x-8y$	$p-3-2x$
$16\times (1,2)$	$p+1-2x$	$p+1+2x+8y$

 | Show Table

DownLoad: CSV

(ii) If $e=8$, then $p=8f+1=x^2+4y^2=a^2+2b^2$ with a unique $x\equiv a\equiv1\pmod4$. Table 2 lists the cyclotomic numbers of order eight when $p\equiv 1\bmod{16}$ (equivalently $f$ is even).

Table  2.  Cyclotomic numbers of order 8 for $p\equiv 1\bmod{16}$.

	If 2 is a quartic residue	If 2 is not a quartic residue
$64\times(0,0)$	$p-23-18x-24a$	$p-23+6x$
$64\times(0,1)$	$p-7+2x+4a+16y+16b$	$p-7+2x+4a$
$64\times(0,2)$	$p-7+6x+16y$	$p-7-2x-8a-16y$
$64\times(0,3)$	$p-7+2x+4a-16y+16b$	$p-7+2x+4a$
$64\times(0,4)$	$p-7-2x+8a$	$p-7-10x$
$64\times(0,5)$	$p-7+2x+4a+16y-16b$	$p-7+2x+4a$
$64\times(0,6)$	$p-7+6x-16y$	$p-7-2x-8a+16y$
$64\times(0,7)$	$p-7+2x+4a-16y-16b$	$p-7+2x+4a$
$64\times(1,2)$	$p+1+2x-4a$	$p+1-6x+4a$
$64\times(1,3)$	$p+1-6x+4a$	$p+1+2x-4a-16b$
$64\times(1,4)$	$p+1+2x-4a$	$p+1+2x-4a+16y$
$64\times(1,5)$	$p+1+2x-4a$	$p+1+2x-4a-16y$
$64\times(1,6)$	$p+1-6x+4a$	$p+1+2x-4a+16b$
$64\times(2,4)$	$p+1-2x$	$p+1+6x+8a$
$64\times(2,5)$	$p+1+2x-4a$	$p+1-6x+4a$

 | Show Table

DownLoad: CSV

2.3   Permutations of $\mathbb{Z}_4$

A permutation of $\mathbb{Z}_4$ is written as $\sigma=(\sigma(0),\sigma(1),$ $\sigma(2),\sigma(3))$. It is well-known that 24 permutations of $\mathbb{Z}_4$ exist, which are ordered as follows:

3.   New construction of perfect quaternary sequences pairs

In this section, we provide a generic construction of uncorrelated quaternary sequences pairs.

Suppose $N$ is an odd integer. We need a special case for Lemma 2.1:

Lemma 3.1. Let $a,b,c$ be quaternary sequences of length $N$. Let $u$ and $v$ be the interleaved sequences

where L is the left shift operator. Subsequently, the auto- and cross-correlation functions of $u$ and $v$ are given by:

where $0\leqslant\tau < 2N$, $\tau=2\tau'+\tau''$, $0\leqslant\tau' < N$ and $0\leqslant\tau'' < 2$.

Definition 3.1. Suppose $\pi=\{A_0,A_1,A_2,A_3\}$ is a partition of $\mathbb{Z}_N^*$, $\sigma=(\sigma(0),\sigma(1),$ $\sigma(2),\sigma(3))$ is a permutation of $\mathbb{Z}_4$, and $s\in \{0,1,2,3\}$. The quaternary sequence $\beta=\beta_{\pi,\sigma, s}$ associated with $\pi$, $\sigma$, and $s$ of length $N$ is defined as

If $\pi$ implied by context and $\sigma=\sigma_i$, then we write $\beta_i^s$ for $\beta_{\pi,\sigma_i,s}$ .

The first result of this study is the following:

Theorem 3.1. Suppose the permutations of $\mathbb{Z}_4$ are ordered as in Chapter 2.3. Subsequently, for any partition $\pi$ of $\mathbb{Z}_N^*$ and any $s\in\{0,1,2,3\}$, if $i,\;j,\;j+4$ are in the same interval $[1,8]$, $[9,16]$, or $[17,24]$, then

Consequently, the interleaved sequence pair

is an uncorrelated pair, that is, $R_{u,v}(\tau)=0$.

Proof. We prove the case in which $i=j=1$ and $s=0$. The other cases can be proved in the same manner.

We write $\beta_i^0=\beta_i$, and we must show that $R_{\beta_1}(\tau)+ R_{\beta_1,\;\beta_5}(\tau)=0$. For subsets $X,Y$ of $\mathbb{Z}_N$, the difference function $d_\tau(X,Y)$ is the function

By definition, the real and imaginary parts of the autocorrelation function $R_{\beta_1}(\tau)$ and the cross-correlation function $R_{\beta_1,\;\beta_5}(\tau)$ are given as follows:

where $0\leq t<N$. If the subsets $X_1\cap X_2=\emptyset$ and $Y_1\cap Y_2=\emptyset$, we verify that

Therefore, $R_{\beta_1}(\tau)+R_{\beta_1,\;\beta_5}(\tau)=0$ for $0\leqslant\tau<N$.

In practice, the pair $(u,v)$, given by Eq. (7), is preferrable as be an uncorrelated sequence pair, which is almost balanced and with low autocorrelation, except at a few positions. Note that

(i) If the partition components $A_i$ are of the same size (that is, $N\equiv 1 \,{\text{mod}}\,{4}$), then $\beta_i^s$ is balanced, that is, $u$ and $v$ are almost balanced.

(ii) By Lemma 3.1,

Hence, the low autocorrelation of $u$ and $v$ at $\tau\neq 0,\; N$ is guaranteed by the low autocorrelation of $\beta_i^s$ and $\beta_j^s$ at $\tau\neq 0$, respectively. We also note that $R_u(0)=R_v(0)=R_u(N)=2N, R_v(N)=-2N.$

For a prime $p$, we choose appropriate partitions of $\mathbb{Z}_p^*$ by cyclotomic classes of orders 4 and 8 to obtain $(u,v)$ with good properties. Here, we provide a toy example.

Suppose $N\equiv1\pmod4$ with the partition given by:

This provides a perfect and almost balanced pair with high autocorrelation.

Example 3.1. Let $N=13$, $A_0=\{1,2,3\}$, $A_1=\{4,5,6\}$, $A_2=\{7,8,9\}$, and $A_3=\{10,11,12\}$. Let $(i,j)=(1,2)$ and $s=1$. Subsequently,

The quaternary sequences pair $(u,v)$ is

We can see that $R_{u,\;v}(\tau)=0$ for $0\leqslant\tau < 26$; however, the sequences $u,v$ have a large autocorrelation.

4.   Construction of sequence pairs using cyclotomic classes of ${\mathbb{Z}_p}$

Let $p$ be an odd prime. We choose the partition of $\mathbb{Z}_p^*$ from cyclotomic classes of orders 4 and 8. This makes the sequences $\beta_i^s$ balanced such that the sequence pairs obtained are uncorrelated, almost balanced, and have low autocorrelation, except at a few positions.

Theorem 4.1. Suppose $p=4f+1=x^2+4y^2$ with $x\equiv 1\bmod{4}$. Let $D_k$ be the cyclotomic class of order $4$ and $\pi$ the partition $A_k=D_k$. Subsequently, $\beta_i^s$ is balanced and

① if $f$ is even,

where $\Delta_1\in\{0,\pm2\}$;

② if $f$ is odd and $1\leqslant i\leqslant 8$,

where $\Delta_1\in\{0,\pm1\}$, $\Delta_2\in\{0,\pm1,\pm2\}$.

Therefore, if $y$ is small, then $\beta_i^s$ has low autocorrelation, except at the in-phase position.

Proof. The real and imaginary parts of the autocorrelation function $R_{\beta_i^s}(\tau)$ are given as follows:

where if $\sigma_i(s)=k$,

If $f$ is even, then $-1\in D_0$, and $\Delta_1\in\{0,\pm2\},\Delta_2=0$, by calculation, for $\tau\in \mathbb{Z}_p^*$, ${\text{Re}}\, R_{\beta_i^s}(\tau)\in\{-1+\Delta_1,-1+y+\Delta_1,-1-y+ \Delta_1\}, {\text{Im}}\,R_{\beta_i^s}(\tau)= 0$, that is, $R_{\beta_i^s}(\tau)\in\{-1+\Delta_1,-1+y+\Delta_1, -1-y+ \Delta_1\}$.

If $f$ is odd, then $-1\in D_2$, and $\Delta_1\in\{0,\pm1\},\Delta_2\in\{0,\pm1,\pm2\}$, by calculation, for $\tau\in \mathbb{Z}_p^*$, ${\text{Re}}\, R_{\beta_i^s}(\tau)\in\{-1+\Delta_1,-1+y+\Delta_1, -1-y+ \Delta_1\}$, we can verify that ${\text{Im}}\, R_{\beta_i^s}(\tau)=\Delta_{2}$ if $1\leqslant i\leqslant 8$, that is, $R_{\beta_i^s}(\tau)\in\{-1+\Delta_1+\Delta_{2}\omega, -1+y+\Delta_1+\Delta_{2}\omega,-1-y+\Delta_1+ \Delta_{2} \omega\}.$

Example 4.1. Suppose $p=37=4\times9+1$, $\mathbb{F}_{37}^\times=\langle2\rangle$. The cyclotomic classes of order 4 over $\mathbb{Z}_{37}$ are

Let $A_k=D_{k},0\leqslant k\leqslant 3$, $i=2,j=3$ and $s=1$, then,

The quaternary sequence pair $(u,v)$ of length $74$ is

By calculation, $R_{u,\;v}(\tau)=0$, and $R_u(\tau)$ and $R_v(\tau)$ are given by:

Theorem 4.2. Suppose $p=m^4+16$ is a prime. Let the partition $\pi$ be given by $A_0=D_0\cup D_4,A_1=D_1\cup D_7,A_2=D_2\cup D_6, A_3= D_3\cup D_5$, where the $D_k$s are cyclotomic classes of order 8. Then, the sequence $\beta_i^s$ is balanced and has low autocorrelation except at the in-phase position: $R_{\beta_i^s}(\tau)\in\{-7,\pm1,\pm3\}$ for $0<\tau<p.$

Proof. If $f$ is even, $x=m^2,y=\pm2,a=m^2-4$. We prove this when $i=1, s=0$, and the other cases are provable in the same manner.

The real and imaginary parts of $R_{\beta_1^0} (\tau)$ are as follows:

For $\tau\in D_0$, we have

Therefore, $R_{\beta_1^0}(\tau)= {\text{Re}}\, R_{\beta_1^0}(\tau)$ if $\tau\in D_0$. Similarly, we obtain the values $R_{\beta_1^0}(\tau)$ for $\tau\in D_l, 0\leqslant l < 8$ as follows: when 2 is a quartic residue,

and when 2 is not a quartic residue,

Example 4.2. For $p=97=3^4+16$, let $\mathbb{F}_{97}^\times=\langle5\rangle$; then, the cyclotomic classes of order 8 in $\mathbb{Z}_{97}$ are

Let $i=1,j=3$ and $s=0$, then,

The quaternary sequence pair $(u,v)$ of length $194$ is

Subsequently, $R_{u,v}(\tau)=0$, $R_u(\tau)$ and $R_v(\tau)$ are as follows:

Remark 4.1. Note that the numbers of primes of the form $x^2+4$, $x^2+9$, $x^4+16$, etc., are all assumed to be infinite by the Bouniakowsky conjecture^[14].

5.   Conclusions

In this study, we constructed uncorrelated quaternary sequence pairs of length 2N by using the cyclotomic classes. The result shows that the sequence pairs are almost balanced and have low autocorrelation, except at a few positions. In the future work, studying other partitions of $\mathbb{Z}_N^*$ would be interesting. For example, if $N=pq$, the partitions of $\mathbb{Z}_{pq}^*$ may be choose as combinations of the generalized cyclotomic classes^[15] introduced by Shen et al..

Acknowledgements

The work was supported by Anhui Initiative in Quantum Information Technologies (AHY150200), USTC Research Funds of the Double First-Class Initiative (YD0010002004), and the Fundamental Research Funds for the Central Universities (WK0010000068).

Conflict of interest

The authors declare that they have no conflict of interest.