BIT-PERMUTE MULTISTAGE INTERCONNECTION NETWORKS

In this paper, we consider a class of log N stage interconnection netw orks called Bit-Permute Multistage Interconnection Networks (BPMIN's) where the ports of each switch of a stage are different at only one bi t position of their labels. We describe the decomposition structure of the BPMIN's and prove that all of the BPMIN's are topologically equiv alent and some of them are functionally equivalent. We also identify a class of 2 log N stage rearrangeable networks called symmetric BPMIN' s where two log N stage BPMIN's are connected in sequence. The symmetr ic BPMIN's are either symmetric or asymmetric and regular or irregular in their inter-stage connections and can be reduced into 2 log N-1 st ages by combining the two center stages. We show that the symmetric BP MIN's constitute larger class of rearrangeable networks than ever know n, We also propose a general routing algorithm for the symmetric BPMIN 's by modifying slightly the looping algorithm of the Benes network.