Method and apparatus for determining minimum/maximum of multiple data

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.