Abstract
Codebooks with low-coherence have wide applications in many fields such as direct spread code division multiple access communications, compressed sensing, signal processing and so on. In this paper, we propose two constructions of complex codebooks from the operations of certain sets. The complex codebooks produced by these constructions are proved to be asymptotically optimal with respect to the Welch bound. In addition, the parameters of the complex codebooks presented in this paper are new and flexible in some cases.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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,
Moreover, the equality holds if and only if for all pairs of (i, j) with i≠j, it holds that
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 − 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
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.
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
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
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:
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
and
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
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
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
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
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
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
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:
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
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)
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)
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)
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
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
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,
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.
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
and define a set \(\mathcal {C}\) of N = N1N2⋯Nl unit-norm complex vectors by
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
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
if Ui = (1,1,⋯ ,1) for any 1 ≤ i ≤ l. Otherwise,
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
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
We check that
and the proof is divided into the following three cases.
-
(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)
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)
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
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
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
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
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
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.
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.
References
Candes, E., Wakin, M.: An introduction to compressive sampling. IEEE Signal Process. 25(2), 21–30 (2008)
Conway, J., Harding, R., Sloane, N.: Packing lines, planes, etc.: Packings in Grassmannian spaces. Exp. Math. 5(2), 139–159 (1996)
Cao, X., Chou, W., Zhang, X.: More constructions of near optimal codebooks associated with binary sequences. Adv. Math. Commun. 11(1), 187–202 (2017)
Ding, C.: Complex codebooks from combinatorial designs. IEEE Trans. Inform. Theory 52(9), 4229–4235 (2006)
Ding, C., Feng, T.: A generic construction of complex codebooks meeting the Welch bound. IEEE Trans. Inform. Theory 53(11), 4245–4250 (2007)
Delsarte, P., Goethals, J., Seidel, J.: Spherical codes and designs. Geometriae Dedicate. 67(3), 363–388 (1997)
Fickus, M., Mixon, D., Tremain, J.: Steiner equiangular tight frames. Linear Algebra Appl. 436(5), 1014–1027 (2012)
Fickus, M., Mixon, D.: Tables of the existence of equiangular tight frames. arXiv:1504.00253v2 (2016)
Fickus, M., Mixon, D., Jasper, J.: Equiangular tight frames from hyperovals. IEEE Trans. Inf. Theory 62(9), 5225–5236 (2016)
Fickus, M., Jasper, J, Mixon, D., Peterson, J.: Tremain equiangular tight frames. arXiv:1602.03490v1 (2016)
Hu, H., Wu, J.: New constructions of codebooks nearly meeting the Welch bound with equality. IEEE Trans. Inf. Theory 60(2), 1348–1355 (2014)
Hong, S., Park, H., Helleseth, T., Kim, Y.: Near optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping. IEEE Trans. Inf. Theory 60(6), 3698–3705 (2014)
Heng, Z., Ding, C., Yue, Q.: New constructions of asymptotically optimal codebooks with multiplicative characters. IEEE Trans. Inf. Theory 63(10), 6179–6187 (2017)
Heng, Z.: Nearly optimal codebooks based on generalized Jacobi sums. Dis. Appli. Math. https://doi.org/10.1016/j.dam.2018.05.017 (2018)
Li, C., Yue, Q., Huang, Y.: Two families of nearly optimal codebooks. Des. Codes Cryptogr. 75(1), 43–57 (2015)
Love, D., Heath, R., Strohmer, T.: Grassmannian beamforming for multiple-input multiple-output wireless systems. IEEE Trans. Inf. Theory 49(10), 2735–2747 (2003)
Luo, G., Cao, X.: Two constructions of asymptotically optimal codebooks via the hyper Eisenstein sum. IEEE Trans. Inf. Theory. https://doi.org/10.1109/TIT.2017.2777492 (2017)
Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Mukkavilli, K., Sabharwal, A., Erkip, E., Aazhang, B.: On beamforming with finite rate feedback in multiple antenna systems. IEEE Trans. Inf. Theory 49(10), 2562–2579 (2003)
Massey, J., Mittelholzer, T.: Welch Bound and Sequence Sets for Code-Division Multiple-Access Systems. Sequences II, pp 63–78. Springer, New York (1999)
Rahimi, F.: Covering graphs and equiangular tight frames. Ph.D. Thesis, University of Waterloo, Ontario. (available at http://hdl.handle.net/10012/10793) (2016)
Renes, J., Blume-Kohout, R., Scot, A., Caves, C.: Symmetric informationally complete quantum measurements. J. Math. Phys. 45(6), 2171–2180 (2004)
Sarwate, D.: Meeting the Welch Bound with Equality. Sequences and their Applications, pp 79–102. Springer, London (1999)
Strohmer, T., Heath, R.: Grassmannian frames with applications to coding and communication. Appl. Comput. Harmonic Anal. 14, 257–275 (2003)
Tsiligianni, E., Kondi, L., Katsaggelos, A.: Construction of incoherent unit norm tight frameswith application to compressed sensing. IEEE Trans. Inform. Theory 60(4), 2319–2330 (2014)
Tan, P., Zhou, Z., Zhang, D.: A construction of codebooks nearly achieving the Levenshtein bound. IEEE Signal Process. Lett. 23(10), 1306–1309 (2016)
Welch, L.: Lower bounds on the maximum cross correlation of signals. IEEE Trans. Inform. Theory 20(3), 397–399 (1974)
Xia, P., Zhou, S., Giannakis, G.: Achieving the Welch bound with difference sets. IEEE Trans. Inform. Theory 51(5), 1900–1907 (2005)
Yu, N.: A construction of codebooks associated with binary sequences. IEEE Trans. Inf. Theory 58(8), 5522–5533 (2012)
Zhang, A., Feng, K.: Two classes of codebooks nearly meeting the Welch bound. IEEE Trans. Inf. Theory 58(4), 2507–2511 (2012)
Zhang, A., Feng, K.: Construction of cyclotomic codebooks nearly meeting the Welch bound. Des. Codes Cryptogr. 63(2), 209–224 (2013)
Zhou, Z., Tang, X.: New nearly optimal codebooks from relative difference sets. Adv. Math. Commun. 5(3), 521–527 (2011)
Acknowledgments
We are grateful to the anonymous referees and the editor for useful comments and suggestions that improved the presentation and quality of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the National Natural Science Foundations of China (Grant Nos. 11771007 and 61572027)
Rights and permissions
About this article
Cite this article
Luo, G., Cao, X. Two constructions of asymptotically optimal codebooks. Cryptogr. Commun. 11, 825–838 (2019). https://doi.org/10.1007/s12095-018-0331-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-018-0331-4