{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/68185"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/68185","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Bounds and Constructions for Codes Protecting Against Asymmetric Errors","abstract":"We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.","abstract_html":"We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.","abstract_has_math":false,"creators":["Borden, J. Martin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-14T13:09:50Z","date_published":"2014-12-14T13:09:50Z","updated_at":"2026-07-22T22:25:58Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8203408"],"render_values":[{"text":"(UMI)AAI8203408","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/68185","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Borden, J. Martin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-14T13:09:50Z","10000-01-01","1981"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/68185","(UMI)AAI8203408"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.","Maximal cardinality error-detecting codes are easily described. The code consisting of all length n words whose Hamming weight is congruent to n/2 modulo e+1 is capable of detecting any occurrence of e or fewer errors, and we prove that this code has the maximum number of codewords among all length n codes detecting e errors.","It is much more difficult to characterize optimal error-correcting codes. We obtain the bound","S(n,e) (LESSTHEQ) A(n,e) (LESSTHEQ) min {S(n+e,e), (e+1)S(n,e)},","which compares A(n,e), the maximal cardinality of an e error-correcting length n asymmetric code, to S(n,e), the corresponding quantity for the familiar symmetric error-correcting codes. It is an interesting consequence that the best asymmetric and symmetric codes asymptotically have the same rates when n tends to infinity and the ratio e/n is held fixed.","At very low rates however, asymmetric codes can differ markedly from symmetric codes. We prove that there are arbitrarily large asymmetric codes that can correct errors occurring in up to 1/3 of the coordinate positions of each codeword. Also, we have the upper bound (e+1)/n (LESSTHEQ) M/(3M-4) for a code with M codewords, which shows that the fraction 1/3 is best possible. This result contrasts with the corresponding Plotkin-Levenshtein bound for symmetric codes where the fraction is 1/4.","Our algebraic constructions are based on a group code construction introduced by Varshamov. We work with prime power cyclic groups to give a new construction from which there results the best lower bound known,","A(n,e) (GREATERTHEQ) 2('n)/(n('e)+n('e-1)+...+ 1),","when n is a prime power.","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8203408.pdf: 3185662 bytes, checksum: d5cf1c8068705a64c1dea850019d23d0 (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68363 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","114 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."]},{"key":"dc:title","label":"Title","values":["Bounds and Constructions for Codes Protecting Against Asymmetric Errors"]}]}],"canonical_facts":{"dc:creator":["Borden, J. Martin"],"dc:date":["2014-12-14T13:09:50Z","10000-01-01","1981"],"dc:description":["We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.","Maximal cardinality error-detecting codes are easily described. The code consisting of all length n words whose Hamming weight is congruent to n/2 modulo e+1 is capable of detecting any occurrence of e or fewer errors, and we prove that this code has the maximum number of codewords among all length n codes detecting e errors.","It is much more difficult to characterize optimal error-correcting codes. We obtain the bound","S(n,e) (LESSTHEQ) A(n,e) (LESSTHEQ) min {S(n+e,e), (e+1)S(n,e)},","which compares A(n,e), the maximal cardinality of an e error-correcting length n asymmetric code, to S(n,e), the corresponding quantity for the familiar symmetric error-correcting codes. It is an interesting consequence that the best asymmetric and symmetric codes asymptotically have the same rates when n tends to infinity and the ratio e/n is held fixed.","At very low rates however, asymmetric codes can differ markedly from symmetric codes. We prove that there are arbitrarily large asymmetric codes that can correct errors occurring in up to 1/3 of the coordinate positions of each codeword. Also, we have the upper bound (e+1)/n (LESSTHEQ) M/(3M-4) for a code with M codewords, which shows that the fraction 1/3 is best possible. This result contrasts with the corresponding Plotkin-Levenshtein bound for symmetric codes where the fraction is 1/4.","Our algebraic constructions are based on a group code construction introduced by Varshamov. We work with prime power cyclic groups to give a new construction from which there results the best lower bound known,","A(n,e) (GREATERTHEQ) 2('n)/(n('e)+n('e-1)+...+ 1),","when n is a prime power.","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8203408.pdf: 3185662 bytes, checksum: d5cf1c8068705a64c1dea850019d23d0 (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68363 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","114 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."],"dc:identifier":["http://hdl.handle.net/2142/68185","(UMI)AAI8203408"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["Bounds and Constructions for Codes Protecting Against Asymmetric Errors"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:58Z"}