Fault-tolerant computation using algebraic homomorphisms
P.E. Beckmann, Bruce R. Musicus · Massachusetts Institute of Technology eBooks · 1992
Arithmetic codes are a class of error-correcting codes that are able to protect computation more efficiently than modular redundancy. In this thesis we consider the problem of designing an arithmetic code to protect a given computation. The main contributions are as follows: (1) The first constructive procedure, outside of modular redundancy, for generating arithmetic codes for a large class of operations. The approach is mathematically rigorous, based on group-theory, and fully characterizes the important class of systematic-separate codes. The results encompass computation that can be modeled as operations in an algebraic group, ring, field, or vector space. (2) A novel set-theoretic framework for characterizing the redundancy present in a system. We present a decomposition of a robust system into a cascade of three systems and determine general requirements for multiple error detection and correction. (3) We identify an important class of errors for which the redundancy present in a system may be completely characterized by a single integer, analogous to the minimum distance of a binary error-correcting code. (4) We unify the existing literature on arithmetic codes. A wide variety of seemingly unrelated codes are combined into a single general framework. (5) A large number of examples illustrating the application of our technique are presented. (6) Detailed analyses of two new and practical fault-tolerant systems: fault-tolerant convolution and A/D conversion. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)