Title :
On the Synthesis of Signal Switching Networks with Transient Blocking
Author :
Goldstein, Larry Joel ; Leibholz, Stephen W.
Author_Institution :
Dept. of Mathematics, Yale University, New Haven, Conn.
Abstract :
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 log2N-N log2 e+(¿) log2 N + log2 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 log2 N 2Ã2 crossbars is described. If N is a power of 2, N = 2m, then the algorithm described requires N log2 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.
Keywords :
Boolean functions; Cities and towns; Conferences; Design automation; Multivalued logic; Network synthesis; Signal synthesis; Switches; Switching circuits; Wires; Group theory; permutation network; switching network;
Journal_Title :
Electronic Computers, IEEE Transactions on
DOI :
10.1109/PGEC.1967.264771