Bounds and Constructions for Codes Protecting Against Asymmetric Errors

114 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.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 boundS(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.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD