Three constructions of asymptotically optimal codebooks via multiplicative characters of finite fields

Wei Lu; Xia Wu; Xiwang Cao

doi:10.3934/amc.2022091

Article Contents

2024, Volume 18, Issue 5: 1334-1342. Doi: 10.3934/amc.2022091

This issue Previous Article Two constructions for optimal Z-complementary sequence sets Next Article RLWE/PLWE equivalence for the maximal totally real subextension of the $ 2^rpq $-th cyclotomic field

Three constructions of asymptotically optimal codebooks via multiplicative characters of finite fields

Wei Lu^1,,
Xia Wu^1, , and
Xiwang Cao^2,

1.
School of Mathematics, Southeast University, Nanjing, 210096, China
2.
Department of Math, Nanjing University of Aeronautics and Astronautics, Nanjing, 211100, China

^* Corresponding author: Xia Wu
^* Corresponding author: Xia Wu

Received: June 2022

Revised: August 2022

Early access: November 2022

Published: October 2024

This research is supported by the National Natural Science Foundation of China (11971102 and 12171241)

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

In this paper, we give three constructions of codebooks with multiplicative characters of finite fields. Our constructions generalize the first construction in A. X. Zhang and K. Q. Feng (IEEE Trans. Inf. Theory 58(4), 2507-2511, 2012) from one dimension to two dimensions. We determine the maximum cross-correlation amplitude of these codebooks by the orthogonal relation of multiplicative characters and the properties of Jacobi sum. We prove that all the codebooks we constructed are asymptotically optimal with respect to the Welch bound. The parameters of these codebooks are new.

Keywords:

Mathematics Subject Classification: Primary: 94A05, 11T24.

Citation:

Full Text(HTML)

Table 1. The parameters of codebooks asymptotically meeting the Welch bound

Parameters $ (N, K) $	$ I_{max} $	References
$(p^n, K=\frac{p-1}{2p}(p^n+p^{n/2})+1)$ with odd $p$	$ \frac{(p+1)p^{n/2}}{2pK} $	[12]
$ (q^2, \frac{(q-1)^2}{2}) $, $ q=p^s $ with odd $ p $	$ \frac{q+1}{(q-1)^2} $	[30]
$ q(q+4), \frac{q+1}{2} $, $ q $ is a prime power	$ \frac{1}{q+1} $	[15]
$ (q, \frac{(q+3)(q+1)}{2}) $, $ q $ is a prime power	$ \frac{\sqrt{q}+1}{q-1} $	[15]
$ (p^n-1, \frac{p^n-1}{2}) $ with odd $ p $	$ \frac{\sqrt{p^n}+1}{p^n-1} $	[29]
$ (q^l+q^{l-1}-1, q^{l-1}) $ for any $ l>2 $	$ \frac{1}{\sqrt{q^{l-1}}} $	[32]
$((q-1)^k+q^{k-1}, q^{k-1}$), for any $k>2$ and $q\geq4$	$ \frac{\sqrt{q^{k+1}}}{(q-1)^k+(-1)^{k+1}} $	[11]
$((q-1)^k+K, K$), for any $k>2$, where $K=\frac{(q-1)^k+(-1)^{k+1}}{q}$	$ \frac{\sqrt{q^{k-1}}}{K} $	[11]
$((q^s-1)^n+K, K)$, for any $s>1$ and $n>1$, where $K=\frac{(q^s-1)^n+(-1)^{n+1}}{q})$	$ \frac{\sqrt{q^{sn+1}}}{(q^s-1)^n+(-1)^{n+1}} $	[18]
$((q^s-1)^n+q^{sn-1}, q^{sn-1})$, for any $s>1$ and $n>1$	$ \frac{\sqrt{q^{sn+1}}}{(q^s-1)^n+(-1)^{n+1}} $	[18]
$(q-1, \frac{q(r-1)}{2r})$, $r=p^t, q=r^s$, with odd $p$ and $p\nmid s$	$ \frac{\sqrt{r}}{\sqrt{q}(\sqrt{r}-1)K} $	[27]
$(q^2, \frac{q(q+1)(r-1)}{2r})$, $r=p^t, q=r^s$, with odd $p$	$ \frac{(r+1)q}{2rK} $	[27]
$((q-1)^2, \frac{q^2-4q+5}{2})$, $q$ is an odd prime power	$\frac{q-2+\sqrt{q}}{2K}$, when $q\geq 9$; $\frac{q+1}{2K}, $ when $q <9$,	this paper
$((q-1)^2, \frac{(q-1)(q-3)}{2})$, $q$ is an odd prime power	$\frac{q-2+\sqrt{q}}{2K}$, when $q\geq 9$; $\frac{q+1}{2K}, $ when $q <9$,	this paper
$((q_1-1)(q_2-1), \frac{q_1q_2-2q_1-2q_2+5}{2})$, $q_1$ and $q_2$ are both odd prime powers	$\frac{q_2-2+\sqrt{q_1}}{2K}$, when $q_2\geq q_1\geq 9$	this paper

| Show Table

DownLoad: CSV

Table 2. Parameters of the $ (N, K) $ codebooks

$ q $	$ N $	$ K $	$ I_{max}( {\mathcal C}) $	$ I_{W} $	$ \frac{I_{max}( {\mathcal C})}{I_{W}} $
$ 3 $	$ 4 $	$ 1 $	$ 2 $	$ 1 $	$ 2 $
$ 5 $	$ 16 $	$ 5 $	$ 0.6 $	$ 0.3830 $	$ 1.5667 $
$ 13 $	$ 144 $	$ 61 $	$ 0.1197 $	$ 0.0975 $	$ 1.2273 $
$ 49 $	$ 2304 $	$ 1105 $	$ 0.0244 $	$ 0.0217 $	$ 1.1257 $
$ 5^{3} $	$ 15376 $	$ 7565 $	$ 0.0089 $	$ 0.0082 $	$ 1.0822 $
$ 5^{4} $	$ 389376 $	$ 194065 $	$ 0.0017 $	$ 0.0016 $	$ 1.0385 $
$ 7^{4} $	$ 5760000 $	$ 2877601 $	$ 4.2535e-04 $	$ 4.1701e-04 $	$ 1.0200 $
$ 11^{4} $	$ 214329600 $	$ 107150161 $	$ 6.8875e-05 $	$ 6.8315e-05 $	$ 1.0082 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. J. Candes and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Process. Mag., 25 (2008)), 21-30. doi: 10.1109/MSP.2007.914731.
[2]	J. H. Conway, R. H. Harding and N. J. A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Exp. Math., 5 (1996), 139-159. https://projecteuclid.org/journals/experimental-mathematics/volume-5/issue-2/Packing-lines-planes-etc-packings-in-Grassmannian-spaces/em/1047565645.full
[3]	P. Delsarte, J. J. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometriae Dedicate, 67 (1997), 363-388. doi: 10.1007/BF03187604.
[4]	C. Ding, Complex codebooks from combinatorial designs, IEEE Trans. Inf. Theory, 52 (2006), 4229-4235. doi: 10.1109/TIT.2006.880058.
[5]	C. Ding and T. Feng, A generic construction of complex codebooks meeting the Welch bound, IEEE Trans. Inf. Theory, 53 (2007), 4245-4250. doi: 10.1109/TIT.2007.907343.
[6]	M. Fickus, J. Jasper, D. Mixon and J. Peterson, Tremain equiangular tight frames, Journal of Combinatorial Theory, Series A, 153 (2016), 54-66. doi: 10.1016/j.jcta.2017.08.005.
[7]	M. Fickus and D. Mixon, Tables of the existence of equiangular tight frames, arXiv: 1504.00253v2, (2016).
[8]	M. Fickus, D. G. Mixon and J. Jasper, Equiangular tight frames from hyperovals, IEEE Trans. Inf. Theory, 62 (2016), 5225-5236. doi: 10.1109/TIT.2016.2587865.
[9]	M. Fickus, D. G. Mixon and J. C. Tremain, Steiner equiangular tight frames, Linear Algebra Appl., 436 (2012), 1014-1027. doi: 10.1016/j.laa.2011.06.027.
[10]	Z. Heng, Nearly optimal codebooks based on generalized Jacobi sums, Discrete Appl. Math., 250 (2018), 227-240. doi: 10.1016/j.dam.2018.05.017.
[11]	Z. Heng, C. Ding and Q. Yue, New constructions of asymptotically optimal codebooks with multiplicative characters, IEEE Trans. Inf. Theory, 63 (2017), 6179-6187. doi: 10.1109/TIT.2017.2693204.
[12]	S. Hong, H. Park, J.-S. No, T. Helleseth and Y.-S. Kim, Near optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping, IEEE Trans. Inf. Theory, 60 (2014), 3698-3705. doi: 10.1109/TIT.2014.2314298.
[13]	H. Hu and J. Wu, New constructions of codebooks nearly meeting the Welch bound with equality, IEEE Trans. Inf. Theory, 60 (2014), 1348-1355. doi: 10.1109/TIT.2013.2292745.
[14]	J. Kovacevic and A. Chebira, An introduction to frames, Found. Trends Signal Process., 2 (2008), 1-94. doi: 10.1561/2000000006.
[15]	C. Li, Y. Qin and Y. Huang, Two families of nearly optimal codebooks, Des. Codes Cryptogr., 75 (2015), 43-57. doi: 10.1007/s10623-013-9891-7.
[16]	R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, (1997).
[17]	W. Lu, X. Wu, X. Cao and M. Chen, Six constructions of asymptotically optimal codebooks via the character sums, Des. Codes Cryptogr., 88 (2020), 1139-1158. doi: 10.1007/s10623-020-00735-w.
[18]	G. Luo and X. Cao, Two constructions of asymptotically optimal codebooks via the hyper Eisenstein sum, IEEE Trans. Inf. Theory, 64 (2018), 6498-6505. doi: 10.1109/TIT.2017.2777492.
[19]	G. Luo and X. Cao, New constructions of codebooks asymptotically achieving the Welch bound, in Proc. IEEE Int. Symp. Inf. Theory, Vail, CO, USA, (2018), 2346-2349. doi: 10.1109/ISIT.2018.8437838.
[20]	G. Luo and X. Cao, Two constructions of asymptotically optimal codebooks, Crypt. Commun., 11 (2019), 825-838. doi: 10.1007/s12095-018-0331-4.
[21]	J. L. Massey and T. Mittelholzer, Welch's bound and sequence sets for code-division multiple-access systems, Sequences II, Springer New York, (1999), 63-78.
[22]	F. Rahimi, Covering Graphs and Equiangular Tight Frames, Ph.D. Thesis, University of Waterloo, Ontario, (2016) (available at http://hdl.handle.net/10012/10793).
[23]	J. M. Renes, R. Blume-Kohout, A. J. Scot and C. M. Caves, Symmetric informationally complete quantum measurements, J. Math. Phys., 45 (2004), 2171-2180. doi: 10.1063/1.1737053.
[24]	D. V. Sarwate, Meeting the Welch bound with equality, New York, NY, USA: Springer-Verlag, (1999), 79-102. doi: 10.1007/978-1-4471-0551-0_6.
[25]	T. Strohmer and R. W. Heath, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal., 14 (2003), 257-275. doi: 10.1016/S1063-5203(03)00023-X.
[26]	L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory, 20 (1974), 397-399. doi: 10.1109/TIT.1974.1055219.
[27]	X. Wu, W. Lu and X. Cao, Two constructions of asymptotically optimal codebooks via the trace functions, Crypt. Commun., 12 (2020), 1195-1211. doi: 10.1007/s12095-020-00448-w.
[28]	P. Xia, S. Zhou and G. B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inf. Theory, 51 (2005), 1900-1907. doi: 10.1109/TIT.2005.846411.
[29]	N. Y. Yu, A construction of codebooks associated with binary sequences, IEEE Trans. Inf. Theory, 58 (2012), 5522-5533. doi: 10.1109/TIT.2012.2196021.
[30]	A. Zhang and K. Feng, Two classes of codebooks nearly meeting the Welch bound, IEEE Trans. Inf. Theory, 58 (2012), 2507-2511. doi: 10.1109/TIT.2011.2176531.
[31]	A. Zhang and K. Feng, Construction of cyclotomic codebooks nearly meeting the Welch bound, Des. Codes Cryptogr., 63 (2013), 209-224. doi: 10.1007/s10623-011-9549-2.
[32]	Z. Zhou and X. Tang, New nearly optimal codebooks from relative difference sets, Adv. Math. Commun., 5 (2011), 521-527. doi: 10.3934/amc.2011.5.521.