What is Developer Zone?

Document Type: Prentice Hall
Author: Shie Qian and Dapang Chen
Book: Joint Time-Frequency Analysis -- Methods and Applications
ISBN: 0-13-254384-2
NI Supported: No
Publish Date: Dec 30, 2011

Yes No

Discrete Gabor Expansion

4 ratings | 3.00 out of 5
Print | PDF

Overview

In the preceding section, we introduced the periodic discrete Gabor expansion that requires the signal, analysis function, and synthesis function to have the same length. This is inconvenient (even impractical) in many applications, particularly when the number of samples L is large. For L-point samples, (3.31) essentially implies an L-by-L linear system. Therefore, it is desirable that lengths of analysis and synthesis function are independent of the length of samples so that we can use short windows to process arbitrarily long data. When this is achieved, the discrete Gabor expansion can then be used in many more signal process applications where typical signals are long.

Fig. 3-9 Due to zero padding, the Gabor transform can be computed without rolling over either signal s[k] or analysis function g[k]. The auxiliary periodic sequences actually release the periodic constraint.

Assume the length of the signal s[k] is Ls and the lengths of Gabor elementary function h[k] and dual function g[k] are L. Let's build auxiliary periodic sequences as

where all have the same period L0 = Ls+L-DM. The periodic discrete Gabor transform can then be plotted as Fig. 3—9.

Because of zero padding, we can compute the Gabor transform without rolling over either the signal s[k] or analysis function g[k]. The auxiliary periodic sequences defined in (3.33), (3.34), and (3.35) actually release the periodic constraint. Substituting auxiliary periodic sequences into the form of the periodic discrete Gabor expansion (3.23) and (3.24) yield

and

where

The oversampling rate is a = N/DM. For the perfect reconstruction, the time sampling step DM has to be less or equal to the number of frequency channels N. The total number of time sampling points is the smallest integer that is larger than or equal to L0/DM. Because of zero padding, the oversampling rate is equal to the ratio between the number of the Gabor coefficients and the number of zero padded samples s[k].

With L remaining finite, letting Ls —> ¥ and thereby L0 —> ¥, (3.36) and (3.37) directly lead to the Gabor expansion pair for discrete-time infinite sequence, i.e.,

and

The remaining question is how to compute the dual function g[k]. Substituting (3.34), and (3.35) into (3.29) and writing the resulting formula in the form of matrices, then we have

where g0 is an L0-by-1 vector and

H is a DML0/N-by-L0 matrix that can be written as

where Hi are DM-by-N block matrices whose entries hp,k(i) are

Because DNN = L, hp,k(i) = 0 for i = (p+l) ³ DN. That is, Hi = 0 for i ³ DN. In order to have dual functions g[k] and h[k] have the same time support, we force the last Ls-DM elements of the vector g0 to be zero, that is,

g is an L-dimensional vector. Replacing g0 in (3.41) by (3.45), (3.41) reduces to

The matrix can be remembered by an auxiliary periodic sequence given by

Then, the entries of H can be defined in the same manner as in the case of the periodic discrete Gabor expansion (3.32), i.e.,

Consequently, (3.46) can be written as

where 0 £ p < DM and 0 £ q < 2(DN-1). The significance of Eq. (3.49) is that it is independent of the signal length. It guarantees that the dual functions, h[k] and g[k], have the same time support.

H in (3.46) is a K-by-L matrix, where

where a denotes the oversampling rate. Therefore, (3.46) is an underdetermined system when

that is, a is larger than 2L/(L+DM).

It is interesting to note that the periodic discrete Gabor expansion and discrete Gabor expansion have a similar formula of computing the dual functions (see (3.31) and (3.46)) except for the structures of functions H. In the case of the periodic Gabor expansion, H is made up of the periodic window function h[k] directly. For the discrete Gabor expansion, H is constituted by the periodic auxiliary function h[k] which is the zero padded window function h[k].

Finally, g[k] derived for the discrete Gabor expansion is a subset of g0 in (3.45), which is a special solution of the periodic discrete Gabor expansion introduced in Section 3.3. Because we force the last Ls-DM elements of the vector g0 to be zero, the existence of g[k] is much more restricted than that in periodic cases, in particular, for the critical sampling DM = N. Because the critical sampling does not introduce any redundancy, it plays an important role in many signal processing applications, such as the maximally decimated linear systems. Then, the important issue is the existence of the critically sampled discrete Gabor expansion. In what follows, we only give the results without derivations. The reader can find the rigorous mathematical treatment in Appendix A.

For clarity of presentation, let's define the operation Ä by

If a set of numbers [e0, e1, e2, ...,em ] satisfies the condition

then we call this set of numbers exclusively non-zero.

Now, we state that for critical sampling, the biorthogonal function g[k] of the discrete Gabor expansion exists if

where 0 £ k < N and DNN = L. If h[k] satisfies Eq. (3.54), then g[k] is uniquely determined by

where 0 £ m < DN and 0 £ k < N.

Fig. 3-10 The locations of h[mN+k] at the critical sampling, where 0 £ k < N and 0 £ m < DN.

Fig. 3-10 depicts the locations of h[mN+k]. Eq. (3.54) implies that h[mN+k] can only contain N non-zeros. Moreover, the non-zero point can only be one k for all different m. When 0 £ m < DN = 1, that is, N = L (the number of frequency channels is equal to the length of the function h[k]), then the necessary and sufficient condition of the existing of dual function is simply that

which is illustrated in Fig. 3—11. In fact, this is exactly the case of non-overlap windowed Fourier transform.

Fig. 3-11 Biorthogonal sequences at the critical sampling (AAf = N = L).

Fig. 3-12 plots h[k] and g[k] for DM = N = L/2 = 64. In this case, non-zero points are h[32] to h[63] and h[64] to h[64+31], which obviously satisfies the conditions described by (3.54) and (3.55).

Fig. 3-12 Biorthogonal sequences at the critical sampling (DM = N = L/2).
4 ratings | 3.00 out of 5
Print | PDF

Legal
Copyright Prentice Hall Inc., A Pearson Education Company, Upper Saddle River, New Jersey 07458.
This material is protected under the copyright laws of the U.S. and other countries and any uses not in conformity with the copyright laws are prohibited, including but not limited to reproduction, DOWNLOADING, duplication, adaptation and transmission or broadcast by any media, devices or processes.