Patent Publication Number: US-4057711-A

Title: Analog switching system with fan-out

Description:
TABLE OF CONTENTS 
     1. abstract of the disclosure 
     2. background of the invention 
     A. field of the Invention 
     B. prior Art 
     3. SUMMARY OF THE INVENTION 
     4. brief description of the drawings 
     5. detailed description 
     6. theory 
     7. switch matrix 14a 
     8. SWITCHING SYSTEM 10 
     9. output amplifier circuits 
     10. input amplifiers 
     11. matrix controller 
     12. operation 
     A. rth-Order Conflict Transfer 
     B. limit Cycles 
     C. description of Flowchart 
     13. TABLE OF COMPONENTS 
     14. program for computer 20 
     A. an Example of a 16 × 32 Matrix Using Program 
     BACKGROUND OF THE INVENTION 
     A. Field of the Invention 
     This invention relates to the field of art of matrix switching networks. 
     B. Prior Art 
     In about the last 10 years, analog-hybrid simulation systems have improved considerably but there has not been a corresponding improvement in automating the process of programming analog-hydrid computers. Accordingly, analog-hybrid computers have still required their analog components to be patched together by hand in a patch board. There has been prior work directed toward the development of practical hardware for automatic patching as described in Hannauer, G.: &#34;Automatic Patching for Analog and Hybrid Computers&#34;, Simulation, May 1969; Starr., D. and Jonsson, J. J.: &#34;Design for an Automatic Patching System&#34;, Simulation, June 1968; Hannauer, G.: IEEE Transactions on Computers, December 1968; Gracon, T. and STrauss, J.: &#34;A Decision Procedure for Selection Among Proposed Automatic Analog Computer Patching Systems&#34;, Simulation, September 1969; Howe, R. M., Moran, R. and Berge, T.: &#34;Time-Sharing of Hybrid Computers Using Electronic Patching&#34;, Simulation, September 1970; and, Shoup, J. F. and Adams, W. S.: &#34;A Practical Automatic Patching System for a Time-Shared Hybrid Computer&#34;, Simulation, April 1972. 
     In addition, the following laid open Japanese patent applications have also investigated this problem: lay-open No. 15057/1972, &#34;Automatic Connector for Analog Computers&#34;; lay open No. 16052/1972, &#34;Interconnecting System for a Hybrid Computer&#34;; lay-open No. 18244/1972, &#34;Automatic Connection Type Analog/Hybrid Computer&#34;; lay-open No. 77736/1973, &#34;Hybrid Computer&#34;; lay-open No. 78852/1973, &#34;Hybrid Computer&#34;; and, lay-open No. 79651/1974, &#34;Central Exchange Automatic Connection System for Analog Computers&#34;. 
     Much of this prior art has been patterned after the three stage interconnecting network or switching matrix of Clos, C.: &#34;A Study of Non-blocking Switching Networks&#34;, Bell System Tech. J., Vol. 32, pp. 406-424, 1953 and Duguid, A. M.: &#34;Structural Properties of Switching Networks&#34;, Brown University, Progress Report BTL-7, 1959. 
     Generally, in these three stage interconnecting networks, it has been known that as connections are being made between input and output, at a certain point a switch block in a stage may not be able to make a certain connection. This is defined as a &#34;block&#34;. In designing a switching matrix it has been known to attempt to provide a minimum number of switch blocks in order to have a nonblocking condition. For example, the above cited Clos article describes the design of such a network assuming nonblocking with a minimum number of switches based upon one input being connected to only one output. However in analog-hybrid applications, this one-to-one relationship is not necessarily used and there are other factors involved. 
     Specifically, in such analog-hydrid computers, connections may be rearranged or rerouted during programming if a blocked condition is found in a given path of interconnection. Thus a flexibility in manipulating connections is important since, for example, it may be desirable in a program to connect one input to any one or more of differing sets of integrators. While one method of rearrangeability is described in the cited Duguid article, both the Duguid and Clos systems assume as in telephone switching that each output is connected to exactly one input. However, in analog patching an analog-hybrid computer, it is frequently required that a particular component feed many other components. As for example, an output of a component may be a variable to be used as an input to several equations which defines &#34;fan-out&#34;. Accordingly, the prior art has left much to be desired in an operable system which implements a minimum number of switching units for an optimal switching matrix to achieve both fan-out and rearrangeability or rerouting. Such a system while initially designed for analog-hybrid computer applications may have applications in other fields such as trunking long lines of analog signals generated by transducers. 
     SUMMARY OF THE INVENTION 
     An analog matrix switching system having fan-out for switching each of a plurality of analog signal sources to one or more predetermined analog signal destinations. A three stage switch matrix includes input, middle and output switch blocks with each switch block having input and output terminals. Each switch block also includes a plurality of analog switch means and latching means. The latching means are adapted for coupling any one input terminal of a switch block to any one or more of the output terminals of that block. A matrix controller is coupled to each of the switch blocks for addressing each switch block and actuating at least one of the latching means to provide a connection assignment for at least one of the analog switch means. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A illustrates in basic block diagram form a switch matrix embodying the invention; 
     FIG. 1B illustrates in basic block diagram form an embodiment of the switch matrix of FIG. 1A; 
     FIG. 2 illustrates in basic block diagram form an analog switching system including the switch matrix of FIG. 1B; 
     FIG. 3A-B illustrate in somewhat more detail switch blocks of FIG. 1B; 
     FIG. 3C illustrates in more detail and in block diagram form a basic switch block of FIGS. 1B, 2 and 3A-B; 
     FIG. 4 illustrates in more detail and in block diagram form an output amplifier circuit of FIG. 2; 
     FIG. 5 illustrates in more detail an input amplifier circuit of FIG. 2; 
     FIG. 6 illustrates in more detail and in block diagram form a matrix controller of FIG. 2; 
     FIG. 7 illustrates connections in a set O arranged so that they map without any conflict into set N; 
     FIGS. 8A-B taken together illustrate a flowchart showing an algorithm to be solved by the computer program; and 
     FIGS. 9A-B illustrate tree diagrams for subroutines QROUTE and QPATCH respectively. 
    
    
     DETAILED DESCRIPTION 
     Referring now to FIG. 1A, there is shown an asymmetrical three stage interconnecting network or switch matrix 14 which comprises a first stage of input switch blocks 40 1-X , a second stage of middle switch blocks 42 1-Y  and a third stage of output switch blocks 44 1-Z . 
     As shown in FIG. 1A, each of the blocks in matrix 14 has the same number of inputs 1-n and the same number of outputs 1-m. The inputs to block 40 X  and the outputs to block 44 Z  are as indicated. In view of the equations shown in FIG. 1A, matrix 14 has a total of N input terminals and M output terminals. 
     THEORY 
     Asymmetrical three stage interconnecting network 14 may be denoted by 
     
         V (Y, N, n, M, m)                                          (1) 
    
     These terms have been defined in FIG. 1A and follow the above cited articles by Clos and Duguid. 
     In order to provide rearrangeability, the parameters of network 14 denoted by equation 1 must satisfy the condition 
     
         Y ≧ max (n, m, + m.sub.e) m ≧ n              (2) 
    
     where m e , the middle block excess, in defined: 
     
         m.sub.e = (m.sub.a - m.sub.b)/2                            (3) 
    
     
         m.sub.a = min (M/m, n)                                     (4) 
    
     
         m.sub.b = min (m-n, n)                                     (5) 
    
     Equation 2 can be verified by building model circuits and trying out the connections. 
     For example, in the matrix of FIG. 2, for equation 1 the minimum condition of the number of middle blocks may be calculated as follows: 
     
         A (64 × 128) matrix V (Y, 64, 8, 128, 8) 
    
     
         m = 8, n = 8 
    
     
         m.sub.a = min (16, 8) = 8 m.sub.b = min (0, 8) = 0 
    
     
         m.sub.e = (m.sub.a - m.sub.b)/2 = 4 
    
     
         Y ≧ max (8, 8, 12) ≧ 12 
    
     The minimum total number of switches required by equation 1 may be formulated by the following 
     
         S = V (Y, N, n, M, m)                                      (6) 
    
     The minimization problem is formulated as 
     
         min V (Y, N, n, M, m)                                      (7) 
    
     subject to the constraint that the network is rearrangeable as given by equation 2. 
     Parameters m and n can be set equal for which the rearrangeability constraint provides: 
     
         Y = max (m, m, m + m/2) = (3m)/2 (for M/m ≧ n)      (8) 
    
     The total number of switches is given by: ##EQU1## 
     A one dimensional minimization along m gives: ##EQU2## 
     Therefore, 
     
         S = 3 ∛ MN (M + N)                                (11) 
    
     where S = the sum of the analog switches where analog switch 48 has 64 of such switches. 
     For the example of FIGS. 2 and 3C, the number of switches in accordance with equation 8 provides 
     
         S = 3 ∛ 128 × 64 × 192 ≃ 3730 switches (12) 
    
     Thus, equation 9 defines a completely rearrangeable nonblocking situation by means of a 64 × 128 three stage matrix. However, as now described, less than 3730 switches may be used so that matrix would not be completely rearrangeable nonblocking but would be &#34;mostly&#34; nonblocking. 
     SWITCH MATRIX 14a 
     While each of the switch blocks of matrix 14 in FIG. 1A has n input terminals and m output terminals, it will be understood that in a practical system, a switch block will have a given number of inputs and outputs depending upon the number of analog switches in the switch block. In FIG. 1B, there is shown a switch matrix 14a which comprises eight input blocks 40 1-8 , eight middle blocks 42 1-8  and 16 output blocks 44 1-16 . However, only one input, middle and output block have actually been illustrated for purposes of simplicity. Each of the input and output switch blocks has been selected to have 64 analog switches configured in an 8 × 8 matrix (basic switch block 48). On the other hand as shown in FIGS. 1B and 3B, each of the middle blocks comprises two basic blocks 48 configured in an 8 × 16 matrix. 
     Thus, in the discussion to follow with respect to switch matrix 14a, it will be understood that the matrix contains a total of 40 basic blocks 48. Since each basic block contains 64 analog switches, there is a total of 2560 switches which is less than the theoretical minimum of 3730 switches set forth in equation 9. Thus, matrix 14a would not be completely nonblocking. 
     As will later be described in detail with respect to basic block 48, any one of the eight output terminals may be connected to any one of the eight input terminals but no more than one input terminal may be connected to any one output terminal. Any one input terminal may be connected to one or more terminals which is defined as &#34;fan-out&#34;. Accordingly, as shown in FIG. 1B for example, in input block 40 1 , any input terminal may fan-out to any one of the output terminals; in middle block 42 2 , any input terminal may fan-out to any one of the output terminals; and in output block 44 3 , any input terminal can fan-out to any one of the output terminals. In this manner, any input terminal such as input terminal 12 1  may be connected to any number or all of the output terminals 13 1-128 . 
     However, in the embodiment of FIG. 1B, there is shown only one connecting link from input block 40 1  to middle block 42 2  and from that middle block to output block 44 3 . However, there may be more than one connecting link from the input block to the middle block and more than one connecting link from the middle block to the output block. 
     The specific interconnection made between input, middle and output blocks as for example shown in FIG. 1B, may be expressed in the form of a matrix table as follows in which the block sizes and number of blocks are reduced for purposes of explanation. 
     
                                           Table I                                 
__________________________________________________________________________
 INPUT BLOCK                                                              
        OUTPUT BLOCK 44.sub.1                                             
                        OUTPUT BLOCK 44.sub.2                             
                                        OUTPUT BLOCK 44.sub.3             
40.sub.1                                                                  
        13.sub.1                                                          
            13.sub.2                                                      
                13.sub.3                                                  
                    13.sub.4                                              
                        13.sub.9                                          
                            13.sub.10                                     
                                13.sub.11                                 
                                    13.sub.12                             
                                        13.sub.17                         
                                            13.sub.18                     
                                                13.sub.19                 
                                                    13.sub.20             
__________________________________________________________________________
12.sub.1                                                                  
        *               *               *                                 
12.sub.2    *               *               *                             
12.sub.3        *               *               *                         
12.sub.4            *                                                     
INPUT BLOCK                                                               
40.sub.2                                                                  
12.sub.9                            *                                     
12.sub.10                                           *                     
12.sub.11                                                                 
12.sub.12                                                                 
__________________________________________________________________________
 
    
     In Table I, an * in the cell formed by the intersection of a column and a row indicates a connection statement between the indicated input and output terminals. 
     This type of representation shown in the matrix of Table I lends itself to mathematical representation as well as to computer programming of the interconnections. A matrix table generally would contain N × M number of cells while in the example of Table I, there are 96 cells i.e., 12 columns by 8 rows. 
     Table I can be simplified by showing the interconnections between the input terminals and the output blocks (IOBA) as follows. 
     
                       Table II                                                    
______________________________________                                    
INPUT BLOCK   OUTPUT BLOCKS                                               
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub.1      *         *        *                                        
12.sub.2      *         *        *                                        
12.sub.3      *         *        *                                        
12.sub.4      *                                                           
INPUT BLOCK                                                               
40.sub.2                                                                  
12.sub.9                *                                                 
12.sub.10                        *                                        
12.sub.11                                                                 
12.sub.12                                                                 
______________________________________                                    
 
    
     In general, the matrix shown in Table II may have N ×(M/m) number of cells. 
     Similarly, the following table represents a sample of the interconnection between the middle blocks and the output blocks (MOB) 
     
                       Table III                                                   
______________________________________                                    
             OUTPUT BLOCKS                                                
______________________________________                                    
MIDDLE BLOCKS  44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
42.sub.1       *        *        *                                        
42.sub.2       *        *        *                                        
42.sub.3       *        *        *                                        
42.sub.4       *        *                                                 
42.sub.5                         *                                        
______________________________________                                    
 
    
     In general, the matrix of Table III contains Y ×(M/m) cells. 
     The information relating to the input and output connections such as those shown in Tables I-III are stored in a computer memory for use in implementing the connections in switching matrix 14. The manner in which this stored information is used will later be described. 
     SWITCHING SYSTEM 10 
     As shown in FIG. 2, switch matrix 14a is a part of a switching system 10. Switching system 10 may be an automatic patching system for an analog-hybrid computer in which analog computing devices are coupled to analog inputs 11 1  -11 64  and to analog outputs 16 1  -16 128 . And thus, system 10 operates to effectively patch the devices together in accordance with signals from matrix controller 18. Further, in another application the analog inputs may be from predetermined analog signal sources and the analog outputs 16 1  -16 128  are coupled to other control or computing elements. 
     Analog inputs 11 1-64  are coupled through input amplifier 23 to matrix 14a while the output of matrix 14 is coupled by way of lines 13 1  -13 128  through output amplifier circuits 25 to analog outputs 16 1  -16 128 . System 10 includes a matrix controller 18 having a data line 28, a load strobe line 30 and the block select line 32 which are applied to switch matrix 14a. In addition, lines 28 and 32 are also applied to output amplifier 16. Further, controller 18 provides a reset line 34 for amplifier 16. Computer 20 is coupled to controller 18 by means of data lines 26, select line 24 and a load line 22. 
     In matrix 14a of system 10, the efficient use of an optimal network of switches may be expressed by substituting in equation 1, viz, V (8, 64, 4, 128, 8). In the operation, later to be described, it will be shown how this type of network may be used in making nonblocking connections between the inputs and outputs by rearranging the conflicts. 
     Basic switch block 48 as shown in FIG. 3A has input and output terminals indicated as 12 1-8  and 41 1-8 . It will be understood that these terminals may be any group of the respective input and output terminals of any selected input or output block shown in FIGS. 1A and 2. 
     Latch select lines 46a-c are used for selecting one of the output terminals. Latch input lines 46b-d are used to select one of the eight input terminals 41 1-8 . In addition, load strobe line 30 is used for selecting the loading of internal latches and switches while line 32 is used to enable block 48 for loading of data. 
     It will be understood that FIG. 3B comprises two 8 × 8 basic switch blocks 48 with the same lines 30, 32 and 46a-f of FIG. 3A. 
     Referring now to FIG. 3C, there is shown in detail the circuitry of the basic 8 × 8 switch block 48. Block 48 comprises eight 1 of 8 analog switches or eight channel multiplexers 60a-h. Associated with switches 60a-h are respective three bit latches (1 of 8 registers) 58a-h. In order to start the loading of block 48, a block select signal is applied to line 32 which enables the loading of block 48 by way of gate 50. Specifically, gate 50 is effective to enable each of NAND gates 54a-h which is coupled to latches 58a-h respectively. The latch select signals are applied by way of lines 46a-c to a 1 of 8 selector 52 which is effective to enable one of the gates 54a-h. In this manner, one of the latches 58a-h is selected which is associated with the enabled gate 54a-h. 
     Accordingly, upon application of a load strobe signal to line 30 and latch input signals to lines 46d-f, the selected latch may be loaded with the information on lines 46d-f. Similarly, all of the remaining latches are consecutively loaded by data on lines 46-f. In this manner, latches 58a-h are loaded with the connection assignment for block 48 in eight strobe frames. Each of the latches actuates its respective analog switch 60a-h in accordance with the information loaded in the latch. It is in this manner that switch block 48 is controlled with the effective latching of the connection assignment for that block. 
     It is in this manner that any one of the eight outputs 13 1-8  may be connected to any one of the eight inputs 43 1-8 . Further, if the connection assignments for switches 60a-h are such that input terminal 43 1  may be coupled to more than one of the output terminals and in fact may be coupled to all of the output terminals 13 1-8 . However, no more than one of the input terminals can be coupled to any one of the output terminals. In other words, two input terminals may not be connected by means of switches 60a-h, to one output terminal. 
     It will be understood that FIG. 3C has been shown with input terminals 43 1-8  and output terminals 13 1-8 . However, these eight input terminals and eight output terminals may be any one of the eight input terminals or output terminals of any one of the input and output blocks. Only one of the basic switch blocks is required to be described in detail. 
     When block 48 is used as an output block as shown in FIGS. 3C, the output of switches 60a-h are applied by way of respective amplifiers 62a-h to output terminals 13 1-8  respectively. Amplifiers 62a-h are not used when blocks 48 form input and middle blocks. 
     Amplifiers 62a-h are each operational amplifiers coupled in a voltage follower mode. In this mode, the operational amplifier provides an extremely high input impedance. This is particularly important since switch 60a may appear as a substantially pure resistor of approximately 500 ohm, for example. Thus, if switch 60a would feed an amplifier having a lower input impedance, then a relatively high error would be provided. As a result of this extremely high input impedance of amplifiers 62a-h, it is only necessary that the output blocks have these amplifiers and not the middle or input blocks. 
     OUTPUT AMPLIFIER CIRCUITS 
     Output amplifier circuit 25 1  is shown in detail in FIG. 4. It will be understood that output terminals 13 1-4  are applied to output amplifier circuit 25 1 . Thus terminals 13 5-8  are applied to circuit 25 2 , terminals 13 9-12  are applied to circuit 25 3 , . . . and terminals 13 125-128  are applied to circuit 25 32 . Since all of the amplifier circuits 25 1-32  are identical, only one of them will be described in detail. 
     The purpose of circuit 25 1  is to act as a driver to ground an input to a respective output amplifier when that amplifier is not used to pass an analog signal. Output amplifier select signals are applied by way of lines 46a-c to a 1 of 4 decoder 90. More particularly, line 46c is applied through an inverter 84 to a NAND gate 88 the other input of which is coupled through an inverter 86 to block select line 32. Decoder 90 selects one of the four similar amplifier subunits 15a-d to be grounded. Specifically, decoder 90 is effective to address one of the amplifier subunits 15a and make a determination if that subunit is to be grounded. Thereafter, the next subunit 15b is addressed and so on. In this manner, none or any one or more of the amplifier subunits may be grounded. 
     More particularly, decoder 90 is effective to first enable gates 92a and 94a if that amplifier subunit 15a is to be grounded. Thereafter, a load strobe signal on line 30 sets flip-flop 96a which is effective through gate 98a to ground amplifier 104a. 
     INPUT AMPLIFIERS 
     Input amplifier circuit 23 1  is shown in detail in FIG. 5 and is identical with the remaining input amplifier circuits 23 2-64 . The purpose of circuit 23 1  is to buffer the analog input and to also precision attenuate the input by a factor of 10. Accordingly, an input resistor 66 and a shunt resistor 68 are provided at the amplifier input 67. Further, a feedback resistor 74 is also provided. Input resistor 66 may have a value of 99.99 kohms and resistor 68 may have a value of 11.11 kohms. In this way, the input is attenuated by a factor of 10. 
     MATRIX CONTROLLER 
     Matrix controller 18 is shown in detail in FIG. 6. Controller 18 decodes the 16 data lines 26 (shown in FIG. 6 as lines 26 0-15 ) in order to select a specific one of the blocks 48 by way of block select lines 32 1-40 . In addition, controller 18 provides delayed load strobe by way of line 30, delayed reset by way of line 34 and buffered data by way of lines 28. 
     In order to select a desired block, lines 26 4-9  are buffered and inverted and applied as shown in FIG. 6 and Table IV. These lines are applied through respective NAND gates 111a-e to BCD to decimal decoders 110a-e. The outputs of these decoders are applied through respective inverters to provide signals on lines 32 1-40 . 
     Data lines 26 13-15  as shown in Table IV are buffered by a group of buffers 122 which provide output lines 46a-c which are used (1) for the latch select in blocks 48 and (2) for the output amplifier select in circuits 25 1-32 . Similarly, lines 26 10-12  are applied through buffers 120 which provide three lines 46d-b which are used as the latch input by block 48. The load signal on line 22 is applied through a monostable multivibrator 112 which provides a delaying pulse on load strobe line 30. Further, the select signal on line 24 is applied through a monostable multivibrator 114. The output of mono 114 and the inverted data pulse from data line 26 1  are applied to a NAND gate 116 to generate a reset pulse on line 34. 
     The data format for loading switch matrix 14 is shown in the following table. 
     
                                           Table IV                                
__________________________________________________________________________
 ##STR1##                                                                 
__________________________________________________________________________
 
    
     As previously described, the data on line 26 1-15  contains information related to block select, latch input, output amplifier select and latch select. 
     The following table shows the data word format on lines 26 1-15  for resetting one of the output amplifier circuits 25 1-32  to ground. 
     
                                           Table V                                 
__________________________________________________________________________
 ##STR2##                                                                 
__________________________________________________________________________
 
    
     OPERATION 
     There will now be explained the operation of system 10 when it is necessary to produce a mostly nonblocking rearrangeable connection system. The connection assignments between inputs and outputs are stored in computer 20 in the form of connection statements. A connection statement is generally expressed as 
     
         G (p, q)                                                   (10) 
    
     Where &#34;p&#34; represents an input interconnection and &#34;q&#34; represents the output interconnection. 
     The connection statement represented by the function G(p,q) is used to represent the function in the form of matrices in a computer memory. During operation, middle blocks are assigned using other rearrangements. This rearrangement consists of several basic operations which will now be described. 
     A move operation is a sequence of one or more transfers of connections in the same output block set, from one middle block set to another in order to get the network from a blocked state to an unblocked state. The following shows a network which is in a blocked state since the connection x is presented with an input block conflict and hence it cannot be made. 
     
                       Table VI A                                                  
______________________________________                                    
 INPUT BLOCK   OUTPUT BLOCKS                                              
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub.1       1        1                                                 
12.sub.2       2        2                                                 
12.sub.3       3        3                                                 
INPUT BLOCK -40.sub.2                                                     
12.sub.9       4                                                          
 12.sub.10              ○x                                         
 12.sub.11                                                                
______________________________________                                    
IOBA                                                                      
BLOCKED CONN: 2,2                                                         
 
    
     As shown in the following table, unblocking of the connection x by a move operation is indicated by the arrows. 
     
                       Table VI B                                                  
______________________________________                                    
 ##STR3##                                                                 
______________________________________                                    
 
    
     in the following table there is shown an MOB array for the same state of the network. 
     
                       Table VII A                                                 
______________________________________                                    
 ##STR4##                                                                 
______________________________________                                    
 
    
     connection (2) cannot be entered in the fourth row of the second column since entry (2,1) is already in that row. However, by moving the entry (1,3) to row 4, column 2, connection (2,2) becomes unblocked and can now be placed in the row 3, column 2 without giving rise to any conflicts as shown as follows. 
     
                       Table VII B                                                 
______________________________________                                    
             OUTPUT BLOCKS                                                
______________________________________                                    
MIDDLE BLOCKS  44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
40.sub.1       1,1      1,1                                               
40.sub.2       1,2      1,2                                               
40.sub.3       1,3      2,2                                               
40.sub.4       2,1      1,3                                               
40.sub.5                                                                  
______________________________________                                    
MOB                                                                       
UNBLOCKED                                                                 
 
    
     While this example shows a sequence which involved only one move operation, the operation may easily be extended to sequences consisting of several such move operations. 
     The process of assigning middle blocks to connections in an output block set is a mapping operation as shown in FIG. 7 where the connections in the set, 0, have to be arranged in a combination such that they map without any conflict onto a bigger set, N. If this mapping cannot be done by rearranging the elements of set, O, the set N, may be configured such that it will accept the set, O, in one of its states, provided the network is rearrangeable. 
     A. rth-Order Conflict Transfer 
     If a rearrangeable network in a blocked state cannot be unblocked by rearranging the elements of a set of output blocks, O, (i.e., no permitted state exists for the set, O), then the conflicts must be transferred to the set, N, in order to unblock the network. A transfer, which results from a state of the set, O, such that single conflicts are caused in exactly r subsets of the set, N = (O i ), is called an rth order conflict transfer. The order of conflict transfers arising in a network according to equation 1 is in the average equal to its expansion factor (M/N) minus 1. 
     For example, in the following table the output block set, O 3  does not map in any of its states in the set, N = (O 1 , O 2 ). However, in the state shown, it represents a single conflict with only one subset, O 2  of the set N. The transfer of conflict from the set, O 3  to O 2  is therefore, a first order conflict transfer. 
     
                       Table VIII A                                                
______________________________________                                    
 INPUT BLOCK   OUTPUT BLOCKS                                              
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub.1       4        4        4                                        
12.sub.2       3        3        ○1                                
12.sub.3       2        ○1                                         
                                 2                                        
INPUT BLOCK                                                               
40.sub.2                                                                  
12.sub.9       1                                                          
 12.sub.10              2                                                 
 12.sub.11                       3                                        
______________________________________                                    
 
    
     B. Limit Cycles 
     Under certain conditions, conflict transfers between output block sets may result in limit cycle oscillations, viz, computation loops. Table VIII A shows transferring of the conflict from output block set, O 3  to O 2  which could produce a number of next states for the network three of which are as follows. 
     
                       Table VIII B                                                
______________________________________                                    
 INPUT BLOCK   OUTPUT BLOCKS                                              
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub. 1      4        4        4                                        
12.sub.2       3        1        1                                        
12.sub.3       2        2        2                                        
INPUT BLOCK                                                               
40.sub.2                                                                  
12.sub.9       1                                                          
 12.sub.10              3○                                         
 12.sub.11                       3○                                
______________________________________                                    
 
    
     
                       Table VIII C                                                
______________________________________                                    
 INPUT BLOCK   OUTPUT BLOCKS                                              
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub.1       4        ○1                                         
                                 4                                        
12.sub.2       3        3        ○1                                
12.sub.3       2        2        2                                        
INPUT BLOCK                                                               
40.sub.2                                                                  
12.sub.9       1                                                          
 12.sub.10              4                                                 
 12.sub.11                       3                                        
______________________________________                                    
 
    
     
                       Table VIII D                                                
______________________________________                                    
 INPUT BLOCK   OUTPUT BLOCKS                                              
40.sub.1       44.sub.1 44.sub.2 44.sub.3                                 
______________________________________                                    
12.sub.1       4        4        4                                        
12.sub.2       3        3        1                                        
12.sub.3       2        2        2                                        
INPUT BLOCK                                                               
40.sub.1                                                                  
12.sub.9       ○1                                                  
 12.sub.10              ○1                                         
 12.sub.11                       3                                        
______________________________________                                    
 
    
     If the next state, indicated by the next succeeding Table VIII B is chosen, then the conflict 3 in 0 2  must again be transferred back to 0 3 . The network could thus oscillate forever between the states indicated by Tables VIII A - VIII B. 
     The state of an output block set, 0, consisting of i elements has i- permutations. The rearrangement procedure allows the systematic filtering through the possible permutations and arrive at a permitted state of the set, 0, which maps into N. 
     A drop state in any column means to jump from the present state to the next lower state as dictated by the element in that column. For example, as set forth in the following table if the present state is, for example, 7, and it is desired to drop that state in column 2, then the next lower state would be 9. If from state 7, the state were dropped in column 1, then the next lower state will be 13. 
     
                       Table IX                                                    
______________________________________                                    
COLUMNS                                                                   
STATES 1         2         3       4                                      
______________________________________                                    
1      4         3         2       1                                      
2      4         3         1       2                                      
3      4         2         3       1                                      
4      4         2         1       3                                      
5      4         1         3       2                                      
6      4         1         2       3                                      
7      3         4         2       1                                      
8      3         4         1       2                                      
9      3         2         4       1                                      
10     3         2         1       4                                      
11     3         1         4       2                                      
12     3         1         2       4                                      
13     2         4         3       1                                      
14     2         4         1       3                                      
15     2         3         4       1                                      
16     2         3         1       4                                      
17     2         1         4       3                                      
18     2         1         3       4                                      
19     1         4         3       2                                      
20     1         4         2       3                                      
21     1         3         4       2                                      
22     1         3         2       4                                      
23     1         2         4       3                                      
24     1         2         3       4                                      
______________________________________                                    
 
    
     C. Description of Flowchart -- FIGS. 8A-B 
     The computer program later to be given is designated to solve the algorithm shown in the flowchart in FIGS. 8A-B. The algorithm assigns middle blocks to all connections arising from the first input terminal and sequentially moves to the last input terminal. Initially, it assigns middle blocks. If any connection gets blocked, then it uses a move operation to unblock it. If the move operation fails, then it performs an ordered rearrangement of the connections in that output block set to resolve the conflict. If a permitted state for the connections in that output block set can be found this way, it moves onto the next connection statement. Otherwise, it performs a first order conflict transfer. With respect to the present program, if either the sequence of these first order transfers leads to a limit cycle or a first order transfer does not exist at all, then the algorithm halts. If the transfers and the following rearrangements can get the network to an unblocked state, then the process moves on to the next connection statement. 
     TABLE OF COMPONENTS 
     In matrix switching system 10, the following components have been used for the operation and function herein described. 
     
         __________________________________________________________________________
REFERENCE                                                                 
CHARACTER                                                                 
        COMPONENT    MODEL NO.                                            
                             MANUFACTURER                                 
__________________________________________________________________________
52, 90  Decoder      CD 4028 RCA                                          
58a-f   Latch        CD 4042 RCA                                          
60a-f   1 of 8, 8 channel                                                 
        multiplexer  DG 508C Analog Devices                               
62a-f, 76,                                                                
104a-d  Operational Amplifier                                             
                     AD 518K Analog Devices                               
96a-f   Set-Reset Flip-Flop                                               
                     CD 4043 RCA                                          
110a-e  BCD to Decimal                                                    
        Decoder      7442    Texas Instruments                            
112, 114                                                                  
        Monostable                                                        
        multivibrator                                                     
                     74121   Texas Instruments                            
__________________________________________________________________________
 
    
     PROGRAM FOR COMPUTER 20 
     A program for computer 20, later set forth in detail, is written in the FORTRAN language and is effective to perform the functions above described. Accordingly, the program comprises the following routines which have been categorized into routing routines, switch matrix patching routines, print routines and a miscellaneous routine. 
     
         __________________________________________________________________________
Routing Routines                                                          
QROUTE:           Route a connection set.                                 
FILL:             Assign middle blocks to connections                     
                  from a matrix input pin.                                
ICONF:            Conflict function.                                      
MAXM:             Find index for maximum variable                         
MOVE:             Move connections to unblock a &#34;blocked&#34;                 
                  connection.                                             
FIND:             Find a non-conflicting connection.                      
MATCH:            Rearrange connections in a column to                    
                  unblock or transfer conflict                            
NCOF:             Find columns with conflict.                             
DROP:             Permutation generator.                                  
Switch Matrix Patching Routines                                           
QPATCH:           Patch a routed connection set.                          
QWPATH:           Patch a single path through matrix.                     
QRESET:           Reset output amplifier switches.                        
QWDO:             Issue a DO instruction.                                 
QWDF:             Issue a DF instruction.                                 
Print Routines                                                            
QWIOBA:           Print IOBA array for a connection set.                  
QWMOB:            Print MOB array for a connection set.                   
JNA:              ASCII table.                                            
DTB:              Decimal to binary converter.                            
DISP              Printout of MOB array.                                  
Miscellaneous Routine                                                     
MONT:*            Return to system monitor.                               
__________________________________________________________________________
 
    
     A tree diagram for subroutine QROUTE is shown in FIG. 9A and a tree diagram for subroutine QPATCH is shown in FIG. 9B. 
     The functional specification of the QROUTE subroutine is as follows. A connection assignment is accepted by way of an array (ISET) specifying the matrix input and matrix output pairs to be connected and properly routed through the connection network. The result of the routing algorithm is returned in an array MID, elements of which represent the middle blocks through which the corresponding matrix input-output pair in array ISET is to be connected. The array ISET, augmented with the array MID, defines completely a network state which will realize the connection assignment specified by ISET. 
     The calling sequence for QROUTE is: 
     
         ______________________________________                                    
CALL QROUTE (MAXPAR, ISET, MID, IERR)                                     
______________________________________                                    
MAXPAR  A 5 word array containing the matrix parameters:                  
MAXPAR  Same as matrix parameter N - number of input                      
(1)=KN  terminals in the connection network.                              
MAXPAR  Same as matrix parameter n - number of input                      
(2)=NN  terminals per input block in the connection                       
        network.                                                          
MAXPAR  Same as matrix parameter Y - number of middle                     
(3)=KK  blocks in the connection network.                                 
MAXPAR  Same as matrix parameter M - number of output                     
(4)=KM  terminals in the connection network.                              
MAXPAR  Same as matrix parameter m - number of output                     
(5)=MM  terminals per output block in the connection                      
        network.                                                          
ISET    A complete set of KM elements specifying the                      
        matrix input-output terminals to be connected.                    
         ##STR5##                                                         
        where J = Integer {1, ---KN} or φ.                            
        Subscript I denotes a matrix output terminal,                     
        J denotes a matrix input terminal and the                         
        equality sign denotes a connection between                        
        that pair.                                                        
        ISET(I) = φ                                                   
        represents nothing is connected to the Ith                        
        output pin or I is an &#34;open&#34; output terminal.                     
        The set must be complete means that every                         
        element of the set must either be φ or                        
        belong to Integer {1, ---, KN}.                                   
______________________________________                                    
 
    
     mid is defined as a subroutine output array of length KM, in which each element represents the middle block through which the corresponding matrix input-output connection in array ISET should be made. 
     In the computer program, equation 1 has been changed to be expressed as V, (N, n, Y, M, m). 
     A. An Example of a 16 × 32 Matrix Using Program 
     The following is an example of switch routing and loading routine usage using a 4 × 4 switch block with the switch matrix being 16 × 32 with 4 input blocks, 4 middle blocks and 8 output blocks. ##SPC1## 
     The computer program written in FORTRAN language follows. ##SPC2## ##SPC3##