A Permutation Network

ABSTRACT

In this paper the construction of a switching network capable of n!-permutation of its n input terminals to its n output terminals is described. The building blocks for this network are binary cells capable of permuting their two input terminals to their two output terminals. The number of cells used by the network is <n · log2 n - n + 1> = ∑n k=1 2 k>. It could be argued that for such a network this number of cells is a lower bound, by noting that binary decision trees in the network can resolve individual terminal assignments only and not the partitioning of the permutation set itself which requires only 2 n!> = <∑n k=1 log2 k> binary decisions. An algorithm is also given for the setting of the binary cells in the network according to any specified permutation.

REFERENCES

• 1: HALL, P. On representatives of subsets. J. London Math. Soe. 10 (1965), 26-30.
• 2: BENES, V. E. MathemaTIcal Theory of connecting networks and Telephone Traffic. Academic Press New York, 1935.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance, Theory