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

共 38 条

[21] Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically [J].

Fan, Jihao ;

Li, Jun ;

Wang, Ya ;

Li, Yonghui ;

Hsieh, Min-Hsiu ;

Du, Jiangfeng .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (01) :262-272

[22] Towers of global function fields with asymptotically many rational places and an improvement on the Gilbert-Varshamov bound [J].

Niederreiter, H ;

Xing, CP .

MATHEMATISCHE NACHRICHTEN, 1998, 195 :171-186

[23] Gilbert-Varshamov Bound for Codes in L1 Metric Using Multivariate Analytic Combinatorics [J].

Goyal, Keshav ;

Dao, Duc Tu ;

Kovacevic, Mladen ;

Kiah, Han Mao .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2025, 71 (01) :244-262

[24] Improved Gilbert-Varshamov Bound for Entanglement-Assisted Asymmetric Quantum Error Correction by Symplectic Orthogonality [J].

Matsumoto, Ryutaroh .

IEEE TRANSACTIONS ON QUANTUM ENGINEERING, 2020, 1

[25] A modified Gilbert-Varshamov bound for self-dual quasi-twisted codes of index four [J].

Wu, Rongsheng ;

Shi, Minjia .

FINITE FIELDS AND THEIR APPLICATIONS, 2020, 62

[26] Nonlinear codes with asymptotic parameters better than the Gilbert-Varshamov and the Xing bounds [J].

Hu Wanbao .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2006, 49 (06) :852-864

[27] Generalized Random Gilbert-Varshamov Codes: Typical Error Exponent and Concentration Properties [J].

Truong, Lan V. ;

Fabregas, Albert .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2024, 70 (02) :820-853

[28] Nonlinear codes with asymptotic parameters better than the Gilbert-Varshamov and the Xing Bounds [J].

HU Wanbao Department of Mathematics Anqing Teachers College Anqing China ;

National Mobile communications Research Southest University Nanjing China .

ScienceinChina(SeriesA:Mathematics), 2006, (06) :852-864

[29] Nonlinear codes with asymptotic parameters better than the Gilbert-Varshamov and the Xing Bounds [J].

Wanbao Hu .

Science in China Series A, 2006, 49 :852-864

[30] INFORMATION COMPRESSION AND VARSHAMOV-GILBERT BOUND [J].

KRICHEVSKY, RE .

INFORMATION AND COMPUTATION, 1987, 74 (01) :1-14

← 1 2 3 4 →