Diagnosis of single faults in bitonic sorters

Bitonic sorters have recently been proposed to construct along with banyan networks the switching fabric of future broadband networks. 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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 1994-10, Vol.2 (5), p.497-507, Article 497
Main Authors: Lee, Tsern-Huei, Chou, Jin-Jye
Format: Article
Language:English
Subjects:
Broadband communication
Councils
Fabrics
Fault detection
Fault diagnosis
Intelligent networks
Solids
Sorting
Switching systems
Testing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Bitonic sorters have recently been proposed to construct along with banyan networks the switching fabric of future broadband networks. 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. 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/spl times/2 sorter).< >
ISSN:1063-6692
1558-2566
DOI:10.1109/90.336322