Strengthening the Gilbert-Varshamov bound
type: Item
instance of: scholarly article
title: Strengthening the Gilbert-Varshamov bound
zbMATH Open document ID: 0996.94040
DOI: 10.1016/S0024-3795(99)00271-2
author: Alexander Barg
author: Sugi Guritman
author: Juriaan Simonis
published in: Linear Algebra and its Applications
publication date: 2002-11-04T00:00:00Z
review text: It is well known to be an extremely difficult problem to improve the Varshamov-Gilbert bound asymptotically. This paper describes some ideas for strengthening the Gilbert-Varshamov bound for linear codes in the non-asymptotic case. The idea is to construct a certain graph constructed on vectors of low weight in the cosets of the code \(C\). The graph is defined as the following undirected graph: The vertex set \(V\) consists of all \(n\)-dimensional vectors with components from GF\((q)\) having Hamming weight at most \(\alpha\). Two vertices are joined by an edge if and only if their difference is a nonzero code word in the code \(C\). The number of edges in the graph turns out to be a function of the weight distribution of the code. Simple estimates of the number of connected components in the graph (in the case \(\alpha= d-2)\) lead to better lower bounds for the minimum distance of linear codes. The paper presents an interesting unifying approach to non-asymptotic improvements of the Varshamov-Gilbert bound. The paper also includes new proofs and improvements of previously known results in the literature.
reviewed by: Tor Helleseth
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 1441335
zbMATH Keywords: Gilbert-Varshamov bound
zbMATH Keywords: linear codes
zbMATH Keywords: weight distribution
zbMATH Keywords: lower bounds
zbMATH Keywords: minimum distance of linear codes
zbMATH Keywords: non-asymptotic improvements
describes a project that uses: Code Tables
MaRDI profile type: Publication
cites work: Q3688305
cites work: Q4242011
cites work: Q5707657
cites work: Q4332871
cites work: Some results on the existence of binary linear codes (Corresp.)
cites work: Q4002255
cites work: Q4146667
cites work: Q3997777
cites work: Q3250141
full work available at URL: s0024-3795(99)00271-2
OpenAlex ID: W2087737172
description: scientific article; zbMATH DE number 1441335