US 4,539,549 A · Method and apparatus for determining minimum/maximum of multiple data words

Abstract

A method and apparatus for very rapidly determining a minimum or maximum data word from a list of such words in which the expected time for completing the determination of the minimum or maximum value decreases as the number of words in the list is increased. Each data word is stored in a dedicated processing element. Each processing element first outputs onto an open-collector bus a "0" in a position corresponding to the highest order "1" bit in the stored data word. The data signal thus assembled on the bus thus has a "0" at positions corresponding to the highest order "1" bit of each of the processing elements. In response to this data signal, a single controller transmits back to the processing elements a control signal having a "0" in and only in the lowest order "0" bit of the data signal received on the bus. In the processing elements, ones of the processing elements which have a "1" bit in a higher position than the single "0" bit of the control signal are eliminated, while in processing elements still active, " 1" bits are eliminated from the stored data word in the same position as the "0" of the control signal. The most significant "1" bit of the modified control word in each processing element is again determined, and the process repeated until only a single processing element, or multiple processing elements in which the same data word is stored, is left transmitting back to the controller. In that processing element is stored the minimum or maximum data word.

Claims21

Dependent claims

A method for determining a minimum/maximum among a plurality of data words, comprising the steps of:

(a) storing each of said data words in a corresponding processing element;
(b) outputting from each of said processing elements a first multi-bit signal having a predetermined bit state only in a position corresponding to the position of the highest order non-zero bit of the data word stored in the processing element;
(c) eliminating from said second multi-bit signal said predetermined bit state in all positions except for a lowest order position in said predetermined bit state to provide a third multi-bit signal;
(e) deactivating ones of said processing elements having a data word having a non-zero bit in a higher position than said lowest order position in said third multi-bit signal;
(f) in each processing element not deactivated, eliminating any non-zero bit from said data word in the same position as said lowest order position in said third multi-bit signal;
and
(g) repeating, with respect to each processing element not deactivated, said steps (b) to (f) until only a single processing element or plural processing elements in which are stored the same data word remain active.

4 more elements

A method for determining a minimum/maximum among a plurality of data words, comprising the steps of:

(a) storing each of said data words in a corresponding processing element;
(b) in each of said processing elements, producing a first multi-bit signal having a "1" bit of the data word stored in the processing element;
(c) in each of said processing elements, complementing said first multi-bit signal;
(d) in each of said processing elements, outputting the complemented first multi-bit signal onto an open-collector bus to provide a second multi-bit signal;
(e) complementing said second multi-bit signal from said bus;
(f) storing the complemented second multi-bit signal;
(g) providing a third multi-bit signal having a "1" only in a bit position corresponding to the position of the lowest order "1" bit of the stored complemented second multi-bit signal;
(h) eliminating ones of said processing elements having a data word having a "1" bit in a bit position higher than the position of said "1" bit in said third multi-bit signal;
(i) in each of said processing elements not deactivated, eliminating any "1" bit from the data word stored therein in the same bit position as said "1" bit in said third multi-bit signal;
and
(j) repeating, with respect to each of said processing elements not deactivated, said steps (b) to (i) until one of said processing elements which is not deactivated produces an all-zeros value as a result of said step (i).

8 more elements

An apparatus for determining a minimum/maximum among a plurality of data words, comprising:

A. a plurality of processing elements, each of said processing elements comprising:
(1) means for for storing a respective one of said data words;
(2) means for producing a first multi-bit signal having a "1" bit in a position corresponding to the position of a highest "1" bit in the data word stored in the processing element;
(3) means for eliminating from said data word a "1" bit in the same position as a "1" bit in a control signal;
and
(4) means for comparing said control signal with said multi-bit signal and deactivating the processing element unless said control signal and said multi-bit signal are the same;
B. means for providing a second multi-bit signal as a bit-by-bit logical OR of said first multi-bit signals from ones of said processing elements which are not deactivated;
and
C. controller means comprising means for producing said control signal by eliminating all but a lowest order "1" bit from said second multi-bit signal.

6 more elements

An apparatus for determining a minimum/maximum among a plurality of data words, comprising:

A. an open-collector bus including a plurality of data lines and a completion signal line;
B. a plurality of processing elements, each of said processing elements comprising:
(1) a first bus transceiver having a bus port coupled to said open-collector bus;
(2) a first register for storing data from a data output port of said bus transceiver;
(3) a second register for storing a respective one of said data words;
(4) an S-R latch register;
(5) first gating means for loading a value stored in said second register into said S-R latch register through S inputs of said S-R latch register at the beginning of a minimum/maximum determination procedure;
(6) second gating means for inputting to said S-R latch register through R inputs thereof an output value from said first register;
(7) leading one detector means having an input port coupled to an output port of said S-R latch register and an output port coupled to a data input port of said first bus transceiver;
(8) comparator means for producing an output signal in an active state when values present on first and second input ports thereof are unequal, said first input port of said comparing means being coupled to said outputs of said first register and said second input port of said comparing means being coupled to said output port of said leading one detector;
(9) a latch for storing said output of said comparing means;
(10) third gating means for controlling a transmit/receive state of said first bus transceiver in accordance an output of said latch;
and
(11) open-collector logical OR means having inputs coupled to said output port of said leading one detector and an output coupled to said completion signal line;
and
C. a controller comprising:
(1) a second bus transceiver having a bus port coupled to said open-collector bus;
(2) a fourth register for storing a data value from a data output port of said second bus transceiver;
(3) trailing one detector means having input port coupled to an output port of said fourth register, an output port of said trailing one detector being coupled to a data input port of said bus transceiver;
and
(4) a control unit for generating control signals for sequentially activating said first and second bus transceivers, said first, second, S-R latch and fourth registers, said first through third gating means, and said latch.

18 more elements

Dependencies are inferred from the claim text.

Method and apparatus for determining minimum/maximum of multiple data words

Life of this patent

Method and apparatus for determining minimum/maximum of multiple data words

Life of this patent

Abstract

Claims21