Related Inventions

The present invention is related to the following inventions which are assigned to the same assignee as the present invention:

(1) "Method and System for Demodulation of Multi- Level PCM", having Serial No. 08/435,365, filed on May 5, 1995.

(2) "Neural Network and Method of Using Same", having Serial No. 08/076,601, filed June 14, 1993.

(3) "Method of Programming a Polynomial Processor" having Serial No. 08/358,278, filed December 19, 1994 The subject matter of the above-identified related inventions is hereby incorporated by reference into the disclosure of this invention.

Technical Field

The present invention relates generally to demodulation methods and systems and, in particular, to a methods and systems for demodulation which are capable of learning conditions for a particular communication channel,

Background of the Invention

Digital modulation techniques are widely used in communication systems today. These digital systems offer the advantages of greater noise immunity, greater versatility and higher efficiency than many of their analog predecessors. The heart of these digital communication systems is the demodulator — the portion of the system which converts the waveforms representative of the digital information conveyed by these systems, into the digital information itself.

Many prior art systems use either matched filtering or correlation to demodulate the digital waveforms. These techniques are complex, yet they can be shown to be optimal under certain conditions such as Gaussian noise. Unfortunately, many actual noise conditions do not statistically conform to the Gaussian noise assumption. Therefore a need exists for a demodulation methods and systems that can conform to differing noise conditions.

Brief Description of the Drawings

The invention is pointed out with particularity in the appended claims. However, other features of the invention will become more apparent and the invention will be best understood by referring to the following detailed description in conjunction with the accompanying drawings in which:

FIG. 1 presents a block diagram representation of one embodiment of the present invention. FIG. 2 presents an example waveform corresponding to a stream of information bits modulated by multi-level PCM.

FIG. 3 presents a flowchart representation of one embodiment of the present invention.

FIG. 4 presents a flowchart representation of a method of one embodiment of the present invention.

FIG. 5 presents a block diagram representation of a method in accordance with one embodiment of the present invention.

FIG. 6 presents an example waveform corresponding to a stream of information bits modulated by m-ary signaling.

FIG. 7 presents a flowchart representation of a method in accordance with one embodiment of the present invention.

FIG. 8 shows a schematic representation of the polynomial processor in accordance with one embodiment of the present invention.

FIG. 9 shows a flow chart representation of a method of training the coefficients for a processor in accordance with one embodiment of the present invention.

FIG. 10 presents a graphical representation of an example waveform used to determine the processor coefficients in accordance with one embodiment of the present invention.

FIG. 11 presents a graphical representation of an example waveform used to demonstrate the training of the polynomial coefficients in accordance with a further embodiment of the present invention.

Detailed Description of the Preferred Embodiments

The present invention provides a demodulation method and system for use in a communication system which is susceptible to noise in the communication link. The various embodiments of the present invention are capable of learning and adapting to the modulation employed and demodulating in a fashion which is robust — that is capable of operating effectively in the presence of high degrees of noise which may or may not conform to Gaussian statistics. In particular, nonlinear mathematics and parallel computation can be employed in a polynomial processor to provide the features described above.

Specific embodiments of the present invention which are directed toward multi-level PCM and M-ary signally are described in detail in the paragraphs which follow.

FIG. 1 presents a block diagram representation of one embodiment of the present invention. This embodiment presents a system 10 for demodulating a waveform corresponding to a stream of information bits modulated by multi-level PCM. Receiver 12 receives the waveform to form a received signal. Sampler 14, in communication with the receiver 12, receives the received signal and samples

the received signal at a plurality of discrete times to form a sequence of received samples. Processor 16, in communication with the sampler 14, receives the received samples from the sampler 14 and processes the received samples to form an output sequence having a plurality of output values, each output value being a polynomial function of at least one of the received samples; wherein each output value represents a respective level of the multi-level PCM corresponding to one or more binary information bits.

System 10 further includes a trainer 18, coupled to the processor and responsive to a plurality of demodulation data for determining a value for each of the plurality of polynomial coefficients by fitting the polynomial function to the plurality of demodulation data. In one embodiment of the present invention, the demodulation data includes a sequence of training samples that represent a sample sequence of received samples, and a sequence of desired output values, each desired output value corresponding to at least one of the sequence of training samples.

An example of the operation of the embodiment of the present invention illustrated by FIG. 1 can be described as follows.

FIG. 2 presents an example waveform corresponding to a stream of information bits modulated by multi-level PCM. Waveform 30 represents a segment of 8-level PCM. Three bits of information are transmitted for each period T. The originally transmitted waveform (not shown) more closely corresponded to levels 5, 3, and 4 respectively for three consecutive time periods. The waveform 30 is corrupted by the noise present in the communication channel.

Waveform 30 is received by receiver 12 and sampled by sampler 14 at four discrete times per period T. While a sampling frequency of 4/T is shown, it should be understood by those skilled in the art that greater or lessor frequencies could advantageously be employed in other circumstances, however the sampling frequency must be at least greater than 1/T. In a preferred embodiment, the sampler consists of an analog to digital (A/D) converter. Thus, the sequence of received samples 32 correspond to a sequence of digital words. For the sake of simplicity, this sequence of received samples can be represented by (X(l), X(2), X(3), . . . X(n), X(n+1), . . .) .

Processor 16 calculates a sequence of output levels as polynomial function of a finite number (at least one) of the sequence of received samples. If the sequence of output levels is represented by (Y(l), Y(2), Y(3), . . . Y(n), Y(n+1), . . .), then the a general output level in the sequence Y(n) can be represented as follows:

m Y(n) = wi-i (X(l)9li.X(2)92i. . . . -X(p)9 _P i) (1) i=l where m is an integer which represents the number of terms in the polynomial, p is an integer that represents the number of past inputs considered (effectively the window-size for the polynomial in time) , gji represents the exponent of X(j) in the ith term and wi-i is the coefficient of the ith term.

In an alternative embodiment of the present invention, the processor 16 includes a truncation function which generates the output levels by truncating an analog polynomial function value. Thus, if Y(n) are real valued.

the actual output values of the processor 16 are values Y' (n) which are truncated or otherwise quantized to the m levels of the modulation scheme. In a further alternative embodiment of the present invention, the processor 16 further includes a decoder for translating the output levels at a plurality of discrete times into their corresponding binary value.

FIG. 3 presents a flowchart representation of one embodiment of the present invention. This flowchart represents a method used in conjunction with the system of FIG. 1. Step 40 includes receiving the waveform to form a received signal. The received signal is sampled at a plurality of discrete times to form a sequence of received samples as shown in step 42. The received samples are processed to form an output sequence having a plurality of output values as shown in step 44, each output value being a polynomial function of at least one of the received samples; wherein each output value represents a respective level of the multi-level PCM corresponding to one or more binary information bits.

FIG. 4 presents a flowchart representation of a method of one embodiment of the present invention. This method is also used in conjunction with the system of FIG. 1. Steps 50 - 54 correspond to steps 40 - 44 of FIG. 3. Step 56 includes determining a value for each of the plurality of coefficients by fitting the polynomial function to a plurality of demodulation data.

FIG. 5 presents a block diagram representation of a method in accordance with one embodiment of the present invention. This figure illustrates a system for demodulating a waveform, the waveform corresponding to a stream of information bits modulated by an m-ary signaling technique. The system includes a receiver 60 for receiving

the waveform to form a received signal. This received signal is fed to a sampler 62, which samples the received signal at a plurality of discrete times to form a sequence of received samples. The sequence of received samples is, in turn, fed to a processor 74 for processing the received samples in a plurality of signal classifiers 64 - 68, each signal classifier forming an classifier sequence having a plurality of classifier values, each classifier value corresponding to one of the plurality of discrete times, each classifier value being a polynomial function of at least one of the received samples.

Each of the classifier sequences are fed to a comparator 70 in communication with the processor 74. The comparator 70 compares, at each of the plurality of discrete times, a magnitude of the classifier value for each of the plurality of signal classifiers. A generator 72, coupled to the comparator, generates an output value corresponding to each of the plurality of discrete times based on the magnitude of at least one of the classifier values.

In one embodiment of the present invention, the polynomial function for each of the plurality of signal classifiers includes a plurality of coefficients and the system further includes a trainer 76, coupled to the processor and responsive to a plurality of demodulation data. The trainer determines a value for each of the plurality of coefficients for each of the plurality of signal classifiers by fitting each polynomial function to the plurality of demodulation data.

In one embodiment of the present invention, the comparator determines, for each discrete time, which of the plurality of classifiers has a classifier value with the greatest magnitude. In this embodiment, each of the

signal classifiers is trained to recognize one of the m- signals that could be transmitted by the transmitter. In turn, the output value corresponds to a determination of which of the plurality of classifiers had the greatest magnitude—therefore indicating that the corresponding signal is most likely to have been transmitted.

An example of the operation of the embodiment of the present invention illustrated by FIG. 5 can be described as follows.

FIG. 6 presents an example waveform corresponding to a stream of information bits modulated by m-ary signaling. Waveform 80 represents a received signal of 4-ary signaling. For each time period T, one of four possible signals 82-88 are transmitted representing 2 bits of information. In this case, the originally transmitted waveform, signal 86 is corrupted by the noise present in the communication channel 90. While the process of carrier modulation is not shown, one of ordinary skill in the art will recognize that any of a wide variety of carrier modulation schemes could be used in conjunction with the present invention. Further, the signals 82-88 are presented solely to illustrate the operation of the present invention. One of ordinary skill in the art will recognize that any of a wide variety of m-ary signaling schemes incorporating signals of differing shape, spectrum, frequency, phase, and/or amplitude could be employed in conjunction with the method and system of the present invention.

Waveform 80 is received by receiver 60 and sampled by sampler 62 at eight discrete times per period T. While a sampling frequency of 8/T is shown, it should be understood by those skilled in the art that greater or lessor frequencies could advantageously be employed in

other circumstances, however the sampling frequency must be at least greater than 1/T. In a preferred embodiment, the sampler consists of an analog to digital (A/D) converter. Thus, the sequence of received samples 82 correspond to a sequence of digital words. For the sake of simplicity, this sequence of received samples can be represented by (X(l), X(2), X(3), . . . X(n), X(n+1), . . .) .

Processor 74 calculates a sequence of output levels as polynomial function of a finite number (at least one) of the sequence of received samples for each of the plurality of signal classifiers. If the sequence of output levels for the kth signal classifier is represented by (Yk(l), Yk(2), Yk<3), . . . Yk<n), Yk(n+1), . . .), then the a general output level in the sequence (n) can be represented as follows:

m Yk(n) ^« J ki-l(X(l)9ii ^« X(2)g2i ^» . . . •X(p)9p±k) (2) i=l where m is an integer which represents the number of terms in the polynomial, p is an integer that represents the number of past inputs considered (effectively the window-size for the polynomial in time) , gjik represents the power of X(j) in the ith term and the kth signal classifier and wki-l is the coefficient of the ith term and the kth signal classifier.

In a preferred embodiment of the present invention, the number of signal classifiers corresponds to the number of possible signals to be sent. Thus, in a 4-ary signaling system as illustrated in FIG. 6, four signal classifiers are used — each signal classifier trained to recognize one of the possible signals to be sent. As waveform 80 is processed, the outputs Y3(l) - Y3(8)

(corresponding to the third signal classifier) are greater than the outputs of the other classifiers since this classifier has been trained to recognize the signal 86 which was the signal that was transmitted during this period of time.

In a preferred embodiment of the present invention, a weighted sum is calculated for each classifier output over a time period T, (Yfc(n) , Yk(n+1), . . ., Yk(n+p-l)). These weighted sums are compared to determine the classifier output whose output is greatest. However, other schemes such as voting, the summing of rank transformed outputs, the summing of normal-scores transformed outputs or the use of parametric statistical techniques, could also be used to determine, for each time period T the classifier with the dominant output.

FIG. 7 presents a flowchart representation of a method in accordance with one embodiment of the present invention. This method is advantageously used in conjunction with the system presented in FIG. 5. The method includes the step of determining a value for each of the plurality of coefficients by fitting the polynomial function to a plurality of demodulation data as shown in step 100. A waveform is received as shown in step 102 in order to form a received signal. The received signal.is sampled as shown in step 104 at a plurality of discrete times to form a sequence of received samples.

The received samples are processed in a plurality of signal classifiers as shown in step 106, each signal classifier forming an classifier sequence having a plurality of classifier values, each classifier value corresponding to one of the plurality of discrete times, each classifier value being a polynomial function of at least one of the received samples. A magnitude of each of

the plurality of classifier values is determined for each of the plurality of signal classifiers as shown in step 108. In addition, an output value is generated, corresponding to each of the plurality of discrete times, based on the magnitude of at least one of the classifier values as shown in step 110. In one embodiment of the present invention, step 110 includes the substep of determining, for each discrete time, which of the plurality of classifiers has a classifier value with the greatest magnitude.

FIG. 8 shows a schematic representation of the polynomial processor in accordance with one embodiment of the present invention. Polynomial processor 190 can be used in the implementation of either the processor 16 or each signal classifier for the processor 74. This processor 190 generates output signals as a polynomial function of one or more input signals. A plurality of input signals, xi, X ₂ , . . ., x _n are fed to input nodes 176, 178, . . . 180 of an input layer. The output of each input node 176, 178, . . . 180 in the input layer is distributed to at least one processing element of a hidden layer (of which only processing elements 182, 184, 186 are shown) . Each processing element applies a gating function (exponent) to each of the control inputs to produce a corresponding gated input. Any given processing element may apply a different gating function to each different input it receives. For example, processing element 182 applies a gating function (911) to the input it receives from input node 176; it applies a gating function (g2i) to the input it receives from input node 78; and so forth. The gated inputs are multiplied together by a multiplier in the processing element to form a product, which is then multiplied by a coefficient wj _. -ι to form the ith term of the polynomial. The ith term of the polynomial is added to the other, similarly calculated, terms by summer 188 to produce the output y.

For example, in FIG. 8 processing element 182, which happens to be responsible for generating the first polynomial term, multiplies its gated inputs together to form a product (which happens to be one because in this case the gating functions gn, g21/ • • • 9nl ^are all 0) , which is multiplied by a coefficient w ₀ to produce a corresponding output w ₀ . Processing element 184, which happens to be responsible for generating the wi xi term of the polynomial, multiplies its gated inputs together to form a product (which happens to be xi because in this case the gated functions are all 0 except for the gating function that is applied to the i output of the input node 176) , which is multiplied by a coefficient wi to produce a corresponding output i w]_. In like fashion, processing element 186 produces an output w _n -ι xi to the power of gin, X2 to the power of g2n _/ • • • , xn to the power of gnN- The outputs of processing elements 182, 184, . . . 186 are summed together by a suitable summing means or function, such as summer 188, in an output layer to produce the output signal y of the processor as follows:

m y = Σ wi-i xχ9li 2^2i . . . x _n 9ni (3) i=l

where m is an integer which represents the number of terms in the polynomial.

While processor 190 has been described to fulfill the functions ascribed to processors 16 and 74, one of ordinary skill in the art will recognize that, in certain embodiments of the present invention, processor 190 would serve merely as a co-processor which performs the polynomial calculations called for by processors 16 and 74. An additional processing element, such as a conventional microprocessor can be used in conjunction

with processor 190 to provide additional functionality. In an alternative embodiment of the present invention, processors 16 and 74 are implemented without the use of a processor such as processor 190. In this instance, a traditional processor, such as a digital signal processor or microprocessor, with or without a traditional math co¬ processor, is employed.

FIG. 9 shows a flow chart representation of a method of training the coefficients for a processor in accordance with one embodiment of the present invention. First, regarding box 169, the demodulation data are provided. Next, regarding box 170, the number of data is compared with the number of coefficients. Regarding decision box 171, if the number of data equal the number of coefficients, the procedure goes to box 172 which indicates that a matrix inversion technique is used to solve for the initial value of each coefficient. If, on the other hand, the number of data is not equal to the number of coefficients, the procedure goes to box 173, which indicates that a least squares estimation technique is used to solve for the initial value of each coefficient.

While a preferred embodiment is described herein, one with ordinary skill in the art will recognize that other suitable estimation techniques, for example, extended least squares, pseudo inverse, Kalman filtering techniques, maximum likelihood techniques, Bayesian estimation, polynomial splines, and alike, could likewise be used to fit the polynomial to the demodulation data.

FIG. 10 presents a graphical representation of an example waveform used to determine the processor coefficients in accordance with one embodiment of the present invention. More particularly, FIG. 10 will be used to illustrate the operation of the method of FIG. 9 in the trainer 18. Waveform 200 represents a segment of 8-level

PCM. The demodulation data used to determine the coefficients of the polynomial function in processor 16 includes a sequence of training samples 202, X(n), that represent an example sequence of received samples. The demodulation data further includes a sequence of desired output values 204, Y(n), each desired output value corresponding to at least one of the sequence of training samples. Thus, given the input and output values for the polynomial function, the coefficients of the polynomial can be determined based on the curve-fitting techniques previous discussed and/or presented in Related Invention #3.

While the example waveform 200 is shown to be relatively noiseless, in an alternative embodiment of the present invention, actual received data such as data produced in the presence of noise can also be used to train the processor. In this fashion, the actual operating conditions of the demodulation method and system can be more closely approximated during the training phase of the system.

FIG. 11 presents a graphical representation of an example waveform used to demonstrate the training of the polynomial coefficients in accordance with a further embodiment of the present invention. FIG. 11 will be used to demonstrate the operation of the system of FIG. 5 and specifically trainer 76. Waveform 210 represents a segment of 4-ary signaling in relation to the example discussed in conjunction with FIG. 6. The demodulation data used to determine the coefficients of the polynomial function in processor 74 includes a sequence of training samples 212, X(n), that represent an example sequence of received samples. The demodulation data further includes a sequence of desired classifier values, each desired

classifier value corresponding to at least one of the sequence of training samples.

The sequences of desired classifier values 214, 216, 218, and 220, corresponding to desired values for Yi (n) , Y2 (n) , Y3 (n) and Y4 (n) and to classifiers for classifying signals 82, 84, 86, and 88, respectively. Thus, given the input and output values for the polynomial function, the coefficients of the polynomial can be determined based on the curve-fitting techniques presented in Related

Invention #3. In this fashion, the classifier trained with training samples 212 and desired classifier sequence 214 will be trained to recognize the signal 82, the classifier trained with training samples 212 and desired classifier sequence 216 will be trained to recognize the signal 84 . . . etc.

While the example waveform 210 is shown to be relatively noiseless, in an alternative embodiment of the present invention, actual received data such as data produced in the presence of noise can also be used to train the processor. In this fashion, the actual operating conditions of the demodulation method and system can be more closely approximated during the training phase of the system.

One of ordinary skill in the art will recognize that the various embodiments of the present invention described herein can be implemented with a custom integrated circuit, a programmable logic array, application specific integrated circuit (ASIC) , other digital logic device or an analog circuit equivalent. In addition, software running on a processor such as a microprocessor could also be used to implement the various systems and methods described herein.

While specific embodiments of the present invention have been shown and described, it will be apparent to those skilled in the art that the disclosed invention may be modified in numerous ways and may assume many embodiments other than the preferred form specifically set out and described above.

Accordingly, it is intended by the appended claims to cover all modifications of the invention which fall within the true spirit and scope of the invention.

What is claimed is: