オンラインSICP読書女子会 #50 (3.3.4)

オンラインSICP読書女子会 #50 (3.3.4)

練習問題 3.28 - 3.30.

今回利用しているファイル.
分解したのでこまごまいっぱい＞ｘ＜；

circuit-base.scm
circuit-inverter.scm
circuit-and.scm
circuit-or.scm
circuit-or-2.scm
circuit-full-adder.scm
circuit-half-adder.scm
test-inverter.scm
test-and.scm
test-or.scm
test-or-2.scm
test-full-adder.scm
test-half-adder.scm
ex-3.30.scm

3.3.4. デジタル回路シミュレータ

Wire, function box, Inverter, And gate, Or gate.
Half adder.
Full adder.

基本関数箱

Primitive function boxes.

(get-signal wire), (set-signal! wire new-value), (add-action! wire procedure)
(after-delay delay procedure)

机上でやってもよくわからないので組んでみた. 疲れた…！＞＜

1. circuit-half-adder.scm
2. circuit-full-adder.scm
3. circuit-inverter.scm
4. circuit-and.scm
5. circuit-or.scm
6. circuit-base.scm
7. test-inverter.scm
8. test-and.scm
9. test-or.scm
10. test-half-adder.scm
11. test-full-adder.scm

1. 半加算器 (circuit-half-adder.scm)

p.298 にあるそのまま.

; [circuit-half-adder.scm]
;
(define (half-adder a b sum carry)
    (let ((d (make-wire)) (e (make-wire)))
        ; (print "XXX: d="d" e="e)
        (or-gate a b d)
        (and-gate a b carry)
        (inverter carry e)
        (and-gate d e sum)
        'ok))

2. 全加算器 (circuit-full-adder.scm)

p.298 にあるそのまま.

; [circuit-full-adder.scm]
;
(define (full-adder a b c so co)
    (let ((s1 (make-wire)) (c1 (make-wire)) (c2 (make-wire)))
        ; (print "XXX: s="s" c1="c1" c2="c2)
        (half-adder b c s1 c1)
        (half-adder a s1 so c2)
        (or-gate c1 c2 co)
        'ok))

3. NOT 素子 (circuit-inverter.scm)

p.300 にあるそのまま.

; [circuit-inverter.scm]
;

(define inverter-delay 1)


(define (inverter input output)
    (define (invert-input)
        (let ((new-value (logical-not (get-signal input))))
            (after-delay
                inverter-delay
                (lambda ()
                    (and debug (print "INVERTER: " input " >> " output " = " new-value))
                    (set-signal! output new-value)))))
    (add-action! input invert-input)
    'ok)


(define (logical-not s)
    (cond
        ((= s 0) 1)
        ((= s 1) 0)
        (else (error "Invalid signal" s))))

4. AND 素子 (circuit-and.scm)

p.300 にあるそのまま.

; [circuit-and.scm]
;

(define and-gate-delay 1)


(define (and-gate a1 a2 output)
    (define (and-action-procedure)
        (define v1 (get-signal a1))
        (define v2 (get-signal a2))
        (let ((new-value (logical-and (get-signal a1) (get-signal a2))))
            (after-delay
                and-gate-delay
                (lambda ()
                    (and debug (print "AND " a1":"v1 "/" a2":"v2 " >> " output " = " new-value))
                    (set-signal! output new-value)))))
    (add-action! a1 and-action-procedure)
    (add-action! a2 and-action-procedure)
    'ok)


(define (logical-and s1 s2)
    (cond
        ((and (= s1 0) (= s2 0)) 0)
        ((and (= s1 0) (= s2 1)) 0)
        ((and (= s1 1) (= s2 0)) 0)
        ((and (= s1 1) (= s2 1)) 1)
        (else (error "Invalid signal" s1 s2))))

5. OR 素子 (circuit-or.scm)

練習問題 3.28 になる部分.
全/半加算器で使ってるので先に実装.

; [circuit-or.scm]
;

(define or-gate-delay 1)


(define (or-gate a b output)
    (define (or-action-procedure)
        (define av (get-signal a))
        (define bv (get-signal b))
        (let ((new-value (logical-or (get-signal a) (get-signal b))))
            (after-delay
                or-gate-delay
                (lambda ()
                    (and debug (print "OR " a":"av "/" b":"bv " >> " output " = " new-value))
                    (set-signal! output new-value)))))
    (add-action! a or-action-procedure)
    (add-action! b or-action-procedure)
    'ok)


(define (logical-or s1 s2)
    (cond
        ((and (= s1 0) (= s2 0)) 0)
        ((and (= s1 0) (= s2 1)) 1)
        ((and (= s1 1) (= s2 0)) 1)
        ((and (= s1 1) (= s2 1)) 1)
        (else (error "Invalid signal" s1 s2))))

6. ベース部分 (circuit-base.scm)

勝手に作成. ベース部分ではあるけれど, でっかいし気力が持ってかれるしなので読み飛ばし推奨.

; [circuit-base.scm]
;

(define debug #f)
(define tick 0)
(define wires '())
(define delays '())


(define (show)
    (print "[show]")
    (show-internal))


(define (show-internal)
    (print ". tick = " tick)
    (print ". wires:")
    (for-each (lambda (wire-data) (print "> " wire-data)) (reverse wires))
    (print ". delays:")
    (for-each (lambda (delay-data) (print "> " delay-data)) delays)
    'ok)


(define (run-actions)
    ; result: any action happened
    (fold-left
        (lambda (acc wire-data)
            (if (list-ref wire-data 3)
                (begin
                    (list-set! wire-data 3 #f)
                    (for-each (lambda(x) (x)) (list-ref wire-data 2))
                    #t)
                acc))
        #f
        wires))


(define (step)
    (define (step-iter)
        (cond
            ((null? delays) 'ok)
            ((<= (list-ref (car delays) 0) tick)
                (let ((head (car delays)))
                    (set! delays (cdr delays))
                    ((list-ref head 1))
                    (step-iter)))
            (else 'ok)))

    (set! tick (+ tick 1))
    (and debug (print "[step] tick = " tick))
    (run-actions)
    (step-iter))


(define (run-debug)
    (run-step show-internal))


(define (run)
    (run-step (lambda () 'ok)))


(define (run-step f)
    (and debug (print "BEFORE-STEP"))
    (f)
    (and debug (print "ACTIONS"))
    (and (run-actions) (f))
    (cond
        ((null? delays) 'ok)
        (else
            (and debug (print "STEP"))
            (step)
            (run-step f))))


; wire-data:
(define W_NAME    0)
(define W_SIGVAL  1)
(define W_ACTIONS 2)
(define W_CHANGED 3)

(define (make-wire)
    (define name (string->symbol (string-append "w" (number->string (length wires)))))
    (define wire-data (list name 0 '() #f))
    (set! wires (cons wire-data wires))
    name)


(define (get-signal wire)
    (let ((wire-data (assoc wire wires)))
        (and
            wire-data
            (list-ref wire-data 1))))


(define (set-signal! wire sig)
    (let ((wire-data (assoc wire wires)))
        (and
            wire-data
            (begin
                (list-set! wire-data 1 sig)
                (list-set! wire-data 3 #t)
                'ok))))


(define (after-delay delay action)
    (define awake-at (+ tick delay))
    (define delay-data (list awake-at action))
    (set!
        delays
        (sort
            (cons delay-data delays)
            (lambda (a b) (< (list-ref a 0) (list-ref b 0)))))
    'ok)


(define (add-action! wire action)
    (let ((wire-data (assoc wire wires)))
        (and
            wire-data
            (begin
                (list-set! wire-data 2 (cons action (list-ref wire-data 2)))
                'ok))))

7. NOT 素子のテスト (test-inverter.scm)

; [test-inverter.scm]
;
(define (test-inverter)
    (define i (make-wire))
    (define o (make-wire))

    (define (stat-inverter)
        (print "> [stat:inverter]")
        (print "> i = " i ": " (get-signal i))
        (print "> o = " o ": " (get-signal o))
        'ok)

    (inverter i o)

    (newline)
    (print "* (i) = (0)")
    (set-signal! i 0)
    (run)
    (stat-inverter)

    (newline)
    (print "* (i) = (1)")
    (set-signal! i 1)
    (run)
    (stat-inverter)

    'done)


(load "circuit-base")
(load "circuit-inverter")

gosh> (test-inverter)

* (i) = (0)
> [stat:inverter]
> i = w0: 0
> o = w1: 1

* (i) = (1)
> [stat:inverter]
> i = w0: 1
> o = w1: 0
done

8. AND 素子のテスト (test-and.scm)

; [test-and.scm]
;
(define (test-and)
    (define a1 (make-wire))
    (define a2 (make-wire))
    (define o  (make-wire))

    (define (stat-and)
        (print "> [stat:and]")
        (print "> a1 = " a1 ": " (get-signal a1))
        (print "> a2 = " a2 ": " (get-signal a2))
        (print "> o  = " o  ": " (get-signal o ))
        'ok)

    (and-gate a1 a2 o)

    (newline)
    (print "* (a1) = (0)")
    (print "* (a2) = (0)")
    (set-signal! a1 0)
    (set-signal! a2 0)
    (run)
    (stat-and)

    (newline)
    (print "* (a1) = (1)")
    (print "* (a2) = (0)")
    (set-signal! a1 1)
    (set-signal! a2 0)
    (run)
    (stat-and)

    (newline)
    (print "* (a1) = (0)")
    (print "* (a2) = (1)")
    (set-signal! a1 0)
    (set-signal! a2 1)
    (run)
    (stat-and)

    (newline)
    (print "* (a1) = (1)")
    (print "* (a2) = (1)")
    (set-signal! a1 1)
    (set-signal! a2 1)
    (run)
    (stat-and)

    'done)


(load "circuit-base")
(load "circuit-and")

gosh> (test-and)

* (a1) = (0)
* (a2) = (0)
> [stat:and]
> a1 = w0: 0
> a2 = w1: 0
> o  = w2: 0

* (a1) = (1)
* (a2) = (0)
> [stat:and]
> a1 = w0: 1
> a2 = w1: 0
> o  = w2: 0

* (a1) = (0)
* (a2) = (1)
> [stat:and]
> a1 = w0: 0
> a2 = w1: 1
> o  = w2: 0

* (a1) = (1)
* (a2) = (1)
> [stat:and]
> a1 = w0: 1
> a2 = w1: 1
> o  = w2: 1
done

9. OR 素子のテスト (test-or.scm)

; [test-or]
;
(define (test-or)
    (define a (make-wire))
    (define b (make-wire))
    (define o (make-wire))

    (define (stat-or)
        (print "> [stat:or]")
        (print "> a = " a ": " (get-signal a))
        (print "> b = " b ": " (get-signal b))
        (print "> o = " o ": " (get-signal o))
        'ok)

    (or-gate a b o)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (set-signal! a 0)
    (set-signal! b 0)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (set-signal! a 1)
    (set-signal! b 0)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (set-signal! a 0)
    (set-signal! b 1)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (set-signal! a 1)
    (set-signal! b 1)
    (run)
    (stat-or)

    'done)


(load "circuit-base")
(load "circuit-or")

gosh> (test-or)

* (a) = (0)
* (b) = (0)
> [stat:or]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

10. 半加算器のテスト (test-half-adder.scm)

; [test-half-adder.scm]
;
(define (test-half-adder)
    (define a (make-wire))
    (define b (make-wire))
    (define so (make-wire)) ; sum/out.
    (define co (make-wire)) ; carry/out.

    (define (stat-half-adder)
        (print "> [stat:half-adder]")
        (print "> a  = " a  ": " (get-signal a))
        (print "> b  = " b  ": " (get-signal b))
        (print "> so = " so ": " (get-signal so))
        (print "> co = " co ": " (get-signal co))
        'ok)

    (half-adder a b so co)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (set-signal! a 0)
    (set-signal! b 0)
    (run)
    (stat-half-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (set-signal! a 1)
    (set-signal! b 0)
    (run)
    (stat-half-adder)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (set-signal! a 0)
    (set-signal! b 1)
    (run)
    (stat-half-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (set-signal! a 1)
    (set-signal! b 1)
    (run)
    (stat-half-adder)

    'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")

gosh> (test-half-adder)

* (a) = (0)
* (b) = (0)
> [stat:half-adder]
> a  = w0: 0
> b  = w1: 0
> so = w2: 0
> co = w3: 0

* (a) = (1)
* (b) = (0)
> [stat:half-adder]
> a  = w0: 1
> b  = w1: 0
> so = w2: 1
> co = w3: 0

* (a) = (0)
* (b) = (1)
> [stat:half-adder]
> a  = w0: 0
> b  = w1: 1
> so = w2: 1
> co = w3: 0

* (a) = (1)
* (b) = (1)
> [stat:half-adder]
> a  = w0: 1
> b  = w1: 1
> so = w2: 0
> co = w3: 1
done

11. 全加算器のテスト (test-full-adder.scm)

; [test-full-adder.scm]
;
(define (test-full-adder)
    (define a (make-wire))
    (define b (make-wire))
    (define c (make-wire))
    (define so (make-wire)) ; sum/out.
    (define co (make-wire)) ; carry/out.

    (define (stat-full-adder)
        (print "> [stat:full-adder]")
        (print "> a  = " a  ": " (get-signal a))
        (print "> b  = " b  ": " (get-signal b))
        (print "> c  = " c  ": " (get-signal c))
        (print "> so = " so ": " (get-signal so))
        (print "> co = " co ": " (get-signal co))
        'ok)

    (full-adder a b c so co)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (print "* (c) = (0)")
    (set-signal! a 0)
    (set-signal! b 0)
    (set-signal! c 0)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (print "* (c) = (0)")
    (set-signal! a 1)
    (set-signal! b 0)
    (set-signal! c 0)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (print "* (c) = (0)")
    (set-signal! a 0)
    (set-signal! b 1)
    (set-signal! c 0)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (print "* (c) = (0)")
    (set-signal! a 1)
    (set-signal! b 1)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (print "* (c) = (1)")
    (set-signal! a 0)
    (set-signal! b 0)
    (set-signal! c 1)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (print "* (c) = (1)")
    (set-signal! a 1)
    (set-signal! b 0)
    (set-signal! c 1)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (print "* (c) = (1)")
    (set-signal! a 0)
    (set-signal! b 1)
    (set-signal! c 1)
    (run)
    (stat-full-adder)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (print "* (c) = (1)")
    (set-signal! a 1)
    (set-signal! b 1)
    (set-signal! c 1)
    (run)
    (stat-full-adder)

    'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")
(load "circuit-full-adder")

gosh> (test-full-adder)

* (a) = (0)
* (b) = (0)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 0
> c  = w2: 0
> so = w3: 0
> co = w4: 0

* (a) = (1)
* (b) = (0)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 0
> c  = w2: 0
> so = w3: 1
> co = w4: 0

* (a) = (0)
* (b) = (1)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 1
> c  = w2: 0
> so = w3: 1
> co = w4: 0

* (a) = (1)
* (b) = (1)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 1
> c  = w2: 0
> so = w3: 0
> co = w4: 1

* (a) = (0)
* (b) = (0)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 0
> c  = w2: 1
> so = w3: 1
> co = w4: 0

* (a) = (1)
* (b) = (0)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 0
> c  = w2: 1
> so = w3: 0
> co = w4: 1

* (a) = (0)
* (b) = (1)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 1
> c  = w2: 1
> so = w3: 0
> co = w4: 1

* (a) = (1)
* (b) = (1)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 1
> c  = w2: 1
> so = w3: 1
> co = w4: 1
done

ex-3.28. OR gate の実装.

ex-3.28. 実装.

上記, (5) OR 素子と (9) OR 素子のテストの部分で実装済み.
以下再掲.

(再掲) 5. OR 素子 (circuit-or.scm)

; [circuit-or.scm]
;

(define or-gate-delay 1)


(define (or-gate a b output)
    (define (or-action-procedure)
        (define av (get-signal a))
        (define bv (get-signal b))
        (let ((new-value (logical-or (get-signal a) (get-signal b))))
            (after-delay
                or-gate-delay
                (lambda ()
                    (and debug (print "OR " a":"av "/" b":"bv " >> " output " = " new-value))
                    (set-signal! output new-value)))))
    (add-action! a or-action-procedure)
    (add-action! b or-action-procedure)
    'ok)


(define (logical-or s1 s2)
    (cond
        ((and (= s1 0) (= s2 0)) 0)
        ((and (= s1 0) (= s2 1)) 1)
        ((and (= s1 1) (= s2 0)) 1)
        ((and (= s1 1) (= s2 1)) 1)
        (else (error "Invalid signal" s1 s2))))

(再掲) 9. OR 素子のテスト (test-or.scm)

; [test-or]
;
(define (test-or)
    (define a (make-wire))
    (define b (make-wire))
    (define o (make-wire))

    (define (stat-or)
        (print "> [stat:or]")
        (print "> a = " a ": " (get-signal a))
        (print "> b = " b ": " (get-signal b))
        (print "> o = " o ": " (get-signal o))
        'ok)

    (or-gate a b o)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (set-signal! a 0)
    (set-signal! b 0)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (set-signal! a 1)
    (set-signal! b 0)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (set-signal! a 0)
    (set-signal! b 1)
    (run)
    (stat-or)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (set-signal! a 1)
    (set-signal! b 1)
    (run)
    (stat-or)

    'done)


(load "circuit-base")
(load "circuit-or")

ex-3.28. 実行結果.

gosh> (test-or)

* (a) = (0)
* (b) = (0)
> [stat:or]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

ex-3.29. AND/NOT 素子を用いた OR gate の実装.

ex-3.29. 実装.

; [circuit-or-2.scm]
;

(define (or-gate-2 a b output)
    ; Lisp で書くと,
    ;   (lambda (a b)
    ;     (not
    ;       (and
    ;         (not a)
    ;         (not b))))
    ; といったかんじ.
    (let ((ax (make-wire)) (bx (make-wire)) (cx (make-wire)))
        (inverter a ax)
        (inverter b bx)
        (and-gate ax bx cx)
        (inverter cx output)
        'ok))

; [test-or-2]
;
(define (test-or-2)
    (define a (make-wire))
    (define b (make-wire))
    (define o (make-wire))

    (define (stat-or-2)
        (print "> [stat:or-2]")
        (print "> a = " a ": " (get-signal a))
        (print "> b = " b ": " (get-signal b))
        (print "> o = " o ": " (get-signal o))
        'ok)

    (or-gate-2 a b o)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (0)")
    (set-signal! a 0)
    (set-signal! b 0)
    (run)
    (stat-or-2)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (0)")
    (set-signal! a 1)
    (set-signal! b 0)
    (run)
    (stat-or-2)

    (newline)
    (print "* (a) = (0)")
    (print "* (b) = (1)")
    (set-signal! a 0)
    (set-signal! b 1)
    (run)
    (stat-or-2)

    (newline)
    (print "* (a) = (1)")
    (print "* (b) = (1)")
    (set-signal! a 1)
    (set-signal! b 1)
    (run)
    (stat-or-2)

    'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or-2")

ex-3.29. 実行結果

gosh> (test-or-2)

* (a) = (0)
* (b) = (0)
> [stat:or-2]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or-2]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or-2]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or-2]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

ex-3.30. 繰り上がり伝播加算器

ripple-carry adder.

ripple はさざなみっていう意味らしい. なんだかおしゃん・ω・*

ex-3.30. 遅延時間:

ここでは素子を抜ける際の遅延時間を |x| として表現する.

• n=1 の場合 |and|
A1-C と B1-C で時間は同じ.

• n=2 の場合 max(|or|, |and| + |inv|) + 2 * |and| + |or|
  full adder の中を通る経路で使われている素子によって, 変化する.

• n>=3 の場合 max(|or|, |and| + |inv|) + 1 * |and| + (n - 1) * (|and| + |or|)
  これ以降は, |and| + |or| 分だけ増加してゆく.

まとまってないけど以下その計算.

half-adder:

|ha:x-s| = max(|or|, |and| + |inv|) + |and|
|ha:x-c| = |and|

full-adder:

|fa:a-s| = |ha:a-s|
         = max(|or|, |and| + |inv|) + |and|
|fa:a-c| = |ha:a-c| + |or|
         = |and| + |or|

|fa:b-s| = |ha:a-s| + |ha:b-s|
         = 2 * max(|or|, |and| + |inv|) + 2 * |and|
|fa:b-c| = |ha:a-s| + |ha:b-c| + |or|
         = (max(|or|, |and| + |inv|) + |and|) + |and| + |or|
         = max(|or|, |and| + |inv|) + 2 * |and| + |or|

|fa:c-s| = |ha:b-s| + |ha:b-s|
         = 2 * max(|or|, |and| + |inv|) + 2 * |and|
|fa:c-c| = |ha:b-c| + |or|
         = |and| + |or|

|fa:a-c| = |fa:c-c| = |and| + |or|
|fa:b-c| = |fa:a-c| + max(|or|, |and| + |inv|) + |and|


ripple-carry-adder:

|ra(1):x{1}-c| = |ha:x-c|
               = |and|

|ra(n):x{n}-c| = max(|ra(n):a{n}-c|, |ra(n):b{n}-c|, |ra(n-1):x{n-1}-c| + |ra(n):c{n}-c|)

|ra(n):a{n}-c| = |fa:a-c| = |and| + |or|
|ra(n):b{n}-c| = |fa:b-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
|ra(n):c{n}-c| = |fa:c-c| = |and| + |or|

n=2:
|ra(2):c1-c| = |ra(1):c1-c| + |ra(2):c2-c|
             = (|and|) + (|and| + |or|)
             = 2 * |and| + |or|
|ra(2):b2-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
             = max(|or|, |and| + |inv|) + |ra(2):c1-c|
             > |ra(2):c1-c|

n=3:
|ra(3):x1-c| = |ra(2):x1-c| + |ra(3):c3-c|
             = (max(|or|, |and| + |inv|) + 2 * |and| + |or|) + (|and| + |or|)
|ra(3):b3-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
             < |ra(3):x1-c|

ex-3.30. 実装.

; [ex-3.30.scm]
;
(define (ex-3.30)
    (define a1 (make-wire))
    (define a2 (make-wire))
    (define a3 (make-wire))
    (define b1 (make-wire))
    (define b2 (make-wire))
    (define b3 (make-wire))
    (define s1 (make-wire))
    (define s2 (make-wire))
    (define s3 (make-wire))
    (define c  (make-wire))

    (define as (list a1 a2 a3))
    (define bs (list b1 b2 b3))
    (define ss (list s1 s2 s3))

    (define (my-stat)
        (print "> [stat:ripple-carry-adder:3]")
        (print "> a1 = " a1 ": " (get-signal a1))
        (print "> a2 = " a2 ": " (get-signal a2))
        (print "> a3 = " a3 ": " (get-signal a3))
        (print "> b1 = " b1 ": " (get-signal b1))
        (print "> b2 = " b2 ": " (get-signal b2))
        (print "> b3 = " b3 ": " (get-signal b3))
        (print "> c  = " c  ": " (get-signal c))
        (print "> s1 = " s1 ": " (get-signal s1))
        (print "> s2 = " s2 ": " (get-signal s2))
        (print "> s3 = " s3 ": " (get-signal s3))
        'ok)

    (ripple-carry-adder as bs ss c)

    (newline)
    (print "* (as) = (1,0,1)")
    (print "* (bs) = (1,1,0)")
    (set-signal! a1 1)
    (set-signal! a2 0)
    (set-signal! a3 1)
    (set-signal! b1 1)
    (set-signal! b2 1)
    (set-signal! b3 0)
    (run)
    (my-stat)

    'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")
(load "circuit-full-adder")


(define (ripple-carry-adder as bs ss c)
    (if
        (eq? (cdr as) '())
        ; then
        (half-adder (car as) (car bs) (car ss) c)
        ; else
        (let ((d (make-wire)))
            (ripple-carry-adder (cdr as) (cdr bs) (cdr ss) d)
            (full-adder (car as) (car bs) d (car ss) c)
            'done)))

ex-3.30. 実行結果

gosh> (ex-3.30)
* (as) = (1,0,1)
* (bs) = (1,1,0)
> [stat:ripple-carry-adder:3]
> a1 = w0: 1
> a2 = w1: 0
> a3 = w2: 1
> b1 = w3: 1
> b2 = w4: 1
> b3 = w5: 0
> c  = w9: 1
> s1 = w6: 0
> s2 = w7: 1
> s3 = w8: 1
done