Sorting on defective VLSI-arrays

Josef G. Krammer, Ernst G. Bernard, Matthias Sauer, Josef A. Nossek

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish
Pages (from-to)33-48
Number of pages16
JournalIntegration, the VLSI Journal
Issue number1
StatePublished - Nov 1991


  • Defect-tolerance
  • VLSI-sorter
  • reconfigurable arrays


Dive into the research topics of 'Sorting on defective VLSI-arrays'. Together they form a unique fingerprint.

Cite this