An algorithmic approach for finding deletion correcting codes

Farzaneh Khajouei, Mahdy Zolghadr, Negar Kiyavash

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

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 languageEnglish (US)
Title of host publication2011 IEEE Information Theory Workshop, ITW 2011
Pages25-29
Number of pages5
DOIs
StatePublished - Dec 21 2011
Event2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil
Duration: Oct 16 2011Oct 20 2011

Publication series

Name2011 IEEE Information Theory Workshop, ITW 2011

Other

Other2011 IEEE Information Theory Workshop, ITW 2011
CountryBrazil
CityParaty
Period10/16/1110/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