n-bit majority digital logic

Question

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

Answer 1

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.

Answer 2

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.