System and method for determination of a horizontal minimum of digital values

• US 8,650,232 B2
• Filed: 10/26/2009
• Issued: 02/11/2014
• Est. Priority Date: 10/26/2009
• Status: Active Grant

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Stortz, Rochelle L., Bertram, Raymond A.
• Primary Examiner(s): PEYTON, TAMMARA R
• Application Number:
  US12/605,702
• Publication Number:
  US 20110095785A1
• Time in Patent Office: 1,569 Days
• Field of Search: 708/709, 708/627, 708/700, 708/207
• US Class Current: 708/207
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

A system for fast determination of a horizontal minimum of multiple digital values including a difference circuit and a compare circuit. The difference circuit may include first and second adders in which the first adder compares upper bits of a first digital value with upper bits of a second digital value and provides a first carry output and a propagate output. The second adder compares lower bits of the first digital value with lower bits of the second digital value and provides a second carry output. The compare circuit determines whether the first digital value is greater than the second digital value based on the carry and propagate outputs. Multiple difference circuits may be used to compare each of multiple digital values with every other digital value to provide corresponding compare bits, which are then used to determine a minimum one of the digital values and its corresponding location.

Claims

1. A microprocessor which is programmed to determine a minimum one of at least two binary values, comprising:

a first adder which is configured to add upper bits of a first binary value with inverted upper bits of a second binary value, said first adder configured to provide a first carry output and a first propagate output;

wherein said first adder is configured OR each bit of said upper bits of said first binary value with a corresponding bit of said inverted upper bits of said second binary value to provide a plurality of result bits and is configured to logically AND said plurality of result bits to provide said first propagate output;

a second adder which is configured to add lower bits of said first binary value with inverted lower bits of said second binary value, said second adder configured to provide a second carry output; and

a compare circuit which is configured to determine whether said first binary value is greater than said second binary value based on said first and second carry outputs and said first propagate output.

2. The microprocessor of claim 1, wherein said first and second binary values are unsigned.

3. The microprocessor of claim 1, wherein said first and second adders are configured to perform unsigned binary addition.

4. The microprocessor of claim 1, wherein said first and second binary values are unsigned binary words in which said first and second adders are configured to compare corresponding upper and lower bytes of first and second binary words.

5. The microprocessor of claim 1, wherein said first propagate output indicates whether a carry input would be propagated through said first adder.

6. The microprocessor of claim 1, wherein said compare circuit comprises:

an OR gate having first and second inputs and an output, wherein said first input receives said first carry output and said output indicates whether said first binary value is greater than said second binary value; and

an AND gate having first and second inputs and an output, wherein said first input receives said propagate output, wherein said second input receives said second carry output, and wherein said output is coupled to said second input of said OR gate.

7. A system for fast determination of a horizontal minimum of a plurality of digital values, comprising:

a plurality of difference circuits, each configured to compare a first digital value with a second digital value;

a routing circuit which is configured to route each of the plurality of digital values to at least one of said plurality of difference circuits in order to compare each digital value with every other one of the plurality of digital values;

wherein each of said plurality of difference circuits comprises;

an upper adder configured to compare an upper portion of a first digital value with an upper portion of a second digital value and to provide a corresponding one of a plurality of first carry outputs and a corresponding one of a plurality of propagate outputs; and

a lower adder configured to compare a lower portion of said first digital value with a lower portion of said second digital value and to provide a corresponding one of a plurality of second carry outputs; and

a compare circuit which is configured to combine said plurality of first and second carry outputs and said plurality of propagate outputs to determine a minimum one of the plurality of digital values, wherein said compare circuit comprises;

a first compare circuit which is configured to combine a first carry output, a second carry output and a propagate output of each of said plurality of difference circuits to provide a corresponding one of a plurality of comparison bits; and

a second compare circuit which is configured to determine a minimum one of the plurality of digital values based on said plurality of comparison bits.

8. The system of claim 7, wherein said first compare circuit comprises AND logic and OR logic for each of said plurality of difference circuits, wherein said AND logic is configured to combine said first propagate output with said second carry output to provide a first bit, and wherein said OR logic is configured to combine said first bit with said first carry output to provide a corresponding one of said plurality of comparison bits.

9. The system of claim 7, wherein said second compare circuit is configured to decode said plurality of comparison bits to provide a plurality of minimum bits each identifying whether a corresponding one of the plurality of digital values is a lesser value.

10. The system of claim 7, wherein the plurality of digital values comprise unsigned binary words, wherein said upper portion comprises an upper byte and wherein said lower portion comprises a lower byte of a corresponding digital value.

11. The system of claim 7, wherein said upper adder and said lower adder of each of said plurality of difference circuits are configured to perform unsigned binary addition.

12. The system of claim 7, wherein each of said plurality of first propagate outputs indicates whether a carry input would be propagated through an upper adder of a corresponding one of said plurality of difference circuits.

13. The system of claim 7, wherein the plurality of digital values are stored in a memory, further comprising a location circuit which is configured to identify a location of said minimum one of the plurality of digital values within said memory.

14. The system of claim 7, further comprising:

a memory which stores the plurality of digital values;

said second compare circuit comprising a decode circuit which is configured to decode said plurality of comparison bits to provide a plurality of minimum bits;

a select circuit which is configured to select one of the plurality of digital values stored in said memory as a minimum value using said plurality of minimum bits; and

a location circuit which is configured to provide a location value using said plurality of minimum bits wherein said location value identifies a location of said minimum value within said memory.

15. The system of claim 7, wherein said plurality of difference circuits, said routing circuit, and said compare circuit are integrated on a microprocessor chip.

16. A method of determining a minimum one of a plurality of digital values, comprising:

comparing, by a microprocessor, upper bits of a first digital value with upper bits of a second digital value and providing a first carry output and a propagate output;

comparing, by the microprocessor, lower bits of the first digital value with lower bits of the second digital value and providing a second carry output; and

determining, by the microprocessor, which of the first and second digital values is a lesser value based on the first and second carry outputs and the propagate output;

wherein said comparing upper bits, comparing lower bits and determining being performed by each of a plurality of adder pairs of the microprocessor;

routing, by the microprocessor, each of a plurality of digital values to at least one of the plurality of adder pairs for comparing each digital value with every other one of the plurality of digital values; and

determining, by the microprocessor, a minimum one of the plurality of digital values based on said comparing.

17. The method of claim 16, wherein said determining a minimum one of the plurality of digital values based on said comparing comprises combining a plurality of carry outputs and a plurality of propagate outputs for providing a plurality of compare bits, and decoding the plurality of compare bits.

18. The method of claim 16, further comprising determining, by the microprocessor, a memory location of the minimum one of the plurality of digital values stored within a memory.

19. A microprocessor which is configured to determine a minimum one of at least two binary values, comprising:

a first adder which is configured to add upper bits of a first binary value with inverted upper bits of a second binary value, said first adder configured to provide a first carry output and a first propagate output;

a second adder which is configured to add lower bits of said first binary value with inverted lower bits of said second binary value, said second adder configured to provide a second carry output; and

a compare circuit which is configured to determine whether said first binary value is greater than said second binary value based on said first and second carry outputs and said first propagate output, wherein said compare circuit comprises;

an OR gate having first and second inputs and an output, wherein said first input receives said first carry output and said output indicates whether said first binary value is greater than said second binary value; and

an AND gate having first and second inputs and an output, wherein said first input receives said propagate output, wherein said second input receives said second carry output, and wherein said output is coupled to said second input of said OR gate.