Title :
An algorithmic approach for finding deletion correcting codes
Author :
Khajouei, Farzaneh ; Zolghadr, Mahdy ; Kiyavash, Negar
Author_Institution :
Dept. of Ind. & Enterprise Syst. Eng., Univ. of Illinois at Urbana-Champaign, Urbana, IL, USA
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.
Keywords :
error correction codes; graph theory; polynomials; Levenshteins lower bound; concatenating codes; deletion-insertion-correcting codes; graph theory; heuristic algorithm; heuristic maximal independent set algorithm; polynomial; s-deletion code; Algorithm design and analysis; Complexity theory; Conferences; Decoding; Heuristic algorithms; Polynomials;
Conference_Titel :
Information Theory Workshop (ITW), 2011 IEEE
Conference_Location :
Paraty
Print_ISBN :
978-1-4577-0438-3
DOI :
10.1109/ITW.2011.6089432
