

Article 361 of comp.theory.cell-automata:
Path: mimsy!haven!uflorida!rex!samsung!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death
>From: [email-masked] (Trevor Green)
Newsgroups: comp.theory.cell-automata
Subject: Re: Wireworld: better cross, xor and and
Keywords: wireworld
Message-ID: <[email-masked]>
Date: 28 Feb 90 17:15:12 GMT
References: <[email-masked]>
Reply-To: [email-masked] (Trevor Green)
Organization: University of Waterloo Computer Science Club
Lines: 136

In article <[email-masked]> [email-masked] (George Phillips) writes:
>About a week ago, Ian Woollard <[email-masked]> sent me a
>wonderful XOR gate he created:

..I...
.====.
.=..=O
.====.
..I...
Transit: 3
IBI: 5
Size: 6x5

I like it. This is "the" XOR gate.

>And then used (A^B)^A == B to do a very good wire crossing.
>BTW:  my wire crossings _do_ work, but who cares with this around:
The first half of that BTW is still open to debate.  The second half is
unconditionally true and makes the debate irrelevant.

...........
.....==....
....=..=...
...=..====.
.I=...=..=O
..=...====.
.====..=...
.=..===....
.====..=...
..=...====.
.I=...=..=O
...=..====.
....=..=...
.....==....
...........
Transit: 9
IBI: 5
Size: 11x15

I tried to "simplify" this (it still looks too open for me) and replaced
the final XORs with much simpler structures.  This also entailed adding
two diodes and I wound up upping the IBI to 11 with the size and transit
time remaining about the same.  This appears to be an excellent design.
I'll see if I can improve on it, but I think that this is *the* A^B^A
design.  It'll be a completely different design that beats it.

>While trying to understand the XOR gate, I realized that one of the
>tricks was to make each incoming pulse cancel themselves.  I used this
>idea to make a faster AND gate:
>
>............==
>...........=..=#-====-===#-
>......==..===
>.....=..=..=..=.=#-===#-====-
>....===..==.==.=
>....==.........=
>====..=========

Now, George, you're making me feel like a tinker to your artist.  This
one looked a little sloppy again, so I "fixed" it. (Believe it or not,
the design below is "topologically" identical to the one above, except
for one inconsequential change.)

.I.....
..=....
.===...
..=....
I=.=...
.=..=..
.=.===.
.=..=..
..==.O.
Transit: 7
IBI: 5 (again!)
Size: 7x9

>I don't know if it's me or wireworld, but none of the AND gates are
>symmetric.  Hmmmm.  Maybe someone will surprise me -- getting new
>patterns from the net is almost as much fun as building them yourself.

My original AND gate was symmetric - double each input, XOR the middle
two and then XOR again for the final output (more or less).

................
..=====.........
.=.....====.==..
.=..==.....=..=.
.=.==.=...===.=.
I.=.==.==..=..=.
........===..==O
I.=.==.==..=..=.
.=.==.=...===.=.
.=..==.....=..=.
.=.....====.==..
..=====.........
................

Then I realised  I could do without one of the doubled lines.

.............
...==........
..==.=.......
I=.==.==.....
.......===...
I..==.==..=..
.===.=...===.
.=.==.....=..
.=....====.O.
..====.......
.............

With the better XOR posted above, I have improved it once again, but it doesn't
hold a candle to George's:

.I........
..=.......
.====.....
.=..===...
.====..=..
..=...===.
.I.=...=..
...=..=.O.
....=.=...
.....=....
..........
Transit: 9
IBI: 5
Size: 10x11

The reason for the inefficiency compared to George's AND is that the XOR
can be replaced by the other doohickey (the "implication" one (a&~b)...what'll
we call it?) for an increase in through speed and decrease in size (amazing
how often one follows the other in wireworld).

>George Phillips [email-masked] {alberta,uw-beaver,uunet}!ubc-cs!phillips
Trevor Green [email-masked] watmath!maytag!watcsc!death