February  2017, 11(1): 187-202. doi: 10.3934/amc.2017012

More constructions of near optimal codebooks associated with binary sequences

1. 

School of Mathematical Sciences, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu 210016

2. 

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

3. 

Institute of Mathematics, Academia Sinica, and Department of Math, National Chengchi University, Taipei 115, Taiwan

4. 

Department of Mathematics, Zhengzhou Information Science and Technology Institute, Zhengzhou, Henan 450002, China

* Corresponding author

Received  August 2015 Revised  January 2016 Published  February 2017

Fund Project: The work is supported by NNSF of China grant 11371011,61572027.

An $(N, K)$ codebook $\mathcal{C}$ is a collection of 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, denoted by $I_{\max}(\mathcal{C})$, between any pair of distinct code vectors. Since the famous Welch bound is a lower bound on $I_{\max}(\mathcal{C})$, it is desired to construct codebooks meeting the Welch bound strictly or asymptotically. Recently, N. Y. Yu presents a method for constructing codebooks associated with a binary sequence from a $\Phi$-transform matrix. Using this method, he discovers new classes of codebooks with nontrivial bounds on the maximum inner products from Fourier and Hadamard matrices. We construct more near optimal codebooks by Yu's idea. We first provide more choices of binary sequences. We also show more choices of the $\Phi$-transform matrices. Therefore, we can present more codebooks $\mathcal{C}$ with nontrivial bounds on their $I_{\max}(\mathcal{C})$. Our work can serve as a complement of Yu's work.

Citation: Xiwang Cao, Wun-Seng Chou, Xiyong Zhang. More constructions of near optimal codebooks associated with binary sequences. Advances in Mathematics of Communications, 2017, 11 (1) : 187-202. doi: 10.3934/amc.2017012
References:
[1]

S. Boztas and P. V. Kumar, Binary sequences with Gold-like correlation but larger linear span, IEEE Trans. Inf. Theory, 40 (1994), 532-537.  doi: 10.1109/18.312181.

[2]

P. CharpinE. Pasalic and C. Tavernier, On bent and semi-bent quadratic Boolean functions, IEEE Trans. Inf. Theory, 51 (2005), 4286-4298.  doi: 10.1109/TIT.2005.858929.

[3]

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.

[4]

P. DelsarteJ. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometriae Dedicate, 67 (1997), 363-388.  doi: 10.1007/BF03187604.

[5]

J. Dillon and H. Dobbertin, New cyclic difference sets with Singer parameters, Finite Fields Appl., 10 (2004), 342-389.  doi: 10.1016/j.ffa.2003.09.003.

[6]

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

[7]

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.

[8]

C. Ding and T. Feng, Codebooks from almost difference sets, Des. Codes Cryptogr., 46 (2008), 113-126.  doi: 10.1007/s10623-007-9140-z.

[9]

D. DongL. QuS. Fu and C. Li, New constructions of semi-bent functions in polynomial forms, Math. Comput. Model, 57 (2013), 1139-1147.  doi: 10.1016/j.mcm.2012.10.014.

[10]

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.

[11]

R. Gold, Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inform. Theory, 14 (1968), 154-156. 

[12]

T. Helleseth and A. Kholosha, On generalized bent functions, in Inf. Theory Appl. Workshop, San Diego, 2010. doi: 10.1109/ITA.2010.5454124.

[13]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier, New York, 1998.

[14]

S. HongH. ParkJ. -S. NoT. 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.

[15]

K. KhooG. Gong and D. R. Stinson, A new characterization of semi-bent and bent functions on finite fields, Des. Codes Cryptogr., 38 (2006), 279-295.  doi: 10.1007/s10623-005-6345-x.

[16]

G. Lachaud and J. Wolfmann, The weights of the orthogonals of the extened quadratic binary Goppa codes, IEEE Trans. Inform. Theory, 36 (1990), 686-692.  doi: 10.1109/18.54892.

[17]

J. LahtonenG. McGuire and H. W. Ward, Gold and Kasami-Welch functions, quadratic forms, Adv. Math. Commun., 1 (2007), 243-250.  doi: 10.3934/amc.2007.1.243.

[18]

M. H. Lee, Jacket Matrices: Constructions and Its Applications for Fast Cooperative Wireless Signal Processing, LAP LAMBERT Publishing, Germany, 2012.

[19]

R. Lidl and H. Niederriter, Finite fields, Encyclopedia Math. Appl. , 20 (1983), AddisonWesley, Reading.

[20]

S. Mesnager, On semi-bent functions and related plateaued functions over the Galois field ${\mathbb{F}_{{2^n}}}$, in Open Problems in Mathematics and Computational Science (ed. K. Koc), Springer, 2014,243-273.

[21]

O. S. Rothaus, On bent fucntions, J. Combin. Theory A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[22]

D. V. Sarwate, Meeting the Welch bound with equality, in Sequences and Their Applications (eds. C. Ding, T. Helleseth and H. Niederreiter), Springer-Verlag, New York, 1999, 79-102.

[23]

T. Strohmer and R. W. Heath Jr, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmonic Anal., 14 (2003), 257-275.  doi: 10.1016/S1063-5203(03)00023-X.

[24]

L. R. Welch, Lower bounds on themaximum cross correlation of signals, IEEE Trans. Inf. Theory, 20 (1974), 397-399. 

[25]

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

[26]

P. XiaS. 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.

[27]

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.

[28]

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

[29]

A. 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.

[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]

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.

show all references

References:
[1]

S. Boztas and P. V. Kumar, Binary sequences with Gold-like correlation but larger linear span, IEEE Trans. Inf. Theory, 40 (1994), 532-537.  doi: 10.1109/18.312181.

[2]

P. CharpinE. Pasalic and C. Tavernier, On bent and semi-bent quadratic Boolean functions, IEEE Trans. Inf. Theory, 51 (2005), 4286-4298.  doi: 10.1109/TIT.2005.858929.

[3]

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.

[4]

P. DelsarteJ. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometriae Dedicate, 67 (1997), 363-388.  doi: 10.1007/BF03187604.

[5]

J. Dillon and H. Dobbertin, New cyclic difference sets with Singer parameters, Finite Fields Appl., 10 (2004), 342-389.  doi: 10.1016/j.ffa.2003.09.003.

[6]

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

[7]

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.

[8]

C. Ding and T. Feng, Codebooks from almost difference sets, Des. Codes Cryptogr., 46 (2008), 113-126.  doi: 10.1007/s10623-007-9140-z.

[9]

D. DongL. QuS. Fu and C. Li, New constructions of semi-bent functions in polynomial forms, Math. Comput. Model, 57 (2013), 1139-1147.  doi: 10.1016/j.mcm.2012.10.014.

[10]

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.

[11]

R. Gold, Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE Trans. Inform. Theory, 14 (1968), 154-156. 

[12]

T. Helleseth and A. Kholosha, On generalized bent functions, in Inf. Theory Appl. Workshop, San Diego, 2010. doi: 10.1109/ITA.2010.5454124.

[13]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier, New York, 1998.

[14]

S. HongH. ParkJ. -S. NoT. 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.

[15]

K. KhooG. Gong and D. R. Stinson, A new characterization of semi-bent and bent functions on finite fields, Des. Codes Cryptogr., 38 (2006), 279-295.  doi: 10.1007/s10623-005-6345-x.

[16]

G. Lachaud and J. Wolfmann, The weights of the orthogonals of the extened quadratic binary Goppa codes, IEEE Trans. Inform. Theory, 36 (1990), 686-692.  doi: 10.1109/18.54892.

[17]

J. LahtonenG. McGuire and H. W. Ward, Gold and Kasami-Welch functions, quadratic forms, Adv. Math. Commun., 1 (2007), 243-250.  doi: 10.3934/amc.2007.1.243.

[18]

M. H. Lee, Jacket Matrices: Constructions and Its Applications for Fast Cooperative Wireless Signal Processing, LAP LAMBERT Publishing, Germany, 2012.

[19]

R. Lidl and H. Niederriter, Finite fields, Encyclopedia Math. Appl. , 20 (1983), AddisonWesley, Reading.

[20]

S. Mesnager, On semi-bent functions and related plateaued functions over the Galois field ${\mathbb{F}_{{2^n}}}$, in Open Problems in Mathematics and Computational Science (ed. K. Koc), Springer, 2014,243-273.

[21]

O. S. Rothaus, On bent fucntions, J. Combin. Theory A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[22]

D. V. Sarwate, Meeting the Welch bound with equality, in Sequences and Their Applications (eds. C. Ding, T. Helleseth and H. Niederreiter), Springer-Verlag, New York, 1999, 79-102.

[23]

T. Strohmer and R. W. Heath Jr, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmonic Anal., 14 (2003), 257-275.  doi: 10.1016/S1063-5203(03)00023-X.

[24]

L. R. Welch, Lower bounds on themaximum cross correlation of signals, IEEE Trans. Inf. Theory, 20 (1974), 397-399. 

[25]

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

[26]

P. XiaS. 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.

[27]

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.

[28]

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

[29]

A. 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.

[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]

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.

[1]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[2]

Francis C. Motta, Patrick D. Shipman. Informing the structure of complex Hadamard matrix spaces using a flow. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2349-2364. doi: 10.3934/dcdss.2019147

[3]

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

[4]

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

[5]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009

[6]

Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014

[7]

Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009

[8]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[9]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026

[10]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[11]

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

[12]

Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021, 3 (4) : 769-791. doi: 10.3934/fods.2021028

[13]

Lei Zhang, Anfu Zhu, Aiguo Wu, Lingling Lv. Parametric solutions to the regulator-conjugate matrix equations. Journal of Industrial and Management Optimization, 2017, 13 (2) : 623-631. doi: 10.3934/jimo.2016036

[14]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

[15]

Houduo Qi, ZHonghang Xia, Guangming Xing. An application of the nearest correlation matrix on web document classification. Journal of Industrial and Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701

[16]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103

[17]

Angelo B. Mingarelli. Nonlinear functionals in oscillation theory of matrix differential systems. Communications on Pure and Applied Analysis, 2004, 3 (1) : 75-84. doi: 10.3934/cpaa.2004.3.75

[18]

A. Cibotarica, Jiu Ding, J. Kolibal, Noah H. Rhee. Solutions of the Yang-Baxter matrix equation for an idempotent. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 347-352. doi: 10.3934/naco.2013.3.347

[19]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[20]

Leda Bucciantini, Angiolo Farina, Antonio Fasano. Flows in porous media with erosion of the solid matrix. Networks and Heterogeneous Media, 2010, 5 (1) : 63-95. doi: 10.3934/nhm.2010.5.63

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (173)
  • HTML views (59)
  • Cited by (7)

Other articles
by authors

[Back to Top]