New Construction of Optimal Type-II Binary Z-Complementary Pairs

A PAIR of sequences is called a Golay complementary pair (GCP), if their aperiodic autocorrelation sums (AACSs) are zero everywhere, except at the zero shift [1], [2]. GCPs were first introduced by Golay in 1961 in the context of an optical problem in multislit spectrometry. Since then, GCPs have found extensive engineering applications for its ideal correlation properties. For example, GCPs are useful in inter-symbol interference channel estimation [3, 4], radar waveform designs [5, 6, 7], asynchronous multi-carrier code-division multiple access (MC-CDMA) communications [8, 9], and peak-to-mean envelope power ratio (PMEPR) control in multi-carrier communications [10, 11].

The main drawback of the GCPs is their limited availability for various lengths. It was conjectured that binary GCPs are available only for lengths of the form $2^{a}10^{b}26^{c}$ where $a,~{}b,~{}c$ are non-negative integers [12]. By computer search, the conjecture has been verified for binary GCPs of length up to $100$ [12]. In search of binary sequence pairs of other lengths, Fan, Yuan and Tu [13] proposed the concept of Z-complementary pair (ZCP) in 2007, which is a pair of sequences whose aperiodic autocorrelation sums are zero not everywhere but within a certain region called zero correlation zone (ZCZ). Based on their lengths, binary ZCPs are categorised into two types: odd-length (OB-ZCPs) and even-length ZCPs (EB-ZCPs). It was further conjectured by Fan, Yuan and Tu [13] that “For OB-ZCPs, the maximum zero correlation zone is given by $Z_{\max}=(N+1)/2$, and for EB-ZCPs, given that the lengths $N\neq 2^{a}10^{b}26^{c}$, the ZCZ is upper bounded by $N-2$.” In 2011 Li et al. [14] proved the conjecture for OB-ZCPs. However, a systematic construction of OB-ZCPs was still unknown.

In 2014, Liu, Udaya and Guan [15] made remarkable progress towards this open problem and proposed a systematic construction of OB-ZCPs. The generated optimal sequence pairs achieve the maximum ZCZ of width $(N+1)/2$ as well as the minimum AACSs magnitude of $2$ at each time-shift outside the ZCZ [15]. The construction of optimal OB-ZCPs in [15] was given by applying the insertion method on binary Golay-Davis-Jedwab (GDJ) sequences. In 2014, Liu, Udaya and Guan [16] also confirmed the conjecture for EB-ZCPs that $Z_{\max}\leq N-2$. Recently, a lot of work has been done for constructing EB-ZCPs (for example, see [17, 18, 19]). Besides the lengths, in [15] Liu, Udaya and Guan further categorised ZCPs based on their correlation properties: Type-I ZCPs are sequence pairs having zero AACSs at each time-shift within the ZCZ around the in-phase position, while Type-II ZCPs are those having zero AACSs at each time-shift within the ZCZ around the end-shift position. Type-I ZCPs can be effectively used in quasi-synchronous CDMA (QS-CDMA) systems [20, 21, 22, 23, 24, 25, 26], which are tolerant of small-signal arrival delays. On the other hand, Type-II ZCPs are useful in wide-band wireless communication systems where the minimum interfering-signal delay can assume a large value. This is because the ZCZ of Type-II ZCP is designed for large time-shifts, and thus the asynchronous interfering signals arriving at the receiver after large delays can be rejected. A typical example of such a channel with large delays is the sparsely populated rural and mountainous areas [25]. In some other important applications, like designing preamble sequences in OFDMA systems [27], where PMEPR plays a very important role, Type-II ZCPs may be advantageous over Type-I ZCPs because of its huge availability with flexible lengths. Moreover, Type-I and Type-II ZCPs can also be used to construct complementary sets [28] and Z-complementary sets [29].

Till now there are only a few constructions of Type-I and Type-II constructions reported in the literature [15, 16, 17, 18, 19, 30, 31]. Note that most of the constructions are based on GCPs and thereby have lengths of the form of $2^{a}+2^{v}$. Recently, based on generalized Boolean functions, Chen [17] gave a direct construction of those Type-I ZCPs having lengths of the form $2^{m-1}+2^{v}$ and a ZCZ of width $2^{\pi(v+1)-1}+2^{v}$, where $\pi$ is a permutation over $\{1,2,\dots,m-1\}$. Adhikary et al. [30, 31] made further progress towards this problem and proposed a systematic construction of Type-I and Type-II ZCPs of lengths of the form $2^{a}10^{b}26^{c}+1$, by applying the insertion method on binary GCPs. Very recently, Shen et al. [32] constructed Type-II ZCP of length $2^{m}+3$, by inserting 3 elements into GDJ sequences. An overview of known Type-II binary ZCPs is given in Table I, together with their corresponding ZCZ width. For the definitions of Z-optimality and optimality of binary ZCPs, see Definitions 6 and 7, respectively.

To the best of our knowledge, the maximum ZCZ width for binary Type-II ZCPs of lengths of the form $10^{b}+1$, $26^{c}+1$ and $10^{b}26^{c}+1$ are $4\times 10^{b-1}+1$, $12\times 26^{c-1}+1$ and $12\times 10^{b}26^{c-1}+1$, respectively. Furthermore, there is no construction of Type-II EB-ZCPs in the literature.

Motivated by the constructions reported in [15, 30], in search of ZCPs with larger ZCZ widths, we propose an iterative construction of Type-II binary ZCPs of both even and odd lengths. Our proposed construction can generate Z-optimal Type-II OB-ZCPs having lengths of any odd length, and also optimal Type-II EB-ZCPs for certain cases. In fact, our proposed construction can generate Type-II ZCPs with more flexible lengths which were unknown before. As a comparison with previous results, our results are given in Table I. We further list down the “best possible” ZCPs up to length $30$ in Table II. The term “best possible”, means that the ZCPs have the closest possible autocorrelation properties to those of the optimal Type-II ZCPs. Note that the sequence pairs, whose lengths are given in bold letters in Table II, were not reported before.

The rest of this paper is organized as follows. In Section II, we introduce some basic definitions and preliminary results about ZCPs, and the peak-to-mean envelope power ratio (PMEPR) control problem in code-keying MC communications. In Section III, we propose a generic construction of Type-II ZCPs, which allows generating both OB-ZCPs and EB-ZCPs. In addition, we propose a construction of optimal Type-II OB-ZCPs in Section IV. In Section V, we analyse the PMEPR of the proposed ZCPs. Finally, Section VI concludes the paper by some future work.

In this section, we recall some definitions and bounds of binary ZCPs. Before that, we fix some notations which will be used throughout the paper.

• •

  $+$ and $-$ denote $1$ and $-1$, respectively.

• •

  $\mathbf{0}_{L}$ and $\mathbf{1}_{L}$ denote length-L vectors whose elements are all $0$ and $1$, respectively.

• •

  $\overleftarrow{\mathbf{c}}=(c_{N_{1}-1},c_{N_{1}-2},\cdots,c_{0})$ denotes the reverse of sequence $\mathbf{c}=(c_{0},\ldots,c_{N_{1}-2},c_{N_{1}-1})$.

• •

  $\mathbf{c}\mid\mid\mathbf{d}$ denote the horizontal concatenation of sequences $\mathbf{c}$ and $\mathbf{d}$.

• •

  $\mathbf{c}\otimes\mathbf{d}$ denotes the Kroneker product of the sequences $\mathbf{c}$ and $\mathbf{d}$ of lengths $N_{1}$ and $N_{2}$, respectively, i.e.,

  $$\mathbf{c}\otimes\mathbf{d}=(c_{0}d_{0},c_{0}d_{1},\cdots,c_{0}d_{N_{2}-1},\cdots,c_{N_{1}-1}d_{0},c_{N_{1}-1}d_{1},\cdots,c_{N_{1}-1}d_{N_{2}-1}).$$

In the following, we first give the definition of aperiodic correlation, and then define the deletion function.

In what follows, we give a series of definitions on a pair of sequences with desirable aperiodic autocorrelation sums, and certain bounds on these sequence pairs.

Clearly, when $Z=N$, both Type-I and Type-II ZCPs become GCPs.

In the following lemma we recall the upper bounds of the ZCZ width for various types of binary ZCPs.

Note that bound 3) in Lemma 1 was obtained by exhaustive computer search. Based on the bounds above, we have the following definition on the Z-optimality of ZCPs.

The following lemma gives the lower bounds of the aperiodic autocorrelation sum magnitude outside the ZCZ of a Z-optimal (Type-I and Type-II) binary ZCP.

The lower bounds above define the optimality of ZCPs, which achieve the smallest possible sum magnitude outside the ZCZ of Z-optimal binary ZCPs.

Infinite families of nontrivial (Type-I and Type-II) OB-ZCPs and Type-I EB-ZCPs were obtained in [15] and [16, 17, 18, 19], respectively. However, there was no infinite family of Type-II EB-ZCPs in the literature. In this section, we present a construction of ZCPs which can generate infinite families of Z-optimal Type-II OB-ZCPs and EB-ZCPs. We first present an example to show that an optimal Type-II EB-ZCP does exist.

Now, we present a systematic construction of Type-II ZCPs in the following.

Based on the construction above, we have the following theorems to obtain Z-optimal (optimal) OB-ZCPs and EB-ZCPs.

In the following, we show some illustrative examples.

Example 3 gives us a construction of Z-optimal Type-II EB-ZCPs. However, the length of Z-optimal Type-II EB-ZCPs which are constructed through the above method is $2^{k}+2^{k-1}$, and this makes the length very limited. By the following construction inspired by the well-known Turyn’s construction, we can obtain Type-II ZCPs of length $(2^{k}+2^{k-1})10^{b}26^{c}$.