Two constructions of asymptotically optimal codebooks via the trace functions

Abstract

In this paper, we present two new constructions of complex codebooks with multiplicative characters, additive characters and trace functions over finite fields, and determin the maximal cross-correlation amplitude of these codebooks. We prove that the codebooks we constructed are asymptotically optimal with respect to the Welch bound. Moreover, in the first construction, we generalize the result in Zhang and Feng (IEEE Trans. Inform. Theory 58(4), 2507–2511, 2012). In the second construction, we generalize the results in Hong et al. (IEEE Trans. Inf. Theory 60(6), 3698–3705, 2014), we can asymptotically achieve Welch bound for any odd prime p, we also derive the whole distribution of their inner products. The parameters of these codebooks are new.

1 Introduction

An (N,K) codebook ${\mathcal C}=\{\mathbf {c}_{0},\mathbf {c}_{1}, ...,\mathbf {c}_{N-1}\}$ is a set of N unit-norm complex vectors $\mathbf {c}_{i} \in \mathbb {C}^{K}$ over an alphabet A, where i = 0,1,…,N − 1. The size of A is called the alphabet size of ${\mathcal C}$. As a performance measure of a codebook in practical applications, the maximum magnitude of inner products between a pair of distinct vectors in ${\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}$ denotes the conjugate transpose of the complex vector c_j. To evaluate an (N,K) codebook ${\mathcal C}$, it is important to find the minimun achievable $I_{max}({\mathcal C})$ or its lower bound. The Welch bound [27] provides a well-known lower bound on $I_{max}({\mathcal C})$,

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

The equality holds if and only if for all pairs of (i,j) with i≠j

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

A codebook ${\mathcal C}$ achieving the Welch bound equality is called a maximum-Welch-bound-equality (MWBE) codebook [25] or an equiangular tight frame [15]. MWBE codebooks are employed in various applications including code-division multiple-access(CDMA) communication systems [22], communications [25], combinatorial designs [3, 4, 28], packing [2], compressed sensing [1], coding theory [5] and quantum computing [23]. To our knowledge, only the following MWBE codebooks are presented as follows:

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

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

• (N,K) MWBE codebooks from conference matrices [2, 26], where N = 2K = 2^d+ 1 for a positive integer d or N = 2K = p^d + 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 [3, 4];

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

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

The construction of an MWBE codebook is known to be very hard in general, and the known classes of MWBE codebooks only exist for very restrictive N and K. Many researches have been done instead to construct asymptotically optimal codebooks, i.e., codebook ${\mathcal C}$ whose $I_{max}({\mathcal C})$ asymptotically achieves the Welch bound. In [25], Sarwate gave some asymptotically optimal codebooks from codes and signal sets. As an extension of the optimal codebooks based on difference sets, various types of asymptotically optimal codebooks based on almost difference sets, relative difference sets and cyclotomic classes were proposed, see [3, 11, 30,31,32]. Asymptotically optimal codebooks constructed from binary row selection sequences were presented in [12, 29]. In [13, 14, 17,18,19,20], some asymptotically optimal codebooks were constructed via Jacobi sums and hyper Eisenstein sum.

In this paper, we present two new constructions of complex codebooks with multiplicative characters, additive characters and trace functions over finite fields, and determine the maximal cross-correlation amplitude of these codebooks. The key ideas in our new constructions are based on transitivity of trace and the Fourier expansion of characters. We prove that the codebooks we constructed are asymptotically optimal with respect to the Welch bound. Moreover, in the second construction, we also derive the whole distribution of their inner products. As a comparison, in Table 1, we list the parameters of some known classes of asymptotically optimal codebooks and those of the new ones.

Table 1 The parameters of codebooks asymptotically meeting the Welch bound

This paper is organized as follows. In Section 2, we recall some notations and basic results which will be needed in our discussion. In Section 3, we present our first construction of codebooks. In Section 4, we present our second construction of codebooks. In Section 5, we conclude this paper.

2 Preliminaries

In this section, we introduce some basic results on trace functions, characters and character sums over finite fields, which will be needed in the following sections.

2.1 Trace functions of finite fields

Let ${\mathbb F}_{p}$, ${\mathbb F}_{r}$ and ${\mathbb F}_{q}$ be finite fields, with ${\mathbb F}_{p}\subseteq {\mathbb F}_{r}\subseteq {\mathbb F}_{q}$. Let Tr_q/r(⋅) be the trace functions from ${\mathbb F}_{q}$ to ${\mathbb F}_{r}$. with

$${\operatorname{Tr}}_{q/r}(x)=x+x^{r}+x^{r^{2}}+...+x^{\frac{q}{r}},\ x\in {\mathbb F}_{q}.$$

Transitivity of trace in [21] is stated as

$${{\operatorname{Tr}}_{r/p}({\operatorname{Tr}}_{q/r}(x))={\operatorname{Tr}}_{q/p}(x)},\ x\in {\mathbb F}_{q},$$

it plays an important role in our constructions.

2.2 Characters over finite fields

Let ${\mathbb F}_{q}$ be a finite field. In this subsection, we recall the definitions of the additive and multiplicative characters of ${\mathbb F}_{q}$.

For each $a\in \mathbb {F}_{q}$, an additive character of $\mathbb {F}_{q}$ is defined by the function $\chi _{a}(x)=\zeta _{p}^{{\operatorname {Tr}}_{q/p}(ax)}$, where ζ_p is a primitive p-th root of complex unity. By the definition, χ_a(x) = χ₁(ax). If a = 0, we call χ₀ the trivial additive character of $\mathbb {F}_{q}$. Let $\widehat {{\mathbb F}_{q}}$ be the set of all additive characters of ${\mathbb F}_{q}$. The orthogonal relation of additive characters (see [21]) is given by

$$ \underset{x\in \mathbb{F}_{q}}{\sum}\chi_{a}(x)=\left\{ \begin{array}{ll} q,& \text{if} a=0,\\ 0,& \text{otherwise.} \end{array} \right. $$

As in [21], the multiplicative character of $\mathbb {F}_{q}$ is defined as follows. For j = 0,1,...,q − 2, the functions φ_j defined by

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

are all the multiplicative characters of $\mathbb {F}_{q}$, where α is a primitive element of $\mathbb {F}_{q}^{*}$, and 0 ≤ i ≤ q − 2. If j = 0, we have φ₀(x) = 1 for any $x\in \mathbb {F}_{q}^{*}$, φ₀ is called the trivial multiplicative character of $\mathbb {F}_{q}$. Let $\widehat {{\mathbb F}_{q}^{*}}$ be the set of all the multiplicative characters of ${\mathbb F}_{q}^{*}$.

Let φ be a multiplicative character of ${\mathbb F}_{q}$. The orthogonal relation of multiplicative characters (see [21]) is given by

$$ \underset{x\in \mathbb{F}_{q}^{*}}{\sum}\varphi(x)=\left\{ \begin{array}{ll} q-1,& \text{if\ }\varphi=\varphi_{0},\\ 0,& \text{otherwise.} \end{array} \right. $$

2.3 Gauss sums over finite fields

Let φ be a multiplicative character of ${\mathbb F}_{q}$ and χ an additive character of ${\mathbb F}_{q}$. Then the Gauss sum over ${\mathbb F}_{q}$ is given by

$$ {G_{q}(\varphi,\chi)={\sum}_{x\in \mathbb{F}_{q}^{*}}\varphi(x){\chi}(x)}. $$

It is easy to see that the absolute value of G_q(φ,χ) is at most q − 1, but is much smaller in general, the following lemma shows all the cases.

Lemma 2.1

[21, Theorem 5.11] Let φ be a multiplicative character and χ an additive character of ${\mathbb F}_{q}$. Then the Gauss sum G_q(φ,χ) satisfies

$$ G_{q}(\varphi,\chi)=\left\{ \begin{array}{ll} q-1, & \text{if\ }\varphi=\varphi_{0}, \chi=\chi_{0}, \\ -1,& \text{if\ }\varphi=\varphi_{0}, \chi\neq\chi_{0},\\ 0,& \text{if\ }\varphi\neq\varphi_{0}, \chi=\chi_{0}. \end{array} \right. $$

For φ≠φ₀ and χ≠χ₀, we have $\left |G_{q}(\varphi ,\chi )\right |=\sqrt {q}$.

Lemma 2.2

Lidl and Niederreiter [21] Gauss sums for the finite field ${\mathbb F}_{q}$ satisfy the following properties:

(1)$G_{q}(\varphi ,\chi _{ab})=\overline {\varphi (a)}G_{q}(\varphi ,\chi _{b})$ for $a\in {\mathbb F}_{q}^{*}$, $b\in {\mathbb F}_{q}$, where $\overline {\varphi (a)}$ denotes the complex conjugate of φ(a);

(2)$G_{q}(\varphi ,\chi )G_{q}(\overline {\varphi },\chi )=\varphi (-1)q$.

Lemma 2.3

Lidl and Niederreiter [21] Let φ be a multiplicative character of ${\mathbb F}_{q}$. Then for any $c\in {\mathbb F}_{q}^{*}$, we have

$$ \varphi(c)=\frac{1}{q}\underset{\chi}{\sum}G_{q}(\varphi,\overline{\chi})\chi(c), $$

where the sum is extended over all additive characters χ of ${\mathbb F}_{q}$.

This is the Fourier expansion of the multiplicative character φ in terms of the additive characters of ${\mathbb F}_{q},$ with Gaussian sums appearing as Fourier coefficients.

2.4 A general construction of codebooks

Let D be a set and K = #D. Let E be a set of some functions which satisfy

$$f:D\rightarrow S,\ \ \text{where\ S\ is\ the\ unit\ circle {on the complex plane}.}$$

A general construction of codebooks is stated as follows,

$${\mathcal C}(D;E)=\{{\mathbf c}_{f}:=\frac{1}{\sqrt{K}}(f(x))_{x\in D}, f\in E\}.$$

3 The first construction of codebooks

In this section, by multiplicative characters, transitivity of trace and fourier expansion, we construct new series of codebooks which asymptotically meet the Welch bound.

We first recall the construction in [30]. Let

$$ D=\{x\in {\mathbb F}_{q}^{*}: \eta(x+1)=-1\}, $$

where η is the quadratic multiplicative character of ${\mathbb F}_{q}$, η(0) is defined as 0 for convenience. Let K = #D and $E=\widehat {{\mathbb F}_{q}^{*}}$. The codebooks ${\mathcal C}(D;E)=\{{\mathbf c}_{\varphi }=\frac {1}{\sqrt {K}}(\varphi (x))_{x\in D}: \varphi \in E\}$, which were constructed in [30] are asymptotically optimal when $q\rightarrow \infty$.

In this section, we generalize this construction in [30] by trace functions. Let p be an odd prime, r = p^t and q = r^s, where t|s and $p\nmid s$. Let η be the quadratic multiplicative character of ${\mathbb F}_{r}$. Let

$$ D=\{x\in {\mathbb F}_{q}^{*}: \eta({\operatorname{Tr}}_{q/r}(x+1))=-\eta(s)\}, $$

and K = #D. Let $E=\widehat {{\mathbb F}_{q}^{*}}$.

We define a codeword of length K as

$$ {\mathbf c}_{\varphi}=\frac{1}{\sqrt{K}}(\varphi(x))_{x\in D},\ \varphi\in E, $$

and construct the following (N,K) codebook ${\mathcal C}(D;E)$ as:

$$ {\mathcal C}(D;E)=\{{\mathbf c}_{\varphi}=\frac{1}{\sqrt{K}}(\varphi(x))_{x\in D}: \varphi\in E\}. $$

(1)

We set

$$ \delta_{1}(x)=\left\{ \begin{array}{ll} \frac{1-\eta(s)\eta({\operatorname{Tr}}_{q/r}(x+1))}{2},& \text{if} {\operatorname{Tr}}_{q/r}(x+1)\neq 0,\\ 0,& \text{if\ }{\operatorname{Tr}}_{q/r}(x+1)= 0.\end{array} \right. $$

Through the definition of D, we know that

$$ \delta_{1}(x)=\left\{ \begin{array}{ll} 1, & \text{if} x\in D, \\ 0,& \text{otherwise.} \end{array} \right. $$

Theorem 3.1

With the above notations, we have N = q − 1, $K=\frac {q(r-1)}{2r}$ and

$$ I_{max}({\mathcal C}(D;E))\leq\frac{\sqrt{r}}{\sqrt{q}(\sqrt{r}-1)}<1. $$

Proof

By the definition of D and E, it is easy to see that N = q − 1 and $K=\frac {q(r-1)}{2r}$.

For any characters φ_i and φ_j in $\widehat {{\mathbb F}_{q}^{*}}$, where 1 ≤ i≠j ≤ q − 2. Let $\varphi :=\varphi _{i}\overline {\varphi _{j}}$. Since i≠j, φ is nontrival. Then we have

$$ \begin{array}{@{}rcl@{}} K({\mathbf c}_{\varphi_{i}}{\mathbf c}_{\varphi_{j}}^{H}) &=&{\sum}_{x\in D}\varphi_{i}(x)\overline{\varphi_{j}(x)}\\ &=&{\sum}_{x\in D}\varphi(x)\\ &=&{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\delta_{1}(x)\\ &=&\underset{\underset{\atop{\operatorname{Tr}}_{q/r}(x+1)\neq 0}{x\in {\mathbb F}_{q}^{*},}}{\sum}\varphi(x)\frac{1-\eta(s)\eta(Tr_{q/r}(x+1))}{2} \\ &=& {\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\frac{1-\eta(s)\eta(Tr_{q/r}(x+1))}{2}\\ &&-\underset{\underset{\atop{\operatorname{Tr}}_{q/r}(x+1)= 0} {x\in {\mathbb F}_{q}^{*}},}{\sum}\varphi(x)\frac{1-\eta(s)\eta(Tr_{q/r}(x+1))}{2}\\ &=&{-\frac{1}{2}\eta(s)\underset{x\in {\mathbb F}_{q}^{*}}{\sum}\varphi(x)\eta(Tr_{q/r}(x+1))}-\frac{1}{2}\underset{\underset{\atop{\operatorname{Tr}}_{q/r}(x+1)= 0}{x\in {\mathbb F}_{q}^{*},}}{\sum}\varphi(x)\\ &=&-\frac{1}{2}\eta(s)A-\frac{1}{2}B, \end{array} $$

where A and B are defined in Lemmas 3.4 and 3.5.

By the results in Lemmas 3.4 and Lemma 3.5, we get

$$ \begin{array}{@{}rcl@{}} I_{max}({\mathcal C}(D;E)) &=& \max\{|{\mathbf c}_{\varphi_{i}}{\mathbf c}_{\varphi_{j}}^{H}|:1\leq i \neq j\leq q-2\}\\ &\leq&\frac{|A|+|B|}{2K}\leq \frac{\sqrt{r}}{\sqrt{q}(\sqrt{r}-1)}<1. \end{array} $$

□

Using Theorem 3.1, we will show the asymptotical-optimality of the proposed codebooks in the following theorem. For simiplicity, we set $I_{max}=I_{max}{\mathcal C}(D;E)$.

Theorem 3.2

Let I_W be the magnitude of the optimal correlation, i.e. the Welch bound equality, for the given N, K in the current section. We hav

$$\underset{r\rightarrow\infty}{\lim}\frac{I_{W}}{\frac{1}{\sqrt{2K}}}=\underset{r\rightarrow\infty}{\lim}\frac{I_{max}}{\frac{1}{\sqrt{2K}}}=1,$$

and

$$ 0\leq \underset{r\rightarrow\infty}{\lim}\frac{I_{max}-I_{W}}{\frac{1}{\sqrt{2Kr}}}\leq 1.$$

Then the codebooks we proposed are asymptotically optimal.

Proof

Note that N = q − 1 and $K=\frac {q(r-1)}{2r}$, we get

$$\frac{I_{W}}{\frac{1}{\sqrt{2K}}}=\sqrt{\frac{N-K}{(N-1)K}}\cdot \sqrt{2K}=\sqrt{1+\frac{q}{r(q-2)}}=1+\frac{q}{2r(q-2)}+o\left( \frac{1}{r}\right),$$

thus

$$\lim_{r\rightarrow\infty}\frac{I_{W}}{\frac{1}{\sqrt{2K}}}=1.$$

By Theorem 3.1, we get

$$ \begin{array}{@{}rcl@{}} \frac{I_{max}}{\frac{1}{\sqrt{2K}}}&\leq& \frac{\sqrt{r}}{\sqrt{q}(\sqrt{r}-1)}\cdot \sqrt{2K}=\sqrt{1-\frac{1}{r}}\cdot \frac{1}{1-\frac{1}{\sqrt{r}}}\\&=&\left( 1-\frac{1}{2r}+o\left( \frac{1}{r}\right)\right)\left( 1+\frac{1}{\sqrt{r}}+\frac{1}{r}+o\left( \frac{1}{r}\right)\right) =1+\frac{1}{\sqrt{r}}+\frac{1}{2r}+o\left( \frac{1}{r}\right). \end{array} $$

We get

$$\frac{I_{max}-I_{W}}{\frac{1}{\sqrt{2K}}}\leq \frac{1}{\sqrt{r}}-\frac{1}{r(q-2)}+o(\frac{1}{r}),$$

thus

$$0\leq \underset{r\rightarrow\infty}{\lim}\frac{I_{max}-I_{W}}{\frac{1}{\sqrt{2Kr}}}\leq 1.$$

It is easy to see

$$\underset{r\rightarrow\infty}{\lim}\frac{I_{max}}{\frac{1}{\sqrt{2K}}}=\underset{r\rightarrow\infty}{\lim}\frac{I_{W}}{\frac{1}{\sqrt{2K}}} +\underset{r\rightarrow\infty}{\lim}\frac{I_{max}-I_{W}}{\frac{1}{\sqrt{2K}}} =1+0=1.$$

Thus the codebooks ${\mathcal C}(D;E)$ asymptotically meet the Welch bound. This completes the proof. □

Remark 1

When r = q, it is exactly the first construction of codebooks in [30].

Let φ be a multiplicative character of ${\mathbb F}_{q}$ and φ^∗ the restriction of φ to ${{\mathbb F}}_{r}$. Let χ_a be an additive character of ${\mathbb F}_{q}$, and $\chi _{a}^{*}$ the restriction of χ_a to ${{\mathbb F}}_{r}$, where $a\in {\mathbb F}_{q}$. Let ψ_b be an additive character of ${\mathbb F}_{r}$, where $b\in {\mathbb F}_{r}$. Let χ = χ₁ and ψ = ψ₁ be the canonical additive characters of ${\mathbb F}_{q}$ and ${\mathbb F}_{r}$ respectively. The Lemmas which are used in the proof of Theorem 3.1 are as follows.

Lemma 3.3

χ^∗ is nontrivial if and only if $p\nmid s$.

Proof

For any $b\in {\mathbb F}_{r}$, we have

$$ \begin{array}{@{}rcl@{}} \chi^{*}(b)&=&\chi(b)=\zeta_{p}^{{\operatorname{Tr}}_{q/p}(b)}=\zeta_{p}^{{\operatorname{Tr}}_{r/p}({\operatorname{Tr}}_{q/r}(b))}=\zeta_{p}^{{\operatorname{Tr}}_{r/p}(b){\operatorname{Tr}}_{q/r}(1)}\\ &=&\zeta_{p}^{{\operatorname{Tr}}_{r/p}(bs)}=\psi(bs)=\psi_{s}(b). \end{array} $$

It follows that χ^∗ = ψ_s, the result is obtained. □

Lemma 3.4

Let $A={\sum }_{x\in {\mathbb F}_{q}^{*}}\varphi (x)\eta (Tr_{q/r}(x+1))$. Then we have

$$ |A|=\left\{ \begin{array}{ll} \sqrt{q},& \text{if} \eta\overline{\varphi}^{*} is nontrivial,\\ \frac{\sqrt{q}}{\sqrt{r}},& \text{if} \eta\overline{\varphi}^{*} is trivial. \end{array} \right. $$

Proof

By the Fourier expansion in Lemma 2.3, A can be rewritten as

$$ \begin{array}{@{}rcl@{}} A&=&{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}})\psi_{b}({\operatorname{Tr}}_{q/r}(x+1))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\psi({\operatorname{Tr}}_{q/r}(bx+b))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\chi(bx+b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\chi(bx)\chi(b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}})G_{q}(\varphi,\chi_{b})\chi(b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}\overline{\eta(-b)}G_{r}(\eta,{\psi})\overline{\varphi(b)} G_{q}(\varphi,\chi)\chi(b)\\ &=&\frac{1}{r}\eta(-1)G_{r}(\eta,{\psi})G_{q}(\varphi,\chi){\sum}_{b\in {\mathbb F}_{r}^{*}}\eta(b)\overline{\varphi(b)}\chi(b)\\ &=&\frac{1}{r}\eta(-1)G_{r}(\eta,{\psi})G_{q}(\varphi,\chi)G_{r}(\eta\overline{\varphi}^{*},\chi^{*}).\\ \end{array} $$

Since $p\nmid s$, the result follows from Lemmas 2.1 and 3.3. □

We set

$$ \delta_{2}(x)=\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}\psi_{b}({\operatorname{Tr}}_{q/r}(x+1)) $$

It is easy to see that

$$\delta_{2}(x)= \left\{ \begin{array}{ll} 1,& \text{if\ }{\operatorname{Tr}}_{q/r}(x+1)= 0,\\ 0,& \text{if\ }{\operatorname{Tr}}_{q/r}(x+1)\neq 0. \end{array} \right.$$

Lemma 3.5

Let $B={\sum }_{x\in {\mathbb F}_{q}^{*},\atop {\operatorname {Tr}}_{q/r}(x+1)= 0}\varphi (x)$. Then we have

$$ |B|=\left\{ \begin{array}{ll} \frac{\sqrt{q}}{\sqrt{r}},& \text{if} \overline{\varphi}^{*} is nontrivial,\\ \frac{\sqrt{q}}{r},& \text{if} \overline{\varphi}^{*} is trivial. \end{array} \right. $$

Proof

By the definition of δ₂(x), we have

$$ \begin{array}{@{}rcl@{}} B&=&\underset{\underset{\atop{\operatorname{Tr}}_{q/r}(x+1)= 0}{x\in {\mathbb F}_{q}^{*},}}{\sum}\varphi(x)={\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\delta_{2}(x)\\ &=&{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}\psi_{b}({\operatorname{Tr}}_{q/r}(x+1))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\psi({\operatorname{Tr}}_{q/r}(bx+b))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\chi(bx+b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}{\sum}_{x\in {\mathbb F}_{q}^{*}}\varphi(x)\chi(bx)\chi(b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{q}(\varphi,\chi_{b})\chi(b)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}\overline{\varphi(b)}G_{q}(\varphi,\chi)\chi(b)\\ &=&\frac{1}{r}G_{q}(\varphi,\chi)G_{r}(\overline{\varphi}^{*},\chi^{*}).\\ \end{array} $$

Since $p\nmid s$, the result follows from Lemmas 2.1 and 3.3. □

4 The second construction of codebooks

In this section, by additive characters, transitivity of trace and fourier expansion, we construct new series of codebooks which asymptotically meet the Welch bound.

In fact, we generalize the construction of codebooks in [12] and show that I_max of the proposed codebooks asymptotically achieves the Welch bound. We also derive the whole distribution of inner products of the proposed codebooks. In [12] the Welch bound can be asymptotically achieved only for sufficiently large prime p, while in our construction the Welch bound can be asymptotically achieved for any odd prime p.

We first recall the construction in [12]. Let p be an odd prime and q a power of p. Let η be the quadratic multiplicative character of ${\mathbb F}_{p}$. The construction in [12] is equivalent to the following one. Let

$$ D=\{x\in {\mathbb F}_{q^{2}}: \eta({\operatorname{Tr}}_{q/p}(x^{T}))=-1\}, $$

and K = #D, where T = q + 1. Let $E=\widehat {{\mathbb F}_{q^{2}}}$.

The codebooks

$$C(D;E)=\{{\mathbf c}_{a}=\frac{1}{\sqrt{K}}(\chi_{a}(x))_{x\in D}: \chi_{a}\in E\},$$

are asymptotically optimal when $p\rightarrow \infty$.

In this Section we generalize the construction in [12]. Let p be an odd prime, r = p^t and q = r^s, where t|s. Let η be the quadratic multiplicative character of ${\mathbb F}_{r}$. Let χ_a be an additive character of ${\mathbb F}_{q^{2}}$, where $a\in {\mathbb F}_{q^{2}}$. Let χ = χ₁ be the canonical additive characters of ${\mathbb F}_{q^{2}}$.

Let

$$ D=\{x\in {\mathbb F}_{q^{2}}: \eta({\operatorname{Tr}}_{q/r}(x^{T}))=-1\}, $$

and K = #D, where T = q + 1. Let $E=\widehat {{\mathbb F}_{q^{2}}}=\{\chi _{a}: a\in {\mathbb F}_{q^{2}}\}$.

We define a codeword of length K as

$$ {\mathbf c}_{a}=\frac{1}{\sqrt{K}}(\chi_{a}(x))_{x\in D}, $$

and construct the following (N,K) codebook as:

$$ {\mathcal C}(D;E)=\{{\mathbf c}_{a}: a\in {\mathbb F}_{q^{2}}\}. $$

(2)

By the definition of D and E, it is easy to see that N = q² and $K=\frac {q(q+1)(r-1)}{2r}$.

The following theorem gives the whole distribution of inner products of ${\mathcal C}(D;E)$.

Theorem 4.1

Let ${\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H}$ be the inner product between a pair of code vectors ${\mathbf c}_{a_{i}}$ and ${\mathbf c}_{a_{j}}$ of the proposed codebooks ${\mathcal C}(D;E)$, where a_i and a_j are distinct elements in ${\mathbb F}_{q^{2}}$, 0 ≤ i≠j ≤ q² − 1. Then ${\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H}$ has the following distribution

$$ {\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H}=\left\{ \begin{array}{ll} \frac{1}{K}\frac{r-1}{2r}q, & \frac{r+1}{2r}(q^{4})-\frac{r-1}{2r}(q^{3})-q^{2}\ times,\\ \frac{1}{K}\frac{-r-1}{2r}q, &\frac{r-1}{2r}(q^{4}+q^{3}) times. \end{array} \right. $$

Proof

We set

$$ \delta_{3}(x)=\left\{ \begin{array}{ll} \frac{1-\eta({\operatorname{Tr}}_{q/r}(x^{T}))}{2},& \text{if\ }{\operatorname{Tr}}_{q/r}(x^{T})\neq 0,\\ 0,& \text{if\ }{\operatorname{Tr}}_{q/r}(x^{T})= 0. \end{array} \right. $$

By the definition of D, we known that

$$ \delta_{3}(x)=\left\{ \begin{array}{ll} 1, & \text{if\ }x\in D, \\ 0,& \text{otherwise.} \end{array} \right. $$

As the notations defined in this section, we have

$$ \begin{array}{@{}rcl@{}} K({\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H})&=&\underset{x\in D}{\sum}\chi_{a_{i}}(x)\overline{\chi_{a_{j}}}(x)\\ &=&\underset{x\in D}{\sum}\chi((a_{i}-a_{j})x)\\ &=&\underset{x\in D}{\sum}\chi(ax), \ (a:=a_{i}-a_{j}\neq 0)\\ &=&\underset{x\in {\mathbb F}_{q^{2}}}{\sum}\chi(ax)\delta_{3}(x)\\ &=&\underset{\underset{\atop {\operatorname{Tr}}_{q/r}x^{T}\neq 0}{x\in {\mathbb F}_{q^{2}}}}{\sum}\chi(ax)\frac{1-\eta({\operatorname{Tr}}_{q/r}(x^{T}))}{2}\\ &=&{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\frac{1-\eta({\operatorname{Tr}}_{q/r}(x^{T}))}{2}\\ &&-\underset{\underset{\atop{\operatorname{Tr}}_{q/r}x^{T}= 0}{x\in {\mathbb F}_{q^{2}}}}{\sum}\chi(ax)\frac{1-\eta({\operatorname{Tr}}_{q/r}(x^{T}))}{2}\\ &=&-\frac{1}{2}{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\eta({\operatorname{Tr}}_{q/r}(x^{T}))\\ &&-\frac{1}{2}\underset{\underset{\atop{\operatorname{Tr}}_{q/r}(x^{T})= 0}{x\in {\mathbb F}_{q^{2}}}}{\sum}\chi(ax)\\ &=&-\frac{1}{2}Q-\frac{1}{2}P, \end{array} $$

where Q and P are defined in Lemmas 4.5 and 4.6.

By the results in Lemmas 4.5 and 4.6, we have

$$ K({\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H})=\left\{ \begin{array}{ll} \frac{r-1}{2r}q, & \text{if\ }{\operatorname{Tr}}_{q/r}(a^{T})=0, \\ \frac{r-1}{2r}q, & \text{if\ }{\operatorname{Tr}}_{q/r}(a^{T})=1,\\ \frac{-r-1}{2r}q, & \text{if\ }{\operatorname{Tr}}_{q/r}(a^{T})=-1. \end{array} \right. $$

To find the distribution, we need the following illustrations. (1) For any $a\in {\mathbb F}_{q^{2}}^{*}$, there are N groups (a_i,a_j) satisfying a_i − a_j = a. (2) For any $z\in {\mathbb F}_{q}^{*}$, there are T different $a\in {\mathbb F}_{q^{2}}^{*}$ which satisfy z = a^T. (3) There are $\frac {q}{r}-1$ different $z\in {\mathbb F}_{q}^{*}$ with Tr_q/r(z) = 0, and there are $\frac {q}{r}$ different $z\in {\mathbb F}_{q}^{*}$ with Tr_q/r(z)≠ 0. (4) The numbers of squares and nonsquares in ${\mathbb F}_{r}^{*}$ are both $\frac {r-1}{2}$.

Then it is easy to get the distribution of ${\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H}$ as follows:

$$ {\mathbf c}_{a_{i}}{\mathbf c}_{a_{j}}^{H}=\left\{ \begin{array}{ll} \frac{1}{K}\frac{r-1}{2r}q, & \frac{r+1}{2r}(q^{4})-\frac{r-1}{2r}(q^{3})-q^{2}\ times,\\ \frac{1}{K}{\frac{-r-1}{2r}q}, &\frac{r-1}{2r}(q^{4}+q^{3})\ times. \end{array} \right. $$

This completes the proof. □

The following corollary which is a direct consequence of Theorem 4.1 gives the value of $I_{max}{{\mathcal C}(D;E)}$.

Corollary 4.2

The maximum magnitude of inner products between a pair of code vectors of the proposed codebooks is

$$I_{max}{{\mathcal C}(D;E)}=\underset{0\leq i\neq j \leq q^{2}-1}{\max}|\mathbf{c}_{a_{i}}\mathbf{c}_{a_{j}}^{H}|{=}\frac{1}{K}\frac{r+1}{2r}q.$$

Using Corollary 4.2, we will show the asymptotical-optimality of the proposed codebooks in the following theorem. For simiplicity, we set $I_{max}=I_{max}{\mathcal C}(D;E)$.

Theorem 4.3

Let I_W be the magnitude of the optimal correlation, i.e. the Welch bound equality, for the given N, K in the current section. We hav

$$\lim_{r\rightarrow\infty}\frac{I_{W}}{\frac{1}{\sqrt{2K}}}=\lim_{r\rightarrow\infty}\frac{I_{max}}{\frac{1}{\sqrt{2K}}}=1,$$

and

$$ \lim_{r\rightarrow\infty}\frac{I_{max}-I_{W}}{\sqrt{2K}r}=1.$$

Then the codebooks we proposed are asymptotically optimal.

Proof

Note that N = q² and $K=q(q+1)\frac {r-1}{2r}$, we get

$$\frac{I_{W}}{\sqrt{\frac{q}{q+1}}\cdot \frac{1}{\sqrt{2K}}} = \sqrt{\frac{N - K}{(N - 1)K}}\cdot\sqrt{\frac{q+1}{q}}\cdot \sqrt{2K} = \sqrt{1+\frac{q+1}{r(q-1)}} = 1+\frac{q + 1}{2r(q - 1)}+o\left( \frac{1}{r}\right),$$

thus

$$\lim_{r\rightarrow\infty}\frac{I_{W}}{\frac{1}{\sqrt{2K}}}=\lim_{r\rightarrow\infty}\frac{I_{W}}{\sqrt{\frac{q}{q+1}}\cdot \frac{1}{\sqrt{2K}}}=1.$$

By Corollary 4.2, we get

$$ \begin{array}{@{}rcl@{}} \frac{I_{max}}{\sqrt{\frac{q}{q+1}}\frac{1}{\sqrt{2K}}}&=& \left( \frac{1}{K}\frac{r+1}{2r}q\right)\cdot\sqrt{\frac{q+1}{q}}\cdot \sqrt{2K}=\left( 1+\frac{1}{r}\right) \left( 1-\frac{1}{r}\right)^{-\frac{1}{2}}\\&=&\left( 1+\frac{1}{r}\right)\left( 1+\frac{1}{2r}+o\left( \frac{1}{r}\right)\right) =1+\frac{3}{2r}+o\left( \frac{1}{r}\right). \end{array} $$

Thus

$$\lim_{r\rightarrow\infty}\frac{I_{max}}{\frac{1}{\sqrt{2K}}}=\lim_{r\rightarrow\infty}\frac{I_{max}}{\sqrt{\frac{q}{q+1}}\cdot \frac{1}{\sqrt{2K}}}=1.$$

We can see

$$\frac{I_{max}-I_{W}}{\sqrt{\frac{q}{q+1}}\cdot \frac{1}{\sqrt{2K}}}=1+\frac{3}{2r}-1-\frac{q+1}{2r(q-1)}+o\left( \frac{1}{r}\right)=\frac{1}{r}\cdot\frac{q-2}{q-1}+o\left( \frac{1}{r}\right),$$

then

$$\lim_{r\rightarrow\infty}\frac{I_{max}-I_{W}}{\frac{1}{\sqrt{2K}r}}=\lim_{r\rightarrow\infty}\frac{I_{max}-I_{W}}{\sqrt{\frac{q}{q+1}}\cdot \frac{1}{\sqrt{2K}r}}=1.$$

The codebooks ${\mathcal C}(D;E)$ asymptotically meet the Welch bound. This completes the proof. □

Remark 2

When r = p, the construction we proposed is exactly the one in [12]. In [12] the codebooks are construced by selecting K rows from N × N Hadamard matrices based on binary row selection sequence, but we use the additive character of finite field and a set D to construct our codebooks. It is pointed out in [12] that I_max of the codebooks asymptotically achieves the Welch bound equality only for sufficiently large prime number p. For small p, I_max of the codebooks has larger value than the Welch bound equality, though $q\rightarrow +\infty$. It is hard to find sufficiently large primes. While, in our construction, for any fixed odd prime p, we can let t increase and then $r=p^{t}\rightarrow +\infty$. So $I_{max}{\mathcal C}(D;E)$ can asymptotically achieve the Welch bound equality.

The Lemmas which are used in the proof of Theorem 4.1 are as follows.

Lemma 4.4

Let f_b(x) = Tr_q/p(bx^T), $\widehat {f_{b}}(a)={\sum }_{x\in {\mathbb F}_{q^{2}}}\omega ^{{\operatorname {Tr}}_{q/p}(bx^{T})+{\operatorname {Tr}}_{q^{2}/p}(ax)}$, where $b\in {\mathbb F}_{r}$, $a\in {\mathbb F}_{q^{2}}$ and ω is the complex p-th root of unity. Then we have

$$\widehat{f_{b}}(a)= \left\{ \begin{array}{ll} -q\omega^{-{\operatorname{Tr}}_{q/p}{(\frac{a^{T}}{b})}},& \text{if} b\in {\mathbb F}_{r}^{*},\\ 0,& \text{if}b=0. \end{array} \right.$$

where $a\in {\mathbb F}_{q^{2}}$.

Proof

Since f_b(x) is a regular bent function, see [10], the result follows. □

Let ψ_b be an additive character of ${\mathbb F}_{r}$, where $b\in {\mathbb F}_{r}$. Let χ = χ₁ and ψ = ψ₁ be the canonical additive characters of ${\mathbb F}_{q^{2}}$ and ${\mathbb F}_{r}$ respectively. We set

$$ \delta_{4}(x)=\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}\psi_{b}({\operatorname{Tr}}_{q/r}(x^{T})), $$

then

$$\delta_{4}(x)= \left\{ \begin{array}{ll} 1,& \text{if\ }\operatorname{Tr}_{q/r}(x^{T})= 0,\\ 0,& \text{if\ }\operatorname{Tr}_{q/r}(x^{T})\neq 0. \end{array} \right.$$

Lemma 4.5

Let $P={\sum }_{x\in {\mathbb F}_{q^{2}} \atop {\operatorname {Tr}}_{q/r}(x^{T})=0}\chi (ax)$, where $a\in {\mathbb F}_{q^{2}}^{*}$. Then we have

$$P= \left\{ \begin{array}{ll} -\frac{q}{r}(r-1),& \text{if} {\operatorname{Tr}}_{q/r}(a^{T})= 0,\\ \frac{q}{r},& \text{if} {\operatorname{Tr}}_{q/r}(a^{T})\neq 0. \end{array} \right. $$

Proof

It follows that

$$ \begin{array}{@{}rcl@{}} P&=&\underset{\underset{\atop {\operatorname{Tr}}_{q/r}x^{T}=0}{x\in {\mathbb F}_{q^{2}}}}{\sum}\chi(ax)\\ &=&{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\delta_{4}(x)\\ &=&{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}\psi_{b}({\operatorname{Tr}}_{q/r}(x^{T}))\\ &=&\frac{1}{r}{\sum}_{x\in {\mathbb F}_{q^{2}}}{\sum}_{b\in {\mathbb F}_{r}}\omega^{{\operatorname{Tr}}_{r/p}(b{\operatorname{Tr}}_{q/r}(x^{T}))}\omega^{{\operatorname{Tr}}_{q^{2}/p}(ax)}\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}{\sum}_{x\in {\mathbb F}_{q^{2}}}\omega^{{\operatorname{Tr}}_{q/p}(bx^{T})+{\operatorname{Tr}}_{q^{2}/p}(ax)}\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}\widehat{f_{b}}(a)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}-q\omega^{-{\operatorname{Tr}}_{q/p}{(\frac{a^{T}}{b})}}\\ &=&-\frac{q}{r}{\sum}_{c\in {\mathbb F}_{r}^{*}}\omega^{{\operatorname{Tr}}_{q/p}{(ca^{T})}}\\ &=&-\frac{q}{r}{\sum}_{c\in {\mathbb F}_{r}^{*}}\omega^{{\operatorname{Tr}}_{r/p}(c{\operatorname{Tr}}_{q/r}{(a^{T})})}\\ &=&-\frac{q}{r}{\sum}_{c\in {\mathbb F}_{r}^{*}}\psi(c{\operatorname{Tr}}_{q/r}{(a^{T})}) \end{array} $$

The result follows from the fact that

$${\sum}_{c\in {\mathbb F}_{r}}\psi(c{\operatorname{Tr}}_{q/r}{(x^{T})})= \left\{ \begin{array}{ll} r,& \text{if }{\operatorname{Tr}}_{q/r}(x^{T})= 0,\\ 0,& \text{if }{\operatorname{Tr}}_{q/r}(x^{T})\neq 0. \end{array} \right. $$

□

Lemma 4.6

Let $Q={\sum }_{x\in {\mathbb F}_{q^{2}}}{\chi (ax)}\eta ({\operatorname {Tr}}_{q/r}(x^{T}))$, where $a\in {\mathbb F}_{q^{2}}^{*}$. Then we have

$$Q= \left\{ \begin{array}{ll} 0,& \text{if}\ \ {\operatorname{Tr}}_{q/r}(a^{T})= 0,\\ -q\eta(-{\operatorname{Tr}}_{q/r}(a^{T})),& \text{if}\ \ {\operatorname{Tr}}_{q/r}(a^{T})\neq 0. \end{array} \right. $$

Proof

It holds that

$$ \begin{array}{@{}rcl@{}} Q&=&{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\eta({\operatorname{Tr}}_{q/r}(x^{T}))\\ &=&{\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}})\psi_{b}({\operatorname{Tr}}_{q/r}(x^{T}))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q^{2}}}\chi(ax)\psi_{b}({\operatorname{Tr}}_{q/r}(x^{T}))\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q^{2}}} \omega^{{\operatorname{Tr}}_{q^{2}/p}(ax)}\omega^{{\operatorname{Tr}}_{r/p}(b{\operatorname{Tr}}_{q/r}(x^{T}))}\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}}G_{r}(\eta,\overline{\psi_{b}}){\sum}_{x\in {\mathbb F}_{q^{2}}}\omega^{{\operatorname{Tr}}_{q^{2}/p}(ax)+{\operatorname{Tr}}_{q/p}(bx^{T})}\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}G_{r}(\eta,\overline{\psi_{b}})\widehat{f_{b}}(a)\\ &=&\frac{1}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}G_{r}(\eta,\overline{\psi_{b}})(-q\omega^{-{\operatorname{Tr}}_{q/p}(\frac{a^{T}}{b})})\\ &=&-\frac{q}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}G_{r}(\eta,\overline{\psi_{b}})\omega^{{\operatorname{Tr}}_{r/p}(-\frac{1}{b}{\operatorname{Tr}}_{q/r}(a^{T}))}\\ &=&-\frac{q}{r}{\sum}_{b\in {\mathbb F}_{r}^{*}}\overline{\eta}(-b)G_{r}(\eta,{\psi})\psi(-\frac{1}{b}{\operatorname{Tr}}_{q/r}(a^{T}))\\ &=&-\frac{q}{r}G_{r}(\eta,{\psi}){\sum}_{c\in {\mathbb F}_{r}^{*}}\eta(c)\psi(c{\operatorname{Tr}}_{q/r}(a^{T}))\\ &=&-\frac{q}{r}G_{r}(\eta,{\psi})G_{r}(\eta,\psi_{{\operatorname{Tr}}_{q/r}(a^{T})}). \end{array} $$

The result follows from the fact that

$$G_{r}(\eta,\psi_{{\operatorname{Tr}}_{q/r}(a^{T})})= \left\{ \begin{array}{ll} 0,& \text{if\ }{\operatorname{Tr}}_{q/r}(a^{T})= 0,\\ \overline{\eta}({\operatorname{Tr}}_{q/r}(a^{T}))G_{r}(\eta,{\psi}),& \text{if\ }{\operatorname{Tr}}_{q/r}(a^{T})\neq 0, \end{array} \right. $$

and

$$G_{r}(\eta,{\psi})G_{r}(\eta,{\psi})=\eta(-1)r.$$

□

5 Concluding remarks

In this paper, we presented two new constructions of codebooks asymptotically achieve the Welch bounds with multiplicative characters, additive characters, trace functions and Fourier expansion of finite fields. Our two constructions are the generalizations of the constructions in [30] and [12], respectively. The parameters of our codebooks are flexible and new.

One feature of our construction is the combination of the character sums and the transitivity of trace functions. Since character sums of finite fields are one of the main methods used in the constructions of asymptotically optimal codebooks, we believe that using trace functions we can generalize more known codebooks constructed by character sums.

In our second construction, one key point is that f_b(x) in the Lemma IV.4 is a regular bent function. We wonder if there exist other (weakly) regular bent functions such that the codebooks constructed by them can asymptotically achieve the Welch bound.