# Deconstructing word embedding algorithms

Kian Kenyon-Dean†
BMO AI Capabilities Team
Bank of Montreal - Toronto, Ontario
<EMAIL_ADDRESS>
&Edward Newell∗, Jackie Chi Kit Cheung
Mila - Québec AI Institute
McGill University - Montréal, Québec
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Kian and Edward contributed equally. $\dagger$ This work was pursued while
Kian was a member of Mila.

###### Abstract

Word embeddings are reliable feature representations of words used to obtain
high quality results for various NLP applications. Uncontextualized word
embeddings are used in many NLP tasks today, especially in resource-limited
settings where high memory capacity and GPUs are not available. Given the
historical success of word embeddings in NLP, we propose a retrospective on
some of the most well-known word embedding algorithms. In this work, we
deconstruct Word2vec, GloVe, and others, into a common form, unveiling some of
the common conditions that seem to be required for making performant word
embeddings. We believe that the theoretical findings in this paper can provide
a basis for more informed development of future models.

##  1 Introduction

The advent of efficient uncontextualized word embedding algorithms (e.g.,
Word2vec Mikolov et al. (2013) and GloVe Pennington et al. (2014)) marked a
historical breakthrough in NLP. Countless researchers employed word embeddings
in new models to improve results on a multitude of NLP problems. In this work,
we provide a retrospective analysis of these groundbreaking models of the
past, which simultaneously offers theoretical insights for how future models
can be developed and understood. We build on the theoretical work of Levy and
Goldberg (2014), proving that their findings on the relationship between
pointwise mutual information (PMI) and word embeddings go beyond Word2vec and
singular value decomposition.

In particular, we generalize several word embedding algorithms into a common
form by proposing the low rank embedder framework. We deconstruct each
algorithm into its constituent parts, and find that, despite their many
different hyperparameters, the algorithms collectively intersect upon the
following two key design features. First, vector-covector dot products are
learned to approximate PMI statistics in the corpus. Second, modulation of the
loss gradient, directly or indirectly, is necessary to balance weak and strong
signals arising from the highly imbalanced distribution of corpus statistics.

These findings can provide an informed basis for future development of both
new embedding algorithms and deep contextualized models.

##  2 Fundamental concepts

We begin by formally defining embeddings, their vectors and covectors (also
known as “input” and “output” vectors Rong (2014); Nalisnick et al. (2016)),
and pointwise mutual information (PMI).

#### Embedding.

In general topology, an embedding is understood as an injective structure
preserving map, $f:X\rightarrow Y$, between two mathematical structures $X$
and $Y$. A word embedding algorithm ($f$) learns an inner-product space ($Y$)
to preserve a linguistic structure within a reference corpus of text,
$\mathcal{D}$ ($X$), based on a vocabulary, $\mathcal{V}$. The structure in
$\mathcal{D}$ is analyzed in terms of the relationships between words induced
by their co-appearances, according to a certain definition of context. In such
an analysis, each word figures dually: (1) as a focal element inducing a local
context; and (2) as elements of the local contexts induced by focal elements.
To make these dual roles explicit, we distinguish two copies of the
vocabulary: the focal, or term, words $\mathcal{V}_{T}$, and the context words
$\mathcal{V}_{C}$.

Word embedding consists of two maps:

$\displaystyle\begin{split}\mathcal{V}_{C}&\longrightarrow\mathbb{R}^{1\times
d}\qquad\mathcal{V}_{T}\longrightarrow\mathbb{R}^{d\times 1}\\\
i&\longmapsto\langle{i}|\quad\;\>\>\,\qquad
j\longmapsto|{j}\rangle.\end{split}$

We use Dirac notation to distinguish vectors $|{j}\rangle$, associated to
focal words, from covectors $\langle{i}|$, associated to context words. In
matrix notation, $|{j}\rangle$ corresponds to a column vector and
$\langle{i}|$ to a row vector. Their inner product is $\langle{i}|{j}\rangle$.
We later demonstrate that many word embedding algorithms, intentionally or
not, learn a vector space where the inner product between a focal word $j$ and
context word $i$ aims to approximate their PMI in the reference corpus:
$\langle{i}|{j}\rangle\approx\mathrm{PMI}(i,j)$.

#### Pointwise mutual information (PMI).

PMI is a commonly used measure of association in computational linguistics,
and has been shown to be consistent and reliable for many tasks Terra and
Clarke (2003). It measures the deviation of the cooccurrence probability
between two words $i$ and $j$ from the product of their marginal
probabilities:

$\begin{split}\mathrm{PMI}(i,j):=\ln\frac{p_{ij}}{p_{i}p_{j}}=\ln\frac{NN_{ij}}{N_{i}N_{j}},\end{split}$
(1)

where $p_{ij}$ is the probability of word $i$ and word $j$ cooccurring (for
some notion of cooccurrence), and where $p_{i}$ and $p_{j}$ are marginal
probabilities of words $i$ and $j$ occurring. The empirical PMI can be found
by replacing probabilities with corpus statistics. Words are typically
considered to cooccur if they are separated by no more than $w$ words;
$N_{ij}$ is the number of counted cooccurrences between a context $i$ and a
term $j$; $N_{i}$, $N_{j}$, and $N$ are computed by marginalizing over the
$N_{ij}$ statistics.

Model | $\frac{\partial f_{ij}}{\partial\psi_{ij}}$ | $\psi_{ij}$ | $\phi_{ij}$ |  $\langle{i}|{j}\rangle\approx$
---|---|---|---|---
SVD |  $2\cdot\big{[}\psi_{ij}-\phi_{ij}\big{]}$ | $\langle{i}|{j}\rangle$ | $\mathrm{PMI}(i,j)$ |  $\mathrm{PMI}(i,j)$
SGNS |  $(N_{ij}+N_{ij}^{-})\cdot\big{[}\sigma(\psi_{ij})-\sigma(\phi_{ij})\big{]}$ | $\langle{i}|{j}\rangle$ | $\ln\frac{N_{ij}}{N_{ij}^{-}}$ |  $\mathrm{PMI}(i,j)-\ln k$
GloVe |  $2h(N_{ij})\cdot\big{[}\psi_{ij}-\phi_{ij}\big{]}\quad\;$ | $\langle{i}|{j}\rangle+b_{i}+b_{j}$ | $\ln N_{ij}$ |  $\mathrm{PMI}(i,j)$
LDS |  $4h(N_{ij})\cdot\Big{[}\psi_{ij}-\phi_{ij}+C\Big{]}$ | $\lVert\langle{i}|+|{j}\rangle^{\intercal}\rVert^{2}$ | $\ln N_{ij}$ |  $d\mathrm{PMI}(i,j)-d\gamma$
Swivel |  $\sqrt{N_{ij}}\cdot\Big{[}\psi_{ij}-\phi_{ij}\Big{]}$ |  $\langle{i}|{j}\rangle$ | $\mathrm{PMI}(i,j)$ |  $\mathrm{PMI}(i,j)$
$1\cdot\sigma\Big{(}\psi_{ij}-\phi_{ij}\Big{)}$ | $\mathrm{PMI}^{*}(i,j)$ |  $\mathrm{PMI}^{*}(i,j)$
Table 1: Comparison of low rank embedders. Final column shows the value of
$\langle{i}|{j}\rangle$ at $\frac{\partial f_{ij}}{\partial\psi_{ij}}=0$.
GloVe and LDS set $f_{ij}=0$ when $N_{ij}=0$; $h(N_{ij})$ is a weighting
function sublinear in $N_{ij}$. Swivel takes one form when $N_{ij}>0$ (first
row) and another when $N_{ij}=0$ (second row). $N_{ij}^{-}$ is the number of
negative samples; in SGNS, $N_{ij}^{-}\propto N_{i}N_{j}$, and both $N_{ij}$
and $N_{ij}^{-}$ are tempered by undersampling and unigram smoothing.

##  3 Word embedding algorithms

We will now introduce the low rank embedder framework for deconstructing word
embedding algorithms, inspired by the theory of generalized low rank models
Udell et al. (2016). We unify several word embedding algorithms by observing
them all from the common vantage point of their global loss function. Note
that this framework is used for theoretical analysis, not necessarily
implementation.

The global loss function for a low rank embedder takes the following form:

$\displaystyle\mathcal{L}$
$\displaystyle=\sum_{\mathclap{(i,j)\in\mathcal{V}_{C}\\!\times\\!\mathcal{V}_{T}}}f_{ij}\Big{(}\;\psi(\langle{i}|,|{j}\rangle),\;\;\phi(i,j)\;\Big{)},$
(2)

where $\psi(\langle{i}|,|{j}\rangle)$ is a kernel function of learned model
parameters, and $\phi(i,j)$ is some scalar function (such as a measure of
association based on how often $i$ and $j$ appear in the corpus); we denote
these with $\psi_{ij}$ and $\phi_{ij}$ for brevity. As well, $f_{ij}$ are loss
functions that take $\psi_{ij}$ and $\phi_{ij}$ as inputs; all $f_{ij}$
satisfy the property:

$\displaystyle\frac{\partial
f_{ij}}{\partial\psi_{ij}}=0\quad\text{at}\quad\psi_{ij}=\phi_{ij}.$ (3)

The design variable $\phi_{ij}$ is some function of corpus statistics, and its
purpose is to quantitatively measure some relationship between words $i$ and
$j$. The design variable $\psi_{ij}$ is a function of model parameters that
aims to approximate $\phi_{ij}$; i.e., an embedder’s fundamental objective is
to learn $\psi_{ij}\approx\phi_{ij}$, and thus to train embeddings that
capture the statistical relationships measured by $\phi_{ij}$. The simplest
choice for the kernel function $\psi_{ij}$, is to take
$\psi_{ij}=\langle{i}|{j}\rangle$. But the framework allows any function that
is symmetric and positive definite, allowing the inclusion of bias parameters
(e.g. in GloVe) and subword parameterization (e.g. in FastText). We later
demostrate that skip-gram with negative sampling takes
$\phi_{ij}:=\mathrm{PMI}(i,j)-\ln k$ and $\psi_{ij}:=\langle{i}|{j}\rangle$,
and then learns parameter values that approximate
$\langle{i}|{j}\rangle\approx\mathrm{PMI}(i,j)-\ln k$.

To understand the range of models encompassed, it is helpful to see how the
framework relates (but is not limited) to matrix factorization. Consider
$\phi_{ij}$ as providing the entries of a matrix:
$\mathbf{M}:=\left[\phi_{ij}\right]_{ij}$. For models that take
$\psi_{ij}=\langle{i}|{j}\rangle$, we can write
$\hat{\mathbf{M}}=\mathbf{WV}$, where $\mathbf{W}$ is defined as having row
$i$ equal to $\langle{i}|$, and $\mathbf{V}$ as having column $j$ equal to
$|{j}\rangle$. Then, the loss function can be rewritten as:

$\displaystyle\mathcal{L}$
$\displaystyle=\sum_{\mathclap{(i,j)\in\mathcal{V}_{C}\\!\times\\!\mathcal{V}_{T}}}f_{ij}\Big{(}(\mathbf{WV})_{ij},\;\mathbf{M}_{ij}\Big{)}.$

This loss function can be interpreted as matrix reconstruction error, because
the constraint in Eq. 3 means that the gradient goes to zero as
$\mathbf{WV}\approx\mathbf{M}$.

Selecting a particular low rank embedder instance requires key design choices
to be made: we must chose the embedding dimension $d$, the form of the loss
terms $f_{ij}$, the kernel function $\psi_{ij}$, and the association function
$\phi_{ij}$. The derivative of $f_{ij}$ with respect to $\psi_{ij}$, which we
call the characteristic gradient, helps compare models because it exhibits the
action of the gradient yet is symmetric in the parameters. In the Appendix we
show how this derivative relates to gradient descent.

In the following subsections, we present the derivations of $\frac{\partial
f_{ij}}{\partial\psi_{ij}}$, $\psi_{ij}$, and $\phi_{ij}$ for SVD Levy and
Goldberg (2014); Levy et al. (2015), SGNS Mikolov et al. (2013), FastText
(Joulin et al., 2017), GloVe Pennington et al. (2014), and LDS (Arora et al.,
2016). The derivation for Swivel Shazeer et al. (2016) as a low rank embedder
is trivial, as it is already posed as a matrix factorization of PMI
statistics. We summarize the derivations in Table 1.

###  3.1 SVD as a low rank embedder

Singular value decomposition (SVD) of the positive-PMI (PPMI) matrix is used
by Levy and Goldberg (2014); Levy et al. (2015) to produce word embeddings
that perform more or less equivalently to SGNS and GloVe. Converting the PMI
matrix into PPMI is a trivial preprocessing step; $\phi$ is augmented
according to a factor $\alpha=0$ such that
$\phi_{ij}=0\,\,\forall\phi_{ij}\leq\alpha$. We now prove why SVD of the PMI
matrix results in word embeddings with dot products
$\langle{i}|{j}\rangle\approx\mathrm{PMI}(i,j)$, noting that this proof
naturally holds for all augmentations of $\phi$ according to the $\alpha$
factor, including PPMI.

#### Proof.

Truncated SVD provides an optimal solution to problem $\min_{D}\|D-A\|_{F}$
for some integer $K$ less than the dimensionality of matrix $A$ such that
$\mathrm{rank}({D})=K$ Udell et al. (2016). The solution is the truncated SVD
of $A$ where $D=\sum_{k=1}^{K}\sigma_{k}u_{k}v_{k}^{\intercal}$ with $\sigma$
being the $k^{th}$ singular value and $u_{k}$ and $v_{k}$ as the $k^{th}$ left
and right singular vectors.

Within our framework, the truncated SVD of the PMI matrix thus solves the
following loss function (note $A_{ij}=\phi_{ij}=\mathrm{PMI}(i,j)$):

$\mathcal{L}=-\sum_{\mathclap{(i,j)\in\mathcal{V}_{C}\\!\times\\!\mathcal{V}_{T}}}\big{(}\psi_{ij}-\mathrm{PMI}(i,j))^{2},$
(4)

where $\psi_{ij}=u_{i}^{\intercal}\Sigma v_{j}$. Allowing the square matrix of
singular values $\Sigma$ to be absorbed into the vectors (as in Levy et al.
(2015)), we have $\langle{i}|=u_{i}$ and $|{j}\rangle=\Sigma v_{j}$. Thus,
taking the derivative $\frac{\partial f_{ij}}{\partial\psi_{ij}}$ (noting that
$f_{ij}$ here is simply the squared difference between $\psi_{ij}$ and
$\phi_{ij}$) and setting it equal to zero we observe:

$\langle{i}|{j}\rangle=\mathrm{PMI}(i,j).$ (5)

###  3.2 SGNS as a low rank embedder

Mikolov et al. (2013) proposed skip-gram with negative sampling with the
following loss function:

$\mathcal{L}=-\sum_{\mathclap{(i,j)\in
D_{2}}}\Big{\\{}\ln\sigma\langle{i}|{j}\rangle+\sum_{\ell=1}^{k}\mathbb{E}\Big{[}\ln(1-\sigma\langle{i^{\prime}_{\ell}}|{j}\rangle)\Big{]}\Big{\\}},$

where $\sigma$ is the logistic sigmoid function, $D_{2}$ is a list containing
each cooccurrence of a context-word $i$ with a focal word $j$ in the corpus,
and the expectation is taken by drawing $i^{\prime}_{\ell}$ from the
(smoothed) unigram distribution to generate $k$ “negative samples” for a given
focal-word Mikolov et al. (2013). We will demonstrate that SGNS is a low rank
embedder with $\langle{i}|{j}\rangle\approx\mathrm{PMI}-\ln k$.

#### Proof.

We can transform the loss function by counting the number of times each pair
occurs in the corpus, $N_{ij}$, and the number of times each pair is drawn as
a negative sample, $N_{ij}^{-}$, while indexing the sum over the set
$\mathcal{V}_{C}\\!\times\\!\mathcal{V}_{T}$:

$\mathcal{L}=-\sum_{\mathclap{(i,j)\in\mathcal{V}_{C}\\!\times\\!\mathcal{V}_{T}}}\Big{\\{}N_{ij}\ln\sigma\langle{i}|{j}\rangle+N_{ij}^{-}\ln(1-\sigma\langle{i}|{j}\rangle)\Big{\\}}.$

The global loss is almost in the required form for a low rank embedder (Eq.
2), and the appropriate setting for the model approximation function is
$\psi_{ij}=\langle{i}|{j}\rangle$. Calculating the partial derivative with
respect to the model approximation function $\psi_{ij}$, following algebraic
manipulation (using the identity $a\equiv(a+b)\sigma(\ln\frac{a}{b})$), we
arrive at the following definition of the characteristic gradient for SGNS as
a low rank embedder, where $\frac{\partial
f_{ij}}{\partial\psi_{ij}}=\frac{\partial\mathcal{L}}{\partial\langle{i}|{j}\rangle}$:

$\displaystyle\frac{\partial\mathcal{L}}{\partial\langle{i}|{j}\rangle}$
$\displaystyle=N_{ij}^{-}\sigma\langle{i}|{j}\rangle-
N_{ij}(1-\sigma\langle{i}|{j}\rangle)$
$\displaystyle=(N_{ij}+N_{ij}^{-})\bigg{[}\sigma\big{(}\langle{i}|{j}\rangle\big{)}-\sigma\big{(}\ln\frac{N_{ij}}{N_{ij}^{-}}\big{)}\bigg{]}$
$\displaystyle=(N_{ij}+N_{ij}^{-})\bigg{[}\sigma\big{(}\psi_{ij}\big{)}-\sigma\big{(}\phi_{ij}\big{)}\bigg{]}.$
(6)

This provides that the association function for SGNS is
$\phi_{ij}=\ln(N_{ij}/N_{ij}^{-})$, since the derivative will be equal to zero
at that point (Eq. 3). However, recall that negative samples are drawn
according to the unigram distribution (or a smoothed variant Levy et al.
(2015)). This means that $N_{ij}^{-}=kN_{i}N_{j}/N$. Therefore, in agreement
with Levy and Goldberg (2014), we find that:

$\displaystyle\phi_{ij}=\ln\frac{N_{ij}N}{N_{i}N_{j}k}=\mathrm{PMI}(i,j)-\ln
k.$ (7)

###  3.3 FastText as a low rank embedder

Proposed by Joulin et al. (2017), FastText’s motivation is orthogonal to the
present work. Its purpose is to provide subword-based representation of words
to improve vocabulary coverage and generalizability of word embeddings.
Nonetheless, it can also be understood as a low rank embedder .

#### Proof.

FastText uses a loss function that is identical to SGNS except that the vector
for each word is taken as the sum of embeddings for all character $n$-grams
appearing in the word, with $3\leq n\leq 6$. Therefore, define $|{j}\rangle$
by $|{j}\rangle\equiv\sum_{g\in z(j)}|{g}\rangle$, where $|{g}\rangle$ is the
vector for $n$-gram $g$, and $z(j)$ is the set of $n$-grams in word $j$.
Covectors are accorded to words directly, so need not be redefined. The loss
function and the derivation of entries for Table 1 is then formally identical
to those for SGNS. This provides that $\psi_{ij}=\langle{i}|{j}\rangle$, and,
$\phi_{ij}=\mathrm{PMI}(i,j)-\ln k$.

###  3.4 GloVe as a low rank embedder

GloVe was proposed as an algorithm halfway between sampling methods and matrix
factorization Pennington et al. (2014). Ignoring samples where $N_{ij}=0$,
GloVe uses the following loss function:

$\displaystyle\begin{split}\mathcal{L}=\sum_{ij}h(N_{ij})\Big{(}\langle{i}|{j}\rangle+b_{i}+b_{j}-\ln
N_{ij}\Big{)}^{2}\\\ \end{split}$ (8)

where $b_{i}$ and $b_{j}$ are learned bias parameters, and $h(N_{ij})$ is a
weighting function sublinear in $N_{ij}$.

GloVe can be cast as a low rank embedder by using the model approximation
function as a kernel with bias parameters, and setting the association measure
to simply be the objective:

$\displaystyle\psi_{ij}=\big{[}\,\langle{i}|_{1}\,\cdots\,\langle{i}|_{d}\>b_{i}\;1\,\big{]}$
$\displaystyle\cdot\big{[}\,|{j}\rangle_{1}\cdots|{j}\rangle_{d}\>\>1\>\>b_{j}\>\big{]}^{\intercal},$
$\displaystyle\text{and}\quad\phi_{ij}$ $\displaystyle=\ln N_{ij}.$

#### Proof.

Observe an optimal solution to the loss function, when $\frac{\partial
f_{ij}}{\partial\psi_{ij}}=0$:

$\displaystyle\frac{\partial f_{ij}}{\partial\psi_{ij}}$
$\displaystyle=2h(N_{ij})\Big{[}\langle{i}|{j}\rangle+b_{i}+b_{j}-\ln
N_{ij}\Big{]}=0$ $\displaystyle\implies\langle{i}|{j}\rangle+b_{i}+b_{j}=\ln
N_{ij}.$

Multiplying the log operand by $1$:

$\displaystyle\langle{i}|{j}\rangle+b_{i}$
$\displaystyle+b_{j}=\ln\left(\frac{N_{i}N_{j}}{N}\frac{N}{N_{i}N_{j}}N_{ij}\right)$
(9)
$\displaystyle=\ln\frac{N_{i}}{\sqrt{N}}+\ln\frac{N_{j}}{\sqrt{N}}+\mathrm{PMI}(i,j).$
(10)

On the right side, we have two terms that depend respectively only on $i$ and
$j$, which are candidates for the bias terms. Based on this equation alone, we
cannot draw any conclusions. However, empirically the bias terms are in fact
very near $\frac{N_{i}}{\sqrt{N}}$ and $\frac{N_{j}}{\sqrt{N}}$, and PMI is
observed to be normally distributed, as can be seen in Fig. 1. This means that
Eq. 10 provides $\langle{i}|{j}\rangle\approx\mathrm{PMI}(i,j)$.

Figure 1: A) Histogram of $\mathrm{PMI}(i,j)$ values, for all pairs $(i,j)$
with $N_{ij}\\!>\\!0$. B) Scatter plot of GloVe’s learned biases. Both from a
Wikipedia 2018 corpus.

Analyzing the optimum of GloVe’s loss function yields important insights.
First, GloVe can be added to the list of low rank embedders that learn a
bilinear parameterization of PMI. Second, we can see why such a
parameterization is advantageous. Generally, it helps to standardize features
of low rank models Udell et al. (2016), and this is essentially what
transforming cooccurrence counts into PMI achieves. Thus, PMI can be viewed as
a parameterization trick, providing an approximately normal target association
to be modelled.

###  3.5 LDS as a low rank embedder

Arora et al. (2016) introduced an embedding perspective based on generative
modelling with random walks through a latent discourse space (LDS). LDS
provided a theoretical basis for the performant SIF document embedding
algorithm, developed soon afterwards Arora et al. (2017). We now demonstrate
that LDS is also a low-rank embedder.

#### Proof.

The low rank learning objective for LDS follows directly from Corollary 2.3,
in Arora et al. (2016):

$\begin{split}\mathrm{PMI}(i,j)&=\frac{\langle{i}|{j}\rangle}{d}+\gamma+O(\epsilon).\end{split}$

$\frac{\partial f_{ij}}{\partial\psi_{ij}}$ can be found by straightforward
differentiation of LDS’s loss function:

$\mathcal{L}=\sum_{ij}h(N_{ij})\big{[}\ln
N_{ij}-\left\lVert\langle{i}|+|{j}\rangle^{\intercal}\right\rVert^{2}-C\big{]}^{2},$

where $h(N_{ij})$ is as defined by GloVe. The quadratic term is a valid kernel
function because:

$\displaystyle\frac{\partial
f_{ij}}{\partial\psi_{ij}}=\left\lVert\langle{i}|+|{j}\rangle^{\intercal}\right\rVert^{2}=\langle\tilde{i}|\tilde{j}\rangle,$

where

$\displaystyle\tilde{\langle{i}|}$
$\displaystyle=\Big{[}\sqrt{2}\langle{i}|_{1}\>\,\cdots\;\sqrt{2}\langle{i}|_{d}\;\;\langle{i}|\langle{i}|^{\intercal}\;\;\;\;1\;\;\;\;\;\Big{]},$
$\displaystyle\tilde{|{j}\rangle}$
$\displaystyle=\Big{[}\sqrt{2}|{j}\rangle_{1}\;\cdots\;\sqrt{2}|{j}\rangle_{d}\;\;\;\,\;1\;\;\;\;|{j}\rangle^{\intercal}|{j}\rangle\;\Big{]}^{\intercal}.$

##  4 Related work

Our derivation of SGNS’s solution is inspired by the work of Levy and Goldberg
(2014), who proved that skip-gram with negative sampling (SGNS) Mikolov et al.
(2013) was implicitly factorizing the $\mathrm{PMI}-\ln k$ matrix. However,
they required additional assumptions for their derivation to hold. Li et al.
(2015) explored relations between SGNS and matrix factorization, but their
derivation diverges from Levy and Goldberg’s result and masks the connection
between SGNS and other low rank embedders. Other works have also explored
theoretical or empirical relationships between SGNS and GloVe Shi and Liu
(2014); Suzuki and Nagata (2015); Levy et al. (2015); Arora et al. (2016).

##  5 Discussion

We observe common features between each of the algorithms (Table 1). In each
case, $\frac{\partial f_{ij}}{\partial\psi_{ij}}$ takes the form
$(\mathrm{multiplier})\cdot(\mathrm{difference})$. The multiplier is always a
“tempered” version of $N_{ij}$ (or $N_{i}N_{j}$); that is, it increases
sublinearly with $N_{ij}$.

For each algorithm, $\phi_{ij}$ is equal to PMI or a scaled log of $N_{ij}$.
Yet, the choice of $\psi_{ij}$ in combination with $\phi_{ij}$ provides that
every model is optimized when $\langle{i}|{j}\rangle$ tends toward
$\mathrm{PMI}(i,j)$ (with or without a constant shift or scaling). We
demonstrated that the optimum for SGNS (and FastTest) is equivalent to the
shifted PMI (§3.2). For GloVe, we showed that incorporation of the bias terms
captures the unigram counts needed for PMI (§3.4). A similar property is found
in LDS with regards to the L2 norm in its learning objective Arora et al.
(2016). Thus, these algorithms all converge on two key points: (1) an optimum
in which model parameters are bilinearly related to PMI; and, (2) the
weighting of $\frac{\partial f_{ij}}{\partial\psi_{ij}}$ by some tempered form
of $N_{ij}$.

##  6 Conclusion

Our low rank embedder framework has evoked the commonalities between many word
embedding algorithms. We believe a robust understanding of these algorithms is
a prerequisite for theoretically motivated development of deeper models.
Indeed, we offer the following conjectures: deep embedding models would
benefit by incorporating PMI statistics into their training objective; such
models will also benefit from sub-linear scaling of frequent word pairs during
training; and, lastly, such models would benefit by learning representations
with a dual character, as all of the embedding algorithms we described do by
learning vectors and covectors.

## Acknowledgements

This work is supported by the Fonds de recherche du Québec – Nature et
technologies and by the Natural Sciences and Engineering Research Council of
Canada. The last author is supported in part by the Canada CIFAR AI Chair
program.

## References

  * Arora et al. (2016) Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2016.  A latent variable model approach to pmi-based word embeddings.  _Transactions of the Association for Computational Linguistics_ , 4:385–399.
  * Arora et al. (2017) Sanjeev Arora, Yingyu Liang, and Tengyu Ma. 2017.  A simple but tough-to-beat baseline for sentence embeddings.  _International Conference on Learning Representations_.
  * Joulin et al. (2017) Armand Joulin, Edouard Grave, and Piotr Bojanowski Tomas Mikolov. 2017.  Bag of tricks for efficient text classification.  _European Association for Computational Linguistics 2017_ , page 427\.
  * Levy and Goldberg (2014) Omer Levy and Yoav Goldberg. 2014.  Neural word embedding as implicit matrix factorization.  In _Advances in Neural Information Processing Systems_ , pages 2177–2185.
  * Levy et al. (2015) Omer Levy, Yoav Goldberg, and Ido Dagan. 2015.  Improving distributional similarity with lessons learned from word embeddings.  _Transactions of the Association for Computational Linguistics_ , 3:211–225.
  * Li et al. (2015) Yitan Li, Linli Xu, Fei Tian, Liang Jiang, Xiaowei Zhong, and Enhong Chen. 2015\.  Word embedding revisited: a new representation learning and explicit matrix factorization perspective.  In _Proceedings of the 24th International Conference on Artificial Intelligence_ , pages 3650–3656. AAAI Press.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _Advances in neural information processing systems_ , pages 3111–3119.
  * Nalisnick et al. (2016) Eric Nalisnick, Bhaskar Mitra, Nick Craswell, and Rich Caruana. 2016.  Improving document ranking with dual word embeddings.  In _Proceedings of the 25th International Conference Companion on World Wide Web_ , pages 83–84. International World Wide Web Conferences Steering Committee.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on Empirical Methods in Natural Language Processing_ , pages 1532–1543.
  * Rong (2014) Xin Rong. 2014.  Word2vec parameter learning explained.  _arXiv preprint arXiv:1411.2738_.
  * Shazeer et al. (2016) Noam Shazeer, Ryan Doherty, Colin Evans, and Chris Waterson. 2016.  Swivel: Improving embeddings by noticing what’s missing.  _arXiv preprint arXiv:1602.02215_.
  * Shi and Liu (2014) Tianze Shi and Zhiyuan Liu. 2014.  Linking glove with word2vec.  _arXiv preprint arXiv:1411.5595_.
  * Suzuki and Nagata (2015) Jun Suzuki and Masaaki Nagata. 2015.  A unified learning framework of skip-grams and global vectors.  In _Proceedings of the 53rd Annual Meeting of the ACL and the 7th IJCNLP (Volume 2: Short Papers)_ , volume 2, pages 186–191.
  * Terra and Clarke (2003) Egidio Terra and Charles LA Clarke. 2003.  Frequency estimates for statistical word similarity measures.  In _Proceedings of the 2003 Conference of NAACL-HLT - Volume 1_ , pages 165–172. Association for Computational Linguistics.
  * Udell et al. (2016) Madeleine Udell, Corinne Horn, Reza Zadeh, Stephen Boyd, et al. 2016.  Generalized low rank models.  _Foundations and Trends in Machine Learning_ , 9(1):1–118.

##  Appendix A Appendix

###  A.1 On the characteristic gradient

The relationship between $\frac{\partial f_{ij}}{\partial\psi_{ij}}$ and the
gradient descent actions taken during learning requires simply taking the next
step in the chain rule during differentiation. For simplicity of exposition,
we will assume, like SGNS and Swivel, that $\psi_{ij}=\langle{i}|{j}\rangle$,
although the motivation of taking this derivative holds for any definition of
$\psi_{ij}$, provided that it is a kernel function of the model parameters.

By examining the derivative $\frac{\partial
f_{ij}}{\partial\langle{i}|{j}\rangle}$ we observe the primary objective of
the model (to approximate dot products), and how this objective symmetrically
updates vectors and covectors during learning.

Consider the generic update that occurs for a single $(i,j)$ pair with the
pairwise loss function $f_{ij}$. The gradient descent rule for a single update
to the vector for word $j$, using some learning rate $\eta$, is:

$|{j}\rangle\leftarrow|{j}\rangle-\eta\frac{\partial f_{ij}}{|{j}\rangle},$
(11)

However, since $f_{ij}$ is a function of $\langle{i}|{j}\rangle$ and not of
the vectors or covectors independently, we can use the chain rule to arrive at
the following:

$\displaystyle|{j}\rangle$
$\displaystyle\leftarrow|{j}\rangle-\eta\frac{\partial
f_{ij}}{\partial\langle{i}|{j}\rangle}\frac{\partial\langle{i}|{j}\rangle}{\partial|{j}\rangle}$
(12) $\displaystyle|{j}\rangle$
$\displaystyle\leftarrow|{j}\rangle-\eta\frac{\partial
f_{ij}}{\partial{\langle{i}|{j}\rangle}}\langle{i}|^{\intercal},$ (13)

since $\frac{\partial\langle{i}|{j}\rangle}{\partial|{j}\rangle}=\langle{i}|$.
Symmetrically, we also arrive at, for the updates to covectors:

$\langle{i}|\leftarrow\langle{i}|-\eta\frac{\partial
f_{ij}}{\partial{\langle{i}|{j}\rangle}}|{j}\rangle^{\intercal}.$ (14)

Therefore, taking $\frac{\partial f_{ij}}{\partial\langle{i}|{j}\rangle}$
(more generally, $\frac{\partial f_{ij}}{\partial\psi_{ij}}$) to be the focal
point of analysis in determining the objectives of the low rank embedders is
well grounded.


# New Constructions of Mutually Orthogonal Complementary Sets and
Z-Complementary Code Sets Based on Extended Boolean Functions

Hongyang Xiao, Xiwang Cao  Hongyang Xiao, College of Mathematics, Nanjing
University of Aeronautics and Astronautics, Nanjing, Jiangsu, 211106, China,
<EMAIL_ADDRESS>author. Xiwang Cao, College of Mathematics,
Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu, 211106,
China; Key Laboratory of Mathematical Modeling and High Performance Computing
of Air Vehicles (NUAA), MIIT, Nanjing, 211106, China<EMAIL_ADDRESS>
###### Abstract

Mutually orthogonal complementary sets (MOCSs) and Z-complementary code sets
(ZCCSs) have many applications in practical scenarios such as synthetic
aperture imaging systems and multi-carrier code division multiple access (MC-
CDMA) systems. With the aid of extended Boolean functions (EBFs), in this
paper, we first propose a direct construction of MOCSs with flexible lengths,
and then propose a new construction of ZCCSs. The proposed MOCSs cover many
existing lengths and have non-power-of-two lengths when $q=2$. Our presented
second construction can generate optimal ZCCSs meeting the set size upper
bound. Note that the proposed two constructions are direct without the aid of
any special sequence, which is suitable for rapid hardware generation.

Keywords: Multi-carrier code division multiple access (MC-CDMA)$\cdot$
mutually orthogonal complementary set (MOCS)$\cdot$ Z-complementary code set
(ZCCS)$\cdot$ extended Boolean function (EBF).

Mathematics Subject Classification: 11T71 $\cdot$ 94A60 $\cdot$ 06E30

##  1 Introduction

The concept of Golay complementary pair (GCP) was initiated by Golay in
1961[1]. The aperiodic auto-correlation function (AACF) of a GCP diminishes to
zero for all time shifts except at zero. In 1972, Tseng and Liu generalized
the concept of GCP to Golay complementary sets (GCSs) and MOCSs [2]. An
$(N,L)$-GCS is a set of $N$ $(\geq 2)$ sequences of length $L$ with the
property that their AACF is zero for any non-zero time shifts and an
$(M,N,L)$-MOCS is a collection of $M$ GCSs, in which every GCS has $N$
sequences of length $L$ such that any two distinct GCSs are orthogonal. In
1988, Suehiro and Hatori proposed the concept of $(N,N,L)$-complete
complementary codes (CCCs) whose set size achieves the theoretical upper bound
of MOCSs (i.e., $M\leq N$)[3]. Due to the ideal correlation properties, MOCSs
have been applied in many practical scenarios such as synthetic aperture
imaging systems[4], OFDM-CDMA systems [5] and MC-CDMA systems [8, 6, 7].

In recent years, the construction of MOCSs has attracted extensive attention
in sequence design community. Generalized Boolean functions (GBFs), usually
are utilized to construct MOCSs. This is initiated by the pioneer work of
Davis and Jedwab in [9] which proposed a direct construction of $2^{h}$-ary
$(h>0)$ GCPs of length $2^{m}$ $(m>0)$. Paterson extended the idea of [9] to
construct $q$-ary (for even $q$) GCPs [10]. Further constructions of GCPs and
GCSs based on GBFs have been proposed in [11, 12]. In [13], Tathinakumar and
Chaturvedi proposed a direct construction of $q$-ary CCCs of length $2^{m}$ by
extending Paterson’s idea in [10]. Wu et al. [14] designed MOCSs with non-
power-of-two lengths. Later, a number of direct constructions of $q$-ary MOCSs
with non-power-of-two lengths are presented in [15, 16]. Sarkar et al. in [17]
proposed $(p^{n+1},p^{n+1},p^{m})$-CCCs via $q$-ary functions
($\mathbb{Z}_{p}^{m}\rightarrow\mathbb{Z}_{q}$), where $p$ is a prime number
and $q$ is a positive multiple of $p$. But these CCCs only have prime power
lengths. In [18], Sarkar et al. designed CCCs of length
$p_{1}^{m_{1}}p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}$ (where each $p_{i}$ is a
prime and $m_{i}$ is a positive integer) using multivariable functions
(MVFs)[18]. This direct construction can generate $q$-ary CCCs of all possible
lengths. However, in the case of $q=2,$ only binary CCC of length of form
$2^{m}$ $(m\in\mathbb{Z})$ has been constructed [18]. Apart from these direct
constructions of MOCSs, there are some other indirect methods to construct
MOCSs such as interleaving, concatenation, paraunitary (PU) matrices,
Kronecker product, extended correlation, etc. [19, 22, 23, 24, 20, 21].
However, the generated MOCSs may not be friendly for hardware generation due
to their large space and time requirements. So how to construct MOCSs with
flexible lengths is still an open problem.

Since the set size is constrained by the number of sub-carrier in MOCSs, which
prevents the communication system from supporting a large number of users, Fan
_et al._ proposed the concept of ZCCSs in [25]. The reason why ZCCSs have
large set sizes is that there is a zero correlation zone (ZCZ) in the
aperiodic cross-correlation and auto-correlation. For an $(M,N,L,Z)$-ZCCS, it
holds that $M\leq N\lfloor L/Z\rfloor$ and it is optimal if the upper bound is
achieved, where $M,$ $N,$ $L,$ $Z$ refer to the set size, number of sub-
carrier, length and ZCZ width, respectively. Especially, an $(M,N,L,Z)$-ZCCS
is called an MOCS if $Z=L$. In the literature, ZCCSs are constructed by using
direct and indirect methods. In [26], Wu et al. proposed ZCCSs with length
$2^{m}$ ($m>0$) based on GBFs, then they expanded the parameters of ZCCSs in
2021 [27]. Several GBFs based constructions of ZCCSs are presented in the
literature [30, 29, 28, 31]. Additionally, Tian et al. constructed ZCCSs by
using PU matrices in [32]. Yu et al. applied Kronecker product to obtain ZCCSs
in [33]. Das et al. presented a class of ZCCSs by using Butson-type Hadamard
(BH) matrices and optimal Z-paraunitary (ZPU) matrices [34]. Adhikary and
Majhi in [35] employed Hadamard product to construct ZCCSs with new
parameters. Further constructions of ZCCSs have been proposed in [36, 37, 38,
39]. In most previous designs, however, the optimal ZCCSs based on direct
methods have limited lengths and the optimal ZCCSs based on indirect methods
have limited hardware generations. Recently, Shen et al. introduced the
concept of EBF and obtained optimal ZCCSs of length $q^{m}$ [40], where $q\geq
2$ is a positive integer. This work helps us to construct more optimal ZCCSs.

Motivated by the existing works on MOCSs and ZCCSs, in this paper, we
construct $(q^{d^{\prime}},q^{v+d},\gamma)$-MOCSs with flexible lengths and
$(q^{v+d},q^{d},q^{m},q^{m-v})$-ZCCSs by using EBFs, where
$\gamma=a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}$,
$0<d^{\prime}<d<m$, $v<m$, $a_{k}\in\mathbb{Z}_{q}$,
$a_{m}\in\mathbb{Z}^{*}_{q}$ and $q\geq 2$ is a positive integer. According to
the arbitrariness of $q$, the proposed MOCSs cover the result in [18] and have
non-power-of-two lengths when $q=2$. In addition, the resulting MOCSs and
ZCCSs can be obtained directly from EBFs without using tedious sequence
operations. Note that the proposed ZCCSs are optimal with respect to the
theoretical upper bound.

The remainder of this paper is outlined as follows. In Section 2, we give the
notations and definitions that will be used throughout this paper. In Section
3, we show a construction of MOCS with flexible lengths. In Section 4, we
present an construction optimal ZCCS. In Section 5, we make a comparison of
the existing literature with this paper. Finally, we conclude this paper in
Section 6.

##  2 Preliminaries

###  2.1 Notation

  * •

$\mathbb{Z}_{q}=\\{0,1,\cdots,q-1\\}$ is the ring of integers modulo $q$,
where $q\geq 2$ is a positive integer throughout this paper, unless we
specifically point out;

  * •

$\mathbb{Z}^{*}_{q}=\mathbb{Z}_{q}\backslash\\{0\\}$;

  * •

$\mathbb{N}_{m}=\\{1,2,\cdots,m\\}$ is the set with $m$ elements;

  * •

$\xi=e^{2\pi\sqrt{-1}/q}$ is a primitive $q$-th root of unity;

  * •

$\lfloor x\rfloor$ denotes the largest integer lower than or equal to $x$;

  * •

$\lceil x\rceil$ denotes the smallest integer bigger than or equal to $x$;

  * •

Bold small letter $\mathbf{a}$ denotes a sequence of length $L$, i.e.,
$\mathbf{a}=(a_{0},a_{1},\cdots,a_{L-1});$

  * •

$(\cdot)^{*}$ denotes the conjugate of $(\cdot).$

###  2.2 Correlation functions and complementary sequence sets

Assume $\mathbf{a}=(a_{0},a_{1},\cdots,a_{L-1})$ and
$\mathbf{b}=(b_{0},b_{1},\cdots,b_{L-1})$ are $\mathbb{Z}_{q}$-valued
sequences of length $L$, where $a_{i}$ and $b_{i}$ are in the ring
$\mathbf{\mathbb{Z}}_{q}$. The aperiodic cross-correlation function (ACCF)
$R_{\mathbf{a},\mathbf{b}}(\tau)$ between $\mathbf{a}$ and $\mathbf{b}$ at a
time shift $\tau$ is defined as

$R_{\mathbf{a},\mathbf{b}}(\tau)=\left\\{\begin{array}[]{ll}\sum_{i=0}^{L-1-\tau}\xi^{a_{i}-b_{i+\tau}},&0\leq\tau\leq
L-1,\\\
\sum_{i=0}^{L-1+\tau}\xi^{a_{i-\tau}-b_{i}},&-L+1\leq\tau<0.\end{array}\right.$

If $\mathbf{a}=\mathbf{b}$, then $R_{\mathbf{a},\mathbf{b}}(\tau)$ is called
the aperiodic auto-correlation function (AACF), denoted as
$R_{\mathbf{a}}(\tau)$. In addition, by the definition of AACF, we get
$R_{\mathbf{b},\mathbf{a}}(-\tau)=R^{*}_{\mathbf{a},\mathbf{b}}(\tau).$

######  Definition 2.1.

A set of $N$ length-$L$ sequences
$\\{\mathbf{a}_{0},\mathbf{a}_{1},\cdots,\mathbf{a}_{N-1}\\}$ is called a GCS
of order $N$ if for all $0<|\tau|\leq L-1,$

$\sum^{N-1}_{i=0}R_{\mathbf{a}_{i}}(\tau)=0.$

######  Definition 2.2.

A set of $M$ sequence sets
$\mathcal{S}=\\{\mathcal{S}_{0},\mathcal{S}_{1},\cdots,\mathcal{S}_{M-1}\\}$
is called an $(M,N,L)$-MOCS if for any $0\leq i\neq j\leq M-1$ and
$0\leq|\tau|\leq L-1,$

$R_{\mathcal{S}_{i},\mathcal{S}_{j}}(\tau)=\sum^{N-1}_{k=0}R_{\mathbf{a}^{i}_{k},\mathbf{a}^{j}_{k}}(\tau)=0,$

where each
$\mathcal{S}_{t}=\\{\mathbf{a}^{t}_{0},\mathbf{a}^{t}_{1},\cdots,\mathbf{a}^{t}_{N-1}\\}$
is a GCS of $N$ length-$L$ sequences.

######  Definition 2.3.

A set of $M$ sequence sets
$\mathcal{S}=\\{\mathcal{S}_{0},\mathcal{S}_{1},\cdots,\mathcal{S}_{M-1}\\}$
is called an $(M,N,L,Z)$-ZCCS if

$\displaystyle R_{\mathcal{S}_{i},\mathcal{S}_{j}}(\tau)$
$\displaystyle=\sum_{k=0}^{N-1}R_{\mathbf{a}^{i}_{k},\mathbf{a}^{j}_{k}}(\tau)=\left\\{\begin{array}[]{ll}NL,&\tau=0,\;i=j,\\\
0,&0<|\tau|<Z,\;i=j,\\\ 0,&|\tau|<Z,\;i\neq j,\end{array}\right.$

where $Z$ denotes the ZCZ width and each
$\mathcal{S}_{t}=\\{\mathbf{a}^{t}_{0},\mathbf{a}^{t}_{1},\cdots,\mathbf{a}^{t}_{N-1}\\}$
consists of $N$ length-$L$ sequences for any $0\leq t\leq M-1$. In addition,
if $Z=L$, then the $(M,N,L,Z)$-ZCCS is called an $(M,N,L)$-MOCS.

The following results give two bounds on the parameters of MOCSs and ZCCSs,
respectively.

######  Lemma 2.4.

[3] For an $(M,N,L)$-MOCS, the upper bound on set size satisfies the
inequality $M\leq N$. When $M=N$, it is called a CCC.

######  Lemma 2.5.

[41] For any $(M,N,L,Z)$-ZCCS, it holds that

$M\leq N\left\lfloor\frac{L}{Z}\right\rfloor.$

Note that a $ZCCS$ is $optimal$ if the above upper bound is achieved,i.e.,
$M=N\left\lfloor\frac{L}{Z}\right\rfloor.$

###  2.3 Extended Boolean functions (EBFs)

An EBF $f$ in $m$ variables $x_{1},x_{2},\cdots,x_{m}$ is a mapping from
$\mathbb{Z}_{q}^{m}$ to $\mathbb{Z}_{q}$ where $x_{i}\in\mathbb{Z}_{q}$ for
$i\in 1,2,\cdots,m$. Given $f(x)$, we define

$\mathbf{f}=(f_{0},f_{1},\cdots,f_{q^{m}-1}),$

where $f_{i}=f(i_{1},i_{2},\cdots,i_{m})$ and $(i_{1},i_{2},\cdots,i_{m})$ is
the $q$-ary representation of the integer $i=\sum^{m}_{k=1}i_{k}q^{k-1}$. For
example, for $f=x_{1}x_{2}+x_{1}+2$ with $m=2$ and $q=3$, we have the sequence
$\mathbf{f}=(2,0,1,2,1,0,2,2,2).$ In addition, we also consider the sequences
of length $L\neq q^{m}.$ Hence we define the corresponding truncated sequence
$\mathbf{f}^{(L)}$ of the EBF $f$ by removing the last $q^{m}-L$ elements of
the sequence $\mathbf{f}$. That is
$\mathbf{f}^{(L)}=(f_{0},f_{1},\cdots,f_{L-1})$ is a sequence of length $L$
with $f_{i}=f(i_{1},i_{2},\cdots,i_{m})$ for $i=0,1,\cdots,L-1$, which is a
naturally generalization of [42]. For convenience, we ignore the superscript
of $\mathbf{f}^{(L)}$ unless the sequence length is undetermined.

##  3 Construction of MOCSs with flexible lengths

In this section, we present a direct construction of MOCSs with flexible
lengths. Before giving the new MOCSs, we introduce the following lemmas.

######  Lemma 3.1.

[43] For an even integer $q$ and any positive integers $m$, $k$ with $k\leq
m$, let $v$ be an integer with $0\leq v\leq m-k$, and $\pi$ be a permutation
of $\mathbb{N}_{m}$ satisfying the following three conditions:

$(1)$ $\pi(m-k+1)<\pi(m-k+2)<\cdots<\pi(m-1)<\pi(m)=m.$

$(2)$ If $v>0$, then $\mathbb{N}_{v}=\\{\pi(1),\pi(2),\cdots,\pi(v)\\}.$

$(3)$ For all $\alpha=1,2,\cdots,k-1,$ if $\pi(t)<\pi(m-k+\alpha),$ then
$\pi(t-1)<\pi(m-k+\alpha)$ where $2\leq t\leq m-k.$
Let

$f=\frac{q}{2}\sum^{m-k-1}_{s=1}x_{\pi(s)}x_{\pi(s+1)}+\sum^{k}_{\alpha=1}\sum^{m-k}_{s=1}c_{\alpha,s}x_{\pi(m-k+\alpha)}x_{\pi(s)}+\sum^{m}_{s=1}c_{s}x_{s}+c_{0},$

where $c_{\alpha,s},c_{s}\in\mathbb{Z}_{q}$. Then the set

$\mathcal{F}=\left\\{\mathbf{f}+\frac{q}{2}\sum^{k}_{\alpha=1}d_{\alpha}\mathbf{x}_{\pi(m-k+\alpha)}+\frac{q}{2}d_{k+1}\mathbf{x}_{\pi(1)}\mid
d_{\alpha}\in\\{0,1\\}\right\\}$

forms a GCS of size $2^{k+1}$ and length
$L=2^{m-1}+\sum^{k-1}_{\alpha=1}a_{\alpha}2^{\pi(m-k+\alpha)-1}+2^{v}$ with
$a_{\alpha}\in\\{0,1\\}.$

######  Lemma 3.2.

For positive integers $m\geq 2$ and $r<m,$ let $h$ be a bijection from
$S_{1}=\mathbb{N}_{r}$ onto $S_{2}\subseteq\mathbb{N}_{m}$ with $r$ elements.
Suppose that $h(u)$ is the smallest element of $S_{2}$. Let $i$ be an integer
with

$\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq u\end{subarray}}a_{l}q^{h(l)-1}\leq
i\leq\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}+q^{h(u)}-1,$

where $a_{l}\in\mathbb{Z}^{*}_{q}$ for $l\in S_{1}\setminus\\{u\\}$ and
$(i_{1},i_{2},\cdots,i_{m})$ is the $q$-ary representation of $i.$ Also let
$i^{(t)}$ be an integer with $q$-ary representation
$(i_{1},i_{2},\cdots,i_{k}\oplus t,\cdots,i_{m})$ for positive integers $k\leq
h(u)$ and $t\in\mathbb{Z}^{*}_{q}$. Then we have

$\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq u\end{subarray}}a_{l}q^{h(l)-1}\leq
i^{(t)}\leq\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}+q^{h(u)}-1.$

###### Proof.

For convenience, we let $j=i-\sum\limits^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}$ and $(j_{1},j_{2},\cdots,j_{m})$ be the
$q$-ary representation of $j.$ Then $0\leq j\leq q^{h(u)}-1$, which means
$j_{s}=0$ for $s\geq h(u)+1$. Similarly, we let
$j^{(t)}=i^{(t)}-\sum\limits^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}$ with $q$-ary representation
$(j_{1},j_{2},\cdots,j_{k}\oplus t,\cdots,j_{m})$. Obviously, the $q$-ary
representation of $j$ differs from that of $j^{(t)}$ in only one position $k$.
So we obtain $j^{(t)}_{s}=j_{s}=0$ for $s\geq h(u)+1$ which implies $0\leq
j^{(t)}\leq q^{h(u)}-1$. Therefore,

$\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq u\end{subarray}}a_{l}q^{h(l)-1}\leq
i^{(t)}\leq\sum^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}+q^{h(u)}-1.$

∎

######  Lemma 3.3.

For positive integers $m\geq 2$ and $r<m,$ let $i$ and $h$ be the same as that
of Lemma 3.2. If $i\leq\sum\limits^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}+q^{h(u)}-1$ and $i_{h(l)}=a_{l}$ for $l\in
S_{1}\setminus\\{u\\}$. Then we have $i_{s}=0$ for
$s=h(u)+1,h(u)+2,\cdots,m-1$ and $s\neq h(l)$ for $l\in
S_{1}\setminus\\{u\\}$.

###### Proof.

Suppose the conclusion doesn’t hold, we assume $i_{t}=b\neq 0$ where
$h(u)+1\leq t\leq m-1$ and $t\neq h(l)$ for $l\in S_{1}\setminus\\{u\\}$. Then
we have $i\geq\sum\limits^{r}_{\begin{subarray}{c}l=1\\\ l\neq
u\end{subarray}}a_{l}q^{h(l)-1}+bq^{t-1}\geq\sum\limits^{r}_{\begin{subarray}{c}l=1\\\
l\neq u\end{subarray}}a_{l}q^{h(l)-1}+q^{h(u)}$ which contradicts the
condition. ∎

######  Lemma 3.4.

[44] Let $q$ be an even number, $(i_{1},i_{2},\cdots,i_{m})$ and
$(j_{1},j_{2},\cdots,j_{m})$ be the binary representations of $i$ and $j$,
respectively, and let $\\{I_{1},I_{2},\cdots,I_{d}\\}$ be a partition of the
set $\mathbb{N}_{m}$. Let $\pi_{\alpha}$ be a bijection from
$\mathbb{N}_{m_{\alpha}}$ to $I_{\alpha}$, where $\lvert
I_{\alpha}\rvert=m_{\alpha}$ for any $\alpha\in\mathbb{N}_{d}.$ If the
following three conditions are satisfied:

$(1)$ $\alpha_{1}$ is the largest integer satisfying
$i_{\pi_{\alpha}(\beta)}=j_{\pi_{\alpha}(\beta)}$ for
$\alpha\in\mathbb{N}_{\alpha_{1}}$ and $\beta\in\mathbb{N}_{m_{\alpha}}.$

$(2)$ $\beta_{1}$ is the smallest integer such that
$i_{\pi_{\alpha_{1}(\beta_{1})}}\neq j_{\pi_{\alpha_{1}(\beta_{1})}}.$

$(3)$ Let $i^{\prime}$ and $j^{\prime}$ be integers which differ from $i$ and
$j$, respectively, in only one position $\pi_{\alpha_{1}(\beta_{1}-1)},$ that
is,
$i^{\prime}_{\pi_{\alpha_{1}(\beta_{1}-1)}}=1-i_{\pi_{\alpha_{1}(\beta_{1}-1)}}$
and
$j^{\prime}_{\pi_{\alpha_{1}(\beta_{1}-1)}}=1-j_{\pi_{\alpha_{1}(\beta_{1}-1)}}$.
Then

$f_{n,i}-f_{n,j}-f_{n,i^{\prime}}+f_{n,j^{\prime}}\equiv\frac{q}{2}\pmod{q},$

where $f(x)$ as shown in Eq. (1) of [44].

######  Lemma 3.5.

Let $\textbf{x}_{n_{1}},\textbf{x}_{n_{2}},\cdots,\textbf{x}_{n_{d}}$ be the
sequences corresponding to EBFs $x_{n_{1}},x_{n_{2}},\cdots,x_{n_{d}}$,
respectively, where $n_{1}<n_{2}<\cdots<n_{d}.$ Let
$\textbf{u}=(u_{0},u_{1},\cdots,u_{L-1})=a_{1}\textbf{x}_{n_{1}}\oplus
a_{2}\textbf{x}_{n_{2}}\oplus\cdots\oplus a_{d}\textbf{x}_{n_{d}}$ be a
$q$-ary sequence with $a_{i}\in\mathbb{Z}_{q}$ for any $i\in\mathbb{N}_{d},$
which is a linear combination of
$\textbf{x}_{n_{1}},\textbf{x}_{n_{2}},\cdots,\textbf{x}_{n_{d}}.$ If
$q^{n_{1}}\mid L$ and $a_{1}\neq 0$, let $(i_{1},i_{2},\cdots,i_{m})$ be the
binary representation of $i$, and let $i^{(t)}$ differ from $i$ in only one
position $n_{1}$, i.e.,

$(i^{(t)}_{1},i^{(t)}_{2},\cdots,i^{(t)}_{m})=(i_{1},i_{2},\cdots,i_{n_{1}-1},i_{n_{1}}\oplus
t,i_{n_{1}+1},\cdots,i_{m}),$

where $t\in\mathbb{Z}^{*}_{q}$. Then

$\xi^{u_{i}}+\xi^{u_{i^{(1)}}}+\xi^{u_{i^{(2)}}}+\cdots+\xi^{u_{i^{(q-1)}}}=0.$

###### Proof.

Since $q^{n_{1}}\mid L$, then for any integer $i$,

$u_{i^{(t)}}-u_{i}=(a_{1}i^{(t)}_{n_{1}}\oplus
a_{2}i^{(t)}_{n_{2}}\oplus\cdots a_{k}i^{(t)}_{n_{k}})-(a_{1}i_{n_{1}}\oplus
a_{2}i_{n_{2}}\oplus\cdots a_{k}i_{n_{k}})\equiv
a_{1}(i^{(t)}_{n_{1}}-i_{n_{1}})\equiv a_{1}t\pmod{q},$

Thus we have

$1+\xi^{u_{i^{(1)}}-u_{i}}+\xi^{u_{i^{(2)}}-u_{i}}+\cdots+\xi^{u_{i^{(q-1)}}-u_{i}}=0.$

∎

Now we state our construction in the following Theorem 3.6, which is based on
Lemma 3.1.

######  Theorem 3.6.

Let $m$, $d$, $d^{\prime}$, $v$ be positive integers with $0<d^{\prime}<d<m$
and $v<m$. Let {$I_{1}$, $I_{2}$, $\cdots$, $I_{d}$} be a partition of the set
$\mathbb{N}_{m-v}$. Put $\pi_{\alpha}$ be a bijection from
$\mathbb{N}_{m_{\alpha}}$ to $I_{\alpha}$, where $\lvert
I_{\alpha}\rvert=m_{\alpha}$ for any $\alpha\in\mathbb{N}_{d}.$ Let $u$ be an
integer with
$\sum_{{\alpha}=1}^{d^{\prime}}m_{\alpha}<u<\sum_{\alpha=1}^{d^{\prime}+1}m_{\alpha}$,
we impose an additional condition below:

$\\{\pi_{1}(1),\pi_{1}(2),\cdots,\pi_{1}(m_{1}),\pi_{2}(1),\cdots,\pi_{d^{\prime}+1}(u^{\prime})\\}=\\{1,2.\cdots,u\\},$

where $0<u^{\prime}<m_{d^{\prime}+1}$. Let $(n_{1},n_{2},\cdots,n_{d+v})$ and
$(p_{1},p_{2},\cdots,p_{d^{\prime}})$ be the $q$-ary representations of $n$
and $p$, respectively. Let

$\displaystyle f(x)$
$\displaystyle=\sum^{d}_{\alpha=1}\sum^{m_{\alpha}-1}_{\beta=1}a_{\alpha,\beta}x_{\pi_{\alpha}(\beta)}x_{\pi_{\alpha}(\beta+1)}+\sum^{d}_{\alpha=1}\sum^{m_{\alpha}}_{\beta=1}\sum_{k=1}^{v}b_{\alpha,\beta,k}x_{\pi_{\alpha}(\beta)}x_{m-v+k}+\sum_{l=1}^{q-1}\sum_{s=1}^{m}c_{s,l}x^{l}_{s}+c_{0},$
(1) $\displaystyle f^{p}_{n}(x)$
$\displaystyle=f(x)+\sum^{d}_{\alpha=1}n_{\alpha}x_{\pi_{\alpha}(1)}+\sum^{v}_{k=1}n_{k+d}x_{m-v+k}+c\sum^{d^{\prime}}_{\alpha=1}p_{\alpha}x_{\pi_{\alpha}(m_{\alpha})},$
(2)

where $a_{\alpha,\beta},c\in\mathbb{Z}^{*}_{q}$ are co-prime with $q$ and
$b_{\alpha,\beta,k},c_{s,l},c_{0}\in\mathbb{Z}_{q}$. Then
$\\{\mathcal{F}^{0},\mathcal{F}^{1},\cdots,\mathcal{F}^{q^{d^{\prime}}-1}\\}$
generates a $(q^{d^{\prime}},q^{v+d},L)$-MOCS with
$L=a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}$,
$a_{k}\in\mathbb{Z}_{q}$ and $a_{m}\in\mathbb{Z}^{*}_{q}$, where
$\mathcal{F}^{p}=\\{\mathbf{f}^{p}_{0},\mathbf{f}^{p}_{1},\cdots,\mathbf{f}^{p}_{q^{v+d}-1}\\}.$

###### Proof.

Since for sequences $\mathbf{f}^{p}_{n}$ and $\mathbf{f}^{p^{\prime}}_{n}$,
$R_{\mathbf{f}^{p^{\prime}}_{n},\mathbf{f}^{p}_{n}}(-\tau)=R^{*}_{\mathbf{f}^{p}_{n},\mathbf{f}^{p^{\prime}}_{n}}(\tau)$,
then it suffice to prove that for $0\leq p,p^{\prime}\leq q^{d^{\prime}}-1$
and $0<\tau\leq L-1$,

$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=\sum^{q^{v+d}-1}_{n=0}\sum^{L-1-\tau}_{i=0}\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i+\tau}}=\sum^{L-1-\tau}_{i=0}\sum^{q^{v+d}-1}_{n=0}\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i+\tau}}=0,$

where $f^{p}_{n,i}$ and $f^{p^{\prime}}_{n,j}$ are the $(i+1)$-th and the
$(j+1)$-th element of sequence $\mathbf{f}^{p}_{n}$ and
$\mathbf{f}^{p^{\prime}}_{n}$, respectively.  For simplicity, we assume
$a_{k}\neq 0$ for any $k\in\mathbb{N}_{v-1}$. Throughout this paper, for a
given integer $i$, we set $j=i+\tau$ and let $(i_{1},i_{2},\cdots,i_{m})$ and
$(j_{1},j_{2},\cdots,j_{m})$ be the $q$-ary representations of $i$ and $j$,
respectively. Let $(p_{1},p_{2},\cdots,p_{d^{\prime}})$ and
$(p^{\prime}_{1},p^{\prime}_{2},\cdots,p^{\prime}_{d^{\prime}})$ are the
$q$-ary representations of $p$ and $p^{\prime}$, respectively.

Case 1: If $i_{\pi_{\alpha}(1)}\neq j_{\pi_{\alpha}(1)}$ for some
$\alpha\in\mathbb{N}_{d}$ or $i_{m-v+k}\neq j_{m-v+k}$ for some
$k\in\mathbb{N}_{v}.$ Then

$\displaystyle
R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=\sum_{i=0}^{L-1-\tau}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d}\left(\sum_{n_{\alpha}=0}^{q-1}\xi^{n_{\alpha}\left(i_{\pi_{\alpha}(1)}-j_{\pi_{\alpha}(1)}\right)}\right)\prod_{\alpha=1}^{d^{\prime}}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}A=0.$

where
$A=\prod_{k=1}^{v}\left(\sum_{n_{d+k}=0}^{q-1}\xi^{n_{d+k}(i_{m-v+k}-j_{m-v+k})}\right)$.

Case 2: If $i_{\pi_{\alpha}(1)}=j_{\pi_{\alpha}(1)}$ for all
$\alpha\in\mathbb{N}_{d}$, $i_{m-v+k}=j_{m-v+k}$ for all $k\in\mathbb{N}_{v}$,
and $i_{m}=j_{m}=0.$ Then

$\displaystyle
R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=q^{d+v}\sum_{i=0}^{L-1-\tau}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d^{\prime}}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}.$

Similar to Lemma 3.4, we assume that

(1) $\alpha_{1}$ is the largest integer satisfying
$i_{\pi_{\alpha}(\beta)}=j_{\pi_{\alpha}(\beta)}$ for
$\alpha\in\mathbb{N}_{\alpha_{1}}$ and $\beta\in\mathbb{N}_{m_{\alpha}}$.

(2) $\beta_{1}$ is the smallest integer such that
$i_{\pi_{\alpha_{1}}(\beta_{1})}\neq j_{\pi_{\alpha_{1}}(\beta_{1})}$.

(3) Let $i^{(t)}$ and $j^{(t)}$ be integers which differ from $i$ and $j$,
respectively, in only one position $\pi_{\alpha_{1}}(\beta_{1}-1),$ that is,
$i^{(t)}_{\pi_{\alpha_{1}}(\beta_{1}-1)}=t\oplus
i_{\pi_{\alpha_{1}}(\beta_{1}-1)}$ and
$j^{(t)}_{\pi_{\alpha_{1}}(\beta_{1}-1)}=t\oplus
j_{\pi_{\alpha_{1}}(\beta_{1}-1)}$.

Thus we get

$f_{i^{(t)}}-f_{i}-f_{j^{(t)}}+f_{j}=ta_{\alpha_{1},\beta_{1}-1}\left(i_{\pi_{\alpha_{1}}(\beta_{1})}-j_{\pi_{\alpha_{1}}(\beta_{1})}\right)$

and

$\xi^{f_{i}-f_{j}}+\xi^{f_{i^{(1)}}-f_{j^{(1)}}}+\xi^{f_{i^{(2)}}-f_{j^{(2)}}}+\cdots+\xi^{f_{i^{(q-1)}}-f_{j^{(q-1)}}}=0,$

which implies

$\displaystyle
R_{\mathcal{F}^{p_{1}},\mathcal{F}^{p_{2}}}(\tau)=q^{d+v}\sum_{i=0}^{L-1-\tau}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d^{\prime}}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}=0.$

Case 3: If $i_{\pi_{\alpha}(1)}=j_{\pi_{\alpha}(1)}$ for all
$\alpha\in\mathbb{N}_{d}$, $i_{m-v+k}=j_{m-v+k}$ for all $k\in\mathbb{N}_{v}$,
and $i_{m}=j_{m}=a_{m}\neq 0.$ Suppose $k_{1}$ is the largest integer such
that $i_{m-v+k}=j_{m-v+k}=0$ for $k<v,$ i.e., $i_{m-v+k}=j_{m-v+k}=a_{k}\neq
0$ for $k\in\\{k_{1}+1,k_{1}+2,\cdots,v\\},$ then

$\displaystyle i,j$
$\displaystyle<L=a_{m}q^{m-1}+\sum^{v-1}_{\alpha=1}a_{k}q^{m-v+k-1}+q^{u}$
$\displaystyle\leq
a_{m}q^{m-1}+\sum^{v-1}_{k=k_{1}+1}a_{k}q^{m-v+k-1}+q^{m-v+k_{1}-1}-1.$

According to Lemma 3.2 and $\pi_{\alpha_{1}(\beta_{1}-1)}<{m-v+k_{1}-1},$ we
have

$i^{(t)},j^{(t)}\leq
a_{m}q^{m-1}+\sum^{v-1}_{k=k_{1}+1}a_{k}q^{m-v+k-1}+q^{m-v+k_{1}-1}-1<L.$

Therefore, we get

$\xi^{f_{i}-f_{j}}+\xi^{f_{i^{(1)}}-f_{j^{(1)}}}+\cdots+\xi^{f_{i^{(q-1)}}-f_{j^{(q-1)}}}=0.$

Case 4: $i_{\pi_{\alpha}(1)}=j_{\pi_{\alpha}(1)}$ for all
$\alpha\in\mathbb{N}_{d}$, $i_{m-v+k}=j_{m-v+k}$ for all $k\in\mathbb{N}_{v}$,
and $i_{m}=j_{m}=a_{m}\neq 0.$ We also consider that
$i_{m-v+k}=j_{m-v+k}=a_{k}\neq 0$ for all $k\in\mathbb{N}_{v},$

$i,j<L=a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}.$

According to Lemma 3.3, we have $i_{s}=j_{s}=0$ for $s=u+1,u+2,\cdots,m-v-1$,
so $\pi_{\alpha_{1}}(\beta_{1})\leq u,$ and $\pi_{\alpha_{1}}(\beta_{1}-1)\leq
u.$ Therefore,

$i^{(t)},j^{(t)}\leq a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}<L$

and

$\xi^{f_{i}-f_{j}}+\xi^{f_{i^{(1)}}-f_{j^{(1)}}}+\cdots+\xi^{f_{i^{(q-1)}}-f_{j^{(q-1)}}}=0.$

Combining the above four cases, we can conclude that
$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=0$ for $0<\tau\leq L-1$.

Next, it remains to show that for $0\leq p\neq p^{\prime}\leq
q^{d^{\prime}}-1$,

$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(0)=\sum^{q^{v+d}-1}_{n=0}\sum^{L-1}_{i=0}{\xi}^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i}}=0.$

Since $p\neq p^{\prime}$, there exists a smallest
$s\in\mathbb{N}_{d^{\prime}}$ such that $p_{s}\neq p^{\prime}_{s}$. Then
according to Lemma 3.5, for any $0\leq i\leq L-1$, there exists $i^{(t)}$
whose $q$-ary representation differs from $i$ in only one position $s$, i.e.,
$(i_{1},i_{2},\cdots,i_{s-1},i_{s}\oplus t,i_{s+1},\cdots,i_{m})$ for any
$t\in\mathbb{Z}^{*}_{q}$. Therefore, we get

$\displaystyle\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i}}+\xi^{f^{p}_{n,i^{(1)}}-f^{p^{\prime}}_{n,i^{(1)}}}+\cdots+\xi^{f^{p}_{n,i^{(q-1)}}-f^{p^{\prime}}_{n,i^{(q-1)}}}$
$\displaystyle=$
$\displaystyle\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i}}\left(1+\xi^{f^{p}_{n,i^{(1)}}-f^{p^{\prime}}_{n,i^{(1)}}-f^{p}_{n,i}+f^{p^{\prime}}_{n,i}}+\cdots+\xi^{f^{p}_{n,i^{(q-1)}}-f^{p^{\prime}}_{n,i^{(q-1)}}-f^{p}_{n,i}+f^{p^{\prime}}_{n,i}}\right)$
$\displaystyle=$
$\displaystyle\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i}}\left(1+\xi^{c(p_{s}-p^{\prime}_{s})}+\cdots+\xi^{c(p_{s}-p^{\prime}_{s})(q-1)}\right)$
$\displaystyle=$ $\displaystyle 0$

and

$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(0)=\sum^{q^{k+1}-1}_{n=0}\sum^{L-1}_{i=0}{\xi}^{f^{p}_{n,i}-f^{p^{\prime}}_{n,i}}=0.$

By the above discussion, we obtain that $\\{\mathcal{F}^{p}\mid
p\in\\{0,1,\cdots,q^{d^{\prime}}-1\\}\\}$ is a
$(q^{d^{\prime}},q^{v+d},L)$-MOCS with
$L=a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}$, where
$a_{k}\in\mathbb{Z}_{q}$ and $a_{m}\in\mathbb{Z}^{*}_{q}$.

∎

######  Remark 3.7.

In Theorem 3.6, if we let $q=2$ and all $a_{k}=0$ and $a_{m}=1$, then the
length $L=a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u}$ turns into the
form $2^{m-1}+2^{u},$ this result is coveblack in [14].

######  Example 3.8.

Let $m=5,$ $v=1,$ $d=2,$ $d^{\prime}=1,$ $m_{1}=m_{2}=2,$
$(\pi_{1}(1),\pi_{1}(2),\pi_{2}(1),\pi_{2}(2))=(1,2,3,4)$ and all
$a_{\alpha,\beta},b_{\alpha,\beta,k},c_{s,l},c_{0},c$ are equal to 1. Then
$\\{\mathcal{F}^{0},\mathcal{F}^{1},\mathcal{F}^{2}\\}$ forms a ternary
$(3,27,108)$-MOCS from Theorem 3.6.

##  4 Constructions of CCCs and optimal ZCCSs

In this section, we mainly propose an approach to constructing an optimal
ZCCS. Before doing this work, we need to construct CCCs as a preparing work.

######  Theorem 4.1.

Let $m$, $d$ be positive integers with $2\leq d<m$, and
$\\{I_{1},I_{2},\cdots,I_{d}\\}$ be a partition of the set $\mathbb{N}_{m}$.
Put $\pi_{\alpha}$ be a bijection from $\mathbb{N}_{m_{\alpha}}$ to
$I_{\alpha}$, where $\lvert I_{\alpha}\rvert=m_{\alpha}$ for any
$\alpha\in\\{1,2,\cdots,d\\}.$ Let

$\displaystyle f(x)=$
$\displaystyle\sum_{\alpha=1}^{d}\sum_{\beta=1}^{m_{\alpha}-1}a_{\alpha,\beta}x_{\pi_{\alpha}(\beta)}x_{\pi_{\alpha}(\beta+1)}+\sum_{l=1}^{q-1}\sum_{u=1}^{m}h_{u,l}x^{l}_{u}+h_{0},$
$\displaystyle f^{p}_{n}(x)=$ $\displaystyle
f(x)+\sum_{\alpha=1}^{d}n_{\alpha}x_{\pi_{\alpha}(1)}+\sum_{\alpha=1}^{d}p_{\alpha}x_{\pi_{\alpha}(m_{\alpha})},$

where $a_{\alpha,\beta}\in\mathbb{Z}^{*}_{q}$ is co-prime with $q$, $h_{u,l}$,
$h_{0}\in\mathbb{Z}_{q}$, $(n_{1},n_{2},\cdots,n_{d})$ and
$(p_{1},p_{2},\cdots,p_{d})$ are the $q$-ary representations of $n$ and $p$,
respectively. Then the set
$\\{\mathcal{F}^{0},\mathcal{F}^{1},\cdots,\mathcal{F}^{q^{d}-1}\\}$ forms a
$q$-ary CCC with
$\mathcal{F}^{p}=\\{\mathbf{f}^{p}_{0},\mathbf{f}^{p}_{1},\cdots,\mathbf{f}^{p}_{q^{d}-1}\\}$.

###### Proof.

The proof consists of two parts. In the first part, we demonstrate that for
any $0\leq p,p^{\prime}\leq q^{d}-1$ and $0<\tau\leq q^{m}-1$,
$\mathcal{F}^{p}$ and $\mathcal{F}^{p^{\prime}}$ satisfy the ideal correlation
property, i.e.,

$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=\sum_{n=0}^{q^{d}-1}R_{\mathbf{f}^{p}_{n},\mathbf{f}^{p^{\prime}}_{n}}(\tau)=\sum_{n=0}^{q^{d}-1}\sum_{i=0}^{q^{m}-1-\tau}\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,j}}=\sum_{i=0}^{q^{m}-1-\tau}\sum_{n=0}^{q^{d}-1}\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,j}}=0,$

where $f^{p}_{n,i}$ and $f^{p^{\prime}}_{n,j}$ are the $(i+1)$-th and the
$(j+1)$-th element of sequence $\mathbf{f}^{p}_{n}$ and
$\mathbf{f}^{p^{\prime}}_{n}$, respectively. Similarly, let the definitions of
$i,j,i^{(t)}$ and $j^{(t)}$ be given as Theorem 3.6. Furthermore, we divide
the set $\\{i\mid 0\leq i\leq q^{m}-1-\tau\\}$ into two parts:
$S_{1}(\tau)=\\{i\mid\exists\ \alpha\in\\{1,2,\cdots,d\\},\ 0\leq i\leq
q^{m}-1-\tau,\ i_{\pi_{\alpha}(1)}\neq j_{\pi_{\alpha}(1)}\\}$ and
$S_{2}(\tau)=\\{i\mid\forall\ \alpha\in\\{1,2,\cdots,d\\},\ 0\leq i\leq
q^{m}-1-\tau,\ i_{\pi_{\alpha}(1)}=j_{\pi_{\alpha}(1)}\\}$. Thus we obtain
that

$\displaystyle
R_{\mathcal{{\color[rgb]{0,0,0}F}}^{p},\mathcal{{\color[rgb]{0,0,0}F}}^{p^{\prime}}}(\tau)=$
$\displaystyle\sum_{i=0}^{q^{m}-1-\tau}\sum_{n=0}^{q^{d}-1}\xi^{f^{p}_{n,i}-f^{p^{\prime}}_{n,j}}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{q^{m}-1-\tau}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d}\left(\sum_{n_{\alpha}=0}^{q-1}\xi^{n_{\alpha}\left(i_{\pi_{\alpha}(1)}-j_{\pi_{\alpha}(1)}\right)}\right)\prod_{\alpha=1}^{d}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}$
$\displaystyle=$ $\displaystyle\sum_{i\in
S_{1}(\tau)}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d}\left(\sum_{n_{\alpha}=0}^{q-1}\xi^{n_{\alpha}\left(i_{\pi_{\alpha}(1)}-j_{\pi_{\alpha}(1)}\right)}\right)\prod_{\alpha=1}^{d}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}$
$\displaystyle+\sum_{i\in
S_{2}(\tau)}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d}\left(\sum_{n_{\alpha}=0}^{q-1}\xi^{n_{\alpha}\left(i_{\pi_{\alpha}(1)}-j_{\pi_{\alpha}(1)}\right)}\right)\prod_{\alpha=1}^{d}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}$
$\displaystyle=$ $\displaystyle q^{d}\sum_{i\in
S_{2}(\tau)}\xi^{f_{i}-f_{j}}\prod_{\alpha=1}^{d}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}},$

where $(p_{k,1},p_{k,2},\cdots,p_{k,d})$ is the $q$-ary representation of
$p_{k}$ for any $k\in\\{1,2\\}.$ For any $i\in S_{2}(\tau)$, according to the
Case 2 of first part in Theorem 3.6, we have

$f_{i^{(t)}}-f_{i}-f_{j^{(t)}}+f_{j}=ta_{\alpha_{1},\beta_{1}-1}\left(i_{\pi_{\alpha_{1}}(\beta_{1})}-j_{\pi_{\alpha_{1}}(\beta_{1})}\right)$

and

$(\xi^{f_{i}-f_{j}}+\xi^{f_{i^{(1)}}-f_{j^{(1)}}}+\xi^{f_{i^{(2)}}-f_{j^{(2)}}}+\cdots+\xi^{f_{i^{(q-1)}}-f_{j^{(q-1)}}})\prod_{\alpha=1}^{d}\xi^{p_{\alpha}i_{\pi_{\alpha}(m_{\alpha})}-p^{\prime}_{\alpha}j_{\pi_{\alpha}(m_{\alpha})}}=0.$

According to the above discussion, we know that the ideal correlation property
is available for any $\tau>0$. Now, we need to prove that for any $0\leq p\neq
p^{\prime}\leq q^{d}-1$ and $\tau=0$,

$\displaystyle
R_{\mathcal{{\color[rgb]{0,0,0}F}}^{p},\mathcal{{\color[rgb]{0,0,0}F}}^{p^{\prime}}}(0)=\sum_{n=0}^{q^{d}-1}R_{\mathbf{{\color[rgb]{0,0,0}f}}^{p}_{n},\mathbf{{\color[rgb]{0,0,0}f}}^{p^{\prime}}_{n}}(0)=\sum_{n=0}^{q^{d}-1}\sum_{i=0}^{q^{m}-1}\xi^{\sum_{\alpha=1}^{d}(p_{\alpha}\oplus
p^{\prime}_{\alpha})i_{\pi_{\alpha}(m_{\alpha})}}=0.$

Put $\textbf{d}=\sum_{\alpha=1}^{d}(p_{\alpha}\oplus
p^{\prime}_{\alpha})\textbf{x}_{\pi_{\alpha}(m_{\alpha})}$. Due to each
$\textbf{x}_{\pi_{\alpha}(m_{\alpha})}$ is a balanced sequence, the linear
combination of
$\textbf{x}_{\pi_{1}(m_{1})},\textbf{x}_{\pi_{2}(m_{2})},\cdots,\textbf{x}_{\pi_{d}(m_{d})}$
is balanced, i.e., d is balanced. Then we have

$\displaystyle
R_{\mathcal{{\color[rgb]{0,0,0}F}}^{p},\mathcal{{\color[rgb]{0,0,0}F}}^{p^{\prime}}}(0)=\sum_{n=0}^{q^{d}-1}\sum_{i=0}^{q^{m}-1}\xi^{\sum_{\alpha=1}^{d}(p_{\alpha}\oplus
p^{\prime}_{\alpha})i_{\pi_{\alpha}(m_{\alpha})}}=0,$

which completes the proof.

∎

With the help of the above Theorem 4.1, the following
$(q^{v+d},q^{d},q^{m},q^{m-v})$-ZCCSs can be obtained easily.

######  Theorem 4.2.

Let $m$, $d$, $v$ be positive integers with $d\leq m-v$ and $v<m$. Let
$\\{I_{1},I_{2},\cdots,I_{d}\\}$ be a partition of the set $\mathbb{N}_{m-v}$.
Put $\pi_{\alpha}$ be a permutation from $\mathbb{N}_{m_{\alpha}}$ to
$I_{\alpha}$, where $\lvert I_{\alpha}\rvert=m_{\alpha}$ for any
$\alpha\in\mathbb{N}_{d}.$ Also let

$\displaystyle f(x)=$
$\displaystyle\sum_{\alpha=1}^{d}\sum_{\beta=1}^{m_{\alpha}-1}a_{\alpha,\beta}x_{\pi_{\alpha}(\beta)}x_{\pi_{\alpha}(\beta+1)}+\sum_{l=1}^{q-1}\sum_{u=1}^{m}h_{u,l}x^{l}_{u}+h_{0},$
$\displaystyle f^{p}_{n}(x)=$ $\displaystyle
f(x)+\sum_{\alpha=1}^{d}n_{\alpha}x_{\pi_{\alpha}(1)}+b\left(\sum_{\alpha=1}^{d}p_{\alpha}x_{\pi_{\alpha}(m_{\alpha})}+\sum_{k=1}^{v}p_{k+d}x_{m-v+k}\right),$

where $(n_{1},n_{2},\cdots,n_{d})$ and $(p_{1},p_{2},\cdots,p_{v+d})$ are the
$q$-ary representations of $n$ and $p$, respectively,
$a_{\alpha,\beta},b\in\mathbb{Z}^{*}_{q}$ are both co-prime with $q$, and
$h_{u,l},h_{0}\in\mathbb{Z}_{q}$. Then
$\left\\{\mathcal{F}^{0},\mathcal{F}^{1},\cdots,\mathcal{F}^{q^{v+d}-1}\right\\}$
forms a $(q^{v+d},q^{d},q^{m},q^{m-v})$-ZCCS with
$\mathcal{F}^{p}=\left\\{\mathbf{f}^{p}_{0},\mathbf{f}^{p}_{1},\cdots,\mathbf{f}^{p}_{q^{d}-1}\right\\}$.

###### Proof.

It is obvious that every sequence $\mathbf{f}^{p}_{n}$ can be divided into
$q^{v}$ relevant sub-sequence by a concatenate method, i.e.,

$\mathbf{f}^{p}_{n}=\mathbf{g}^{p}_{n,0}|\mathbf{g}^{p}_{n,1}|\cdots|\mathbf{g}^{p}_{n,q^{v}-1},$

Each $\mathbf{g}^{p}_{n,e}$ can be expressed as $\mathbf{g}^{p}_{n,0}\oplus
x_{e}$, i.e., $\mathbf{g}^{p}_{n,e}=\mathbf{g}^{p}_{n,0}\oplus x_{e},$ where
$\mathbf{g}^{p}_{n,e}$ denotes the $(e+1)$-th sub-sequence of
$\mathbf{f}^{p}_{n}$, $x_{e}\in\mathbb{Z}_{q}$ and
$e\in\\{0,1,2,\cdots,q^{v}-1\\}.$ For any $0<\tau\leq q^{m-v}-1$ and any
$0\leq p\leq q^{v+d}-1$,

$\displaystyle R_{\mathcal{F}^{p}}(\tau)$
$\displaystyle=\sum^{q^{d}-1}_{n=0}R_{\mathbf{f}^{p}_{n}}(\tau)$
$\displaystyle=\left(1+\sum^{q^{v}-1}_{k=1}\xi^{u_{k}-w_{k}}\right)\sum^{q^{d}-1}_{n=0}R_{\mathbf{g}^{p}_{n,0}}(\tau)+\left(\xi^{-w_{1}}+\sum^{q^{v}-2}_{k=1}\xi^{u_{k}-w_{k+1}}\right)\sum^{q^{d}-1}_{n=0}R^{*}_{\mathbf{g}^{p}_{n,0}}(q^{v}-\tau)$
$\displaystyle=0.$

By the way of Theorem 4.1, we conclude that the sequence set
$\left\\{\mathbf{g}^{p}_{0,0},\mathbf{g}^{p}_{1,0},\cdots,\mathbf{g}^{p}_{q^{d}-1,0}\right\\}$
forms a GCS. Therefore, we know that
$\left\\{\mathbf{f}^{p}_{0},\mathbf{f}^{p}_{1},\cdots,\mathbf{f}^{p}_{q^{d}-1}\right\\}$
satisfies the auto-correlation property for $0<\tau\leq q^{m-v}-1$.

Next, we verify the cross-correlation property, i.e., for $0\leq p\neq
p^{\prime}\leq q^{v+d}-1$ and for any $0<\tau<q^{m-v}$,

$\displaystyle R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)$
$\displaystyle=\sum^{q^{d}-1}_{n=0}R_{\mathbf{f}^{p}_{n},\mathbf{f}^{p^{\prime}}_{n}}(\tau)$
$\displaystyle=\left(1+\sum^{q^{v}-1}_{k=1}\xi^{u_{k}-w_{k}}\right)\sum^{q^{d}-1}_{n=0}R_{\mathbf{g}^{p}_{n,0},\mathbf{g}^{p^{\prime}}_{n,0}}(\tau)+\left(\xi^{-w_{1}}+\sum^{q^{v}-2}_{k=1}\xi^{u_{k}-w_{k+1}}\right)\sum^{q^{d}-1}_{n=0}R^{*}_{\mathbf{g}^{p^{\prime}}_{n,0},\mathbf{g}^{p}_{n,0}}(q^{v}-\tau)$
$\displaystyle=0,$

where $\mathbf{f}^{p}_{n}=\mathbf{g}^{p}_{n,0}|(\mathbf{g}^{p}_{n,0}\oplus
u_{1})|\cdots|(\mathbf{g}^{p}_{n,0}\oplus u_{q^{v}-1})$ and
$\mathbf{f}^{p^{\prime}}_{n}=\mathbf{g}^{p^{\prime}}_{n,0}|(\mathbf{g}^{p^{\prime}}_{n,0}\oplus
w_{1})|\cdots|(\mathbf{g}^{p^{\prime}}_{n,0}\oplus w_{q^{v}-1})$ with
$u_{i},w_{i}\in\mathbb{Z}_{q}.$ The $q$-ary representations of $p$ and
$p^{\prime}$ are $(p_{1},p_{2},\cdots,p_{v+d})$ and
$(p^{\prime}_{1},p^{\prime}_{2},\cdots,p^{\prime}_{v+d})$, respectively.

According to the definition of $f^{p}_{n}(x)$, we get that

$g^{p}_{n,0}(x)=h(x)+\sum_{\alpha=1}^{d}n_{\alpha}x_{\pi_{\alpha}(1)}+b\sum_{\alpha=1}^{d}n_{\alpha}x_{\pi_{\alpha}(m_{\alpha})},$

where
$h(x)=\sum_{\alpha=1}^{d}\sum_{\beta=1}^{m_{\alpha}-1}a_{\alpha,\beta}x_{\pi_{\alpha}(\beta)}x_{\pi_{\alpha}(\beta+1)}+\sum_{l=1}^{q-1}\sum_{u=1}^{m-v}h_{u,l}x^{l}_{u}+h_{0}$
with $\\{I_{1},I_{2},\cdots,I_{d}\\}$ a partition of the set
$\mathbb{N}_{m-v}$. Obviously, according to Theorem 4.1, we get that

$\sum^{q^{d}-1}_{n=0}R_{\mathbf{g}^{p}_{n,0},\mathbf{g}^{p^{\prime}}_{n,0}}(\tau)=0$

and

$\sum^{q^{d}-1}_{n=0}R^{*}_{\mathbf{g}^{p^{\prime}}_{n,0},\mathbf{g}^{p}_{n,0}}(q^{v}-\tau)=0.$

This shows that $R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=0.$
Similarly, we can prove that
$R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(\tau)=0$ for any
$-q^{d}+1\leq\tau<0.$

When $\tau=0,$ for any $0\leq p\neq p^{\prime}\leq q^{v+d}-1$,

$\displaystyle
R_{\mathcal{F}^{p},\mathcal{F}^{p^{\prime}}}(0)=\sum^{q^{d}-1}_{n=0}\sum_{i=0}^{q^{m}-1}\prod_{\alpha=1}^{d}\xi^{b(p_{\alpha}\oplus
p^{\prime}_{\alpha})i_{\pi_{\alpha}(m_{\alpha})}}\prod_{k=1}^{v}\xi^{b(p_{k+d}\oplus
p^{\prime}_{k+d})i_{m-v+k}}=0.$

The equality holds because $p\neq p^{\prime}$ leads to the existence of at
least one index $s\in\mathbb{N}_{v+d}$ such that $p_{s}\neq p^{\prime}_{s}$
and $gcd(b,q)=1.$ By the above two cases, we get that
$R_{\mathbf{f}^{p},\mathbf{f}^{p^{\prime}}}(\tau)=0$ for any
$-q^{d}<\tau<q^{d}$ and $0\leq p\neq p^{\prime}\leq q^{v+d}.$ Thus we prove
that
$\left\\{\mathcal{F}^{0},\mathcal{F}^{1},\cdots,\mathcal{F}^{q^{v+d}-1}\right\\}$
is a $(q^{v+d},q^{d},q^{m},q^{m-v})$-ZCCS with
$\mathcal{F}^{p}=\left\\{\mathbf{f}_{0}^{p},\mathbf{f}_{1}^{p},\cdots,\mathbf{f}_{q^{d}-1}^{p}\right\\}$.

∎

######  Remark 4.3.

According to Lemma 2.5, we know the ZCCS constructed from Theorem 4.2 is
optimal since $M/N=q^{v+d}/q^{d}=L/Z$ is available. In particular, when $v=0$,
the Theorem 4.2 changes into Theorem 4.1.

######  Example 4.4.

Let $a_{1,1}=b=1$, $q=4$, $m=3$, $v=1$, $d=1$, $m_{1}=2$,
$(\pi_{1}(1),\pi_{1}(2))=(2,1)$, $h_{0}=1$,
$(h_{1,1},h_{2,1},h_{3,1})=(1,2,2)$, $(h_{1,2},h_{2,2},h_{3,2})=(3,1,0)$ and
$(h_{1,3},h_{2,3},h_{3,3})=(2,1,3)$ in Theorem 4.2. Then
$\left\\{\mathcal{F}^{0},\mathcal{F}^{1},\cdots,\mathcal{F}^{15}\right\\}$
forms a quaternary $(16,4,64,16)$-ZCCS, where $\mathcal{F}^{3}$ and
$\mathcal{F}^{10}$ are given by

$\begin{bmatrix}\mathbf{f}^{3}_{0}\\\ \mathbf{f}^{3}_{1}\\\
\mathbf{f}^{3}_{2}\\\
\mathbf{f}^{3}_{3}\end{bmatrix}=\begin{bmatrix}1212133132323311121213313232331112121331323233111212133132323311\\\
1212200210102200121220021010220012122002101022001212200210102200\\\
1212311332321133121231133232113312123113323211331212311332321133\\\
1212022010100022121202201010002212120220101000221212022010100022\par\end{bmatrix}$
$\begin{bmatrix}\mathbf{f}^{10}_{0}\\\ \mathbf{f}^{10}_{1}\\\
\mathbf{f}^{10}_{2}\\\
\mathbf{f}^{10}_{3}\end{bmatrix}=\begin{bmatrix}1133121231133232331130301331101011331212311332323311303013311010\\\
1133232313312121331101013113030311332323133121213311010131130303\\\
1133303031131010331112121331323211333030311310103311121213313232\\\
1133010113310303331123233113212111330101133103033311232331132121\par\end{bmatrix}$

The sum of aperiodic auto-correlation of sequences $\mathcal{F}^{3}$ is
presented in Figure 2 and the sum of aperiodic cross-correlation of sequences
$\mathcal{F}^{3}$ and $\mathcal{F}^{10}$ is presented in Figure 2.

Figure 1: Auto-correlation of $\mathcal{F}^{3}$

Figure 2: Cross-correlation of $F^{3}$ and $\mathcal{F}^{10}$

##  5 Comparison

Table 1: Summary of Existing MOCSs Source |  Based on |  Parameters |  Conditions
---|---|---|---
[13] |  GBF |  $(2^{k},2^{k},2^{m})$ |  $0<k\leq m$
[14] |  GBF |  $(2^{k^{\prime}},2^{k+1},2^{m}+2^{t})$ |  $0<k,t\leq m;0\leq{k^{\prime}}\leq t;{k^{\prime}}\leq{k-1}$
[14] |  GBF |  $(2^{k},2^{k+1},2^{m}+2^{t})$ |  $0<k\leq t\leq m$
[15] |  GBF |  $(2^{k},2^{k+1},2^{m}+2^{t})$ |  $0\leq t<k\leq m$
[16] |  GBF |  $(2^{k+1},2^{k+1},2^{m-1}+2^{m-3})$ |  $k\leq m-5$
[17] |  $q$-ary function |  $(p^{n+1},p^{n+1},p^{m})$ |  $p$ is a prime number, $0<n<m$
[18] |  MVF |  $(\prod^{k}_{i=1}p_{i}^{n_{i}},\prod^{k}_{i=1}p_{i}^{n_{i}},\prod^{k}_{i=1}p_{i}^{m_{i}})$ |  $p_{i}|q,$ $q$ is a finite positive integer, $i\in\mathbb{N}_{k}$,$0<n_{i}\leq m_{i}$
[20] |  PU matrix |  $(M,M,M^{m})$ |  $m>0$, $M$ is the order of PU matrix
[21] |  PU matrix |  $(M,M,N^{m})$ |  $N|M,m>0$, $M$ is the order of PU matrix
[22] |  Kronecker product |  $(M_{1}M_{2},M_{1}M_{2},N_{1}N_{2})$ |  $(M_{1},M_{1},N_{1})$-CCC and $(M_{2},M_{2},N_{2})$-CCC, $M1,M2,N_{1},N_{2}$ are four even numbers
[23] |  Kronecker product |  $(M,M,MN_{1}N_{2})$ |  $(M,M,N_{1})$-CCC and $(M,M,N_{2})$-CCC, $2\leq M,N_{1},N_{2}$
[24] |  Extended correlation |  $(MP,MP,2N-1)$ |  $(M,M,N)$-CCC and $(P,P,N)$\- CCC, $2\leq M,P,N$
[40] |  concatenation |  $(M_{1}M_{2}/2,M_{1}M_{2}/2,2L_{1}L_{2})$ |  $M_{1},M_{2}$ are two even numbers, $L_{1},L_{2}$ are two positive integers
Theorem 3.6 |  EBF |  $(q^{d^{\prime}},q^{v+d},a_{m}q^{m-1}+\sum^{v-1}_{k=1}a_{k}q^{m-v+k-1}+q^{u})$ |  $0<d^{\prime}<d<m$, $a_{k}\in\mathbb{Z}_{q}$, $a_{m}\in\mathbb{Z}^{*}_{q}$, and $q\geq 2$ is a positive integer
Table 2: Summary of Existing ZCCSs Source |  Based on |  Parameters |  Conditions |  Optimal |  Remark
---|---|---|---|---|---
[19] |  GBF |  $(2^{k+1},2^{k+1},3\cdot 2^{m},2^{m+1})$ |  $0<k\leq m$ |  $\times$ |  Direct
[19] |  GBF |  $(2^{k+2},2^{k+2},2^{m}\cdot L,2^{m}\cdot L^{\prime})$ |  $L^{\prime}>\frac{L}{2}$ |  $\surd$ |  Direct
[19] |  GBF |  $(2^{k+1},2^{k+1},3\times 2^{m},2^{m+1})$ |  $m>0,k>0$ |  $\surd$ |  Direct
[26] |  GBF |  $(2^{k+v},2^{k},2^{m},2^{m-v})$ |  $v\leq m,k\leq m-v$ |  $\surd$ |  Direct
[28] |  GBF |  $(2^{n},2^{n},2^{m-1}+2,2^{m-2}+2^{\pi(m-3)}+1)$ |  $\pi$ is a permutation of $\mathbb{N}_{m-2}$, $m\geq 3$ |  $\surd$ |  Direct
[28] |  GBF |  $(2^{n+1},2^{n+1},2^{m-1}+2,2^{m-2}+2^{\pi(m-3)+1})$ |  $\pi$ is a permutation of $\mathbb{N}_{m-2}$, $v\leq m$, $q\geq 2$, $m\geq 2$ |  $\surd$ |  Direct
[29] |  GBF |  $(2^{n+p},2^{n},2^{m},2^{m-p})$ |  $p\leq m$ |  $\surd$ |  Direct
[30] |  GBF |  $(2^{k+p+1},2^{k+1},2^{m},2^{m-p})$ |  $k+p\leq m$ |  $\surd$ |  Direct
[31] |  GBF |  $(2^{k+1},2^{k+1},3(2^{m-1}+2^{m-3}),2(2^{m-1}+2^{m-3}))$ |  $m\geq 5$, $k>0$ |  $\surd$ |  Direct
[31] |  GBF |  $(R2^{k+l},2^{k+1},R(2^{m-1}+2^{m-3}),2^{m-1}+2^{m-3})$ |  $m\geq 5$, $k>0$, and $R$ is even |  $\surd$ |  Direct
[34] |  BH Matrix |  $(MP,M,MP,M)$ |  $M,P$ are the order of BH matrix |  $\surd$ |  Indirect
[34] |  Optimal ZPU Matrix |  $(MP,M,M^{N+1}P,M^{N+1})$ |  $M,P$ are the order of BH matrix, $N>0$ |  $\surd$ |  Indirect
[35] |  Hadamard product |  $(2^{n+1},2^{n+1},N,Z)$ |  $N\geq 3,$ $N$ is odd, $\lfloor\frac{N}{Z}=1\rfloor$ |  $\surd$ |  Direct
[35] |  ZCP |  $(2^{m},2^{m},L,Z)$ |  $Z\geq\lceil\frac{L}{2}\rceil$ |  $\surd$ |  Direct
[37] |  PBF |  $(\prod^{l}_{i=1}p_{i}2^{n+1},2^{n+1},2^{m}\prod^{l}_{i=1}p_{i},2^{m})$ |  $\forall p_{i}$ is a prime, $n,m>0$ |  $\times$ |  Direct
[38] |  PBF |  $(p2^{k+1},2^{k+1},p2^{m},2^{m})$ |  $p$ is a prime |  $\surd$ |  Direct
[39] |  MVF |  $(\prod^{k}_{i=1}p_{i}^{2},\prod^{k}_{i=1}p_{i},\prod^{k}_{i=1}p_{i}^{m_{i}},\prod^{k}_{i=1}p_{i}^{m_{i}-1})$ |  $p_{i}$ is a prime number, $m_{i}>0$ |  $\surd$ |  Direct
[40] |  EBF |  $(q^{v+1},q,q^{m},q^{m-v})$ |  $q\geq 2$, $v\leq m$ |  $\surd$ |  Direct
Theorem 4.2 |  EBF |  $(q^{v+d},q^{d},q^{m},q^{m-v})$ |  $v<m$, $d\leq m-v$, $q\geq 2$ is a positive integer |  $\surd$ |  Direct

Table 1 and Table 2 show the existence of constructions of MOCSs and ZCCSs in
previous papers. The notation “$\surd$” (resp. “$\times$”) in Table 2 means
the corresponding ZCCSs are optimal (resp. non-optimal).

From Table 1, we know that all GBFs based MOCSs have lengths of $2^{m}$ or
$2^{m}+2^{t}$ [13, 14, 15, 16]. The constructions in [17] and [18] generate
MOCSs with flexible lengths by using $q$-ary functions and MVFs, respectively.
But both of these methods only have power of two lengths when $q=2.$ Other
methods for designing MOCSs include PU matrices [20, 21], interleaving,
Kronecker product [23, 22], extended correlation [24] and concatenation [40].
However, These methods are hard to be applied in engineering due to their
large space and time requirements in hardware generation. Compablack with the
previous constructions, our results have flexible lengths and non-power-of-two
lengths when $q=2$.

From Table 2, we know the constructions of ZCCSs in the literature mainly
divided into direct and indirect approaches. The direct methods are mainly
based on GBFs [28, 29, 30, 26, 19, 31], Pseudo-Boolean functions (PBFs) [37,
38], EBFs [40] and MVFs [39]. In fact, all existing ZCCSs constructed based on
GBFs and PBFs have multiples of two lengths and the ZCCSs based on MVFs have
limited set sizes. For other indirect methods, some researchers provided ZCCSs
by Hadamard product [35], Z-complementary pairs (ZCPs) [35], BH matrix and
optimal Z-paraunitary (ZPU) matrices [34]. These constructs are difficult to
implement on hardware. In the case of the same length and ZCZ width,
compablack to [40], the proposed ZCCSs have larger set sizes or lengths.
Moreover, our ZCCSs can accommodate more users on the basis of achieving the
optimality.

##  6 Conclusion

In this paper, we mainly present a construction of optimal ZCCSs and a
construction of MOCSs with flexible lengths based on EBFs. According to the
arbitrariness of $q$, the proposed MOCSs cover the result in [18] and have
non-power-of-two lengths when $q=2$. Moreover, the resulting MOCSs can be
obtained directly from EBFs without using tedious sequence operations. The
proposed MOCSs with flexible lengths find many applications in wireless
communication due to its good correlation properties. The proposed ZCCSs are
optimal with respect to the theoretical upper bound and we can obtain a new
class of ZCCSs of arbitrary lengths with large zero correlation zone width.

## Declarations

Funding This research was supported by the National Natural Science Foundation
of China (Grant No. 12171241)
Conflicts of Interest The authors declare that they have no conflicts of
interest.
Ethics approval and consent to participate Not applicable.
Consent for publication Not applicable.

## References

  * [1] Golay M.J.E.: Complementary series. IEEE Trans. Inf. Theory. 7(2), 82-87 (1961).
  * [2] Tseng C.C. and Liu C.: Complementary sets of sequences. IEEE Trans. Inf. Theory. 18(5), 644-652 (1972).
  * [3] Suehiro N., and Hatori M.: N-shift cross-orthogonal sequences. IEEE Trans. Inf. Theory. 34(1), 143-146 (1988).
  * [4] Tasinkevych Y., Trots I., and Nowicki A.: Mutually orthogonal Golay complementary sequences in the simultaneous synthetic aperture method for medical ultrasound diagnostics. Ultrasonics. 115 (2021).
  * [5] Zhang Z., Tian F., Zeng F., Ge L., and Xuan G.: Mutually orthogonal complementary pairs for OFDM-CDMA systems. 12th Int. conf. Signal Process, HangZhou. 1761-1765 (2014).
  * [6] Aparicio J., and Shimura T.: Asynchronous detection and identification of multiple users by multi-carrier modulated complementary set of sequences. IEEE Access. 6, 22054-22069 (2018).
  * [7] Liu Z., Guan Y.L., and Parampalli U.: New complete complementary codes for peak-to-mean power control in multi-carrier CDMA. IEEE Trans. Commun. 62(3), 1105-1113 (2014).
  * [8] Tseng S.M. and Bell M.R.: Asynchronous multicarrier DS-CDMA using mutually orthogonal complementary sets of sequences,” IEEE Trans. Commun. 48(1), 53-59 (2000).
  * [9] Davis J. A., and Jedwab J.: Peak-to-mean power control in OFDM, Golay complementary sequences, and Reed-M$\rm\ddot{u}$ller codes. IEEE Trans. Inf. Theory. 45(7), 2397-2417 (1999).
  * [10] Paterson K.G.: Generalized Reed-M$\rm\ddot{u}$ller codes and power control in OFDM modulation. IEEE Trans. Inf. Theory. 46(1), 104-120 (2000).
  * [11] Li Y., and Chu W. B.: More Golay sequences. IEEE Trans. Inf. Theory. 51(3), 1141-1145 (2005).
  * [12] Chen C. Y., Wang C. H., and Chao C. C.: Complementary sets and Reed-M$\rm\ddot{u}$ller codes for peak-to-average power ratio blackuction in OFDM. in Proc. 16th Int. Symp. AAECC. 3857, 317-327 (2006).
  * [13] Rathinakumar A., and Chaturvedi A.K.: Complete mutually orthogonal golay complementary sets from Reed-M$\rm\ddot{u}$ller codes. IEEE Trans. Inf. Theory. 54(3), 1339-1346 (2008).
  * [14] Wu S., Chen C., and Li Z.: How to construct mutually orthogonal complementary sets with non-power-of-two lengths?. IEEE Trans. Inf. Theory. 67(6), 3464-3472 (2021).
  * [15] Tian L., Lu X., Xu C., and Li Y.: New mutually orthogonal complementary sets with non-power-of-two lengths. IEEE Commun. Lett. 28, 359-363 (2021).
  * [16] Kumar P., Majhi S., and Paul S.: A direct construction of GCP and binary CCC of length non-power-of-two. arXiv:2109.08567 (2021).
  * [17] Sarkar P., Li C., Majhi S., and Liu Z.: New correlation bound and construction of quasi-complementary code sets. arXiv: 2204.13538 (2022)
  * [18] Sarkar P., Liu Z., and Majhi S.: Multivariable function for new complete complementary codes with arbitrary lengths. arXiv:2102.10517 (2021).
  * [19] Xie C., Sun Y., and Ming Y.: Constructions of optimal binary Z-complementary sequence sets with large zero correlation zone. IEEE Signal Process. Lett. 28, 1694-1698 (2021).
  * [20] Das S., Budišin S., Majhi S., Liu Z., and Guan Y.L. : A multiplier-free generator for polyphase complete complementary codes. IEEE Trans. Signal Process. 66(5), 1184-1196 (2018).
  * [21] Das S., Majhi S., and Liu Z.: A novel class of complete complementary codes and their applications for APU matrices. IEEE Signal Process. Lett. 25(9), 1300-1304 (2018).
  * [22] Jin Y., and Koga H.: Basic properties of the complete complementary codes using the DFT matrices and the Kronecker products. In Proc. 2008 International Symp. Inf. Theory and Its Appl. 1-6 (2008).
  * [23] Gu Z., Zhou Z., Adhikary A., Feng Y., and Fan P.: Asymptotically optimal Golay-ZCZ sequence sets with flexible length. arXiv:2112.08678 (2021).
  * [24] Liu K., Liu J., and Ni J.: Generalized construction of Z-complementary code sets of odd length. IEEE Signal Process. Lett. 30, 354-358 (2023).
  * [25] Fan P., Yuan W., and Tu Y.: Z-complementary binary sequences. IEEE Signal Process. Lett. 14(8), 509-512 (2007).
  * [26] Wu S., and Chen C.: Optimal Z-complementary sequence sets with good peak-to-average power-ratio property. IEEE Signal Process. Lett. 25(10), 1500-1504 (2018).
  * [27] Wu S. W., Sahin A., Huang Z. M., and Chen C. Y.: Z-complementary code sets with flexible lengths from generalized Boolean functions. IEEE Access. 9, 4642-4652 (2021).
  * [28] Sarkar P., Roy A., and Majhi S.: Construction of Z-complementary code sets with non-power-of-two lengths based on generalized Boolean functions. IEEE Commun. Lett. 24(8), 1607-1611 (2020).
  * [29] Sarkar P., and Majhi S.: A direct construction of optimal ZCCS with maximum column sequence PMEPR two for MC-CDMA system. IEEE Commun. Lett. 25(2), 337-341 (2021).
  * [30] Sarkar P., Majhi S., and Liu Z.: Optimal Z-complementary code set from generalized Reed-M$\rm\ddot{u}$ller codes. IEEE Trans. Commun. 67(3), 1783-1796 (2019).
  * [31] Ghosh G., Majhi S., Paul S.: Construction of optimal binary Z-complementary code sets with new lengths. arXiv:2301.03294 (2023).
  * [32] Tian L., Li Y., Zhou Z., and Xu C.: Two classes of Z-complementary code sets with good cross-correlation subsets via paraunitary matrices. IEEE Trans. Commun. 69(5), 2935-2947 (2021).
  * [33] Yu T., Adhikary A. R., Wang Y., and Yang Y.: New class of optimal Z-complementary code sets. IEEE Signal Process. Lett. 29(5), 1477-1481 (2022).
  * [34] Das S., Parampalli U., Majhi S., Liu Z., and S. Budišin.: New optimal Z-complementary code sets based on generalized paraunitary matrices. IEEE Trans. Commun. 68, 5546-5558 (2020).
  * [35] Adhikary A., and Majhi S.: New construction of optimal aperiodic Z-complementary sequence sets of odd-lengths. Electron. Lett. 55(19), 1043-1045 (2019).
  * [36] Li Y., and Xu C.: ZCZ aperiodic complementary sequence sets with low column sequence PMEPR. IEEE Commun. Lett. 19(8), 1303-1306 (2015).
  * [37] Ghosh G., Sudhan M., Palash S., and Ashish K.U.: Direct construction of optimal Z-complementary code sets for all possible even length by using pseudo-Boolean functions. IEEE Signal Process. Lett. 29, 872-876 (2022).
  * [38] Sarkar P., Majhi S., and Liu Z.: Pseudo-Boolean functions for optimal Z-complementary code sets with flexible lengths. IEEE Signal Process. Lett. 28, 1350-1354 (2021).
  * [39] Roy A., Majhi S.: Construction of inter-group complementary code set and 2-D Z-complementary array code set based on multivariable functions. arXiv:2109.00970 (2021).
  * [40] Shen, B., Meng, H., Yang, Y. et al. New constructions of Z-complementary code sets and mutually orthogonal complementary sequence sets. Des. Codes Cryptogr. 91, 353-371 (2023).
  * [41] Feng L., Fan P., and Zhou X.: Lower bounds on correlation of Z-complementary code sets. Wirel. Pers. Commun.  72(2), 1475-1488 (2013).
  * [42] Chen C.: Complementary sets of non-power-of-two length for peak-to-average power ratio blackuction in OFDM. IEEE Trans. Inf. Theory. 62(12), 7538-7545 (2016).
  * [43] Chen C.: A novel construction of complementary sets with flexible lengths based on Boolean functions. IEEE Commun. Lett. 22(2), 260-263 (2018).
  * [44] Chen C., Wang C.H., and Chao C.C.: Complete complementary codes and generalized Reed-M$\rm\ddot{u}$ller codes. IEEE Commun. Lett. 12(11), 849-851 (2008).