# sicp-ex-3.30

3pmtea

```
;;
(define (ripple-carry-adder a-list b-list s-list c)
(let ((c-list (map (lambda (x) (make-wire)) (cdr a-list)))
(c-n (make-wire)))
a-list
b-list
(append c-list (list c-n))
s-list
(cons c c-list))
(set-signal! c-n 0)
'ok))

```

What is the delay needed to obtain the complete output from an n -bit ripple-carry adder, expressed in terms of the delays for and-gates, or-gates, and inverters?

```Let
Da = and-gate-delay
Do = or-gate-delay
Di = inverter-delay

In a half-adder in Figure 3.25,
Delay of A->SUM, Dh(A->SUM) = Do + Da
Delay of A->C, Dh(A->C) = Da
Delay of B->SUM, Dh(B->SUM) = 2Da + Di
Delay of B->C, Dh(B->C) = Da

In a full-adder in Figure 3.26,
Delay of A->SUM, Df(A->SUM) = Dh(A->SUM)
= Do + Da
Delay of A->Cout, Df(A->Cout) = Dh(A->C) + Do
= Da + Do
Delay of B->SUM, Df(B->SUM) = Dh(A->SUM) + Dh(B->SUM)
= Do + 3Da + Di
Delay of B->Cout, Df(B->Cout) = Dh(A->SUM) + Dh(B->C) + Do
= 2Do + 2Da
Delay of Cin->SUM, Df(Cin->SUM) = 2Dh(B->SUM)
= 4Da + 2Di
Delay of Cin->Cout, Df(Cin->Cout) = Dh(B->SUM) + Dh(B->C) + Do
= 3Da + Do + Di

In a ripplr-carry adder in Figure 3.27,
Because Cn always keeps 0. So in the first processing full adder(connecting An, Bn, Cn, Sn, Cn-1), we don't have to take into account the delay from Cn to Sn and the delay from Cn to Cn-1.

Delay of Sn, D(Sn) = max(Delay from An to Sn, Delay from Bn to Sn)
= max(Df(A->SUM), Df(B-SUM))
= Df(B->SUM)
= Do + 3Da + Di
Delay of Cn-1, D(Cn-1) = max(Delay from An to Cn-1, Delay from Bn to Cn-1)
= max(Df(A->Cout), Df(B->Cout))
= Df(B->Cout)
= 2Do + 2Da

Delay of Sn-1, D(Sn-1) = max(max(Delay from An-1 and Bn-1 to Sn-1),
(Delay of Cn-1 + Delay from Cn-1 to Sn-1))
= max(D(Sn), D(Cn-1) + Df(Cin->SUM))
= max(Do + 3Da + Di, 2Do + 2Da + 4Da + 2Di)
= 2Do + 2Da + 4Da + 2Di
= D(Cn-1) + Df(Cin->SUM)
Delay of Cn-2, D(Cn-2) = max(max(Delay from An-1 and Bn-1 to Cn-2),
(Delay of Cn-1 + Delay from Cn-1 to Cn-2))
= max(D(Cn-1), D(Cn-1) + Df(Cin->SUM))
= D(Cn-1) + Df(Cin->Cout)

So similarly,
Delay of Sn-2, D(Sn-2) = D(Cn-2) + Df(Cin->SUM)
= D(Cn-1) + Df(Cin->Cout) + Df(Cin->SUM)
Delay of Cn-3, D(Cn-3) = D(Cn-2) + Df(Cin->Cout)
= D(Cn-1) + 2Df(Cin->Cout)

Finally,
Delay of S1, D(S1) = D(Cn-1)+ (n-2)*Df(Cin->Cout) + Df(Cin->SUM)
Delay of C, D(C) = D(Cn-1) + (n-1)*Df(Cin->Cout)

So we have the final delay:
Delay = max(D(S1), D(C))
= D(Cn-1)+ (n-2)*Df(Cin->Cout) + max(Df(Cin->SUM), Df(Cin->Cout))
= 2Do + 2Da + (n - 2)*(3Da + Do + Di) + max(4Da + 2Di ,3Da + Do + Di)
= 2Do + 5Da + Di + (n - 2)*(3Da + Do + Di) + max(Da + Di, Do)
```

```
;;a
(define (ripple-carry-adder Ak Bk Sk C)
(define (iter A B S c-in c-out)
(if (null? A)
S
(begin (full-adder (car A) (car B)
c-in (car S) c-out)
(iter (cdr A) (cdr B) (cdr S)
(c-out) (make-wire)))))
(iter Ak Bk Sk C (make-wire)))

```
```

;;a
(define (ripple-carry-adder a b s c)
(let ((c-in (make-wire)))
(if (null? (cdr a))
(set-signal! c-in 0)
(ripple-carry-adder (cdr a) (cdr b) (cdr s) c-in))
(full-adder (car a) (car b) c-in (car s) c)))
```
```

(define (ripple-carry-adder a b c-in sum)
(if (not (null? a))
(let ((carry (make-wire)))
(full-adder         (car a) (car b) c-in (car sum) carry)
(ripple-carry-adder (cdr a) (cdr b) carry (cdr sum)))))

;;some convinience methods to test the adder
(define (build-wires input-signals)
(if (null? input-signals)
'()
(let ((new-wire (make-wire)))
(set-signal! new-wire (car input-signals))
(cons new-wire (build-wires (cdr input-signals))))))

(define (get-signals wires)
(map (lambda (w) (get-signal w)) wires))

;;biggest digit first
(define (to-binary number)
(if  (< number 2)
(list number)
(cons (mod number 2) (to-binary (div number 2)) )))

;;simulation
(define the-agenda (make-agenda))
(define inverter-delay 1)
(define and-gate-delay 1)
(define or-gate-delay 1)

(define a (build-wires '(0 0 1 0 0 0))) ;;4
(define b (build-wires '(1 1 0 1 0 0))) ;;11
(define s (build-wires '(0 0 0 0 0 0)))
(define c-in (make-wire))
(ripple-carry-adder a b c-in s)

(propagate)
(get-signals s) ;;should be 15
```

Added a couple of convenience procedures if someone wants to play with adders and multipliers

the delays of An or Bn are always 0,so the delays of Cn and Sn are only depends on Cn-1-delay. the recursion formula of Cn-delay is

```(+ Cn-1-delay
(* 2 and-gate-delay)
or-gate-delay
(max or-gate-delay
(+ and-gate-delay
inverter-delay)))
```

and C0-delay equals 0,so the general formula of Cn-delay is

```(+ (* 2 n and-gate-delay)
(* n or-gate-delay)
(* n (max or-gate-delay
(+ and-gate-delay
inverter-delay)))
```

Sn-delay is

```(+ Cn-1-delay
(* 2
and-gate-delay)
(* 2
(max or-gate-delay
(+ and-gate-delay
inverter-delay))))
```

equals

```(+ (* 2 n and-gate-delay)
(* (- n 1) or-gate-delay)
(* (+ n 1) (max or-gate-delay
(+ and-gate-delay
inverter-delay)))
```

Sphinxsky

```

(define (ripple-carry-adder a-list b-list s-list c)
(if (null? a-list)
(begin (set-signal! c 0) c)
(begin
(car a-list)
(car b-list)
(cdr a-list)
(cdr b-list)
(cdr s-list)
(make-wire))
(car s-list)
c)
c)))

;; ============================test============================

(define (inc init)
(lambda (m)
(cond ((number? m)
(set! init (+ init m)))
((eq? m 'get) init))))

(define counter (inc 0))

(counter 1)
(counter 'get))

(define (make-wire)

(define set-signal! set-cdr!)

(define (full-adder a b c-in sum c-out)
(newline)
(display (list a b c-in sum c-out)))

(list 1 2 3 4 5 6 7 8)
(list 1 2 3 4 5 6 7 8)
(list 1 2 3 4 5 6 7 8)
(cons 'c 'out))

; (define t-and and-gate-delay)
; (define t-or or-gate-delay)
; (define t-not inverter-delay)

; (define t-ha-s (+ t-and (max t-or (+ t-not t-and))))
; (define t-ha-s
; (if (>= t-or (+ t-not t-and))
; (+ t-and t-or)
; (+ (* 2 t-and) t-not)))

; (define t-ha-c t-and)

; (define t-fa-s (+ t-ha-s (max 0 t-ha-s)))
; (define t-fa-s (* 2 t-ha-s))

; (define t-fa-c (+ t-or (max t-ha-c (+ t-ha-c (max 0 t-ha-s)))))
; (define t-fa-c (+ t-or t-ha-c t-ha-s))
; (define t-fa-c (+ t-or t-and t-ha-s))

; (= (- t-fa-s t-fa-c) (- t-ha-s t-or t-and))
; (if (>= t-or (+ t-not t-and))
; (= t-fa-s t-fa-c)
; (>= t-fa-s t-fa-c))
; (= (max t-fa-s t-fa-c) t-fa-s)
; (define t-fa t-fa-s)

; (define t-rca-c (+ t-fa-c (max 0 0 t-rca-c1)))
; (define t-rca-c (+ t-fa-c t-rca-c1))
; (define t-rca-ci (+ t-fa-c t-rca-ci+1))

; (define t-rca-s1 (+ t-fa-s (max 0 0 t-rca-c1)))
; (define t-rca-s1 (+ t-fa-s t-rca-c1))

; (define t-rca (max t-rca-c t-rca-s1 t-rca-s2 ... t-rca-sn))
; (define t-rca t-rca-s1)
; (define t-rca (+ t-fa-s t-rca-cn (* (- n 1) t-fa-c)))

; (define t-rca-cn 0)

; (define t-rca
; (+  (* (- n 1) t-or)
; (* (- n 1) t-and)
; (* (+ n 1) t-ha-s)))
; (define t-rca
; (if (>= t-or (+ t-not t-and))
; (* 2 n (+ t-or t-and))
; (+ (* (- n 1) t-or)
; (* (+ n 1) t-not)
; (* (+ (* 3 n) 1) t-and))))
```