Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound

Gang Wang; Deng-Ming Xu; Fang-Wei Fu

doi:10.3934/amc.2021065

Article Contents

2021, Volume 0. Doi: 10.3934/amc.2021065

Previous Article Next Article

Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound

1.
School of Mathematical Sciences, Tianjin Normal University, Tianjin 300387, China
2.
Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China
3.
Chern Institute of Mathematics and LPMC, Nankai University, Tianjin 300071, China

^*Corresponding author: Gang Wang
^*Corresponding author: Gang Wang

Received: May 31, 2021

Revised: September 30, 2021

Early access: December 2021

G. Wang is supported by the Doctoral Foundation of Tianjin Normal University (Grant No. 52XB2014). F.-W Fu is supported by the National Key Research and Development Program of China (Grant No. 2018YFA0704703), the National Natural Science Foundation of China (Grant No. 61971243), the Natural Science Foundation of Tianjin (20JCZDJC00610), the Fundamental Research Funds for the Central Universities of China (Nankai University), and the Nankai Zhide Foundation

Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by

Abstract

Codebooks with small maximum cross-correlation amplitudes are used to distinguish the signals from different users in code division multiple access communication systems. In this paper, several classes of codebooks are introduced, whose maximum cross-correlation amplitudes asymptotically achieve the corresponding Welch bound and Levenshtein bound. Specially, a class of optimal codebooks with respect to the Levenshtein bound is obtained. These classes of codebooks are constructed by selecting certain rows deterministically from circulant matrices, Fourier matrices and Hadamard matrices, respectively. The construction methods and parameters of some codebooks provided in this paper are new.

Keywords:

Mathematics Subject Classification: Primary: 94B15; Secondary: 11T71.

Citation:

FullText(HTML)

Table 1. The parameters of codebooks asymptotically achieving Welch bound

Parameters $ (N,K) $	$ {I_{\max }} $	Constraints	Ref.
$ ({p^n},K = \frac{{p - 1}}{{2p}}({p^n} + {p^{\frac{n}{2}}}) + 1) $	$ \frac{{(p + 1){p^{\frac{n}{2}}}}}{{2pK}} $	$ p $ is an odd prime	[14]
$ ({q^2},\frac{{{{(q - 1)}^2}}}{2}) $	$ \frac{{q + 1}}{{{{(q - 1)}^2}}} $	$ q $ is an odd prime power	[40]
$ (q(q + 4),\frac{{(q + 3)(q + 1)}}{2}) $	$ \frac{1}{{q + 1}} $	$ q $ and $ q+4 $ are two prime powers	[18]
$ (q,\frac{{q - 1}}{2}) $	$ \frac{{\sqrt q + 1}}{{q - 1}} $	$ q $ is a prime power	[18]
$ ({q^l} + {q^{l - 1}} - 1,{q^{l - 1}}) $	$ \frac{1}{{\sqrt {{q^{l - 1}}} }} $	$ q $ is a prime power and $ l> 2 $	[42]
$ ({(q - 1)^k} + {q^{k - 1}},{q^{k - 1}}) $	$ \frac{{\sqrt {{q^{k + 1}}} }}{{{{(q - 1)}^k} + {{( - 1)}^{k + 1}}}} $	$ q \ge 4 $ is a prime power and $ k> 2 $	[12]
$ \begin{array}{l} ({(q - 1)^k} + K,K),\\K = \frac{{{{(q - 1)}^k} + {{( - 1)}^{k + 1}}}}{q}\end{array} $	$ \frac{{\sqrt {{q^{k - 1}}} }}{K} $	$ q $ is a prime power and $ k> 2 $	[12]
$ \begin{array}{l} ({({q^s} - 1)^n} + K,K),\\K = \frac{{{{({q^s} - 1)}^n} + {{( - 1)}^{n + 1}}}}{q}\end{array} $	$ \frac{{\sqrt {{q^{sn + 1}}} }}{{{{({q^s} - 1)}^n} + {{( - 1)}^{n + 1}}}} $	$ q $ is a prime power, $ s> 1,n> 1 $	[22]
$ ({({q^s} - 1)^n} + {q^{sn - 1}},{q^{sn - 1}}) $	$ \frac{{\sqrt {{q^{sn + 1}}} }}{{{{({q^s} - 1)}^n} + {{( - 1)}^{n + 1}}}} $	$ q $ is a prime power, $ s> 1,n> 1 $	[22]
$ ({q^3} + {q^2},{q^2}) $	$ \frac{1}{q} $	$ q $ is a prime power	[31]
$ ({q^3} + {q^2} - q,{q^2} - q) $	$ \frac{1}{{q - 1}} $	$ q $ is a prime power	[31]
$ ({q^3} - q,{q^2} - q) $	$ \frac{1}{{q - 1}} $	$ q $ is a prime power	[21]
$ ({q^3} - 2q + 1,{(q - 1)^2}) $	$ \frac{q}{{{{(q - 1)}^2}}} $	$ q $ is a prime power	[21]
$ (({p_{\min }} + 1){Q^2},{Q^2}) $	$ \frac{1}{Q} $	$ Q> 1 $ is an integer and $ {p_{\min }} $ is the smallest prime factor of $ Q $	[32]
$ (({p_{\min }} + 1){Q^2} - Q,Q(Q - 1)) $	$ \frac{1}{{Q - 1}} $	$ Q> 2 $ is an integer and $ {p_{\min }} $ is the smallest prime factor of $ Q $	[32]
$ ({N_1}{N_2},\frac{{{N_1}{N_2} - 1}}{2}) $	$ \frac{{\sqrt {({N_1} + 1)({N_2} + 1)} }}{{{N_1}{N_2} - 1}} $	$ {N_1} \equiv 3\bmod 4 $ and $ {N_2} \equiv 3\bmod 4 $	[15]
$ ({N_1} \cdots {N_l},\frac{{{N_1} \cdots {N_l} - 1}}{2}) $	$ \frac{{\sqrt {({N_1} + 1) \cdots ({N_l} + 1)} }}{{{N_1} \cdots {N_l} - 1}} $	$ {N_i} \equiv 3\bmod 4 $ for any $ l \ge 1 $	[15]
$ \begin{array}{l} (2K + 1,K),\\K = \frac{{{{({2^{{s_1}}} - 1)}^n}{{({2^{{s_2}}} - 1)}^n} - 1}}{2}\end{array} $	$ \frac{{{2^{\frac{{{s_1}n + {s_2}n}}{2}}}}}{{{{({2^{{s_1}}} - 1)}^n}{{({2^{{s_2}}} - 1)}^n} - 1}} $	$ n \ge 1,{s_1},{s_2}> 1 $	[23]
$ \begin{array}{l} (2K + {( - 1)^{mn}},K),\\K = \frac{{{{({2^{{s_1}}} - 1)}^n} \cdots {{({2^{{s_m}}} - {{( - 1)}^{mn}})}^n} - 1}}{2}\end{array} $	$ \frac{{{2^{\frac{{{s_1}n + {s_2}n + \cdots + {s_m}n}}{2}}}}}{{2K}} $	$ n \ge 1,l> 1 $ and $ {s_i}> 1 $ for any $ 1 \le i \le m $	[23]
$ (k{p^2} + {p^2},{p^2}) $	$ \frac{1}{p} $	$ p $ is a prime and $ k\|(p + 1) $	[24]
$ ({p^n} - 1,\frac{{{p^n} - 1}}{2}) $	$ \frac{{\sqrt {{p^n}} + 1}}{{{p^n} - 1}} $	$ p $ is an odd prime	[39]

| Show Table

DownLoad: CSV

Table 2. The parameters of codebooks asymptotically achieving Levenshtein bound

Parameters $ (N,K) $	$ {I_{\max }} $	Constraints	Ref.
$ ({2^{2m}} + {2^m},{2^m}) $	$ \frac{1}{{\sqrt {{2^{m - 1}}} }} $	$ m $ is a positive integer	[37]
$ ({q^2} - 1,q - 1) $	$ \frac{{\sqrt q }}{{q - 1}} $	$ q $ is a prime power	[29]
$ ({q^2} - q - 1,q - 2) $	$ \frac{{\sqrt q }}{{q - 2}} $	$ q $ is a prime power	[12]
$ ({q^2} + q - 1,q) $	$ \frac{1}{{\sqrt q }} $	$ q $ is a prime power	[42]

| Show Table

DownLoad: CSV

Table 3. The explicit parameter values of codebooks $ {\mathbb{\mathbb{C}}_3} $ in Theorem 3.6

$ q $	$ {N_3} $	$ {K_3} $	$ {I_{\max }}({\mathbb{C}_3}) $	$ {I_W} $	$ \frac{{{I_W}}}{{{I_{\max }}({\mathbb{C}_3})}} $
23	528	24	0.241492980	0.199620133	0.826608429
43	1848	44	0.171759966	0.148990467	0.867434190
61	3720	62	0.142100801	0.125954276	0.886372738
97	9408	98	0.110702631	0.100493097	0.907775146
125	15624	126	0.096669364	0.088729970	0.917870629
169	28560	170	0.082352941	0.076469234	0.928554986
343	117648	344	0.056744939	0.053837732	0.948767114

| Show Table

DownLoad: CSV

Table 4. The explicit parameter values of codebooks $ {\mathbb{\mathbb{C}}_4} $ in Theorem 3.8

$ p $	$ {N_4} $	$ {K_4} $	$ {I_{\max }}({\mathbb{C}_4}) $	$ {I_W} $	$ \frac{{{I_W}}}{{{I_{\max }}({\mathbb{C}_4})}} $
7	49	8	0.455718914	0.326758065	0.717016685
17	289	18	0.284616979	0.228639967	0.803325114
23	529	24	0.241492980	0.199597259	0.826513710
37	1369	38	0.186388488	0.160012599	0.858505805
61	3721	62	0.142100801	0.125954559	0.884263552
97	9409	98	0.110702631	0.100493153	0.907775652
157	24649	158	0.085632684	0.079301951	0.926071067
343	117649	344	0.056744939	0.053837733	0.948767131

| Show Table

DownLoad: CSV

Table 5. The parameters of codebooks asymptotically achieving Welch bound

$ (N,K) $	$ {I_{\max }} $	Constraints	References
$ ({q^2} - 1,q + 1) $	$ \frac{{1 + \sqrt q }}{{q + 1}} $	$ q $ is a prime power	Theorem 3.6
$ ({q^2} - 1,q) $	$ \frac{{\sqrt q }}{q} $	$ q $ is a prime power	codebooks $ {\mathbb{C}'_3} $
$ ({q^2} + q,q + 1) $	$ \frac{{1 + \sqrt q }}{{q + 1}} $	$ q $ is a prime power	codebooks $ {\mathbb{B}_3} $
$ ({p^2},p + 1) $	$ \frac{{1 + \sqrt p }}{{p + 1}} $	$ p $ is an odd prime	Theorem 3.8
$ ({p^2},p) $	$ \frac{{\sqrt p }}{p} $	$ p $ is an odd prime	codebooks $ {\mathbb{C}'_4} $
$ ({p^2} + p + 1,p + 1) $	$ \frac{{1 + \sqrt p }}{{p + 1}} $	$ p $ is an odd prime	codebooks $ {\mathbb{B}_4} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Bombieri, On exponential sums in finite fields, Am. J. Math., 88 (1966), 71-105. doi: 10.2307/2373048.
[2]	A. R. Calderbank, P. J. Cameron and W. M. Kantor et al., ${\mathbb{Z}_4}$-kerdock codes, orthogonal spreads, and extremal Euclidean line-sets, Proc. London Math. Soc., 75 (1997), 436-480. doi: 10.1112/S0024611597000403.
[3]	D. Chu, Polyphase codes with good periodic correlation properties, IEEE Trans. Inform. Theory, 18 (1972), 531-532. doi: 10.1109/TIT.1972.1054840.
[4]	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.
[5]	P. Delsarte, J. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometriae Dedicate, 6 (1977), 363-388. doi: 10.1007/bf03187604.
[6]	C. Ding, Complex codebooks from combinatorial designs, IEEE Trans. Inform. 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. Inform. Theory, 53 (2007), 4245-4250. doi: 10.1109/TIT.2007.907343.
[8]	C. Ding and J. Yin, Singal sets from functions with optimal nonlinearity, IEEE Trans. Commun., 55 (2007), 936-940. doi: 10.1109/TCOMM.2007.894113.
[9]	M. Fickus, D. G. Mixon and J. Jasper, Equiangular tight frames from hyperovals, IEEE Trans. Inform. Theory, 62 (2016), 5225-5236. doi: 10.1109/TIT.2016.2587865.
[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]	S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge Univ., Press, Cambridge, U.K., 2005. doi: 10.1017/CBO9780511546907.
[12]	Z. Heng, C. Ding and Q. Yue, New constructions of asymptotically optimal codebooks with multiplicative characters, IEEE Trans. Inform. Theory, 63 (2017), 6179-6187. doi: 10.1109/TIT.2017.2693204.
[13]	Z. Heng and Q. Yue, Optimal codebooks achieving the Levenshtein bound from generalized bent functions over ${\mathbb{Z}_4}$, Cryptogr. Commun., 9 (2017), 41-53. doi: 10.1007/s12095-016-0194-5.
[14]	S. Hong, H. Park, J.-S. No and T. Helleseth, et al., Near optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping, IEEE Trans. Inform. Theory, 60 (2014), 3698-3705. doi: 10.1109/TIT.2014.2314298.
[15]	H. Hu and J. Wu, New constructions of codebooks nearly meeting the Welch bound with equality, IEEE Trans. Inform. Theory, 60 (2014), 1348-1355. doi: 10.1109/TIT.2013.2292745.
[16]	N. M. Katz, An estimate for character sums, J. Am. Math. Soc., 2 (1989), 197-200. doi: 10.1090/S0894-0347-1989-0965007-8.
[17]	V. I. Levenshtein, Bounds for packing of metric spaces and some of their applications, Probl. Kibern., 40 (1983), 43-110.
[18]	C. Li, Q. Yue and Y. Huang, Two families of nearly optimal codebooks, Des. Codes Cryptogr., 75 (2015), 43-57. doi: 10.1007/s10623-013-9891-7.
[19]	S. Li and G. Ge, Deterministic sensing matrices arising from near orthogonal systems, IEEE Trans. Inform. Theory, 60 (2014), 2291-2302. doi: 10.1109/TIT.2014.2303973.
[20]	D. J. Love, R. W. Heath and T. Strohmer, Grassmannian beamforming for multiple input multiple output wireless systems, IEEE Trans. Inform. Theory, 49 (2003), 2735-2747. doi: 10.1109/TIT.2003.817466.
[21]	W. Lu, X. Wu and X. Cao, et al., Six constructions of asymptotically optimal codebooks via the character sums, Des. Codes Cryptogr., 88 (2020), 1139-1158. doi: 10.1007/s10623-020-00735-w.
[22]	G. Luo and X. Cao, Two constructions of asymptotically optimal codebooks via the hyper Eisenstein sum, IEEE Trans. Inform. Theory, 64 (2017), 6498-6505. doi: 10.1109/TIT.2017.2777492.
[23]	G. Luo and X. Cao, Two constructions of asymptotically optimal codebooks, Cryptogr. Commun., 11 (2019), 825-838. doi: 10.1007/s12095-018-0331-4.
[24]	G. Luo and X. Cao, New constructions of codebooks asymptotically achieving the Welch bound, in "IEEE Int. Symp. Inf. Theory", Vail, CO, USA, (2018), 2346–2350. doi: 10.1109/ISIT.2018.8437838.
[25]	J. L. Massey and T. Mittelholzer, Welch$^{\prime}$s bound and sequence sets for code division multiple access systems, in "Sequences II: Methods in Communication, Security and Computer Science", Springer, New York, (1993), 63–78.
[26]	L. Qian and X. Cao, Gaussian Sums, Hyper Eisenstein Sums and Jacobi Sums over a Local Ring and their Applications, Applicable Algebra in Engineering, Communication and Computing, 2021. doi: 10.1007/s00200-021-00491-x.
[27]	D. V. Sarwate, Meeting the Welch bound with equality, in "Proc. SETA$^{\prime}$98", Springer, London, (1999), 79–102.
[28]	T. Strohmer and R. W. Heath, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal., 14 (2003), 257-275. doi: 10.1016/S1063-5203(03)00023-X.
[29]	P. Tan, Z. Zhou and D. Zhang, A construction of codebooks nearly achieving the Levenstein bound, IEEE Signal Process. Lett., 23 (2016), 1306-1309. doi: 10.1109/LSP.2016.2595106.
[30]	V. Tarokh and I. M. Kim, Existence and construction of noncoherent unitary space-time codes, IEEE Trans. Inform. Theory, 48 (2002), 3112-3117. doi: 10.1109/TIT.2002.805075.
[31]	L. Tian, Y. Li and T. Liu, et al., Constructions of codebooks asymptotically achieving the Welch bound with additive characters, IEEE Signal Pro. Let., 26 (2019), 622-626. doi: 10.1109/LSP.2019.2891896.
[32]	Q. Wang and Y. Yan, Asymptotically optimal codebooks derived from generalised bent functions, IEEE Access, 8 (2020), 54905-54909. doi: 10.1109/ACCESS.2020.2980330.
[33]	X. Wang, J. Zhang and G. Ge, Deterministic convolutional compressed sensing matrices, Finite Fields App., 42 (2016), 102-117. doi: 10.1016/j.ffa.2016.07.002.
[34]	L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, 20 (1974), 397-399. doi: 10.1109/TIT.1974.1055219.
[35]	W. K. Wooters and B. D. Fields, Optimal state-determination by mutually unbiased measurements, Ann. Phys., 191 (1989), 363-381. doi: 10.1016/0003-4916(89)90322-9.
[36]	P. Xia, S. Zhou and G. B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory, 51 (2005), 1900-1907. doi: 10.1109/TIT.2005.846411.
[37]	C. Xiang, C. Ding and S. Mesnager, Optimal codebooks from binary codebooks meeting the Levenshtein bound, IEEE Trans. Inform. Theory, 61 (2015), 6526-6535. doi: 10.1109/TIT.2015.2487451.
[38]	G. Xu and Z. Xu, Compressed sensing matrices from Fourier matrices, IEEE Trans. Inform. Theory, 61 (2015), 469-478. doi: 10.1109/TIT.2014.2375259.
[39]	N. Y. Yu, A construction of codebooks associated with binary sequences, IEEE Trans. Inform. Theory, 58 (2012), 5522-5533. doi: 10.1109/TIT.2012.2196021.
[40]	A. Zhang and K. Feng, Two classes of codebooks nearly meeting the Welch bound, IEEE Trans. Inform. Theory, 58 (2012), 2507-2511. doi: 10.1109/TIT.2011.2176531.
[41]	Z. Zhou, C. Ding and N. Li, New families of codebooks achieving the Levenshtein bound, IEEE Trans. Inform. Theory, 60 (2014), 7382-7387. doi: 10.1109/TIT.2014.2353052.
[42]	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.