Rearrangeability of (2n -1)-stage shuffle-exchange networks

Abstract. Rearrangeable networks can realize each and every permutation in one pass through the network. Shuffle-exchange networks provide an efficient interconnection scheme for implementing various types of parallel processes. Whether (2n − 1)-stage shuffle-exchange networks with N =2 n inputs/outputs are rearrangeable has remained an open question for approximately three decades. This question has been answered affirmatively in this paper. An important corollary of the main result is the proof that two passes through an Omega network are sufficient and necessary to implement any permutation. In obtaining the main results of this paper, frames that look like grids with horizontal links of different lengths are shown to be remarkable tools for identifying and characterizing the binary matrix representations of permutations