The Universality of the Shuffle-Exchange Network

Abstract

This paper has focused on the realization of every arbitrary permutation with the shuffle-exchange network. Permutation properties of shuffle-exchange networks are studied and are used to demonstrate several universal networks. It is concluded that 3(log2 N) –1 passes through a single-stage regular shuffle exchange network are sufficient to realize every arbitrary permutation where N is network size. A routing algorithm is also developed to calculate control settings of the shuffle-exchange switches for the permutation realization. Three optimal universal networks, namely, expanded direct- connection shuffle-exchange network, multiple-pass omega network, and modified shuffle-exchange network are then exploited for better interconnection purposes. In addition, this work specifies the inherent relationship between the shuffle-exchange network and the Benes binary network so that designers can have a broad prospect.