"Charles" wrote in news:Fa2dnTOv-42P_xfVnZ2dnUVZ snipped-for-privacy@comcast.com:
I know, but NAND and NOR gates are also non-linear (see my definition in the answer to Helmut's post). I would like to build it without such gates.
Regards, Bernd
"Charles" wrote in news:Fa2dnTOv-42P_xfVnZ2dnUVZ snipped-for-privacy@comcast.com:
I know, but NAND and NOR gates are also non-linear (see my definition in the answer to Helmut's post). I would like to build it without such gates.
Regards, Bernd
"Bernd Schneider" schrieb im Newsbeitrag news:g6esau$74l$ snipped-for-privacy@aioe.org...
Hello Bernd,
To be honest, this definition of "linear" together with digital logic is nonsense. Please ask your friend for a web-link. I am really interested to see who uses this definition.
Best regards, Helmut
You can build any logic function out of XOR gates. Since you have defined the XOR as a linear gate, use it.
-- The Force is dark on one side, light on the other and holds the world together. Hmmm, just like Gaffer Tape then.
-- Whether you use explicit NANDs or NORs is immaterial; you\'ll have to implement those _functions_ in order to make your circuit work. Why not post a truth table of what you want? JF
hi I think its a simple misunderstanding with linear and non.. a gate will always make a change in state, from Vcc to gnd or like , It will never act like a linear device.
But it is so that Nor ,not ,nand inverts the signal and and ,or do not invert signals. So you have inverting and non inverting gates .
alex
No, not with XORs. You can with all NANDs or all NORs, but not with all XORs.
-- Reply in group, but if emailing add another zero, and remove the last word.
Whoever told you that should not be used as a reference in the future.
The terms min-term and max-term were in use at one time, and although they serve little purpose at least they make sense. Calling a gate linear just because its output is true 50% of the time doesn't make sense.
-- Reply in group, but if emailing add another zero, and remove the last word.
The Fredkin gate is what you call a "linear gate", because for each of the three outputs the probability is 1/2 that it is 1. It is universal, so your functions can be implemented with linear gates, only.
For your first function:
u s e w
0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1the logic function looks like this: w = (e AND u) OR ((NOT e) AND s) It is not possible to implement it with XOR and NOT, only.
To prove this, you have to show that it is not possible to implement your function with XORs, 1 and 0, only (because NOT p = 1 XOR p). First we prove that it is impossible to implement half of your function, with s=0, which is a selector for just one bit (an AND gate)
u e w
0 0 0 0 1 0 1 0 0 1 1 1To prove it, we have to show that any number of XOR gates, connected in any valid combination, does not produce an AND gate. Lets start with 0 XOR gates. The possible values for w are u, e, 1 and 0.
With one XOR gate:
1 (u and e not used, fixed input 1 and 0) 0 (u and e not used, fixed input 0 and 0) u xor e u (=u xor 0) e (=e xor 0) not u (= u xor 1) not e (= e xor 1)Adding one more XOR gate, the output of the previous gate, u, e, 0 and 1 can be used for both inputs. u, e, 0 and 1 are outputs of the previouse gate, too, so there are 49 combinations to test:
1 xor 1 = 0 0 xor 1 = 1 (u xor e) xor 1 = not(u xor e) u xor 1 = not u e xor 1 = not e (not u) xor 1 = u (not e) xor 1 = e1 xor 0 = 1
0 xor 0 = 0 (u xor e) xor 0 = u xor e u xor 0 = u e xor 0 = e (not u) xor 0 = not u (not e) xor 0 = not e1 xor (u xor e) = not(u xor e)
0 xor (u xor e) = u xor e (u xor e) xor (u xor e) = 0 u xor (u xor e) = e e xor (u xor e) = u (not u) xor (u xor e) = not e (not e) xor (u xor e) = not u1 xor u = not u
0 xor u = u (u xor e) xor u = e u xor u = 0 e xor u = u xor e (not u) xor u = 1 (not e) xor u = not(u xor e)1 xor e = not e
0 xor e = e (u xor e) xor e = u u xor e = u xor e e xor e = 0 (not u) xor e = not(u xor e) (not e) xor e = 11 xor (not u) = u
0 xor (not u) = not u (u xor e) xor (not u) = not e u xor (not u) = 1 e xor (not u) = not(u xor e) (not u) xor (not u) = 0 (not e) xor (not u) = u xor e1 xor (not e) = e
0 xor (not e) = not e (u xor e) xor (not e) = not u u xor (not e) = not(u xor e) e xor (not e) = 1 (not u) xor (not e) = u xor e (not e) xor (not e) = 0This shows that only the expression not(u xor e) is new. Now we calculate the result of any combination of the new 8 expressions. All combinations with the first 7 expressions are already tested, so we have to test only the 7 combinations with the new one:
1 xor not(u xor e) = u xor e 0 xor not(u xor e) = not(u xor e) (u xor e) xor not(u xor e) = 1 u xor not(u xor e) = not e e xor not(u xor e) = not u (not u) xor not(u xor e) = e (not e) xor not(u xor e) = uThis shows that there is no new result, which means it doesn't matter how many XOR gates you add, there are only 8 possible logic functions with XOR gates:
1 0 u xor e u e not u not e not(u xor e)No function is the AND gate, so it is not possible to create an AND gate with XOR gates.
This means that for your function with 3 inputs and s=0 it is not possible to build it with NOT and XOR, only. This means it is not possible to build your whole function, because no matter what you feed to s, you can't build at least half of your logic table with XOR and NOT, only, so the full logic is not possible, too.
-- Frank Buss, fb@frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
hsa.googlegroups.com:
=3D1
You could think of the Kmap as a way to create the Boolean equation, then massage the equation to get what gates you want to use.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.