8
$\begingroup$

According to the Nyquist–Shannon sampling theorem, any continuous time signal with a bandwidth $B$ smaller than Nyquist frequency $f_N=f_s/2$ (with $f_s$ the sampling frequency), which is sampled at sampling frequency $f_s$ can be perfectly reconstructed by sinc interpolation (i.e. the Whittaker–Shannon interpolation formula).

Assume we sample an unknown, bounded in magnitude, continuous time signal with constant sampling time $T=1/f_s$ at sample instances $kT$, ($k\in\mathbb{Z}$), without sampling jitter or quantization. We add the constraint that $B=\alpha f_N$, with $0\leq\alpha\leq 1$.

What I would like to figure out is the following: At sample instant $k$, I want to determine for each $\alpha$ a worst case fractional 'overshoot' of any continuous time signal between samples $k-1$ and $k$, that I could have had. I.e. how much the continuous time signal was higher than the highest (absolute) sampled values at sample instants $k$ and $k-1$. The continuous signal, or reconstruction (since the sinc interpolation is perfect!!), that we have 'missed' by sampling.

Example: We set $\alpha=1$ and assume discrete time signal [1,0,1,0,1,1,0,1,0,1] (notice the double 1 near the middle, and does this signal even have $\alpha=1$?). Its sinc reconstruction (blue line) from the samples (black impulses) looks as follows (I have plotted the sincs belonging to each sample in gray): Sinc Reconstruction for sequence The 'overshoot' between samples $k=0$ and $k=1$, is $\approx 0.7$ or $70\%$. So we missed a peak of value 1.7 in our original band-limited continuous time, or the 'perfectly band limited reconstructed', signal. If I would have put 3 or more consecutive 1's the overshoot would have been less (the Gibbs phenomenon is in the end much smaller). Therefore, 2 consecutive continuous samples like this is 'worst case'.

Extending the signal in both directions will make the overshoot grow: enter image description here Which shows relative overshoot of $\approx 1.1$ to a value of almost 2.1.

For any sequence length $2m$, this 'overshoot' $o(m)$ will grow indefinitely, $o(m)\propto\ln{(m)}$, which goes to $\infty$ when $m\to\infty$. This is because each sample the sincs will create constructive 'interference', and the sum of $1/\pi n$ (the contributions of all the envelopes of unit sinc's) for $n\to\infty$ does not converge.

This (I think) simlar to the following: if constantly sampling a value 0, I could also reconstruct a continuous time signal with infinite amplitude that is only sampled in the nodes at values of 0, e.g. $\sin{\pi f_s t}$. This tells me the same thing: that if I allow a signal to be at the Nyquist frequency the worst overshoot I could 'miss' is infinite.

We can now state that $o(m\to\infty)|_{\alpha=1}=\infty$. And we can reason that that $o(m\to\infty)|_{\alpha=0}=0$ (sampling a constant signal of which you know that it is band limited has a unique constant reconstruction).

What if $\alpha<1$?

If we now assume we do this same sinc interpolation, but know for sure $\alpha<1$, like $\alpha=0.5$. Then, (my gut feeling says) this effect should go down and should even remain finite (when $m\to \infty$)!. Since for any signal brick-wall limited to bandwidth $\alpha f_s/2$, we get a filter impulse response of $h(t)\propto \text{sinc}{\left(\frac{t-kT}{\alpha T}\right)}$ (right?). Therefore, signal transitions cannot be as fast as for the changing impulse train example above, and therefore contributions of each sinc function during reconstruction cannot create infinite constructive interference.

My problem: I don't know how to proceed from here; how to form a 'proof' of the worst case overshoot I could ever have find between 2 consecutive samples, knowing that $\alpha<1$, for $any$ signal (not necessarily these unit impulse-train like examples). A given value for $\alpha$ gives me a slope $\frac{dh(t)}{dt}$ of the band-limiting convolution kernel $h(t)$, which should tell me something about how much consecutive samples need to be different, but I do not see the steps to take from there to reach any generic conclusion.

$\endgroup$
  • $\begingroup$ We discussed such pathological sequences at comp.dsp in 2002, subject: A Sampled Data Interpolation Poser, groups.google.com/d/msg/comp.dsp/EQ31d-2SS2o/wT5HXbjQpogJ and 2003, subject: Worst Case Signal for Reconstruction, groups.google.com/d/msg/comp.dsp/xwb9p3awrOg/zl20Wl2EiesJ $\endgroup$ – Olli Niemitalo Oct 2 '16 at 11:40
  • $\begingroup$ I think there is a theorem that relates the bandwidth of a function to an upper limit of its average density of zero crossings. Now, for an almost everywhere infinite function those finite-valued samples are perhaps much like zero crossings are to a finite-valued function: their average density has an upper limit. $\endgroup$ – Olli Niemitalo Oct 2 '16 at 19:01
  • $\begingroup$ Thanks, I will read both Google group discussions in detail when I have some more time (where did your answer with the figure go?). Still, MBaz's answer seems to suggest that a worst case maximum absolute derivative exists, which, if $\sup{|x|}$ is finite, will be finite. Hence for any band limited signal, it cannot go to infinite value. How does that relate to what you are suggesting? $\endgroup$ – Retinite Oct 2 '16 at 19:15
  • $\begingroup$ I removed my answer because I did not take into account that the discrete sequence must be such that it survives lowpass filtering intact. So you may well be right about what happens at $\alpha < 1$, and my comment above would agree with that. $\textrm{sup}|x|$ might be found between samples so it doesn't say much. $\endgroup$ – Olli Niemitalo Oct 2 '16 at 19:38
  • $\begingroup$ I wonder if the math would be simpler for infinite-length periodic sequences with the period $\rightarrow\infty$ $\endgroup$ – Olli Niemitalo Oct 5 '16 at 6:01
8
$\begingroup$

I don't have a real answer but I have the feeling that this result will help you out: Bernstein's inequality says that, if the signal $x(t)$ is bandlimited to $|f|\leq B$, then $$\left| \frac{\textrm{d}x(t)}{\textrm{d}t}\right|\leq 4\pi B \,\textrm{sup}_{\tau\in\mathbb{R}}|x(\tau)| ,\,\,t\in\mathbb{R}$$ where $\textrm{sup}$ stands for "least upper bound".

I found about this inequality in Amos Lapidoth excellent (and free in PDF format) book "A Foundation in Digital Communication". A proof can be found in M. A. Pinsky, "Introduction to Fourier Analysis and Wavelets".

$\endgroup$
  • $\begingroup$ Thanks! That is really useful; reasoning from the continuous time signal. This should mean that when linearly extrapolating 'forward' at sample $k-1$ and 'backward' at sample $k$, we would get a triangle for which we know that the continuous time signal has to be below that triangle. If it wouldn't be, it would contain higher frequency content. Couldn't we then say that the max $|dx(t)/dt|$ is actually bounded by the highest frequency ($\alpha f_N$) (co)sine at maximum amplitude that I allow? (I will have to read the proof in Pinsky if I can find it to see how it relates) $\endgroup$ – Retinite Oct 2 '16 at 8:36
  • $\begingroup$ I cannot find a proof yet that I do understand, and don't want to spend over 100 USD for Pinksy's book just to get 1 proof. My gut feeling says we could be certain that $|\frac{dx(t)}{dt}|\leq 2\pi B A_{max}$ instead of ($2\pi$ vs $4\pi$), with $A_{max}$ the maximum allowed signal value. I found some general proof here but I don't understand the use of the $L_1$ norm with $||g ||_1$, and am not sure if the answer implies that $g(\xi)$ would be a $\text{rect}$ function (approximation) in the frequency domain. $\endgroup$ – Retinite Oct 3 '16 at 10:20
  • 1
    $\begingroup$ Never mind, by just filling in the explanation in the aforementioned post I constructed the proof. $\endgroup$ – Retinite Oct 3 '16 at 11:10
5
$\begingroup$

Observations

I have used +1 and -1 in the sequence instead of your 1 and 0. With $\alpha=1$, the band-limited continuous function $f_m(T)$ in your first two figures (with the above mentioned modification) is:

$$f_m(T) = \sum_{k=1-m}^m \operatorname{sign}\left(\operatorname{sinc}(\pi k - \pi/2)\right)\operatorname{sinc}(\pi T-\pi k),\tag{1}$$

where:

$$\operatorname{sinc}(T) = \begin{cases}\sin(T)/T&\text{if }T \ne 0\\1&\text{if }T = 0\end{cases}\\ \operatorname{sign}(x) = \begin{cases}-1&\text{if }x < 0\\0&\text{if }x = 0\\1&\text{if }x>0.\end{cases}$$

$f_m(1/2)$ grows linearly to the logarithm of $m$:

Growth of peak as function of $m$
Figure 1. $f_m(1/2)$ plotted as function of $\log_2(m)$ The logarithmic horizontal axis linearizes the growth as $m\rightarrow\infty$.

We can simplify $f_m(1/2)$ with help from Wolfram Alpha:

$$f_m(1/2) = 2\sum_{k=1}^m\left|\frac{\sin\left(\pi(k - 0.5)\right)}{\pi(k - 0.5)}\right| = \begin{cases} 4/\pi & \text{if }n = 1\\ -\frac{2\left(\psi^{(0)}(1/2)-\psi^{(0)}(m+1/2)\right)}{\pi} & \text{otherwise}, \end{cases}\tag{2}$$

where $\psi^{(0)}$ is the digamma function. The dominant term of the series of $(2)$ about $m=\infty$ is:

$$\frac{2\log(m)}{\pi},$$

which explains the linearization seen in Fig. 1. We can now construct a normalized version $g_m(T)$ of the function $f_m(T)$ that inherits its bandlimitedness but does not blow up as $m\rightarrow\infty$:

$$g_m(T) = \frac{\pi f_m(T)}{2\log(m)}$$

As $m\rightarrow\infty$, $g_m(T)$ seems to approach a Nyquist frequency sinusoid sampled at its zeros:

$g_{100000}(T)$
Figure 2. $g_{100000}(T)$ does not blow up.

The original Nyquist–Shannon sampling theorem requires that the highest frequency is below half the sampling frequency, so we seem to have a borderline case that is not covered by it. Arbitrarily large finite $m$ and consequently arbitrarily large finite $f_m(1/2)$ are still covered though.

Proof outline

Here is an outline for a proof of your original statement: Let the sampling period be 1. Let $f_\infty(T)$ be bandlimited to below frequency $\alpha\pi$, where $\pi$ represents a frequency with a period of 2 and $\alpha < 1$. Let $f_\infty(T)$ be finite for all integer $T$. Exclude the trivial case $f_\infty(T) = 0$ for all $T$. Let $g_\infty(T) = f_\infty(T)/\sup_Tf_\infty(T)$. It follows that $g_\infty(T) \ne 0$ for some $T$. Either:

Case 1. $g_\infty(T) \ne 0$ for some integer $T$. $\sup_Tf_\infty(T)$ is finite for all $T$.

Case 2. $g_\infty(T) = 0$ for all integer $T$. $\sup_Tf_\infty(T)$ is infinite for some $T$. Up to a scale factor, $g_\infty(T)$ is determined by a fraction $\alpha$ of its zeros. Use one more of the remaining zeros to make the function vanish: $g_\infty(T) = 0$ for all $T$. This is a contradiction, because earlier we determined that $g_\infty(T) \ne 0$ for some $T$. Case 2 cannot be true.

It follows that case 1 is true and $f_\infty(T)$ is finite for all $T$.

It would be nice to find a definite proof that a portion of the uniformly distributed zeros can be used to reconstruct the function given its relatively low bandwidth compared to the mean density of those zeros. I suppose if $\alpha < 1$, the sampling theorem suffices to make $g_\infty(T)$ vanish. In the literature, I've found some statements of interest:

The proof of part 2 of Theorem 4.1 showed that a band limited signal with $Ω = π$ with the property that the signal vanished at the points $x = n ∈ \mathbb{Z}$ must vanish identically.

Jeffrey Rauch, "Fourier Series, Integrals, and, Sampling From Basic Complex Analysis".

It is well known that $g$ can have no more zeros, roughly speaking, than cos $\lambda t$ without vanishing identically.

BF Logan, Jr. "Information in the Zero Crossings of Bandpass Signals", Bell System Technical Journal, vol. 56, pp. 487-510, April 1977

Most of the results on the unique specification of one-dimensional signals are based upon the fact that a bandlimited function is entire (analytic everywhere) and is thus uniquely specified by its zeros (real and complex) to within a constant and an exponential factor. An arbitrary bandlimited function is uniquely specified by its (real) zero crossings if all its zeros are guaranteed to be real.
...
Additional work has involved identifying signals which are uniquely specified by their (real) zero crossings despite the fact that they also contain complex zeros. This is possible if the zero crossing rate is in some sense higher than the information rate or bandwidth of a signal.

S. R. Curtis, "Reconstruction of multidimensional signals from zero crossings", thesis, MIT, 1985.

$\endgroup$
  • $\begingroup$ Interesting. The maximal derivative approach from the other post proves to give an extremely worst case estimation. I want to approach this problem again from my initial (and your) side. Basically we could say that the signal consists of two cosines (one running forward, the other backward) stitched together at samples 0 and 1. It seems to me that it should be 'rather easy' to redo your analysis for $\alpha=0.5$ and $0.25$ etc. to create a function or several estimations of this g(m) or f(1/2) that are also dependent on $\alpha$. $\endgroup$ – Retinite Oct 4 '16 at 9:19
  • $\begingroup$ @Retinite perhaps not that easy because one would first have to ensure that the samples really encode a function bandlimited as advertised. $\endgroup$ – Olli Niemitalo Oct 4 '16 at 11:00
  • $\begingroup$ Thanks for the proof! For $\alpha=0.5$ I came up with: $f_m(T)=\sum_{k=-1-m}^m{\text{sign}\left(\cos(k \pi\alpha-\frac{\pi}{4}(\text{sign}(k-\frac{1}{2})+1)))\right) \text{sinc}(k-T)}$. This gives sequence [...1 0 -1 0 1 1 0 -1 0 1 ...]. (is this actually BL to $\alpha=0.5$?!) This I could not get simplified (automagically) such that I could obtain a series expansion around $m\to\infty$. What I do get is a pretty obvious geometric series in $m$ for which I can check if the sum is finite (and it is) and what that value might be. But this is still a partial brute force method. $\endgroup$ – Retinite Oct 4 '16 at 20:32
  • $\begingroup$ You can test if the sequence represents a half-band bandlimited function. Compare "interpolation" given by the full-band sinc kernel and the half-band sinc kernel. If at some $T$ the two do not converge as $m\rightarrow\infty$, the answer is no. (Quotation marks because you can test at the sample points too.) $\endgroup$ – Olli Niemitalo Oct 4 '16 at 21:56
1
$\begingroup$

Consider the band-limited function $\operatorname{sinc}(t)$ with Fourier transform $\operatorname{rect}(f)$ which can be recovered perfectly (since interpolation!) from its samples spaced $1$ second apart even though the samples include only the central peak and miss all the other local maxima and minima of the sinc function. Delay the sinc function by $\frac 12$ second so that the sampler misses the central peak entirely but instead gets adjacent samples with identical values $$\operatorname{sinc}\left(\frac 12\right) = \frac{\sin\pi/2}{\pi/2} = \frac 2\pi.$$ The overshoot of the maximum is thus $1 - \frac 2\pi$. I don't have a proof but I suspect that this will turn out to be the maximum overshoot for the case $\alpha = 1$. Smaller values of $\alpha$ will give samples closer to the peak value of $1$ and the overshoot will be correspondingly smaller.

$\endgroup$

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.