I have been given this diagram of a circuit: https://www.google.com/search?q=full+adder+logic+gate&rlz=1C1CHBF_enCA831CA831&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjCjZzc_PbfAhXCj4MKHahtCvcQ_AUIDigB&biw=1536&bih=792#imgrc=GFIqfN5OgCdtRM:

The second XOR gate looks like its output is being connected as inputs of 2 different gates at the same time. Am I interpreting this incorrectly or is it possible to send the a single output to 2 gates simultaneously?

  • $\begingroup$ It is definitely possible (and required in many designs) to connect the output of a gate to the inputs of several other gates. The only limitation is electrical. If this number is to high, gate performances can be degraded. If interested, you can check en.wikipedia.org/wiki/Fan-out $\endgroup$ Jan 18 '19 at 10:08
  • 1
    $\begingroup$ This seems more suited to Electrical Engineering. $\endgroup$ Jan 18 '19 at 12:51
  • 1
    $\begingroup$ Questions should be self-contained. Please do not simply add a link to an image; insert the image as such directly in the question instead. Thank you. $\endgroup$
    – dkaeae
    Jan 18 '19 at 13:39

In circuit complexity, the fan-out of a gate is the number of gates its output is connected to (similarly, the fan-in is the number of inputs to the gate). A circuit in which all gates have fan-out 1 is known as a formula. It is known that some $n$-bit functions can be computed by circuits of size $O(2^n/n)$ but require formulas of size $\Omega(2^n/\log n)$. It is conjectured that polynomial size circuits can compute more functions than polynomial size formulas, but this conjecture, known as the $\mathsf{NC^1} \stackrel?= \mathsf{P}$ question, remains unproved.


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.