Talk:Nyquist–Shannon sampling theorem/Archive 3

Archive 1

Archive 2

Archive 3

Figs 3, 4 and 8 -- very unclear

These figures are not very clear and should be tidied up by someone more knowledgeable than myself.

Problems:

1. The term "images" is introduced without explanation. From my mostly-forgotten understanding of Shannon's theorem, it appears to me that these "images" are similar to what are called "sidebands" in radio communications. Whatever "images" are, they should be explained either in the text or the figures.

2. The lettering on the frequency scale is unclear, particularly for Fig 3. For example, what is supposed to be made of "-f+ BB"? Some of the lettering should be moved above the scale to get it out of the way of the others. —Preceding unsigned comment added by Guyburns (talk • contribs)

Fig 3 was an .svg file and was reverted to the .png file it previous was. They tell us that the vector graphics versions of the same drawn image is better because they are scalable without sampling artifacts, but in fact, because of some screw up, the .svg files never appear the same uploaded as they were created as one can see from the comments of the image creator at Commons. The letters were jammed together. The .png file is better.

Images are not quite the same as "sideband" like in single sideband or double sideband in AM communications. If your reference point is that of an amateur radio operator or similar, images from sampling are like what happens with what we used to call a "crystal calibrator" that began as a 100 kHz signal, then passed through a nonlinearity to create more images of that 100 kHz at integer multiples of 100 kHz. The sampling operation is such a non-linear operator that takes the original spectrum and creates copies of that original spectrum centered at integer multiples of f_s. Those copies are the images and an ideal brickwall filter can remove the images while leaving the original spectrum unchanged. 70.109.185.199 (talk) 03:23, 27 April 2010 (UTC)

Dubious external link

'Undersampling and an application of it' looks a little dubious to me. It starts out quite interesting but further down some rambling starts. I'm not sure if an encyclopedia should link to this site. Even if it is legit, I don't think it's entirely on topic. In accordance with wiki guidelines to avoid external links I'd vote to remove it (and possibly use it as a reference rather than an external link in an article more focused on undersampling, in case it meets the quality guidelines). 91.113.115.233 (talk) 08:00, 18 August 2010 (UTC)

Angular frequency vs. Frequency

I think the article should show equivalent forms of the sampling theorem stated in terms of angular frequency, as many textbooks use this convention. I realize its simple to convert, but still... 173.206.212.10 (talk) 03:39, 23 November 2010 (UTC)

You might be right, but sometimes I wish we would stamp out nearly all of the use of angular frequency in EE lit because either the Fourier Transform is not "unitary" (a scaling difference between forward and inverse F.T.) or there is this awful $1/{\sqrt {2\pi }}$ scaling factor in both forward and inverse. Having a unitary transform with no scaling factor in front makes it easy to remember how specific transforms are scaled (like the rect() and sinc() functions) and makes theorems like Parsevals and duality much simpler. 71.169.180.100 (talk) 06:57, 23 November 2010 (UTC)

The Sampling Process Section

The article currently states: "In practice, for signals that are a function of time, the sampling interval is typically quite small, on the order of milliseconds, microseconds, or less."

This is not really true - it depends on which "practice" to which you are referring. What about long-term studies? Moreover, this sentence is not really helpful. It doesn't add any useful or insightful information to the article. — Preceding unsigned comment added by Wingnut123 (talk • contribs) 16:46, 22 March 2011 (UTC)

Sentence from intro removed

I removed the following sentence from the introductory section. It is not really related to the Nyquist-Shannon theorem and furthermore it is false.

A signal that is bandlimited is constrained in how rapidly it changes in time, and therefore how much detail it can convey in an interval of time.

Using results from Robert M. Young, An Introduction to Nonharmonic Fourier Series, Academic Press, 1980, one can show without much trouble that the following is true:

For every B>0, every f∈L²([a,b]) and every ε>0, there exists a function g∈L²(R) which is band-limited with bandwidth at most B and such that $\int _{a}^{b}|f-g|^{2}\;dx<\epsilon$.

So band-limited functions can change extremely rapidly and can convey arbitrary large amounts of detail in a given interval, as long as one doesn't care about what happens outside of the interval. AxelBoldt (talk) 22:56, 15 October 2011 (UTC)

Your point is taken, and the sentence should probably be removed (if not reworded). However, I think your example might actually weaken your argument. After all, g is not chosen uniformly over all B, a, and b. Moreover, your f is taken from L², which constrains the behavior of the function substantially. So even though the wording of the phrase you removed was poor, I think there is still a relevant sentiment which could be re-inserted that does not go against your example (perhaps something about the information content of a bandlimited signal being captured entirely (and thus upper bounded) by a discrete set of samples with certain temporal characteristics). —TedPavlic (talk/contrib/@) 05:09, 16 October 2011 (UTC)

I've never liked that sentence much either, since it has no definite meaning. Even the information rate is not limited to be proportional to B, unless you include noise, so it's not clear what is intended by "how much detail it can convey". Dicklyon (talk) 05:13, 16 October 2011 (UTC)

• g is not chosen uniformly over all B, a, and b.

True, g must depend on B, the bandwidth we desire, and on a and b, since that's the time-interval we are looking at. In a sense that is the whole point: if you focus solely on one time interval, any crazy behavior can be prescribed there for a band-limited function, and furthermore you can require the bandwidth to be as small as you want.

• f is taken from L², which constrains the behavior of the function substantially

That's correct, but L²[a,b] has a lot of detailed and extremely rapidly changing stuff in it. For example, you could encode all of Wikipedia as a bit string in an L²[0,1] function, where a 1 is encoded as a +∞ singularity and a 0 is a -∞ singularity. Choosing your ε wisely, you will find a band-limited g (with bandwidth as small as you want!) that still captures all the crazyness that is Wikipedia.

AxelBoldt (talk) 18:44, 16 October 2011 (UTC)

No, the point is that "constrained in how rapidly it changes in time" relates to the size of the function. And indeed, the L²-norm of the derivative of a band-limited function (indeed any derivative) is bounded by the product of (a power of) the bandwidth and the L²-norm of the function itself.

$\|f'\|_{2}=\|{\widehat {f'}}\|_{2}=\|\omega {\hat {f}}(\omega )\|_{2}\leq \sup _{\omega \in [-B,B]}|\omega |\cdot \|{\hat {f}}\|_{2}=B\cdot \|f\|_{2}$

Or the other way around: given such a band-limited approximation for the restriction to an interval, the behavior outside of the interval can and typically will be explosive. And more so with increasing accuracy of the approximation--LutzL (talk) 15:32, 22 November 2011 (UTC)

Question

Isn't it the case that in practice, due to the possibility of accidentally sampling the ‘nodes’ of a wave, frequencies near the limit will suffer on average an effective linear volume reduction of 2/pi? — Preceding unsigned comment added by 82.139.90.173 (talk) 04:57, 6 March 2012 (UTC)

In practice, "the limit" is chosen significantly above the highest frequency in the passband of the anti-aliasing filter, to accommodate the filter's skirts. So I think the answer is "no". And I have no clue how you arrived at the 2/π factor. It might help to explain that.

--Bob K (talk) 05:42, 6 March 2012 (UTC)

It depends on the filters used. If you reconstruct with square pulses instead of sincs (or zero-order hold instead of impulses into a sinc filter), then you get a rolloff at Nyquist that's equal to an amplitude gain of 2/pi, which comes from evaluating the sinc in the frequency domain, since that's the transform of the rect. It's nothing to do with "accidentally sampling the nodes". Dicklyon (talk) 05:50, 6 March 2012 (UTC)

New section by Ytw1987

New editor User:Ytw1987 has been adding a bunch of stuff on nonuniform sampling and nonuniform DFT here and elsewhere, all sourced to one book by Marvasti. It's probably not bad stuff, but it's big and complicated, not well wikified, badly styled, and smacks of WP:SPA or WP:COI. If someone else has the time to help assess the new material, and advise him on how to make it more suitable, that would be great. Dicklyon (talk) 19:17, 4 July 2012 (UTC)

The new material is now in Nonuniform sampling, which seems like a more appropriate place for it. It needs work, if anyone if up for it. Dicklyon (talk) 23:51, 5 July 2012 (UTC)

Good solution. --Bob K (talk) 15:17, 6 July 2012 (UTC)

Issues with section on Shannon's proof

There are some issues with the proof outlined in the section. It is not clear what is assumed about the function f. The context is the Hilbert space L^2(R) but, a priori, the argument doesn't hold for elements of L^2(R). For one thing, pointwise evaluation doesn't make sense for elements of L^2. Also, the very first equation

$f(t)\,$

$={1 \over 2\pi }\int _{-\infty }^{\infty }F(\omega )e^{i\omega t}\;{\rm {d}}\omega \$

assumes Fourier inversion formula holds for f, which again does hold for general elements of L^2. For counter example, take the sinc function; the integral does not converge. This only works if f is assumed to have slightly better decay at infinity, to be in L^1.

This can be cleaned up as follows:

If f in L^2 has Fourier transform lying in the Hilbert subspace $\{F(\omega ),\;\;F_{|_{|\omega |>W}}=0\}$ then the well-definedness of the Fourier transform implies that f = g almost everywhere for a continuous function g.

The Stone-Weierstrass theorem shows the family $\{e^{i\omega {n \over {2W}}}\}_{n\in \mathbb {Z} }$ is an orthonormal basis for $\{F(\omega ),\;\;F_{|_{|\omega |>W}}=0\}$. So their inverse Fourier transforms $\sin \pi (2Wt-n) \over \pi (2Wt-n)$ is an orthonormal basis for L^2 elements of bandwidth limit W.

One then directly computes the Fourier coefficient in the t-domain, obtaining the L^2-series $f(t)=\sum _{n=-\infty }^{\infty }f({n \over {2W}}){\sin \pi (2Wt-n) \over \pi (2Wt-n)}.\,$ I have a reference somewhere that says the equality in fact holds pointwise but I am not sure how that goes.

From the mathematical point of view, loosely speaking, the theorem holds because one is dealing with a compact set [-W, W] in the frequency domain. This leads to a situation similar to what we have for the circle, whose Pontryagin dual is the discrete set Z. Mct mht (talk) 00:37, 12 July 2012 (UTC)

If you think it's important to know what assumptions Shannon was making, it would be good to check his papers before just rewriting his proof and calling your proof his, no? Dicklyon (talk) 07:10, 19 July 2012 (UTC)

I don't want to get into an edit conflict. That section, as is, is not clean at all. Shannon, being an engineer, doesn't state any assumptions in his paper. It doesn't make sense to talk about a "proof" in the absence of a even clear statement. We don't call Fourier's justifications of theorems bearing his name "proofs" either and wouldn't teach those "proofs" to students. It's questionable whether a word by word reading of Shannon's arguments belongs in the article.

Both the statement of the sampling theorem I gave and proof outlined is very standard in the harmonic analysis literature. The article is currently wanting mathematically. Hopefully something will be done about it, while preserving other points of view. Mct mht (talk) 16:48, 19 July 2012 (UTC)

Signals are in practice continuous functions, so is f. The Fourier integral exists for any compactly supported L2-function F, I don't get the insistence on L1 in this context, even if it is a tradition. The integral on the right hand side gives a continuous function in t. (Again, F has compact support. This is the stated assumption.) -- Shannon was a mathematician, cryptography and cybernetics were still mathematical topics in his time (or Hardy would be an engineer too). The theorem and proof in his article are short sketches of commonly known facts, serving to introduce the concept of orthogonality of signals and "dimension per time" of a band-limited transmission channel. As a sketch his treatment of Fourier theory is exact enough. Please do also note that strict proofs that are drowned in technicalities are not covered by the guidelines of the mathematics project in wikipedia. Short proofs or sketches that illuminate a topic are the exception.--LutzL (talk) 18:29, 19 July 2012 (UTC)

That any compactly supported L^2-function F also lies in L^1, by Holder's inequality, is the point. If it's merely in L^2, then there is no inversion in the sense of the Fourier inversion formula. On L^2, the (inverse, in this case) Fourier transform is not given by formula, but via a density argument. It is a fact (needed in this case) that on the intersection of L^1 and L^2, this agrees with the usual integral formula on L^1.

Shannon's sketch indeed works with a little care, and it also happens to be pretty standard. That was the intention of the edit. Also, the proof doesn't come close to the "too technical" threshold, in my opinion: argue that the inversion works a la Shannon, identify a natural orthonormal basis using Stone-Weierstrass, go back to time domain, done. Short and sweet. Mct mht (talk) 13:31, 20 July 2012 (UTC)

There is no inversion involved, the formula is the definition of a bandlimited function as the reverse Fourier transform of a compactly supported function. That the Fourier series is the representation in an orthogonal basis in L2([-W,W]) is a standard fact, there is, in this given context, nothing to "construct" or to refer to "Stone-Weierstrass" (which is a last part in one of the proofs of the completeness of the basis. A nice proof, but one that belongs into the Fourier series article. This is Wikipedia, this is the internet, links exist for a reason). So indeed you are trying to load up the proof or sketch thereof with unnecessary technical "graffiti".--LutzL (talk) 13:43, 20 July 2012 (UTC)

Of course there is inversion involved. Sure, the inverse Fourier integral is defined, since the spectrum lies in L^1 also. Inversion comes in precisely because one is trying to recover original signal from the spectrum. Also, without knowing you have a orthonormal basis, simply taking it as a definition is pretty pointless; you can't even assume you are not losing any information on the spectrum in the L^2 sense. I am happy to leave the article alone but that is ignorant. Mct mht (talk) 14:56, 20 July 2012 (UTC)

common misconception surrounding digital audio

could someone add this to the article? basically, it says that most people think (I certainly did, and was surprised to learn otherwise) that sampling is by its very nature inexact (no doubt prompted by pictures where a stair-stepped jagggedy line is overlaid on a smooth sinusoid), but the theorem says (it does, doesn't it?) that the digital signal contains just enough information to faithfully restore the analog signal. Уга-уга12 (talk) 19:06, 26 July 2012 (UTC) I was going to put this into our List of common misconceptions article, but it said there that the misconception must be sourced both regarding the subject matter AND the fact that it's a misconception (but how do you prove something is a misconception short of conduncting a survey? Intutively, however, it seems clear that a lot of people think this way about digitalization) Уга-уга12 (talk) 19:12, 26 July 2012 (UTC)

The theorem does not hold in general. See for instance Poisson summation formula, which says when you take a discrete sample, on the integers, in the frequency domain and take the inverse Fourier transform, you get the periodized sum of the original signal. The enabling assumption here is that the signal is bandlimited. Loosely speaking, when your signal is only non-zero on the frequencies, say [-π, π], its Fourier transform is like a function on the circle and therefore is determined by its Fourier coefficients, a discrete set. Mct mht (talk) 12:20, 27 August 2012 (UTC)

The theorem does hold in general. I think what you're saying is that sampling without bandlimiting doesn't give perfect reconstruction. And the theorem does not suggest that it would. Dicklyon (talk) 14:37, 27 August 2012 (UTC)

"In general" means no restrictions, as in given any signal in, say, L^1, perfect reconstruction, in some suitable sense, is possible by sampling a countable set of values. Sampling theorem (this one or any other one) or not, this is clearly too much to hope for, since in the L^1 case, even Fourier inversion doesn't apply in general. Mct mht (talk) 15:19, 27 August 2012 (UTC)

That sounds like splitting hairs. The theorem states the conditions under which it is valid, "If a function x(t) contains no frequencies higher than B hertz..." Maybe you can argue that these are not realistic conditions for real signals (see section below) but I think the article should make it clear that a bandlimited signal can be sampled and reconstructed without error. The misconception is that sampling produces an approximation of the signal. It is exact. The only caveat is that any energy above the nyquist frequency in the sampled signal is either lost (in the anti-aliasing filter) or causes aliasing distortion. --Kvng (talk) 17:08, 27 August 2012 (UTC)

No, in general means just that. E.g. the Hahn-Banach theorem holds for Banach spaces in general; the spectral theorem does not hold for bounded operators on Hilbert spaces in general, for there exists counter-examples. In this case, the theorem is violently wrong in general. Even for bandlimited signals which are very regular, sampling interval must be no bigger than the 1/2W. One can prove the following: given any δ > 1/2W, there exists a bandlimited function f of Schwartz class such that f(kδ) = 0 for any integer k. Thus no information whatsoever can be recovered. Mct mht (talk) 23:55, 1 September 2012 (UTC)

It seems like you've moved on to a different issue. The article discusses the problem of reconstructing signals exactly at Nyquist. Safer to say "Contains no frequencies higher or equal to B hertz..." Can we talk about reconstruction here in a way readers would understand? We can't use "the Hahn-Banach theorem holds for Banach spaces in general; the spectral theorem does not hold for bounded operators on Hilbert spaces in general" in the article. --Kvng (talk) 14:16, 4 September 2012 (UTC)

No, exactly the same issue, read what I said please. I was explaining to you what "in general" means, naming as examples two theorems---one holds in general, the other doesn't. They are not (immediately) relevant to the sampling theorem. As for reconstruction, I just gave you a scenario above where no reconstruction of any kind is possible. Mct mht (talk) 01:04, 8 September 2012 (UTC)

Can we talk about reconstruction here in a way readers would understand? The fact is, Kvng, that this article had, at one time, a far simpler and more elucidating mathematical treatment of sampling and reconstruction that closely matched what nearly any rigorous DSP or communications text would have. This article is a prime example of how some, many, articles in Wikipedia get worse, not better as time proceeds. Another example, not coincidentally, is the related article Poisson summation formula. Sometimes people try to hold the line on it but a couple of editors have took ownership of the article and the rest of us have given up trying to keep the article useful and informative. Best I can suggest is to buy a good textbook or check one out in an engineering library at some university, if you have access to such. 70.109.181.175 (talk) 18:07, 4 September 2012 (UTC)

I haven't given up on this article. Can you provide a pointer to a past version that you believe was better than the current version? --Kvng (talk) 19:20, 4 September 2012 (UTC)

This is the last version with a decent derivation of the sampling and reconstruction and this version of PSF is the last with a derivation . The current versions of both are abysmal and proof that Wikipedia articles do not always "advance" in quality with time. 71.169.179.221 (talk) 02:01, 11 September 2012 (UTC)

Poisson summation formula is an interdisciplinary topic. An engineer's pov on the formula is not the same as a number theorist. That article right now is pretty basic and can go both ways. Mct mht (talk) 01:04, 8 September 2012 (UTC)

There certainly are hairs to be split here. Where Nyquist (or whoever) said "If a function x(t) contains no frequencies higher than B hertz, it is completely determined by giving its ordinates at a series of points spaced 1/(2B) seconds apart", they must have known that the "series of points" would have to be infinite, and that there would be problems in the general case of unbounded total energy, even if the max is limited, due to the failure of the sinc function to be uniformly summable, or whatever you call it. But if we're going to split those hairs in the article, it should be by reference to a good source that does so. I think we'd be on safer ground with a theorem that states that reconstruction is possible to within any positive error epsilon, or something like that. Dicklyon (talk) 06:36, 2 September 2012 (UTC)

Timelimiting, bandlimiting

Statements about timelimiting in the lead here and in Aliasing and probably other places on WP are potentially misleading as they make it sound like sampling theorem can't be applied to real signals because of an infinite time requirement.

What the theorem really says is that only bandlimited signals can be accurately reconstructed, full stop. The timelimiting issue is really about the nature of bandlimited signals, not about a requirement for infinite sampling. If you timelimit a bandlimited signal, it is no longer a bandlimited signal. e.g., A timelimited sinusoid is a a pulse-modulated sinusoid and will have out-of-band components from the pulse and from the modulation process. Or, looking at it from the other direction, if you want to do perfect bandlimiting of a signal, you need to be able to process that signal over infinite time.

I believe the statements implying a requirement for an infinite number of samples should be reworded as a reminder that, for real signals, perfect bandlimiting is impractical and with imperfect bandlimiting, sampling theorem warns you'll get aliasing. --Kvng (talk) 19:51, 26 August 2012 (UTC)