Self-correcting programs and error-correcting codes
Manuel Blum, Hal Wasserman · 1997
Error-correcting codes allow us to send information over unreliable channels, to detect if errors have occurred during transmission, and if so to automatically correct these errors. The field of result-checking, defined in analogy, is concerned with algorithms which allow a program to determine if it has made an incorrect calculation, and if so to correct its own errors. Here we consider the application of these fields to problems of real-number computation and of communicating in the presence of a very high amount of noise. In the domain of result-checking, we argue that debugging efficiency and hardware/software reliability may be enhanced by embedding checkers and correctors. We present two case studies. First, we describe how a microprocessor could automatically check and correct its own IEEE standard floating-point arithmetic computations. Second, we specify checkers and correctors for arbitrary multivariate linear transformations acting on fixed-point real numbers. In the domain of error-correcting codes, Sudan (87) has recently considered the problem of decoding Reed-Solomon codes (equivalently, reconstructing polynomials from noisy data) and has specified algorithms which allow for reconstruction of meaningful information in spite of an amount of noise which may go far beyond the conventional error-correction bound. Here, we extend this work in two respects. First, we give improved results for the problem of reconstructing multivariate polynomials, and for the problem of reconstructing from noise which is random in a specified sense. Second, we generalize Sudan's method to algebraic-geometric codes, and are thereby able to formulate new decoding algorithms, new asymptotic bounds, and intriguing open questions. We believe that both self-correcting programs and error-correcting codes may be important to the future development of complex yet error-resistant computer systems. This belief motivates our current theoretical work in increasing the power and generality of error-correction methodologies.