I have 31 digital inputs (each is high or low) and want one digital output which is high only if at least 16 inputs are high. How can I implement this "majority" function (which is also the most significant bit of the sum) with the fewest MOS transistors?
As a bonus, I'd also like to know the fastest-in-worst-case implementation.
Configure 31 MOS transistors as switchable current sources which feed a 32nd which is configured as a current sink at 15 times the source currents. Then observe the voltage of the summing node.
EDIT - I should not play games. The title said "Digital", so it's digital we'll go. One configuration would be
simulate this circuit – Schematic created using CircuitLab
This handles 15 inputs. Duplicate it and add a 4-bit full adder and Bob's your uncle. I haven't shown the last adder, but you should be able to figure it out for yourself.
And, of course, if you build this with BJTs, as with TTL or ECL logic, there will be no MOS transistors used at all.
Connect the 31 inputs (0-30 in the diagram below) to four 8-bit parallel-in, serial out shift registers such as the 74HC597 which are cascaded in series (only two shown). Clock the serial output of the last register into a binary counter such as the 74HC4024. Use another 74HC4024 counter to keep track of when 32 clock pulses have occurred which then repeats the cycle.
For some crazy reason the original CD4024, and the follow-on 74HC4024 started numbering their flip-flops with Q1 instead of Q0. Very confusing. So I am showing the NXP part (HEF4024B) instead which corrected this anomaly.
So every 32 clock pulses (when Q5 of the second counter goes high), if at least 16 inputs were high (meaning Q4 of the first counter is 1), then this status is latched into a D-type flip-flop (74HC74) and remembered until the next set of 32 clock pulses complete. Meanwhile the inputs are reloaded in parallel to the shift registers.
This is somewhat of a special case, in that the majority threshold is a power of two, so only one pin (in this case Q4, representing 16-31) has to be queried. If instead the threshold was 14/27 for example, an address decoder would need to be added, to separate out the values 14 and 15 in addition to 16.
With a 90 MHz input clock, there will be a maximum of 355 ns delay from a change in the input until the update of majority status at the output.
Note -- not all "glue logic" necessarily shown, but this should get across the idea.
It seems like you are confusing a few concepts here. You are saying you want a majority voter circuit. In which case you could make a very large truth table and reduce the circuit using reduction techniques. For example:
Input / Output
000 / 0
001 / 0
010 / 0
011 / 1
100 / 0
101 / 1
...so on and so forth. Then when you have the final logic gates, simply disassemble the gate into your transistor count. You are not going to be able to do this for 32 bits unless you have a lot of time on your hands. Assuming it took you 1 second to do each combination it will still take you 2^32 seconds, or 136 years. Having lived this long you would then have to do some type of gate reduction.
When you say "The most significant bit of the sum" this is a little confusing. Consider you have 3 inputs that are high, the most significant bit of the sum is 1, likewise with 2. If your majority counter had only 3 bits, this information wouldn't tell you anything.
"The fastest in-worst-case implementation" sounds like the sum of the gate delays that would happen in the worst case realization; the most cascaded realization would have the largest delay.
Hint: Latches and Flip flops are also made out of logic gates, which are also made out of transistors. Maybe you could make a shift register and a counter, then use a little combinational logic on the output of the counter.
Good luck.
I'm mostly an analog person, so I would do this using analog techniques.
Sum all of the inputs together in a summing amplifier. Feed the output of the amplifier to a comparitor that trips when the desired number of inputs is HI.
This can be simplified to a resistive summer (no op-amp needed) and a comparitor.
