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]

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

[2]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[3]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2559-2599. doi: 10.3934/dcds.2020375

[4]

Liqin Qian, Xiwang Cao. Character sums over a non-chain ring and their applications. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020134

[5]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[6]

Mengyao Chen, Qi Li, Shuangjie Peng. Bound states for fractional Schrödinger-Poisson system with critical exponent. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021038

[7]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061

[8]

Mrinal K. Ghosh, Somnath Pradhan. A nonzero-sum risk-sensitive stochastic differential game in the orthant. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021025

[9]

Cheng Wang. Convergence analysis of Fourier pseudo-spectral schemes for three-dimensional incompressible Navier-Stokes equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2021019

[10]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068

[11]

Andreia Chapouto. A remark on the well-posedness of the modified KdV equation in the Fourier-Lebesgue spaces. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3915-3950. doi: 10.3934/dcds.2021022

[12]

Changpin Li, Zhiqiang Li. Asymptotic behaviors of solution to partial differential equation with Caputo–Hadamard derivative and fractional Laplacian: Hyperbolic case. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021023

[13]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[14]

Chloé Jimenez. A zero sum differential game with correlated informations on the initial position. A case with a continuum of initial positions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021009

[15]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (I): The sum of indices of equilibria is $ -1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021096

[16]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (II): The sum of indices of equilibria is $ 1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021101

[17]

Ruonan Liu, Run Xu. Hermite-Hadamard type inequalities for harmonical $ (h1,h2)- $convex interval-valued functions. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021005

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (94)
  • HTML views (57)
  • Cited by (6)

Other articles
by authors

[Back to Top]