Deterministic routing method for minimal switch circuits
First Claim
1. A method for routing a set of N inputs taken M output groupings at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:
- (a) ordering said set of N inputs into a first order;
(b) selecting one of said N inputs;
(c) locating one of said M output columns coupled to said one of said N inputs;
(d) assigning said one of said M output columns to said one of said N inputs; and
(e) iteratively repeating steps (b), (c), and (d) for the remaining said N inputs until all of said N inputs has been assigned to a unique one of said M output columns, wherein if all of said N inputs cannot be assigned one of said M output columns, then shifting said set of N inputs to produce a second order of said set of N inputs and then repeating steps (b), (c), (d) and (e) using said set of N inputs in the second order until all of said N inputs have been routed.
1 Assignment
0 Petitions
Accused Products
Abstract
A deterministic routing method for switch matrices. The routed matrix receives N input signals and produces M output signals on M output columns. The method of the present invention has three steps. First, each of the M output columns in the switch matrix is searched for each of N separate input signals. Secondly, each of the N inputs is assigned to its located column. If all of the N inputs cannot be assigned to one of the M columns, the set of inputs is shifted and the steps are repeated until all of the N inputs are routed.
-
Citations
13 Claims
-
1. A method for routing a set of N inputs taken M output groupings at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:
-
(a) ordering said set of N inputs into a first order; (b) selecting one of said N inputs; (c) locating one of said M output columns coupled to said one of said N inputs; (d) assigning said one of said M output columns to said one of said N inputs; and (e) iteratively repeating steps (b), (c), and (d) for the remaining said N inputs until all of said N inputs has been assigned to a unique one of said M output columns, wherein if all of said N inputs cannot be assigned one of said M output columns, then shifting said set of N inputs to produce a second order of said set of N inputs and then repeating steps (b), (c), (d) and (e) using said set of N inputs in the second order until all of said N inputs have been routed. - View Dependent Claims (2, 4, 5)
-
-
3. A method for routing a set of N inputs taken M outputs at a time in a switch matrix having R inputs rows of switches and M output columns of switches, said method comprising the steps of:
-
(a) ordering said set of N inputs to have an order; (b) selecting one of said N inputs; (c) locating one of said M output columns coupled to said one of said N inputs; (d) assigning said one of said M output columns to said one of said N inputs; and (e) iteratively repeating steps (b), (c), and (d) for each of the remaining said N inputs until all of said N inputs is assigned to a unique one of said M output columns wherein if all of said N inputs cannot be assigned to one of said M output columns, then shifting the order of said set of N inputs according to a number of cycles of said N inputs that occur throughout said matrix and then repeating steps (b), (c), (d) and (e) until all of said N inputs have been routed. - View Dependent Claims (6)
-
-
7. A method for routing N inputs taken M outputs at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:
-
(a) ordering said set of N inputs, said step of ordering producing an ordered set of said set of N inputs; (b) searching each of said M output columns for one of said N inputs; (c) assigning one of said M output columns to said one of said N inputs; (d) marking said one of said M output columns as taken; and (e) repeating steps (a) through (e) for the next of said N inputs in said ordered set and all non-taken ones of M output columns until all of said N inputs in said set have been assigned, wherein if all of said N inputs in said set cannot be assigned to a separate one of said M outputs columns, said method further includes the step of shifting said N inputs in said ordered set in a cyclical manner and then repeating steps (a) through (e). - View Dependent Claims (9, 10, 11)
-
-
8. A method for routing N inputs taken M outputs at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:
-
(a) ordering said set of N inputs, said step of ordering producing an ordered set of said set of N inputs; (b) searching each of said M output columns for one of said N inputs; (c) assigning one of said M output columns to said one of said N inputs; (d) marking said one of said M output columns as taken; and (e) repeating steps (a) through (e) for the next of said N inputs in said ordered set and all non-taken ones of M output columns until all of said N inputs in said set have been assigned, wherein if all of said N inputs in said set cannot be assigned to a separate one of said M output columns said method further includes the step of shifting said N inputs in said ordered set and then repeating steps (a) through (e), wherein the order of said N inputs is shifted according to the number of cycles of said N inputs occur throughout said matrix. - View Dependent Claims (12)
-
-
13. A method for routing a set of N inputs taken to M outputs in a switch matrix having R input rows of switches and M output columns of switches, said method comprising the steps of:
-
(a) ordering said set of N inputs into an order; (b) selecting one of said N inputs; (c) locating one of said M output columns coupled to said one of said N inputs; (d) assigning said one of said M output columns to said one of said N inputs; (e) repeating steps (b), (c), and (d) for successive ones of said N inputs until each of said N inputs is assigned to a unique one of said M output columns; and (f) if step (e) fails, such that each of said N inputs is not assigned to a unique one of said M output columns then; discarding all previous assignments, shifting the order of the N inputs a number of positions, and repeating steps (b) through (f) until each of N inputs has a unique output assigned to it.
-
Specification