Improving the Gilbert-Varshamov Bound by Graph Spectral Method

Abstract

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph G_q,n,d is a graph with all vectors in ${\mathbb{F}}_{q}^{n}$ as vertices where two vertices are adjacent if their Hamming distance is less than d. In this paper, we calculate the eigenvalues and eigenvectors of G_q,n,d using the properties of Cayley graph. The improved bound is associated with the minimum eigenvalue of the graph. Finally we give an algorithm to calculate the bound and linear codes which satisfy the bound.

Keywords

Gilbert-Varshamov bound / independence number / graph spectral method / Cayley graph / linear codes

References

[1] T.M. Apostol, Introduction to Analytic Number Theory, Springer Science & Business Media, 2013.

[2] A. Barg, S. Guritman, and J. Simonis, Strengthening the Gilbert-Varshamov bound. Linear algebra and its applications, 307(1-3):119-129, 2000.

[3] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer Science & Business Media, 2011.

[4] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Suppl., vi+-97, 1973.

[5] M. Elia, Some results on the existence of binary linear codes (Corresp.), IEEE Trans. Inf. Theory, 29(6):933-934, 1983.

[6] E.N. Gilbert, A comparison of signalling alphabets, Bell Syst. Tech. J., 31(3):504-522, 1952.

[7] C. Godsil and G.F. Royle, Algebraic Graph Theory, Vol. 207, Springer Science & Business Media, 2013.

[8] J. Hao, H. Huang, G. Livshyts, and K. Tikhomirov, Distribution of the minimum distance of random linear codes, in: 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 114-119, 2020.

[9] T. Jiang and A. Vardy, Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes, IEEE Trans. Inf. Theory, 50(8):1655-1664, 2004.

[10] V.I. Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inf. Theory, 41(5):1303-1321, 1995.

[11] K.M. O'Brien and P. Bounds on codes derived by counting components in Varshamov graphs, Des. Codes Cryptogr., 39(3):387-396, 2006.

[12] S.El. Rouayheb and C.N. Georghiades, Graph theoretic methods in coding theory, in: Classical, Semi-Classical and Quantum Noise, Springer, 53-62, 2012.

[13] N.J.A. Sloane, Unsolved problems in graph theory arising from the study of codes, Graph theory notes N. Y., 18:11-20, 1989.

[14] A. Trachtenberg, Designing lexicographic codes with a given trellis complexity, IEEE Trans. Inf. Theory, 48(1):89-100, 2002.

[15] M.A. Tsfasman, S.G. Vlădutx, and Th. Zink, Modular curves, shimura curves, and goppa codes, better than Varshamov-Gilbert bound, Mathematische Nachrichten, 109(1):21-28, 1982.

[16] R.R. Varshamov, Estimate of the number of signals in error correcting codes, Docklady Akad. Nauk, SSSR, 117:739-741, 1957.

[17] H.S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Comb. Theory. Ser. B, 40(1):113-117, 1986.