{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/31180"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/31180","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions","abstract":"The construction of the largest codebook capable of correcting multiple number of deletions and insertions is an open problem in coding theory. The efforts in the design of these codes mostly concentrate on finding the largest codebook size for a fixed number of deletions and a codeword length. In fact, most of these codebooks are designed for a specific number of deletions as few as one or two. We are interested in finding the largest codebook that can correct multiple deletion and insertion errors. Previous research focused on block codes in dealing with deletion and insertion errors. The problem of constructing the largest codebook can be converted into an independent set problem in some specific graphs. The exact solution for the maximal independent set in these graphs is equivalent to finding the largest possible codebooks capable of correcting specific number of deletions and insertions. We propose a greedy algorithm which can find a maximal solution in polynomial time in the number of vertices of the graph. Results are presented for block codes of length n and the lower bounds are proved from analyzing the greedy algorithm on these graphs. A general construction for binary block codes, capable of correcting up to s number of deletion and insertion errors, is proposed. The construction is based on the concatenation of codes with shorter blocks. The algorithm will construct an s deletion and insertion correcting code based on a given s/2-deletion insertion correcting code. The size of the codebook grows exponentially and is comparable to asymptotic lower bound of Levenshtein. The greedy algorithm combined with the concatenation method can give codebooks of larger sizes.","abstract_html":"The construction of the largest codebook capable of correcting multiple number of deletions and insertions is an open problem in coding theory. The efforts in the design of these codes mostly concentrate on finding the largest codebook size for a fixed number of deletions and a codeword length. In fact, most of these codebooks are designed for a specific number of deletions as few as one or two. We are interested in finding the largest codebook that can correct multiple deletion and insertion errors. Previous research focused on block codes in dealing with deletion and insertion errors. The problem of constructing the largest codebook can be converted into an independent set problem in some specific graphs. The exact solution for the maximal independent set in these graphs is equivalent to finding the largest possible codebooks capable of correcting specific number of deletions and insertions. We propose a greedy algorithm which can find a maximal solution in polynomial time in the number of vertices of the graph. Results are presented for block codes of length n and the lower bounds are proved from analyzing the greedy algorithm on these graphs. A general construction for binary block codes, capable of correcting up to s number of deletion and insertion errors, is proposed. The construction is based on the concatenation of codes with shorter blocks. The algorithm will construct an s deletion and insertion correcting code based on a given s/2-deletion insertion correcting code. The size of the codebook grows exponentially and is comparable to asymptotic lower bound of Levenshtein. The greedy algorithm combined with the concatenation method can give codebooks of larger sizes.","abstract_has_math":false,"creators":["Khajouei, Farzaneh"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Kiyavash, Negar"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-05-22T00:33:49Z","date_published":"2012-05-22T00:33:49Z","updated_at":"2026-07-22T22:25:30Z","subjects":["Error Correcting Codes","Deletion and Insertion Correcting Codes","Coding theory","Concatenation of Codes, Levenshtein's bound"],"languages":["en"],"rights":["Copyright 2012 Farzaneh Khajouei"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/31180","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kiyavash, Negar"]},{"key":"dc:creator","label":"Author","values":["Khajouei, Farzaneh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-05-22T00:33:49Z","2012-05"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Error Correcting Codes","Deletion and Insertion Correcting Codes","Coding theory","Concatenation of Codes, Levenshtein's bound"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Farzaneh Khajouei"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/31180"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The construction of the largest codebook capable of correcting multiple number of deletions and insertions is an open problem in coding theory. The efforts in the design of these codes mostly concentrate on finding the largest codebook size for a fixed number of deletions and a codeword length. In fact, most of these codebooks are designed for a specific number of deletions as few as one or two. We are interested in finding the largest codebook that can correct multiple deletion and insertion errors. Previous research focused on block codes in dealing with deletion and insertion errors. The problem of constructing the largest codebook can be converted into an independent set problem in some specific graphs. The exact solution for the maximal independent set in these graphs is equivalent to finding the largest possible codebooks capable of correcting specific number of deletions and insertions. We propose a greedy algorithm which can find a maximal solution in polynomial time in the number of vertices of the graph. Results are presented for block codes of length n and the lower bounds are proved from analyzing the greedy algorithm on these graphs. A general construction for binary block codes, capable of correcting up to s number of deletion and insertion errors, is proposed. The construction is based on the concatenation of codes with shorter blocks. The algorithm will construct an s deletion and insertion correcting code based on a given s/2-deletion insertion correcting code. The size of the codebook grows exponentially and is comparable to asymptotic lower bound of Levenshtein. The greedy algorithm combined with the concatenation method can give codebooks of larger sizes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-04-27T18:08:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 16 Khajouei_Farzaneh.pdf: 575383 bytes, checksum: 21e7af5b1bfa49965a875f0bf02bbe61 (MD5) DLbib.bib: 8508 bytes, checksum: 69dc4985203281367fc8522745473476 (MD5) Related.tex: 18965 bytes, checksum: 394ba668d6927d23487bff3f99d2411a (MD5) LP.tex: 11358 bytes, checksum: f3f4ee2fb37c19a4547c26373df12421 (MD5) linearprob.tex: 14285 bytes, checksum: 095801835dac5616fc2d36ea6027cec5 (MD5) balanced.tex: 7970 bytes, checksum: cfce13108d758f7efb5b55bfdc244076 (MD5) ack.tex: 1423 bytes, checksum: 2362edf45d6ac36f1dd34c8a7ca12391 (MD5) conclusion.tex: 1881 bytes, checksum: 256262fd209385de60fdb331b34196f2 (MD5) complexity.tex: 1666 bytes, checksum: b6b43a404f77055132d65ad4e11900c7 (MD5) app_numerical.tex: 3905 bytes, checksum: 5504b2c4c961af07ef1455d2e9426f6d (MD5) introduction.tex: 5532 bytes, checksum: a9684724193ff18eecbd2c50e9e348cd (MD5) degreeL1.tex: 18688 bytes, checksum: 8fa75f538f97ac8a7d4b2d06739b587b (MD5) concatenation.tex: 40418 bytes, checksum: c11b8a9bcb180248c95f57015b5c499d (MD5) abstract.log: 2168 bytes, checksum: f93169bea937798442ee73d93da7b884 (MD5) Khajouei_Farzaneh.tex: 3967 bytes, checksum: 6141c60cddc95494ac9a564603d93c40 (MD5) Khajouei_Farzaneh.pdf: 581766 bytes, checksum: 09c06781e72b170f6dcd3c46d018633d (MD5)","Made available in DSpace on 2012-05-22T00:33:49Z (GMT). No. of bitstreams: 16 Khajouei_Farzaneh.pdf: 581760 bytes, checksum: 98e049b5dd42673350080a91f93c0083 (MD5) DLbib.bib: 8508 bytes, checksum: 69dc4985203281367fc8522745473476 (MD5) Related.tex: 18965 bytes, checksum: 394ba668d6927d23487bff3f99d2411a (MD5) LP.tex: 11358 bytes, checksum: f3f4ee2fb37c19a4547c26373df12421 (MD5) linearprob.tex: 14285 bytes, checksum: 095801835dac5616fc2d36ea6027cec5 (MD5) balanced.tex: 7970 bytes, checksum: cfce13108d758f7efb5b55bfdc244076 (MD5) ack.tex: 1423 bytes, checksum: 2362edf45d6ac36f1dd34c8a7ca12391 (MD5) conclusion.tex: 1881 bytes, checksum: 256262fd209385de60fdb331b34196f2 (MD5) complexity.tex: 1666 bytes, checksum: b6b43a404f77055132d65ad4e11900c7 (MD5) app_numerical.tex: 3905 bytes, checksum: 5504b2c4c961af07ef1455d2e9426f6d (MD5) introduction.tex: 5532 bytes, checksum: a9684724193ff18eecbd2c50e9e348cd (MD5) degreeL1.tex: 18688 bytes, checksum: 8fa75f538f97ac8a7d4b2d06739b587b (MD5) concatenation.tex: 40418 bytes, checksum: c11b8a9bcb180248c95f57015b5c499d (MD5) abstract.log: 2168 bytes, checksum: f93169bea937798442ee73d93da7b884 (MD5) Khajouei_Farzaneh.tex: 3967 bytes, checksum: 6141c60cddc95494ac9a564603d93c40 (MD5) license.txt: 4067 bytes, checksum: f3c587941dba06e7540afaad6fd097ac (MD5)"]},{"key":"dc:title","label":"Title","values":["A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions"]}]}],"canonical_facts":{"dc:contributor":["Kiyavash, Negar"],"dc:creator":["Khajouei, Farzaneh"],"dc:date":["2012-05-22T00:33:49Z","2012-05"],"dc:description":["The construction of the largest codebook capable of correcting multiple number of deletions and insertions is an open problem in coding theory. The efforts in the design of these codes mostly concentrate on finding the largest codebook size for a fixed number of deletions and a codeword length. In fact, most of these codebooks are designed for a specific number of deletions as few as one or two. We are interested in finding the largest codebook that can correct multiple deletion and insertion errors. Previous research focused on block codes in dealing with deletion and insertion errors. The problem of constructing the largest codebook can be converted into an independent set problem in some specific graphs. The exact solution for the maximal independent set in these graphs is equivalent to finding the largest possible codebooks capable of correcting specific number of deletions and insertions. We propose a greedy algorithm which can find a maximal solution in polynomial time in the number of vertices of the graph. Results are presented for block codes of length n and the lower bounds are proved from analyzing the greedy algorithm on these graphs. A general construction for binary block codes, capable of correcting up to s number of deletion and insertion errors, is proposed. The construction is based on the concatenation of codes with shorter blocks. The algorithm will construct an s deletion and insertion correcting code based on a given s/2-deletion insertion correcting code. The size of the codebook grows exponentially and is comparable to asymptotic lower bound of Levenshtein. The greedy algorithm combined with the concatenation method can give codebooks of larger sizes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-04-27T18:08:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 16 Khajouei_Farzaneh.pdf: 575383 bytes, checksum: 21e7af5b1bfa49965a875f0bf02bbe61 (MD5) DLbib.bib: 8508 bytes, checksum: 69dc4985203281367fc8522745473476 (MD5) Related.tex: 18965 bytes, checksum: 394ba668d6927d23487bff3f99d2411a (MD5) LP.tex: 11358 bytes, checksum: f3f4ee2fb37c19a4547c26373df12421 (MD5) linearprob.tex: 14285 bytes, checksum: 095801835dac5616fc2d36ea6027cec5 (MD5) balanced.tex: 7970 bytes, checksum: cfce13108d758f7efb5b55bfdc244076 (MD5) ack.tex: 1423 bytes, checksum: 2362edf45d6ac36f1dd34c8a7ca12391 (MD5) conclusion.tex: 1881 bytes, checksum: 256262fd209385de60fdb331b34196f2 (MD5) complexity.tex: 1666 bytes, checksum: b6b43a404f77055132d65ad4e11900c7 (MD5) app_numerical.tex: 3905 bytes, checksum: 5504b2c4c961af07ef1455d2e9426f6d (MD5) introduction.tex: 5532 bytes, checksum: a9684724193ff18eecbd2c50e9e348cd (MD5) degreeL1.tex: 18688 bytes, checksum: 8fa75f538f97ac8a7d4b2d06739b587b (MD5) concatenation.tex: 40418 bytes, checksum: c11b8a9bcb180248c95f57015b5c499d (MD5) abstract.log: 2168 bytes, checksum: f93169bea937798442ee73d93da7b884 (MD5) Khajouei_Farzaneh.tex: 3967 bytes, checksum: 6141c60cddc95494ac9a564603d93c40 (MD5) Khajouei_Farzaneh.pdf: 581766 bytes, checksum: 09c06781e72b170f6dcd3c46d018633d (MD5)","Made available in DSpace on 2012-05-22T00:33:49Z (GMT). No. of bitstreams: 16 Khajouei_Farzaneh.pdf: 581760 bytes, checksum: 98e049b5dd42673350080a91f93c0083 (MD5) DLbib.bib: 8508 bytes, checksum: 69dc4985203281367fc8522745473476 (MD5) Related.tex: 18965 bytes, checksum: 394ba668d6927d23487bff3f99d2411a (MD5) LP.tex: 11358 bytes, checksum: f3f4ee2fb37c19a4547c26373df12421 (MD5) linearprob.tex: 14285 bytes, checksum: 095801835dac5616fc2d36ea6027cec5 (MD5) balanced.tex: 7970 bytes, checksum: cfce13108d758f7efb5b55bfdc244076 (MD5) ack.tex: 1423 bytes, checksum: 2362edf45d6ac36f1dd34c8a7ca12391 (MD5) conclusion.tex: 1881 bytes, checksum: 256262fd209385de60fdb331b34196f2 (MD5) complexity.tex: 1666 bytes, checksum: b6b43a404f77055132d65ad4e11900c7 (MD5) app_numerical.tex: 3905 bytes, checksum: 5504b2c4c961af07ef1455d2e9426f6d (MD5) introduction.tex: 5532 bytes, checksum: a9684724193ff18eecbd2c50e9e348cd (MD5) degreeL1.tex: 18688 bytes, checksum: 8fa75f538f97ac8a7d4b2d06739b587b (MD5) concatenation.tex: 40418 bytes, checksum: c11b8a9bcb180248c95f57015b5c499d (MD5) abstract.log: 2168 bytes, checksum: f93169bea937798442ee73d93da7b884 (MD5) Khajouei_Farzaneh.tex: 3967 bytes, checksum: 6141c60cddc95494ac9a564603d93c40 (MD5) license.txt: 4067 bytes, checksum: f3c587941dba06e7540afaad6fd097ac (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/31180"],"dc:language":["en"],"dc:rights":["Copyright 2012 Farzaneh Khajouei"],"dc:subject":["Error Correcting Codes","Deletion and Insertion Correcting Codes","Coding theory","Concatenation of Codes, Levenshtein's bound"],"dc:title":["A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:30Z"}