DSP in the Kentucky Derby

« previous post | next post »

This headline in yesterday's NYT caught my attention: "Despite His Credentials, Nyquist Has Many Doubters". Of course the story is about Nyquist the Horse, who is named after Nyquist the Hockey Player. But for a moment, I thought it might be about Nyquist the Engineer.

Now, you may not have heard of Nyquist the Engineer, but if you're reading this, then you rely on his work many times a day — every time you use a computer or a phone or a (digital) camera or a monitor, or pretty much any other digital device that interacts with continuous signals in the real world.

At least, you rely on some work that bears his name, the Nyquist-Shannon Sampling Theorem. But like Nyquist the Horse, Nyquist the Engineer has some doubters.


The Wikipedia article on the Sampling Theorem notes that

The theorem was also discovered independently by E. T. Whittaker, by Vladimir Kotelnikov, and by others. It is thus also known by the names Nyquist–Shannon–Kotelnikov, Whittaker–Shannon–Kotelnikov, Whittaker–Nyquist–Kotelnikov–Shannon, and cardinal theorem of interpolation.

But the article ends with an unusual section under the heading Why Nyquist?, which starts "Exactly how, when, or why Harry Nyquist had his name attached to the sampling theorem remains obscure", and goes to discuss the history with comments like

Exactly what "Nyquist's result" they are referring to remains mysterious […] This explains Nyquist's name on the critical interval, but not on the theorem. […] it is not a sampling rate, but a signaling rate.

So, doubters.

Whatever Nyquist's role, the history of the sampling theorem is really interesting, as you can learn by reading Hans Lüke, "The origins of the sampling theorem" IEEE Communications Magazine 1999. He starts like this:

In 1948 and 1949, Claude E. Shannon published the two revolutionary papers in which he founded the information theory [1, 2]. In [1] the sampling theorem is formulated as “Theorem 13”:

Let f(t) contain no frequencies over W. Then

$$f(t) = \sum_{-\inf}^{\inf} X_n \frac{\sin \pi (2Wt – n)}{\pi(2Wt – n)}$$

where

$$X_n = f(\frac{n}{2W})$$

It was not until these papers were published that the theorem known as “Shannon’s sampling theorem” became common property among communication engineers, although Shannon himself writes in [2] that

This is a fact which is common knowledge in the communication art.

A few lines further on, however, he adds:

… but in spite of its evident importance [it] seems not to have appeared explicitly in the literature of communication theory.

The following analysis takes the above statement as its starting point. It will become apparent that mathematicians, practicians, and theoreticians in communication engineering came across the implications of the sampling theorem almost independent of one another, and that the links between them did not emerge until later stages of this development.

Lüke's reference [1] is Claude Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal 1948, which has the extraordinary property of being accessible to any bright high-school student, despite being the founding document of the most important new area of mathematics in the 20th century.

Lüke ends his history this way:

The sampling theorem for lowpass functions plays an important role in communication engineering as a connecting link between continuous-time and discrete-time signals. The numerous different names to which the sampling theorem is attributed in the literature — Shannon, Nyquist, Kotelnikov, Whittaker, to Someya — gave rise to the above discussion of its origins. However, this history also reveals a process which is often apparent in theoretical problems in technology or physics: first the practicians put forward a rule of thumb, then the theoreticians develop the general solution, and finally someone discovers that the mathematicians have long since solved the mathematical problem which it contains, but in “splendid isolation.”

Some of the original references:

Edmund Taylor Whittaker, "On the functions which are represented by the expansions of the interpolation theory," Proc. Royal Soc. Edinburgh, Sec. A, vol.35, 1915.
Harry Nyquist,  "Certain topics in telegraph transmission theory",  Transactions of the A.I.E.E., 1928.
Karl Küpfmüller,"Utjämningsförlopp inom Telegraf- och Telefontekniken", ("Transients in telegraph and telephone engineering"), Teknisk Tidskrift 1931.
V. A. Kotelnikov, "On the carrying capacity of the ether and wire in telecommunications", Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA, 1933 (in Russian).
Claude Shannon,  "Communication in the presence of noise", Proceedings of the IRE , 1949.

More of the history can be found in A.J. Jerri, "The Shannon sampling theorem—Its various extensions and applications: A tutorial review", Proceedings of the IEEE, 1977.

Or for a broader and more digestible survey (with pictures!), in the form of a slide deck, see Radomir Stanovic et al., "Some Historical Remarks on Sampling Theorem", which follows the prehistory from Lagrange to Cauchy and Borel — and concludes that

Nyquist considered a different problem, the sampling theorem is a statement dual to that of Nyquist.

I'll take this as qualified support for the view that Nyquist deserves to have his name left on the theorem. And they do leave his name — along with 22 others — on their final slide:

It's a shame, anyhow, that none of these folks have ever had a race horse named after them.

Update — but whatever, Nyquist won the race.

 



8 Comments

  1. David L said,

    May 7, 2016 @ 10:49 am

    Off topic — but I was interested to see Whittaker's name here. As a physics student (in the 1970s) I knew of Whittaker and Watson, an old-school but still useful textbook on analysis. Later I came across his "History of the Theories of Aether and Electricity," which is a nice account of the emergence of Maxwell's theory, but became notorious for claiming that Poincare and Lorentz invented special relativity and that Einstein merely polished the idea up a little.
    https://en.wikipedia.org/wiki/E._T._Whittaker#History_of_science

    I thought of him mainly as a teacher, in other words, and didn't know anything of his original work.

  2. Chappers said,

    May 7, 2016 @ 2:20 pm

    This reminds me of the brand of suncream Riemann, which is not named after a certain prominent Hanoverian mathematician of the mid-19th century, but nevertheless will always bring a mathematician up short.

    @David L I still teach my undergraduates special functions out of Whittaker and Watson: there's almost no improvement in the basic theory in more modern texts, so why not? Especially when it's available for free nowadays. Plus, they could do proper typesetting in them days…

  3. peterv said,

    May 7, 2016 @ 3:22 pm

    The main, and perhaps only, purpose of any human communicative act is to transmit some meaning, whether direct or indirect or phatic, text or sub-text, open or hidden, bluff or double bluff or n-fold bluff. But Shannon's 1948 paper explicitly ignores the semantics of messages. So how could a theory which dismisses meaning have any relevance to human linguistics?

    [(myl) Indeed, how could there be any relevance to human linguistics in a theory that explicitly ignores the semantics of messages, like phonetics, phonology, morphology, or syntax? But the relationships among form, content, and predictability are topics for another day, since the subject of this post is the sampling theorem, which is a different thing entirely.]

  4. maidhc said,

    May 7, 2016 @ 6:50 pm

    As a graduate student, Claude Shannon showed that Boolean algebra could be used to describe the operation of switching circuits. Thus he created two fields of study that are basic to modern technology: switching theory and information theory.

    [(myl) Surely the most consequential master's thesis in history. For more, see Siobhan Robers, "Claude Shannon, the father of the information age, turns 1100100", The New Yorker 4/30/2016.]

  5. peterv said,

    May 8, 2016 @ 2:28 am

    Shannon's use of Boolean algebra 80-odd years after it was first expounded is a good example of the need for society to fund pure, curiosity-driven research without any regard to its potential wider impact or societal value. Boole would never had had his research funded under Britain's current myopic funding regime. Every research proposal submitted to the UK EPSRC needs to include a statement on pathways to impact, as if anyone could predict the future uses of research.

  6. January First-of-May said,

    May 8, 2016 @ 12:48 pm

    @Chappers – and Raymond Poincare, the French president of roughly a century ago, was only distantly related to the famous mathematician Henri Poincare (who had apparently already died by then). But there are apparently more tbings named after the latter than after the former (who was rather mediocre).

  7. Rubrick said,

    May 9, 2016 @ 12:20 am

    @Chappers: This reminds me of the brand of suncream Riemann, which is not named after a certain prominent Hanoverian mathematician of the mid-19th century

    No doubt the task of discovering its true roots is nontrivial.

  8. KeithB said,

    May 9, 2016 @ 9:46 am

    AFAICT, Boole was a mathematics professor. I fail to see how his "research" was "funded" by the state. If so, than most of our esteemed hosts are similarly funded.

RSS feed for comments on this post