Improving the Gilbert-Varshamov Bound by Graph Spectral Method

被引：0

作者：

Ye, Zicheng ^{[1
,2
]}

Zhang, Huazi ^{[3
]}

Li, Rong ^{[3
]}

Wang, Jun ^{[3
]}

Yan, Guiying ^{[1
,2
]}

Ma, Zhiming ^{[1
,2
]}

机构：

[1] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

[2] Univ Chinese Acad Sci, Beijing 100049, Peoples R China

[3] Hangzhou Res Ctr Huawei Technol Co Ltd, Hangzhou 310052, Zhejiang, Peoples R China

来源：

CSIAM TRANSACTIONS ON APPLIED MATHEMATICS | 2023年 / 4卷 / 01期

关键词：

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

D O I：

10.4208/csiam-am.SO-2021-0024

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph G(q,n,d) is a graph with all vectors in 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.

引用

页码：1 / 12

页数：12

共 35 条

[1] Lengthening and the Gilbert-Varshamov bound
Edel, Y
Bierbrauer, J
IEEE TRANSACTIONS ON INFORMATION THEORY, 1997, 43 (03) : 991 - 992
[2] Improving the Gilbert-Varshamov bound for q-ary codes
Vu, V
Wu, L
IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (09) : 3200 - 3208
[3] Evaluating the Gilbert-Varshamov Bound for Constrained Systems
Goyal, Keshav
Kiah, Han Mao
ENTROPY, 2024, 26 (04)
[4] IMPROVED GILBERT-VARSHAMOV BOUND FOR CONSTRAINED SYSTEMS
MARCUS, BH
ROTH, RM
IEEE TRANSACTIONS ON INFORMATION THEORY, 1992, 38 (04) : 1213 - 1221
[5] An Improvement on the Gilbert-Varshamov Bound for Permutation Codes
Gao, Fei
Yang, Yiting
Ge, Gennian
IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (05) : 3059 - 3063
[6] Asymptotic improvement of the Gilbert-Varshamov bound for binary linear codes
Gaborit, Philippe
Zemor, Gilles
2006 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1-6, PROCEEDINGS, 2006, : 287 - +
[7] An Improvement of the Gilbert-Varshamov Bound Over Nonprime Fields
Bassa, Alp
Beelen, Peter
Garcia, Arnaldo
Stichtenoth, Henning
IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (07) : 3859 - 3861
[8] The Gilbert-Varshamov Bound for Stabilizer Codes Over Zm
Tang, Nianqi
Li, Zhuo
Xing, Lijuan
Zhang, Ming
IEEE ACCESS, 2018, 6 : 45699 - 45706
[9] Subquadratic Time Encodable Codes Beating the Gilbert-Varshamov Bound
Narayanan, Anand Kumar
Weidnet, Matthew
IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (10) : 6010 - 6021
[10] More Goppa Geometric Codes Achieving the Gilbert-Varshamov Bound
Zhang, Ying
Yue, Dian-Wu
2008 4TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-31, 2008, : 1526 - 1530

← 1 2 3 4 →