American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020066

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

Gaojun Luo 1, and  Xiwang Cao 1,2,,

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.

Keywords: Codebook, Welch bound, linear code, permutation polynomial.
Mathematics Subject Classification: Primary: 11T71; Secondary: 11T23.
Citation: Gaojun Luo, Xiwang Cao. Two classes of near-optimal codebooks with respect to the Welch bound. Advances in Mathematics of Communications, 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. Cao, W. 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. Conway, R. 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. Delsarte, J. 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. Ding, J. 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. 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.  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. Hong, H. Park, T. 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. Luo, X. W. Cao, D. 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. Renes, R. Blume-Kohout, A. 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. Tan, Z. 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. Tang, N. Li, Y. 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. Xia, S. 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. Xiang, C. 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. Yu, K. 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. Zhou, C. 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. Zhou, N. Li, C. 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. Cao, W. 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. Conway, R. 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. Delsarte, J. 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. Ding, J. 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. 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.  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. Hong, H. Park, T. 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. Luo, X. W. Cao, D. 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. Renes, R. Blume-Kohout, A. 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. Tan, Z. 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. Tang, N. Li, Y. 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. Xia, S. 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. Xiang, C. 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. Yu, K. 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. Zhou, C. 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. Zhou, N. Li, C. 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 $
Table Options

Download as excel

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]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[2]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[3]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004
[4]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269
[5]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[6]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[7]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[8]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302
[9]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168
[10]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266
[11]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences