-
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
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 |
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.
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. 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. |
[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. |
[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. |
[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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
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. 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. |
[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. |
[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. |
[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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
Bent functions | ||
arbitrary | arbitrary | |
arbitrary | ||
arbitrary | ||
arbitrary |
Bent functions | ||
arbitrary | arbitrary | |
arbitrary | ||
arbitrary | ||
arbitrary |
[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
Tools
Article outline
Figures and Tables
[Back to Top]