Fault tolerance analysis of odd-even transposition sorting networks with single pass and multiple passes

The odd-even transposition sorting networks have a simple and reliable VLSI implementation, and also have good fault tolerance properties. In this paper, a formal proof is presented for a well-known conjecture that states the odd-even transposition sorting networks are one-fault tolerant with respect to stuck-at-X fault at any internal comparators. Also, new simulation results are reported for a new mode of operation, sorting via multiple passes through the networks. Under this mode, the simulation results reveal that the odd-even transposition networks are k-fault tolerant with respect to stuck-at-X, stuck-at-H, and stuck-at-T at any set of internal comparators.