Is The Nyquist Rate Enough? PDF

Preview

Summary

The Third International Conference on Digital Telecommunications Is The Nyquist Rate Enough? Subhendu Das, CCSI, West Hills, California, [email protected] Nirode Mohanty, Fellow-IEEE, CCSI, West Hills, California, [email protected] Avtar Singh, San Jose State University, San Jose, Ca...

Description

The Third International Conference on Digital Telecommunications

Is The Nyquist Rate Enough? Subhendu Das, CCSI, West Hills, California, [email protected] Nirode Mohanty, Fellow-IEEE, CCSI, West Hills, California, [email protected] Avtar Singh, San Jose State University, San Jose, California, USA [email protected]

engineering systems use three to four times the Nyquist sample rate.

Abstract The Nyquist rate was derived using infinite time interval. But all our applications are based on finite time intervals. In digital communications we repeat our processes usually over the symbol time interval. The Nyquist rate will provide very few samples on this small interval. It will be very difficult to recover the symbol function from so few samples. In this paper we provide a mathematical proof that faster sample rate is meaningful, necessary, and it provides additional information about the function. We extend the sampling theorem for signals defined over finite time measurement interval. Our proofs use the very well known mathematical concept of infinite dimensionality of function space.

We highlight in many different ways the well known fact that any continuous function defined over any finite time interval has infinite dimension. We know that a continuous function, defined over finite time interval, can be represented by infinite number of Fourier series coefficients or Taylor series coefficients. Using the above facts and similar other results we establish that a continuous function carries infinite amount of information when expressed in terms of these parameters. We show with an example that over finite time intervals the Nyquist rate will produce very few samples. We prove that it is theoretically necessary to sample a function that is defined over finite time interval, infinite number of times, to extract all the information from the function.

1. Introduction

Our main goal is to translate the derivations of the sampling theorem [1] to finite time interval. We show that this can be achieved by increasing the sample rate to a high value. This higher sample rate over finite time will produce large number of samples. The infinite dimension property of functions over finite time assures that these samples will be meaningful and will carry information. Thus first we quickly bring out the well known results of this infinite dimensionality concept of function space. We use Hilbert space theory, Taylor series, and a new sampling theorem.

Digital Signal Processing (DSP) is very much dependent on the number of samples you have for the signal. We show that more samples you have better will be the recovery of the signal over finite time intervals. All practical systems use finite duration signals. Fixed DSP processes are repeated over and over again on signals of fixed and finite time durations. Those systems that use asynchronous real time multitasking operating systems also perform their DSP activities involving signals of finite durations. In most of today’s engineering systems these intervals are usually of the order of milliseconds or microseconds. They cannot be considered as infinite time intervals. We show that there is no need for that assumption also.

2. Infinite Dimensionality We will use the following basic notations and definitions in our paper. Consider the class of all real valued measurable functions in L2[a,b], defined over the finite time interval [a,b]. We assume that the following Lebesgue integral is bounded, i.e. b 2 ∫ | f ( t ) | dt < ∞ , f ∈ L [ a , b ] 2 a

The original sampling theorem assumes that the signals exist over infinite time intervals. This infinite time interval is not practical. Therefore we extend the sampling theorem for systems that use finite time intervals. The result of this extension justifies the common engineering practice – more samples you take more information you get. In practice most

978-0-7695-3188-5/08 $25.00 © 2008 IEEE DOI 10.1109/ICDT.2008.11

Then we define the L2 norm as

27

b 2  f =  ∫ f ( t ) dt   a

continuous function. The Hilbert space theory ensures the existence of N in (6) for a given . The existence of such a countably infinite number of orthonormal basis functions (4) proves that the function space is an infinite dimensional vector space. This dimensionality does not depend on the length of the interval [a,b]. Even for a very small interval, like symbol time, or an infinite interval, a function is always an infinite dimensional vector.

1/ 2

(1)

Which in turn can be used to define the metric d as d( f , g ) = f − g

b = ∫ a

f ( t ) − g( t )

2

 dt  

1/ 2

(2)

In addition we also define the inner product as b (3) f , g = ∫ f ( t ) g ( t )dt a Under the above conditions the function space, L2 [a,b], is a Hilbert space. One very important property of the Hilbert space [4, pp31-32], related to the communication theory, is that it contains a countable set of orthonormal basis functions. Let { ϕ n , n = 1.2...} be such a set of basis functions. Then the following is true: 0 if m ≠ n (4) ϕ m ,ϕ n = δ mn =  1 if m = n

It is not necessary to have orthonormal basis functions for demonstrating that the function space is infinite dimensional. The collection of all polynomial n functions { t , n = 1.2...} is linearly independent over the interval [a,b] and their number is also countable infinity. These polynomials can be used to represent any analytic function, i.e. a function that has all derivatives. Using Taylor’s series we can express such a f(t) at t as: ∞ f ( n )( c ) f (t ) = ∑ ( t − c )n (7) n ! n=0 around the neighborhood of any point c. Thus the above polynomial set is also a basis set for the function space. Therefore using the infinite Taylor series expression (7), we prove again that a function is an infinite dimensional vector over a finite interval. Here the information is defined by the derivative coefficients and the polynomial functions.

Also for any f ∈ L [ a , b ] we have the Fourier series 2 ∞ (5) f ( t ) = ∑ anϕ n ( t ), ∀t ∈ [ a , b ] n=1 The above expression (5) really means that for any given > 0 there exists an N such that K f ( t ) − ∑ anϕ n ( t ) < ε , ∀K > N (6) n=1

Let f(t) be a continuous function defined over L2[a,b]. Assume that we divide the finite time interval [a,b] into n ≥ 1 equal parts using equally spaced points { t , t ,...t n , t } . Where t = a and t = b . Use 1 2 n+1 1 n+1 the following notations to represent the t-subintervals ∆ ti = [ ti , t ), i = 1..n − 1, and i+1 ∆ t n = [ tn ,t ] n+1 Define the characteristic functions: Χ i ( t ) = 1 , when t ∈ ∆ ti

In this paper we will consider only continuous functions and their Riemann integrability. We note that the continuous functions are measurable functions and the Riemann integrable functions are also Lebesgue integrable. Thus the Hilbert space theory (16) and associated concepts will still remain applicable to our problems. We say that to represent a function accurately over any interval we need two sets of information: (A) An infinite set of basis functions, not necessarily orthogonal, like the ones given by (4) and (B) An infinite set of coefficients in the infinite series expression for the function, similar to (5). That is, these two sets completely define the information content in a mathematical function.

Χ i ( t ) = 0 , otherwise, for i=1..n. In this case the characteristic functions, Χ i ( t ) are orthogonal over the interval [a,b] with respect to the inner product on L2 [a,b]. Because X i ( t ) X j ( t ) = 0 , i ≠ j , ∀t ∈ [ a , b ] (8)

Equality (5) happens only for infinite number of terms. Otherwise, the Fourier representation in (6) is only approximate for any finite number of terms. In this paper in (6) will be called as the measure of approximation or accuracy estimate in representing the

Also define the simple functions n f n ( t ) = ∑ f ( ti )Χ i ( t ) ∀t ∈ [ a , b ] i=1

28

(9)

The expression (11) says that a function is an infinite dimensional vector and can be correctly represented by all the infinite samples, while the expression (10) can be used for approximate representation with accuracy given by . Essentially Theorem 1 proves that infinite sample rate is necessary to represent a continuous function correctly over a finite time interval. Theorem 1 is similar to the one described for measurable functions in [3, pp185187]. However the coefficients are not sampled values in that theorem. Another proof can be found in [6, pp247-257] where the Bernstein polynomial has been used instead of the characteristic function.

Here f ( ti ) is the sampled value of the function f(t) at t = ti . It is easy to visualize that fn(t) is a sequence of discrete step functions over n. Expression (9) is an approximate Fourier series representation of f(t) over [a,b]. This representation uses the samples of the function f(t) at equal intervals, fn(t) uses n number of samples. We show that this approximate representation (9) improves and approaches f(t) as we increase the value of n. Theorem 1: fn(t) → f(t) as n → ∞ over [a,b]. To prove the theorem, consider the error ∆ y n = max f ( t ) − f n ( t ) , ∀t ∈ [ a , b ] t It is clear that { ∆ yn } is a monotonically decreasing sequence of n. Therefore, given any ε > 0 we can

We now show that a band limited function is also infinite dimensional and therefore carries infinite amount of information. Consider a band limited function f(t), with bandwidth [-W,+W]. Then f(t) is given by the following inverse Fourier Transform [2]: 1 +∞ iwt f (t ) = ∫ F ( w )e dw 2π − ∞ (12) + 2 W π 1 iwt = ∫ F ( w )e dw 2π − 2πW In (12) t is defined for all time in (–∞,+∞). But the frequency w is defined only over [–W,+W], and it can take any value: integer, rational, or irrational frequencies, within that range.

find an N such that ∆ yn ≤ ε / ( b − a ) for all n > N. We can also verify that 1/ 2 2  b f − f n = ∫ f ( t ) − f n ( t ) dt a  2  b n n  = ∫ ∑ f ( t ) X ( t ) − ∑ f ( t ) X ( t ) dt  i i i a i = 1  i=1  

1/ 2

Now performing the squaring operation, noting that (8) holds, we get 1/ 2 b  n 2 2   = ∫ ∑ f ( t ) − f ( ti ) X ( t ) dt a i=1   i

[

]

b n  2 2 ≤ ∫  ∑ [∆y n ] X ( t ) dt a i=1   i

    n = ∆y 2 ∫ab  ∑ Χ 2 ( t ) dt    n   i = 1 i 

[

= ∆y 2 [ b − a ] n

The second line in expression (12) shows that the band limited function f(t) has uncountably infinite number of frequencies. Therefore f(t) is an infinite dimensional vector. This is true even when we consider a small interval of time for the function f(t). In that small interval the function still has all the infinite frequency components corresponding to the points in [–W,+W]. This is another way of showing that a band limited function is an infinite dimensional vector over a finite measurement window. It is clear though that the Theorem 1 does not depend on the bandwidth of the function f(t).

]

1/ 2

1/ 2

1/ 2

We point out here that a constant function f(t) = C, as an element of function space, is also an infinite dimensional vector. The only difference is that all sample values are same. In terms of Taylor series the coefficients for a constant function are {C,0,0,….}, which is an infinite dimensional vector.

= ( b − a )∆y ≤ ε n

Thus we can write:

n f ( t ) − ∑ f ( ti ) X i ( t ) ≤ ε , ∀t ∈ [ a , b ], ∀n ≥ N i =1

Which means: ∞ f ( t ) = ∑ f ( ti )Χ i ( t ) ∀t ∈ [ a , b ] i=1 This concludes the proof of Theorem 1.

(10)

This infinite dimensionality is not the same as dimensionality of the time-bandwidth product found in communication theory text [9]. We will explore this relationship in a subsequent paper.

(11)

29

which is defined using Fourier series or transform, which in turn uses sinusoidal functions.

3. Sampling Theorem Consider the sinusoidal function s( t ) = A sin ( 2 π f t + θ ) and assume that it is defined only for one period. We can see from the above expression that a sinusoidal function can be completely specified by three parameters A, f, and θ. That is we can express a sine function as a three dimensional vector: s = [ A, f ,θ ] (13) However (13) is very misleading. There is a major hidden assumption; that the parameters of (13) are related by the sine function. Therefore more precise representation of (13) should be: s = [ A, f ,θ , " sin e" ] (14) The word sine in (14) means the Taylor’s series, which has an infinite number of coefficients. Therefore when we say (13) we really mean (14) and that the sine function, as usual, is really an infinite dimensional vector.

Theorem 2 says that the sampling theorem should be stated as fs > 2fm instead of fs ≥ 2fm that is, the equality should be replaced by strict inequality. Here, fm is the signal bandwidth, and fs is the sampling frequency. There are some engineering books [7, p63] that mention strict inequality. Shannon states his sampling theorem [1, p448] in the following way: “If a function f(t) contains no frequencies higher than W cps, it is completely determined by giving its ordinates at a series of points spaced 1/2 W seconds apart.” The proof [1] is very simple and runs along the following lines. See also [2, p271]. A band limited function f(t) can be written as in (12). Substituting t = n/(2W) in (12) we get the following expression: n iw  n  1 + 2πW (16) f ∫ F ( w )e 2W dw =  2W  2π − 2πW Then the paper [1] makes the following comments: “On the left are the values of f(t) at the sampling points. The integral on the right will be recognized as essentially the nth coefficient in a Fourier-series expansion of the function F(w), taking the interval –W to +W as a fundamental period. This means that the values of the samples f(n/2W) determine the Fourier coefficients in the series expansion of F(W).” It then continues “Thus they determine F(w), since F(w) is zero for frequencies greater than W, and for lower frequencies F(w) is determined if its Fourier coefficients are determined.”

Similarly we can use the following three equations to solve for the three unknown parameters, A, f, and θ: s = A sin ( 2 π f t + θ ) 1 1 s = A sin ( 2 π f t + θ ) 2 2 s = A sin ( 2 π f t + θ ) 3 3 where t1 , t2 , t3 are sample times and s1 , s2 , s3 are corresponding sample values. Again a correct representation in terms of samples would be s = [( s , t ),( s , t ),( s , t ), " sin e" ] (15) 1 1 2 2 3 3 Hence with sinusoidal assumption, a sine function can be completely specified by three samples. The above analysis gives a simple proof of the sampling theorem. For band limited functions we can consider this sinusoid as the highest frequency sine wave in the signal. We can now state the well known result:

Thus the idea behind his proof is that from the samples of f(t) we reconstruct the unknown F(w) using (16). Then from this known F(w) we can find f(t) using (12) for all time t. One important feature of the above proof is that it requires that the function needs to exist for infinite time, because only then you get all infinite samples from (16). We show that his proof can be extended to define functions over any finite interval with any degree of accuracy by increasing the sample rate. The idea is similar, we construct F(w) from the samples of f(t).

Theorem 2: A sinusoidal function can be completely specified by three non-zero samples of the function taken at any three points in its period. From (15) we see that if we assume sinusoidality then more than three samples, or higher than Nyquist rate, will give redundant information. However without sinsoidality assumptions more sample we take more information we get, as is done in common engineering practice. It should be pointed out that Shannon’s sampling theorem assumes sinusoidality. Because it is derived using the concept of bandwidth,

We use the principles behind the numerical inversion of Laplace transform method as described in [5, p359]. Let F(w) be the unknown band limited Fourier transform, defined over [-W,+W]. Let the measurement window for the function f(t) be [0,T], where T is finite and not necessarily a large number. Divide the frequency interval 2W into K smaller equal

30

sub-intervals of width ∆w with equally spaced points {wj} and assume that {F(wj)} is constant but unknown over that i-th interval. Then we can express the integration in (12) approximately as: K itw j 1 f (t ) ≈ ( ∆w ) ∑ e F( w ) (17) j j =1 2π The right hand side of (17) is a linear equation in {F(wj)}, which is unknown. Now we can also divide the interval [0,T] into K equal parts with equally spaced points {tj} and let the corresponding known sample values be {f(tj)}. Then if we repeat the expression (17) for each sample point tj we get K simultaneous equations in the K unknown variables {F(wj)}. These equations are independent because exponential functions in (17) are independent. Therefore we can solve them for {F(wj)}. Theorem 1 ensures that the sets {F(wj)} and {f(tj)} can be selected to achieve any level of accuracy requirements in (17) for either f(t) or F(w).

an = f ( n / f s ) (19) Thus the function f(t) can be expressed as [8, p58]: n =∞ sin{π f s [t − ( n / f s )]} f ( t ) = ∑ f ( n / fs ) (20) n=−∞ π f s [t − ( n / f s )] Here fs ≥ 2W, where W is the bandwidth of the function f(t). The set {φn } in (18) is orthogonal only over (-∞,+∞).

We make the following observations about (20): 1. The representation (20) is exact only when infinite time interval and infinite terms are considered. 2. If we truncate to finite time interval then the functions φn in (18) will no longer be orthogonal, and therefore will not form a basis set, and consequently will not be able to represent the function f(t) correctly. 3. If in addition we consider only finite number of terms of the series in (20) then more errors will be created because we are not considering all the basis functions. We will only be considering a subspace of the entire function space.

For convenience we assume that the number of terms K in (17) is equal to Tkfs =2kWT. Here fs is the Nyquist sample rate and k > 1. We state the following new sampling theorem.

We prove again that, by increasing the sample rate we can get any desired approximation of f(t), over any finite time interval [0,T], using the same sinc functions of (18). From calculus we know that the following limit holds: sin x Lim =0 (21) x→∞ x Assume that fs is the Nyquist sampling frequency, i.e. fs = 2W. Let us sample the signal at k times the Nyquist rate. Here k>1 is any real number. Then using (21), we can show that given any T and a small > 0, there exists an N such that

Theorem 3: Let f(t) be a band limited function with bandwidth restricted to [-W,+W] and available over the finite measurement window [0,T]. Then given any accuracy estimate >0, there exists a constant k>1 such that 2kWT equally spaced samples of f(t) over [0,T] will completely specify the Fourier transform F(w) of f(t) with the given accuracy . This F(w) can then be used to find f(t) for all time t. In a sense Shannon’s sampling theorem gives a sufficient condition. That is, if we sample at twice the bandwidth rate and collect all the infinite number of samples then we can recover the function. We point out that this is not a necessary condition. That is, his theorem does not say that if T is finite then we cannot recover the function accurately by sampling it. We have confirmed this idea in the above proof of Theorem 3.

sin π k f t  s   < δ, π kf t s

∀k > N ,

∀t ≥ T

(22)

Thus these orthogonal functions (18) subs...