Deterministic method and an apparatus for minimal switch circuits

• US 5,530,439 A
• Filed: 09/26/1994
• Issued: 06/25/1996
• Est. Priority Date: 01/24/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Vireday, Richard P., Sturges, Jay J., Steele, Randy C., Hibdon, Gregory B.
• Primary Examiner(s): Horabik, Michael
• Application Number:
  US08/312,422
• Time in Patent Office: 638 Days
• Field of Search: 340/825.79, 340/825.85, 340/825.86, 340/825.89, 340/825.9, 340/825.91, 340/825.83, 370/65, 364/716, 326/41, 326/39, 326/101
• US Class Current: 340/7.1
• CPC Class Codes: G06F 30/30 Circuit design

Abstract

A deterministic method and apparatus for defining the size and switch assignments of a switch matrix. The method operates on a switch matrix having a number of inputs (N) and a number of outputs (M). When constructing the switch matrix, there will be M columns in the matrix. The method determines a minimum number of rows (R) for the switch matrix. The resultant general purpose R×M switch matrix allows any combination of a subset of the N inputs, with up to M members, to be assigned to the outputs. The resultant R×M switch matrix will be smaller than an N×M switch matrix.

Claims

1. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix given a sample size of N number of inputs taken M number of outputs at a time, wherein N and M are positive integers, said switch matrix taking said M number of outputs independent of order, said computer controlled method comprising the steps of:

sizing said switch matrix using said processing logic such that said switch matrix has a plurality of rows of switches and M output columns, said plurality of rows being less in number than the sample size of N number of inputs, wherein each one of said switches in said plurality of rows is coupled to an individual one of said M output columns and each row has M switches; and

coupling said N inputs to M output columns using said switches in said rows, such that said switch matrix outputs M number of outputs in response to each possible combination of M number of inputs.

2. The method defined in claim 1 wherein said step of sizing includes the step of determining said plurality of rows according to the equation ((N-M)+1).

3. The method defined in claim 1 wherein said step of coupling includes the step of distributing said N number of inputs to said switches in said plurality of rows, such that said N number of inputs are as evenly loaded as possible within said matrix with respect to one another.

4. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix having a sample size of N number of inputs taken M number of outputs at a time, wherein N and M are positive integers, said M number of inputs taken independent of order, said computer controlled method comprising the steps of:

determining a number of rows in said switch matrix using said processing logic according to the equation ((N-M)+1), each of said rows having M number of switches;

coupling a plurality of output columns to said plurality of switches, said matrix having M output columns, wherein each of said M output columns is coupled to each of said rows in said matrix at a separate one of said M number of switches; and

distributing said N number of inputs to said switches in said number of rows, wherein each of said N number of inputs is distributed and coupled to a first quantity of switches or to a second quantity of switches, wherein said first quantity is one fewer than said second quantity, such that said N number of inputs are evenly loaded throughout said matrix.

5. In a computer system having processing logic and at least one memory, a computer controlled method of generating a connection matrix given a sample size of N number of inputs taken M number of outputs at a time, each of said outputs coupled to one of M columns, wherein N and M are positive integers, said connection matrix grouping said M number of outputs independent of order, said computer controlled method comprising the steps of:

determining using said processing logic the minimum plurality of rows of switches necessary to produce all possible combinations of said M number of outputs, each of said switches in said rows being coupled to one of said M columns; and

distributing each of said N number of inputs among said switches in said connection matrix, wherein each of said N number of inputs is distributed and coupled to a first quantity of switches or to a second quantity of switches, wherein said first quantity is one fewer than said second quantity, such that said N number of inputs are evenly loaded throughout said matrix, and wherein said connection matrix outputs M number of outputs in response to each possible combination of said M number of inputs.

6. The method defined in claim 5 wherein said step of determining comprises calculating said minimum number of rows according to the equation ((N-M)+1).

7. The method defined in claim 5 wherein if said N number of inputs is evenly divisible by said M number of outputs, said method further comprises the step of redistributing each subsequent cycle of N number of inputs, such that said matrix outputs all possible combinations of M number of inputs.

8. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix having N number of inputs and outputting M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order, said computer controlled method comprising the steps of:

determining using said processing logic the R number of rows of switches required for said switch matrix to output all possible combinations of M number of inputs, said R number of rows equal to ((N-M)+1), each of said plurality of rows having M number of switches, wherein each of said columns is coupled to each of said plurality of rows at a separate switch on said each of said plurality of rows, such that said switch matrix is an R×

M matrix;

distributing each One of the N number of inputs to a separate one of said switches in said switch matrix by assigning and coupling each of the N number of inputs in an order to a separate one of said switches and repeatedly assigning and coupling each of said N number to separate switches in the order until all of said switches are assigned an input.

9. The method defined in claim 8 wherein if said M number is evenly divisible by said N number, each subsequent cycle of N number of inputs is column shifted, such that each N inputs in the cycle assigned to switches in one of said rows is shifted to another one of said switches in said one row, such that said switch matrix outputs M number of outputs in response to each possible combination of M number of inputs.

10. The method defined in claim 9 wherein the number of cycles, S, to distribute the N number of inputs within said matrix of R rows by M columns is given by:

space="preserve" listing-type="equation">S=R/(N/M).

11. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix having N number of inputs and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order, said computer controlled method comprising:

determining using said processing logic a minimum number of rows necessary to produce said M number of outputs, each of said minimum number of rows having an M number of switches, such that each of said M outputs is coupled to each of said minimum number of rows at a separate one of said M number of switches;

distributing the N number of inputs to said switches by cycling the inputs through said matrix, wherein said cycling steps includes, assigning and coupling each of the N number of inputs in an order to a separate one of said switches and repeatedly assigning and coupling each of said N number to separate switches in the order until all of said switches are assigned an input; and

determining using said processing logic whether said matrix outputs M number of outputs for all possible combinations of M number of inputs, such that if said switch matrix does not produce M number of outputs in response to all possible combinations of M number of inputs then said method includes, a step of shifting each cycle of inputs until said switch matrix produces M number of outputs in response to each possible combinations of M number of inputs.

12. The method defined in claim 11 wherein the minimum number of rows is determined according to the equation ((N-M)+1).

13. The method defined in claim 11 wherein said step of determining whether said switch matrix outputs all possible combinations comprises the step of determining whether the number of inputs N is evenly divisible by the number of outputs M.

15. The method defined in claim 11 or claim 14 wherein the step of shifting comprises the steps of:

determining a number of cycles of said N number of inputs are in said switch matrix;

shifting each of the cycles in a predetermined number of switch positions, such that each subsequent cycle is shifted said predetermined number of switch positions more than the previous cycle.

16. The method defined in claim 15 wherein a first cycle of N number of inputs is not shifted.

17. The method defined in claim 15 wherein said cycles in said matrix are shifted one position.

14. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix having N number of inputs and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order, said computer controlled method comprising:

determining using said processing logic a minimum number of rows necessary to produce said M number of outputs, each of said minimum number of rows having an M number of switches, such that each of said M outputs is coupled to each of said minimum number of rows at a separate one of said M number of switches;

distributing using said processing logic the N number of inputs to said switches by,

a) assigning each of said switches in one of said rows a distinct input from said N number of inputs,

b) repeating step (a) for the next of said rows in said matrix using those of said N number of inputs not previously used,

c) repeating step (b) until all of said N number of inputs has been assigned, and

if all of said N number of inputs have been assigned then continue assigning each of said remaining switches in said matrix one of said N inputs in the same order as said N inputs were assigned in steps (a) and (b) on a row by row basis wherein all of said switches are assigned one of said N number of inputs, such that said N number of inputs are within one input of being evenly distributed within said matrix with respect to any of the other of said N number of inputs; and

determining using said processing logic whether said matrix outputs M number of outputs in response to each possible combination of M number of inputs, such that if said switch matrix does not produce M number of outputs for all possible combinations of M number of inputs then said method includes, a step of shifting each cycle of inputs until said switch matrix produces M number of outputs in response to each possible combination of M number of inputs.

18. In a computer system having processing logic and at least one memory, a computer controlled method of generating a switch matrix having switches, N number of inputs, and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order, said computer controlled method comprising:

defining a plurality of rows using said processing logic, wherein each of said plurality of rows has an M number of switches;

cycling N number of inputs to said switches in said matrix by assigning each of the N number of inputs in an order to a separate one of said switches and repeatedly assigning each of said N number to separate switches in the order until all of said switches are assigned an input such that a switch matrix assignment is generated;

determining using said processing logic whether each of said N number of inputs is assigned to said switches in a same column, and if so, modifying the switch matrix assignment by,

identifying a first set of N number of inputs wherein one of said first set is assigned in the same column as one of a previous set of N number of inputs,

identifying a set of rows of said plurality of rows in which said first N number of inputs set reside, and

reassigning each of said first N number of inputs set by rotating one column position assignments made for each row of said set of rows thereby modifying the switch matrix assignment; and

coupling said switch matrix assignment to said switches of said switch matrix.

19. In a computer system having processing logic and at least one memory, a computer controlled method for generating a switch matrix having N number of inputs and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping M number of inputs independent of order, said computer controlled method comprising the steps of:

sizing said matrix using said processing logic such that said switch matrix has R number of rows of switches and M number of outputs, wherein R and M are positive integers and R is equal to the quantity ((N-M)+1), and further wherein each of said switches in said R number of rows are coupled to said M output columns;

distributing each of said N number of inputs among said switches in said switch matrix, wherein each of said N number of inputs is connected to a first quantity of switches or to a second quantity of switches, wherein said first quantity is one fewer than said second quantity, such that said N number of inputs are evenly loaded throughout said matrix, such that said switch matrix outputs M number of outputs for each possible combination of said M number of inputs; and

eliminating rows in said matrix, such that said switch matrix does not output M number of outputs for all possible combinations of M inputs.

20. An apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions for generating a switch matrix given a sample size of N number of inputs taken M number of outputs at a time, wherein N and M are positive integers, said matrix taking said M groups independent of order;

means for sizing said matrix such that said switch matrix has a plurality of rows of switches and M output columns, said plurality of rows being less in number than the number of N inputs, wherein each of said switches in said plurality of rows are coupled to said M output columns; and

means for coupling said N inputs to M output columns using said switches in said rows, such that said switch matrix outputs M number of outputs for each possible combination of M number of inputs.

21. An apparatus for generating a switch matrix having a sample size of N number of inputs taken M number of outputs at a time, wherein N and M are positive integers, said M number of outputs taken independent of order said apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions;

means for determining a number of rows in said matrix according to the equation ((N-M)+1), each of said rows having M number of switches;

means for coupling a plurality of output columns to said plurality of switches, said matrix having M output columns, wherein each of said M output columns is coupled to each of said rows in said matrix at a separate one of said M number of switches; and

means for distributing said N number of inputs to said switches in said ((N-M)+1) rows, wherein each of said N number of inputs is connected to a first quantity of switches or to a second quantity of switches, wherein said first quantity is one fewer than said second quantity, such that said N number of inputs are evenly loaded throughout said switch matrix.

22. An apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions for generating a connection matrix given a sample size of N number of inputs taken M number of outputs at a time, each of said outputs coupled to one of M columns, wherein N and M are positive integers, said switch matrix grouping said M number of outputs independent of order;

means for determining a minimum plurality of rows of switches necessary to produce said M number of outputs, each of said switches in said rows being coupled to one of said M columns; and

means for distributing each of said N number of inputs among said switches in said switch matrix, wherein each of said N number of inputs is connected to a first quantity of switches or to a second quantity of switches, wherein said first quantity is one fewer than said second quantity, such that said N number of inputs are evenly loaded throughout said matrix, wherein said switch matrix outputs M number of outputs for each possible combination of said M number of inputs.

23. An apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions for generating a switch matrix having switches, N number of inputs, and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order;

means for determining a minimum number of rows necessary to produce said M number of outputs, each of said minimum number of rows having an M number of switches;

means for distributing the N number of inputs to said switches by assigning each of the N number of inputs in an order to a separate one of said switches and repeatedly assigning each of said N number of inputs to separate switches until all of said switches are assigned to an input;

means for coupling each switch to an appropriately assigned input; and

means for determining whether said matrix outputs M number of outputs for each possible combinations of M number of inputs, such that if said matrix does not produce M number of outputs for all possible combinations of M number of inputs then said apparatus includes a means for shifting each cycle of inputs until said matrix outputs M number of outputs for each possible combination of M number of inputs.

24. The apparatus defined in claim 23 wherein the minimum number of rows is determined according to the equation ((N-M)+1).

25. The apparatus defined in claim 23 wherein said means for determining whether said matrix outputs all possible combinations comprises the means for determining whether the number of inputs N is evenly divisible by the number of outputs M.

27. The apparatus defined in claim 23 or claim 26 wherein the means for shifting comprises:

means for determining the number of cycles of said N number of inputs are in said switch matrix; and

means for shifting each of the cycles in a predetermined number of switch positions, such that each subsequent cycle is shifted said predetermined number of switch positions more than the previous cycle.

28. The apparatus defined in claim 27 wherein a first cycle of N number of inputs is not shifted.

29. The apparatus defined in claim 27 wherein said cycles in said matrix are shifted one position.

26. An apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions for generating a switch matrix having N number of inputs and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order;

means for determining a minimum number of rows necessary to produce said M number of outputs, each of said minimum number of rows having an M number of switches;

means for distributing each one of the N number of inputs to a separate one of said switches in said switch matrix by,

a) means for assigning each of said switches in one of said rows a distinct input from said N number of inputs;

b) means for repeating step (a) for the next of said rows in said matrix using those of said N number of inputs not previously used;

c) means for repeating step (b) until all of said N number of inputs has been assigned, and

if all of said N number of inputs have been assigned then continue assigning each of said remaining switches in said matrix one of said N inputs in the same order as said N inputs were assigned in steps (a) and (b) on a row by row basis wherein all of said switches are assigned one of said N number of inputs, such that said N number of inputs are within one input of being evenly distributed within said matrix with respect to any of the other of said N number of inputs;

means for coupling each switch to an appropriately assigned input; and

means for determining whether said matrix outputs M number of outputs for each possible combination of M number of inputs, such that if said matrix does not produce M number of outputs for all possible combinations of M number of inputs then said apparatus includes a means for shifting each cycle of inputs until said matrix outputs M number of outputs for all possible combinations of M number of inputs.

30. An apparatus comprising:

a bus;

a processor coupled to said bus;

a storage device coupled to said bus, containing a set of instructions for generating a switch matrix having N number of inputs and producing M number of outputs, each of said M outputs corresponding to a column in said matrix, said switch matrix grouping the M number of outputs independent of order;

means for determining a minimum plurality of rows necessary to produce said M number of outputs, each of said plurality of rows having an M number of switches;

means for cycling N number of inputs to said switches in said matrix, wherein said means for cycling includes means for assigning and coupling each of the N number of inputs in an order to separate one of said switches and repeatedly assigning and coupling each of said N number to separate switches in the order until all of said switches are assigned an input; and

means for determining whether each of said N number of inputs is assigned to said switches in the same column, such that said matrix does not produce M number of outputs in response to each possible combination of M number of inputs then said method includes a step of shifting each cycle of N inputs one column position from the column position of the previous cycle.

31. In a computer system having processing logic and at least one memory, a computer controlled method of generating a R×

M switch matrix having switches, N inputs, and M outputs from a preliminary set of R×

M switch assignments, wherein R and M are a number of rows and columns respectively, and further wherein R, N and M are positive integers and R is less than N, said computer controlled method comprising the steps of;

generating using processing logic an intermediate matrix of N×

M switch assignments having M columns and N rows with each of said N rows corresponding to an individual one of said N inputs, said intermediate matrix generated by marking each column location of each of said N rows with either a marker identical to said individual one if said individual one resides in any row of an individually associated column of said preliminary set of R×

M switch assignments, or with an empty marker if said individual one does not reside in any row of said individually associated column of said preliminary set of R×

M switch assignments;

compressing using processing logic said intermediate matrix of N×

M switch assignments to generate a new matrix of R×

M switch assignments by

identifying using processing logic each empty marker in said intermediate matrix, and

for each identified empty marker moving switch assignments up one row for a partial column segment, said partial column segment being all of a column below said empty marker thereby eliminating all empty markers in said new matrix of R×

M switch assignments; and

coupling said new matrix of R×

M switch assignments to said switches of said R×

M switch matrix.