Method and Apparatus for Time Varying Spectrum Analysis

A portion of the disclosure of this patent document contains material to which the claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction by any person of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office file or records, but reserves all other rights whatsoever.

1. Field of the Invention

The present invention relates to digital signal processing; and more particularly, to machines and methods for determining characteristics of signals having frequency components that vary in time.

2. Description of the Related Art

Typical systems for digital signal processing involve conversion of an input analog signal to a sequence of digital samples, supplying blocks of the digital samples in the sequence to a digital signal processing engine which performs array or block level computations on the digital signals, and analyzing the results of the computations. This field is rapidly expanding in the areas of speech processing, image recognition for radar and sonar, underwater acoustics, and other technologies.

The discrete Fourier transform DFT and fast Fourier transform FFT implementation of the DFT, are fundamental processing techniques in digital signal processing systems. These techniques suffer the limitation that they do not characterize signals being processed in terms of how frequency components vary in time very well.

Prior art systems for analyzing signals with frequency components that vary in time have used the so-called short time Fourier transform STFT. This algorithm is based on a computationally intensive Fourier transform of a large number of short windows of the input signal. Transforms of each of the short time windows are combined to generate a time varying spectrum of the input signal. However, time varying spectra generated using the STFT technique do not have very good resolution. Also, the STFT technique is computationally expensive.

The Gabor transform is another digital signal processing tool which generates a joint time-frequency representation of a signal. See, D. Gabor, "Theory of Communication", J.IEE (London), Vol. 93, No. III, November, 1946, pp. 429-457. Its applications, however, have been limited primarily due to the difficulty of selecting the biorthogonal auxiliary window function .gamma.. Recently, a framework for designing the auxiliary function .gamma. for the finite and cyclic discrete Gabor transform has been developed. See, Wexler, et al., "Discrete Gabor Expansions", Signal Processing, Vol. 21, No. 3, November, 1990, pp. 207-221. In many signal processing applications, however, the finite, cyclic Gabor transform is not adequate. The lack of a general solution for the infinite discrete Gabor transform has limited the usefulness of this digital processing technique, and it has not been applied successfully to creating time-varying energy spectra. See, Qian, et al., "Wigner Distribution Decomposition and Cross-Term Interference Cancellation", UMBC Technical Report No. EER-91-1, University of Maryland, January, 1991.

The present invention provides a signal analyzer for generating a time varying spectrum for input signals characterized by frequency components which change in time. The invention can also be characterized as a method for analyzing a signal based on the time varying spectrum.

Thus, according to a first aspect, the present invention comprises a signal analyzer which includes a converter generating a sequence of digital signals representative of an input signal. The sequence of digital signals is supplied to a first processor which computes orthogonal-like discrete Gabor transform coefficients C.sub.m,n in response to the sequence, and a time varying spectrum, termed herein the Gabor spectrum, of the input signal energy in response to the coefficients. Finally, a second processor processes the spectrum for further analysis or display. One particular analysis step for which the time varying spectrum is useful is in partitioning the input signal into separate components. The separate components may then be individually analyzed using any of a variety of techniques.

The first processor includes an input buffer which receives the incoming sequence of digital signals, and supplies those signals in a format appropriate for computation of the coefficients in response to a buffer controller. Similarly, the processor includes an output buffer, which stores a matrix of values representative of the time varying spectrum, in coordination with the processor engine.

The digital signal processor is programmed to compute the coefficients and the time varying spectrum either by a hardware implementation, or software control of a generic processor. The routine is based on the following steps:

acquiring a sequence of digital signals representative of the input signal;

sampling the sequence of digital signals to define a plurality of windows of length L, each window in the plurality including a plurality of digital signals and shifted by length AM digital signals relative to an adjacent window;

computing orthogonal-like discrete Gabor transform coefficients C.sub.m,n in sampling intervals .DELTA.N and .DELTA.M, for n=0 through N-1 for each window m, and for the plurality of windows m=0 through M-1, such that .DELTA.N.DELTA.M is less than L;

computing the time-varying spectrum of energy of the input signal in response to the coefficients C.sub.m,n ; and

analyzing the input signal in response to the time-varying spectrum.

The orthogonal-like discrete Gabor transform coefficients are computed using a non-periodic, localized discrete window function h, and a discrete auxiliary function .gamma., similar to h. The time varying spectrum is computed utilizing a cross-term deleted Wigner-Ville distribution.

According to yet another aspect of the present invention, the discrete window function h is a gaussian function having a variance .sigma..sup.2 less than or equal to about 0.5 (L/12).sup.2, where L is a window length used in the computations.

In yet another aspect of the invention, the spectrum is computed utilizing a look-up table of pre-computed factors used in an energy distribution function based on the coefficients. For each coefficient, an update region around the coefficient on the spectrum is determined in response to the magnitude of the coefficient. The energy distribution is then computed within the update regions for each coefficient. The lookup table of pre-computed factors is calculated having a size sufficient to cover the update region of the coefficient having the maximum magnitude. In this way, a look-up table of determinant size can be utilized with a given Gabor spectrum engine.

The signal analyzer and method according to the present invention are particularly useful for signals characterized by frequency components which change in time, such as encountered in speech processing, acoustic or electromagnetic communications, acoustic or electromagnetic surveillance, radar, sonar, and a variety of other signal processing environments. For instance, the ability to identify the beginning and ending in time of a signal having a certain frequency spectrum, among a complex group of signals, such as might be encountered when a specific person begins speaking in a room with other persons present, is greatly improved by the Gabor spectrum signal analyzer and method provided by the present invention.

Other aspects and advantages of the present invention can be seen upon review of the figures, the detailed description, and the claims which follow.

FIG. 1 is a schematic block diagram of a signal analyzer according to the present invention.

FIGS. 2A and 2B are a flow chart of the method for computing the Gabor spectrum according to the present invention.

FIG. 3 illustrates the construction of frames of digital signals used in the computation of the Gabor spectrum.

FIG. 4 is a heuristic diagram illustrating the sampling distribution used in the computation of the Gabor spectrum.

FIG. 5 is an example of an update region used for computation of the energy distribution for the Gabor spectrum according to the present invention.

FIG. 6 is a more detailed block diagram of a signal analyzer for generation of the Gabor spectrum according to the present invention.

FIGS. 7A and 7B are graphs of a frequency hopper signal and a noisy hopper signal, respectively, representative of an input signal having frequency components which vary in time.

FIGS. 8A and 8B are graphs of the Gabor spectrum generated in one application of the present invention from the input signals of FIGS. 7A and 7B, respectively.

FIG. 9 is a graph of the localized window function h and the discrete auxiliary function .gamma. used in one application of the signal analyzer of the present invention.

A detailed description of preferred implementations of the present invention is provided with respect to the figures.

In FIG. 1, a heuristic block diagram of a signal analyzer according to the present invention is provided. The analyzer, generally referred to by the reference number 10, includes an analog to digital converter 11, a digital signal processor 12, a control module 13 coupled to the digital signal processor, a Gabor spectrum analyzer 14, and a display system 15. An input s(t) is supplied from a transducer or other source on line 16. The analog to digital converter 11 generates a sequence of digital values s(i) representative of the input signal s(t). A sequence s(i) is supplied to the digital signal processor 12. The digital signal processor may be implemented using a general purpose computer programmed to perform the DSP functions, or a special DSP engine adapted for this purpose. The digital signal processor 12 performs a discrete Gabor transformation DGT to compute the Gabor coefficients for the input signal s(i), and computes an energy distribution in time and frequency based on a cross-term deleted Wigner-Ville distribution PWDV in response to the coefficients. The energy distribution GS(i,k) is supplied at the output of the digital signal processor 12 on line 17. The energy distribution GS(i,k) is analyzed in a Gabor spectrum analyzer 14 to generate a graphic representation of the energy distribution for supply to the display 15. Also, the Gabor spectrum analyzer 14 may perform other analysis functions, such as partitioning the input signal into components in time for use in speech processing, communications, image recognition, or other purposes. The spectrum analyzer 14 may be a programmed general purpose computer, or a specialized system designed for this purpose. The analyzer 14 may be implemented on the same processor as the digital signal processor 12.

The control block 13, in one preferred embodiment, comprises a computer program, such as provided in Appendix A.

The program shown in Appendix A is one example of a source code routine written for LABVIEW (trademark of National Instruments, Inc.) instrumentation software system. Obviously a wide variety of other source code implementations could be utilized.

Appendix A consists of three routines including GaborSpectrum.c, GaborMagnitude.c, and autoWV.c. The GaborSpectrum.c sets up the data for the computation of the Gabor coefficients. The user is able to initialize the routine by selecting parameters such as the oversampling rate, the variance, and the window length for computing the spectrum. More details concerning these parameters is described below. The GaborSpectrum.c routine calls the GaborMagnitude.c routine which calculates the complex Gabor coefficients and supplies as outputs the magnitude of the coefficients for use in computing the Gabor spectrum. The routine autoWV.c calculates the energy distribution in response to the coefficients and supplies the Gabor spectrum output.

Basically, the Gabor spectrum algorithm consists of the following steps 1-8.

Select a window length L. In one implementation, the value L is always a power of two. For instance, L=64, 128, 256, 512, . . . , etc. After L is determined, the frequency resolution is also determined by ##EQU1## where fs is the sampling frequency of the converter.

L =128 or L=256 is suitable for a typical speech processing application.

Select an oversampling rate. The oversampling rate is decided by ##EQU2## where .DELTA.M is the time-domain increment, and

.DELTA.N is the frequency domain increment.

(m.DELTA.M, n.DELTA.N), where m goes 0 to (SL/.DELTA.M-1), where SL is the sample length, and n goes from 0 to (L/.DELTA.N-1), are the coordinates where a gaussian function is found in the Gabor transform. FIG. 4 illustrates the location of coefficients C.sub.m,n in a Gabor transform algorithm. The oversampling rate of 4 is preferred, though other values are possible. The bigger the oversampling rate, the more computation you must do. An oversampling rate of four has proven to be a good compromise between resolution of the output spectrum and the amount of computation required.

Select .DELTA.M and .DELTA.N such that ##EQU3##

In the implementation of Appendix A, when L=128, we chose .DELTA.M=8 and .DELTA.N=4 though other choices may be quite suitable as well. The selection of .DELTA.M and .DELTA.N determine the resolution of the Gabor spectrum in the time and frequency coordinates, respectively.

Given L, .DELTA.M, and .DELTA.N, the variance value .sigma..sup.2 for the window function can be determined by ##EQU4##

This ensures a localized gaussian function for the window function h. A larger variance can be used for better frequency domain resolution. A smaller variance can be used for better time domain resolution.

Given L and .sigma..sup.2, the gaussian window function h[L] is given, and the discrete auxiliary function .gamma.[L] may be determined as shown in Appendix B, such that .gamma. is similar to h in terms of least squares error. In a preferred system, .gamma. and h are non-overlapping at the limits of the indexed region. Example auxiliary function .gamma.[L] and window function h[L] are shown in FIG. 9.

Steps 1-5 are preliminary steps. The actual spectrum calculation is done from Step 6 on.

FIG. 3 shows how a continuous signal is discretized and how the current algorithm is applied to a sequence of L point frames of the discrete signal s(i). Once the L-points of a frame are acquired, the magnitudes of Gabor coefficients for the L-points are computed by ##EQU5## where * indicates complex conjugate

s(i)=0 for i<0

m=-L/.DELTA.M+1, -L/.DELTA.M+2, . . . , 0, 1, 2, . . .

n=0, 1, 2, . . . , N-1 ##EQU6##

The quantity of m.DELTA.M shows how the input data are used. The following examples illustrate this process.

m=-L/.DELTA.M+1, s(-L+.DELTA.M), s(-L+.DELTA.M+1), . . . , s(.DELTA.M-1) are used

m=0, s(0), s(1) . . . , s(L-1) are used;

m=1, s(.DELTA.M), s(.DELTA.M+2), . . . , s(.DELTA.M+L-1) are used;

m=2, s(2.DELTA.M), s(2.DELTA.M+2), . . . , s(2.DELTA.M+L-1) are used;

In general, s(m.DELTA.M), s(m.DELTA.M+1), . . . , s(m.DELTA.M+L-1) are used.

In each time, the coefficients C.sub.m,n are computed where n=0, 1, . . . , N-1.

As can be seen, this computation has the form of a sequence of FFT computations.

After the coefficients C.sub.m,n are computed for s(i), the spectrum of the signal can be computed by using the cross-term deleted Wigner-Ville Distribution. Note that the Gabor coefficients C.sub.m,n are sparsely located, a complete reconstruction of the spectrum requires the interpolation of the points between the coefficients C.sub.m,n. After deleting the cross-term interference in a Wigner-Ville Distribution, the signal energy can be computed by ##EQU7##

For each Gabor coefficient .vertline.C.sub.m,n .vertline. at (m.DELTA.M, n.DELTA.N), the spectrum value GS.sub.s (i,k) is computed by the formula in Step 7 and accumulated with the previous value of GS.sub.s (i,k). That is, as shown in FIG. 5, the energy at point (i,k) is the accumulated contribution from the distributions of coefficients C.sub.22, C.sub.21, C.sub.31, and C.sub.32, and possibly others. Using the computer language expression, such accumulation can be expressed as ##EQU8##

The constant "4" in equation (8) is a normalization factor that can vary according to a particular application. Because the term ##EQU9## decreases rapidly when the point (i,k) is away from the Gabor coefficient at (m.DELTA.M, n.DELTA.N), the iteration in this step may be limited to a very small region around the point (m.DELTA.M, n.DELTA.N). The exact size region can be adjusted for applications. Also, the above exponential term need not be computed every time. It can be precomputed and stored in a look-up table.

A key problem of computing the spectrum is to decide when to stop, or the size of the update region. Because the energy contributions of C.sub.m,n to its neighboring points exponentially decrease, there is no need to compute the points very far away from (m.DELTA.M, n.DELTA.N). Hence, we need to decide the update region for each Gabor coefficient C.sub.m,n. The update region is defined as an elliptic within which the spectrum needs to be computed such as shown in FIG. 5.

Let i'=i-m.DELTA.M and k'=k-n.DELTA.N, Eq. (9) can be rewritten as: ##EQU10## which is a two dimensional elliptic such as trace 60 of FIG. 5. The update region for any coefficient is defined to be: ##EQU11## where .vertline.C.sub.m,n .vertline..sub.max is the maximum magnitude of all the Gabor coefficients.

Hence, the update region for each coefficient is: ##EQU12##

The maximum update region is the one when .vertline.C.sub.m,n .vertline..sup.2 =.vertline.C.sub.m,n .vertline..sup.2.sub.max, which leads to: ##EQU13##

Thus, k'.sub.max and j'.sub.max give the size of the look-up table. Only positive indices and their values need to be stored because Eq. (B.2) is an even function in terms of i' and k'.

Once the table is created, the computing of Eq. (8) is straightforward. Find the correspondent entry in the table and multiply the value by .vertline.C.sub.m,n .vertline..sup.2. The evaluation of computationally expensive exponential function is thus avoided.

FIGS. 2A and 2B illustrate the basic techniques involving computing the Gabor spectrum according to a preferred embodiment.

The routine involves first initializing the processor (block 50). This initialization involves the performing of steps 1-5 outlined above.

Next, the Gabor coefficients are computed according to the algorithm embodied by blocks 51, 52, 53, 54, and 55 on FIG. 2A.

In particular, the index i is set to -L+.DELTA.M, the index m is set to L/.DELTA.M+1 and M is set to zero (block 51).

Next, the routine acquires the next L points, and sets the input function s(i) equal to zero for i less than zero (block 52).

The next step computes an L-point orthogonal-like discrete Gabor coefficient C.sub.m,n, for the index n=0 through N-1. This computes a column of coefficients for m equal to a constant (block 53). In the next step, m is incremented, and the index i is set equal to i+.DELTA.M (block 54).

Next, the routine determines whether the coefficients have been calculated for all of the frames by testing the index of the loop M, where M equals the number of frames in the sample sequence processed by the loop (block 55). If the routine is not finished, then it branches to block 55A when M is incremented and then back to block 52. If the sequence is finished, then the algorithm proceeds to compute the energy distribution for each of the coefficients according to the routine shown in FIG. 2B.

To compute the spectrum, based on the energy distribution around each of the coefficients, the algorithm receives the coefficients generated by the routine shown in FIG. 2A (block 56). In the next step, the index m is set to -L/.DELTA.M+1 (block 57). Next, the index n is set to zero (block 58).

Next, the update region for the coefficient C.sub.m,n is found based on the magnitude of the coefficient (block 59).

For each point (i,k) within the update region for the coefficient, the energy distribution or spectrum is computed (block 60). Next, the index n is incremented (block 61). In the next step, the index n is tested against the value N to determine whether the distribution for all of the coefficients in the column has been computed. If n is not equal to N, then the algorithm loops back to block 59. If n is equal to N, then a column has been completed and the algorithm proceeds to block 63 where the index m is incremented. In the next step (block 64) the algorithm determines whether the index m has reached the maximum value M. If not, then the algorithm loops to block 58 to process the next frame of coefficients. If m is equal to M, then the algorithm is completed, and the energy distribution values are used to output the Gabor spectrum (block 65). Finally, the routine stops (block 66).

FIG. 6 illustrates a Gabor spectrogram analyzer according to the present invention. The Gabor spectrogram analyzer is an instrument used to analyze an input signal characterized by a time varying frequency spectrum. The apparatus shown in FIG. 6 is particularly useful for signals in the range from 0-20 kH, such as encountered in typical speech processing algorithms. However, the apparatus may be designed to operate in a variety of frequency ranges. Therefore, the same basic apparatus is applicable to a wide variety of input signals with varying frequency ranges.

The system includes a converter/filter 100, including an anti-aliasing filter and an A/D converter. The anti-aliasing filter is an integral part of a variety of data acquisition systems. The purpose of the anti-aliasing filter is to remove unwanted high frequency components so that there will be no aliasing problem when the continuous signal is digitized. According to the sampling theorem, if the highest frequency in an instrument frequency range is f, then the anti-aliasing filter must be designed in such a way that any frequency higher than f should be effectively removed. Because it is not possible to design a perfect low pass filter, the anti-aliasing filter is often designed in such a way that the cutoff frequency is slightly higher than f. The sampling frequency (the rate at which the continuous signal is digitized) must be at least twice that of the highest frequency. In the analyzer shown in FIG. 6, in which the highest frequency is 20 kH, the minimum sampling rate is 40 kH. To provide some safeguard, an audioboard sampling at 48 kH is used which guarantees no aliasing between 0 and 20 kH.

The output of the converter/filter 100 is supplied on line 101 as the signal s(i). A storage device 102 is used for storing the input sequence for later use. For signals that have already been acquired and stored, the converter/filter 100 may not be necessary in a given application. The storage device 102 may act as the source of the sequence of digital signals representing an analog input.

The discrete data on line 101 is supplied to an input buffer 103. The input buffer is controlled by input buffer control 104. The purpose of the buffer 103 is to accumulate enough points (L) for further processing. Each L point block of data is called a frame.

The input buffer control controls the input buffer. Its primary function is to maintain the input buffer 103 and provide overlapping data addressing and the like for ongoing processing of the routine. Depending on the selected time domain increment .DELTA.M, the input buffer control appends .DELTA.M points to a current frame, and removes the first .DELTA.M points to form a new frame.

An L point data frame is available at the output of the buffer 103 on line 105. The frame on line 105 is supplied to a discrete Gabor transform engine 106. The engine 106 performs the Gabor transform according to the algorithm shown in FIG. 2A. The engine 106 maps the one dimensional signal data s(i) to a set of Gabor coefficients in a two dimensional time-frequency domain over the index (i,k).

The output of the Gabor transform engine 106 is an array of coefficients C.sub.m,n for frame m over a sequence of frequency increments on index n. This array of coefficients may be supplied to a coefficient buffer 107, such as a register array or the like. From the coefficient buffer 107, the array of coefficients is supplied to a pseudo-Wigner-Ville distribution engine 108. The engine 108 performs the pseudo-Wigner-Ville distribution with deleted cross term interference according to the routine shown in FIG. 2B. The output is a spectrum defined by the Wigner distribution of energy around each of the coefficients C.sub.m,n. A collection of spectra for the array of coefficients is the Gabor spectrogram GS(i,k). The spectrogram is supplied to a Gabor spectrogram buffer 109 under control of the Gabor spectrogram buffer control 110. The Gabor spectrogram buffer control maintains and controls the Gabor spectrogram buffer 109.

Coupled with the pseudo-Wigner-Ville distribution engine is a look-up table 111. The look-up table stores factors used in the distribution function, as discussed above. Using the look-up table, the computation of these factors can be performed offline, making the algorithm suitable for near real time computation of the Gabor spectrogram.

The Gabor spectrogram buffer control 110 appropriately disposes of the data in the buffer 109 once it is full. For instance, the data is supplied on line 112 to a display system 113 in which a graphic representation of the Gabor spectrogram is generated and displayed. Alternatively, the data on line 112 may be supplied to a storage device 114 for later processing.

In the embodiment shown in FIG. 6, the data on line 112 is supplied to an analysis engine 115. The input sequence s(i) on line 101 is also supplied as an input to the analysis engine. This analysis engine may partition the input signal s(i) in response to the Gabor spectrogram data on line 112 so that the partitioned sections of the input signal may be independently analyzed.

Applications of the displayed Gabor spectrogram, or the data generated by the spectrogram for analysis engine 115 include spectrum analyzers, speech recognition systems, speech analysis and synthesis systems, voice detection systems, underwater acoustics detectors, radar communications, mobile phone communications, and telephone tune detection systems.

FIGS. 7A and 7B illustrate input signals which are analyzed using a routine such as provided in Appendix A according to the present invention. In FIG. 7A, a frequency hopper signal is shown in which there are four discrete frequency components in discrete time windows. In FIG. 7B, a noisy hopper signal with a signal to noise ratio of 0 dB is shown.

FIG. 8A illustrates a Gabor spectrum for the frequency hopper signal of FIG. 7A, in which the contours represent increasing energy values at the time and frequency locations on the spectrum. Thus, if the graph shown in FIG. 8A were shown in three dimensions, each of the regions having contours would appear as peaks on the field of the paper.

It can be seen that each of the four frequency components of the hopper signal are localized in time in the Gabor spectrum. Because of this clear localization and separation between the components, the Gabor spectrum is particularly useful for analyzing signals which have frequency components which vary in time.

FIG. 8B illustrates the Gabor spectrum of the noisy hopper signal of FIG. 7B at the quadruple oversampling rate. As can be seen, even in a very noisy signal, the Gabor spectrum localizes the frequency components relatively well. It is believed that the Gabor spectrum is better than prior art techniques for generating time varying spectra of input signals.

The foregoing description of preferred embodiments of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Obviously, many modifications and variations will be apparent to practitioners skilled in this art. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.

Appendices A and B. ##SPC1##