FINITE STATE MODEL AND COMPATIBILITY THEORY: NEW ANALYSIS TOOLS FOR PERMUTATION NETWORKS.

A new model, the finite permutation machine (FPM), to describe permutation networks is presented. A set of theorems is developed to capture the theory of operations for the permutation networks. Using this new framework, the following problem is attacked: Are 2n-1 passes of shuffle exchange necessary and sufficent to realize all permutations? Where n equals log//2 N, where N is the number of inputs and outputs interconnected by the network. It is proved that in order 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 two from the best known result. The Benes network is the best known network that can realize all permutations. To show the flexibility of the approach, the authors describe a general class of FPM, the stack permutation machine (SPM), which can realize all permutations, and show that an FPM corresponding to the Benes network belongs to the class of SPMs. It is also shown that an FPM corresponding to the network with two cascaded reverse-exchange networks can realize all permutations. To show the simplicity of the approach, a simple mechanism to verify several equivalence relationships of various permutation networks is outlined.