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

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

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

[4]

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

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

[6]

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

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

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

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

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

[11]

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

[12]

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

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

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

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

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

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

[18]

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

[19]

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

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

[21]

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

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

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

[24]

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

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

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

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

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

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

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

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

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

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

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

[4]

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

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

[6]

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

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

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

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

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

[11]

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

[12]

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

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

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

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

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

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

[18]

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

[19]

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

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

[21]

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

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

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

[24]

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

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

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

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

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

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

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

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

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Debasisha Mishra. Matrix group monotonicity using a dominance notion. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 267-274. doi: 10.3934/naco.2015.5.267

[15]

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053

[16]

Joshua Du, Jun Ji. An integral representation of the determinant of a matrix and its applications. Conference Publications, 2005, 2005 (Special) : 225-232. doi: 10.3934/proc.2005.2005.225

[17]

Boris Baeumer, Lipika Chatterjee, Peter Hinow, Thomas Rades, Ami Radunskaya, Ian Tucker. Predicting the drug release kinetics of matrix tablets. Discrete & Continuous Dynamical Systems - B, 2009, 12 (2) : 261-277. doi: 10.3934/dcdsb.2009.12.261

[18]

A. Chauviere, L. Preziosi, T. Hillen. Modeling the motion of a cell population in the extracellular matrix. Conference Publications, 2007, 2007 (Special) : 250-259. doi: 10.3934/proc.2007.2007.250

[19]

Yi Yang, Jianwei Ma, Stanley Osher. Seismic data reconstruction via matrix completion. Inverse Problems & Imaging, 2013, 7 (4) : 1379-1392. doi: 10.3934/ipi.2013.7.1379

[20]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020103

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (11)
  • HTML views (1)
  • Cited by (0)

Other articles
by authors

[Back to Top]