A fault-tolerant systolic sorter

A fault-tolerant systolic sorter design is proposed. An algorithm-based fault tolerance is achieved by testing the invariants of a systolic sorter during normal operation. Transient and permanent computation errors can be detected by using error-checking code and some redundant cells. A block with a single faulty cell can be located. Small hardware overhead and negligible time overhead are shown to be the major advantages of the method. A hierarchical structure is suggested as an efficient architecture for realizing the method. An offline fault-testing method for permanent stuck-at faults is presented