# US 2001/0055304 A1 · Switching concentrator

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2001/0055304 A1
- Document ID: US20010055304A1
- Status: Published application
- Kind: A1
- Application number: 09/882,439
- Filed: 2001-06-15
- Published: 2001-12-27
- Earliest claimed: 2000-06-16
- Assignees: Industrial Technology Research Institute
- Inventors: Shuo-Yen Robert Li
- Web page: https://patentgrep.com/patent/US20010055304A1

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An m-to-n concentrator constructed from smaller concentrator/sorters wherein m is not necessarily equal to 2n. For instance, the m-to-n concentrator can be implemented from an └m/2┘-to-n concentrator/sorter, an ┌m2┐-to-n concentrator/sorter, and n sorting cells to thereby produce the desired arrangement of outputs required of the m-to-n concentrator.

## Claims

### Claim 1

An m×m switch having m input ports and m output ports to route m incoming signals, the switch arranged as an m-to-n concentrator, n<m/2, wherein m−n of the m output ports are grouped into a 0-output group while the remaining n output ports are grouped into a 1-output group, and the m incoming signals are compared according to a predetermined order among all possible values of a signal and thus the largest n among the m incoming signals are routed to the 1-output group while the remaining m−n of the m incoming signals are routed to the 0-output group, the concentrator comprising
an └m/2┘-to-n first concentrator/sorter to process ┌m/2┐ of the incoming signals wherein n of the ┌m/2┘ output ports are grouped into a first 1-output group of the first concentrator/sorter and the largest n among the └m/2┘ incoming signals are routed to the first 1-output group,
an ┌m/2┐-to-n second concentrator/sorter to process the remaining ┌m/2┐ of the incoming signals wherein n of the ┌m/2┐ output ports are grouped into a second 1-output group of the second concentrator/sorter and the largest n among the ┌m/2┐ incoming signals are routed to the second 1-output group, and
n sorting cells wherein the k-th one of the sorting cells, k=1, 2, . . . , n, has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter to receive one signal from the specific output port of the first concentrator/sorter as the first one of the two input signals to the k-th sorting cell and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter to receive one signal from the specific output port of the second concentrator/sorter as the second one of the two input signals to the k-th sorting cell and the sorting cell compares the values of its two input signals and routes the one with the larger value to the lower one of its two output ports, and wherein the 1-output group for the m-to-n concentrator comprises the lower output port of all n sorting cells.

### Claim 2 (depends on 1)

The concentrator as recited in claim 1 wherein the └m/2┘-to-n first concentrator/sorter is an └m/2┘×└m/2┘ sorter and/or the ┌m/2┐-to-n second concentrator/sorter is an ┌m/2┐×┌m/2┐ sorter.

### Claim 3 (depends on 1)

The concentrator as recited in claim 1 wherein the first concentrator/sorter and the second concentrator/sorter are connected to the sorting cells as follows: the output port having the largest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the smallest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to a first one of the sorting cells; the output port having the next-largest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the smallest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to a second one of the sorting cells; with the interconnection pattern continuing in this manner so that, finally, the output port having the smallest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the largest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to the n-th one of the sorting cells.

### Claim 4 (depends on 1)

The concentrator as recited in claim 1 wherein the n signals routed to the 1-output group of first concentrator/sorter are ordered from 1 to n in association with increasing signal values and the n signals routed to the 1-output group of second concentrator/sorter are ordered from 1 to n in association with decreasing signal values, and wherein the n sorting cells are interconnected with the two concentrator/sorters such that the k-th output signal in the 1-output group of first concentrator/sorter and the k-th output signal in the 1-output group of second concentrator/sorter serve as the two input signals to the k-th sorting cell.

### Claim 5 (depends on 1)

The concentrator as recited in claim 1 wherein the first concentrator/sorter and the second concentrator/sorter are each constructed from multi-stage interconnection network of sorting cells.

### Claim 6 (depends on 1)

The concentrator as recited in claim 1 wherein the 1-output group of the concentrator includes the lower output port of each of the n sorting cells and the 0-output group of the concentrator includes the upper output port of each of the n sorting cells plus the └m/2┘-n output ports of the 0-output group of the first concentrator/sorter and the ┌m/2┐-n output ports of the 0-output group of the second concentrator/sorter.

### Claim 7

An m×m switch having m input ports and m output ports, the switch arranged as an m-to-n concentrator, n<m/2, wherein m−n of the m output ports are grouped into a 0-output group and the remaining n output ports are grouped into a 1-output group, the concentrator comprising
an └m/2┐-to-n first concentrator/sorter wherein n of the └m/2┐ output ports are grouped into a 1-output,
an ┌m/2┐-to-n second concentrator/sorter wherein n of the ┌m/2┐ output ports are grouped into a 1-output group, and
n sorting cells wherein each of the sorting cells has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter and wherein the n lower output ports of the sorting cells form the 1-output group for the concentrator.

### Claim 8

An m×m switch having m input ports and m output ports to route m incoming signals, the switch arranged as an m-to-n concentrator, n<m/2, wherein m−n of the m output ports are grouped into a 0-output group while the remaining n output ports are grouped into a 1-output group, and the m incoming signals are compared according to a predetermined order among all possible values of a signal and thus the largest n among the m incoming signals are routed to the 1-output group while the remaining m−n of the m incoming signals are routed to the 0-output group, the concentrator comprising
an ┌m/2┐-to-n first concentrator/sorter to process ┌m/2┐ of the incoming signals wherein n of the ┌m/2┐ output ports are grouped into a first 1-output group of the first concentrator/sorter and the largest n among the ┌m/2┐ incoming signals are routed to the first 1-output group,
an └m/2┘-to-n second concentrator/sorter to process the remaining └m/2┘ of the incoming signals wherein n of the └m/2┘ output ports are grouped into a second 1-output group of the second concentrator/sorter and the largest n among the └m/2┘ incoming signals are routed to the second 1-output group, and
n sorting cells wherein the k-th one of the sorting cells, k=1, 2, . . . , n, has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter to receive one signal from the specific output port of the first concentrator/sorter as the first one of the two input signals to the k-th sorting cell and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter to receive one signal from the specific output port of the second concentrator/sorter as the second one of the two input signals to the k-th sorting cell and the sorting cell compares the values of its two input signals and routes the one with the larger value to the lower one of its two output ports, and wherein the 1-output group for the m-to-n concentrator comprises the lower output port of all n sorting cells.

### Claim 9 (depends on 8)

The concentrator as recited in claim 8 wherein the ┌m/2┐-to-n first concentrator/sorter is an ┌m/2┐×┌m/2┐ sorter and/or the └m/2┘-to-n second concentrator/sorter is an └m/2┘×└m/2┘sorter.

### Claim 10 (depends on 8)

The concentrator as recited in claim 8 wherein the first concentrator/sorter and the second concentrator/sorter are connected to the sorting cells as follows: the output port having the largest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the smallest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to a first one of the sorting cells; the output port having the next-largest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the smallest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to a second one of the sorting cells; with the interconnection pattern continuing in this manner so that, finally, the output port having the smallest address among the n output ports of the 1-output group of the second concentrator/sorter and the output port having the largest address among the n output ports of the 1-output group of the first concentrator/sorter are connected to the n-th one of the sorting cells.

### Claim 11 (depends on 8)

The concentrator as recited in claim 8 wherein the n signals routed to the 1-output group of first concentrator/sorter are ordered from 1 to n in association with increasing signal values and the n signals routed to the 1-output group of second concentrator/sorter are ordered from 1 to n in association with decreasing signal values, and wherein the n sorting cells are interconnected with the two concentrator/sorters such that the k-th output signal in the 1-output group of first concentrator/sorter and the k-th output signal in the 1-output group of second concentrator/sorter serve as the two input signals to the k-th sorting cell.

### Claim 12 (depends on 8)

The concentrator as recited in claim 8 wherein the first concentrator/sorter and the second concentrator/sorter are each constructed from multi-stage interconnection network of sorting cells.

### Claim 13 (depends on 8)

The concentrator as recited in claim 8 wherein the 1-output group of the concentrator includes the lower output port of each of the n sorting cells and the 0-output group of the concentrator includes the upper output port of each of the n sorting cells plus the └m/2┘-n output ports of the 0-output group of the first concentrator/sorter and the ┌m/2┐-n output ports of the 0-output group of the second concentrator/sorter.

### Claim 14

An m×m switch having m input ports and m output ports, the switch arranged as an m-to-n concentrator, n<m/2, wherein m−n of the m output ports are grouped into a 0-output group and the remaining n output ports are grouped into a 1-output group, the concentrator comprising
an ┌m/2┐-to-n first concentrator/sorter wherein n of the ┌m/2┐ output ports are grouped into a 1-output,
an └m/2┘-to-n second concentrator/sorter wherein n of the └m/2┘ output ports are grouped into a 1-output group, and
n sorting cells wherein each of the sorting cells has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter and wherein the n lower output ports of the sorting cells form the 1-output group for the concentrator.

### Claim 15

A method for implementing an m-to-n concentrator, n<m/2, comprising
configuring an ┌m/2┐-to-n first concentrator/sorter having a 1-output group,
configuring an ┌m/2┐-to-n second concentrator/sorter having a 1-output group, and
interconnecting the first concentrator/sorter and the second concentrator/sorter with n sorting cells wherein each of the sorting cells has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter and wherein the n lower output ports of the n sorting cells form the 1-output group for the concentrator.

### Claim 16 (depends on 15)

The method as recited in claim 15 wherein configuring the └m/2┘-to-n first concentrator/sorter includes configuring an └m/2┘×└m/2┘ first sorter and/or configuring the ┌m/2┐-to-n second concentrator/sorter includes configuring an ┌m/2┐×┌m/2┐ sorter.

### Claim 17 (depends on 15)

The method as recited in claim 15 wherein n output signals at the 1-output group of first concentrator/sorter are ordered from 1 to n in association with increasing signal values and n output signals at the 1-output group of second concentrator/sorter are ordered from 1 to n in association with decreasing signal values, and wherein interconnecting the n sorting cells includes interconnecting the two concentrator/sorters such that the k-th output signal in the 1-output group of first concentrator/sorter and the k-th output signal in the 1-output group of second concentrator/sorter serve as the input signals to the k-th sorting cell for k=1, 2, . . . , n.

### Claim 18

A method for implementing an m-to-n concentrator, n<m/2, comprising
configuring an ┌m/2┐-to-n first concentrator/sorter having a 1-output group,
configuring an └m/2┘-to-n second concentrator/sorter having a 1-output group, and
interconnecting the first concentrator/sorter and the second concentrator/sorter with n sorting cells wherein each of the sorting cells has a first input port connected to a specific one of the output ports of the 1-output group of the first concentrator/sorter and a second input port connected to a specific one of the output ports of the 1-output group of the second concentrator/sorter and wherein the n lower output ports of the n sorting cells form the 1-output group for the concentrator.

### Claim 19 (depends on 18)

The method as recited in claim 18 wherein configuring the ┌m/2┐-to-n first concentrator/sorter includes configuring an ┌m/2┐×┌m/2┐ first sorter and/or configuring the └m/2┘-to-n second concentrator/sorter includes configuring an └m/2┘×└m/2┘ sorter.

### Claim 20 (depends on 18)

The method as recited in claim 18 wherein n output signals at the 1-output group of first concentrator/sorter are ordered from 1 to n in association with increasing signal values and n output signals at the 1-output group of second concentrator/sorter are ordered from 1 to n in association with decreasing signal values, and wherein interconnecting the n sorting cells includes interconnecting the two concentrator/sorters such that the k-th output signal in the 1-output group of first concentrator/sorter and the k-th output signal in the 1-output group of second concentrator/sorter serve as the input signals to the k-th sorting cell for k=1, 2, . . . , n.

### Claim 21

The methodology and construction for m-to-(m−n) concentration, 1≦n<m/2, associated with a particular order among all possible values of an input signal by adapting the methodology and construction, as in any of the preceding claims, for m-to-n concentration associated with the reverse of said order.
