Report Number: CSL-TR-72-35
Institution: Stanford University, Computer Systems Laboratory
Title: Separate non-homomorphic checking codes for binary addition
Author: Kolupaev, Stephen G.
Date: July 1972
Abstract: 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.
http://i.stanford.edu/pub/cstr/reports/csl/tr/72/35/CSL-TR-72-35.pdf