Dec. 12, 1967
`
`3,358,269
`V. E. BENES
`S
`QUARE SWITCH DISTRIBUTION NETWORK EMPLOYING
`A
`Filed April l0, 1964
`3. Sheets-Sheet
`
`A OC
`
`It
`S.
`
`lit.
`s
`
`
`
`S
`S
`U
`
`//V/A/W7OAP
`M. A. AAWAS
`
`Page 1 of 10
`
`FLEX LOGIX EXHIBIT 1040
`
`

`

`3,358,269
`V. E. BENES
`Dec. 12, 1967
`SQUARE SWITCH DISTRIBUTION NETWORK EMPLOYING
`A MINIMAL NUMBER OF CROSSPOINTS
`Filed April l0, 1964
`3 Sheets-Sheet 2
`
`N
`y
`a N-S N
`
`is
`
`L
`
`Ys
`Enl N
`
`N
`CS
`S
`S
`
`O &
`
`-
`
`
`
`
`
`of I
`
`His Hi Hi HE
`it in
`
`Page 2 of 10
`
`

`

`3,358,269
`V. E. BENES
`Dec. 12, 1967
`SQUARE SWITCH DISTRIBUTION NETWORK EMPLOYING
`A MINIMAL NUMBER OF CROSSPOINTS
`Filed April 10, 1964 .
`3. Sheets-Sheet 3
`
`
`
`s
`
`s
`
`8
`
`9.
`
`8
`R
`Q
`(yo) y Olovy WOS/2/va woo
`
`O
`
`Page 3 of 10
`
`

`

`United States Patent Office
`
`3,358,269
`Paterated Dec. 2, 1967
`
`3,358,269
`SQUARE SWITCH DISTRIBUTION NETWORK
`EMPLOYNG. A. MNMALL NUMBER OF
`CROSSPONTS
`Waclav E. Benes, Chester, N.J., assignor to Bei Telephone
`Laboratories, Incorporated, New York, N.Y., a corpo
`ration of New York
`Filed Apr. 10, 1964, Ser. No. 358,712
`9 Claims. (C. 340-166)
`
`ABSTRACT OF THE DISCLOSURE
`A rearrangeable symmetrical distribution network is
`disclosed for connecting any one of N input terminals
`to any one of N output terminals where N is any positive
`integer such that 22:33 . . . k"k is the prime decomposi
`tion of N into a product of prime numbers raised to inte
`ger exponents. The network includes
`
`10
`
`5
`
`20
`
`2
`sively be fabricated from a plurality of similar circuit
`combinations.
`These and other objects of the present invention are
`realized in a specific, illustrative, rearrangeable symmet
`rical distribution connector which includes a minimum
`number of crosspoints for each input and output ter
`minal connected thereto. The composite distribution net
`work includes an odd number of stages each comprising
`a plurality of square switches of a like size.
`Corresponding to N input and N output terminals,
`where N is any positive integer whose prime decomposi
`tion 2's 38 . . . k"k includes a prime factor greater than
`three or includes a prime factor equal to three and N
`is odd, the switching structure includes
`
`2(S o)-1
`
`stages. Where the largest prime factor of the prime de
`composition of N is equal to three and N is even or
`where the largest prime factor is equal to two, the switch
`ing structure includes
`
`2(S)-3
`
`2(a)-
`2(S o)-3
`
`interconnected stages if the largest prime factor of N
`exceeds three or if it equals three and N is odd, or
`
`interconnected stages if the largest prime factor of N
`equals two or if it equals three and N is even. Each stage
`includes a plurality of square switches of like size. The
`30
`number of inputs and outputs of each stage equals N.
`
`25
`stages. Each stage includes a plurality of square switches
`of like size. In the first situation mentioned above, the
`number of square switches included in each stage is de
`rived by dividing N by a corresponding prime factor. In
`the second situation the number of square switches in
`cluded in each stage except the middle stage is also de
`rived by dividing N by a corresponding prime factor.
`The middle stage in this latter case includes either four
`or six square switches depending on the value of N.
`The total number of crosspoints included in the instant
`connector is proportional to N log N, which compares
`favorably with the N factor characterizing prior art square
`matrix switches.
`40
`It is thus a feature of the present invention that a
`distribution switch include a plurality of switching stages
`each comprising a plurality of like size, square switches.
`It is another feature of the present invention that
`a distribution network comprise a like number of inlets
`and outlets, an odd number of symmetrically-connected
`switching stages each employing like-sized square switches,
`wherein the network comprises a minimum number of
`crosspoint contact pairs.
`It is still another feature of the present invention that
`a symmetrical distribution network employing square
`switches comprise N input and N output terminals, and
`S switching stages serially connected between the input and
`output terminals, where
`s
`
`35
`
`45
`
`50
`
`This invention relates to switching circuits and, more
`specifically, to a distribution switching networb employ
`ing a minimal number of crosspoint contact pairs.
`Pursuant to relatively recent innovations in the elec
`tronic and magnetic arts, much effort is currently bein
`directed towards the development of economic telephone
`Systems employing electronic switching principles. Such
`arrangements are inherently capable of faster operative
`speeds and increased flexibility than were prior telephone
`communication embodiments.
`Experience with electronic telephone switching systems
`has indicated that the crosspoint switches found in signal
`distribution switching arrays included therein comprise
`a greater percentage of the over-all system cost than
`these circuit combinations did in older, electro-mechan
`ical switching arrangements. Accordingly, electronic tele
`phone systems require distribution networks comprising
`a minimal number of crosspoints. In addition, it is fur
`ther desirable that such connecting networks be rearrange
`able, i.e., allow each idle inlet to be connected to each
`idle outlet by rearranging the existing connection pattern.
`55
`An illustrative rearrangeable network, along with com
`mon control equipment associated therewith, is disclosed
`in a copending application by M. C. Paull, Ser. No. 154,-
`477, filed Nov. 24, 1961 (now patent 3,129,407 issued
`Apr. 14, 1964). However, the above-described combina
`60
`tion of features in a distribution connector, viz., rear
`rangeability and a crosspoint minimum, are in general
`conflicting, and have therefore not been embodied in prior
`art switching structures.
`It is thus an object of the present invention to provide
`an improved distribution switching network.
`More specifically, an object of the present invention is
`the provision of an economical, rearrangeable distribu
`tion network which includes a minimum number of cross
`point switches.
`It is another object of the present invention to provide
`a distribution connector which may easily and inexpen
`
`65
`
`k
`
`when the largest prime factor of the prime decomposition
`of N is greater than three or is equal to three and N is
`odd, and
`Sas 2(s o)-3
`j=2
`when the largest prime factor of the prime decomposition
`of N is equal to two or is equal to three and N is even.
`A complete understanding of the present invention
`and of the above and other features, advantages and
`variations thereof may be gained from a consideration of
`the following detailed description of an illustrative em
`70
`bodiment thereof presented hereinbelow in conjunction
`with the accompanying drawing, in which:
`
`Page 4 of 10
`
`

`

`3,358,269
`4.
`3
`are interconnected in a repeating, overlapping manner.
`FIGS. 1 (A) and 1 (B) are schematic diagrams respec
`That is, a junctor connects the first outlet of the first (or
`tively illustrating the upper and lower halves of a distri
`top-most) switch includes in a left-hand switching stage
`bution network which embodies the principles of the
`with the first inlet of the first switch in the right-adjacent
`present invention; and
`stage. The second outlet on the first switch of the left stage
`FIG. 2 is a graph comparing the number of cross
`is joined with the first inlet of the second switch of the
`point switches employed in the instant class of distribution
`adjacent switching stage. This connection pattern con
`arrangements with the number of corresponding elements
`tinues until each switch of the right stage has one junctor
`required in prior art square matrix embodiments.
`connected thereto. At this point, the process starts over
`As indicated above, it is considered important in the
`again with the first switch, continuing cyclically until all
`switching art to provide a rearrangeable distribution net
`the junctors emanating from the left stage have been
`work which connects each of N input terminals, or inlets,
`assigned.
`to each of N output terminals, or outlets, and which em
`It is noted that the above relationships define a complete
`ploys a relatively small number of crosspoint switches.
`distribution structure for any value of N. The structure
`Accordingly, one aspect of the present invention is the
`embodying the above-described class of distribution net
`provision of a distribution network which employs an
`Works, and the particular method of fabrication thereof,
`absolute minimum number of crosspoints for the class of
`will become more clear from the discussion hereinafter of
`rearrangeable distribution connectors which comprise an
`a particular, illustrative connector shown in FIG. 1, which
`odd number of serially-connected symmetrically-arranged
`Succeeds a mathematical proof of crosspoint minimization.
`switching stages each employing square switches. Each
`square switch, in turn, comprises a matrix array including
`20
`Proof of minimization
`a like number of inlets and outlets which are intercon
`The following proof demonstrates that the herein
`nected via a plurality of crosspoint switches. The cross
`presented class of distribution networks in fact employs an
`point switches may advantageously comprise electronic
`absolute minimum number of crosspoint switches for the
`devices, such as PNPN rectifiers or transistors, or elec
`above-described connector requirements, viz., and odd
`25
`tromechanical elements such as relays.
`number of symmetrically-connected switching stages each
`The over-all network is symmetrical to facilitate the
`including square switches of a like size.
`fabrication thereof and also to simplify the associated
`common control circuit which may advantageously be of
`SECTION 1-PRELIMINAREES
`the type disclosed in the aforementioned Paul applica
`The symbol CN, NS2, is used to denote the class of all
`tion. Further, the serially-connected switching stages
`connecting networks v with the following properties:
`include square switches to further facilitate the fabrication
`(1) v is two-sided, with N terminals on each side;
`of the present distribution network.
`(2) v is built of an odd numbers of stages 8 k=v, . . . ,
`of Square switches, each stage having N inlets and
`General network structure
`35
`N outlets;
`A distribution network constructed according to the
`(3) v is symmetric in the sense that 8-3-ki for
`principles of the present invention is exactly defined when
`k=1,. . . . , 72 (s-1); and
`the number of switching stages, the composition of each
`(4) Employing the notation
`stage, and the interstage linkage patterns are specified.
`S-s(v)=number of stages of v, n= n(v)=switch size
`The former two criteria are dependent upon the particular
`in the kh stage of v, where v has N/nidentical switches
`value of N, corresponding to the N input and N output
`in the kth stage.
`terminals to be interconnected by the composite distri
`bution network. The precise nature of this dependence is
`The defining conditions of CN imply that
`given hereinbelow.
`- 1
`As is well known, every integer N has associated there
`ki-ki- for k-1,
`.
`with a corresponding prime decomposition into a product
`of prime numbers each raised to an integer exponent. That
`is, for every integer N, there exists a sequence of prime
`factors 2, 3, 5, . . . k such that
`(1)
`N-22.3's .55 . . . k.k.
`where the or exponents may take on any integer value
`including zero. For example, the integer 126 has the prime
`decomposition.
`(2)
`126-21. 32.50.71
`Also, it is well known that there is only one, unique prime
`decomposition for any particular integer.
`With the above in mind, a distribution network embody
`ing N inlets and N outlets is derived as follows. The case
`where the number of switching stages S is given by
`S -(2 o)-1
`(3)
`2.
`will be considered. In this case, the central switching stage
`includes N/k square switches each comprising k inlets
`and outlets. The remaining switching stages are sym
`metrically distributed about the aforementioned central
`stage and comprise N/f square switches each having f
`inlets and outlets, where f is the corresponding prime
`factor included in the prime decomposition of N. Each
`prime factor f gives rise to 2 of switching stages, where
`of is the corresponding exponent of the prime factor f,
`with these switching stages being symmetrically connected
`on both sides of the central switching stage.
`Adjacent ones of the serially-connected switching stages
`
`4 (s--1) TT n=N
`(5)
`k=
`It is assumed throughout that n(v)is 2 for all v and all
`k=1,. . . . , s(v).
`The cost per terminal (on a side) c(v) of a network
`veCN is defined to be the total number of crosspoints of v
`divided by the number N of terminals on a side. Since
`there are
`Nin a k-trek
`Switches in stage k, the total number of crosspoints is
`(using the symmetry condition)
`S
`S
`N . . .2s N
`
`0.
`
`5
`
`30
`
`40
`
`45
`
`and that
`
`(4)
`
`nk = N 1-1/2(s
`
`%(s-l)
`2
`7,
`
`50
`
`55
`
`60
`
`65
`
`k W
`
`70
`
`25:-Nank ( acro-2'Sn)
`
`(6)
`
`and so
`
`34(s-1)
`c(v) = n.1/2(+1)--2
`2.
`kc1
`
`(7)
`
`A network v is called optimal if
`(8)
`c(v)=min{c(a):pleCN}
`It is clear that the cost per terminal of a network veCN
`75 depends only on the switch sizes, and not at all on the
`
`Page 5 of 10
`
`

`

`3,358,269
`5
`6
`permutations that define the junctor patterns between
`0(v) results from 0(pl.) by adding an occurrence of
`stages.
`Also, it may be observed that given any network
`vieCN there is another network veCN that is rearrangeable
`and differs from v1 only in the fixed permutations that
`are used to connect the stages; in particular v1 and v2 have
`the same number of cross-points. Thus, the problem of
`selecting an optimal rearrangeable network from CN is
`equivalent to that of choosing an optimal network from
`CN, rearrangeable or not. A network in CN can be made
`rearrangeable by changing its junctor patterns at no in
`crease in cost,
`Let
`Definition 1:
`m= m (v) -s ( t = numerical index of the
`middle stage
`and
`n=n(v)=nm (v)=size of middle stage switches.
`Definition 2: 0(v)={n-1, . . . , nim-1}=the set of switch
`sizes (with repetitions) in outer (i.e., nonmiddle) stages.
`Definition 3: w(N)={0(v) : veCN}.
`Remark 1: c(v) = n(v)+2 XX
`Xe00)
`Theorem 1: Let (An) be a point (element) of wN)xX
`with
`
`Thus c(v)2c(u) if and only if
`n(p)Y 2n(u)
`n()(1-1)+40
`2y
`(13)
`itsa
`20
`where x= n(v) and y = n(u)/n (v). Now n (u) >6 implies
`that either
`(i)
`
`5
`
`that is if
`
`25
`O
`
`(ii)
`
`(12)
`
`n(p)
`-
`n(v)=2 and n(v) 24
`
`n (pl.)
`-
`n(v)=3 and m (v) >3
`
`n(v) >3
`
`(9)
`
`30 or
`(iii)
`The condition
`
`7. . y=N
`Then there exists a nonempty set Y CC
`CN Such that
`(10)
`T(v)=(An), veY
`The v's in Y differs only in the permutations between the
`stages, and in the placing of the outer stages, and at least
`one of them is rearrangeable. This result follows from the
`definition of C.N.
`SECTION 2-CONSTRUCTION OF THE BASIC
`PARTIAL ORDERING
`The solution to the problem of synthesizing an optimal
`rearrangeable network from CN will be accomplished as
`follows: first define a mapping T of CN into w(N)xX,
`with X={1, . . . , N}, and a partial ordering 2 of
`T(C); the map T will have the property that c(v) is a
`function of T(v); then prove that (roughly speaking) a
`network v is optimal if and only if T(v) is at the "bottom'
`of the partial ordering, i.e., that c(v) is almost an isotone
`function of T(v).
`To define a partial ordering of a finite set, it is enough
`to specify consistently which elements cover which others.
`Let Z.Z.Z. . . . be sets of positive integers 2N possibly
`containing repetitions.
`Definition 4: Z1 covers Z2 if and only if there are positive
`integers i and k such that k occurs in Zi, j divides k, and
`Z is obtained from Z. by replacing an occurrence of k.
`with one occurrence each of i and k/j.
`Definition 5: Z-27, if and only if there is an integer n
`and sets Z172 . . . Zn such that Z-1 covers Zi, i=0,
`1, . . . n-1 and Z=Z.
`Definition 6: T: v->0 (v), n(p)
`Apartial ordering 2 of T(CN) is defined by the follow
`ing definition of covering:
`Definition 7: Let u, v be elements of C(N) T(u) covers
`T(v) if and only if either
`i(i) n(v) <n (v), n(v) divides n(p), and 0 (v) results
`from 0 (pl.) by adding an occurrence of n(u)/n (v), or
`(ii) n(v)=n (u) and 0(u) covers 0(v).
`SECTION 3. COST IS NEARLY ISOTONE ON T(C)
`Theorem 2: If T(v)2T(u), and n(p) >6, then c(v)ac(u).
`Proof: It is enough to prove the result for u and v such
`that T(u) covers T(v).
`Case (i): n(p) <n (u), n(v) divides n(p), n(v(S2, and
`
`2y
`21st
`35
`is fulfilled in all three cases, and so c(v)2c (pl.).
`Case (ii): n (u)=n (v) and 0(u) covers 0(v). There
`exist integers j, k such that i divides k, is2 in 0(u), and
`40 00) results from 0(u) by replacing one occurrence of k
`with one each of i and k/i. Then
`
`45
`
`xe0)
`. . 2k
`= n(u)=2k+2.j----2X a
`x0)
`
`50
`
`70
`
`. . 2k
`(14)
`=c(u)-2k+2}+;
`Since i divides k and is2, ks2i and ks2k/i, so
`(15)
`ki>2 max (i.)> j+
`and c(v) <c(u).
`Theorem 3: If veCN and 0 (v) do not consist entirely of
`55 prime numbers (possibly repeated), then there exists a
`network u in CN of s(v)--2 stages with c(u)<c(v), and v
`cannot be optimal in CN.
`Proof: There is a value of k in the range 12kam (v)-1
`for which nik is not a prime, say nk=ab. Replace the kth
`60 stage of 2 by two stages, one of N/a axia switches, the
`other of N/b bxb switches. Replace the (s-k-1)th stage
`of 2 by two stages, one of N/b bxb switches, the other of
`N/a axia switches. It is possible to interconnect these
`stages to give a symmetric network pl. that is rearrangeable.
`65
`It is apparent that nm ()=nm() and that 0(v) covers
`0(a). Hence, the argument for case (ii) of Theorem 2
`shows that p, has strictly lower cost than v.
`Corollary 1: If N>6 and is not prime, then a network v
`consisting of one square switch is not optimal.
`SECTION 4. PRINCIPAL RESULTS
`Definition 8: An element T(v) of T(CN) is ultimate if
`there are no pleCN such that T(v) covers T(u).
`Remark 2: T(v) is ultimate if and only if n(v) is
`75 prime and 0 (v) consists entirely of prime numbers.
`
`Page 6 of 10
`
`

`

`3,358,269
`7
`it is true that
`Definition 9: An element T(v) of T (CN) is penulti
`mate if it covers an ultimate element.
`Definition 10: p.m. n=1,2, . . . , is the nth prime.
`Definition 11: r(n) is the prime decomposition of n,
`that is, the set of numbers (with repetitions) such that
`n = p11p.2 . . . pe
`(16)
`if and only if tr(n) contains exactly ox1 occurrences of
`pi, i=1,..., l, and nothing else.
`Definition 12: p is the largest prime factor of N.
`Lemma 1: If p=3 and ND6 is even, then the following
`conditions are equivalent:
`(i) v is optimal
`(ii) T(v) is penultimate and n(v)=6, or 4
`
`S
`(21)
`c(v)2c(u)
`i.e., v is at least as good as a. Among such v, that is best
`for which ris largest.
`Proof: Existence of a rearrangeable veCN satisfying
`T(v)=(M,p) is is given by Theorem 1. For the rest of
`the proof, we observe that r25 and
`
`10
`
`X w.
`
`= r --n (u) - 4a-6y-102 -- c(v)
`
`(22)
`
`" ro-(()) (())
`
`if 4 divides N
`Proof: By Theorems 2,3 only v with n(v)26 and (v)
`consisting entirely of primes can be optimal. Writing
`N=2x3y with x>1 and y21, it is seen that such v must
`have a cost c(v) having one of the forms
`
`25
`
`Since x, y, and z can only assume the values 0 and 1,
`with z=1 if and only if x=y=0, we have c(u)2c(v)
`the best v corresponding to the largest r.
`-
`20
`Definition 13:
`Q={(4, r): r a prime and A= r()
`Definition 14: L-T-1(O).
`Remark 2: Q consists of all the absolute minima in
`the partial ordering 2 of T(CN), i.e., v c L implies that
`there are no u e CN for which
`(23)
`T(a) <T(v)
`30
`Theorem 6: If pd3, then all optimal networks belong
`to L.
`Proof: Let ueCN-L be given. The following shows that
`there exists a veL that at least as good.
`Case 1: There is a sequence use u1, u2, . . . , p with
`35
`unzáv, veL, it (ten)26
`(24)
`T(u)ST(u)s . . . ST(u)
`and such that T(w) covers T(v). Then the numbers
`n(u), i=1,. . . . , n are all >6, and the result follows
`40
`from Theorem 2.
`Case 2: All sequences u=p1, p.2, . . . , pin, v with
`unzy, veL, T(p1)sT(u2)s . . . ST(un), and such
`that T(a) covers T(v), are such that n (un)26. Consider
`such a sequence. Let i be the smallest index i for which
`45
`n(u)=26, i=1, . . . , n. Then Theorem 2 gives
`
`The least of these is either of the last two, which corre
`spond to n(v)=6 if x=1, or to n(v)=6 or 4 if x.) 1.
`It is apparent that (ii) is equivalent to (iii).
`Lemma 2: If p=2, and ND4, then the following con
`ditions are equavalent:
`(i) v is optimal
`(ii) T(v) is penultimate and n(v) = 4
`(iii) T() = r() 4.
`Proof: With N=2x it can be seen as in Lemma 1 that
`only those v can be optimal whose cost c(v) has one
`of the forms
`2-22(x-1)
`4-1-22(x-2)]
`The second of these is the better, and corresponds to
`n(v)=4.
`Theorem 4: Let u be a network such that a prime
`humber ird n(u) occurs in 0(u). Let M result from 0(u)
`by replacing one occurrence of r by n(p). Then for any
`network v with
`(17)
`T(v)=(M,r)
`(18)
`c(v) <c(pl.)
`i.e., v is strictly better than p. Among such v, that is best
`for which ris largest.
`Proof: Existence of a rearrangeable v satisfying
`
`it is true that
`
`is guaranteed by Theorem 1. For the rest of the proof,
`observe that ron (a) and
`
`Since n (u)26 and T(w) covers T(v), it follows that
`0 (pi) contains an occurrence of pc3. Hence by Theorem
`50
`5 there exists a network neCN with n(n)=p and
`(25)
`c(n)2c(u)2c (pl.)
`Let &sll be such that n(3) = p and T(n) covers T(8).
`Then c(3)2c(n) by case (ii) of Theorem 2. Hence
`55
`c(8)2c (pl.)
`(26)
`&c.
`Theorem 7: If Na6 and v is optimal, then v is a square
`switch and c(v)=N.
`Proof: For prime N with 22NC6 the result is patent.
`60
`If N=6 and veCs then exactly one of the following al
`ternatives obtains:
`
`xeM
`
`(19)
`= r- (u) -- c(v)
`Theorem 5: If n (u)26, n(u)=2x3 y52, some prime
`number r)3 occurs in O(u), and if M results from 0 (pl.)
`by replacing one occurrence of r by x occurrences of 2,
`y occurrences of 3, and z occurrences of 5 then for any
`network veCN with
`
`(20)
`
`75
`
`65
`The first alternative is optimal, and there is exactly one
`veCs such that T(v)=(6, 6), viz., the 6x6 square switch.
`Similarly, if n=4 and veC4, then T(v) = (0, 4) or
`({2}, 2); the former has cost 4, the latter 6.
`70
`Definition 15: For ns2, D(n) is the sum of the prime
`divisors of n counted according to their multiplicity; thus
`if
`
`n = 2^32 ... p.k
`
`(28)
`
`Page 7 of 10
`
`

`

`then
`
`9
`
`k
`D(n) = ty
`X
`(n)
`Pe. Xe(n)
`Definition 16: c(N)=min{c(v) : veC}
`Theorem 8:
`
`(29)
`
`N
`c(N)
`
`Proof:
`Putting together Lemmas 1, 2 and Theorems 1, 2, 3,
`4, 6, and 7 we obtain the following values for the minimal
`cost in crosspoints per terminal on a side for networks
`in CN:
`
`(30)
`
`N if N <6 or N is prime
`p--2D(N1p) if N)6 and either p)3 or N is
`odd
`2D(N12) if N)6 in all other cases
`(i.e., p -2, or p=3
`and N is even).
`
`3,358,269
`10
`N/3 or 10 Switching stages each comprising a 3 x 3 array.
`Finally, the remaining prime factor 2 gives rise to the two
`remaining switching stages 10 and 14 which are symmetri
`cally disposed about the central switching stage 12. The
`stages 10 and 14 each include N/2, or 15 square switches
`each comprising a 2 x 2 matrix array. It is noted that the
`thirty input terminals 20 correspond to the inlets of the
`first stage square switches 101 through 1915, with the
`thirty output terminals corresponding to the outlets of
`the fifteen 2 X 2 square switches 141 through 1415 which
`are included in the fifth switching stage 14.
`With the switching structures described above, it re
`mains only to specify the interstage linkage pattern. As
`indicated hereinabove, the junctors connecting adjacent
`switching stages are connected in the above-described
`5
`overlapping manner. For example, examining the inter
`connections between the second and third switching stages
`11 and 12, note that the junctors emanating from any
`particular square switch 111 through 110 are connected
`to the uppermost free terminals located on consecutive
`20
`square switches 21 through 126 included in the third
`if p)3, N>6
`switching stage 2. More particularly note, for example,
`that the junctors emanating from the switch is are respec
`kär. xia
`tively connected to inlets of the third stage switches 12,
`125 and 126. It is observed from the above that any par
`25
`c(N)=
`if p=3, N>6, N even
`ticular value of N gives rise to a corresponding, rear
`3-2
`ac=3-6(logs N-1)
`rangeable distribution connector which, as indicated by
`Xsar (NPs)
`the above proof, includes a minimum number of cross
`if p=3, N>6, Nodd
`point switches. This connector may advantageously inter
`connect the N inlets and outlets in any desired pattern.
`4+2 X a = 4(logs N-2)=2
`30
`Xer(N14)
`Xer(N12)
`Comparison with prior art connectors
`if p = 2, N>6
`To more fully illustrate the significant crosspoint saving
`which may be effected by the teachings of the present
`(31)
`simplification gives Theorem 8.
`invention, the number of contacts included in an illus
`35
`trative member of the present class of distribution net
`Hence, it may be observed that the general circuit
`works will now be compared with the number of similar
`described hereinabove is an exact minimum for the here
`elements included in prior art, square matrix arrays.
`in-considered class of networks when N is greater than
`Specifically, a comparison will be made for particular
`six.
`values of N given by
`Specific example
`40
`N-5m
`With the above general principles of network con
`where m is any positive integer.
`struction, and the associated proof of minimization de
`For such a network, the total number of crosspoints
`scribed in detail above, a specific, illustrative distribution
`T is given by the product of the number of switching
`network will now be described. Referring to FIGS. 1 (A)
`stages S multiplied by the number of crosspoints per
`and 1.(B), there is shown a distribution switching net
`45
`switching stage C where
`work which connects thirty input terminals 20 with each
`of thirty output terminals 25. Employing the general net
`(35)
`S=2(m)-1)
`work structure described hereinabove, and letting N=30,
`we have the prime decomposition:
`(36)
`C=N/5(5 x 5)=5N
`N-30:21-31.51
`(32)
`(37)
`T= 2m-15N)
`Hence, the number of switching stages S is given by
`(38)
`malogs N
`S=2X cy; -1 =2(1--1-1) -1 =5
`2.
`(1--1-1)
`(33)
`(39)
`T=5N (2. logs N-1)
`wherein the five switching stages are denoted in FIGS.
`Hence, it is observed that the total number of contacts
`1(A) and 1 (B) by the reference numerals ie through 14.
`T varies as N log N. To compare the crosspoints Tem
`The central switching stage 12 includes a plurality of
`ployed in the instant distribution switch, with the N2
`square switches equal in size to the largest prime factor
`number of crosspoints employed in prior art square
`60
`of 30. Hence, each of the switches in the central stage 12
`matrix arrays, let a comparison factor C.F., expressed
`includes a 5 x 15 array of crosspoint contact pairs, with
`as a percentage, be defined as
`each device being represented in FIGS. 1 (A) and 1 (B) by
`100.5N2 logs N-1) 100N (10 logs N-5)
`a heavy dot. The number of Such square Switches in the
`C.F. =
`stage 12 is given by N/5, or 6. The six square switches
`N2
`N
`comprising the third switching stage 12 are identified
`(40)
`by the reference numeral 121 through 126, with the num
`ber 12 representing the switching stage, and the subscript
`symbolizing the particular square switch within the switch
`ing stage.
`The next step in constructing the thirty inlet and out
`let distribution network illustrated in FIGS. 1 (A) and
`1(B) is to choose another prime factor of 30, for Ex
`ample 3. As illustrated in FIGS. 1 (A) and 1 (B), the sec
`ond and fourth switching stages 11 and 13 each include
`
`N if N 36 or N is prime
`p--2
`Xer (NIp)
`6-2
`ac=2
`
`3C
`
`(34)
`
`and
`
`50
`
`Hence,
`But, since
`then
`55
`
`65
`
`70
`
`75
`
`TABLE I
`
`10 logs N-5
`
`C.F.
`
`
`
`2
`3
`4.
`5
`6
`
`5
`5
`35
`35
`35
`55
`
`100
`60
`20
`5, 6
`1.44
`,353
`
`N
`
`5
`25
`125
`625
`3,125
`15,615
`
`Page 8 of 10
`
`

`

`3,358,269
`2
`What is claimed is:
`Table I, supra, illustrates the relationship between m,
`1. A symmetrical distribution network employing
`N, 10 logsW-5, and C.F. for a range of values for in,
`square switches comprising N input and N output ter
`with the comparison factor C.F. being illustrated in FIG.
`minals, where N is any positive integer such that
`2 in graphical form. Thus, for example, in a distribu
`22:38 . . . k"k is the prime decomposition of N into a
`tion connector comprising 625 inlets and outlets, the Sav
`product of prime factors raised to integer exponents, S
`ings in the number of crosspoints required, along with
`switching stages serially connected between said input
`the reduction in the associated cost of the connector fabri
`and output terminals, where S equals
`cation, amounts to the extremely significant factor of
`94.4%. In general, for the larger values of N commonly
`found in operative distribution connectors, the saving be
`comes proportionately larger, and exceeds 99% as N
`becomes greater than 3125.
`Summarizing the basic concepts of the present inven
`tion, a rearrangeable distribution connector made in ac
`cordance therewith includes an odd number of stages each
`15
`comprising a plurality of square switches of a like size.
`Corresponding to N input and output terminals, where N
`is any positive integer such that 2"2:38 . . . k"k is the
`prime decomposition of N into a product of prime num
`bers raised to integer exponents, the composite distribu
`20
`tion switch includes
`
`5
`
`0
`
`2(a)-1
`
`if the largest prime factor of N equals three and N is odd
`or if the largest prime factor of N is greater than three,
`and equals
`
`if the largest prime factor of N equals three and N is
`even or if the largest prime factor of N equals two, each
`of said switching stages including a plurality of square
`switches of equal size.
`2. A combination as in claim 1 wherein each of said
`square switches comprise a plurality of inlets, a like plu
`rality of outlets, and a plurality of switching means con
`necting each of said inlets to each of said outlets.
`3. A combination as in claim 2 wherein the central
`switching stage comprises N/k square switches if said
`largest prime factor equals three and N is odd or if said
`largest prime factor is greater than three, and comprises
`N/4 square switches if said largest prime factor equals two
`or if said largest prime factor equals three and N is even
`and divisible by four and comprises N/6 if said largest
`prime factor equals three and N is even and not divisible
`by four, each of said switches including k inlets and k.
`outlets.
`4. A distribution network comprising N input and N
`output terminals, where N is any positive integer such
`that 22-38 . . . k"k is the prime decomposition of N into
`a product of prime factors raised to integer exponents,
`and S switching stages serially connected between said
`input and said output terminals, where S equals
`
`25
`
`30
`
`35
`
`40
`
`stages if the largest prime factor of N exceeds three or
`if the largest prime factor equals three and N is odd,
`and includes
`
`k
`
`S = 2(S o)-3
`j=2
`stages if the largest prime factor of N equals three and
`N is even or if the largest prime factor equals two.
`Where the number of stages is
`
`the number of square switches included in each stage is
`derived by dividing N by a corresponding prime factor.
`Where the number of stages is
`
`S-2(S a)-3
`
`the number of square switches included in each stage
`45
`other than the middle stage is also derived by dividing N
`by a corresponding prime factor. The number of Switches
`included in the middle stage in the last case is determined
`as follows. When the largest prime factor of N is equal
`to two, the number of switches in the middle stage is N/4
`50
`(from Lemma 2). When the largest prime factor of N
`is equal to three and N is even, the number of switches
`in the middle stage is N/4 if N is divisible by four and
`N/6 otherwise (from Lemma 1).
`The total number of crosspoints included in the instant
`connector is proportional to N log N, which compares
`favorably with the N2 factor characterizing prior art
`square matrix switches.
`It is to be understood that the above-described arrange
`ments are only illustrative of the application of the prin
`ciples of the present invention. Numerous other embodi
`ments may be devised by those skilled in the art withou