Diagnosis of Single Faults in Bitonic Sorters

Tsern-Huei Lee, Chou Jin-Jye

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Bitonic sorters have recently been proposed to con- struct along with banyan networks the switching fabric of future broadband networks [2]. Unfortunately, a single fault in a bitonic sorter may have disastrous consequences for the switching system. Therefore, a bitonic sorter must be proved to be free of faults before it can be used. In this paper we study the topological properties of bitonic sorters and present an efficient fault diagnosis procedure to detect, locate, and identify the fault type of single faults. Our diagnosis procedure can detect most single faults in two tests. Faults which cannot be detected in two tests can always be detected in four tests. Several binary search techniques are developed to locate a faulty sorting element (i.e., a 2 x 2 sorter).

Original languageEnglish
Article number336322
Pages (from-to)497-507
Number of pages11
JournalIEEE/ACM Transactions on Networking
Issue number5
StatePublished - Oct 1994

Fingerprint Dive into the research topics of 'Diagnosis of Single Faults in Bitonic Sorters'. Together they form a unique fingerprint.

Cite this