5
$\begingroup$

For a continuous signal (function), we have Bernstein inequality : $$ |{df(t)}/dt| \le 2AB\pi $$ where $A=\sup|f(t)|$ and $B$ is the bandwidth of $f(t)$. The question is: is there a relationship for a discrete function $x[n]$ like this? $$ |x[n] -x[n-1] | \le\ \mu\ W $$ where $$ X[k] = \sum\limits_{n = 0}^{N - 1} {x[n]{e^{ - j\frac{{2\pi }}{N}nk}}} $$ is the DFT for $x[n]$, $X[k]=0$ for $k> W$.

$\endgroup$
5
  • 1
    $\begingroup$ How do you define the bandwidth of $x[n]$? $\endgroup$
    – AlexTP
    Commented Oct 29, 2018 at 18:17
  • 1
    $\begingroup$ I'm sitting – tired – in front of a paper; my understanding of the Bernstein ineq is: $$P(\omega)=\sum_{n=0}^N\left(a_k\cos(n \omega)+b_k\sin(n\omega)\right)$$ $$\max_{-\pi\le\omega < \pi} \left\lvert P'(\omega)\right\rvert\le \max_{-\pi\le\omega < \pi} \left\lvert P(\omega)\right\rvert $$ From that follows that continuous bandwidth would be $2N\omega$; assuming Nyquist-limiting $W < 2N\omega$. $\endgroup$ Commented Oct 29, 2018 at 18:35
  • $\begingroup$ @OlliNiemitalo edited $\endgroup$
    – dt128
    Commented Oct 30, 2018 at 8:06
  • 3
    $\begingroup$ If $A=\max |x[n]|$, then we simply have $|x[n]-x[n-1]|\le 2A$. So any formula involving the bandwidth should be tighter than that, if it's any good. $\endgroup$
    – Matt L.
    Commented Oct 30, 2018 at 13:41
  • $\begingroup$ An alternative and not equivalent way to define $A$ is that it is the supremum of the absolute value of the band-limited continuous-time function the samples of which are $x[n].$ $\endgroup$ Commented Oct 30, 2018 at 14:02

1 Answer 1

3
$\begingroup$

As shown in the answers to this question, for continuous-time signals, the bound predicted by Bernstein's inequality is achieved with equality by a sinusoidal signal with a frequency equal to the upper frequency limit.

In analogy to this, in this answer I'll show a bound on $\big|x[n]-x[n-1]\big|$ for a discrete-time sinusoidal signal $x[n]$ at angular frequency $W$:

$$x[n]=A\sin(nW+\phi)\tag{1}$$

For the signal $x[n]$ given by $(1)$, the largest value of $\big|x[n]-x[n-1]\big|$ for all $n\in\mathbb{Z}$ occurs for two values $x[k]$ and $x[k-1]$ symmetrical to the point of the largest derivative of a (continuous) sinusoid, i.e., for $x[k]=A\sin(W/2)$ and $x[k-1]=A\sin(-W/2)$. Consequently, the bound for a sinusoid with frequency $W$ is given by

$$\big|x[n]-x[n-1]\big|\le 2A\sin\left(\frac{W}{2}\right)\tag{2}$$

This bound is achieved with equality for the signals

$$x[n]=A\sin\left(nW+\frac{(2l+1)W}{2}\right),\qquad l\in\mathbb{Z}\tag{3}$$

Note that the constant $A$ does not generally equal the maximum amplitude $B=\max |x[n]|$ of $x[n]$. Depending on the sampling phase, the maximum amplitude $B$ lies in the following interval:

$$A\cos\left(\frac{W}{2}\right)\le B\le A\tag{4}$$

Consequently, we have

$$A\le\frac{B}{\cos\left(\frac{W}{2}\right)},\qquad 0<W<\pi\tag{5}$$

Combining $(2)$ and $(5)$ we get

$$\big|x[n]-x[n-1]\big|\le 2B\tan\left(\frac{W}{2}\right),\qquad B=\max_n\big|x[n]\big|\tag{6}$$

Note, however, that $(6)$ is only useful for $\tan(W/2)<1$, i.e., for $W<\pi/2$ because for any $x[n]$ with $\max|x[n]|=B$ we must have

$$\big|x[n]-x[n-1]\big|\le 2B\tag{7}$$

I believe that the bound $(6)$ holds for all discrete-time band-limited signals with a maximum frequency $W$ (i.e., with $X(e^{j\omega})=0$ for $|\omega|\in (W,\pi]$), but I don't know how to show it.

$\endgroup$
7
  • $\begingroup$ Hi! What do you mean by discrete-time band-limited signals ? Are there non band-limited discrete-time signals as well ? $\endgroup$
    – Fat32
    Commented Oct 31, 2018 at 10:21
  • 1
    $\begingroup$ Consider $x[n] = \frac{2}{\sqrt{2}}\sin\left(\frac{\pi n}{2}+\frac{\pi}{4}\right) = [1, 1, -1, -1, 1, 1, -1, -1, \ldots].$ Eq. 2 gives $\left|x[n] - x[n-1]\right| \le \sqrt{2}A, $ which is correct if $A = \frac{2}{\sqrt{2}}$ (see my comment to the question) but incorrect if $A = \max|x[n]| = 1.$ $\endgroup$ Commented Oct 31, 2018 at 11:33
  • $\begingroup$ @OlliNiemitalo: Yes, I need to clarify the definition of $A$. $\endgroup$
    – Matt L.
    Commented Oct 31, 2018 at 11:46
  • 1
    $\begingroup$ @OlliNiemitalo: Fixed, kind of ... $\endgroup$
    – Matt L.
    Commented Oct 31, 2018 at 15:51
  • 2
    $\begingroup$ That can be a useful result. It may well be a tight bound in cases that band limit $W = \frac{\pi}{N},$ where $N$ is an integer, because then each extrema of a sinusoid of frequency $W$ can be located just between the samples. With other band limit values, things may get complicated and the "worst case" sinusoid may have a frequency lower than the band limit, or perhaps the worst case is not a sinusoid at all. $\endgroup$ Commented Oct 31, 2018 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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