HIERARCHICAL-CLASSIFICATION OF PERMUTATION CLASSES IN MULTISTAGE INTERCONNECTION NETWORKS

This brief contribution explores a new hierarchy among different permu tation classes, that has many applications in multistage interconnecti on networks. The well-known LC (linear-complement) class is shown to b e merely a subset of the closure set of the BP (bit-permute) class, kn own as the BPCL (bit-permute-closure) class; the closure is obtained b y applying certain group-transformation rules on the BP-permutations. It indicates that for every permutation P of the LC class, there exist s a permutation P in the BP class, such that the conflict graphs of P and pf are isomorphic, for n-stage MIN's. This obviates the practice of treating the LC class as a special case; the existing algorithm for optimal routing of BPC class in an n-stage MIN, can take care of opti mal routing of the LC class as well. Finally, the relationships of BPC L with other classes of permutations, e.g., LIE (linear-input-equivale nce), BPIE (bit-permute-input-equivalence), BPOE (bit-permute-output-e quivalence) are also exposed. Apart from lending better understanding and an integral view of the universe of permutations, these results ar e found to be useful in accelerating routability in n-stage MIN's as w ell as in (2n - 1)-stage Benes and shuffle-exchange networks.