Fault-tolerant matrix operations on multiple processor systems using weighted checksums

Hardware for performing matrix operations at high speeds is in great demand in signal and image processing and in many real-time and scientific applications. VLSI technology has made it possible to perform fast large-scale vector and matrix computations by using multiple copies of low-cost processors. Since any functional error in a high performance system may seriously jeopardize the operation of the system and its data integrity, some level of fault-tolerance must be obtained to ensure that the results of long computations are valid. A low-cost checksum scheme had been proposed to obtain fault- tolerant matrix operations on multiple processor systems. However, this scheme can only correct errors in matrix multiplication; it can detect, but not correct errors in matrix-vector multiplication, LU- decomposition, and matrix inversion. In order to solve these problems with the checksum scheme, a very general matrix encoding scheme is proposed in this paper to achieve fault-tolerant matrix operations with multiple processor systems. Since many signal and image processing algorithms involving a wmultiply-and-accumulateM type of expression can be transformed into matrix-vector multiplication operations and executed in a linear array, this scheme is extremely useful for cost-effective and fault-tolerant signal and image processing.