DESIGN, ANALYSIS, AND EVALUATION OF CONCURRENT CHECKING SORTING NETWORKS

In this brief, we propose two new concurrent error-detection (CED) sch emes for a class of sorting networks, e.g., odd-even transposition, bi tonic, and perfect shuffle sorting networks, A probabilistic method is developed to analyze the fault coverage, and the hardware overhead is evaluated, We first propose a CED scheme by which all errors caused b y single faults in a concurrent checking sorting network can he detect ed. This scheme is the first one available to use significantly less h ardware overhead than duplication without compromising throughput, Fro m this scheme, we develop another fault detection scheme which sharply reduces the hardware overhead (using an additional 10% similar to 30% hardware) but still achieves virtually 100% fault coverage.