SICP Exercise 3.75 zero-crossings on noisy signal

Exercise 3.75.  Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:

(define (make-zero-crossings input-stream last-value)
  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
    (cons-stream (sign-change-detector avpt last-value)
                 (make-zero-crossings (stream-cdr input-stream)
                                      avpt))))

This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)

SOLUTION

 Explanation: Louis Reasoner's logic does not average the right quantities. Instead of averaging each value of the sensor data with the previous value, it averages each value with the previous *average*. So the smoothed signal will gradually drift away from the raw sensor signal.

 The attached graphs show how the different signals compare with each other. The first graph shows what happens when we do the two types of average-smoothing of a stream of random values. We can see that my implementation more closely tracks the raw signal than Louis' implementation.

The second graph shows the same graphs for a values produced by a parabolic function:

 f(x) = x^2 - 15

 It is easy to see how Louis's stream of average values gradually diverges from the 
raw signal whereas my average stream tracks the raw stream more closely.

 The code and tests are here.



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