Defect-tolerant hierarchical sorting networks for wafer-scale integration

A novel hierarchical defect-tolerant sorting network that meets application requirements and area-time complexity constraints is presented. It is very regular in structure and hence easier to reconfigure than any existing sorting network with the same time complexity. Redundancy is provided at every level of the hierarchy. Hierarchical reconfiguration is implemented by replacing the defective cells with spare cells at the lowest level first, and reconfiguration goes to the next higher level if there is not enough redundancy at the current level. These redundant cells can be used for single error correction at run time. Simulations demonstrate that significant yield improvements over other approaches can be achieved