Invariant Properties of the Shuffle-Exchange and a Simplified Cost-Effective Version of the Omega Network
- 1 May 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (5) , 444-450
- https://doi.org/10.1109/tc.1983.1676255
Abstract
Let Ω denote the set of permutations performable by a pass through the Omega network (an n-stage shuffle-exchange network), and let π denote an arbitrary permutation of N = 2n elements. In this paper we characterize the sets {π|πΩ = Ω} (called left invariants) and {π|Ωπ = Ω} (called right invariants). This characterization provides a useful criterion for determining whether or not the composition of two permutations belongs to Ω; it also allows a number of known results to be generalized and their derivations simplified.Keywords
This publication has 10 references indexed in Scilit:
- The Universality of the Shuffle-Exchange NetworkIEEE Transactions on Computers, 1981
- The Reverse-Exchange Interconnection NetworkIEEE Transactions on Computers, 1980
- Notes on Shuffle/Exchange-Type Switching NetworksIEEE Transactions on Computers, 1980
- Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used PermutationsIEEE Transactions on Computers, 1978
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange NetworkIEEE Transactions on Computers, 1976
- A Shuffle-Exchange Network with Simplified ControlIEEE Transactions on Computers, 1976
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- A Permutation NetworkJournal of the ACM, 1968