Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks

In this paper, we present a new model, finite permutation machine (FPM), to describe the permutation networks. A set of theorems are developed to capture the theory of operations for the permutation networks. Using this new framework, an interesting problem is attacked: are 2n — 1 passes of shuffle exchange necessary and sufficient to realize all permutations? where n = log2N and N is the number of inputs and outputs interconnected by the network. We prove that to realize all permutations, 2n − 1 passes of shuffle exchange are necessary and that 3n-3 passes are sufficient. This reduces the sufficient number of passes by 2 from the best-known result. Benes network is the most well-known network that can realize all permutations. To show the flexibility of our approach, we describe a general class of FPM, stack permutation machine (SPM), which can realize all permutations, and show that FPM corresponding to Benes network belongs to SPM. We also show that FPM corresponding to the network with 2 cascaded reverse-exchange networks can Realize all permutations. To show the simplicity of our approach, we also present a very simple mechanism to verify several equivalence relationships of various permutation networks.