Tuesday, 13 September 2016

interpolation - Signal values we will 'miss' between sampling instances during sampling of band limited signals


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.



Answer



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".


No comments:

Post a Comment

readings - Appending 内 to a company name is read ない or うち?

For example, if I say マイクロソフト内のパートナーシップは強いです, is the 内 here read as うち or ない? Answer 「内」 in the form: 「Proper Noun + 内」 is always read 「ない...