DocumentCode :
891662
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.
Issue :
5
fYear :
1967
Firstpage :
637
Lastpage :
641
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;
fLanguage :
English
Journal_Title :
Electronic Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0367-7508
Type :
jour
DOI :
10.1109/PGEC.1967.264771
Filename :
4039154
Link To Document :
بازگشت