A coloring approach to constructing deletion correcting codes from constant weight subgraphs

Daniel Cullina, Ankur A. Kulkarni, Negar Kiyavash

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We take a graph theoretic view of deletion correcting codes. The problem of finding an n-bit s-deletion correcting code is equivalent to finding an independent set in a particular graph. We discuss the relationship between codes and colorings and demonstrate that the VT codes are optimal in a coloring sense. We describe a method of partitioning the set of bit strings by Hamming weight and finding codes within each partition. In the single deletion case, we find an optimal coloring of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We also prove a lower bound on size of codes constructed using these partitions for any number of deletions.

Original languageEnglish (US)
Title of host publication2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
Pages513-517
Number of pages5
DOIs
StatePublished - 2012
Event2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States
Duration: Jul 1 2012Jul 6 2012

Other

Other2012 IEEE International Symposium on Information Theory, ISIT 2012
CountryUnited States
CityCambridge, MA
Period7/1/127/6/12

ASJC Scopus subject areas

  • Applied Mathematics
  • Modeling and Simulation
  • Theoretical Computer Science
  • Information Systems

Fingerprint Dive into the research topics of 'A coloring approach to constructing deletion correcting codes from constant weight subgraphs'. Together they form a unique fingerprint.

Cite this