1
\$\begingroup\$

I have 2 16-bit inputs: A[15, 0] and B[15: 0]. There are also two outputs: OUT[15: 0] and Z[1: 0]. The way it works is if # of bits that are 1 in A is greater than or equal to the # of bits that are 1 in B then OUT=A and Z=1, else OUT=B and Z=0.

As an example, if A[15:0]=0010001000100010, B[15:0]=1010101010101010 then B has more 1s and thus OUT=1010101010101010 and Z=0

I'm really new to this and want to implement it with only NOT, NAND gates, Multiplexer, Adder, and Comparator. But I don't know where to start or how to begin. Could anyone help me out or tell me which steps to take? Should I draw out a truth table?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Does the problem change for 951 bits, 3, 2 or even one? Start with the lowest number of bits the problem looks the same. \$\endgroup\$
    – greybeard
    Commented May 28, 2023 at 5:52
  • \$\begingroup\$ Um - why is Z introduced as a two-bit signal? \$\endgroup\$
    – greybeard
    Commented May 28, 2023 at 10:52
  • 1
    \$\begingroup\$ For homework questions we expect you to show us that you have made a substantial effort to solve this yourself. Show us all of your work, and then ask a specific question. If you really, truly, don't know where to start then you should talk to your instructor. \$\endgroup\$ Commented May 28, 2023 at 12:29

2 Answers 2

1
\$\begingroup\$

Start with the simplest thing that could possibly work (XP).

It is OK to select A if
• A = B
• A = 1111111111111111
• B = 0
• A contains at most one 0s (an or of 16 15-input ands) and B != 1111111111111111
• A contains at most two 0s (an or of 16*15 14-input ands - dang, this is getting out of hand, ending with 16!/8! 8-input gates - times 2: some billion gates. And doesn't get that much better using complements)
(Trying to make a unary-to-binary encoder/combinatorial binary counter along these lines gets worse.)

Looks like one needs to exploit all bits of any given input being equivalent.

Hint: All three inputs of a full adder are equivalent.

The outputs of a full adder are the binary count of 1s at the inputs.

I failed to find a lucid diagram for a "single significance compressor tree" as well as creating one.
14/15:4 combinatorial counter as falstad.com/circuit

(If Adder means k-bit full adder instead: you can use it as \$\lceil(k-1)/2\rceil\$ independent full adders.)


There is an entirely different approach to this:
Build an n input unary-to-binary encoder from a binary sorter: a circuit moving all 1s to one "end", 0s to the other. You can compare these unary numbers easily, or convert to 1-hot and from there to binary:
n+1 x AND NOT y gates to get the boundary between 0s and 1s encoded "one hot" followed by a (simple) encoder.
For 16 bits this takes 4 8-input gates and 137 2-input gates using a "60 arrow" (see below) 10 level sorter.

The circuit to sort two (1-bit) inputs is simple enough:
an OR gate to the 1s end and an AND gate to the 0s end - I'll call it arrow.
One very regular construction to sort more than two values/signals/bit is an odd-even transposition network, for 16 inputs it needs 120 arrows/240 2-input gates, and 16 levels/stages.
The fastest/least deep "16-sorter" is 9 levels, the smallest known as of 2023/05 is 60 arrows.
A CIRCUITLAB finger exercise that proved tedious
(The left sorter showing the better half of gates can easily be inverting):

schematic

simulate this circuit – Schematic created using CircuitLab


There are loads of papers on population count / popcount, most "scholarly".

\$\endgroup\$
3
  • \$\begingroup\$ I guess lookup table doesn't conform only NOT, NAND gates, Multiplexer, Adder, and Comparator - unless using 4 abusively large 65536:1 multiplexers is fair game. \$\endgroup\$
    – greybeard
    Commented May 29, 2023 at 6:18
  • \$\begingroup\$ Could you elaborate on your hint? I think this is the way I should be going, but I am not sure how I would set this up. \$\endgroup\$ Commented May 29, 2023 at 23:25
  • \$\begingroup\$ One can, of course, recreate the "2-input adder tree" of a decent software popcount in hardware, and get an inferior variant of the Wallace tree implementation. Or use 15 "conditional incrementers". \$\endgroup\$
    – greybeard
    Commented May 30, 2023 at 2:24
0
\$\begingroup\$

Do you want a really easy ways to do that?

Include some analog circuits.

  • Buffer both inputs with buffer gates, all powered from the same 5 V supply (this is to ensure that the voltage from each high bit is exactly the same, and the voltage from each high bit is exactly 0 V)
  • Connect 16 equal-value, 0.1 % resistors to input A.
  • Connect 16 equal-value, 0.1 % resistors to input B.
  • Use an analog comparator IC to see which set of resistors has the highers voltage.
  • Drive a multiplexer from the output of the comparator, to select either A or B.

Another easy way to do it is in software, in a microprocessor with at least 48 IOs.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ (Not quite combinatorial.) \$\endgroup\$
    – greybeard
    Commented May 28, 2023 at 16:44
  • \$\begingroup\$ I am an engineer: I go for the most practical solution and disregard artificially imposed limitations. ;-) \$\endgroup\$ Commented May 28, 2023 at 17:08

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