\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • *Corresponding author: Gang Wang

    *Corresponding author: Gang Wang 

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
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [1] E. Bombieri, On exponential sums in finite fields, Am. J. Math., 88 (1966), 71-105.  doi: 10.2307/2373048.
    [2] A. R. CalderbankP. 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. ConwayR. H. Harding and N. J. A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Exp. Math., 5 (1996), 139-159. 
    [5] P. DelsarteJ. 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. FickusD. 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. 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] S. W. Golomb and  G. GongSignal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge Univ., Press, Cambridge, U.K., 2005.  doi: 10.1017/CBO9780511546907.
    [12] Z. HengC. 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. HongH. ParkJ.-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. LiQ. 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. LoveR. 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. LuX. 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. TanZ. 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. TianY. 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. WangJ. 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. XiaS. 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. XiangC. 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. ZhouC. 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.
  • 加载中

Tables(5)

SHARE

Article Metrics

HTML views(3056) PDF downloads(582) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return