• Previous Article
    An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $
  • AMC Home
  • This Issue
  • Next Article
    On the existence of PD-sets: Algorithms arising from automorphism groups of codes
May  2021, 15(2): 279-289. doi: 10.3934/amc.2020066

Two classes of near-optimal codebooks with respect to the Welch bound

1. 

Department of Math, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

2. 

State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

* Corresponding author: Xiwang Cao

Received  March 2017 Revised  June 2017 Published  May 2021 Early access  January 2020

Fund Project: The second author is supported by the National Natural Science Foundation of China (Grant No. 11771007 and 61572027)

An $ (N,K) $ codebook $ {\mathcal C} $ is a collection of $ N $ unit norm vectors in a $ K $-dimensional vectors space. In applications of codebooks such as CDMA, those vectors in a codebook should have a small maximum magnitude of inner products between any pair of distinct code vectors. In this paper, we propose two constructions of codebooks based on $ p $-ary linear codes and on a hybrid character sum of a special kind of functions, respectively. With these constructions, two classes of codebooks asymptotically meeting the Welch bound are presented.

Citation: Gaojun Luo, Xiwang Cao. Two classes of near-optimal codebooks with respect to the Welch bound. Advances in Mathematics of Communications, 2021, 15 (2) : 279-289. doi: 10.3934/amc.2020066
References:
[1]

A. Calderbank and W. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122.  doi: 10.1112/blms/18.2.97.

[2]

E. J. Candes and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Process, 25 (2008), 21-30. 

[3]

X. W. Cao, J. F. Mi and S. D. Xu, Two constructions of approximately symmetric information complete positive operator-valued measures, J. Math. Phys, 58 (2017), 062201, 12pp. doi: 10.1063/1.4985153.

[4]

X. W. CaoW. Chou and X. Zhang, More constructions of near optimal codebooks associated with binary sequences, Adv. Math. Commun., 11 (2017), 187-202.  doi: 10.3934/amc.2017012.

[5]

J. H. ConwayR. H. Harding and N. J. A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Exp. Math., 5 (1996), 139-159.  doi: 10.1080/10586458.1996.10504585.

[6]

P. DelsarteJ. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometry and Combinatorics, (1991), 68-93.  doi: 10.1016/B978-0-12-189420-7.50013-X.

[7]

C. S. DingJ. Q. Luo and H. Niederreiter, Two-weight codes punctured from irreducible cyclic codes, Ser. Coding Theory Cryptol, 4 (2008), 119-124.  doi: 10.1142/9789812832245_0009.

[8]

C. S. Ding, Complex codebooks from combinatorial designs, IEEE Trans. Inform. Theory, 52 (2006), 4229-4235.  doi: 10.1109/TIT.2006.880058.

[9]

C. S. Ding and T. Feng, A generic construction of complex codebooks meeting the Welch bound, IEEE Trans. Inform. Theory, 53 (2007), 4245-4250.  doi: 10.1109/TIT.2007.907343.

[10]

C. S. Ding and H. Niederreiter, Cyclotomic linear codes of order 3, IEEE Trans. Inform. Theory, 53 (2007), 2274-2277.  doi: 10.1109/TIT.2007.896886.

[11]

C. S. Ding, A construction of binary linear codes from Boolean functions, Discret. Math., 339 (2016), 2288-2303.  doi: 10.1016/j.disc.2016.03.029.

[12]

K. L. Ding and C. S. Ding, A class of two-weight and three-weight codes and their applications in secret sharing, IEEE Trans. Inform. Theory, 61 (2015), 5835-5842.  doi: 10.1109/TIT.2015.2473861.

[13]

M. FickusD. 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.

[14]

T. Helleseth and A. Kholosha, Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 52 (2006), 2018-2032.  doi: 10.1109/TIT.2006.872854.

[15]

T. Helleseth and A. Kholosha, New binomial bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 56 (2010), 4646-4652.  doi: 10.1109/TIT.2010.2055130.

[16]

S. HongH. ParkT. Helleseth and Y. S. Kim, Near optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping, IEEE Trans. Inform. Theory, 60 (2014), 3698-3705.  doi: 10.1109/TIT.2014.2314298.

[17]

H. Hu and J. Wu, New constructions of codebooks nearly meeting the Welch bound with equality, IEEE Trans. Inform. Theory, 60 (2014), 1348-1355.  doi: 10.1109/TIT.2013.2292745.

[18]

V. I. Levenshtein, Bounds for packing of metric spaces and some of their applications, Probl. Cybern., 40 (1983), 43-110. 

[19] R. Lidl and H. Niederreiter, Finite Fields, Cambridge university press, 1997. 
[20]

G. J. LuoX. W. CaoD. Xu and J. Mi, Binary linear codes with two or three weights from niho exponents, Cryptogr. Commun., 10 (2018), 301-318.  doi: 10.1007/s12095-017-0220-2.

[21]

J. L. Massey and T. Mittelholzer, Welch's bound and sequence sets for code-division multiple-access systems, Sequences II, Springer New York, (1993), 63–78.

[22]

J. M. RenesR. Blume-KohoutA. Scot and C. Caves, Symmetric informationally complete quantum measurements, J. Math. Phys., 45 (2004), 2171-2180.  doi: 10.1063/1.1737053.

[23]

D. V. Sarwate, Meeting the Welch bound with equality, Sequences and their Applications, Springer London, (1999), 79–102.

[24]

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.

[25]

P. TanZ. C. Zhou and D. Zhang, A construction of codebooks nearly achieving the Levenshtein bound, IEEE Signal Processing Letters, 23 (2016), 1306-1309. 

[26]

C. M. TangN. LiY. Qi and Z. C. Zhou, Linear codes with two or three weights from weakly regular bent functions, IEEE Trans. Inform. Theory, 62 (2016), 1166-1176.  doi: 10.1109/TIT.2016.2518678.

[27]

L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, 20 (1974), 397-399.  doi: 10.1109/TIT.1974.1055219.

[28]

W. Wootters and B. Fields, Optimal state-determination by mutually unbiased measurements, Ann. Phys., 191 (1989), 363-381.  doi: 10.1016/0003-4916(89)90322-9.

[29]

P. XiaS. Zhou and G. B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory, 51 (2005), 1900-1907.  doi: 10.1109/TIT.2005.846411.

[30]

C. XiangC. S. Ding and S. Mesnager, Optimal codebooks from binary codes meeting the levenshtein bound, IEEE Trans. Inform. Theory, 61 (2015), 6526-6535.  doi: 10.1109/TIT.2015.2487451.

[31]

N. Y. Yu, A construction of codebooks associated with binary sequences, IEEE Trans. Inform. Theory, 58 (2012), 5522-5533.  doi: 10.1109/TIT.2012.2196021.

[32]

N. Y. YuK. Feng and A. X. Zhang, A new class of near-optimal partial Fourier codebooks from an almost difference set, Des. Codes Cryptogr., 71 (2014), 493-501.  doi: 10.1007/s10623-012-9753-8.

[33]

A. X. Zhang and K. Feng, Two classes of codebooks nearly meeting the Welch bound, IEEE Trans. Inform. Theory, 58 (2012), 2507-2511.  doi: 10.1109/TIT.2011.2176531.

[34]

A. X. Zhang and K. Feng, Construction of cyclotomic codebooks nearly meeting the Welch bound, Des. Codes Cryptogr., 63 (2012), 209-224.  doi: 10.1007/s10623-011-9549-2.

[35]

Z. C. ZhouC. S. Ding and N. Li, New families of codebooks achieving the Levenshtein bound, IEEE Trans. Inf. Theory, 60 (2014), 7382-7387.  doi: 10.1109/TIT.2014.2353052.

[36]

Z. C. Zhou and X. H. Tang, New nearly optimal codebooks from relative difference sets, Adv. Math. Commun., 5 (2011), 521-527.  doi: 10.3934/amc.2011.5.521.

[37]

Z. C. ZhouN. LiC. L. Fan and T. Helleseth, Linear codes with two or three weights from quadratic Bent functions, Des. Codes Cryptor., 81 (2016), 283-295.  doi: 10.1007/s10623-015-0144-9.

show all references

References:
[1]

A. Calderbank and W. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122.  doi: 10.1112/blms/18.2.97.

[2]

E. J. Candes and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Process, 25 (2008), 21-30. 

[3]

X. W. Cao, J. F. Mi and S. D. Xu, Two constructions of approximately symmetric information complete positive operator-valued measures, J. Math. Phys, 58 (2017), 062201, 12pp. doi: 10.1063/1.4985153.

[4]

X. W. CaoW. Chou and X. Zhang, More constructions of near optimal codebooks associated with binary sequences, Adv. Math. Commun., 11 (2017), 187-202.  doi: 10.3934/amc.2017012.

[5]

J. H. ConwayR. H. Harding and N. J. A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Exp. Math., 5 (1996), 139-159.  doi: 10.1080/10586458.1996.10504585.

[6]

P. DelsarteJ. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometry and Combinatorics, (1991), 68-93.  doi: 10.1016/B978-0-12-189420-7.50013-X.

[7]

C. S. DingJ. Q. Luo and H. Niederreiter, Two-weight codes punctured from irreducible cyclic codes, Ser. Coding Theory Cryptol, 4 (2008), 119-124.  doi: 10.1142/9789812832245_0009.

[8]

C. S. Ding, Complex codebooks from combinatorial designs, IEEE Trans. Inform. Theory, 52 (2006), 4229-4235.  doi: 10.1109/TIT.2006.880058.

[9]

C. S. Ding and T. Feng, A generic construction of complex codebooks meeting the Welch bound, IEEE Trans. Inform. Theory, 53 (2007), 4245-4250.  doi: 10.1109/TIT.2007.907343.

[10]

C. S. Ding and H. Niederreiter, Cyclotomic linear codes of order 3, IEEE Trans. Inform. Theory, 53 (2007), 2274-2277.  doi: 10.1109/TIT.2007.896886.

[11]

C. S. Ding, A construction of binary linear codes from Boolean functions, Discret. Math., 339 (2016), 2288-2303.  doi: 10.1016/j.disc.2016.03.029.

[12]

K. L. Ding and C. S. Ding, A class of two-weight and three-weight codes and their applications in secret sharing, IEEE Trans. Inform. Theory, 61 (2015), 5835-5842.  doi: 10.1109/TIT.2015.2473861.

[13]

M. FickusD. 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.

[14]

T. Helleseth and A. Kholosha, Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 52 (2006), 2018-2032.  doi: 10.1109/TIT.2006.872854.

[15]

T. Helleseth and A. Kholosha, New binomial bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 56 (2010), 4646-4652.  doi: 10.1109/TIT.2010.2055130.

[16]

S. HongH. ParkT. Helleseth and Y. S. Kim, Near optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping, IEEE Trans. Inform. Theory, 60 (2014), 3698-3705.  doi: 10.1109/TIT.2014.2314298.

[17]

H. Hu and J. Wu, New constructions of codebooks nearly meeting the Welch bound with equality, IEEE Trans. Inform. Theory, 60 (2014), 1348-1355.  doi: 10.1109/TIT.2013.2292745.

[18]

V. I. Levenshtein, Bounds for packing of metric spaces and some of their applications, Probl. Cybern., 40 (1983), 43-110. 

[19] R. Lidl and H. Niederreiter, Finite Fields, Cambridge university press, 1997. 
[20]

G. J. LuoX. W. CaoD. Xu and J. Mi, Binary linear codes with two or three weights from niho exponents, Cryptogr. Commun., 10 (2018), 301-318.  doi: 10.1007/s12095-017-0220-2.

[21]

J. L. Massey and T. Mittelholzer, Welch's bound and sequence sets for code-division multiple-access systems, Sequences II, Springer New York, (1993), 63–78.

[22]

J. M. RenesR. Blume-KohoutA. Scot and C. Caves, Symmetric informationally complete quantum measurements, J. Math. Phys., 45 (2004), 2171-2180.  doi: 10.1063/1.1737053.

[23]

D. V. Sarwate, Meeting the Welch bound with equality, Sequences and their Applications, Springer London, (1999), 79–102.

[24]

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.

[25]

P. TanZ. C. Zhou and D. Zhang, A construction of codebooks nearly achieving the Levenshtein bound, IEEE Signal Processing Letters, 23 (2016), 1306-1309. 

[26]

C. M. TangN. LiY. Qi and Z. C. Zhou, Linear codes with two or three weights from weakly regular bent functions, IEEE Trans. Inform. Theory, 62 (2016), 1166-1176.  doi: 10.1109/TIT.2016.2518678.

[27]

L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, 20 (1974), 397-399.  doi: 10.1109/TIT.1974.1055219.

[28]

W. Wootters and B. Fields, Optimal state-determination by mutually unbiased measurements, Ann. Phys., 191 (1989), 363-381.  doi: 10.1016/0003-4916(89)90322-9.

[29]

P. XiaS. Zhou and G. B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory, 51 (2005), 1900-1907.  doi: 10.1109/TIT.2005.846411.

[30]

C. XiangC. S. Ding and S. Mesnager, Optimal codebooks from binary codes meeting the levenshtein bound, IEEE Trans. Inform. Theory, 61 (2015), 6526-6535.  doi: 10.1109/TIT.2015.2487451.

[31]

N. Y. Yu, A construction of codebooks associated with binary sequences, IEEE Trans. Inform. Theory, 58 (2012), 5522-5533.  doi: 10.1109/TIT.2012.2196021.

[32]

N. Y. YuK. Feng and A. X. Zhang, A new class of near-optimal partial Fourier codebooks from an almost difference set, Des. Codes Cryptogr., 71 (2014), 493-501.  doi: 10.1007/s10623-012-9753-8.

[33]

A. X. Zhang and K. Feng, Two classes of codebooks nearly meeting the Welch bound, IEEE Trans. Inform. Theory, 58 (2012), 2507-2511.  doi: 10.1109/TIT.2011.2176531.

[34]

A. X. Zhang and K. Feng, Construction of cyclotomic codebooks nearly meeting the Welch bound, Des. Codes Cryptogr., 63 (2012), 209-224.  doi: 10.1007/s10623-011-9549-2.

[35]

Z. C. ZhouC. S. Ding and N. Li, New families of codebooks achieving the Levenshtein bound, IEEE Trans. Inf. Theory, 60 (2014), 7382-7387.  doi: 10.1109/TIT.2014.2353052.

[36]

Z. C. Zhou and X. H. Tang, New nearly optimal codebooks from relative difference sets, Adv. Math. Commun., 5 (2011), 521-527.  doi: 10.3934/amc.2011.5.521.

[37]

Z. C. ZhouN. LiC. L. Fan and T. Helleseth, Linear codes with two or three weights from quadratic Bent functions, Des. Codes Cryptor., 81 (2016), 283-295.  doi: 10.1007/s10623-015-0144-9.

Table 1.  Known weakly regular bent functions over $ {\mathbb F}_{p^m} $ with odd characteristic $ p $
Bent functions $ m $ $ p $
$ \sum_{i=0}^{\lfloor m/2\rfloor}\operatorname{Tr}_{1}^{m}(a_ix^{p^i+1}) $ arbitrary arbitrary
$ \sum_{i=0}^{p^k-1}\operatorname{Tr}^m_1(a_ix^{i(p^k-1)})+\operatorname{Tr}^l_1(\epsilon x^{\frac{p^m-1}{e}}) $, $ e|p^k+1 $ $ m=2k $ arbitrary
$ \operatorname{Tr}_{1}^{m}(ax^{\frac{3^m-1}{4}+3^k+1}) $ $ m=2k $ $ p=3 $
$ \operatorname{Tr}_{1}^{m}(x^{p^{3k}+p^{2k}-p^k+1}+x^2) $ $ m=4k $ arbitrary
$ \operatorname{Tr}_{1}^{m}(ax^{\frac{3^i+1}{2}}) $; $ i $ odd, $ {\rm gcd}(i,m)=1 $ arbitrary $ p=3 $
Bent functions $ m $ $ p $
$ \sum_{i=0}^{\lfloor m/2\rfloor}\operatorname{Tr}_{1}^{m}(a_ix^{p^i+1}) $ arbitrary arbitrary
$ \sum_{i=0}^{p^k-1}\operatorname{Tr}^m_1(a_ix^{i(p^k-1)})+\operatorname{Tr}^l_1(\epsilon x^{\frac{p^m-1}{e}}) $, $ e|p^k+1 $ $ m=2k $ arbitrary
$ \operatorname{Tr}_{1}^{m}(ax^{\frac{3^m-1}{4}+3^k+1}) $ $ m=2k $ $ p=3 $
$ \operatorname{Tr}_{1}^{m}(x^{p^{3k}+p^{2k}-p^k+1}+x^2) $ $ m=4k $ arbitrary
$ \operatorname{Tr}_{1}^{m}(ax^{\frac{3^i+1}{2}}) $; $ i $ odd, $ {\rm gcd}(i,m)=1 $ arbitrary $ p=3 $
[1]

Gang Wang, Deng-Ming Xu, Fang-Wei Fu. Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021065

[2]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[3]

Marcin Dumnicki, Łucja Farnik, Halszka Tutaj-Gasińska. Asymptotic Hilbert polynomial and a bound for Waldschmidt constants. Electronic Research Announcements, 2016, 23: 8-18. doi: 10.3934/era.2016.23.002

[4]

John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.

[5]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132

[6]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure and Applied Analysis, 2009, 8 (3) : 1053-1065. doi: 10.3934/cpaa.2009.8.1053

[7]

J. De Beule, K. Metsch, L. Storme. Characterization results on weighted minihypers and on linear codes meeting the Griesmer bound. Advances in Mathematics of Communications, 2008, 2 (3) : 261-272. doi: 10.3934/amc.2008.2.261

[8]

Paolo Gidoni, Alessandro Margheri. Lower bound on the number of periodic solutions for asymptotically linear planar Hamiltonian systems. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 585-606. doi: 10.3934/dcds.2019024

[9]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[10]

Stefano Barbero, Emanuele Bellini, Rusydi H. Makarim. Rotational analysis of ChaCha permutation. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021057

[11]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018

[12]

Jaume Llibre, Yilei Tang. Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1769-1784. doi: 10.3934/dcdsb.2018236

[13]

Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363

[14]

Elimhan N. Mahmudov. Optimal control of evolution differential inclusions with polynomial linear differential operators. Evolution Equations and Control Theory, 2019, 8 (3) : 603-619. doi: 10.3934/eect.2019028

[15]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[16]

Alireza Khatib, Liliane A. Maia. A positive bound state for an asymptotically linear or superlinear Schrödinger equation in exterior domains. Communications on Pure and Applied Analysis, 2018, 17 (6) : 2789-2812. doi: 10.3934/cpaa.2018132

[17]

David Gómez-Ullate, Niky Kamran, Robert Milson. Structure theorems for linear and non-linear differential operators admitting invariant polynomial subspaces. Discrete and Continuous Dynamical Systems, 2007, 18 (1) : 85-106. doi: 10.3934/dcds.2007.18.85

[18]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[19]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[20]

Jyrki Lahtonen, Gary McGuire, Harold N. Ward. Gold and Kasami-Welch functions, quadratic forms, and bent functions. Advances in Mathematics of Communications, 2007, 1 (2) : 243-250. doi: 10.3934/amc.2007.1.243

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (279)
  • HTML views (609)
  • Cited by (0)

Other articles
by authors

[Back to Top]