Optimal error detection codes for completely asymmetric binary channels

Abstract

The (n/2)-out-of-n code is proved to be the least redundant binary block code which permits the detection of all errors in completely asymmetric channels. It is then proved that the sum code of Berger, Smith, and Freiman is the least redundant of all separable codes of this type. The redundancies of the sum and (n/2)-out-of-n codes are then compared and it is shown that the former is asymptotically twice as redundant as the latter. An efficient method of constructing separable codes which detect up to a given number, but not all, asymmetric errors is included as an appendix. © 1963 Academic Press Inc.