1 Introduction
Sequence set with good correlation is of considerable interest in many applications in communication and radar system. The ideal sequence set should have perfect impulselike autocorrelation as well as allzero crosscorrelation for all pairs of sequences. Unfortunately, the famous Welch bound [23] implies that it is impossible to have impulselike autocorrelation functions and allzero crosscorrelation functions simultaneously in a sequence set.
While the ideal sequence set is unattainable, an alternate compromise is to require that outofphase autocorrelation and crosscorrelation of sequences are equal to zero in a finite zone. Such sequences are referred to as zero correlation zone (ZCZ) sequences which have found many applications in quasisynchronous CDMA (QSCDMA) system[7], ranging system [6]
, channel estimation
[10] and spectrumspreading [14]. Moreover, ZCZ sequences have been deployed as uplinked random access channel preambles in the fourthgeneration cellular standard LTE [8].Generally, an () ZCZ sequence set is characterized by the period of sequences , the set size and the length of zero correlation zone . The TangFanMatsufuji bound [21] implies that the parameters of a ZCZ sequence set must satisfy
This theoretical bound describes the tradeoff between the set size and the length of ZCZ for a fixed period of a sequence set. Increasing the length of ZCZ must be achieved at the expense of reducing the set size and vice versa. A ZCZ sequence set reaching the theoretical bound is called optimal.
It is remarkable that the above theoretical bound does not make any restrictions on the behavior of correlation functions outside ZCZ. We take into account ZCZ sequence sets with allzero crosscorrelations, which are referred to as interferencefree ZCZ (IFZCZ) sequence sets in this paper. It’s possibly beneficial when IFZCZ sequences are deployed in some interferencelimited systems, such as heterogeneous cellular networks (HetNet) [19], multifunction radar system envisaged for autonomous cars [18]. For instance, an envisioned HetNet is composed of many low powered base stations (BS) within the coverage area of conventional BS. With the increasing density of BS in a HetNet, the signals from multiple BS in its neighborhood are superposed to the mobile terminal (MT) leading to severe interferencelimited performance. MT may attept to connect to the closest low powered BS but the strongest signal may come from a conventional BS. On account of some given scenarios of HetNet, the delays of conventional cell signals may lay in a correlation zone whose length is hard to predict. IFZCZ sequence set with proper parameters is a good candidate for these scenarios.
A series of papers are devoted to the design of IFZCZ sequence sets. In [15, Th.4], Matsufuji et al. proposed optimal IFZCZ sequence sets with restriction that and must be relatively prime. In [16, Th.4], Mow proposed optimal IFZCZ sequence set, where must be a squarefree integer. Recently in [24, Construction 2], Zhang indicated that it is not necessary for to be squarefree. In [2, Construction A], Brozik proposed suboptimal IFZCZ sequence sets through the theory of finite Zak transform (FZT). All sequences in these sets have period and set size . If is a prime, this construction is optimal with . If is not a prime, , where is an arbitrary nontrivial factor of . An extension of construction A, called construction A’, was also proposed in [2, Construction A’]. The IFZCZ sequence sets in construction A’ have parameters , where is a nontrivial factor of . In [3, Construction B], Brozik proposed an optimal construction of IFZCZ sequence sets by FZT. In [17, Equ.2], Popovi presented a general construction including all aforementioned constructions of optimal IFZCZ sequence sets.
The Zak transform is named by Zak, who studied it systematically for applications in solidstate physics [25]. After Janssen’s work [11], it began to be used in digital signal processing. Meanwhile, the Zak transform has been used for numerous applications in signal and echo analysis, ambiguity function[20], WeylHeisenberg expansions[12, 13, 22], and the design of sequence [2, 3, 4, 1]. Moreover, the recently proposed orthogonal time frequency space (OTFS) modulation technique [9] multiplexes QAM information in Zak space.
Inspired by the excellent idea given in [2], we propose a new construction of optimal IFZCZ sequence sets. The size and the period of sequences in new construction are both the same as those in [2]. Note that the Zak space constructions of IFZCZ sequence sets in [2] are not optimal except for a special case. The optimality of the proposed construction in this paper is guaranteed by a newly designed lattice tessellation in Zak space.
In concluding remarks of [17], it concluded that the general construction in [17] is the “most general possible construction of the sequence set having jointly the properties of allzero crosscorrelation, zero autocorrelation zone, complementarity, and optimality”. The proposed construction in this paper shares the same properties, but it is different from the general construction [17] of optimal IFZCZ sequence sets from the perspective of FZT. For general construction [17], the nonzero values of Zak spectrum of any sequence are all in a certain row, which depends on the index of sequence. For our new construction, there is only one nonzero element in each column of Zak spectra, and the rows with nonzero elements are equidistantly positioned. Moreover, the sparse and highly structured Zak and Fourier spectra of the new construction can decrease the computational complexity of the implementation of the banks of matched filters by FZT algorithm [2] and DFT algorithm [17]. Besides, the alphabet size in the general construction [17] cannot be smaller than the period of the sequences, while the alphabet size of the new construction here can be a factor of the period of the sequences.
The rest of this paper is organized as follows. The basic definitions and essential notations will be introduced in Section 2. In Section 3 we propose a new construction of optimal IFZCZ sequence sets based on constant magnitude sequences, and give some properties of the new construction. In Section 4, we give the Zak spectra analysis of known constructions and the comparisons of the new construction with known constructions. Finally, Section 5 concludes the paper.
2 The Basic Definitions and Notations
In this section, we introduce some basic definitions and notations of IFZCZ sequence set and Zak transform. Throughout the paper, is the th root of unity.
2.1 ZCZ Sequence Set
Let be a sequence set with complex sequences of period . We first define the correlation of sequences.
Definition 1.
Let and be two complex sequences of length . The crosscorrelation between and at shift is defined by
(1) 
where is taken modulo and the symbol denotes the complex conjugation. When , the autocorrelation of at shift is denoted by .
The length of zero correlation zone (ZCZ) of the set is defined by
is referred to as an ZCZ sequence set. It is clear . To determine the value of , it suffices to compute the correlation function of sequence set with , i.e.,
The parameters of a ZCZ sequence set must satisfy the following theoretical bound.
Fact 1.
(TangFanMatsufuji bound [21]) For any ZCZ sequence set, we have
(2) 
Furthermore, an ZCZ sequence set is said to be optimal if .
Definition 2.
A sequence set is referred to as an interferencefree (IF) sequence set if the crosscorrelation of any two distinct sequences in is always zero.
An ZCZ sequence set is referred to as IFZCZ sequence set if the crosscorrelation of any two distinct sequences in is always zero. It is obvious that the parameters of an IFZCZ sequence set must also satisfy the above TangFanMatsufuji bound.
2.2 Finite Zak Transform
In addition to the traditional method to study the sequences in time and Fourier space, another approach to study the sequences in Zak space was proposed in [2, 3, 4, 5].
Suppose for the remainder of this paper that , where and are positive integers, and set , for , .
Definition 3.
The finite Zak transform (FZT) [25] of sequence is defined by
(3) 
If we set as the entry of an matrix at row and column , it is much simple to understand the FZT by the product of the matrices. The sequence can be reexpressed by an matrix , where the entry , i.e,
Let be the DFT matrix of order . It is straightforward that
If and , the FZT is identical to the DFT. If and , the FZT of is identical to the original sequence . Thus, the FZT is a primary timefrequency representation which can concurrently encodes both the time and the frequency information about a sequence.
Similar to the inverse DFT, we can define the inverse FZT, where
(4) 
The sequence can be recovered from the inverse FZT.
2.3 FZT and Correlation of Sequences
The relationship between the Zak spectra and the Fourier spectra of the sequence can be given by the following formula.
(5) 
For sequnces and of length , their crosscorrelation at shift can be calculated by Definition 1. We take as a sequence of length , denoted by . The relationship between the Zak spectra of and and the Zak spectra of their correlation sequence is given below.
Note that in formula (6) may be less than 0, which is not well defined. On the other hand, by extending the definition of the FZT, it is shown that FZT is quasiperiodic in the time variable [2], i.e,
(7) 
It is much clear to reexpress the formula (6) as following:
(8) 
From Fact 2, the correlation of the sequences can be studied by the FZT. Several Zak space constructions of IFZCZ sequence sets were proposed in [2, 3], where the ideas are based on the following observations.

For the case , we use and to denote the sequence of autocorrelation and its FZT respectively. If the entries of are all zeroes except the first column, the length of ZCZ of sequences must be equal to where is a positive integer. The optimality of IFZCZ sequence sets is depended on the value .
Note that the Zak space constructions of IFZCZ sequence sets in [2] are not optimal except for a special case. We will propose a new construction of optimal IFZCZ sequence set, in which the size and the length of sequences are both the same as those in [2]. The optimality of the new construction is guaranteed by a newly designed lattice tessellation in Zak space.
3 Main Construction
By extending the excellent idea in [2], we propose a construction of optimal IFZCZ sequence sets in this section. we first show the properties of sequences in the new construction, and then give the detailed proof.
3.1 Main results
For positive intergers and , is a set containing sequences with period . Each sequence in is based on the following constant magnitude sequence and permutation:

is a complex sequence with unit magnitude elements of period for .

is an arbitrary permutation of the set for .
Let be the th sequence of , whose th () element is defined as
(9) 
for and .
Theorem 1.
is an optimal IFZCZ sequence set.
Zak spectra of sequences in are given below.
Theorem 2.
Sequence in set has sparse and highly structured Zak spectra:
(10) 
where .
From Zak spectra in Theorem 2, the correlation of the sequences can be determined by the following results.
Corollary 1.
For sequence and in and shift , we have the crosscorrelation
for , and the autocorrelation
Corollary 2.
Fourier spectra of sequence in set are determined as following.
(11) 
where and .
Remark 1.
If we choose the sequence such that for all and , then the th element of sequence in can be written in the form
for and . In this case, the alphabet size of sequences in is and every sequence in has binary Zak spectra. The sparse and binary support of the Zak transform facilitates sequence storage.
From Theorem 2 and Corollary 2, it can be easily seen that both the Zak and Fourier spectra of sequences in are sparse and with certain structure, but the expression of the nonzero Zak spectra is much simpler than that of Fourier spectra. This is the reason why FZT is employed to study the IFZCZ sequence set, instead of DFT. We use the following example to illustrate the Zak spectra of sequences in our construction.
Example 1.
Let , , and . There are two sequences in the set :
From Theorem 2, their Zak spectra can be respectively given below.
The FZTs of crosscorrelation and autocorrelation and are given as following.
By the inverse FZT, we can obtain the crosscorrelation and the autocorrelation and from and , respectively:
It is clear that the sequence set is an optimal IFZCZ sequence set.
Remark 2.
Note that the IFZCZ set proposed [2, Example 3] cannot reach the TangFanMatsufuji bound with the sequence length and set size , while the sequence set in Example 2 from our construction is optimal with the same length and size parameters.
Similar to the IFZCZ sequence set given in [17, 2], the construction proposed here is also a periodically complementary sequence set.
Corollary 3.
is a periodically complementary sequence set, i.e.,
for .
3.2 Proofs for the Main results
Let in this subsection. We first compute the FZT of the sequence in our construction.
Proof of Theorem 2. By the definition of FZT, we have
(12) 
for , where is the delta function such that and for .
Note that for sequence , the positions of the nonzero elements in matrix must satisfy . In other words, the entries of are all zeroes except for and .
Moreover, for each column , there is a unique such that
so there is only one nonzero element in each column of matrix . For each row , there is a unique nonzero element in this row if and only if . Otherwise, the elements in row must be all zeroes.
Proof of Corollary 1. The FZT of the crosscorrelation of sequences and can be calculated by applying the formula (8).
The row with nonzero element of Zak spectra matrix must satisfy . If , it is clear , we obtain
for . By applying the inverse FZT in (4), we obtain the crosscorrelation of and :
Thus the sequence set must be interference free.
If , we immediately have , since for .
If and , there is only one nonzero element in th row, so the product of and must be zero for . Thus we have
If and , by applying formula (16), we have
Now we can calculate the periodic autocorrelation of by inverse FZT in (4), i.e.,
For , the fact for leads to
For , since equals if for and otherwise, we have
Thus,
(13) 
which complete the proof.
From Corollary 1, we know the length of ZCZ in is , which is optimal with respect to the TangFanMatsufuji bound, so Theorem 1 is proved.
Proof of Corollary 2. Fourier spectra of sequences in can be determined by their Zak spectra in (15) and the relationship between the Zak and Fourier spectra in (5):
If , we have for , so it is clear
If , we have if and only if . Then we obtain the nonzero Fourier spectra:
which complete the proof.
4 Zak Spectra Analysis of Known Constructions and Comparisons
There were several constructions of the optimal IFZCZ sequence sets. In particular, Popovi [17] proposed a general construction including all the known optimal IFZCZ sequence sets introduced in [15, 16, 3, 24]. We will give Zak spectra analysis of the sequences in [17] in this section. The results show that the lattice tessellations in Zak space of the known general construction is different from our new construction.
4.1 Zak Spectra Analysis of Known Constructions
The general construction [17] can be reexpressed in the following manner. For positive integer and , each sequence is based on the following perfect sequence and functions:

is an arbitrary perfect sequence of length for .

is an arbitrary permutation of the set .

is a function from the set to the set such that (mod ).
The th element of sequence is defined as
(14) 
for and .
Remark 3.
Theorem 3.
Sequence has sparse and highly structured Zak spectra:
(15) 
for .
Proof.
By the definition of FZT, we have
(16) 
The result follows that equals if and otherwise. ∎
From Theorem 3, the elements of th row in Zak spectra matrix of sequence are all nonzeroes if , and the elements are all zeroes for other rows. Thus the lattice tessellations in Zak space of the known general construction are different from our new construction.
Similar to our new construction, the properties of sequences can be well analyzed by their Zak spectra and Fourier spectra. Since they have been well studied in [17], we just list the properties without the proof as follows.
Fourier spectra of sequence :
(17) 
where is also a perfect sequence of length , and is the DFT of .
Crosscorrelation of sequence :
Remark 4.
The following example is used to illustrate the Zak spectra of sequences .
Comments
There are no comments yet.