How to design a combinational circuit that finds the minimum among multiple given numbers?

Question

There are quite a few articles (for example, this) that can be found online discussing the design of a comparator that takes two numbers (say, A and B) as inputs, and outputs whether A > B, A < B or A = B. But what if I want to compare multiple numbers?

Let's say we have four 4-bit binary numbers denoted as i0, i1, i2 and i3. I want the output of the circuit to be the index of the minimum value among them. Below are some examples: The highlighted value in each row represents the minimum value among the four which the output should correspond to.

I've thought of comparing the bits one-by-one starting from the MSB, but things got ugly when I tried to realize using combinational gates. Is there any efficient ways to do this?

Answer 1

An approach that is fairly easy to explain is the following idea:

1. Design a functional block that compares two 4-bit values and emits either 0 or 1 to indicate which of the two is lower or same. This is essentially just a comparator, except that you don't need all three outputs, so the logic involved can be a bit less. The logic for this should be within reach of some relatively easy analysis.
2. Apply the above functional block from (1) to accept \$i_0\$ and \$i_1\$ as inputs and use the output as the selector input (\$s_0\$) to a 4-bit bus 2-to-1 MUX, with \$i_0\$ and \$i_1\$ as its two 4-bit bus inputs. The output will be the lessor or same of those two values as \$o_0\$.
3. Apply the above functional block from (1) to accept \$i_2\$ and \$i_3\$ as inputs and use the output as the selector input (\$s_1\$) to a 4-bit bus 2-to-1 MUX, with \$i_2\$ and \$i_3\$ as its two 4-bit bus inputs. The output will be the lessor or same of those two values as \$o_1\$.
4. Apply the above functional block from (1) to accept \$o_0\$ and \$o_1\$ as inputs and use the output as the selector input (\$A_1\$) to a 1-bit 2-to-1 MUX, with \$s_0\$ and \$s_1\$ as its two 1-bit inputs. The output will be \$A_0\$.

The index is then \$A_1..A_0\$.

I'm not saying this is the most efficient method. Only that it is the more obvious and more easily followed method:

^{simulate this circuit – Schematic created using CircuitLab}

I'm sure you can work out the logic for the indicated special function in step (1) above. It's not terribly complicated. The rest is just standard mux logic, which is found almost anywhere you want to look.

This may be a benchmark design. I'll leave the problem of making it still more efficient up to you.

Answer 2

This is the best circuit I came up with for this. It is similar to @JasenСлаваУкраїні's design in his answer, in that it evaluates each bit from most significant to least significant, and excludes any number that "loses" at any bit height. It does this by NAND:ing each bit (at a given height) for all values (to check if anyone had a zero), and if anyone had a zero, each candidate will remove themselves if they did not. They do this with the result of the NAND (that is passed into an OR gate to get the same result as for a multi-input NAND gate) that is fed into an AND together with the input bit value, and the result of this OR:ed with the input to the next bit so that it will always be 1 if the candidate was excluded, and 1 is treated as "excluded" (and does not affect the circuit. ) I then also feed the AND output into an multi-input OR gate (or a hierarchy of first two OR gates then those into one OR gate) and this outputs if the value was the lowest or not. Here is the Logisim file for it: https://snippet.host/xttouz/raw.

Answer 3

Start with the first bit; if any bits in that column are cleared, exclude the input that has it set from further processing, e.g. by OR'ing it with 1111.

Then repeat the circuit for the second bit, and so on.

AND together whatever is left.

Answer 4

if you want a simple way. run the inputs into demultiplexers to convert the 4 bits into 1 of 16 signals. OR those together across inputs and then feed the result to a priority decoder.