0
\$\begingroup\$

I have \$2^n\$ inputs \$a_{0}, a_{1} .. a_{2^n}\$, these can be either hich or low, and \$n\$ outputs \$z_{0}, z_{1} .. z_{n}\$, these give out a binary number of how many of the inputs are high. Is there any simple way to realize this without using half and/or full adders?

\$\endgroup\$
  • \$\begingroup\$ Are adders really that difficult? FA is 5 2-input gates. \$\endgroup\$ – Eugene Sh. Sep 10 '15 at 19:47
  • 1
    \$\begingroup\$ It could be done, with a whole bunch more gates than an adder takes. \$\endgroup\$ – Matt Young Sep 10 '15 at 19:56
  • \$\begingroup\$ It can be done without adders. Smells a bit like homework so I will not give an answer. Your hint is to make some truth tables and K-maps, then figure out the formulas. Show us your effort and update your question; we may guild you if you get stuck. \$\endgroup\$ – Greg Sep 10 '15 at 20:05
  • \$\begingroup\$ Not really...Do the most trivial case...2 input lines and 2 output lines...and the logic is a half adder.Then try 3 input lines and 2 output lines....The 2 bit is a "ANY 2" Gate and the 1 Bit is a "ANY 1 or 3" gate. \$\endgroup\$ – Jotorious Sep 10 '15 at 20:10
  • \$\begingroup\$ @Greg truth tables and K-maps for 2^N inputs and N outputs?? That won't be easy... \$\endgroup\$ – Eugene Sh. Sep 10 '15 at 20:12
1
\$\begingroup\$

No. There isn't. If you want a binary number in which the nth output represents the place value of 2n, you have to cascade adders. Keep in mind though that an adder is just an AND gate for the carry bit, and an XOR gate for the sum bit.

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

If you have a clock, you can use a mux to step through and count the inputs.

If this needs to be combinatorial logic, you can search under "compressor tree" for efficient approaches.

The basic idea of a compressor tree is to reduce the number of signals in each cascaded stage until the signals represent the final sum:

A 2-input adder doesn't help much in this situation because the sum of two input bits still needs two output bits to represent the count of 0, 1, or 2 high input bits. But as Jotorius noted in the comments, you can create logic that adds groups of three input bits to generate corresponding two-bit sums (0, 1, 2, or 3 high inputs). This is making some progress because the number of signals has been reduced by a factor of 2/3. The next stage uses the same approach, but now the input bits have different weights or "ranks". Half of the bits have a weight of 1 (the LSBs of the two-bit sums) and the others have a weight of 2 (the MSBs of the two-bit sums).

In the second stage, the 1's bits are summed in groups of three and the 2's bits are grouped and summed in groups of three resulting in yet a smaller set of signals with weights of 1, 2, and 4. (The sum bits of the 2's inputs will have weights of 2 and 4.)

The compressor stages continue until there are only two or fewer bits left of each weight. At this point, you can use a standard ripple-carry adder to get the final result.

Depending on the exact bit counts at each stage, some three-bit adders won't use all of their inputs.

A compressor tree isn't limited to a 3:2 compression at each stage. For example, an FPGA with 6-input LUTs could efficiently implement 6:3 compression at each stage of the tree.

If N is small, you can totally cheat and use a static parallel EEPROM to make a lookup table.

\$\endgroup\$
0
\$\begingroup\$

You are asking for a sum of high/active inputs. A sum needs adders to be calculated! You can name it like you want, but in the end there are adders involved.

If you want to find fast solutions, search for 'Hamming Weight' or 'Bit Count'.

There are solutions using lookup tables or DSPs to achive a higher speed up than using simple RCAs.

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