Concurrent error detection and correction in real-time systolic sorting arrays

An approach to online error detection and correction for high-throughput VLSI sorting arrays is presented. The error model is defined at the sorting element level, and both functional errors and data errors generated by a faulty element are considered. The functional errors are detected and corrected by exploiting inherent properties of the sorting array, as well as special properties we discovered by the authors. Coding techniques and an online fault diagnosis procedure are developed to locate data errors. All the checkers are designed to be totally self-checking, and hence the sorting array is highly reliable. Two-level pipelining is employed in this design, making it very efficient and suitable for real-time application. The hardware overhead is not significant for typical array sizes, and the time penalty is only 3 clock cycles. The structure is very regular and therefore very attractive for VLSI or WSI implementation.