SICP Exercise 3.30 ripple-carry-adder

Exercise 3.30.  Figure 3.27 shows a ripple-carry adder formed by stringing together n full-adders. This is the simplest form of parallel adder for adding two n-bit binary numbers. The inputs A1, A2, A3, ..., An and B1, B2, B3, ..., Bn are the two binary numbers to be added (each Ak and Bk is a 0 or a 1). The circuit generates S1, S2, S3, ..., Sn, the n bits of the sum, and C, the carry from the addition. Write a procedure ripple-carry-adder that generates this circuit. The procedure should take as arguments three lists of n wires each -- the Ak, the Bk, and the Sk -- and also another wire C. The major drawback of the ripple-carry adder is the need to wait for the carry signals to propagate. 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?

 SOLUTION

 The code is here.

 Look at the implementation and test results below. I am also printing the number of times the delay procedure is called for each addition. In a freshly constructed ripple-carry-adder when we add two 1-bit numbers, the delay proc is called 16 times. When we add two 2-bit numbers, the delay proc is called 32 times. Note that while constructing a new ripple-carry-adder, every action procedure on every device is called (sometimes even more than once) and the computation happens in response to whatever signals are wired to the adder at the start.

 A full-adder contains two half adders and an or-gate.
A half-adder contains 2 and-gates, 1 or-gate and 1 inverter.
So the total number of components in a full-adder is: {2 * (2 + 1 + 1)} + 1 = 9

 Note that the first computation/processing in any gate happens during its construction. The numbers 16 and 32 above are the number of times the delay proc is called when the ripple-carry-adder is constructed. Each-time an or-gate is constructed, its action procedure is called twice (since add-action! is called twice). The same is true for the and-gate. Each time an inverter is constructed, its action procedure is called once. So when a half-adder is constructed, the delay proc is called {(2 * 2) + (1 * 2) + 1} = 7 times. Since a full-adder contains two half-adders and an or-gate, when a full-adder is constructed, the delay proc is called {(7 * 2) + 2} = 16 times. (This can be seen in the test results below.)

 So the delay in one full-adder is
Full-Adder Delay = {2 * (2 * and-gate-delay + or-gate-delay + inverter-delay)} + or-gate-delay
Therefore, for an n-bit ripple carry adder, the delay will be:

n * [{2 * (2 * and-gate-delay + or-gate-delay + inverter-delay)} + or-gate-delay]

 We also observe in the test results below that when an existing adder is re-used for addition of new input values, there is no fixed value for the number of times the the delay proc is called. This is because only those gates are activated (and action procedures called) that are connected to wires where there is a change in signal.

 Of course, in real circuits, signals flow in parallel and therefore gates will also function in
parallel so the actual delay will be lesser than what is computed above.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more