Generalized sphere-packing bounds on the size of codes for combinatorial channels

Daniel Cullina, Negar Kiyavash

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Many of the classic problems of the coding theory are highly symmetric, which makes it easy to derive the sphere-packing upper bounds on the size of codes. We discuss the generalizations of the sphere-packing bounds to the arbitrary error models. These generalizations become especially important when the sizes of the error spheres are nonuniform. The best possible sphere-packing bounds are the solutions to the linear programs. We derive a series of bounds from the approximations to the packing and covering problems and study the relationships and the trade-offs between them. We show the method to obtain the upper bounds by optimizing across a family of channels that admit the same codes. We present a generalization of the local degree bound of Kulkarni and Kiyavash, and use it to improve the best-known upper bounds on the sizes of the single deletion correcting codes and the single grain error correcting codes.

Original languageEnglish (US)
Article number7467537
Pages (from-to)4454-4465
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Generalized sphere-packing bounds on the size of codes for combinatorial channels'. Together they form a unique fingerprint.

Cite this