• 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  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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19] R. Lidl and H. Niederreiter, Finite Fields, Cambridge university press, 1997.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19] R. Lidl and H. Niederreiter, Finite Fields, Cambridge university press, 1997.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[2]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[3]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[4]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[5]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[6]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[7]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[9]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024

[10]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[11]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[12]

Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006

[13]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

[14]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

[15]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (95)
  • HTML views (521)
  • Cited by (0)

Other articles
by authors

[Back to Top]