Abstract
A general construction for deletion/insertion correcting codes is proposed by concatenating codes derived from a heuristic maximal independent set algorithm on an appropriately defined graph. Our heuristic algorithm is polynomial with respect to the number of nodes in the graph. This methodology may be used for construction of any length n, s-deletion code. Our experimental results show that cardinalities of our codebooks exceed sizes of all previously known constructions. In fact, they are comparable to Levenshteins lower bound.
| Original language | English (US) |
|---|---|
| Title of host publication | 2011 IEEE Information Theory Workshop, ITW 2011 |
| Pages | 25-29 |
| Number of pages | 5 |
| DOIs | |
| State | Published - Dec 21 2011 |
| Event | 2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil Duration: Oct 16 2011 → Oct 20 2011 |
Publication series
| Name | 2011 IEEE Information Theory Workshop, ITW 2011 |
|---|
Other
| Other | 2011 IEEE Information Theory Workshop, ITW 2011 |
|---|---|
| Country | Brazil |
| City | Paraty |
| Period | 10/16/11 → 10/20/11 |
ASJC Scopus subject areas
- Information Systems
Fingerprint Dive into the research topics of 'An algorithmic approach for finding deletion correcting codes'. Together they form a unique fingerprint.
Cite this
Khajouei, F., Zolghadr, M., & Kiyavash, N. (2011). An algorithmic approach for finding deletion correcting codes. In 2011 IEEE Information Theory Workshop, ITW 2011 (pp. 25-29). [6089432] (2011 IEEE Information Theory Workshop, ITW 2011). https://doi.org/10.1109/ITW.2011.6089432