sicp-ex-3.30

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 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 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 

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

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

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

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