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

comparatordigital-comparatordigital-logic

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?

Best Answer

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:

schematic

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.

Related Topic