A Generalized Gilbert-Varshamov Bound Derived via Analysis of a Code-Search Algorithm

Abstract

This correspondence derives a generalization of the Gilbert- Varshamov bound that is applicable to block codes whose codewords must be drawn from irregular sets; the bound improves by a factor of four a similar result recently published by Kolesnik and Krachkovsky. It is derived by analyzing a code search algorithm we refer to as the "Altruistic Algorithm". This algorithm iteratively deletes potential codewords so that at each iteration the "worst" candidate is removed; the bound is derived by demonstrating that, as the algorithm proceeds, the average volume of a sphere of a given radius approaches the maximum such volume and so a bound previously expressed in terms of the maximum volume can in fact be expressed in terms of the average volume. Examples of applications where the bound is relevant include error-correcting (d, k)- constrained codes and binary codes for code division multiple access.