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

Loading...
Thumbnail Image

Files

TR_92-87.pdf (573.49 KB)
No. of downloads: 723

Publication or External Link

Date

1992

Advisor

Citation

DRUM DOI

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.

Notes

Rights