Rearrangeability of 7-stage 16 × 16 shuffle exchange networks

Abstract

It has long been an outstanding conjecture that any (2n - 1)-stage shuffle exchange network (Omega network) is rearrangeable for 2ⁿ × 2ⁿ. Many researchers have failed to prove this conjecture, including a recent one established by Hasan. However, nobody has pointed out its fallacy. Therefore, as one of the objectives, this paper shall clarify this fact. Since the case of n = 3 has been proven by many researchers 12, this paper uses a constructive approach to prove that when n = 4, the 7-stage 16 × 16 shuffle exchange network is also rearrangeable. The paper also presents the model of a balanced tree to avoid internal conflict, the representation of permutations using a connection graph and loop graph, and the concepts of symmetry graph and identical transform. Based on graphic composition and bipartition, the permutations 16 × 16 are divided into five classes, with five assignment algorithms proposed. These algorithms are simpler, clearer and easier to program. The techniques used for n = 4 may provide hints for the general case of n > 4.

Keywords

multistage interconnection network (MIN) / shuffle exchange network / rearrangeability / equivalent transform / identical transform