Method and apparatus for frequency analysis of telephone signals

What is claimed is:

1. A method for identifying an analog or digital signal on a telecommunications line which was produced by a predetermined human voice response, which method comprises the steps of:

(a) storing C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) where:

C.sub.k (x.sub.k,n)=x.sub.k *cos (2.pi.kn/N) and S.sub.k (x.sub.k,n)=x.sub.k *sin (2.pi.kn/N)

for: k=0, . . . , (N-1); n=0, . . . , (N-1); and x.sub.k ranging over all the values of a set of M predetermined digital levels into which the amplitude of the signal is mapped, if the signal is a digital signal, or into which samples of the amplitude of the signal is mapped, if the signal is an analog signal

where: N is a predetermined number of values of the signal, if the signal is a digital signal, or N is the predetermined number of samples of the signal, if the signal is an analog signal, which values or samples are used in determining at least a portion of the frequency spectrum; and n is an index of frequency bins of the frequency spectrum;

(b) determining the sound level of the signal and, when the sound level of the signal exceeds a first predetermined sound level, setting a timer and a frame counter;

(c) obtaining a digital value from the signal, the digital value comprising an amplitude value of the signal if the signal is a digital signal and the digital value comprising a sample of the amplitude of the signal if the signal is an analog signal;

(d) matching the digital value with one of the predetermined set of M predetermined digital levels into which the signal is mapped to provide a value x.sub.j ;

(e) retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j from storage for each of predetermined frequency bins f for the value x.sub.j ;

(f) accumulating the sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for N digital values x.sub.j, by repeating steps (c) through step (f) a sufficient number of times, to provide the real and imaginary part of the content for each of the predetermined frequency bins f;

(g) determining the sound level of the signal and, when the sound level of the signal falls below a second predetermined sound level, proceeding to step (i), otherwise proceeding to step (h);

(h) determining a measure of energy for each of the predetermined frequency bins f from the real and imaginary part of the content thereof, incrementing the frame counter and the timer and, if the frame counter is less than a predetermined frame count, proceeding to step (c), otherwise, storing the measure of energy in the predetermined frequency bins f for predetermined frames, resetting the frame counter and proceeding to step (c);

(i) determining if the timer is outside of a predetermined time range and, if so, transmitting a message that the signal corresponds to an unrecognized response;

(j) comparing variations of functions of the measure of energy for the predetermined frequency bins f in predetermined frames with predetermined variations of the measure of energy for the predetermined frequency bins f for the predetermined human voice response and, if they compare within predetermined limits, transmitting a message that the predetermined human voice response has been detected.

2. The method of claim 1 wherein step (a) of storing comprises storing all of the values of C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) and wherein step (e) of retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) utilizes the values x.sub.j as a pointer into storage.

3. The method of claim 1 wherein step (a) of storing comprises storing a subset of all of the values of C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n), wherein the subset includes values which are different.

4. The method of claim 3 wherein step (e) of retrieving and step (f) of accumulating are performed on a processor wherein a different subroutine is used to carry out step (e) of retrieving and step (f) of accumulating for each of the N values.

5. The method of claim 1 wherein step (h) of determining a measure of energy for each of the predetermined frequency bins f comprises summing the absolute value of the real and the absolute value of the imaginary part of the contents of each of the predetermined frequency bins f.

6. The method of claim 1 wherein step (h) of determining a measure of energy for each of the predetermined frequency bins f comprises summing the square of the real and the square of the imaginary part of the contents of each of the predetermined frequency bins f.

7. The method of claim 1 for use in identifying a signal which was produced by a human voice response of "yes" wherein the predetermined number of frequency bins f is two.

8. The method of claim 7 wherein one of the predetermined frequency bins f has a substantially higher frequency than the other.

9. The method of claim 8 wherein step (h) of determining a measure of energy and storing the measure for predetermined frames comprises storing the measure for the last two frames where the sound level of the signal exceeded the second predetermined sound level, the measure for the lower frequency bin being referred to as the "lower frequency measure" and the measure for the higher frequency bin being referred to as the "higher frequency measure";

wherein step (j) of comparing comprises determining a fraction for each of the last two frames, which fraction equals: ##EQU4## and comparing the sum of the fractions for the last two frames with a predetermined amount and transmitting a message that the predetermined human voice response was "yes" if the sum of the fractions exceeds the predetermined amount.

10. A method for identifying an analog or digital signal on a telecommunications line which was produced by a predetermined human voice response, which method comprises the steps of:

(a) storing C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) where:

C.sub.k (x.sub.k,n)=x.sub.k *cos (2.pi.kn/N) and S.sub.k (x.sub.k,n)=x.sub.k *sin (2.pi.kn/N)

for: k=0, . . . , (N-1); n=0 , . . . , (N-1); and x.sub.k ranging over all the values of a set of M predetermined digital levels into which the amplitude of the signal is mapped, if the signal is a digital signal, or into which a sample of the amplitude of the signal is mapped, if the signal is an analog signal

where: N is a predetermined number of values of the signal, if the signal is a digital signal, or N is a predetermined number of samples of the signal, if the signal is an analog signal, which values or samples are used in determining at least a portion of the frequency spectrum; and

n is an index of frequency bins of the frequency spectrum;

(b) determining the sound level of the signal and, when the sound level of the signal exceeds a first predetermined sound level, setting a timer and a frame counter;

(c) obtaining digital values from the signal, the digital values comprising N amplitude values of the signal if the signal is a digital signal and the digital values comprising N samples of the amplitude of the signal if the signal is an analog signal;

(d) matching each of the digital values with one of the predetermined set of M predetermined digital levels into which the signal is mapped to provide N values x.sub.j for j=0, . . . , N-1;

(e) retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) from storage for each of predetermined frequency bins f and each of the N values x.sub.j ;

(f) accumulating the sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for the N values x.sub.j to provide the real and imaginary part of the content for each of the predetermined frequency bins f;

(g) determining the sound level of the signal and, when the sound level of the signal falls below a second predetermined sound level, proceeding to step (i), otherwise proceeding to step (h);

(h) determining a measure of energy for each of the predetermined frequency bins f from the real and imaginary part of the content thereof, incrementing the frame counter and the timer and, if the frame counter is less than a predetermined frame count, proceeding to step (c), otherwise, storing the measure of energy in the predetermined frequency bins f for predetermined frames, resetting the frame counter and proceeding to step (c);

(i) determining if the timer is outside of a predetermined timer range and, if so transmitting a message that the signal corresponds to an unrecognized response;

(j) comparing variations of functions of the measure of energy for the predetermined frequency bins f in predetermined frames with predetermined variations of the measure of energy for the predetermined frequency bins f for the predetermined human voice response and, if they compare within predetermined limits, transmitting a message that the predetermined human voice response has been detected.

11. Apparatus for identifying an analog or digital signal on a telecommunications line which was produced by a predetermined human voice response, which apparatus comprises:

storage means for storing C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) where:

C.sub.k (x.sub.k,n)=x.sub.k *cos (2.pi.kn/N) and S.sub.k (x.sub.k,n)=x.sub.k *sin (2.pi.kn/N)

for: k=0, . . . , (N-1); n=0, . . . , (N-1); and x.sub.k ranging over all the values of a set of M predetermined digital levels into which the amplitude of the signal is mapped, if the signal is a digital signal, or into which a sample of the amplitude of the signal is mapped, if the signal is an analog signal

where: N is a predetermined number of values of the signal, if the signal is a digital signal, or N is a predetermined number of samples of the signal, if the signal is an analog signal, which are used in determining at least a portion of the frequency spectrum; and

n is an index of frequency bins of the frequency spectrum;

sound level for determining the sound level of the signal and for transmitting a sound level indicator signal;

first initial means, responsive to the sound level indicator signal, for setting a timer and a frame counter when the sound level of the signal exceeds a first predetermined sound level and for sending a signal to a second initial means;

second initial means, responsive to a signal from a measure means or the first initial means, for initializing a sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for N amplitude values of the signal, if the signal is a digital signal, or for N samples of the amplitude of the signal, if the signal is an analog signal, and for sending a signal to a value means;

value means, responsive to a signal from the first initial means or the accumulating means, for obtaining a digital value from the signal, the digital value comprising an amplitude value of the signal if the signal is a digital signal and the digital value comprising a sample of the amplitude of the signal if the signal is an analog signal;

matching means, responsive to a signal from the value means, for matching the digital value with one of the predetermined set of M predetermined digital levels into which the signal is mapped to provide a value x.sub.j ;

retrieving means, responsive to a signal from the matching means, for retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) from the storage means for each of predetermined frequency bins f for the value x.sub.j ;

accumulating means, responsive to a signal from the retrieving means, for accumulating the sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for the value of x.sub.j to provide the real and imaginary part of the content for each of the predetermined frequency bins f and for determining if this is the Nth value of x.sub.j and, if so, for transmitting a signal to a level means, otherwise, transmitting a signal to the value means;

level means, responsive to a signal from the accumulating means and the sound level indicator signal, for determining the sound level of the signal and, when the sound level of the signal falls below a second predetermined sound level, for sending a signal to a time check means, otherwise, for sending a signal to the measure means;

measure means, responsive to a signal from the level means, for determining a measure of energy for each of the predetermined frequency bins f from the real and imaginary part of the content thereof, for incrementing the frame counter and the timer and, if the frame counter is less than a predetermined frame count, for sending a signal to the second initial means, otherwise, for storing the measure of energy in the predetermined frequency bins f for predetermined frames, for resetting the frame counter, and for sending a signal to the second initial means;

time check means, responsive to a signal from the level means, for determining if the timer is outside of a predetermined time range and, if so, for transmitting a message signal denoting that the signal corresponds to an unrecognized response; and, otherwise, for transmitting a signal to a comparison means;

comparison means, responsive to a signal from the time check means, for comparing variations of functions of the measure of energy for the predetermined frequency bins f in predetermined frames with predetermined variations of functions of the measure of energy for the predetermined frequency bins f for the predetermined human voice response and, if they compare within predetermined limits, for transmitting a message signal denoting that the predetermined human voice response has been detected.

12. The apparatus of claim 11 wherein the storage means comprises means for storing all of the values of C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) and wherein the retrieving means for retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) utilizes the values x.sub.j as a pointer into storage.

13. The apparatus of claim 11 wherein the storage means comprises means for storing a subset of all of the values of C.sub.k (x.sub.k, n) and S.sub.k (x.sub.k,n), wherein the subset includes values which are different.

14. The apparatus of claim 13 wherein the retrieving means and the accumulating means comprise a processor means wherein a different subroutine retrieves and accumulates for each of the N values.

15. The apparatus of claim 11 wherein the measure means comprises means for summing the absolute value of the real and the absolute value of the imaginary part of the contents of each of the predetermined frequency bins f.

16. The apparatus of claim 11 wherein the measure means comprises means for summing the square of the real and the square of the imaginary part of the contents of each of the predetermined frequency bins f.

17. The apparatus of claim 11 for use in identifying a signal which was produced by a human voice response of "yes" wherein the predetermined number of frequency bins f is two.

18. The apparatus of claim 17 wherein one of the predetermined frequency bins f has a substantially higher frequency than the other.

19. The apparatus of claim 18 wherein the measure means comprises means for storing the measure for the last two frames where the sound level of the signal exceeded the second predetermined sound level, the measure for the lower frequency bin being referred to as the "lower frequency measure" and the measure for the higher frequency bin being referred to as the "higher frequency measure";

wherein the comparison means comprises means for determining a fraction for each of the last two frames, which fraction equals: ##EQU5## and means for comparing the sum of the fractions for the last two frames with a predetermined amount and for transmitting a message signal denoting that the predetermined human voice response was "yes" if the sum of the fractions exceeds the predetermined amount.

20. Apparatus for identifying an analog or digital signal on a telecommunications line which was produced by a predetermined human voice response, which apparatus comprises:

means for storing C.sub.k (x.sub.k,n) and S.sub.k (x.sub.k,n) where:

C.sub.k (x.sub.k,n)=x.sub.k *cos (2.pi.kn/N) and S.sub.k (x.sub.k,n)=x.sub.k *sin (2.pi.kn/N)

for: k=0, . . . , (N-1); n=0, . . . , (N-1); and x.sub.k ranging over all the values of a set of M predetermined digital levels into which the amplitude of the signal is mapped, if the signal is a digital signal, or into which a sample of the amplitude of the signal is mapped, if the signal is an analog signal

where: N is a predetermined number of values of the signal, if the signal is a digital signal, or N is a predetermined number of samples of the signal, if the signal is an analog signal, which are used in determining at least a portion of the frequency spectrum; and

n is an index of frequency bins of the frequency spectrum;

sound level means for determining the sound level of the signal and for transmitting a sound level indicator signal;

initial means, responsive to the sound level indicator signal, for setting a timer and a frame counter when the sound level of the signal exceeds a first predetermined sound level and for sending a signal to a value means;

value means, responsive to a signal from the initial means or a measure means, for obtaining digital values from the signal, the digital values comprising N amplitude values of the signal if the signal is a digital signal and the digital values comprising N samples of the amplitude of the signal if the signal is an analog signal;

matching means, responsive to a signal from the value means, for matching each of the digital values with one of the predetermined set of M predetermined digital levels into which the signal is mapped to provide N values x.sub.j for j=0, . . . , N-1;

retrieving means, responsive to a signal from the matching means, for retrieving C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) from the storage means for each of predetermined frequency bins f and each of the values x.sub.j ;

accumulating means, responsive to a signal from the retrieving means, for accumulating the sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for the N values x.sub.j to provide the real and imaginary part of the content for each of the predetermined frequency bins f, and for sending a signal to a level means;

level means, responsive to a signal from the accumulating means and the sound level indicator signal, for determining the sound level of the signal and, when the sound level of the signal falls below a second predetermined sound level, for sending a signal to a time check means, otherwise, for sending a signal to the measure means;

measure means, responsive to a signal from the level means, for determining a measure of energy for each of the predetermined frequency bins f from the real and imaginary part of the content thereof, for incrementing the frame counter and the timer and, if the frame counter is less than a predetermined frame count, for sending a signal to the value means, otherwise: for storing the measure of energy in the predetermined frequency bins f for predetermined frames, for resetting the frame counter, and for sending a signal to the value means;

time check means, responsive to a signal from the level means, for determining if the timer is outside of a predetermined time range and, if so, for transmitting a message signal denoting that the signal corresponds to an unrecognized response; and, otherwise, for transmitting a signal to a comparison means;

comparison means, responsive to a signal from the time check means, for comparing variations of functions of the measure of energy for the predetermined frequency bins f in predetermined frames with predetermined variations of functions of the measure of energy for the predetermined frequency bins f for the predetermined human voice response and, if they compare within predetermined limits, for transmitting a message signal denoting that the predetermined human voice response has been detected.

Description Submit all comments and votes

TECHNICAL FIELD OF THE INVENTION

The present invention pertains to the field of frequency analysis of signals and, in particular, to method and apparatus for performing frequency analysis of signals which occur in a telephone network such as the public telephone network. Further, in particular, the present invention pertains to method and apparatus for performing frequency analysis of signals using processors wherein multiplication requires a substantially longer time to perform than addition.

BACKGROUND OF THE INVENTION

It is well known to those of ordinary skill in the art that automated systems for use in telecommunications applications typically require the capability of analyzing and identifying signals which are transmitted over a telephone network, such as, for example, the public telephone network, in order to function properly. For example, it is well known that, under certain conditions, specific machine-generated single-frequency signals, denoted as "call-progress" signals, are transmitted over a telephone network to indicate call status conditions. Examples of commonly occurring call status conditions are busy, call-pickup, operator-intercept and so forth and examples of commonly occurring "call-progress" signals which are used to indicate these call status conditions include, without limitation, SIT tones (system intercept tones), answering machine tones, and so forth.

In addition to machine-generated single-frequency signals, it is also well known that automated systems for use in telecommunications voice processing applications require the capability of analyzing and identifying machine-generated communication signals such as ringback, dial tone, dual tone multifrequency (DTMF) tones, and so forth, as well as signals which are produced by human speech, noise and hum, and so forth. Such a capability of analyzing and identifying signals has many uses which are well known to those of ordinary skill in the art. For example, if an automated system places a call over the public telephone network to a predetermined telephone number, the automated system needs to have the capability of analyzing and identifying a whole host of signals which correspond, for example, to ringback, operator interception, human voice response to the telephone call, and so forth. In addition, because certain voice processing applications require a human to respond to queries with specific spoken responses, an automated system in such an application needs to have the capability of analyzing the signal produced by the human speech and of identifying the particular spoken response the called party gave.

In addition to the above-described need for an automated system to have the capability of analyzing and identifying signals, it is well known to those of ordinary skill in the art that it is desirable for the automated system to have the capability of analyzing and identifying signals rapidly enough so that the automated system can take an action which is an appropriate response to the identified signal.

In addition to the above-described need for an automated system to have the capability of analyzing and identifying signals rapidly enough for the automated system to provide an appropriate response to the identified signal, it is well known to those of ordinary skill in the art that the automated system advantageously should have the capability of analyzing and identifying signals which occur in analog signals or in digital signals. Further, in this regard, it is well known that the capability of analyzing and identifying signals which occur in an analog signal typically comprises a step of providing a digital representation of the analog signal and that there are many methods for performing such an analog-to-digital signal conversion. For example, one may use a linear analog-to-digital conversion method or a differential analog-to-digital conversion method--many such differential analog-to-digital conversion methods are well known to those of ordinary skill in the art collectively as delta modulation and there are many different forms thereof, such as, for example, DM (delta modulation), ADPCM (adaptive differential pulse code modulation), CVSD (continuously variable slope delta modulation), and so forth.

It well known to those of ordinary skill in the art that the capability of analyzing and identifying signals referred to above typically requires an automated system to perform an analysis of the frequency spectrum of a signal. In particular, one method which is well known to those of ordinary skill in the art for determining the frequency spectrum of a signal is the discrete Fourier Transform (DFT) which is used to determine the frequency spectrum of a signal. The DFT for a real signal is defined as follows: ##EQU1## where: x.sub.k are a set of N consecutive digital samples of the amplitude of the signal to be analyzed;

n is a frequency index;

R.sub.n and I.sub.n are the real and imaginary frequency coefficients, respectively; and

the frequency bandwidth of each frequency bin n is equal to (Sample Rate)/N.

As one can readily appreciate from the above, an automated system that uses the DFT set forth in eqn. (1) needs to execute multiplications and additions in apparatus such as a processor. Further, in order for the automated system to analyze and identify the signal in order to provide an appropriate response thereto, it needs to execute the DFT rapidly to provide appropriate portions of the frequency spectrum. As a result, the apparatus in the automated system which executes the required multiplications and additions must execute them rapidly. However, as is well known to those of ordinary skill in the art, the need for apparatus which executes multiplications and additions rapidly has been a problem and, as a result, much activity has been directed towards developing methods for providing the frequency spectrum of a signal which reduce the number of multiplications and additions required in order to improve the speed at which such a frequency spectrum can be provided.

One method which is well known to those of ordinary skill in the art for carrying out the DFT set forth in eqn. (1) entails storing the values of the trigonometric functions in a memory. However, this method is inadequate in certain applications because it requires a large number of multiplications and additions to provide the full frequency spectrum of a signal, which number is given by:

2N.sup.2 multiplications+2N.sup.2 additions: all frequency bins

Further improvements in speed occur in certain applications where it is not necessary to compute the coefficients R.sub.n and I.sub.n for each frequency bin in the frequency spectrum. In such a case, one requires the following number of multiplications and additions to provide the coefficients for a single frequency bin:

2N multiplications+2N additions: per bin

Another method which is well known in the art for carrying out the DFT set forth in eqn. (1) is known as the fast Fourier transform (FFT). The FFT is a method which takes advantage of specific symmetry features of trigonometric functions to provide the full frequency spectrum of a signal. The number of multiplications and additions which are required to provide the full frequency spectrum of a signal using the FFT is given by:

Nlog.sub.2 N multiplications+Nlog.sub.2 N additions: all frequency bins

Although the FFT requires fewer arithmetic operations to provide the entire frequency spectrum than the DFT, when using the FFT one must necessarily determine the content of all frequency bins in the frequency spectrum. As a result of this, in certain application where it is not necessary to compute the coefficients R.sub.n and I.sub.n for each frequency bin in the frequency spectrum, it can take less time to determine the coefficients for the limited number of frequency bins which are of particular interest with the DFT than it does to determine the coefficients for each frequency bin with the FFT. In addition, a further advantage in using the DFT instead of the FFT in such cases is that the DFT permits one to save a little time by performing the multiplications and additions on the "fly," i.e., as the samples are obtained instead of having to wait untill all N samples have been collected as is required with the FFT.

An additional problem occurs when either the DFT or the FFT is used to provide an analysis of the frequency spectrum of a signal. This problem is that a multiplication in a typical processor takes substantially longer to perform than an addition. For example, when one uses the well known 80188 microprocessor which is available from INTEL Corp., a multiplication can take from 5 to 10 times longer than an addition. As a result of this relatively slow multiplication, use of either the DFT or the FFT is prohibitively inefficient and may prevent an automated telephone interactive system from using such microprocessors for analyzing and identifying signals.

As one can readily appreciate from the above, there is a need in the art for method and apparatus for performing frequency analysis of signals rapidly. Further, there is such a need for method and apparatus for performing such frequency analysis using microprocessors wherein a multiplication takes substantially longer to perform than an addition. Still further, there is a need in the art for method and apparatus for performing such frequency analysis of analog signals and of digital signals, whether the digital signals are digitally encoded by a differential encoding scheme or a non-differential encoding scheme such as a linear encoding scheme, a u-law encoding scheme, an A-law encoding scheme, a pulse code modulation (PCM) encoding scheme and so forth.

Lastly, there is a need in the art for method and apparatus for use in automated systems in telecommunications voice processing applications which can identify and differentiate between certain human responses such as, for example between a human response of "yes" and a human response of "no."

SUMMARY OF THE INVENTION

Embodiments of the present invention advantageously solve the above-identified problems in the art by providing method and apparatus for performing frequency analysis of signals rapidly and, in particular, by providing method and apparatus for performing frequency analysis of signals which occur in a telephone network rapidly. Further, embodiments of the present invention advantageously provide method and apparatus for performing such frequency analysis rapidly using microprocessors wherein a multiplication takes substantially longer to perform than an addition.

Specifically, an embodiment of the invention method for determining the content of a predetermined frequency bin f in the frequency spectrum of an analog signal comprises the steps of:

(1) storing:

C.sub.k (x.sub.k,n)=x.sub.k *cos(2.pi.kn/N) and S.sub.k (x.sub.k,n)=x.sub.k *sin(2.pi.kn/N)

for:

k=0, . . . , (N-1); n=0, . . . , (N-1); and x.sub.k ranging over all the values of the set of M predetermined digital levels of a sample of the analog signal

where:

N is a predetermined number of samples of the analog signal, which predetermined number of samples are used in analyzing the frequency spectrum;

n is an index of frequency bins of the frequency spectrum; and

x.sub.k, the digital level of a sample, is restricted to being selected from a predetermined set of M possible amplitude values

(2) sampling the analog signal to provide the j.sup.th sample value and determining x.sub.j, the particular one of the predetermined set of M amplitude values which corresponds thereto;

(3) retrieving the values of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) from storage;

(4) accumulating the sum of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f) for the predetermined number of N samples to determine the real and imaginary part of the content of predetermined frequency bin f.

A preferred embodiment of the above-described method comprises an embodiment wherein the step of retrieving comprises using the sample values x.sub.j as a pointer into storage for retrieving the values of C.sub.j (x.sub.j,f) and S.sub.j (x.sub.j,f). Further, embodiments of the inventive method which take advantage of certain symmetries of the sine and cosine function will be described in detail below.

As one can readily appreciate from the above, the inventive method advantageously requires only 2N additions in real time to determine the content of a frequency bin in the frequency spectrum of a signal. Consequently, the estimated ratio of processor operation time per bin required to perform the direct DFT as compared to the inventive method is given by: ##EQU2##

In particular, for the above-described INTEL 80188, the inventive method operates approximately 5-10 times faster per bin than the direct DFT.

In addition to this advantage over the direct DFT, the inventive method also provides an advantage over the FFT in certain cases where one does not need to determine the content of all the frequency bins in the frequency spectrum. For example, if one confines his interest to a subset L of the N bins in the frequency spectrum, the ratio of processor operation time required for the FFT to that required for the inventive method is given by:

T.sub.2 =T.sub.1 *[log.sub.2 N)/2L]

As an example, if the number of samples N=256, one would need to know the content of at least 24 frequency bins to justify the use of the FFT over the use of the inventive method.

In addition, the above-described inventive method may be used to provide the content of a predetermined frequency bin in the frequency spectrum of a digital signal by omitting the sampling step. Further, as will be described in detail below, the results provided by the inventive method may be used in a great many applications involving a digital signal, for example, in applications pertaining to a digital signal which occurs in a telephone network, without regard to whether the digital signal was digitally encoded using a differential encoding scheme or by a non-differentially encoding scheme such as a linear encoding scheme, a u-law encoding scheme, an A-law encoding scheme, a pulse code modulation (PCM) encoding scheme and so forth.

Further in addition, the invention method and apparatus may be used as part of an inventive method and apparatus for identifying a signal corresponding to a human voice response of "yes.". Embodiments of the inventive method and apparatus for identifying a signal corresponding to a human voice response of "yes," identifies this signal on the basis of the variation of the energy content of various frequency bins in the frequency spectrum of the signal over time. In particular, a preferred embodiment of the inventive method and apparatus, performs a DFT using 8 samples and determines the dynamic behavior of two predetermined frequency bins. Specifically, a preferred embodiment of the inventive method and apparatus used with a signal which is transmitted over a telephone network having a 3000 Hz bandwidth: (a) utilizes a sampling rate of 6000 Hz and determines a measure of the energy of the signal in frequency bins surrounding 750 Hz and 2250 Hz, respectively; (b) determines the fraction of the sum of the energy measure in these two bins which occurs in the frequency bin at the higher frequency over time; and (c) identifies the signal as having been produced by a "yes" if the fraction of the sum of the energy measure in the higher frequency bin is large at the end of the sound, i.e., when the energy of the signal falls below a predetermined level.

In general, embodiments of the inventive method and apparatus compare the variation in the fraction of energy which occurs in the higher frequency bin over time with a library of predetermined envelopes of such variations. The library of predetermined envelopes are stored, for example, in a memory. The embodiment identifies the human voice response which produced the signal by comparing the variation of energy with the library envelopes. If no match is determined, a voice processing application can ask for a further response from the speaker in order to provide the system another chance for properly interpreting the human voice response.

BRIEF DESCRIPTION OF THE DRAWING

A complete understanding of the present invention may be gained by considering the following detailed description in conjunction with the accompanying drawing, in which:

FIG. 1 shows, in pictorial form, a block diagram of a preferred embodiment of the inventive apparatus for detecting signals on a telephone line and analyzing the frequency spectrum thereof; and

FIGS. 2A and 2B show a flow chart of a microprocessor program which forms part of a preferred embodiment of the inventive apparatus shown in FIG. 1.

To facilitate understanding, identical reference numerals have been used to denote identical elements common to the figures.

DETAILED DESCRIPTION

FIG. 1 shows a block diagram of a preferred embodiment of inventive apparatus DM 10 and the manner in which it is used for detecting signals on a telephone line and for analyzing the frequency spectrum thereof to identify the human response which produced the signal. Further, as will be described in detail below, this preferred embodiment of inventive apparatus DM 10 can be used to identify a signal which was produced by a human voice response of "yes."

As shown in FIG. 1, telephone signal 100 from telephone network 20 is transmitted by telephone network interface 25 to DM 10 as signal 110. Many apparatus for use as telephone interface 25 are well known to those of ordinary skill in the art. For example, one such apparatus comprises a portion of a DIALOG/41 Digitized Voice and Telephony Computer Interface circuit which is available from Dialogic Corporation, 129 Littleton Road, Parsippany, N.J. 07054. In pertinent part, this circuit comprises well known means for interfacing with the telephone network to send and receive calls; means, such as transformers, to electrically isolate subsequent circuits; and filter circuits.

Signal 100 which is output from telephone network interface 25 is applied as input to DM 10 and, in particular, to ancillary hardware 70. Specifically, signal 110 is applied to a sample and hold circuit (not shown) in ancillary hardware 70, which sample and hold circuits are well known to those of ordinary skill in the art.

The output from the sample and hold circuit contained in ancillary hardware 70 is applied to differential analog-to-digital converter 40. There are many circuits which are well known to those of ordinary skill in the art that can be used as differential analog-to-digital converter 40. For example, differential analog-to-digital converter 40 may be a Motorola MC3518 CVSD encoder which is available from Motorola Semiconductor Products Division of Austin Texas, an Oki Electric MSM5218 ADPCM encoder which is available from Oki Semiconductor of Sunnyvale, Calif., or any other such equipment. The differentially encoded signal output from differential analog-to-digital converter 40 is placed, sample by sample, into a tri-state buffer (not shown) for subsequent tranmsittal to a data bus (not shown). A tri-state buffer for performing this function is well known to those of ordinary skill in the art. For example, the tri-state buffer may be a TI 74LS244 tri-state buffer which is available from Texas Instruments of Dallas, Tex., or any other such equipment.

DM 10 further comprises microprocessor 50, memory 60, and a portion of ancillary hardware 70 for use interfacing with a host computer 30. Microprocessor 50 may be any one of a number of microprocessors which are well known to those of ordinary skill in the art such as an INTEL 8086 or an INTEL 80188 microprocessor which are available from INTEL of Santa Clara, Calif., or any other such equipment. Memory 60 may be any one of a number of memory equipments which are well known to those of ordinary skill in the art such as an HITACHI 6264 RAM memory which is available from HITACHI America Ltd. of San Jose, Calif., or any other such equipment. The portion of ancillary hardware 70 which interfaces with host computer 30 may be readily fabricated by those of ordinary skill in the art by using circuits which are also well known to those of ordinary skill in the art. For example, the portion of ancillary hardware 70 which interfaces with host computer 30 may be comprised of TI 74LS245 data bus transceivers, TI 74LS244 address buffers, and TI PAL 16L8 control logic, all of which is available from Texas Instruments of Dallas, Texas, or any other such equipment. Finally, as shown in FIG. 1, DM 10 interfaces with host computer 30, which may be any one of a number of computers which are well known to those of ordinary skill in the art such as, for example, an IBM PC/XT/AT, or any other such equipment.

The differentially encoded digital samples output from differential analog-to-digital encoder 40 are placed in the buffer (not shown) and are output, in turn, therefrom to the data bus (not shown). Then, the digital samples are received from the data bus, digital sample by digital sample, by microprocessor 50.

As stated above, apparatus DM 10 identifies a signal which was produced by a human voice response of "yes." In so doing, DM 10 determines the content of certain predetermined frequency bins of the frequency spectrum of incoming telephone signal 100. Advantageously, the inventive method for identifying a signal produced by a human voice response of "yes" does not depend on a determination of exact values of the frequency content of the predetermined frequency bins in the frequency spectrum of incoming signal 100. As a result, embodiments of the inventive method can utilize ADPCM digitally encoded sample values of signal 100 without the need to convert the ADPCM samples into linear PCM sample values. This is advantageous because this broadens the applicability of the inventive method and apparatus and saves the time required to perform such conversions. Further, an additional advantage is that the inventive method and apparatus can be used when incoming signal 100 is already a digital signal because, in such applications, there is no need to convert the input digital signal, which input digital signal may been encoded using u-law or A-law PCM, into a linear PCM format. Because of this, in describing the inventive method, we will merely refer to the samples which are used in the inventive method and apparatus as digital samples.

Before describing a preferred embodiment for identifying a signal which was produced by a human voice response of "yes," we will describe the method by which the content of predetermined frequency bins in the frequency spectrum of incoming signal 100 is determined. After that, we will describe how this method is used in the preferred embodiment of the inventive method and apparatus to identify a signal which was produced by a human voice response of "yes."

In accordance with the inventive method, the total set of possible sample values of the amplitude of the inpu