Sorting on defective VLSI-arrays

A method for adapting shortperiodic sorting algorithms to defective arrays is presented. The approach is based on nearest neighbor interconnections and thus requires no additional wiring and switches for bypassing defective cells. The algorithm is adapted by reindexing, i.e., by modifying the ordering of the sorted sequence (indexing scheme). An efficient strategy for determining an indexing scheme is presented. A worst case sorting time of O( N ) is proved for these sorters. Simulation results show thatthe typical sorting time is only slightly higher than O(√N) and thus all advantages of the two-dimensional sorter are preserved. A sorting network implementing the adapted algorithm has the same topology as that for the algorithm in the fault-free case. The only modification is the programmability of the exchange operation of the cells. A simple and efficient method for testing the array is presented.