The Nyquist formula for digitally sampling and recovering a continuous waveform is well known. Are there any mathematical formulas that show that it is computationally infeasible (or impossible) to reconstruct a waveform if you go below a certain sampling frequency?

  • 2
    $\begingroup$ You are misunderstanding the concept of the Nyquist sampling rate. The Nyquist sampling rate is the minimum sampling rate that is needed to reconstruct a signal of finite bandwidth from its samples. If $s(t)$ is a signal whose Fourier transform $S(f)$ is identically $0$ for $|f| > W$, then it can be reconstructed from its samples taken at rate $2W$ per second or more. If the sample rate is less than $2W$ samples per second, then the signal is not necessarily recoverable from its samples. $\endgroup$ – Dilip Sarwate May 26 '13 at 15:14
  • $\begingroup$ My question is a little weak, I will reformulate it to make it clearer. $\endgroup$ – William Hird May 26 '13 at 22:04
  • 1
    $\begingroup$ Some signals can be recovered from below the sampling frequency. This is the basis of compressed sensing. $\endgroup$ – geometrikal May 27 '13 at 10:03
  • $\begingroup$ @geometrikal: This is what I was looking for, the concept of compressed sensing. I was looking for a proof that below a certain sampling rate where even compressed sensing won't recover the signal. My original question was poor, I apologize, this is a new field for me. $\endgroup$ – William Hird May 27 '13 at 16:32
  • 1
    $\begingroup$ @WilliamHird The answer will strongly depend on what assumptions you are willing to make about your signal. Is it bandlimitted? Does it have a multiband structure? Is it sparse in a friendly basis? Etc. I'd recommend having a look at Unser's paper "Sampling: 50 Years After Shannon". Here's a link: bigwww.epfl.ch/publications/unser0001.pdf $\endgroup$ – lp251 May 27 '13 at 17:29

Sampling a continuous signal $x(t)$ can be modeled by multiplication with a delta pulse train:

$$x_s(t)=x(t)\cdot\sum_{n=-\infty}^{\infty}\delta(t-nT)= \sum_{n=-\infty}^{\infty}x(nT)\delta(t-nT)$$

where $T$ is the sampling interval: $T=1/f_s$ ($f_s$ is the sampling frequency). Multiplication in the time-domain corresponds to convolution in the frequency domain. So the spectrum of the sampled signal can be computed by convolving the transforms of $x(t)$ and of the pulse train:

$$x(t)\Longleftrightarrow X(f)\\ \sum_{n=-\infty}^{\infty}\delta(t-nT)\Longleftrightarrow \frac{1}{T}\sum_{k=-\infty}^{\infty}\delta(f-kf_s) $$

Convolution of these two Fourier transforms gives

$$x_s(t)\Longleftrightarrow X_s(f)= \frac{1}{T}\sum_{k=-\infty}^{\infty}X(f-kf_s)\tag{1}$$

Equation (1) shows that the spectrum of a sampled signal is composed of shifted versions of the original spectrum. The shift corresponds to multiples of the sampling frequency $f_s$. Consequently, if the spectrum $X(f)$ is exactly zero for frequencies greater than $f_s/2$, then the shifted versions do not overlap, and the original spectrum can be reconstructed by lowpass filtering the spectrum of the sampled signal. If $X(f)$ is not band-limited to $f_s/2$, i.e. it has frequency components greater than $f_s/2$, the shifted spectra in Equation (1) overlap, and the original signal can in general not be reconstructed from the sampled signal. This is what the sampling theorem states.

EDIT: For non-periodic signals - i.e. if $X(f)$ does not contain Dirac impulses - it is sufficient for reconstruction that $X(f)$ does not contain frequency components above $f_s/2$. In this case it is (theoretically) possible to reconstruct $x(t)$ from its samples $x(nT)$ by applying an ideal lowpass filter with cut-off frequency $f_s/2$. The impulse response of such an ideal lowpass filter is given by

$$h_{LP}(t)=\frac{\sin (\pi t/T)}{\pi t/T}$$

Filtering $x_s(t)$ with this impulse response yields the original signal

$$x(t)=\sum_{n=-\infty}^{\infty}x(nT)\frac{\sin [\pi (t-nT)/T]}{\pi (t-nT)/T}\tag{2}$$

Equation (2) is usually referred to as the Whittaker-Shannon interpolation formula.

Normally one does not need to consider what is actually happening at the frequency $f_s/2$. The only case where this is necessary is the presence of a pure sinusoid with frequency $f_s/2$. From Equation (1) we can see that in this case the shifted spectra (for $k=\pm 1$) will also produce spectral lines at $\pm f_s/2$, which in general will make impossible the reconstruction of the sinusoid at $f_s/2$. Apart from this somewhat artificial case, it suffices to require that the signal does not contain any frequency components greater than $f_s/2$.

The above considerations are of course of a purely theoretical nature, because there exist neither ideally band-limited signals nor ideal lowpass filters. Consequently, in practice we will choose the sampling frequency such that it is well above twice the maximum signal frequency of interest. The anti-aliasing filter must pass frequencies up to this maximum frequency, then it has a finite transition bandwidth, and then we can choose a frequency in the stopband of the filter where the stopband attenuation guarantees that aliasing errors are sufficiently small for the given application. This frequency can finally be considered the "bandwidth" $B$, and the sampling frequency can now be chosen as $f_s\ge 2B$.

  • 1
    $\begingroup$ Incorrect. Signal has to be bandlimited to below Fs/2 for reconstruction. $\endgroup$ – hotpaw2 May 26 '13 at 20:10
  • 1
    $\begingroup$ Talking about frequency-continuous spectra, there is no difference. The cut-off frequency simply is $f_s/2$. I'm not talking about the academic example of a sinusoid at exactly $f_s/2$. So I think "incorrect" is a rather strong statement here. The notion band-limited to "below" some frequency does not make sense for frequency-continuous spectra. $\endgroup$ – Matt L. May 26 '13 at 20:48
  • $\begingroup$ Thanks for the input guys, I found what I was looking for, it is the concept of compressed sensing as mentioned in the previous comments above. $\endgroup$ – William Hird Jun 14 '13 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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