NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Finite state model and compatibility theory - New analysis tools for permutation networksA simple model to describe the fundamental operation theory of shuffle-exchange-type permutation networks, the finite permutation machine (FPM), is described, and theorems which transform the control matrix result to a continuous compatible vector result are developed. It is found that only 2n-1 shuffle exchange passes are necessary, and that 3n-3 passes are sufficient, to realize all permutations, reducing the sufficient number of passes by two from previous results. The flexibility of the approach is demonstrated by the description of a stack permutation machine (SPM) which can realize all permutations, and by showing that the FPM corresponding to the Benes (1965) network belongs to the SPM. The FPM corresponding to the network with two cascaded reverse-exchange networks is found to realize all permutations, and a simple mechanism to verify several equivalence relationships of various permutation networks is discussed.
Document ID
19860060460
Acquisition Source
Legacy CDMS
Document Type
Reprint (Version printed in journal)
Authors
Huang, S.-T.
(Maryland Univ. College Park, MD, United States)
Tripathi, S. K.
(Maryland, University College Park, United States)
Date Acquired
August 12, 2013
Publication Date
July 1, 1986
Publication Information
Publication: IEEE Transactions on Computers
Volume: C-35
ISSN: 0018-9340
Subject Category
Cybernetics
Accession Number
86A45198
Funding Number(s)
CONTRACT_GRANT: NAS5-27704
CONTRACT_GRANT: NSF MCS-81-12896
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available