US 3,961,167 AGrant
PCM Tone Receiver Using Optimum Statistical Technique
Issue Date:1976-06-01
•8 Claims
•6 Drawing Sheets
Abstract
This invention relates to signal detecting and in particular to apparatus and a method for detecting one or more audio frequencies (tones) contained in a Pulse-Coded Modulation (PCM) signal.
Metadata
Assignee
- GTE Automatic Electric Laboratories Incorporated
Inventor
- Jeffrey P. Mills
Application Information
Application Number:US 4904508
Filing Date:1974-07-22
Priority Date:1974-07-22
Art Unit:236
Classifications
IPC:
G06F 1536H04Q 1100
Field of Search:
235325179178324152;150.1;151.3321;38 R;38 A;39;4015 AP;15 BY68;8877 B;77 D
Patent Drawings (6 sheets)
Description
Background of the Invention
Reference may be made to the following U.S. Pat. Nos.: 2,902,542; 3,432,619; 3,435,147; 3,544,723; 3,548,107 and 3,632,888.
Pulse-Coded Modulation (PCM) is a system of audio frequency transmission whereby the continuously varying (analog) audio signal is coded into a series of digital binary pulses, transmitted over a distance, and then converted back to analog. The signal, while in digital form, may be transmitted over very large distances. Any distortion or attenuation introduced by the transmission medium can be corrected for at strategic points ("repeaters") since the full amount of information can be recovered from the digital pulse-coded signal at each repeater. Furthermore, many audio signals can be combined onto one PCM line, and later separated, so that the line can transmit many conversations. This multiplexing is achieved by sequentially transmitting one pulse from each conversation onto the line, and, at the receiving end of the line, using a demultiplexer to divert each pulse to the correct converter, each of which then converts the pulses of one conversation back to the conventional analog form. The principle is described in various publications, and reference may be made for instance to "An Introduction to PCM Switching", Automatic Electric Technical Journal, April, 1971.
Control signal information, such as the number being called, etc., is conveyed over conventional telephone lines by audio-frequency tones, such as the Touch Calling Multifrequency (TCMF) and the Two-Out-of-Six Multifrequency (2/6 MF) schemes. In these schemes two audio frequencies are generated by oscillators and applied to the conventional telephone line, and filters are used at the receiving end to detect the presence of these control signal tones and cause the system to operate accordingly.
Although many different schemes could be used to transmit the control signal information over PCM lines, it is desired, for compatibility reasons, to inject the same tones into the analog circuitry and code them, like any other audio signal, such as voice signals, into the PCM format. Then, at the receiving end, the demultiplexer could convert this pulse-coded tone back to analog, and the presence of the tones may be detected, as with conventional telephone lines, by filters, as set forth for example in U.S. Pat. No. 3,544,723. This patent also suggests the detection of a PCM tone signal by comparing an incoming signal to its delayed derivative, the detection being effected in the PCM domain.
Improved method and apparatus for detecting one or more tones in a PCM signal are disclosed in applicant's copending applications, Ser. No. 309,020, filed Nov. 24, 1972, now U.S. Pat. No. 3,863,030; and Ser. No. 311,064, filed Dec. 1, 1972, now U.S. Pat. No. 3,824,471, and assigned to the same assignee here. Those applications use digital Fourier spectrum analysis and describe two different techniques for implementation.
Summary of the Invention
Accordingly it is a principal object of the present invention to provide a novel PCM receiver combination and method for detecting a PCM tone signal utilizing logic circuits without the necessity of converting the PCM signal to analog and then filtering it, without the necessity for deriving the derivative of the PCM signal, and with a lower error rate than that obtainable using Fourier spectrum analysis. The detector monitors the incoming PCM signal to determine the presence of a valid combination consisting of any two of the six frequencies used for control. It determines the tone combination (or absence of tones) which would most likely cause the sequence of samples being observed. This process constitutes statistical detection, which is a well-known process. The application of the process to this problem is discussed in my paper entitled "Statistical Detection of Quantized Audio Tones", Proceedings of the National Electronics Conference, vol. 28, 1973.
The apparatus required for the detection technique described herein is somewhat more complex than that described in either of my above mentioned applications. Therefore, this technique is best suited for applications where the errors introduced by the previously described techniques, although small, are unacceptable. However, as more large scientific computers are produced, the component circuits may become readily available in large-scale monolithic form. Then, the present invention may be preferable over those described in the aforementioned applications even when the reduced error rate is not required.
In one embodiment of the invention, a multiplicity of N samples from the PCM signal are observed and are designated by an N-dimensional vector, x. Typically, 10 samples are observed, i.e., N = 10. The audio signal which was encoded to obtain these samples may or may not contain a pair of MF tones, and there are several combinations of MF tones which the signal could contain. The combination of MF tones is designated .beta., which may be equal to 1, 2, etc., or 0 if no tones are present at all. Depending on the PCM samples x, it is possible to estimate which combination of MF tones .beta. was probably transmitted. Specifically, for each possible combination of MF tones .beta., the probability that the sequence of samples x would result is calculated. This probability is designated P.sub.x .sub..beta.. The combination .beta. for which P.sub.x .sub..beta. is highest is then deemed to be the combination of MF tones which is present. If .beta. is deemed to be 0, then this is equivalent to deciding that no MF tones are present at all.
Other objects will appear from time to time in the ensuing specification, drawings and claims.
Brief Description of the Drawings
FIG. 1 is a block diagram representation of the PCM tone receiver of the present invention;
FIG. 2 is a block diagram representation of the floating-point multipliers of FIG. 1;
FIG. 3 is a block diagram representation of the floating-point adders of FIG. 1;
FIGS. 4 and 5 are a block diagram representation of a detector circuit driven by the PCM tone receivers of the type in FIG. 1; and
FIG. 6 is a graphic representation of a quantizing function useful in describing the method of the present invention.
Description of the Preferred Embodiment
The essence of my invention is a device which calculates the probability P.sub.x .sub..beta. defined above. The theory behind this calculation is fully justified in my dissertation, entitled Statistical Detection of Quantized Audio Tones, Illinois Institute of Technology, Chicago, 1973. The process will be described here.
Corresponding to each possible combination of MF tones, (including the special case of no tones at all, or .beta. = 0), there exists a unique covariance matrix, which is designated .LAMBDA. .sub..beta. . If the number of PCM samples to be observed is designated N, then .LAMBDA. .sub..beta. is a positive-definite, symmetric N .times. N matrix. The actual values of the numbers contained in the matrix depend on the tone frequencies being sought, as well as their strength and tolerance and the amount of background noise. The numbers must be calculated, for each possible pair of tones, by the method described below.
A tone generated by an oscillator will vary slightly in amplitude and frequency and therefore constitutes a stochastic process. A stochastic process will first be defined corresponding to each single tone, and, by summing the two appropriate processes, it will then be possible to define a stochastic process corresponding to each possible combination, .beta..
The output of a sinewave oscillator is a stochastic process given by:
where t represents time and where V, .omega., and .phi. are random variables representing peak amplitude, angular velocity (2.pi.- frequency), and phase, respectively. The process must be stationary, since the time origin is unknown and therefore cannot affect the process. Therefore, the phase must be uniformly distributed, or:
System specifications state that the frequency of an audio signaling tone must be held within a certain range centered about the nominal frequency, but nothing is usually specified regarding the probability density of the frequency within its permissible limits. For the purpose of this analysis, the frequency is assumed to have a normal probability density function with its mean equal to the given nominal frequency, f.sub.0, and with its standard deviation equal to one third of the specified frequency tolerance, .DELTA.f. Then the conditional probability density of given f.sub.0 is given by: ##EQU1## where .omega..sub.0 = 2.pi.f.sub.0 and .sigma..sub.2 = 2.pi..DELTA.f/3.
System specifications state V.sub.max and V.sub.min, the tolerance limits of the tone amplitude, but, again, nothing is usually known about the probability density function of the amplitude between these limits. In this case it is most reasonable to assume that the logarithm of the amplitude is normally distributed between the limits. The resulting amplitude probability density function is the logarithmico-normal function: ##EQU2## where .sigma..sub.1 = (1/6)1n(V.sub.max /V.sub.min). Furthermore, it is assumed that .phi., .omega., and V are all statistically independent.
The stochastic process, u(t), consisting of a single, undistorted audio tone, with random amplitude, frequency, and phase, is completely defined by Eqs. (1) through (4). Except for the small probability that one of the normally-distributed random variables exceeds three times its standard deviation, this definition is consistent with the system specifications.
It may be shown by one skilled in the art that the mean of u(t) is zero and that its autocorrelation function, which depends on the nominal tone frequency, f.sub.0, is given by: ##EQU3## where: ##EQU4## The quantity .sigma..sub.u.sup.2 is equal to R.sub.fo (0) and therefore represents the average total power present in u(t).
Equation (5) states the autocorrelation function of u(t) in terms of V.sub.max, V.sub.min, f.sub.0, and .DELTA.f, all of which are explicitly specified for a particular tone in a given system. When numerical values are substituted for these quantities, a well-defined function, R.sub.fo (.tau.) results.
A new process, designated u(t), is now defined to be an ergodic Gaussian process with its mean equal to zero and its autocorrelation function equal to R.sub.fo (.tau.) given by Eq. (5). Thus, the mean and autocorrelation function of u(t) are identical to those of u(t). The sample functions of the two processes may be shown to be similar, although not identical. For the purposes of this invention, the Gaussian process u(t) is used to represent u(t). With this approximation, computation is greatly simplified.
Now consider the sum of two such processes designated u.sub.1 (t) and u.sub.2 (t). Their cross-correlation functions are identically zero; therefore, the processes are uncorrelated, or linearly independent. Thus, the autocorrelation function of their sum is equal to the sum of their autocorrelation functions.
Let u.sub.1 (t) and u.sub.2 (t) represent the Gaussian approximations of u.sub.1 (t) and u.sub.2 (t), respectively. In order that the autocorrelation function of u.sub.1 (t) + u.sub.2 (t) be identical to that of u.sub.1 (t) + u.sub.2 (t), u.sub.1 (t) and u.sub.2 (t) must be uncorrelated. Therefore, in order to achieve a sum process which is Gaussian, u.sub.1 (t) and u.sub.2 (t) must be statistically independent, and any possible interdependence between u.sub.1 (t) and u.sub.2 (t) must be ignored in the Gaussian approximation. This does not significantly reduce the optimality of the detector.
The generated audio tones pass through various sources of additive noise before being applied to the input of the PCM encoder. System specifications stipulate that the detector must operate under the assumption that the additive noise is Gaussian, band-limited white noise with specified power and bandwidth. This noise will therefore be added to the tones present in each message, and it represents only channel noise applied before the signal is encoded into PCM format. It does not include quantizing noise, which will be discussed later.
If n(t) is a stationary band-limited white Gaussian process, its autocorrelation function is given by:
where .sigma..sub.n.sup.2 is the noise power, f.sub.2 is the upper cut-off frequency, and the lower cutoff frequency is zero. Since the noise process is Gaussian, it is completely specified by Eq. (7).
Let u(t) represent any stationary Gaussian random process, and let it be sequentially sampled N times with a period designated T. The amplitude of u(t) at each respective instant of sampling will then be u(t.sub.0), u(t.sub.0 +T), u(t.sub.0 +2T), u(t.sub.0 +3T), . . . , u(t.sub.0 +(N-1)T), where t.sub.0 is an arbitrary time origin. Let u be an N-element column vector representing these amplitudes. Then, since u(t) is Gaussian, the joint probability density function of all elements of u is Gaussian and is therefore given by:
where .LAMBDA. is the convariance matrix of u, and where u.sup.t represents the transpose of u. Each element of .LAMBDA. is given by:
where R represents the autocorrelation function of the stationary process u(t).
If u(t) approximates a single audio tone, then its autocorrelation function is given by Eq. (5); its covariance matrix, .LAMBDA..sub.fo, may be obtained by evaluating R.sub.fo (.tau.) at .tau.=0, .tau.=T, .tau.=2T, etc. On the other hand, if u(t) is band-limited white Gaussian noise, then its autocorrelation function is given by Eq. (7). In the physical systems discussed herein, the upper cutoff frequency of the system, f.sub.2, is equal to one half the sampling rate. Symbolically:
then, by Eq. (7):
and therefore:
where I is the identity matrix. Finally, if u(t) is a combination of these processes representing a message, .beta., then its covariance matrix, .LAMBDA.36 .sub..beta., is equal to the sum of the covariance matrices of the individual processes, each obtained as above. The joint probability density function of the amplitudes of all samples, u, resulting from the tone combination .beta., is then given by:
This probability density function is the basis of the detection scheme used in this invention.
A pulse-modulated signal is quantized in order that it may be encoded into binary form. Quantization may be regarded as a function, designated Q. It is a step function possibly with varying step sizes, such as shown for a D-2 channel quantizer in FIG. 6. The independent variable, u, is a continuous variable which represents the quantizer input voltage, and the dependent variable, x, is a discrete number which specifies the appropriate quantizing level on the graph. Only the magnitudes of u and x are shown; it is understood that their signs are identical.
To define the function, Q, it is only necessary to tabulate the lower end point a(x) and the upper end point b(x) for each segment x. Alternatively, the midpoint c(x) may be tabulated, along with d(x), the distance from the midpoint to either end of segment x. These quantities are illustrated for x = +120 in FIG. 6. The table is not included here but it may easily be derived from the compatibility specification for the system under consideration. Functions a and b are related to c and d as follows:
These functions will be subsequently utilized to derive the joint probability distribution of the output of the quantizer.
Let a sample u.sub.k be applied to the input of the quantizer defined above. The output of the quantizer, designated x.sub.k, will then be Q(u.sub.k), where Q represents the quantizing function. If each of the N samples is sequentially applied to the quantizer, then the N consecutive outputs, designated by the vector x, will be given by:
A particular value of x occurs if and only if the following inequality is satisfied for every sample:
where a and b are the end-point functions defined.
Let the variables u.sub.1 through u.sub.N define the coordinates of a point in an N-dimensional Euclidean space. Then Eq. (16) is satisfied for every sample if and only if the point lies within the region bounded by the hyperplanes u.sub.1 = a(x.sub.1), u.sub.2 = a(x.sub.2), . . . , u.sub.N = a(x.sub.N), and the hyperplanes u.sub.1 = b(x.sub.1), u.sub.2 = b(x.sub.2), . . . , u.sub.N = b(x.sub.N). This region, designated .OMEGA.(X), is a rectangular hypersolid; its position and size depend on x.
The conditional distribution of x given .beta. is therefore given by: ##EQU5## where P.sub.u .sub..beta. (u.vertline..beta.) is given by Eq. (13) which, when substituted into Eq. (17), yields: ##EQU6## where .LAMBDA. .sub..beta. is the covariance matrix corresponding to the message .beta..
A multi-dimensional hypervolume integral may be calculated approximately by multiplying the hypervolume of the region of integration by the value of the integrand at the center of the region. The hypervolume of region .OMEGA.(x) is equal to the product of all of its dimensions, which is expressed as ##EQU7## since each i -th dimension is equal to 2d(x.sub.i). The value of u at the center of .OMEGA.(x) is equal to c(x), which is a vector containing c(x.sub.1), c(x.sub.2), . . . , c(x.sub.N). Therefore: ##EQU8## This expression yields an acceptable approximation to P.sub.x .sub..beta., and will henceforth be assumed to be equal to P.sub.x .sub..beta. for practical purposes.
Since .LAMBDA..sub..beta. is positive definite, there must exist a lower triangular matrix, A.sub..beta., such that (A.sub..beta.).sup.t . (A.sub..beta.) = 1/2 .LAMBDA..sub..beta..sup..sup.-1, where (A.sub..beta.).sup.t represents the transpose of the matrix A.sub..beta., .LAMBDA..sub..beta..sup..sup.-1 represents the inverse of matrix .LAMBDA..sub..beta., and where .sup.. represents conventional matrix multiplication. The numbers contained in matrix A.sub..beta. may be calculated from those contained in matrix .LAMBDA..sub..beta. by a well-known technique known as triangular decomposition.
For each pair of MF tones, .beta., therefore, the numbers contained in matrix .LAMBDA..sub..beta. and those contained in matrix A.sub..beta. may be calculated by known techniques. These numbers are constants for each possible pair of MF tones .beta. and are stored in certain read-only memories contained in the apparatus to be subsequently described.
The apparatus to be described is entirely digital. Where analog quantities must be represented, the quantities are expressed as 8-bit floating-point binary numbers. The convention used in my invention is such that any floatingpoint number contains a 1-bit sign, s, a three-bit exponent, c, and a 4-bit fraction, m. The 8-bit floating-point number is organized thus:
where each letter represents 1 binary bit which may be either zero (0) or one (1). Thus, the range of C is from zero 000 to seven (111). The number m is assumed to have a binary point immediately to the left of m.sub.1, therefore its value may range from zero (0.0000) to 15/16 (0.1111). If S = 0, the floatingpoint number is positive, whereas if S = 1 then the number is negative. With these conventions, the value, V, of the floatingpoint number represented by these bits is defined to be:
Therefore, this convention may be used to approximately represent any positive or negative quantity whose magnitude is between zero (which is represented by 00000000 or 10000000) and one (which is represented by 01111111 if positive, or 11111111 if negative). Several of the quantities to be represented (probabilities, for example) have precisely this range. If the quantity being represented has a different range, then a scale factor, V.sub.o, will be included which is equal to the maximum possible value of the quantity being represented. Thus:
In particular, the instantaneous voltage of the analog signal is represented in this manner when encoded into a PCM sample (except for a small displacement discussed later). Typically, the range of the analog signal voltage is from 0 volts to .+-.2 volts. Therefore, the instantaneous voltage is properly represented if a scale factor of 2 volts is assumed, i.e., V.sub.o = 2 volts.
A block diagram of the preferred embodiment of my invention is shown in FIG. 1. Each interconnection which is represented by a heavy (double) line consists of eight leads which convey a floating-point binary number as defined above. An interconnection represented by a fine (single) line consists of a single lead which conveys 1 binary bit. The function of each block will now be described. For simplicity, the circuitry is shown for N = 4; it may be expanded as shown to provide any value of N.
Blocks 1 through 5 are floating-point multipliers. The floating-point number appearing at the output of each multiplier is equal to the product of the floating-point numbers applied to the two inputs of that multiplier. Since floatingpoint multiplication is a well-known technique, known circuits may be used here. One such circuit is shown in FIG. 2. The floating-point multiplication algorithm is as follows:
1. The sign of the product is equal to the exclusive-or (.sym.) of the signs of the factors, i.e.:
2. The exponent of the product is equal to the sum of the exponents of the factors minus eight, i.e.:
The value of eight must be subtracted in order to account for the scaling factor of 256 described earlier.
3. The fraction of the product is related to the fractions of the factors in the following manner:
or
The operation of FIG. 2 is self-explanatory, with the exception of the function of the AND gates. If c.sub.1 + c.sub.2 is eight or greater, an addition overflow occurs, and, if this overflow is ignored, the output of the 3-bit fixed-point adder is equal to c.sub.1 + c.sub.2 - 8, as desired. If c.sub.1 + c.sub.2 is less than 8, however, no overflow occurs, and, in fact, c.sub.1 + c.sub.2 - 8 is negative. Since a negative exponent represents a very small number, the sum is forced to zero by the AND gates in this case. This avoids the necessity of providing for negative exponents. The 256-word read-only memory is addressed by 8 bits--four from each fraction m.sub.1 and m.sub.2. The word read out from that address is equal to
Blocks 6 through 12 are floating-point adders. The floating-point number appearing at the output of each adder is equal to the sum of the floating-point numbers applied to the two inputs of that adder. Since floating-point addition is a well-known technique, known circuits may be used here. One such circuit is shown in FIG. 3, and is described as follows.
Subtractor 70 is a four-bit subtractor. Its outputs are defined as follows: ##EQU9## where all outputs are 1-bit binary numbers. The outputs thus represent a 5-bit positive or negative binary number in signed magnitude form. This is also a standard logic circuit as used, for instance, in digital computers.
Selector 71 is a data selector, which is also a standard logic circuit as used in digital computers. Its data inputs and output are each three bits. Since it contains two data inputs, its address input requires one bit. When the address input is 0, the data on input 0 is routed through to the output, and when the address input is 1, the data on input 1 is routed through to the output. AND gates 72 through 77 are standard logic circuits wherein an output is 1 if and only if both inputs are 1. Not gate 92 is also a standard logic circuit wherein the output is 1 if and only if the input is 0.
Adder 89 is a fixed-point adder identical to Adder 52 of FIG. 2 except that input a.sub.2 is only one bit.
The adder unit 88 is also a fixed-point adder. The inputs and the output are 5-bit signed binary numbers with negative numbers expressed in signed magnitude form. Each 6-bit signed number contains a sign bit and five magnitude bits.
This is also a standard logic circuit.
Shifter circuits 80 through 86 are described as follows. Input a and the output are 5-bit binary numbers. The amount of shift, m, is one for circuits 80, 81 and 86; two for circuits 82 and 93; and four for circuits 84 and 85. If a.sub.i o.sub.i represent one input bit and one output bit, respectively (1.ltoreq.i.ltoreq.5), where bit 1 is the left-most bit, and bit 5 is the right-most, the logic of all shifter circuits is as follows, substituting the appropriate number for m as specified above:
where E and .vertline. represent Boolean "AND" and "OR", to distinguish from multiplication or addition. The result is that, if input s is 1, the output is equal to input a shifted m bits to the right, with binary zeros shifted into bits o.sub.1 through o.sub.m. Shifter 86 provides a special function; namely, it replaces a bit lost due to overflow; therefore, this shifter shifts a binary "one" into bit o.sub.1. If input s of any shifter is o, its output is equal to input a with no shift or other change whatsoever.
Operation of the floating-point adder is as follows. The entire circuit is combinational; i.e., the floating-point sum or difference appears at its output as soon as the two numbers are applied at the inputs, except for gate delays.
The binary output of subtractor 70 is equal to the difference of the two exponents. Case 1 occurs when the exponent of a.sub.2 is greater than or equal to the exponent of a.sub.1. Then s = 0 and the outputs of AND gates 72, 73, and 74 are 0. Since the coefficient of a.sub.2 is equal to its fraction plus one (1 + m), a constant 1 must be added to the fraction. The resulting coefficient of a.sub.2 is propagated through shifter circuits 80, 82, and 84, with no shifting, to input a.sub.2 of adder 88. The address input of selector 71 is also 0, and the exponent of a.sub.2 is propagated through selector 71 to input a.sub.1 of adder 89.
The magnitude of the difference of the exponents is represented, in binary format, by the three outputs d.sub.1 through d.sub.7, of subtractor 70. Since output s is 0, the output of Not gate 92 is 1. Therefore, the s inputs of shifters 81, 83, and 85 will be equal to the outputs d.sub.1, d.sub.2, and d.sub.4, respectively, of subtractor 70. The coefficient of a.sub.1 (i.e., its fraction plus 1) is applied to shifter 81, which will shift it one bit if d.sub.1 = 1. The result is applied to shifter 83 which in turn will shift it two more bits if d.sub.2 = 1, and so forth. The total number of shifted positions will be equal to the binary number represented by d.sub.1, d.sub.2, and d.sub.4 which is equal to the difference of the two exponents. The shifted coefficient is then in the correct position to be applied to input a.sub.1 of adder 88.
The output of adder 88 is the sum of the coefficient of a.sub.2 and the shifted coefficient of a.sub.1. According to the well-known floating-point addition algorithm, this sum will represent the coefficient of the floating-point sum.
Case 2 occurs when the exponent of a.sub.1 is greater than the exponent of a.sub.2. Then s = 1, the exponent of a.sub.1 is propagated through selector 71, and the coefficient of a.sub.2 is shifted by an amount equal to the difference between a.sub.1 and a.sub.2 in the same manner as the coefficient of a.sub.1 was shifted in case 1. The output of adder 88 is, as with case 1, the coefficient of the sum of a.sub.1 and a.sub.2.
When the addition or subtraction within adder 88 causes an overflow, i.e., when the sum or difference would require 6 magnitude bits, output ovf is 1. The coefficient of the sum or difference is shifted one bit to the right by shifter 87, which also shifts the lost bit back into the coefficient, as previously described. Adder 89 adds 1 to the exponent to correct for this shift. On the other hand, if no overflow occurs, the coefficient and exponent are propagated through shifter 87 and adder 89, respectively, with no change. The output is, in all cases, the floating-point representation of the sum of a.sub.1 and a.sub.2. The uppermost bit of the coefficient is ignored, and the remaining 4 bits comprise the fraction.
Blocks 13 and 28 are NOT gates, or inverters. These are well-known digital logic circuits.
Blocks 14 through 18 are four-bit buffers, or D-registers. When the C input changes from a logic 0 to a logic 1, the 4-bit binary number applied to the data input will appear at the otput of the respective buffer. At all other times the output will retain its previous value regardless of the state of the data input. This is a standard logic circuit.
Block 19 is a 256-word, 8-bit read-only memory which is used as a function generator to generate the function f. The contents of the memory are fixed at the time of manufacture. The contents of each word are related to its address in the following manner. The 8-bit address applied to the memory is designated x and is actually a floating-point binary number whose value is designated c(x). Let d(x) represent the difference between this value, c(x), and the next larger value which may be represented by the type of floating-point number used here. Thus, d(x) is a measure of the precision of the value c(x). The contents of the read-only memory location at each address x is made equal to the floating-point representation of the natural logarithm of the difference, d(x). Thus, for any binary number x applied to the memory, where x represents the quantity c(x), the output of the memory will represent the quantity 1 n[d(x)].
Blocks 20 through 23 are N-word, 8-bit read-only memories, where N is the number of observed PCM samples as defined previously. In this case, the address is a fixedpoint binary number, i, which may range from 1 to N. Word i of memory 20 contains the floating-point representation of the number a.sub.ii, which is the number contained in the i-th row and the i-th column of matrix A.sub..beta., defined earlier. Word 1 of memory 21 contains zero, and for i>1, word i contains the number a.sub.i, i.sub.-1 which is the number contained in the i-th row and the (i-1)-th column of matrix A.sub..beta.. Words 1 and 2 of memory 22 contain zero, and for i>2, word i contains the number a.sub.i, i.sub.-2, which is the number contained in the i-th row and the (i-2)-th column of matrix A.sub..beta.. The contents of the remaining memories up to 23 follow the same pattern; the first k-1 words of the k-th memory contain zero, and for i>k-1, word i contains a.sub.i, i-k-1. As stated earlier, the matrix A.sub..beta. (and therefore the numbers a.sub.ii, etc.) are determined by known mathematical techniques from the covariance matrix .LAMBDA..sub..beta., which is, in turn, determined from information known about the MF tones being sought. The numbers a.sub.ii, etc., are different for each pair of MF tones being sought, i.e., for each value of .beta..
Block 24 is a modulo-N binary counter. Each time its input is changed from 0 to 1, its output changes to the next higher binary number, until the number N is reached at which time it returns to zero. This is a well-known logic circuit.
Block 25 is an autonomous clock circuit which generates alternate 1s and 0s at its output at a rate corresponding to the rate of the observed PCM samples, which in this case is 8 kilohertz, i.e., 8000 logic 1s and 8000 logic 0s per second.
Block 26 is a decoder circuit. Its output is a logic zero if and only if the binary number applied to its input is zero. This is a well-known logic circuit.
Block 27 is a multiple AND gate (the symbol & is used to distinguish it from multiplication). When input C is a logic 1 the binary number at its output equals that at its DATA input, otherwise the output is zero. This is also a well-known logic circuit.
Operation of the detector is as follows, referring to FIG. 1. A sequence of N samples from the PCM signal is applied at the point labelled PCM Samples In. If each sample is regarded as a floating-point number, then its value, V, is equal to:
where s, m, and c are certain bits in the sample as defined previously. However, the amplitude of the analog signal, V.sub.a, which was encoded to obtain this sample, is:
where V.sub.o is the scaling factor described earlier. This correspondence is dictated by the PCM encoding technique, which is well established. To correct for the displacement of -1, a floating-point number is generated whose sign s is opposite to that contained in the PCM sample, and whose fraction m and exponent c are zero. This is achieved by inverting the sign bit via NOT gate 28 and combining it with 7 binary zeros. This number is added, by adder 6, to the incoming PCM sample, and the value represented by the output of the adder, designated c(x), is:
or:
Therefore, this value represents the true analog voltage (appropriately scaled) encoded into the PCM sample. This is a combinational (non-time-dependent) process which is repeated on each PCM sample.
As each PCM sample appears at the output of Adder 6, Buffers 14 through 17 are pulsed by clock 25. This causes each sample to be gated into the next buffer (the last sample is lost). Therefore, at any time, the last N samples are stored in these buffers.
Counter 24 advances continuously after being reset. Let i represent the number of PCM samples received since counter 24 was last reset (0 .ltoreq. i < N). The value represented by the output of Buffer 14 is c(x.sub.i), and the value represented by the output of Read-only Memory 20 is a.sub.ii, both of which were defined earlier. These floating-point numbers are multiplied by Multiplier 1, the output of which represents the value a.sub.ii c(x.sub.i). Similarly, the output of Buffer 15 represents the value c(x.sub.i-1), and for i>1, the output of Read-only Memory 21 represents the value a.sub.i, i-1. Therefore, for i>1, the output of Multiplier 2 represents the value a.sub.i, i-1 c(x.sub.i-1). Similarly, for i>2, the output of Multiplier 3 represents a.sub.i, i-2 c(x.sub.i-2), and so on up to Multiplier 4. The outputs of these multipliers are added by Adders 7 through 9, and the output of Adder 9, designated w.sub.i, is therefore: ##EQU10## This quantity is multiplied by itself (squared) by Multiplier 5, and its sign is inverted by NOT gate 13. The quantity applied to the lower input of Adder 12 is therefore -w.sub.i.sup.2.
The PCM sample x.sub.i is also applied to Read-only Memory 19, and the output of the latter represents the quantity 1n[d(x.sub.i)], as defined previously. This quantity is applied to the upper input of Adder 12, the output of which is 1n[d(x.sub.i)]-w.sup.2. This quantity is added, by Adder 10, to the contents of Buffer 18, which was set to zero by AND gate 27 controlled by decoder 26, when counter 24 was equal to zero, i.e., before the first observed PCM sample. The above quantity is added to the total in Buffer 18 as each PCM sample is processed. Therefore, after N samples are processed, Buffer 18 will contain the quantity Q': ##EQU11## The following floating-point constant is hard-wired into the lower input of Adder 11:
where .vertline..LAMBDA..sub..beta..vertline. represents the determinant of the covariance matrix .LAMBDA..sub..beta. defined previously. Therefore, the output of Adder 11, designated Q, will be equal to: ##EQU12## This is mathematically equivalent to: ##EQU13## Let w be an N-dimensional column vector consisting of the numbers w.sub.1 through w.sub.N. It is a well-known mathematical fact that: ##EQU14## where w.sup.t represents the transpose of w and where .sup.. represents conventional matrix multiplication. Furthermore, let c(x) be an N-dimensional column vector consisting of the numbers c(x.sub.1) through c(x.sub.N). Then the earlier definition of w.sub.i for all values of i may be written thus
where A.sub..beta. is as defined earlier (note that A.sub..beta. was chosed to be lower-triangular, i.e., a.sub.ik = 0 for k > i). Therefore: ##EQU15## or: ##EQU16## and the output of Adder 11 is equal to: ##EQU17##
As shown in my dissertation, referred to above, the expression within the braces is the expression for the desired probability, P.sub.x .sub..beta., therefore;
Thus, the output of Adder 11 represents the natural logarithm of the desired probability, P.sub.x .sub..beta..
FIG. 1 is implemented separately for each possible combination of MF tones, i.e., for each value of .beta.. Typically, there are 15 possible combinations, plus the additional case of no tones at all (.beta.=0); therefore, FIG. 1 is repeated 16 times. As stated above, the contents of Read-only Memories 20 through 23 and the constant which is hard-wired into the lower input of Adder 11 are different for each of the sixteen implementations of FIG. 1. These numbers were determined from the covariance matrix .LAMBDA..sub..beta. associated with each MF-tone combination, .beta., with .LAMBDA..sub..beta. calculated as described in my dissertation, as mentioned above.
To determine the most-likely combination of MF tones (the most likely value of .beta.) which caused the observed sequence of PCM samples, x, it is only necessary to choose the value of .beta. which yields the highest value of P.sub.x .sub..beta., or, equivalently, the highest value of 1nP.sub.x .sub..beta.. A circuit for this purpose is shown in FIGS. 4 and 5.
Blocks 101 throgh 115 in FIG. 4 are 8-bit comparator circuits. The output of each such circuit is a logic 1 if and only if the value of 8-bit binary number applied to its lower input exceeds the value of the binary number applied to its upper input. Blocks 116 through 129 in FIG. 4, and blocks 150 through 156 in FIG. 5, are data selectors which are similar to block 71 in FIG. 3. If input a is a logic 0, then the binary bits at the output of a data selector are respectively equal to the bits applied to input 0, whereas if input a is a logic 1, then the output bits are equivalent to those applied to input 1. The data inputs and output of Selectors 116 through 129 contain eight bits; Selectors 150 through 153 contain one bit, Selectors 154 and 155 contain 2 bits, and Selector 156 contains three bits. All blocks contained in FIGS. 4 and 5 are well-known logic circuits.
Operation of the circuit is as follows. The outputs of the sixteen implementations of FIG. 1 (for the 16 MF-tone combinations being sought) are applied to the sixteen inputs of FIG. 4 labelled 1n P.sub.x 0 in through 1n P.sub.x 15 in. Comparator 101 compares 1n P.sub.x 0 with 1n P.sub.x 1, and its output is applied to Selector 116 which therefore "selects" the larger of these quantities and displays it at its output. Comparators 102 through 108, in conjunction with selectors 117 through 123, repeat this process on the numbers 1n P.sub.x 2 through 1n P.sub.x 15, in pairs of two, each selector selecting the larger of the two numbers. The reslting eight numbers are then compared in pairs of two, in the same manner, by Comparators 109 through 112, and the larger number of each pair is selected by the appropriate Selector in the group 124 through 127. The resulting four numbers are compared, and the larger of each pair selected, by Comparators 113 and 114, and by Selectors 128 and 129. Finally, the resulting two numbers are compared by Comparator 115, and its output determines which is larger.
The information about the relative magnitudes of 1n P.sub.x 0 through 1n P.sub.x 15 is contained in the outputs of Comparators 101 through 115. Each such output is applied to the circuit of FIG. 5, which converts these outputs to the binary representation of .beta.. Its operation is as follows. If the maximum value of 1n P.sub.x .sub..beta. occurs for .beta. .gtoreq. 8, then it will be on one of the lower eight inputs of FIG. 4, the number applied to the lower input of Comparator 115 will exceed that applied to the upper input, and its output will be a binary 1. Conversely, if the maximum occurs for .beta. < 8, then the output of Comparator 115 will be a binary 0. Therefore, this bit constitutes the high-order bit of the desired number, .beta.. The bit is designated b.sub.41 in FIGS. 4 and 5. By similar reasoning, it may be shown that the second-highest bit of .beta. is equal to b.sub.31 if .beta. < 8, or b.sub.32 if .beta. .gtoreq. 8. The appropriate bit (b.sub.31 or b.sub.32 ) is therefore selected by Selector 156 according to the state of b.sub.41. The third-highest bit of .beta. is equal to b.sub.21 if .beta. < 4, b.sub.22 if 4 .ltoreq. .beta. < 8, b.sub.23 if 8 .ltoreq. .beta. < 12, or b.sub.24 if .beta. .gtoreq. 12. Therefore, the appropriate one of these bits is selected, by Selectors 154 or 155, and 156, according to the states of b.sub.31 or b.sub.32, and b.sub.41. Finally, the lowest-order bit of .beta. is equal to one of the bits b.sub.11 through b.sub.18, and is selected, as above, according to the states of bit b.sub.21 or b.sub.22 or b.sub.23 or b.sub.24, bit b.sub.31 or b.sub.32, and bit b.sub.41. The binary number resulting from these 4 bits constitutes the desired value of .beta. which yields the highest value of 1n P.sub.x .sub..beta.. This completes the detection process.
The case illustrated here assumes that all tone combinations are symmetrical, i.e., that the average usage of all combinations are equal. It is possible, however, that some combinations are used more frequently than others. Then the well-known Bayes rule implies that the likelihood of error is reduced if the heavily-used combinations are weighted more heavily before comparison.
This requires that each probability, P.sub.x .sub..beta. be multiplied by a constant, designated P.sub..beta., and then the products compared to determine the maximum. Each constant P.sub..beta. is equal to the relative occurrence of the tone combination .beta.. For example, if .beta.=2 occurs twice as often as .beta.=3, then P.sub.2 would be twice as large as P.sub.3. It is a known fact that this tends to reduce the average error.
The required constant P.sub..beta. is multiplied by P.sub.x .sub..beta. simply by adding its logarithm to Q, since 1n(P.sub.x .sub..beta..sup.. P.sub..beta.)=Q + 1n P.sub..beta..
Thus, the weighting factor 1n P.sub..beta. is included simply by hard-wiring a different constant (the old constant increased by 1n P.sub..beta.) to the lower input of Adder (11), and the operation of the circuit is unchanged. This constant may also be selected to satisfy other decision rules (such as the Neymann-Pearson rule, which is also well-known).
The component blocks contained in the figures, except where stated otherwise, are well-known circuits and are available in monolithic form. In some cases, multiple blocks may be combined into a single package; in other cases, two or more packages may be required to implement a single block. In all cases, the division of the blocks is functional and the functions are described in various literature.
The following list of standard logic circuits has been found satisfactory in implementing the invention although they should not be interpreted as design limiting or optimum but only as illustrative:
Whereas the preferred embodiment of the invention has been shown and described herein, it should be realized that there may be many modifications, substitutions and alterations thereto without departing from the teachings of the invention.
Claims
Having described what is new and novel and desired to secure by Letters Patent, what is claimed is:
1. A pulse code modulation (PCM) tone receiver for determining the probability that a particular combination of audio frequencies was transmitted by monitoring PCM samples, said PCM tone receiver comprising: means for storing N PCM samples as received, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; first means for multiplying said N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where i is a fixed point binary number ranging from 1 to N and where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the particular tone combination to be detected, said first multiplying means including means for storing said fixed predetermined constants a.sub.il through a.sub.iN, said first multiplier means operating on said stored output of said storage means; means for combining said multiplied products of samples c.sub.1 through c.sub.N and constants a.sub.il through a.sub.iN according to the equation ##EQU18## means for squaring said resulting combined w.sub.i term; means for accumulating the resulting w.sub.i.sup.2 term as each of said N PCM samples are received; second means for multiplying said accumulated samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted.
2. The PCM tone receiver as recited in claim 1 further characterized in that said fixed constants in said second multiplier means is modified by a weighting factor based on the average usage of each tone combination.
3. A pulse code modulation (PCM) tone receiver for determining the probability that a particular combination of audio frequencies was transmitted by monitoring PCM samples, said PCM tone receiver comprising: means for storing N PCM samples as received, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; first means for multiplying said N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where i is a fixed point binary number ranging from 1 to N and where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the particular tone combination to be detected, said first multiplying means including means for storing said fixed predetermined constants a.sub.il through a.sub.iN, said first multiplier means operating on said stored output of said storage means; means for combining said multiplied products of samples c.sub.l through c.sub.N and constants a.sub.il through a.sub.iN according to the equation ##EQU19## means for squaring said resulting combined w.sub.i term; weighting means for subtracting said squared term w.sub.i.sup.2 from a weighting factor f(x), said weighting factor determined by the magnitude of the quantizing increment of the PCM quantization process for converting the sampled analog waveform to the received PCM samples; means for accumulating the resulting f(x)-w.sub.i.sup. 2 term as each of said N PCM samples are received; second means for multiplying said accumulated samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted.
4. A Pulse Code Modulation (PCM) tone receiver apparatus for determining the probability that a particular combination of audio frequencies was transmitted, said tone receiver apparatus comprising: a plurality of PCM tone receivers, each of said plurality of PCM tone receivers comprises: means for storing N PCM samples as received, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; first means for multiplying said N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where i is a fixed point binary number ranging from 1 to N and where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the particular tone combination to be detected, said first multiplying means including means for storing said fixed predetermined constants a.sub.il through a.sub.iN, said first multiplier means operating on said stored output of said storage means; means for combining said multiplied products of samples c.sub.l through c.sub.N and constants a.sub.il through a.sub.iN according to the equation ##EQU20## means for squaring said resulting combined w.sub.i term; means for accumulating the resulting w.sub.i.sup.2 term as each of said N PCM samples are received; and second means for multiplying said accumulated samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted, each of said plurality of PCM tone receiver detecting the probability that a different particular combination of audio frequencies was transmitted; and combinational means for indicating which one of said plurality of specific tone combinations was most likely transmitted by combining said probability outputs of each of said plurality of PCM tone receivers.
5. The PCM tone receiver apparatus as recited in claim 4 further characterized in that said combinational indicating means includes comparator means for comparing the relative magnitude of said plurality of resultant probability products.
6. A method for statistically estimating the probability that a specific combination of audio frequencies was transmitted in a Pulse Code Modulation (PCM) format signal, comprising the steps of: storing N samples, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; multiplying said set of N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where i is a fixed point binary number ranging from 1 to N and where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the particular tone combination to be detected and adding the products according to the equation ##EQU21## squaring the resulting w.sub.i terms; processing the resulting squared term w.sub.i.sup.2 through accumulator means as each sample is received; multiplying said squared term samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted.
7. A method for statistically estimating the probability that a specific combination of audio frequencies was transmitted in a Pulse Code Modulation (PCM) format signal, comprising the steps of: storing N samples, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; multiplying said set of N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the particular tone combination to be detected and adding the products according to the equation ##EQU22## squaring the resulting w.sub.i terms; subtracting the squared term w.sub.i.sup.2 from a weighting factor f(x), said weighting factor determined by the magnitude of the quantizing increment of the PCM quantization process converting the sampled analog waveform to the received PCM samples; processing the resulting squared term f(x)-w.sub.i.sup.2 through accumulator means as each sample is received; multiplying said squared term samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted.
8. A method for statistically determining which specific one of several combinations of audio frequencies was most likely transmitted in a Pulse Code Modulation (PCM) format signal, comprising the steps of: a. storing N samples, where N is an integer, c.sub.l through c.sub.N representing a quantization of the analog voltage waveform sampled; b. multiplying said set of N samples represented by c.sub.l through c.sub.N by a set of fixed predetermined constants a.sub.il through a.sub.iN, where i is a fixed point binary number ranging from 1 to N and where a.sub.il through a.sub.iN are determined from the covariance matrix of the process represented by the paticular tone combination to be detected and adding the products according to the equation ##EQU23## c. squaring the resulting w.sub.i terms; d. processing the resulting squared term w.sub.i.sup.2 through accumulator means as each sample is received; e. multiplying said squared term samples by a set of fixed constants related to the covariance matrix with the resulting product representing the probability that the specific combination of audio frequencies was transmitted; f. repeating steps (a) - (e) for each of said several combinations of audio frequencies to obtain for each a resulting probability product; g. comparing said plurality of resulting probability products, said comparing step indicating which of said plurality of probability products represented by a binary number is maximum representing which specific one of said several combinations of audio frequencies was most likely transmitted.
Patent Citations (3)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3710028 | 1973-01-01 | Pitroda | |
| US3803390 | 1974-04-01 | Schaepman | |
| US3824471 | 1974-07-01 | Mills |
Non-Patent Literature (1)
- Modestino & Davisson "Adaptive Detection of Weak Signals in Statistically Undefined Noise Backgrounds" Symposium on Computer Processing in Communications Polytechnic Institute of Brooklyn, Apr. 8-10, 1969, pp. 629-651.