More constructions of near optimal codebooks associated with binary sequences

Xiwang Cao; Wun-Seng Chou; Xiyong Zhang

doi:10.3934/amc.2017012

Article Contents

2017, Volume 11, Issue 1: 187-202. Doi: 10.3934/amc.2017012

This issue Previous Article Codes from hall planes of odd order Next Article Information retrieval and the average number of input clues

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
^* Corresponding author

Received: August 2015

Revised: January 2016

Published: May 2017

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

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11T71; Secondary: 11T23.

Citation:

Full Text(HTML)

Related Papers

Cited by

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. Charpin, E. 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. 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.
[4]	P. Delsarte, J. 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. Dong, L. Qu, S. 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. 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.
[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. Hong, H. Park, J. -S. No, T. 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. Khoo, G. 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. Lahtonen, G. 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. Xia, S. 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. Yu, K. 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.