0
\$\begingroup\$

Question: Is there an algorithmic way to produce a digital logic circuit for an n-bit majority function? (hopefully reasonably efficient as well).

Motivation: Half adders can be put together to make full adders, which in turn can easily be put together to make an n-bit adder. This is a nice hierarchical solution.

Another nice solution would be a sort of simple logic equation like the one from Wikipedia:

$$\operatorname{Majority} \left ( p_1,\dots,p_n \right ) = \left \lfloor \frac{1}{2} + \frac{\left(\sum_{i=1}^n p_i\right) - 1/2}{n} \right \rfloor. $$, except that this requires adding 1/2 which is not allowed in Boolean logic.

Attempts: For 3 and 4 bit adders, I can come up with a logic circuit from the truth table. Now, you could do this for n bits, but that is not a nice algorithmic solution

\$\endgroup\$
5
  • \$\begingroup\$ Best to search for S. Muroga. In 1959, "The principle of majority decision logic elements and the complexity of their circuits" followed by his book, "Threshold Logic and Its Applications," in 1971. Start there, then find anyone referencing his work in their own work -- look particularly for symmetric boolean functions and threshold functions. \$\endgroup\$
    – jonk
    May 4, 2019 at 4:06
  • \$\begingroup\$ Did my answer truly answer your problem? \$\endgroup\$ May 10, 2019 at 20:56
  • \$\begingroup\$ @HarrySvensson It answered the question I posed originally, but its a problematic solution if the number of inputs large. It scales a bit like factorial. I was thinking there might be something more efficient with gates. Maybe with more than 2 levels. \$\endgroup\$
    – Ion Sme
    May 10, 2019 at 21:00
  • \$\begingroup\$ @IonSme If you are allowed to use hardware, then one comparator and a bunch of resistors can do it all. The reason for why it is so few components in hardware is because you move the problem to having good resistors, good comparator (not op-amp), good shielding from noise. With gates (my answer), all of those problems disappear and you get something that works exactly the same in winter, in a sunny day, 3 in the morning, 3 in the afternoon, in space, on earth. - How is your data actually stored? Like what are you actually dealing with? Sensor inputs? Images? \$\endgroup\$ May 10, 2019 at 21:16
  • 1
    \$\begingroup\$ @IonSme You can add things after each other, you don't have to do it all in parallel, have the values you want to sum in a queue, sum = sum + last in queue, move queue forward, etc. If you want everything in parallel (and digital) then it's going to be very expensive (as my answer shows). In series it's very cheap. Just have a couple of shift registers (a Parallel in, Serial Out) and one adder. Somewhat like this, look for serial adders. \$\endgroup\$ May 10, 2019 at 21:26

2 Answers 2

1
\$\begingroup\$

I believe you only care about odd number of inputs, because even number of inputs doesn't really make sense. Like what is the majority of 2 zeros and 2 ones? I don't know the answer to that. But I do know the majority of 2 zeros and 3 ones, in other words, odd number of inputs.

So let's calculate two majority equations with 3 and 5 inputs and see if we can find any pattern.


With 3 inputs, using Karnaugh maps, you will get this answer if you try to make them all into NAND's:

\$M = \overline{\overline{AB}~\overline{AC}~\overline{BC}}\$

A,B,C are each used 2 times to form all combinations.

The number of grouped NANDs at the input is \${3 \choose 2} = 3\$


With 5 inputs, using Karnaugh maps, you will get this answer:

\$M = \overline{\overline{ABC}~\overline{ABD}~\overline{ACD}~\overline{BCD}~\overline{CDE}~\overline{ABE}~\overline{ACE}~\overline{BCE}~\overline{ADE}~\overline{BDE}}\$

A,B,C,D,E are each used 6 times to form all combinations.

The number of grouped NANDs at the input is \${5 \choose 3} = 10\$


I think I see the pattern and can extrapolate it to get this equation:

  • N = number of inputs (should be odd)
  • Total number of NAND-gates \$ = {N \choose \lceil \frac{N}{2} \rceil }+1\$

So with, say 11 inputs you will have \${11 \choose 6}+1 = 463\$ NAND gates, 462 of them will have 6 inputs each, and the 463rd will have 462 inputs.

I haven't made a 7 input majority input, so I can't verify the equation above through induction, but my make-a-sense-o-meter says that it makes sense.


I don't know any good algorithm for mixing \$\lceil\frac{N}{2}\rceil\$, which is essentially AB, AC, BC in the first equation at the top. My first attempt would be to just do it with a couple of nested for loops in c++/matlab/octave and call it a day.

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

I think you can reduce this (for odd n) to a set of AND gates followed by an OR gate.

For n voters you have a majority if (n+1)/2 agree. So this is an n pick k situation where k = (n+1)/2 and you need

z = \$\frac{n!}{k!(n-k)!}\$ k-input AND gates and a z-input OR gate (where n is odd and k = \$\frac{n+1}{2}\$)

For even n it would be similar except a majority is n/2 +1.


For the n choose k algorithmically, I refer you to this Python code.

\$\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.