Design and analysis of defect tolerant hierarchical sorting networks

A novel hierarchical defect-tolerant sorting network is presented. The design achieves a balance in area-time cost between the odd-even transposition sort and the bitonic sort. It uses less hardware than a single-level odd-even transposition sorter and reduces the wire complexity of the bitonic sorter in VLSI or WSI (wafer scale integration) implementation. The optimal number of levels in the hierarchy is evaluated and the sorting capability of each level is derived to minimize the hardware overhead. The hierarchical sorting network is very regular in structure and hence it is easy to provide redundancy at every level of the hierarchy. Hierarchical reconfiguration is implemented by replacing the defective cells with spare cells at the bottom level first, and goes to the next higher level to perform reconfiguration if there is not enough redundancy at the current level. Simulation results show that the defect tolerant hierarchical sorting network considered achieves a significant yield increase over a nonredundant sorting network