{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72914"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72914","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Constant composition deletion correcting codes","abstract":"We investigate deletion correcting codes and constant composition codes in particular. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a suprising property: for any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account: for any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of constant composition codes. We use a different technique to prove an upper bound. We construct binary constant composition single deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of constant composition codes as long as the set of compositions used themselves form a code. The nonbinary single deletion codes constructed by Tenengolts are a special case of this method. We show that there is a qualitative difference between the problem of correcting a single deletion and the problem of correcting multiple deletions. In the single deletion case, the Varshamov Tenengolts codes are an optimal coloring of the confusion graph and each individual color class is asymptotically optimal. By constructing large cliques in the multiple deletion confusion graphs, we show that no construction can have both of the properties.","abstract_html":"We investigate deletion correcting codes and constant composition codes in particular. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a suprising property: for any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account: for any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of constant composition codes. We use a different technique to prove an upper bound. We construct binary constant composition single deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of constant composition codes as long as the set of compositions used themselves form a code. The nonbinary single deletion codes constructed by Tenengolts are a special case of this method. We show that there is a qualitative difference between the problem of correcting a single deletion and the problem of correcting multiple deletions. In the single deletion case, the Varshamov Tenengolts codes are an optimal coloring of the confusion graph and each individual color class is asymptotically optimal. By constructing large cliques in the multiple deletion confusion graphs, we show that no construction can have both of the properties.","abstract_has_math":false,"creators":["Cullina, Daniel"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Kiyavash, Negar"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-21T19:49:27Z","date_published":"2015-01-21T19:49:27Z","updated_at":"2026-07-22T22:26:07Z","subjects":["coding theory","error correction","deletion channel","combinatorics"],"languages":["en"],"rights":["Copyright 2014 Daniel Cullina"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/72914","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":["Cullina, Daniel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-21T19:49:27Z","2014-12","2015-01-21"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["coding theory","error correction","deletion channel","combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Daniel Cullina"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72914"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We investigate deletion correcting codes and constant composition codes in particular. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a suprising property: for any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account: for any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of constant composition codes. We use a different technique to prove an upper bound. We construct binary constant composition single deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of constant composition codes as long as the set of compositions used themselves form a code. The nonbinary single deletion codes constructed by Tenengolts are a special case of this method. We show that there is a qualitative difference between the problem of correcting a single deletion and the problem of correcting multiple deletions. In the single deletion case, the Varshamov Tenengolts codes are an optimal coloring of the confusion graph and each individual color class is asymptotically optimal. By constructing large cliques in the multiple deletion confusion graphs, we show that no construction can have both of the properties.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-11-17T16:42:47Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 5 thesis-body.tex: 85701 bytes, checksum: 943d5ca241503469ec62771f75a17d12 (MD5) thesis.tex: 5007 bytes, checksum: 18cc76557dbb03bef58d011366d40c27 (MD5) def.tex: 1933 bytes, checksum: fcdfee1bd37b4f2400ee10c5e1b91726 (MD5) abstract.tex: 1707 bytes, checksum: f32b1f77a55103e5eebc190e5b0ac3eb (MD5) Cullina_Daniel.pdf: 364645 bytes, checksum: d7b125abe8403ef05d2c75c638e4774a (MD5)","Made available in DSpace on 2015-01-21T19:49:27Z (GMT). No. of bitstreams: 5 Daniel_Cullina.pdf: 364645 bytes, checksum: d7b125abe8403ef05d2c75c638e4774a (MD5) thesis-body.tex: 85701 bytes, checksum: 943d5ca241503469ec62771f75a17d12 (MD5) thesis.tex: 5007 bytes, checksum: 18cc76557dbb03bef58d011366d40c27 (MD5) def.tex: 1933 bytes, checksum: fcdfee1bd37b4f2400ee10c5e1b91726 (MD5) abstract.tex: 1707 bytes, checksum: f32b1f77a55103e5eebc190e5b0ac3eb (MD5)"]},{"key":"dc:title","label":"Title","values":["Constant composition deletion correcting codes"]}]}],"canonical_facts":{"dc:contributor":["Kiyavash, Negar"],"dc:creator":["Cullina, Daniel"],"dc:date":["2015-01-21T19:49:27Z","2014-12","2015-01-21"],"dc:description":["We investigate deletion correcting codes and constant composition codes in particular. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a suprising property: for any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account: for any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of constant composition codes. We use a different technique to prove an upper bound. We construct binary constant composition single deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of constant composition codes as long as the set of compositions used themselves form a code. The nonbinary single deletion codes constructed by Tenengolts are a special case of this method. We show that there is a qualitative difference between the problem of correcting a single deletion and the problem of correcting multiple deletions. In the single deletion case, the Varshamov Tenengolts codes are an optimal coloring of the confusion graph and each individual color class is asymptotically optimal. By constructing large cliques in the multiple deletion confusion graphs, we show that no construction can have both of the properties.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-11-17T16:42:47Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 5 thesis-body.tex: 85701 bytes, checksum: 943d5ca241503469ec62771f75a17d12 (MD5) thesis.tex: 5007 bytes, checksum: 18cc76557dbb03bef58d011366d40c27 (MD5) def.tex: 1933 bytes, checksum: fcdfee1bd37b4f2400ee10c5e1b91726 (MD5) abstract.tex: 1707 bytes, checksum: f32b1f77a55103e5eebc190e5b0ac3eb (MD5) Cullina_Daniel.pdf: 364645 bytes, checksum: d7b125abe8403ef05d2c75c638e4774a (MD5)","Made available in DSpace on 2015-01-21T19:49:27Z (GMT). No. of bitstreams: 5 Daniel_Cullina.pdf: 364645 bytes, checksum: d7b125abe8403ef05d2c75c638e4774a (MD5) thesis-body.tex: 85701 bytes, checksum: 943d5ca241503469ec62771f75a17d12 (MD5) thesis.tex: 5007 bytes, checksum: 18cc76557dbb03bef58d011366d40c27 (MD5) def.tex: 1933 bytes, checksum: fcdfee1bd37b4f2400ee10c5e1b91726 (MD5) abstract.tex: 1707 bytes, checksum: f32b1f77a55103e5eebc190e5b0ac3eb (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/72914"],"dc:language":["en"],"dc:rights":["Copyright 2014 Daniel Cullina"],"dc:subject":["coding theory","error correction","deletion channel","combinatorics"],"dc:title":["Constant composition deletion correcting codes"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}