Sampling Frequency Math

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?

• 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. May 26 '13 at 15:14
• My question is a little weak, I will reformulate it to make it clearer. May 26 '13 at 22:04
• Some signals can be recovered from below the sampling frequency. This is the basis of compressed sensing. May 27 '13 at 10:03
• @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. May 27 '13 at 16:32
• @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 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$.

• Incorrect. Signal has to be bandlimited to below Fs/2 for reconstruction. May 26 '13 at 20:10
• 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. May 26 '13 at 20:48
• 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. Jun 14 '13 at 20:20