Separate non-homomorphic checking codes for binary addition

[摘要] In this paper, necessary and sufficient conditions for successful detection of errors in a binary adder by any separate code are developed. We demonstrate the existence of separate checking codes for addition modulo $2^n$ (n >= 4) and modulo $2^n$-1 (n > 5, n even), which are not homomorphic images of the addition being checked. A non-homomorphic code is constructed in a regular fashion from a single check symbol with special properties. Finding all such intial check symbols requires an exhaustive search of a large tree, and results indicate that the number of distinct codes for a particular modulus grows rapidly with n. In an appendix, we examine a modulo $2^n$ adder where the carry out of the high position is also presented to a checker.

[学科分类] 计算机科学（综合）