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\$
  • 2
    \$\begingroup\$ Start with 1 bit. Expand to 2. Extend to 4. \$\endgroup\$ – Ignacio Vazquez-Abrams Nov 25 '17 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 '17 at 5:25
  • \$\begingroup\$ no. start bith 1 bit, \$\endgroup\$ – Jasen Nov 25 '17 at 7:27
2
\$\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\$
  • \$\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 '17 at 4:29
0
\$\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\$
  • 1
    \$\begingroup\$ Hm, op asked for a combinatorial circuit, you give him an iterative algorithm \$\endgroup\$ – Marcus Müller Nov 25 '17 at 10:50
  • \$\begingroup\$ no, it's an iterative description of the logic to use \$\endgroup\$ – Jasen Nov 25 '17 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\$ – Marcus Müller Nov 25 '17 at 18:20
  • \$\begingroup\$ so is are many hardware design languages, this problem has many repeated elements, and so will most solutions \$\endgroup\$ – Jasen Nov 25 '17 at 18:26
0
\$\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, privacy policy and cookie policy

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