Method and circuits for performing the quick search of the minimum/maximum value among a set of numbers
US6748405B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 4, 2001 |
| Grant date | Jun 8, 2004 |
| Priority date | — |
| Expiry date | Sep 28, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/30021
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
In the search of the minimum value among a set of p Numbers coded on q bits, each Number is split into K sub-values coded on n bits (q>=K×n). Parameter K thus assigns a rank to each sub-value so that K slices of bits are formed wherein each slice is composed of sub-values of the same rank. Each sub-value is then encoded on m bits (m>n) using a “thermometric” coding technique. A parallel search is then performed on the first slice of encoded sub-values (MSBs) to determine the minimum sub-value of that slice. All the Numbers associated to sub-values that are greater than the minimum sub-value that has been evaluated are deselected. The evaluation process is continued the same way until the last slice (LSBs) has been processed. At the end of the evaluation process, the Number which remains selected has the minimum value. The response time (i.e. the number of processing steps) now only depends upon the number K of sub-values in which the Numbers have been split up. The method applies to search the maximum as well.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.