The Time Limited Band Limited Theorem

We have seen that the behaviour of signals and their Fourier transforms at infinity can be a major concern. Indeed, in any practical digital computing scheme, signals and the Fourier transforms have to be of limited length. Normally then, any general statement that can be made about the length of Fourier transform pairs will have considerable bearing on digital signal processing, both in theory and in practice.

Our discussion addresses time-limited and band-limited signals. A time-limited signal is one that is confined to a finite length of time and is zero outside that interval. For a time-limited signal, its total energy is contained in an interval

2a:

A= \int_{-a}^{a} |f(t)|^{2}dt

Likewise, a band-limited signal has its spectrum completely confined to a finite frequency interval, so that its total energy is

B= \int_{-b}^{b}|F(\omega)|^{2}d\omega

The time-limited band-limited theorem says that no signal can be both time-limited and band-limited, except for the trivial case where f(t) is identically equal to zero. We prove this important theorem by assuming f(t) is both time-limited and band-limited; then, we show that f(t) necessarily must be the null function. First, observe that not only is this signal

f(t)=\int_{-b}^{b}F(\omega)e^{i\omega t }d\omega =0 for |t| \geq a

but all of its derivatives must also be zero at |t| \geq a. Therefore, differentiating wrt to time under the integral n times gives

\int_{-b}^{b}F(\omega)e^{i\omega a}(\omega)^{n}d\omega for n=0,1,2 \ldots

Next, we write the inverse Fourier transform of a band-limited signal in a special form. For such a signal, we can write

f(t)=\int_{-b}^{b}F(\omega)e^{i\omega t}d\omega=\int_{-b}^{b}F(\omega)e^{i\omega (t-a)}e^{i\omega a}d\omega

Then, using the power series expansion for the exponential function allows term by term integration to give

f(t)= \sum_{n=0}^{\infty} \frac {(i(t-a))^{n}}{n!}\int_{-b}^{b}F(\omega)e^{i\omega a }(\omega)^{n}d\omega

as an alternative representation of a band-limited signal in terms of its spectrum. But, we have shown that if the signal is also time limited, each of the integrals in this sum is identically zero. Hence, f(t)=0 is the only function that can be both time-limited and band-limited.

The theorem immediately raises a spectre of a fundamental nature for digital signal processing because it says that every signal must be infinitely long either in time domain or in the frequency domain, or both. We will see the consequences of this requirement later where we develop the relationship  between continuous signals and their sampled counterparts.

So far, our discussion of the continuous Fourier integral transform has been on a general level, giving powerful theorems and properties applicable to a wide variety of continuous functions. Next, to exemplify these theorems and also to form a basis for further discussion, we introduce a repertoire of Fourier transforms particularly important to digital signal processing.

To continue later…

Nalin Pithwa

 

The Wiener-Khintchine Theorem

An important method of treating such signals that do not decay at infinity, due independently to Wiener in 1930 and Khintchine in 1934, starts from the form of the convolution theorem given in the previous blog [equation 15 reproduced again:

FT \int_{-\infty}^{\infty} f(\tau)f(t+\tau)d\tau = |F(\omega)|^{2} ]

The inverse Fourier transform of this equation is

\int_{-\infty}^{\infty}f(\tau)f^{*}(t+\tau)d\tau=(1/2\pi)\int_{-\infty}^{\infty}|F(\omega)|^{2}e^{i\omega t}d\omega equation 16

For many signals of interest, such as sinusoids, step functions, and random noise of fixed statistical properties, the autocorrelation integral on the left does not converge. But, if we define a truncated version of f(t) by

f_{T}(t)= f(t) if -T<t<T and f_{T}(t)=0 otherwise

then we can write

\int_{-\infty}^{\infty}f_{T}(\tau)f_{T}(t+\tau)d\tau which equals

(1/2\pi)\int_{-\infty}^{\infty}|F_{T}(\omega)|^{2}e^{i\omega t} d\omega equation 17

where F_{T}(\omega) is the Fourier transform of f_{T}(t). Dividing by the time interval 2T and taking the limit, equation 17 becomes

\lim_{T \rightarrow \infty} (1/2\pi) \int_{-T}^{T}f(\tau)f(t+\tau)d\tau=(1/2\pi)\int_{-\infty}^{\infty}\lim_{T \rightarrow \infty} (|F_{T}(\omega)|^{2})(e^{i\omega t})/(2T)d\omega

Wiener (1949) was able to show that, under the condition that the limit on the left exists, the limit inside of the right hand integral converges to a function:

P(\omega)=\lim_{T \rightarrow \infty} (|F_{t}(\omega)|^{2})/(2T) equation 18

which we call the power spectrum density of f. Using these revised definitions of autocorrelation,

\phi (t)=\lim_{T \rightarrow \infty} (1/2T) \int_{-T}^{T} f(\tau)f(\tau +t)d\tau equation 19

and power spectrum, our result now reads

P(\omega)=(1/2\pi)\int_{-\infty}^{\infty}P(\omega)e^{i \omega t}d\omega equation 20 

which is called the Wiener-Khintchine theorem, the autocorrelation is the inverse Fourier transform of  the power spectrum. This is a very significant result, not a simple restatement of our starting point, equation 16. In Equation 16, both f(t) and F(\omega) must be square integrable,  that is, they must contain finite energy over all time and frequency. In equation 20, f(t) must only be sufficiently well behaved so that

\lim_{T \rightarrow \infty} (1/2T)\int_{-\infty}^{\infty} |f(t)|^{2}dt < \infty

That is to say, f(t) is only required to have finite power (signal squared per unit time) to have a power spectrum, but f(t) must have a finite energy (that is, square integrable or, with additional restrictions, be only absolutely integrable0 to possess a Fourier transform. Two classes of functions of interest, periodic functions and some types of random noise, satisfy the first condition, but not the second.

We will exploit the Wiener-Khintchine theorem further when we discuss Power Spectral Estimation. Here, we have introduced it to show how Fourier integral theory can be generalized to include functions with infinite energy but finite power. Having presented this vignette of the theory of generalized Fourier integrals, we now feel free to abandon further convergence questions in our heuristic discussion of Fourier transform pairs.

More later…

Nalin Pithwa

 

The Continuous Fourier Integral Transform Part 2: Properties of the Fourier Integral Transform

Symmetry properties and a few simple theorems play a central role in our thinking about the DFT. These same properties carry over to  the Fourier integral  transform as the DFT sums go over into  Fourier integrals. Since these properties are generally quite easy to prove, (and, hopefully, you are already familiar with them), we will simply list them in this section. (The proofs are exercises for you :-))

The symmetry properties are, of course, crucial for understanding and manipulating Fourier transforms. They can be summarized by

\mathcal {F}f^{*}(t)=F^{*}(-\omega)  Equation 8a

and \mathcal{F}f(-t)=F(-\omega) Equation 8b

The applications of these basic symmetry properties leads to

\mathcal{F}f^{*}(-t)=F^{8}(\omega)

and for two cases of special interest we can show that

if f(t) is real, then F(\omega) is Hermitian, F^{*}(\omega)=F(\omega)

and if f(t) is imaginary, then F(\omega) is anti-Hermitian, F^{*}(-\omega)=-F(\omega)

The similarity theorem results from a simple change of variable in the Fourier integral

\mathcal{F}f(\omega)=(1/|a|)F((\omega)/a) Equation 9

and likewise for the familiar shift theorem

\mathcal{F}f(t-\tau)=e^{-i\tau \omega}F(\omega) Equation 10

The power theorem which states that

2\pi\int_{-\infty}^{\infty}f(t)g^{*}(t)dt=\int_{-\infty}^{\infty}F(\omega)G^{*}(\omega)d\omega Equation 11

can be specialized to Rayleigh’s theorem by setting g=f

2\pi\int_{-\infty}^{\infty}|f(t)|^{2}dt=\int_{-infty}^{\infty}|F(\omega)|^{2}d\omega Equation 12

In more mathematical works, Rayleigh’s theorem is sometimes called Plancherel’s theorem.

Of course, the important and powerful convolution theorem — meaning linear convolution — is valid in continuum theory  also:

\mathcal{F} \int_{-\infty}^{\infty}f(\tau)g(t-\tau)d\tau=F(\omega)G(\omega) Equation 13

The many variations of the convolution theorem arising from the symmetry properties of the Fourier transform apply as well. For example, the autocorrelation theorem is as follows:

\mathcal{F}\int_{-\infty}^{\infty}f(\tau)g(t+\tau)d\tau=F(\omega)G^{*}(\omega) Equation 14

The function FG^{*} is called the cross-power spectrum. When we set g=f, this equation states the important result that the Fourier transform of the autocorrelation of a function is its power spectrum:

\mathcal{F}\int_{-\infty}^{\infty}f(\tau)f(t+\tau)d\tau=|F(\omega)|^{2} Equation 15

The formal similarity between these continuous-theory properties and those of the DFT makes them easy to remember and to visualize. But, there are essential differences between the two. The DFT with its finite sum has no convergence questions. The Fourier integral transform, on the other hand, has demanded the attention of some of our greatest mathematicians to elucidate its convergence properties. As we know, the absolute integrable condition is only a start; it can be relaxed — quite easily at the heuristic level — to include the sine wave/\delta function pair. The sine wave’s ill behaviour is characteristic of a wide class of functions of  interest in DSP that do not  decay sufficiently fast at infinity for them to possess a Fourier Transform in the normal sense.

More later…

Nalin Pithwa