3
\$\begingroup\$

Some basics of digital logic are the half-adder and full-adder. We know how to produce the sum of two binary values at the level of AND/OR/NOT gates, in a straightforward way presented in many textbooks. (Never mind any advanced tricks used in real-world high performance chips.) A few tweaks, and we can subtract.

What I don't recall ever seeing is gate-level ways to produce the minimum or maximum of two binary values. Is there such a thing? If so, do any microprocessors use it?

\$\endgroup\$
10
  • \$\begingroup\$ Relative comparisons require cascading through the bits and can't be performed with fewer than log n layers. Another two layers to AND and OR with the input values and you're done. \$\endgroup\$ – Ignacio Vazquez-Abrams Aug 30 '13 at 4:01
  • 1
    \$\begingroup\$ @IgnacioVazquez-Abrams, what do you mean by "can't be performed with fewer than log n layers"? A big enough ROM could do it in 1 step. \$\endgroup\$ – The Photon Aug 30 '13 at 5:00
  • 2
    \$\begingroup\$ @ThePhoton: I looked through my Big List of Gates, but couldn't find one called "ROM". \$\endgroup\$ – Ignacio Vazquez-Abrams Aug 30 '13 at 5:02
  • \$\begingroup\$ @IgnacioVazquez-Abrams Think of it as a really wide fan-in sum-of-products. \$\endgroup\$ – The Photon Aug 30 '13 at 5:04
  • \$\begingroup\$ @IgnacioVazquez-Abrams There is no single gate that can solve this problem, even what you proposed. ROM LUT can certainly be constructed from gates just as your cascade system... \$\endgroup\$ – travisbartley Aug 30 '13 at 5:38
8
\$\begingroup\$

Before considering the min/max, how about just comparing two numbers? Let's say that you have two binary numbers: A and B, and you want to know if A>B. What you do is some simple subtraction, C=B-A. If C is negative, then A was greater than B. With a binary two's compliment number the most significant bit (MSB) will be 1 if the number is negative, and 0 if it is positive. So after the subtraction, a single bit will tell you if A or B is larger.

Now, that was a super simple way to explain it. There are some details that need to be paid attention to.

This works with signed numbers (two's compliment). If A and B are unsigned, you will have to convert them to signed first. All this really means is that you add a zero-bit on the left, and the resulting number is one bit larger. For example, if A=1111(unsigned) then you need to make A=01111(signed).

The other issue is that you need to pay attention to the range of numbers that you are going to use, and make sure that you do not have any overflow/underflow conditions. The usual way I deal with this is to give A and B an extra bit. So an 8 bit signed number will become a 9 bit signed number. You do this by duplicating the top (sign) bit. For example, if A=1000(signed) then A will become 11000(signed).

Once you have correctly done the math, you can use the MSB of C to determine which number is larger. You can then use a simple MUX to select A or B depending on the value of C's MSB.

\$\endgroup\$
1
  • \$\begingroup\$ Subtracting followed by selecting one or the other. Well, that's the obvious way, and currently what's done. I was hoping there'd be a more direct clever way. \$\endgroup\$ – DarenW Aug 30 '13 at 18:50
0
\$\begingroup\$

It's called magnitude comparator and uses less gates than the vanilla solution. See https://stackoverflow.com/questions/10767316/finding-the-maximum-of-two-integers-in-binary-using-bit-logic-only .

The "vanilla" solution of computing the difference and looking at the MSB has the advantage of reusing known "parts" and might save you some design time, depending on your use case. You can at least save all but one gates for the output, since you will be looking only at the MSB.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.