DIMACS TR: 98-41
Strengthening the Varshamov-Gilbert Bound
Authors: Alexander Barg, Sugi Guritman, Juriaan Simonis
The paper discusses some ways to strengthen (nonasymptotically)
the Gilbert-Varshamov bound for linear codes.
The unifying idea is to study a certain graph constructed on vectors
of low weight in the cosets of the code, which we call the
Varshamov graph. Various simple estimates of the number of its connected
components account for better lower bounds on the minimum distance
of codes, some of them known in the literature.
Paper Available at:
DIMACS Home Page