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 language | English (US) |
|---|---|
| Title of host publication | 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012 |
| Pages | 513-517 |
| Number of pages | 5 |
| DOIs | |
| State | Published - 2012 |
| Event | 2012 IEEE International Symposium on Information Theory, ISIT 2012 - Cambridge, MA, United States Duration: Jul 1 2012 → Jul 6 2012 |
Other
| Other | 2012 IEEE International Symposium on Information Theory, ISIT 2012 |
|---|---|
| Country/Territory | United States |
| City | Cambridge, MA |
| Period | 7/1/12 → 7/6/12 |
ASJC Scopus subject areas
- Applied Mathematics
- Modeling and Simulation
- Theoretical Computer Science
- Information Systems