TY - GEN
T1 - An algorithmic approach for finding deletion correcting codes
AU - Khajouei, Farzaneh
AU - Zolghadr, Mahdy
AU - Kiyavash, Negar
PY - 2011/12/21
Y1 - 2011/12/21
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=83655193057&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=83655193057&partnerID=8YFLogxK
U2 - 10.1109/ITW.2011.6089432
DO - 10.1109/ITW.2011.6089432
M3 - Conference contribution
AN - SCOPUS:83655193057
SN - 9781457704376
T3 - 2011 IEEE Information Theory Workshop, ITW 2011
SP - 25
EP - 29
BT - 2011 IEEE Information Theory Workshop, ITW 2011
T2 - 2011 IEEE Information Theory Workshop, ITW 2011
Y2 - 16 October 2011 through 20 October 2011
ER -