On the Synthesis of Signal Switching Networks with Transient Blocking

Signal switching networks with transient blocking are defined. The number of 2×2 crossbars necessary to synthesize a signal switching network with transient blocking capable of performing all one-to-one connections of N inputs to N outputs is shown to be at least N log 2 N-N log 2 e+(½) log 2 N + log 2 2 + 0(1) as N→ ∞. It is shown that this lower bound can never be attained for N>2. An algorithm for building a network using at most 2N log 2 N 2×2 crossbars is described. If N is a power of 2, N = 2 m , then the algorithm described requires N log 2 N-N+1 2×2 crossbars, which is close to the theoretical minimum. Generalizations of this work to networks performing an arbitrary permutation group of connections of inputs to outputs are indicated. Explicit results are obtained in the case of Abelian groups.