SICPを読む(109) 問題3.28 - 3.32 - ディジタル回路のシミュレータ

Scheme

楽しいMIL記号の時間です。


加算器 - Wikipediaみたいなシミュレータを作っていきます。

問題 3.28

オアゲートを作れ。という問題。

(define (logical-or a b)
  (cond ((or (and (= a 1) (= b 1))
             (and (= a 0) (= b 1))
             (and (= a 1) (= b 0))) 1)
        ((and (= a 0) (= b 0) 0))
        (else
          (error "Invalid signal" s))))

(define (or-gate a1 a2 output)
  (let ((or-action-proc
          (lambda ()
            (let ((new-value (logical-or (get-signal a1)
                                         (get-signal a2))))
              (after-delay *or-gate-delay*
                           (lambda ()
                             (set-signal! output new-value)))))))
  (add-action! a1 or-action-proc)
  (add-action! a2 or-action-proc)
  'or-gate))

ふふ。回答は簡単なんだけど、ここまでのコーディングが結構めんどいぜ。


オアゲートが出来たので、半加算器を動かしてみる。

(define (harf-adder a b s c)
  (let ((d (make-wire))
        (e (make-wire)))
    (or-gate a b d)
    (and-gate a b c)
    (inverter c e)
    (and-gate d e s)))

(define a (make-wire))
(define b (make-wire))
(define s (make-wire))
(define c (make-wire))

(set-signal! a 1)
(set-signal! b 1)

(harf-adder a b s c)

(propagete) ; done

(probe 's s) ; s 5 New-value = 0
(probe 'c c) ; c 5 New-value = 1

1 + 1 = 10(2)

スゲー足し算した！！


Cで書くと、こんな感じ。

#include <stdio.h>

int main(void)
{
    int a = 1;
    int b = 1;

    printf("s = %d\n", (a | b) & ~(a & b)); /* a ^ b */
    printf("c = %d\n", a & b);

    return 0;
}

と、サックリ書けちゃうので、あんまりシミュレタ部分は重要では無くて、今回は、after-delayを使った遅延がポイントになりそうな感じ。

問題 3.29

inverterとand-gateを使って、or-gateを作る。

くらげ、くらげ。

(define (or-gate a b output)
  (let ((c (make-wire))
        (d (make-wire))
        (e (make-wire)))
    (inverter a c)
    (inverter b d)
    (and-gate c d e)
    (inverter e output)
    'or-gate))

最初,凄い図になったのは秘密。

全加算器

半加算器は1+1で、全加算器は1+1+1をする。つまり、最小が0,最大が3。

これおもろいな。

(define (full-adder a b c-in sum c-out)
  (let ((s (make-wire))
        (c1 (make-wire))
        (c2 (make-wire)))
    (harf-adder b c-in s c1)
    (harf-adder a s sum c2)
    (or-gate c1 c2 c-out)
    'full-adder))
  • 1+1をすると、10(2)になるので1を置くスペースが出来る。つまり、次に1を足してもキャリーは発生しない。
  • 1+0をすると、01(1)になるので、次はキャリーが発生するか、しないかわからない。
  • だから、キャリーをorすれば、1+1+1の演算の組合せを処理できる。おもろいな。

問題 3.30

繰上り伝播加算器を作れと。

list->number,number->listはいつも使ってる奴。

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))

(define (list->number l . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (l cont)
                  (if (null? l)
                      (cont 0 0)
                      (iter (cdr l) (lambda (sum k)
                                      (cont (+ (* (car l) (expt b k)) sum)
                                            (+ k 1))))))))
          (iter l (lambda (sum k) sum))))

(define (ripple-carry-adder a b)
  (letrec ((list->wire (lambda (n)
                         (map (lambda (x)
                                (let ((w (make-wire)))
                                      (set-signal! w x)
                                      w))
                              (number->list n 2))))
           (a-wires (list->wire a))
           (b-wires (list->wire b))
           (res (fold-right
                  (lambda (a b acc)
                    (let* ((sum (make-wire))
                           (carry (make-wire)))
                      (full-adder a b (car acc) sum carry)
                      (cons carry
                            (cons sum (cdr acc)))))
                  (list (make-wire))
                  a-wires
                  b-wires)))
    (propagete)
    (list->number (map get-signal res) 2)))

(ripple-carry-adder 12345678 11111111) ; 23456789

10進数→2進数→演算→10進数っと。

2進数にした時に、同じ桁になってないと桁落ちするのは仕様です。ホントは同じ桁になるようにゼロを補完しないとダメ。


一桁計算するのに、半加算器+半加算器+オアゲートが必要なので、n桁計算するにはn倍の計算が必要。しかも2進数なので・・・。

問題 3.31

新しいアクションを追加したのに、反映できてない事になる。つまり、アクションの連鎖が起こらないので、値が変わらない。

問題 3.32

順番どうりに進まないとおかしなことになることはわかるけど、イマイチこのシステムが掴みきれてないな。