0
\$\begingroup\$

I have the SOP (Sum of Products) equation: F = ¬A¬BC + A¬BC + A¬B¬C + ABC, which is the sum output of a full adder.

Could someone please help me and show me how by using Boolean algebra i can change this SOP expression to use only XOR gates.

In table below CIN is C the from formula of F above and Sum is result of F.

$$ \begin{array}{c|c|c|c|c} \text{A} & \text{B} & C_{IN} & C_{OUT} & \text{Sum} \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} $$

\$\endgroup\$
  • \$\begingroup\$ Are you sure it is possible? XOR is not a complete logical system, so not every function can be represented using only XORs. But if it a homework assignment, I guess it is possible.. \$\endgroup\$ – Eugene Sh. Feb 10 '15 at 21:43
  • \$\begingroup\$ BTW, two input gates, or three? If more than two, there are two different definitions of XOR. \$\endgroup\$ – Eugene Sh. Feb 10 '15 at 21:49
  • \$\begingroup\$ 3 inputs (A,B,C) \$\endgroup\$ – QWE Feb 10 '15 at 22:02
  • \$\begingroup\$ @EugeneSh. The equation above is the SUM output of a full adder. I got the equation above using the truth table. But now it says im supposed to change it so that the sum of products is represented only using XOR. But im not sure what the procedure in doing this is :/ \$\endgroup\$ – QWE Feb 10 '15 at 22:04
  • 1
    \$\begingroup\$ I don't think it would be helpful to anyone else, so I'll let it remain in comments. \$\endgroup\$ – Eugene Sh. Feb 10 '15 at 22:33
2
\$\begingroup\$

One can not implement every logical function using only XOR gates.

Since XOR is a logical operator which obeys associativity, the function implemented using only XOR gates can always be written as $$f = a_1\oplus a_2 \oplus a_3 \oplus \cdots \oplus a_n $$ where \$a_1, a_2 \ldots\$ are the inputs.

So the only possible functions that can be implemented using XOR gates are:

1. Odd number of 1's

$$\tag1 f= \begin{array}{|cl} 1 & \mathrm{if }\ N = odd \\0 & else \end{array}$$

Where N is the number of 1's in the input. \$f\$ can be implemented as $$f = a_1\oplus a_2 \oplus a_3 \oplus \cdots \oplus a_n $$

2. Even number of 1's

$$\tag2 f= \begin{array}{|cl} 1 & \mathrm{if }\ N = even \\0 & else \end{array}$$

can be implemented as $$f = a_1\oplus a_2 \oplus a_3 \oplus \cdots \oplus a_n \oplus 1 $$

3. Inverter

$$\tag3 f = \overline{a}$$ can be implemented as $$f = a\oplus 1 $$

In your case, SUM can be implemented using XOR gates only (as given in (1)) but not COUT.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

A three-input gate which outputs true when exactly one of its inputs is true may be used as a two-input NOR gate by tying one of its inputs high; it may also be used as an "A and not B" input by tying one input to the desired "A" and two to the desired "B", or as a two-input exclusive-or gate by tying one input low. Such two-input gates may be combined to produce any other kind of logic.

Using such a three-input gate purely to implement the above two-input functions may seem wasteful, but in reality I'm unaware of anyone actually mass-producing chips to compute true-only-if-exactly-one-input-is-true functions; since such gates only exist in simulation, there's no practical need to avoid including excess gates as there would be if one were building actual circuits.

PS--I would draw the above gate in a schematic as a trapezoid, with each inputs on the long side labeled "+1", and the output on the short side labeled "total == 1". Such a labeling scheme would allow a variety of devices, including "total = 2", or "total < 2", total > 1, or even total = 1..2, to be notated in clearly-understandable and consistent fashion. Additionally, such a device could easily accommodate various weightings of inputs, and one set of inputs could be used to derive multiple outputs.

For example, consider the following device [pretend it's a trapezoid]

    |-----._____
 ---| +16       `---.
 ---| +8  total>=10 |---
 ---| +4            |
 ---| +2   total>=9 |---
 ---| +1  _____,---'
    |-----'

The meaning of such devices in a BCD carry-propagation chain would likely be clearer than the appropriate combination of gates [the two outputs would be "+16 OR (+8 AND (+4 OR +2))", and "+16 OR (+8 AND (+4 OR +2 OR +1))`].

|improve this answer|||||
\$\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.