Re: Conway life - calculation of next generation with logic gates
From: Frank Buss (fb_at_frank-buss.de)
Date: 11/29/04
- Previous message: Kenny Tilton: "Re: using function names as variable names? Is it Justified?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 29 Nov 2004 14:27:51 +0000 (UTC)
user1 <bsg@net.com> wrote:
> Actually I would be surprised if there were no errors in the original
> schematic. I'm sure it could be improved in numerous ways.
there is no error in your schematic, I've checked it with the Lisp
program below, which I've extracted from your schematic:
http://www.frank-buss.de/tmp/life.png
I'm crossposting this to comp.lang.lisp, because I wonder if it is
possible to write a program, which simplifies the boolean expression,
which is calculated by (get-bool 0) or if it is possible to create the
simplest possible boolean expression from a given truth table.
(defparameter *inputs* '(a b c d e f g h s))
(defparameter *gates*
'(logior
logand
logxor
logand
logxor
logand
logxor
logand
logxor
logand
logxor
logand
logxor
logxor
logand
logxor
logand
logxor
logxor
logand
logxor
logand
logxor
logxor
logand
logxor
logand
logxor
logxor
logand
logxor
logxor
lognot
logand
logand
logand
lognot
logand))
(defparameter *wires*
'((35 37)
(a b)
(a b)
(2 c)
(2 c)
(1 3)
(1 3)
(4 d)
(4 d)
(6 7)
(6 7)
(8 e)
(8 e)
(5 9)
(10 11)
(10 11)
(12 f)
(12 f)
(13 14)
(15 16)
(15 16)
(17 g)
(17 g)
(18 19)
(20 21)
(20 21)
(22 h)
(22 h)
(23 24)
(25 26)
(25 26)
(28 29)
(31)
(30 32)
(30 27)
(33 s)
(31)
(36 34)))
(defun get-bool (gate)
(if (find gate *inputs*)
gate
(let ((wire (elt *wires* gate)))
(append (list (elt *gates* gate)) (mapcar #'get-bool wire)))))
(defmacro life ()
(get-bool 0))
(defun test ()
(let ((false 0))
(loop for i from 0 to 511 do
(let* ((a (if (> (logand i 1) 0) 1 0))
(b (if (> (logand i 2) 0) 1 0))
(c (if (> (logand i 4) 0) 1 0))
(d (if (> (logand i 8) 0) 1 0))
(e (if (> (logand i 16) 0) 1 0))
(f (if (> (logand i 32) 0) 1 0))
(g (if (> (logand i 64) 0) 1 0))
(h (if (> (logand i 128) 0) 1 0))
(s (if (> (logand i 256) 0) 1 0))
(next-life (life))
(count 0)
(next-calculated 0))
(when (= a 1) (incf count))
(when (= b 1) (incf count))
(when (= c 1) (incf count))
(when (= d 1) (incf count))
(when (= e 1) (incf count))
(when (= f 1) (incf count))
(when (= g 1) (incf count))
(when (= h 1) (incf count))
(setf next-calculated s)
(when (= count 3) (setf next-calculated 1))
(when (< count 2) (setf next-calculated 0))
(when (> count 3) (setf next-calculated 0))
(when (/= next-life next-calculated) (incf false))))
(format t "false: ~a~%" false)))
Using Lisp syntax the boolean expression for the next state (which is
returned by "(get-bool 0)") looks like this:
(LOGIOR (LOGAND (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D))
(LOGAND (LOGXOR (LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR
(LOGXOR (LOGXOR A B) C) D) E) F)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E) F) G)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGXOR (LOGXOR A B) C) D) E) F) G) H)) (LOGNOT (LOGXOR (LOGXOR (LOGXOR
(LOGXOR (LOGXOR (LOGAND (LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND
(LOGXOR (LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A
B) C) D))) (LOGAND (LOGXOR (LOGXOR (LOGAND A B) (LOGAND (LOGXOR A B) C))
(LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND (LOGXOR (LOGXOR (LOGXOR A B)
C) D) E))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGAND A B) (LOGAND (LOGXOR A
B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C) D)
E) F))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGAND A B) (LOGAND
(LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND (LOGXOR
(LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR A
B) C) D) E) F)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C)
D) E) F) G))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGAND A
B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND
(LOGXOR (LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E) F)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR
A B) C) D) E) F) G)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E) F) G) H))))) S) (LOGAND (LOGNOT (LOGXOR (LOGXOR
(LOGXOR (LOGXOR (LOGXOR (LOGAND (LOGAND A B) (LOGAND (LOGXOR A B) C))
(LOGAND (LOGXOR (LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR
(LOGXOR A B) C) D))) (LOGAND (LOGXOR (LOGXOR (LOGAND A B) (LOGAND (LOGXOR
A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGAND A B)
(LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND
(LOGXOR (LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E) F))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A B) C) D))
(LOGAND (LOGXOR (LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR (LOGXOR
(LOGXOR (LOGXOR A B) C) D) E) F)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGXOR A B) C) D) E) F) G))) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR
(LOGXOR (LOGAND A B) (LOGAND (LOGXOR A B) C)) (LOGAND (LOGXOR (LOGXOR A
B) C) D)) (LOGAND (LOGXOR (LOGXOR (LOGXOR A B) C) D) E)) (LOGAND (LOGXOR
(LOGXOR (LOGXOR (LOGXOR A B) C) D) E) F)) (LOGAND (LOGXOR (LOGXOR (LOGXOR
(LOGXOR (LOGXOR A B) C) D) E) F) G)) (LOGAND (LOGXOR (LOGXOR (LOGXOR
(LOGXOR (LOGXOR (LOGXOR A B) C) D) E) F) G) H)))) (LOGAND (LOGXOR (LOGXOR
(LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGAND A B) (LOGAND (LOGXOR A B) C))
(LOGAND (LOGXOR (LOGXOR A B) C) D)) (LOGAND (LOGXOR (LOGXOR (LOGXOR A B)
C) D) E)) (LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C) D) E) F))
(LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C) D) E) F) G))
(LOGAND (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C) D) E) F)
G) H)) (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR (LOGXOR A B) C) D)
E) F) G) H))))
-- Frank Buß, fb@frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
- Previous message: Kenny Tilton: "Re: using function names as variable names? Is it Justified?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
