# US 7,072,922 B2 · Integrated circuit and process for identifying minimum or maximum input value among plural inputs

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

- Number: US 7,072,922 B2
- Document ID: US7072922B2
- Status: Granted
- Kind: B2
- Application number: 10/319,219
- Filed: 2002-12-13
- Published: 2004-06-17
- Granted: 2006-07-04
- Earliest claimed: 2002-12-13
- Assignees: LSI Logic Corporation
- Inventors: Alexander E. Andreev; Anatoli A. Bolotov; Igor Vikhliantsev
- Web page: https://patentgrep.com/patent/US7072922B2

## CPC

- G06F 9/30021: {Compare instructions, e.g. Greater-Than, Equal-To, MINMAX}
- G06F 7/22: Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Apparatus and process identifies a maximum or minimum value among a plurality of binary values on a plurality of a-bit wide wires in an integrated circuit module. An N-bit vector K is calculated based on n most significant bits of all a-bit binary signals, where N=2n. M N-bit vectors K—0, . . . ,K_(M−1) are calculated based on the n most significant and the m least significant bits of all a-bit binary signals, where M is at least 2m−1. A table is constructed from vectors K—0, . . . ,K(M−1) to create table vectors. A table vector is selected based on vector K, is used to derive a vector P, which in turn is used to select another table vector. The minimum or maximum binary value is identified from the two selected table vectors.

## Claims

### Claim 1

Apparatus for identifying a maximum or minimum value among a plurality of values represented by respective a-bit binary signals on a plurality of a-bit wide wires in an integrated circuit module, the apparatus comprising:
first means responsive to the a-bit binary signal on each of the plurality of wires to calculate an N-bit vector K based on n most significant bits of all a-bit binary signals and to calculate M N-bit vectors K_0, . . . ,K_(M−1) based on the n most significant bits and m least significant bits of all a-bit binary signals, where n=a−m, N=2n, M is at least 2m−1 and m is either a/2 or (a−1)/2;
second means responsive to vectors K_0, . . . ,K(M−1) for calculating N table vectors;
third means responsive to vector K for selecting one of the table vectors to derive a vector P;
fourth means responsive to vector P for selecting a table vector; and
an output for calculating the minimum or maximum binary value from the vectors selected by the third and fourth means.

### Claim 2 (depends on 1)

Apparatus of claim 1, wherein each a-bit binary signal is represented by a respective a-bit vector, W_1, . . . ,W_s, and the first means comprises:
a first segmenter for segmenting each a-bit vector into respective n-bit first portions and m-bit second portions,
a first conjunctor responsive to the n-bit first portions for generating a plurality of N-bit vectors, kx, each having a bit in a position representing a value of the respective n-bit first portion, and
a disjunctor responsive to the kx vectors for deriving vector K.

### Claim 3 (depends on 2)

Apparatus of claim 2, wherein the first means further comprises:
a second conjunctor responsive to the m-bit second portions for generating a plurality of 2m-bit vectors each having a bit in a position representing a value of the respective m-bit second portion,
a concatenator responsive to the 2m-bit vectors to generate select signals, and
a multiplexer responsive to the kx vectors and to the select signals to generate vectors K_0, . . . ,K_(M−1).

### Claim 4 (depends on 1)

Apparatus of claim 1, wherein the second means comprises:
a table containing vectors K_0, . . . ,K_(M−1) arranged in columns, with each row representing a respective table vector.

### Claim 5 (depends on 4)

Apparatus of claim 4, wherein the table is a concatenation of a first N×n table of binary numbers arranged in order in rows starting from 0 and a second table formed of vectors K_0, . . . ,K_(M−1) arranged in columns such that there are N rows of n+M bits forming table vectors V_0, . . . ,V_(N−1).

### Claim 6 (depends on 5)

Apparatus of claim 5, wherein the third means comprises:
a first hierarchical tree responsive to the bits of vector K to select one of table vectors V_0, . . . ,V_(N−1), and
a third segmenter for segmenting the vector selected by the first tree into an n-bit code and an M-bit vector, and
a generator for generating a vector P based on the M-bit vector.

### Claim 7 (depends on 6)

Apparatus of claim 6, wherein the generator comprises:
a concatenator for concatenating a bit of predetermined value to the M-bit vector to form vector P.

### Claim 8 (depends on 6)

Apparatus of claim 6, wherein the fourth means comprises:
a second table of binary numbers arranged in order in N rows starting from 0 such that each row contains m bits forming table vectors U_0, . . . ,U_(N−1), and
a second hierarchical tree responsive to the bits of vector P to select one of the table vectors U_0, . . . ,U_(N−1) to derive an m-bit code.

### Claim 9 (depends on 8)

Apparatus of claim 8, wherein the output includes:
a second concatenator for concatenating the n-bit code and the m-bit code.

### Claim 10 (depends on 1)

Apparatus of claim 1, further including:
an inverter for inverting each vector W_1,W_2, . . . ,W_s, whereby the output identifies a maximum binary value.

### Claim 11

A process of identifying a maximum or minimum binary value among a plurality of values represented by respective a-bit binary signals on a plurality of a-bit wide wires in an integrated circuit module, the process comprising steps of:
a) calculating an N-bit vector K based on n most significant bits of all a-bit binary signals, where n=a−m, N=2n and m is either a/2 or (a−1)/2;
b) calculating M N-bit vectors K_0, . . . ,K_(M−1) based on the n most significant and the m least significant bits of all a-bit binary signals, where M is at least 2m−1;
c) calculating N table vectors based on vectors K_0, . . . ,K(M−1);
d) selecting one of the table vectors based on vector K;
e) selecting a table vector based on a vector P derived from the table vector selected in step d); and
f) identifying the minimum or maximum binary value among the plurality of values represented by the respective a-bit binary signals on the plurality of a-bit wide wires based on the vectors selected in steps d) and e).

### Claim 12 (depends on 11)

The process of claim 11, wherein each a-bit binary signal is represented by a respective a-bit vector, W_1, . . . ,W_s, and step a) comprises steps of:
a1) segmenting each a-bit vector into respective n-bit first portions and m-bit second portions,
a2) generating a plurality of N-bit vectors, kx, each having a bit in a position representing a value of the respective n-bit first portion, and
a3) disjoining the kx vectors to derive vector K.

### Claim 13 (depends on 12)

The process of claim 12, wherein step b) comprises steps of:
b1) generating a plurality of 2m-bit vectors each having a bit in a position representing a value of the respective m-bit second portion,
b2) concatenating the 2m-bit vectors to generate select signals, and
b3) multiplexing the kx vectors to the select signals to generate vectors K_0, . . . ,K_(M−1).

### Claim 14 (depends on 11)

The process of claim 11, wherein step c) comprises steps of:
c1) arranging vectors K_0, . . . ,K_(M−1) in columns of a table, and
c2) deriving table vectors from respective rows of the table.

### Claim 15 (depends on 14)

The process of claim 14, wherein the table is formed by steps of:
forming a first table having n columns and N rows, the rows being arranged in order to contain binary values starting from 0,
forming second table formed of vectors K_0, . . . ,K_(M−1) arranged in columns, and
concatenating the first and second tables so that there are N rows of n+M bits forming table vectors V_0, . . . ,V_(N−1).

### Claim 16 (depends on 14)

The process of claim 14, wherein step d) comprises steps of:
d1) selecting one of the table vectors V_0, . . . ,V_(N−1) using a hierarchical tree and bits of vector K,
d2) segmenting the vector selected by the tree into an n-bit code and an M-bit vector, and
d3) generating a vector P based on the M-bit vector.

### Claim 17 (depends on 16)

The process of claim 16, wherein step d) further includes:
d4) concatenating a bit of predetermined value to the M-bit vector to form vector P.

### Claim 18 (depends on 16)

The process of claim 16, step e) comprises steps of:
e1) forming a second table having m columns and N rows, the rows being arranged in order to contain binary values starting from 0, and
e2) selecting one of the table vectors U_0, . . . ,U_(N−1) using a hierarchical tree and bits of vector P to derive an m-bit code.

### Claim 19 (depends on 18)

The process of claim 18, wherein step f) comprises:
concatenating the n-bit code and m-bit code.

### Claim 20 (depends on 11)

The process of claim 11, further including, before step a):
inverting each vector W_1,W_2, . . . ,W_s, whereby step f) calculates a maximum binary value.