1 Introduction

An (N,K) codebook \(\mathcal {C}\) (also called a signal set) is a set of N unit-norm complex vectors ci with length K, where 0 ≤ i ≤ N − 1. For all pairs of distinct vectors in \(\mathcal {C}\), the maximum cross-correlation amplitude of \(\mathcal {C}\) is defined by

$$I_{max}(\mathcal{C})=\underset{0\leq i\neq j \leq N-1}{\max}|\mathbf{c}_{i}\mathbf{c}_{j}^{H}|, $$

where \(\mathbf {c}_{j}^{H}\) is the conjugate transpose of the complex vector cj. In code division multiple access (CDMA) systems, codebooks with small \(I_{max}(\mathcal {C})\) are utilized to separate the signals of different users. The optimization of various performance indicators such as outage probability, average signal-to-noise ratio and symbol error probability for multiple-antenna transmit beamforming from limited-rate feedback can be achieved by minimizing the maximum cross-correlation amplitude \(I_{max}(\mathcal {C})\) of a codebook \(\mathcal {C}\) [16, 19]. For a certain length K, it is desirable to design a codebook such that the number of the vectors N is as large as possible and the maximum cross-correlation amplitude \(I_{max}(\mathcal {C})\) is as small as possible. However, between the parameters N, K and \(I_{max}(\mathcal {C})\) of a codebook \(\mathcal {C}\), there exists a tradeoff, known as Welch bound [27].

Lemma 1

[27] For any(N,K) codebook\(\mathcal {C}\)withN ≥ K,

$$I_{max}(\mathcal{C})\geq I_{W}=\sqrt{\frac{N-K}{(N-1)K}}. $$

Moreover, the equality holds if and only if for all pairs of (i, j) with i≠j, it holds that

$$|\mathbf{c}_{i}\mathbf{c}_{j}^{H}|=\sqrt{\frac{N-K}{(N-1)K}}. $$

We term \(\mathcal {C}\) a maximum-Welch-bound-equality (MWBE) codebook [23] if \(\mathcal {C}\) achieves the Welch bound. MWBE codebooks have many applications in communications [23], CDMA systems [20], compressed sensing [1], coding theory [6] and quantum computing [22]. MWBE codebooks can also be described by equiangular tight frames [25] or line packing in Grassmannian spaces [24]. With the wide utilization, the constructions of MWBE codebooks have attracted much attention and the known classes of MWBE codebooks are presented as follows:

  • (N,N) orthogonal MWBE codebooks for any N > 1 [23, 28];

  • (N,N − 1) MWBE codebooks for N > 1 based on discrete Fourier transformation matrices [23, 28] or m-sequences [23];

  • (N,K) MWBE codebooks from conference matrices [2, 24], where N = 2K = 2d+ 1 for a positive integer d or N = 2K = pd + 1 for a prime p and a positive integer d;

  • (N,K) MWBE codebooks based on (N,K,λ) difference sets in cyclic groups [28] and abelian groups [4, 5];

  • (N,K) MWBE codebooks from (2,k,ν)-Steiner systems [7];

  • (N,K) MWBE codebooks depended on graph theory and finite geometries [8,9,10, 21].

Aside from MWBE codebooks, many researchers concern about asymptotically optimal codebooks \(\mathcal {C}\), i.e., the maximum cross-correlation amplitude asymptotically achieves the Welch bound for the sufficiently large length of the vectors. As a generalization of the MWBE codebooks derived from difference sets, several classes of asymptotically optimal codebooks were generated from almost difference sets [11, 15, 30, 31], relative difference sets [32]. In [3, 12, 29], asymptotically optimal codebooks constructed from binary row selection sequences were proposed. In [26], Tan et al. proposed a class of asymptotically optimal codebooks by using Gauss sums. Employing Jacobi sums, Heng et al. [13] presented two classes of asymptotically optimal codebooks. As generalizations of Heng et al.’s work, the authors provided several classes of asymptotically optimal codebooks in [14, 17].

Assume that G1 and G2 are sets. Let D1 and D2 be subsets of G1 and G2, respectively. We define the operation of D1 and D2 by

$$D_{1}\bigtriangledown D_{2}=(D_{1}\times \overline{D}_{2})\cup (\overline{D}_{1}\times D_{2}), $$

where \(\overline {D}_{1}=G_{1}\setminus D_{1}\), \(\overline {D}_{2}=G_{2}\setminus D_{2}\) and D1 × D2 = {(a,b) : a ∈ D1, b ∈ D2}. When D1 and D2 are difference sets, Hu et al. [11] constructed two classes of asymptotically optimal codebooks. Motivated by their work, we investigate the case that D1 and D2 are certain sets and propose two classes of codebooks asymptotically meeting the Welch bound. Notably, the parameters of our codebooks are new and flexible in some cases. For reference, the parameters of known classes of codebooks asymptotically achieving the Welch bound and the new ones are given in Table 1.

Table 1 The parameters of codebooks asymptotically meeting the Welch bound
Full size table

This paper is organized as follows. In Section 2, we briefly recall some definitions and notation which will be needed in our discussion. We devote Sections 3 and 4 to our constructions of asymptotically optimal codebooks. Finally, Section 5 concludes this paper.

2 Preliminaries

Let q = ps and \(\mathbb {F}_q\) denote the finite field with q elements, where p is a prime number and s is a positive integer. The trace function from \(\mathbb {F}_{q}\) to \(\mathbb {F}_p\) is defined by

$$\text{Tr}_{q}(x)=x+x^{p}+\cdots+x^{p^{s-1}}, $$

where \(x\in \mathbb {F}_q\).

Denote by \(\mathbb {F}_q^{*}\) the multiplicative group of \(\mathbb {F}_q\). It is well-known that \(\mathbb {F}_q^{*}\) is a cyclic group of order q − 1. A generator of \(\mathbb {F}_q^{*}\) is said to be a primitive element of the finite field \(\mathbb {F}_q\). Assume that α is a primitive element of \(\mathbb {F}_q\). For each integer i with 0 ≤ i ≤ q − 2, a multiplicative character φi of \(\mathbb {F}_q\) is defined by

$$\varphi_{i}(\alpha^{j})=\xi_{q-1}^{ij}, $$

where 0 ≤ j ≤ q − 2 and \(\xi _{q-1}=e^{2\pi \sqrt {-1}/(q-1)}\). Each multiplicative character of \(\mathbb {F}_q\) can be obtained in this way. If i = 0, the multiplicative character φ0 is called the trivial multiplicative character of \(\mathbb {F}_q\). For any multiplicative character φi of \(\mathbb {F}_q\), its conjugate \(\overline {\varphi _i}\) is given by \(\overline {\varphi _i}(g)=\overline {\varphi _i(g)}=\varphi _i(g^{-1})\), where \(g\in \mathbb {F}_q^{*}\). All the multiplicative characters of \(\mathbb {F}_q\) form a cyclic group \(\widehat {\mathbb {F}_q^{*}}\) under the multiplication of characters defined as follows:

$$\chi\psi(g)=\chi(g)\psi(g), $$

for every \(g\in \mathbb {F}_q^{*}\), where χ, ψ are multiplicative characters of \(\mathbb {F}_q\). The group \(\widehat {\mathbb {F}_q^{*}}\) is isomorphic to the multiplicative group \(\mathbb {F}_q^{*}\). The orthogonal relations of \(\mathbb {F}_q^{*}\) and \(\widehat {\mathbb {F}_q^{*}}\) are

$$\sum\limits_{g\in \mathbb{F}_{q}^{*}}\varphi(g)=\left\{ \begin{array}{ll} 0,& \text{if } \varphi \text{ is a nontrivial multiplicative character of } \mathbb{F}_{q},\\ q-1,& \text{if } \varphi \text{ is the trivial multiplicative character of } \mathbb{F}_{q}, \end{array} \right. $$

and

$$\sum\limits_{\varphi\in \widehat{\mathbb{F}_{q}^{*}}}\varphi(g)=\left\{ \begin{array}{ll} 0,& \text{if } g\neq 1\in \mathbb{F}_{q}^{*},\\ q-1,& \text{if } g = 1. \end{array} \right. $$

For each \(a\in \mathbb {F}_q\), an additive character of \(\mathbb {F}_q\) is defined by the function \(\chi_a(x)=\zeta _p^{\text{Tr}_q(ax)}\), where \(\zeta _p=e^{2\pi \sqrt {-1}/p}\). If a = 1, then χ1(x) is the canonical additive character of \(\mathbb {F}_q\). Let χ0(x) denote the trivial additive character of \(\mathbb {F}_q\). The additive character of \(\mathbb {F}_q\) has the similar properties as the multiplicative character of \(\mathbb {F}_q\). For more details on the character theory over finite fields, we refer the reader to [18, Chapter. 5].

Luo et al. [17] established the hyper Eisenstein sum over \(\mathbb {F}_q\). Let \(D=\{(x_1,x_2,\cdots , x_n )\in (\mathbb {F}_q^{*})^n: \text{Tr} _{q}(x_1+x_2+\cdots +x_n)= 1\}\) and assume that φ1,⋯ ,φn are multiplicative characters of \(\mathbb {F}_q\). Then the hyper Eisenstein sum is given by

$$E_{q}(\varphi_{1},\cdots,\varphi_{n})=\sum\limits_{(x_{1},x_{2},\cdots, x_{n} )\in D}\varphi_{1}(x_{1})\cdots\varphi_{n}(x_{n}). $$

The following two lemmas evaluate the absolute value of the hyper Eisenstein sums.

Lemma 2

[17] For 1 ≤ k < n, assume thatφ1,⋯ ,φkare nontrivial multiplicativecharacters of\(\mathbb {F}_q\)andφk+ 1,⋯ ,φnare trivial multiplicativecharacters of\(\mathbb {F}_q\).Then

$$E_{q}(\varphi_{1},\cdots,\varphi_{n})=(-1)^{n-k}E_{q}(\varphi_{1},\cdots,\varphi_{k}). $$

Lemma 3

[17] Letφ1,⋯ ,φnbe nontrivialmultiplicative characters of\(\mathbb {F}_q\).Denote by (φ1⋯φn)∗the restriction ofφ1⋯φnto\(\mathbb {F}_p\).Then

$$|E_{q}(\varphi_{1},\cdots,\varphi_{n})|=\left\{ \begin{array}{ll} p^{\frac{sn-1}{2}},& \text{if } (\varphi_{1}\cdots\varphi_{n})^{*} \text{ is nontrivial,}\\ p^{\frac{sn-2}{2}},& \text{if } (\varphi_{1}\cdots\varphi_{n})^{*} \text{ is trivial.} \end{array} \right. $$

If p = 2, (φ1⋯φn)∗ is always trivial which leads to the following proposition.

Proposition 1

Letq = 2s, wheresis a positive integer.Assume thatφ1,⋯ ,φnare nontrivialmultiplicative characters of\(\mathbb {F}_q\).Then

$$|E_{q}(\varphi_{1},\cdots,\varphi_{n})|= 2^{\frac{sn-2}{2}}. $$

3 A new construction of asymptotically optimal codebooks

In this section, we propose a construction of asymptotically optimal codebooks by the operation D1 ▽ D2. We begin with the definitions of two certain sets.

Let n ≥ 1, s1 > 1 and s2 > 1 be positive integers. Throughout the section, we write \(q_1 = 2^{s_1}\) and \(q_2 = 2^{s_2}\). Put \(D_1=\{(x_1,x_2,\cdots , x_n )\in (\mathbb {F}_{q_1}^{*})^n: \text{Tr} _{q_1}(x_1+x_2+\cdots +x_n)= 1\}\) and \(D_2=\{(x_1,x_2,\cdots , x_n )\in (\mathbb {F}_{q_2}^{*})^n: \text{Tr} _{q_2}(x_1+x_2+\cdots +x_n)= 1\}\). To determine the cardinalities of D1 and D2, we need the following lemma.

Lemma 4

[17] Letq = ps, wherepis a prime ands > 1 is a positive integer.Assume that\(F=\{(x_1,x_2,\cdots , x_n )\in (\mathbb {F}_q^{*})^n: \text{Tr} _{q}(x_1+x_2+\cdots +x_n)=a\}\).Then

$$\#F=\left\{ \begin{array}{ll} \frac{(p^{s}-1)^{n}+(-1)^{n + 1}}{p},& \text{if } a\in\mathbb{F}_{p}^{*},\\ \frac{(p^{s}-1)^{n}+(-1)^{n}(p-1)}{p},& \text{if } a = 0. \end{array} \right. $$

Applying Lemma 4, we deduce that \(\#D_1=\frac {(q_1-1)^n+(-1)^{n + 1}}{2}\) and \(\#D_2=\frac {(q_2-1)^n+(-1)^{n + 1}}{2}\). Let \(D=(D_1\times \overline {D}_2)\cup (\overline {D}_1\times D_2)\), where \(\overline {D}_1=(\mathbb {F}_{q_1}^{*})^n\setminus D_1\), \(\overline {D}_2=(\mathbb {F}_{q_2}^{*})^n\setminus D_2\). It is easy to check that \(\#D=\frac {(q_1-1)^n(q_2-1)^n-1}{2}\). For simplicity, we write \(K=\frac {(q_1-1)^n(q_2-1)^n-1}{2}\).

Assume that φ1,⋯ ,φn are multiplicative characters of \(\mathbb {F}_{q_1}\) and λ1,⋯ ,λn are multiplicative characters of \(\mathbb {F}_{q_2}\). Then we define a vector of length K by

$$\mathbf{c}_{U,V}=\frac{1}{\sqrt{K}}(\varphi_{1}(x_{1})\cdots\varphi_{n}(x_{n})\lambda_{1}(y_{1})\cdots\lambda_{n}(y_{n}))_{X\times Y\in D}, $$

where U = (φ1,⋯ ,φn), V = (λ1,⋯ ,λn), X = (x1,⋯ ,xn) and Y = (y1,⋯ ,yn). When U and V run over the multiplicative characters groups \((\widehat {\mathbb {F}}_{q_1}^{*})^n\) and \((\widehat {\mathbb {F}}_{q_2}^{*})^n\), respectively, we obtain a set \(\mathcal {C}\) of (q1 − 1)n(q2 − 1)n unit-norm complex vectors as follows:

$$ \mathcal{C}=\{\mathbf{c}_{U,V}:U\in(\widehat{\mathbb{F}}_{q_{1}}^{*})^{n},V\in(\widehat{\mathbb{F}}_{q_{2}}^{*})^{n}\}. $$
(1)

Theorem 1

Lets1 > 1 ands2 > 1 betwo positive integers. Assume that\(q_1 = 2^{s_1}\)and\(q_2 = 2^{s_2}\).Then the set\(\mathcal {C}\)definedby (1) is an\(\left (N=(q_1-1)^n(q_2-1)^n,K=\frac {(q_1-1)^n(q_2-1)^n-1}{2}\right )\)codebookwith the maximum cross-correlation amplitude\(I_{max}(\mathcal {C})=\frac {2^{\frac {s_1n+s_2n}{2}}}{(2^{s_1}-1)^n(2^{s_2}-1)^n-1}\).

Proof

According to the definition of the codebook \(\mathcal {C}\), it can be easily shown that \(N=(q_1-1)^n(q_2-1)^n\) and \(K=\frac {(q_1-1)^n(q_2-1)^n-1}{2}\). Our task now is to calculate the maximum cross-correlation amplitude. For simplicity, we take N1 = (q1 − 1)n, N2 = (q2 − 1)n, \(K_1=\#D_1=\frac {(q_1-1)^n+(-1)^{n + 1}}{2}\) and \(K_2=\#D_2=\frac {(q_2-1)^n+(-1)^{n + 1}}{2}\). Assume that \(U=(\varphi _1,\cdots ,\varphi _n),U^{\prime }=(\varphi _1^{\prime },\cdots ,\varphi _n^{\prime })\in (\widehat {\mathbb {F}}_{q_1}^{*})^n\) and \(V=(\lambda _1,\cdots ,\lambda _n),V^{\prime }=(\lambda _1^{\prime },\cdots ,\lambda _n^{\prime })\in (\widehat {\mathbb {F}}_{q_2}^{*})^n\). For any two distinct vectors \(\mathbf {c}_{U,V}\) and \(\mathbf {c}_{U^{\prime },V^{\prime }}\) with \((U,V)\neq (U^{\prime },V^{\prime })\), we have

$$\begin{array}{@{}rcl@{}} \left|\mathbf{c}_{U,V}\mathbf{c}_{U^{\prime},V^{\prime}}^{H}\right|&=&\frac{1}{K}\left|\sum\limits_{(x_{1},\cdots x_{n})\in D_{1}}\varphi_{1}\overline{\varphi_{1}^{\prime}}(x_{1})\cdots\varphi_{n}\overline{\varphi_{n}^{\prime}}(x_{n})\sum\limits_{(y_{1},\cdots y_{n})\in \overline{D}_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})\right.\\ &&+\left.\sum\limits_{(x_{1},\cdots x_{n})\in \overline{D}_{1}}\varphi_{1}\overline{\varphi_{1}^{\prime}}(x_{1})\cdots\varphi_{n}\overline{\varphi_{n}^{\prime}}(x_{n})\sum\limits_{(y_{1},\cdots y_{n})\in D_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})\right|. \end{array} $$

In the following, we divide the computation of \(\left |\mathbf {c}_{U,V}\mathbf {c}_{U^{\prime },V^{\prime }}^H\right |\) into three cases.

  1. (1)

    If \(\varphi _1\overline {\varphi _1^{\prime }},\cdots ,\varphi _n\overline {\varphi _n^{\prime }}\) are trivial, then \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _n\overline {\lambda _n^{\prime }}\) are not all trivial. Without loss of generality, we assume that \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _k\overline {\lambda _k^{\prime }}\) are nontrivial, where 1 ≤ k ≤ n. So we obtain

    $$\begin{array}{@{}rcl@{}} \left|\mathbf{c}_{U,V}\mathbf{c}_{U^{\prime},V^{\prime}}^{H}\right|&=&\frac{1}{K}\left|K_{1}\sum\limits_{(y_{1},\cdots y_{n})\in \overline{D}_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})\right.\\ &&\left.+(N_{1}-K_{1})\sum\limits_{(y_{1},\cdots y_{n})\in D_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})\right|\\ &=&\frac{|N_{1}-2K_{1}|}{K}\left|E_{q_{2}}(\lambda_{1}\overline{\lambda_{1}^{\prime}},\cdots,\lambda_{n}\overline{\lambda_{n}^{\prime}})\right|, \end{array} $$

    where the last equality is derived from the definition of the hyper Eisenstein sums over \(\mathbb {F}_{q_2}\) and the fact that

    $$\begin{array}{@{}rcl@{}} &&\sum\limits_{(y_{1},\cdots y_{n})\in \overline{D}_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})+\sum\limits_{(y_{1},\cdots y_{n})\in D_{2}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})\\ &&=\sum\limits_{y_{1}\in\mathbb{F}_{q_{2}}^{*}}\lambda_{1}\overline{\lambda_{1}^{\prime}}(y_{1})\cdots\sum\limits_{y_{n}\in\mathbb{F}_{q_{2}}^{*}}\lambda_{n}\overline{\lambda_{n}^{\prime}}(y_{n})= 0. \end{array} $$

    It follows from Lemma 2 and Proposition 1 that

    $$\left|\mathbf{c}_{U,V}\mathbf{c}_{U^{\prime},V^{\prime}}^{H}\right|=\frac{2^{\frac{s_{2}k-2}{2}}}{K}\leq\frac{2^{\frac{s_{2}n-2}{2}}}{K}. $$

    The equality holds if and only if \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _n\overline {\lambda _n^{\prime }}\) are nontrivial.

  2. (2)

    If \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _n\overline {\lambda _n^{\prime }}\) are trivial, using the same argument as in the first case, we can easily deduce that

    $$\left|\mathbf{c}_{U,V}\mathbf{c}_{U^{\prime},V^{\prime}}^{H}\right|=\frac{2^{\frac{s_{1}k-2}{2}}}{K}\leq\frac{2^{\frac{s_{1}n-2}{2}}}{K}. $$

    The equality holds if and only if \(\varphi _1\overline {\varphi _1^{\prime }},\cdots ,\varphi _n\overline {\varphi _n^{\prime }}\) are nontrivial.

  3. (3)

    If \(\varphi _1\overline {\varphi _1^{\prime }},\cdots ,\varphi _n\overline {\varphi _n^{\prime }}\) are not all trivial and \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _n\overline {\lambda _n^{\prime }}\) are not all trivial, without loss of generality, suppose that \(\varphi _1\overline {\varphi _1^{\prime }},\cdots ,\varphi _l\overline {\varphi _l^{\prime }}\) are nontrivial and \(\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _k\overline {\lambda _k^{\prime }}\) are nontrivial, where 1 ≤ l,k ≤ n. By Lemma 2 and Proposition 1, we have

    $$\begin{array}{@{}rcl@{}} \left|\mathbf{c}_{U,V}\mathbf{c}_{U^{\prime},V^{\prime}}^{H}\right|&=&\frac{2}{K}\left|E_{q_{1}}(\varphi_{1}\overline{\varphi_{1}^{\prime}},\cdots,\varphi_{n}\overline{\varphi_{n}^{\prime}})\right| \left|E_{q_{2}}(\lambda_{1}\overline{\lambda_{1}^{\prime}},\cdots,\lambda_{n}\overline{\lambda_{n}^{\prime}})\right|\\ &=&\frac{2^{\frac{s_{1}l+s_{2}k-2}{2}}}{K}\leq\frac{2^{\frac{s_{1}n+s_{2}n-2}{2}}}{K}. \end{array} $$

    The equality holds if and only if \(\varphi _1\overline {\varphi _1^{\prime }},\cdots ,\varphi _n\overline {\varphi _n^{\prime }},\lambda _1\overline {\lambda _1^{\prime }},\cdots ,\lambda _n\overline {\lambda _n^{\prime }}\) are nontrivial.

Combining three cases above, we see that the maximum cross-correlation amplitude

$$I_{max}(\mathcal{C})=\frac{2^{\frac{s_{1}n+s_{2}n-2}{2}}}{K}=\frac{2^{\frac{s_{1}n+s_{2}n}{2}}}{(2^{s_{1}}-1)^{n}(2^{s_{2}}-1)^{n}-1}.$$

Theorem 2

Let the symbols be the same as those in Theorem 1. Then thecodebook\(\mathcal {C}\)definedby (1) asymptotically achieves the Welch bound.

Proof

Since \(\mathcal {C}\) has parameters \((N=(q_1-1)^n(q_2-1)^n,K=\frac {(q_1-1)^n(q_2-1)^n-1}{2})\), the corresponding Welch bound is

$$I_{W}=\sqrt{\frac{N-K}{(N-1)K}}=\sqrt{\frac{K + 1}{2K^{2}}}. $$

Note that the maximum cross-correlation amplitude of \(\mathcal {C}\) is \(I_{max}(\mathcal {C})=\frac {2^{\frac {s_1n+s_2n-2}{2}}}{K}\). Therefore,

$$\frac{I_{max}(\mathcal{C})}{I_{W}}=\sqrt{\frac{2^{s_{1}n+s_{2}n-2}}{K^{2}}\frac{2K^{2}}{K + 1}}=\sqrt{\frac{2^{s_{1}n+s_{2}n}}{(2^{s_{1}}-1)^{n}(2^{s_{2}}-1)^{n}+ 1}}\rightarrow 1, $$

when \(s_1\rightarrow +\infty \) and \(s_2\rightarrow +\infty \).

Remark 1

Let Q1 ≡ 3 mod 4 and Q2 ≡ 3 mod 4. Hu et al. [11, Corollary 1] proposed a \((Q_1Q_2,\frac {Q_1Q_2-1}{2})\) codebook with the maximum cross-correlation amplitude \(I_{max}=\frac {\sqrt {(Q_1 + 1)(Q_2 + 1)}}{Q_1Q_2-1}\). If n = 1, then the codebooks generated by Theorem 1 have the same parameters as the codebooks constructed by Hu. If n > 1 is odd, the codebooks generated by Theorem 1 have the same parameters N,K as the codebooks proposed by Hu. However, the maximum cross-correlation amplitude of our construction is greater than the maximum cross-correlation amplitude of Hu’s construction. If n > 1 is even, the codebooks produced by Theorem 1 have the new parameters due to \((2^{s_1}-1)^n \equiv 1\ \text {mod}\ 4\) and \((2^{s_2}-1)^n \equiv 1\ \text {mod}\ 4\). In Table 2, we list some examples of codebooks generated by Theorem 1 for n = 2 and some given s1 and s2 such that s = s1 = s2. As can be seen, the codebook \(\mathcal {C}\) asymptotically achieves the Welch bound.

Table 2 Parameters of the (N,K) codebook of Theorem 1 for n = 2 and some given s = s1 = s2
Full size table

4 A recursive construction

Based on the construction of asymptotically optimal codebooks in the previous section, we study how to recursively construct asymptotically optimal codebooks with large and flexible parameters.

For convenience, we adopt the following notation throughout this section.

  • Let si > 1 be positive integers and \(q_i = 2^{s_i}\), where 1 ≤ i ≤ l and l > 1 is an integer.

  • For any \(1\leq i\leq l\), we write \(N_i=(q_i-1)^n\), where n ≥ 1 is an integer.

  • \(\mathbb {F}_{q_i}\) is a finite filed with qi elements, where 1 ≤ i ≤ l.

  • \(\text{Tr} _{q_i}(\cdot )\) is the trace function from \(\mathbb {F}_{q_i}\) to \(\mathbb {F}_2\).

  • \(D_i=\{(x_1,x_2,\cdots , x_n )\in (\mathbb {F}_{q_i}^{*})^n: \text{Tr} _{q_i}(x_1+x_2+\cdots +x_n)= 1\}\), where 1 ≤ i ≤ l.

  • \(X_i=(x_{i1},x_{i2},\cdots , x_{in} )\in (\mathbb {F}_{q_i}^{*})^n\) for any 1 ≤ i ≤ l.

In Section 3, we present a construction of asymptotically optimal codebooks from the operation D1 ▽ D2. Here, we consider the similar operation of D1, D2,⋯ ,Dl by a recursive method. Let \((\mathbb {F}_{q_1}^{*})^n\times (\mathbb {F}_{q_2}^{*})^n\times \cdots \times (\mathbb {F}_{q_l}^{*})^n=\{(X_1,X_2,\cdots ,X_l):X_i\in (\mathbb {F}_{q_i}^{*})^n,1\leq i\leq l\}\). Now we construct a subset D of \((\mathbb {F}_{q_1}^{*})^n\times (\mathbb {F}_{q_2}^{*})^n\times \cdots \times (\mathbb {F}_{q_l}^{*})^n\) as follows. Assume that P1 = D1. For any 1 ≤ i ≤ l − 1, we put \(P_{i + 1}=(P_i\times \overline {D}_{i + 1})\cup (\overline {P}_i\times D_{i + 1})\), where \(\overline {P}_i=(\mathbb {F}_{q_1}^{*})^n\times (\mathbb {F}_{q_2}^{*})^n\times \cdots \times (\mathbb {F}_{q_i}^{*})^n\backslash P_i\). In the end, let D = Pl.

Suppose that φi1, φi2,⋯ ,φin are multiplicative characters of \(\mathbb {F}_{q_i}\) and Ui = (φi1, φi2,⋯ ,φin) for any 1 ≤ i ≤ l. For simplicity, denote by Ui(Xi) = φi1(xi1)φi2(xi2)⋯φin(xin). Then we define a vector of length K = #D as

$$\mathbf{c}_{(U_{1},\cdots,U_{l})}=\frac{1}{\sqrt{K}}(U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l}))_{(X_{1},X_{2},\cdots,X_{l})\in D}, $$

and define a set \(\mathcal {C}\) of N = N1N2⋯Nl unit-norm complex vectors by

$$ \mathcal{C}=\{\mathbf{c}_{(U_{1},\cdots,U_{l})}:U_{i}\in(\widehat{\mathbb{F}_{q_{i}}^{*}})^{n},1\leq i\leq l\}. $$
(2)

Obviously, the set \(\mathcal {C}\) is an (N,K) codebook. In order to determine the length K and the maximum cross-correlation amplitude of \(\mathcal {C}\), we need the following two lemmas.

Lemma 5

With the notation as above,\(\#P_i=\frac {N_1N_2\cdots N_i-(-1)^{in}}{2}\)forany 1 ≤ i ≤ l.Furthermore,\(K=\frac {N_1N_2\cdots N_l-(-1)^{ln}}{2}\).

Proof

We prove this lemma by mathematical induction. It follows from Lemma 4 that \(P_1=D_1=\frac {N_1-(-1)^{n}}{2}\). Assume that \(\#P_i=\frac {N_1N_2\cdots N_i-(-1)^{in}}{2}\) for i > 1. Then, by the definition of the set Pi+ 1, we have

$$\begin{array}{@{}rcl@{}} \#P_{i + 1}&=&\#P_{i}\times(N_{i + 1}-\#D_{i + 1})+(N_{1}N_{2}\cdots N_{i}-\#P_{i})\times\#D_{i + 1}\\ &=&\frac{N_{1}N_{2}\cdots N_{i}-(-1)^{in}}{2}\times\frac{N_{i + 1}+(-1)^{n}}{2}\\ &&+\frac{N_{1}N_{2}\cdots N_{i}+(-1)^{in}}{2}\times\frac{N_{i + 1}-(-1)^{n}}{2}\\ &=&\frac{N_{1}N_{2}\cdots N_{i + 1}-(-1)^{(i + 1)n}}{2}. \end{array} $$

Therefore, \(\#P_i=\frac {N_1N_2\cdots N_i-(-1)^{in}}{2}\) for any 1 ≤ i ≤ l and \(K=\#P_l=\frac {N_1N_2\cdots N_l-(-1)^{ln}}{2}\).

Lemma 6

With the notation as above, for any multiplicativecharacters\(U_i\in (\widehat {\mathbb {F}_{q_i}^{*}})^n\),1 ≤ i ≤ l, weget

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|=K, $$

if Ui = (1,1,⋯ ,1) for any 1 ≤ i ≤ l. Otherwise,

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\leq 2^{\frac{s_{1}n+\cdots+s_{l}n-2}{2}}. $$

The equality holds if and only if φi1, φi2,⋯ ,φin are all nontrivial for any 1 ≤ i ≤ l.

Proof

If Ui = (1,1,⋯ ,1) for any 1 ≤ i ≤ l, it is easy to show that

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|=\#D=K. $$

Otherwise, we verify \(\left |\sum _{(X_1,X_2,\cdots ,X_l)\in D}U_1(X_1)U_2(X_2)\cdots U_l(X_l)\right |\leq 2^{\frac {s_1n+\cdots +s_ln-2}{2}}\) by using mathematical induction. According to the proof of Theorem 1, the result is correct for l = 2. If l > 2, assume that

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1}}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\right|\leq 2^{\frac{s_{1}n+\cdots+s_{l-1}n-2}{2}}. $$

We check that

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\leq 2^{\frac{s_{1}n+\cdots+s_{l}n-2}{2}}, $$

and the proof is divided into the following three cases.

  1. (1)

    If Ul = (1,1,⋯ ,1) and there is at least one Ui≠(1,1,⋯ ,1), where 1 ≤ i < l, then we obtain

    $$\begin{array}{@{}rcl@{}} &&\left|\sum_{(X_{1},X_{2},\cdots,X_{l})\in D}\!U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\\ &&\quad=\left|(N_{l}-\#D_{l})\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\right.\\ &&\qquad+\left.\#D_{l}\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in \overline{P_{l-1}} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\right|\\ &&\quad=\left|N_{l}-2\#D_{l}\right|\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1} }\!U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\right|\\ &&\quad\leq2^{\frac{s_{1}n+\cdots+s_{l-1}n-2}{2}}, \end{array} $$

    where the last equality follows from the fact that

    $$\begin{array}{@{}rcl@{}} &&\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\\ &&+\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in \overline{P_{l-1}} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})= 0. \end{array} $$
  2. (2)

    If Ui = (1,1,⋯ ,1) for any 1 ≤ i ≤ l − 1 and Ul≠(1,1,⋯ ,1), it follows from Lemma 2 and Proposition 1 that

    $$\begin{array}{@{}rcl@{}} &&\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\\ &&\quad=\left|\#P_{l-1}\sum\limits_{X_{l}\in \overline{D_{l}}}U_{l}(X_{l})+(N_{1}N_{2}\cdots N_{l-1}-\#P_{l-1})\sum\limits_{X_{l}\in D_{l}}U_{l}(X_{l})\right|\\ &&\quad=\left|N_{1}N_{2}\cdots N_{l-1}-2\#P_{l-1}\right|\left|\sum\limits_{X_{l}\in D_{l}}U_{l}(X_{l})\right|\\ &&\quad\leq 2^{\frac{s_{l}n-2}{2}}. \end{array} $$
  3. (3)

    If Ul≠(1,1,⋯ ,1) and there is at least one Ui≠(1,1,⋯ ,1), where 1 ≤ i < l, then we obtain

    $$\begin{array}{@{}rcl@{}} &&\left|\sum_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\\ &&\quad=\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\sum\limits_{X_{l}\in \overline{D_{l}}}U_{l}(X_{l})\right.\\ &&\qquad+\left.\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in \overline{P_{l-1}} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\sum\limits_{X_{l}\in D_{l}}U_{l}(X_{l})\right|\\ &&\quad= 2\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l-1})\in P_{l-1} }U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l-1}(X_{l-1})\right|\left|\sum\limits_{X_{l}\in D_{l}}U_{l}(X_{l})\right|\\ &&\quad\leq 2^{\frac{s_{1}n+\cdots+s_{l}n-2}{2}}. \end{array} $$

Consequently, we infer that

$$\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}(X_{1})U_{2}(X_{2})\cdots U_{l}(X_{l})\right|\leq 2^{\frac{s_{1}n+\cdots+s_{l}n-2}{2}}.$$

By the method analogous to that used above and Proposition 1, we can show that the equality holds if and only if φi1, φi2,⋯ ,φin are all nontrivial for any 1 ≤ i ≤ l.

Next, we present our second class of codebooks in the following theorem.

Theorem 3

Let the symbols be the same as above andn ≥ 1,l > 1 beintegers. We writeN = N1N2⋯Nland\(K=\frac {N_1N_2\cdots N_l-(-1)^{ln}}{2}\).Then the set\(\mathcal {C}\)definedby (2) is an (N,K) codebookand its maximum cross-correlation amplitudeis\(I_{max}(\mathcal {C})=\frac {2^{(s_1n+s_2n+\cdots +s_ln)/2}}{N_1N_2\cdots N_l-(-1)^{ln}}\).

Proof

From the definition of the set \(\mathcal {C}\) and Lemma 5, it follows that \(\mathcal {C}\) has N1N2⋯Nl vectors and the length of each vector is \(\frac {N_1N_2\cdots N_l-(-1)^{ln}}{2}\). For any two distinct vectors \(\mathbf {c}_{(U_1,\cdots ,U_l)}\) and \(\mathbf {c}_{(V_1,\cdots ,V_l)}\) of \(\mathcal {C}\), where Ui = (φi1, φi2,⋯ ,φin) and Vi = (λi1, λi2,⋯ ,λin) for any 1 ≤ i ≤ l, we get

$$\left|\mathbf{c}_{(U_{1},\cdots,U_{l})}\mathbf{c}_{(V_{1},\cdots,V_{l})}^{H}\right|=\frac{1}{K}\left|\sum\limits_{(X_{1},X_{2},\cdots,X_{l})\in D}U_{1}V_{1}^{-1}(X_{1})U_{2}V_{2}^{-1}(X_{2})\cdots U_{l}V_{l}^{-1}(X_{l})\right|, $$

where \(U_iV_i^{-1}(X_i)=\varphi _{i1}\lambda _{i1}^{-1}(x_{i1})\varphi _{i2}\lambda _{i2}^{-1}(x_{i2})\cdots \varphi _{in}\lambda _{in}^{-1}(x_{in})\). Due to (U1,⋯ ,Ul)≠(V1,⋯ ,Vl), it follows from Lemma 6 that

$$\left|\mathbf{c}_{(U_{1},\cdots,U_{l})}\mathbf{c}_{(V_{1},\cdots,V_{l})}^{H}\right|\leq\frac{ 2^{\frac{s_{1}n+\cdots+s_{l}n-2}{2}}}{K}=\frac{2^{(s_{1}n+s_{2}n+\cdots+s_{l}n)/2}}{N_{1}N_{2}\cdots N_{l}-(-1)^{ln}}. $$

The equality holds if and only if \(\varphi _{i1}\lambda _{i1}^{-1},\varphi _{i2}\lambda _{i2}^{-1},\cdots ,\varphi _{in}\lambda _{in}^{-1}\) are all nontrivial for any 1 ≤ i ≤ l.

Theorem 4

Let the symbols be the same as those in Theorem 3. Then thecodebook\(\mathcal {C}\)definedby (2) is asymptotically optimal with respect to the Welch bound.

Proof

Observe that \(\mathcal {C}\) is an \(\left (N=N_1N_2\cdots N_l,K=\frac {N_1N_2\cdots N_l-(-1)^{ln}}{2}\right )\) codebook. The corresponding Welch bound of \(\mathcal {C}\) is

$$I_{W}=\sqrt{\frac{K+(-1)^{ln}}{2K^{2}+((-1)^{ln}-1)K}}. $$

Due to \(I_{max}(\mathcal {C})=\frac {2^{(s_1n+s_2n+\cdots +s_ln)/2}}{N_1N_2\cdots N_l-(-1)^{ln}}\), it follows that

$$\frac{I_{max}(\mathcal{C})}{I_{W}}=\sqrt{\frac{2^{s_{1}n+\cdots s_{l}n\left( 1+\frac{(-1)^{ln}-1}{(2^{s_{1}}-1)^{n}\cdots (2^{s_{l}}-1)^{n}}\right)}}{(2^{s_{1}}-1)^{n}\cdots (2^{s_{l}}-1)^{n}+(-1)^{ln}}}\rightarrow 1, $$

if \(s_i\rightarrow 1\) for any 1 ≤ i ≤ l.

Remark 2

Let l > 1 be an integer and Qi ≡ 3 mod 4, where 1 ≤ i ≤ l. The codebooks generated by [11, Theorem 2] has parameters \(N=Q_1Q_2\cdots Q_l,K=\frac {Q_1Q_2\cdots Q_l-1}{2}\) and the maximum cross-correlation amplitude \(I_{max}=\frac {\sqrt {(Q_1 + 1)(Q_2 + 1)\cdots (Q_l + 1)}}{Q_1Q_2\cdots Q_l-1}\). If n = 1, then the codebooks in Theorem 3 has the same parameters as the codebooks constructed by [11, Theorem 2]. For any n > 1 such that n is odd, the codebooks produced by Theorem 3 has the same parameters N,K as the codebooks proposed by [11, Theorem 2]. While the maximum cross-correlation amplitude of our construction is greater than the maximum cross-correlation amplitude of codebooks generated by [11, Theorem 2]. If n > 1 is even, the codebooks produced by Theorem 3 has the new parameters due to \((2^{s_i}-1)^n \equiv 1\ \text {mod}\ 4\) for any 1 ≤ i ≤ l. In Table 3, we provide some explicit examples of the codebook \(\mathcal {C}\) in Theorem 3 for n = 2, l = 3 and some given s = s1 = s2 = s3. It is indicated that the codebook \(\mathcal {C}\) produced by Theorem 3 is asymptotically optimal with respect to the Welch bound.

Table 3 Parameters of the (N,K) codebook of Theorem 3 for n = 2, l = 3 and some given s = s1 = s2 = s3
Full size table

5 Concluding remarks

In this paper, we investigated the operation of certain sets and its recursive construction. Based on the operations of sets, we proposed two constructions of codebooks and determined the maximum cross-correlation amplitude of codebooks generated by these two constructions. We verified that the codebooks generated by these two constructions are asymptotically optimal with respect to the Welch bound. Although our constructions are very similar to the constructions proposed in [11], the codebooks generated by our constructions have new parameters in some cases.

The technique of compression while sampling, usually referred to as Compressed Sensing, has been the center of attention for a decade. In Compressed Sensing, an (N,K) codebook can be viewed as a K × N compressed sensing matrix. As an application, we can employ our codebooks to construct compressed sensing matrices with low coherence.