University of Illinois Urbana-Champaign

Bounds and Constructions for Codes Protecting Against Asymmetric Errors

Borden, J. Martin

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/68185

Description

Title
Bounds and Constructions for Codes Protecting Against Asymmetric Errors
Author(s)
Borden, J. Martin
Issue Date
1981
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Mathematics
Language
eng
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.
  • 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.
Graduation Semester
1981
Type of Resource
text
Permalink
http://hdl.handle.net/2142/68185

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics