Method and circuits for performing the quick search of the minimum/maximum value among a set of numbers

A circuit for searching for a desired extreme value, the desired extreme value being one of a minimum value and a maximum value, among a set of p numbers coded in a binary format on q bits, the circuit comprising:

• (a) extreme value evaluation means, including m p-way AND gates, for performing an AND function on each of m bits of a same weight of p m-bit coded binary words;
• and
• (b) p blocks, each block being associated with a number in the set and including
• (1) splitting means to split each number into K sub-values of n bits characterized as n-bit sub-values, where K≧1 and q≦K×n,
• (2) encoding means, connected to said splitting means, for encoding each of the n-bit sub-values on m bits, where m>n, to form m-bit encoded sub-values, said encoding means having an output thereof connected to said extreme value evaluation means,
• wherein the m-bit encoded sub-values formed by said encoding means are output to said extreme value evaluation means to evaluate a desired extreme m-bit encoded sub-value among all the m-bit encoded sub-values, said encoding means using an encoding process allowing evaluation of the desired extreme m-bit encoded sub-value by the AND function, and
• (3) deselecting means, connected to said encoding means, for deselecting the number associated with a given block, when the desired extreme value is the minimum value and an m-bit encoded sub-value corresponding to said number is greater than said desired extreme m-bit encoded sub-value evaluated by said evaluation means, and when the desired extreme value is the maximum value and an m-bit encoded sub-value corresponding to said number is less than said desired extreme m-bit encoded sub-value evaluated by said evaluation means.

A circuit for searching for a desired extreme value, the desired extreme value being one of a minimum value and a maximum value, among a set of p numbers coded in a binary format on q bits, the circuit comprising:

• (a) extreme value evaluation means, including m p-way AND gates, for performing an AND function on each of m bits of a same weight of p m-bit coded binary words;
• (b) decoding means, connected to said extreme value evaluation means, for transforming an m-bit coded word into an n-bit coded word, where n<m;
• and
• (c) p blocks, each block being associated with a number in the set and including
• (1) splitting means to split each number into K sub-values of n bits characterized as n-bit sub-values, where K≧1 and q≦K×n,
• (2) encoding means, connected to said splitting means, for encoding each of the n-bit sub-values on m bits, where m>n, to generate m-bit encoded sub-values, thereby generating encoded words, said encoding means having an output thereof connected to said extreme value evaluation means, said encoding means using an encoding process allowing evaluation of the desired extreme value for all the encoded words generated by all said encoding means using the AND function, and
• (3) deselecting means, connected to said splitting means and to said encoding means, for deselecting a number,
• wherein
• the m-bit encoded sub-value generated by the encoding means is applied, with all the m-bit encoded sub-values generated by other blocks, to the extreme value evaluation means to evaluate the desired extreme m-bit encoded sub-value, and
• the desired extreme m-bit encoded sub-value is applied to the decoding means to generate a desired extreme n-bit coded sub-value which is compared with an n-bit coded sub-value in said deselecting means to generate an exclusion signal to deselect the number associated with a given block, when the desired extreme value is the minimum value and an n-bit coded sub-value corresponding to said number is greater than said desired extreme n-bit coded sub-value, and when the desired extreme value is the maximum value and an n-bit coded sub-value corresponding to said number is less than said desired extreme n-bit encoded sub-value.