Universal multistage networks via linear permutations
Charles M. Feduccia, Elaine M. Jacobson · 1991
The universality of iterated multistage interconnection networks on N = Y inputs is examined by representing them as directed 2-graphs on N/2 nodes.The shuj?e-exchange network is generalized, by allowing any invertible linear operator T, over GF(2), to replace the perfect shujle and any nonzero translation v H v + Q to replace the exchange operation.It is shown that a pair (T, a] gives rise to a universal network if and only if the vectors a, Ta, T2CY, . . . .Tn-la are linearly independent, and that the 2-graph for any such pair is isomorphic to the de Brui'n graph.Thus, a pair (T, a) is either useless, because its network is not connected, or as good as the shujj?e-exchange network.This provides a wide range of design alternatives for networks that can pass all N! permutations with 2n-1 identical stages.