Name
Title | ||
|---|---|---|
A coloring approach to constructing deletion correcting codes from constant weight subgraphs |
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/ISIT.2012.6284242 | Information Theory Proceedings |
Keywords | Field | DocType |
Hamming codes,channel coding,error correction codes,graph theory,Hamming finding codes,Hamming weight codes,Hamming weight induced subgraphs,VT codes,asymptotically optimal,coloring approach,coloring sense,constant weight subgraphs,deletion channels,graph theoretic view,n-bit s-deletion correcting code,optimal coloring | Hamming code,Complete coloring,Discrete mathematics,Combinatorics,Hamming(7,4),Block code,Expander code,Hamming distance,Reed–Muller code,Linear code,Mathematics | Conference |
ISSN | ISBN | Citations |
2157-8095 E-ISBN : 978-1-4673-2578-3 | 978-1-4673-2578-3 | 8 |
PageRank | References | Authors |
0.84 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Cullina | 1 | 109 | 16.16 |
| Ankur A. Kulkarni | 2 | 106 | 20.95 |
| Negar Kiyavash | 3 | 673 | 63.55 |