Understanding the Nyquist Limit

The Nyquist Limit of half the sampling rate, often seemed to me as a ‘magical limit’. After I read the proof I understood it better, and the graphical representation of the overlapping spectra (also seen on the wikipedia page of the proof) is quite convincing. Yet now I found a very interesting and ‘easy’ explanation, which I’m going to relate. The explanation may not be complete, but it certainly gave me a good feel of the limit.

It all started when some late night I was driving with my girlfriend from Haifa to Tel-Aviv. (In Israel, many mathematical school problems start that way :). As it sometimes happens, part of the road was under repairs, and there were ‘danger lights’ alongside the road. These danger lights were many beacons, spaced a few meters apart along the road, each blinking in its own time. Driving alongside them, you could see it as if the ‘light’ was going through them ( see illustration, 0 is unlighted, x is lighted):

… x 0 0 x 0 …

… 0 x 0 0 x …

… 0 0 x 0 0 …

and so on. To me it seemed as if the light was advancing. Let us assume now a light pattern of one lighted, two off, and so on, going forward, one beacon at a time. This is the pattern in the illustration. This pattern however, is identical to the pattern of one lighted, two off, going backwards, two beacons at a time. Just like watching a rotor – you could parse it either way, and both ways are correct. This could be interpreted as aliasing.

At this point – this will already start to ‘smell’ like something is going on with the sampling theorem… Come to think of it, watching a rotor is exactly an example of the application of the sampling theorem! Cool!

(Warning: this is very reminiscent of group theory. Every now and then I will use it a little. To the non-mathematically-inclined: bear with me :)

Let’s move on. Imagine now a finite number of beacons. Let’s say five. Now consider a single light traveling through the beacons. What is the maximum speed in which it can travel, where we still can discern the direction? (this is equivalent to an infinite number of beacons, with a pattern of 1 on, 4 off. Just like Z5 ~= Z/[5])

Let’s check it out. (note: since 5 is prime each speed will generate one pattern only and not more.) We will obviously ignore the zero speed, and move on to the speed of 1. At this speed, the pattern generated is:

x 0 0 0 0
0 x 0 0 0
0 0 x 0 0
0 0 0 x 0
0 0 0 0 x

or in reverse.

At the speed of 2, the pattern generated is:

x 0 0 0 0
0 0 x 0 0
0 0 0 0 x
0 x 0 0 0
0 0 0 x 0

or in reverse.

Notice that we can discern both cases which direction the pattern is going. But a speed of 3, will be exactly the reverse of the speed of two! Equivalently, a speed of four will not be discernible from a reverse of speed 1! If you don’t believe me, try to see it in the patterns above. This is equivalent of saying that over Z5, -1 == 4, and -2 == 3. We can carry on with this, and show it is the same for any n. (In the additive group Zn, it is easy to show that the inverses lie in the different halves of the group). To summarize – given a finite number N of beacons, we will be able to discern the directions of speeds up to floor((N-1)/2). Cool.

I know that for the mathematically inclined this might seem obvious, and for the rest of the world, this could seem a little cryptic. But I’m really happy with finding this connection, and such a simple example of the Nyquist Limit.

Mathematical note: I bet I got a few mathematical things wrong here. I didn’t write a rigorous proof (but I did proof read it). Tell me your corrections, and what you think. I’ll be glad to hear.

This entry was posted in Group Theory, Math. Bookmark the permalink.

2 Responses to Understanding the Nyquist Limit

  1. kirai says:

    maybe is not rigorous but is the best and simplest Nyquist explanation I’ve ever read. Thanks! and keep up with good work! :)

  2. Ilan says:

    Cute!!!

    Hey, Imri, funny lights going in your head, hehehe.
    ;o)

    I just did it the boring way: plotting sample points (in the time domain: -1.0, 1.0, -1.0, 1.0) and, well, it’s just plain obvious that you can’t force a _lower_ frequency sinusoid through these points, exactly two samples per cycle, and somehow it just makes sense (to me) that this is precisely the “amount of information” retained in those sample points, and that they cannot define a higher frequency, either. Hmm? (Perhaps an argument based on symmetry?)

    Say, can you relate this curiosity to the ECC theorems/proofs, too? Y’know, error detection and correction codes, Solomon-Reed, de Bruijn sequences, that stuff… oy, I forget my CS (way fascinating, but, eh, never did have the brains for it). Where’s my Wikipedia?!

    (I’ve gotta try this Google App Engine toy!)