On the Maximum Size of Block Codes Subject to a Distance Criterion

Ling Hua Chang, Po-Ning Chen, Vincent Y.F. Tan, Carol Wang, Yunghsiang S. Han

Research output: Contribution to journalArticlepeer-review

Abstract

We establish a general formula for the maximum size of finite length block codes with minimum pairwise distance no less than d. The achievability argument involves an iterative construction of a set of radius- d balls, each centered at a codeword. We demonstrate that the number of such balls that cover the entire code space cannot exceed this maximum size. Our approach can be applied to codes i ) with elements over arbitrary code alphabets, and ii ) under a broad class of distance measures. Our formula indicates that the maximum code size can be fully characterized by the cumulative distribution function of the distance measure evaluated at two independent and identically distributed random codewords. When the two random codewords assume a uniform distribution over the entire code alphabet, our formula recovers and thus naturally generalizes the Gilbert-Varshamov (GV) lower bound. Finally, we extend our study to the asymptotic setting.

Original languageEnglish
Article number8586900
Pages (from-to)3751-3757
Number of pages7
JournalIEEE Transactions on Information Theory
Volume65
Issue number6
DOIs
StatePublished - 1 Jun 2019

Keywords

  • Coding theory
  • block codes
  • graph theory
  • minimum distance

Fingerprint Dive into the research topics of 'On the Maximum Size of Block Codes Subject to a Distance Criterion'. Together they form a unique fingerprint.

Cite this