이 문제는 자리 올림 덧셈기(ripple-carry adder)를 구현하는 문제입니다.

ripple-carry adder - SICP

ripple carry adder에 대해서는 '논리회로' 수업에서 배웠습니다.

그래서 보다 쉽게 구현할 수 있었습니다.

하지만 make-wire 프로시저 등이 이 문제 뒤에 나오는터라 실행을 시키지 않았습니다.

그래서 제 생각으로는 맞는 코드인 듯싶으나 디버그를 하지 않아 잘 모르겠습니다.ㅜ

그럼 이렇게 Full Adder를 이용하여 ripple-carry adder를 만들면

얼마나 기다려야 하는지 계산해보았습니다.

Full Adder는 두 개의 Half Adder와 OR 회로를 가집니다.

Half Adder는 하나의 OR 회로, 두 개의 AND 회로, 하나의 inverter 회로가 있습니다.

따라서 Full Adder는 3개의 OR 회로, 4개의 AND 회로, 2개의 inverter 회로가 있습니다.

이런 Full Adder가 총 n개 있으니 전체에 n을 곱한만큼의 delay가 있을 듯싶습니다.

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 360

;;NB. To use half-adder, need or-gate from exercise 3.28
(define (half-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)
    'ok))

(define (full-adder a b c-in sum c-out)
  (let ((s (make-wire))
        (c1 (make-wire))
        (c2 (make-wire)))
    (half-adder b c-in s c1)
    (half-adder a s sum c2)
    (or-gate c1 c2 c-out)
    'ok))

(define (inverter input output)
  (define (invert-input)
    (let ((new-value (logical-not (get-signal input))))
      (after-delay inverter-delay
                   (lambda ()
                     (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))))

(define (and-gate a1 a2 output)
  (define (and-action-procedure)
    (let ((new-value
           (logical-and (get-signal a1) (get-signal a2))))
      (after-delay and-gate-delay
                   (lambda ()
                     (set-signal! output new-value)))))
  (add-action! a1 and-action-procedure)
  (add-action! a2 and-action-procedure)
  'ok)

(define (logical-and x y)
  (if (and (= x 1) (= y 1))
      1
      0))

(define (or-gate a1 a2 output)
  (define (or-action-procedure)
    (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-procedure)
  (add-action! a2 or-action-procedure)
  'ok)

(define (logical-or x y)
  (if (and (= x 0) (= y 0))
      0
      1))

; answer
(define (ripple-carry-adder An Bn Sn C)
  (define (r-c-adder-iter Ak Bk Sk Ck)
    (cond ((null? Ak) null) ; Cn을 넣으려고 하였으나 Cn은 필요없는 듯싶어 null return으로 끝냄.
          (else
           (full-adder (car Ak) (car Bk) Ck (car Sk) Ck)
           (r-c-adder-iter (cdr Ak) (cdr Bk) (cdr Sk) Ck))))
  (r-c-adder-iter An Bn Sn C))

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.