0

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} $$

Ricardo
  • 6,134
  • 19
  • 52
  • 85
QWE
  • 3
  • 1
  • 5
  • 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.. – Eugene Sh. Feb 10 '15 at 21:43
  • BTW, two input gates, or three? If more than two, there are two different definitions of XOR. – Eugene Sh. Feb 10 '15 at 21:49
  • 3 inputs (A,B,C) – QWE Feb 10 '15 at 22:02
  • @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 :/ – QWE Feb 10 '15 at 22:04
  • Well, it is not a function of a full adder, sorry. Redo it again. You might want to show the steps here. – Eugene Sh. Feb 10 '15 at 22:06
  • Ive added the truth table i used above – QWE Feb 10 '15 at 22:09
  • Please update the question – Eugene Sh. Feb 10 '15 at 22:09
  • But my function is only relates to the SUM portion of it – QWE Feb 10 '15 at 22:10
  • The truth table is correct, the function is not. Look at the 5'yh and 6'th rows. – Eugene Sh. Feb 10 '15 at 22:11
  • Oh my, i was yea i did that wrong. I corrected it in the question. But do you know how I could get the sop now using only XOR? – QWE Feb 10 '15 at 22:18
  • Yep. It's easy. You don't even need to write the function, just look at the table. What is the basic property of XOR operation? – Eugene Sh. Feb 10 '15 at 22:20
  • The value will be true when one of A , B, or C is true but not all at the same time – QWE Feb 10 '15 at 22:25
  • But when you look at the table, the last entry is 1 -1 -1 and the truth value result is also 1. – QWE Feb 10 '15 at 22:25
  • So this is exactly the two different definitions of three-input XOR that I was talking about. The second definition says that the output is true when the ODD number of inputs is true. And this behaviour is actually achieved by chaining two-input xors (A xor B xor C). Look for related discussion here: http://electronics.stackexchange.com/questions/93713/how-is-an-xor-with-more-than-2-inputs-supposed-to-work – Eugene Sh. Feb 10 '15 at 22:27
  • I finally got it. Thank you so much for helping me. If you post this as an answer below, id be happy to mark it as best answer. – QWE Feb 10 '15 at 22:31
  • 1
    I don't think it would be helpful to anyone else, so I'll let it remain in comments. – Eugene Sh. Feb 10 '15 at 22:33

2 Answers2

3

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.

nidhin
  • 8,197
  • 3
  • 28
  • 46
  • Well, inverter (3) is just particular case of (2) for only argument. – Fizz Feb 11 '15 at 16:46
  • Implementing the sum output a full adder with XOR gates is somewhat of standard exercise: e.g. http://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder or http://cs.smith.edu/dftwiki/index.php/File:FullAdder3Bits.png – Fizz Feb 11 '15 at 16:57
  • @RespawnedFluff Yes. (3) is a particular case of (2). But I think that particular case is special. :) – nidhin Feb 12 '15 at 14:20
1

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))`].

supercat
  • 45,939
  • 2
  • 84
  • 143