I ran into a 2013 contest question on computer-science filed.

What is the following True about F and G function. (The output of Decoder is zero when disabled).

I) Is equal.

II) Complement to each other.

III) the 1's in F is more than 1's in G.

IV) the 0's in F is more than 0's in G.

Answer Sheet Select (1), But I think (2) is Correct. Who can verify me and hint how we can correctly solve such a circuit?

enter image description here


Assuming the decoder is active, the Truth table is as follows :

XZ    Dec_Out    HA1        HA2    a b cin    F G
               Sum | C    Sum | C
00   1000      1     0    0     0  1 1 0      0 1
01   0100      1     0    0     0  1 1 0      0 1
10   0010      0     0    1     0  0 1 1      0 1
11   0001      0     0    1     0  0 1 1      0 1

The truth table is easy to construct :

  • First determine the output of decoder corresponding to various inputs
  • Next apply D0 and D1 as inputs to HA1 and D2 and D3 as inputs to HA2
  • Compute their outputs and apply them to FA

Now since it was a competition problem, there has to be a short cut (which I was not able to figure out initially as well) instead of solving the truth table :P

  • Two outputs of a decoder cant be simultaneously high. This means that the sum of both half adders cant be one simultaneously. Infact, output of exactly one HA HAS to be 1 always, and also that both have to give a carry of zero.
  • The Xnor will always give a 1, since both carry are always zero.
  • If 2 of the inputs to the Full adder are always one, the sum ie F will always be 0, while the carry ie G will always be 1.

Similar arguments hold when decoder is inactive, but this time output of both HA will be 0.

  • With outputs of both half adders as zero, the XNOR is still high while A and Cin are zero
  • So the input of FA consists of exactly one, which means sum ie F will always be 1 while carry ie G will always be 0.

In either case, F and G are always complements to each other.

  • \$\begingroup\$ Complete answer, your means which one is True / \$\endgroup\$ – user4249446 Apr 20 '15 at 19:08
  • \$\begingroup\$ The second option most definitely ! \$\endgroup\$ – Plutonium smuggler Apr 20 '15 at 19:14
  • \$\begingroup\$ is it possible make your answer a bit clearer? \$\endgroup\$ – user4249446 Apr 20 '15 at 19:16
  • \$\begingroup\$ What part is not clear ? \$\endgroup\$ – Plutonium smuggler Apr 20 '15 at 19:17
  • \$\begingroup\$ why III and IV is not true ? \$\endgroup\$ – user4249446 Apr 20 '15 at 19:27

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.