A GENERALIZED GILBERT-VARSHAMOV BOUND DERIVED VIA ANALYSIS OF A CODE-SEARCH ALGORITHM

A generalization of the Gilbert-Varshamov bound that is applicable to block codes whose codewords must be drawn from irregular sets is deriv ed; the bound improves by a factor of four a similar result recently p ublished by Kolesnik and Krachkovsky. It is derived by analyzing a cod e search algorithm we refer to as the ''Altruistic Algorithm.'' This a lgorithm iteratively deletes potential codewords so that at each itera tion the ''worst'' candidate is removed; the bound is derived by demon strating that, as the algorithm proceeds, the average volume of a sphe re 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 ex pressed in terms of the average volume. Examples of applications where the bound is relevant include error-correcting (d, k)-constrained cod es and binary codes for code division multiple access.