Note: I know absolutely nothing about zero crossings nor signal processing in general. However, I am doing programming exercises that require them. I've searched around but I cannot understand most of the information I'm getting. Hopefully I get clarification here. Feel free to close if it is off topic.

Here are two exercises from a computer science book (Structure and Interpretation of Computer Programs - Section 3.5.3 Exploiting the Stream Paradigm). I'll only include the relevant details.

Exercise 3.74: Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be 1 whenever the input signal changes from negative to positive, -1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

… 1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 …
… 0 0 0 0 0 -1 0 0 0 0 1 0 0 …


The associated second exercise is:

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)

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

note: sense-data is the input signal

My questions are:

  • What is Exercise 3.75 referring to? Is it the large amounts of 0s?
  • Suppose we filter out the noise from the signals in "… 0 0 0 0 0 -1 0 0 0 0 1 0 0 …", should the resulting filtered signal be "… 0 -1 0 1 0 …" or "… -1 1 …"?
  • In this exercise, smoothing is done by averaging each value of the input signal with the previous value, for the life of me, I don't understand what that should do and why we do it?

1 Answer 1


Without knowing the context, here is what probably is meant:

3.75 refers to a more real-world sensor. The sensor described in 3.74 apparently is assumed to be perfect, ie whenever there is a negative/positive sensor data, the true signal does have the associated property. Ideal sensors, however, do not exist and 3.75 tells you, that your sensor does have imperfections that lead to spurious false sign alterations. The sensor shall be assumed to produce randomly additional zero-crossings that might look like that:

Instead of: 1 0  1 2 3  1 -5 -2 -2 -1 5 3 
You get:    1 3 -2 3 2 -2 -4  3 -2 -1 2 3 

Your example data suggested that a positive/negative periods are typically longer than just one measurement. You are supposed to "harden" your filter a bit to still provide the valid zero-crossings. This filter will never be perfect, but it should be better than the naive filter you probably implemented for 3.74.

In 3.74 you probably implemented a simple if-check: If the sign alternates between measurement $n-1$ and $n$, spit out the corresponding 1 or -1. A hardened filter could be implemented by looking back $n-k$ points with $k=1,2,3,...$ chosen appropriately and spit out a 1 or -1 if all of the $k$ points were of the same sign. This, however, would introduce a delay into your filter, and it would miss zero-crossings that are shorter than $k$ points. So, key would be to know the shortest duration between two zero crossings and choose $k$ smaller than that, and it would be important to know whether or not the delay is acceptable.

And no, noise does not refer to the zeros in your signal ;)

  • $\begingroup$ Two questions: 1. How can I get started of knowing the shortest duration between two zero crossings? And 2. How would I know if the delay is acceptable? $\endgroup$ Commented Mar 24, 2019 at 7:08
  • $\begingroup$ Sorry, it seems I left out some important information because I wanted to just focus on the relevant details. I thought I now know what to do but got stuck on smoothing. The relevant texts I posted on exercise 3.75 did not give all the details, I updated the question with the complete description of the exercise and an additional question. $\endgroup$ Commented Mar 24, 2019 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.