I have a circuit X which has 4 inputs A0,B0,A1,B1 and 2 outputs A2,B2. For n of A,B bits, I need them to pass through X. I'm trying to build an equation on how many circuits X I need for n bits. For example, for n=8 we need 7 circuits:

enter image description here

I found out that for 2<=n<=7 we need n-1 X cuirits, but I know that for n=32 we need to get 30. What is the right formula?

  • 1
    \$\begingroup\$ So each level is half the number of the previous level. Now sum these up. Hint: Geometric progression. \$\endgroup\$ – Eugene Sh. Jul 16 '19 at 17:49
  • 4
    \$\begingroup\$ I don't understand what the "X" boxes are supposed to do. How is the output of an X box related to the input of that box? How do you know that you need 30 X boxes for n=32, because I am skeptical of that answer. \$\endgroup\$ – Elliot Alderson Jul 16 '19 at 17:50
  • 1
    \$\begingroup\$ Indeed, for 32 bits you need 15 boxes. At least if the other information in the question is correct. \$\endgroup\$ – Eugene Sh. Jul 16 '19 at 17:52

Each of your X boxes reduces 4 input signals to 2.

To put it another way, each X box reduces the total number of signals by 2.

This result is the same whatever arrangement of X boxes you use: a fat tree (like the one you drew) or a long thin chain.

If you have 2n inputs, you will always need n-1 boxes if you want only 2 outputs.

Your “n=32” solution must therefore be wrong somehow.


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.