Professor Sampler’s Notes: The Shannon-Nyquist Sampling Theorem Part I

Topics Covered:

  • Practical sampling

There are things which seem incredible to most men who have not studied mathematics – Archimedes

The curious case of Postman Hertz
Heinrich Hertz

Postman Hertz is Wolfcrow’s only postman, and has never missed a day’s work in twenty years. “He’s leica machine,” people say.

What’s his secret? Exercise. On an average day, he walks for four hours and delivers to twenty houses. He is so perfect he doesn’t miss a single step. He never stops – the very epitome of a continuous periodic signal. Let’s take a typical day for our analysis.

Here’s the map of Wolfcrow, which shows Postman Hertz’s route – beginning and ending at the Post Office (the orange box).
Postman Hertz's typical path in Wolfcrow

Total time taken by Hertz = 4 hours
Total distance covered = 20 km
Total delivery points = 20 (marked in blue dots)

Postman Hertz’s boss, Mr. Shutterbug, wants to see for himself how good Hertz is. He decides to plant a GPS tracker on Hertz that returns his location every hour. Shutterbug guesses one ‘check’ per hour will give him a realistic idea of Hertz’s average day. He has it all figured out. What are his aims?

1. To recreate Hertz’s path precisely
2. To check how many stops Hertz really makes on his rounds

This is what the GPS returned:
One sample per hour
And here’s Shutterbug’s recreation of Hertz’s path from this data:
Map - one sample per hour
Something wasn’t right. Shutterbug couldn’t catch Hertz on a single delivery, and most of the time he was in isolated patches of Wolfcrow. Was Hertz a closet landscape photographer? Even a nincompoop like Shutterbug knew he had to recheck his methods. He decides to sample Hertz’ path every 20 minutes. This is what the GPS returned (assuming Hertz covered the exact same path):
One sample every 20 minutes
The orange spikes are when Hertz was ‘caught’ making a delivery. The black spikes are when he was on the road. Shutterbug was excited. This one should do it! Here’s the recreation:
Map - one sample per 20 minutes
What? Only 3 houses? But the report says 20! That’s 15%! How’s it possible that one tracks a man every 20 minutes over 4 hours and only catch him at 3 houses? This was when Shutterbug decided to get in touch with a professional sampler – me. He should have called me earlier, but when have people listened to engineers?

I figured since Hertz covered 20 houses in 4 hours, he probably covered 5 houses per hour on average. An hour is 60 minutes, so that means 12 minutes per house on average. So I instructed Shutterbug, with a heavy heart (I hated spying on my fellow Crower), to sample Hertz’s route every 12 minutes. This is what resulted:
Sample every 12 minutes
The resulting reconstruction was disappointing:
Map - Sample every 12 minutes
We had nine houses, but still less than half of what he covered (45%). Shutterbug was convinced Hertz wasn’t as good as people made him out to be. I wasn’t too sure, and that night I stayed up to recheck my math.

At 4 a.m., somewhere in between counting sheep jumping over the Post Office fence and the alarm cock’s erratic crowing, I came up with a solution. I couldn’t send an innocent man into retirement.

If Hertz covered 20 houses, then some of them might be bunched up close together and the only way to get all of them was to increase the sampling rate to match that. At 5 samples per hour, we only got 20 samples, and it was ludicrous to expect to catch all 20 houses exactly at those points. Why didn’t I think of that earlier?

With 20 samples, I got 9 houses. If I doubled that to 40 samples, I might get 18. If I wanted all twenty, I was better off with 60 samples. After all, I might have just one chance to change Shutterbug’s mind. After pleading my case, Shutterbug agreed to give it one last try. Here’s what we found with 60 samples over a four hour period:
Sample every 4 minutes
17 out of 20 (85%)! The results stunned Shutterbug, and he recommended Hertz for a promotion. Hertz never knew how close he had come to ruin.

But the result had an unexpected effect on me. I was wrong! I still only had 17 houses, and while it was good enough to convince Shutterbug, it wasn’t good enough for me. I want 20/20! I’m not used to being wrong, you know. I decided to rethink my math, one step at a time. I was going to find the answer no matter what.

Takeaways:

  • Don’t jump to conclusions

Links for further study:

A persistent sampler: http://en.wikipedia.org/wiki/Thomas_Edison

Next: Professor Sampler’s Notes: The Shannon-Nyquist Sampling Theorem Part II
Previous: Professor Sampler’s Notes: Sampling Analog Signals