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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[20]

Stefan Possanner, Claudia Negulescu. Diffusion limit of a generalized matrix Boltzmann equation for spin-polarized transport. Kinetic & Related Models, 2011, 4 (4) : 1159-1191. doi: 10.3934/krm.2011.4.1159

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]