0
\$\begingroup\$

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?

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Start with 1 bit. Expand to 2. Extend to 4. \$\endgroup\$ Nov 25, 2017 at 4:11
  • \$\begingroup\$ Hmm need to solve some big k maps. Using only gates, will make it too complex. \$\endgroup\$
    – Mitu Raj
    Nov 25, 2017 at 5:25
  • \$\begingroup\$ no. start bith 1 bit, \$\endgroup\$ Nov 25, 2017 at 7:27

4 Answers 4

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is indeed a simple way to achieve the desired result, but definitely not the fastest (that is, with shortest propagation delay). I tried first building a 4-bit comparator, then for each of the four inputs, I compare it to the other three (using three 4-bit comparators in each comparison) and check whether it is smaller than all three other inputs. This uses a total of twelve 4-bit comparators, resulting in a more complicated circuit. However, each comparison can be done simultaneously and does not have to wait for the result of others, thereby reducing the critical path of the circuit. \$\endgroup\$
    – Mike Lee
    Dec 1, 2017 at 4:29
2
\$\begingroup\$

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.

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Hm, op asked for a combinatorial circuit, you give him an iterative algorithm \$\endgroup\$ Nov 25, 2017 at 10:50
  • \$\begingroup\$ no, it's an iterative description of the logic to use \$\endgroup\$ Nov 25, 2017 at 18:15
  • \$\begingroup\$ so, that's still an iterative description of something combinatorical. I must admit I don't see how the translation is easy/implied enough for this to actual answer the question, but I do see your point more clearly now. \$\endgroup\$ Nov 25, 2017 at 18:20
  • \$\begingroup\$ so is are many hardware design languages, this problem has many repeated elements, and so will most solutions \$\endgroup\$ Nov 25, 2017 at 18:26
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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