Bit counter using basic logic gates [closed]

I cannot figure out a puzzle which is to create a 4-bit bit counter using basic logic gates (NOT, OR, AND, NOR, NAND, XOR, XNOR, MUX, FULL ADDER). A bit counter tells how many bits are set in a value. So, for example, the value '1011' would have the result '011' because three bits are set and '011' means 3 in binary.

I bought a book called "Digital Principles" by Schaum's Outlines and nowhere in this book does it tell how to make a bit counter out of logic gates. I also have the book Hill & Horowitz, used to teach digital logic. Nowhere in this book does it tell how to make a bit counter out of logic gates. I find it extremely frustrating that making basic combinatorial logic circuits is some kind of black voodoo that is undocumented.

Is there any book that COMPREHENSIVELY describes the construction of all common combinatorial circuits, such as bit counters, adders, etc, using basic logic gates?

Note: figuring out how to do this is not easy. This is a 16-row truth table with 3 columns of outputs. If you try to write that all out and simplify it, it will be very complex and a lot of opportunity for making errors. The truth table for a 4-bit bit counter looks like this (inputs on left, output on right):

I tried solving this using a Karnaugh map, but it is still resulting in an expression that is way too big for the puzzle solution area. For example, for the second output column, I got the following Karnaugh map:

which has the following expression:

A'B'CD + A'BD + ABC' + AB'D + BCD' + AB'CD'


Representing this in the puzzle would require 6 4-way ANDs, 1 4-way OR, and 3 2-way ORs. All these components would not even fit in the available area for the puzzle solution.

closed as too broad by Eugene Sh., Daniel Grillo, Dmitry Grigoryev, laptop2d, uint128_tJul 8 '16 at 4:16

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What's bit-counter? and by the way, any logic can be designed just out of NAND or NOR gates only... – Eugene Sh. Jul 6 '16 at 14:50
• @EugeneSh. A bit counter counts the number of bits in a binary value. So for example the value 1011 has 3 set bits in it. Therefore, if the input to the bit counter is 1011, then the output would be 0011 which equals 3. – Tyler Durden Jul 6 '16 at 14:51
• In this case just draw a truth table. As easy as this. Hint: 4 inputs 3 outputs.. – Eugene Sh. Jul 6 '16 at 14:52
• I second Eugene Sh's comment. You seem to have missed the point about logic synthesis. Once you know how to synthesize a simple function, more complex functions are not qualitatively different, so you won't find "how to make an adder" (well, OK, bad example - you can find such directions). Instead, sit down, define exactly what your function is supposed to do, then break it down to simple terms and synthesize them. For instance, your bit counter can be seen as a pair of 1-bit adders which feed a 2-bit adder. Take it from there. – WhatRoughBeast Jul 6 '16 at 15:06
• @TylerDurden If you don't know how to translate a truth table into a gate implementation - then you should make a step back and learn how to do it for simpler functions. – Eugene Sh. Jul 6 '16 at 16:38

Given inputs A, B, C, D and outputs X, Y, Z, where XYZ is a 3 bit unsigned binary number representing the number of bits in ABCD that are 1. Let X be the most siginfiant bit of the binary number and let Z be the least significant bit.

The truth table for the function looks like...

ABCD => XYZ
0000 => 000
0001 => 001
0010 => 001
0011 => 010
0100 => 001
0101 => 010
0110 => 010
0111 => 011
1000 => 001
1001 => 010
1010 => 010
1011 => 011
1100 => 010
1101 => 011
1110 => 011
1111 => 100

From the truth table we see plainly that the X output is only 1 when all bits in ABCD are 1. Therefore...

X = A AND B AND C AND D

We see plainly that the Z output only 1 when an odd number of bits are 1. An odd parity function is easily implemented using XOR gates. Therefore...

Z = A XOR B XOR C XOR D

The function for the Y output is a little less obvious. 1 when at least two of ABCD are on but not when all four are on. The Y term may be written as all combinations of two inputs being on except when all four are on.

Y = ((A AND B) OR (A AND C) OR (A AND D) OR (B AND C) OR (B AND D) OR (C AND D)) AND NOT X