1
\$\begingroup\$

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):

enter image description here

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:

enter image description here

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.

\$\endgroup\$

closed as too broad by Eugene Sh., Daniel Grillo, Dmitry Grigoryev, laptop2d, uint128_t Jul 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.

  • 1
    \$\begingroup\$ What's bit-counter? and by the way, any logic can be designed just out of NAND or NOR gates only... \$\endgroup\$ – Eugene Sh. Jul 6 '16 at 14:50
  • \$\begingroup\$ @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. \$\endgroup\$ – Tyler Durden Jul 6 '16 at 14:51
  • 3
    \$\begingroup\$ In this case just draw a truth table. As easy as this. Hint: 4 inputs 3 outputs.. \$\endgroup\$ – Eugene Sh. Jul 6 '16 at 14:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – WhatRoughBeast Jul 6 '16 at 15:06
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Eugene Sh. Jul 6 '16 at 16:38
3
\$\begingroup\$

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

As an alternate to what is described above, this function could also be constructed by cascading a two bit adder and two three bit adders. The first adder adds A and B. The second adder adds the result of the first adder to C. And the third adder adds the result of the second adder to D, and so on for any number of inputs.

\$\endgroup\$
  • \$\begingroup\$ How did you figure out the expression for Y? \$\endgroup\$ – Tyler Durden Jul 6 '16 at 19:48
  • \$\begingroup\$ I also presume that Y can be shortened even further using Karnaugh diagrams \$\endgroup\$ – Artūras Jonkus Jul 6 '16 at 21:18
-1
\$\begingroup\$

I figured out the solution, which is similar to what user96037 says at the end of his answer. Due to the limited space available in the solution area, using adders is necessary and it appears two adders are needed as follows:

enter image description here

So the basic strategy here is that you generate the bit counts for inputs 1+2 and 3+4 separately first which can be done with just 2 gates each (XOR and AND). Now, you have two 2-bit values. You can then add these two values using a pair of full adders chained together. The carry in to the first adder must be set to 0. So, altogether there are 6 components plus the 0 in.

\$\endgroup\$
  • \$\begingroup\$ What's this game? \$\endgroup\$ – Eugene Sh. Jul 6 '16 at 19:37
  • \$\begingroup\$ @EugeneSh. Its called "circuit coder". The program gives you a problem (like here to create a 4-bit bit counter) and you must assemble the logic gates to form a solution. The program can test your solution to see if you are right and show you the cases where you were wrong. With the arrow keys ("1/16" in lower left) you can step through all the input possibilities and try them manually. \$\endgroup\$ – Tyler Durden Jul 6 '16 at 19:39
  • \$\begingroup\$ Nice. No app for android, that's pity. \$\endgroup\$ – Eugene Sh. Jul 6 '16 at 19:40
  • \$\begingroup\$ @EugeneSh. I am trying to learn digital logic using this game and I can solve most of the problems, but some of them (like this one) are difficult for me. \$\endgroup\$ – Tyler Durden Jul 6 '16 at 19:43

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