Constellation design for modem receiver

This application claims the benefit of U.S. Provisional Application No. 60/122,596, filed Mar. 3, 1999.

This invention relates to improvements in channel modeling and constellation design for modems. Particularly, the invention concerns apparatus and methods for enhancing the operation of a PCM modem receiver.

FIG. 9 illustrates elements of a typical communication system. The communication system includes a transmitter, a receiver, and a connecting medium called a channel. The transmitter prepares and sends data down the channel, and the receiver reflects the inverse operations of those in the transmitter in order to recover the transmitted data. In modem design, such as Pulse Code Modulation (i.e. “PCM”), the channel can include noise. For instance, the channel can include digital impairment and an additive independent noise “n”. Under all current modem design, the noise is considered independent of the signal transmitted by the transmitter.

The noise n is a continuous random variable with a probability density function f n (a). As a result, the received random variable Y is also of the continuous type. For a particular observed value, say Y(k), assume that the receiver determines the transmitted message is t(i). Then, the conditional probability of correct detection is just the probability that t(i) was actually transmitted given that Y(k) is observed. According to well known probability theory, the decision rule is to set the receiver output to t(i) if and only if:

P[t ( i )/ Y=Y ( k )]=max n {P[t ( n )/ Y=Y ( k )]} for all n.

Thus, the optimum receiver is a probability processor. The optimum receiver computes the a posteriori probability given Y=Y(k) for all messages in the set and decides on the message with the largest computed a posteriori probability.

Further communication theory has demonstrated that functionality of the probability processor can be simplified for channels with arbitrary signal and noise statistics. In particular, receivers in the prior art assume that noise is independent of the signal characteristics. Under these circumstances, known receivers are designed according to a minimum distance criteria. In other words, the receiver decides on the message t(i) whose voltage level is closest to the received voltage level Y; this is referred to as minimum distance decoding.

FIG. 10 illustrates the minimum distance criteria as typically implemented. The transmitted signal levels are shown on the left, the received signal levels are shown on the right, and the digital impairment is shown between the transmitted and received signal levels. Under this deterministic communication system, each transmitted level is mapped onto a received signal level by the receiver. Received signal voltages that don't exactly line-up with a received signal level are mapped onto the closest signal level under minimum distance decoding.

FIG. 11 further illustrates an exemplary constellation design for a receiver using minimum distance decoding. When a communication system transmits “i” equally likely messages, the received voltage when the i th message is transmitted is Y=s(i)+n. Under minimum distance decoding the receiver chooses a message t(i) whose voltage level is closest to the received voltage level Y. Hence, if Y is less than Δ/2 then the receiver decides t 1 ; if Δ/2<Y<3Δ/2 then the receiver decides t 2 ; if 3Δ/2<Y<5Δ/2 then the receiver decides t 3 , etc. As illustrated by this example, the known constellation designs in a receiver include a constant range for each possible message level. With particular reference to minimum distance decoding, each possible message level has a constant range Δ.

FIG. 12 shows an example of the conditional probability density functions (i.e. “pdf”) for the different transmitted messages t 1 –t 4 . The probability density functions for each message do not end at the boundaries between messages t 1 –t 4 , rather the pdfs overlap. The overlapping of the pdfs gives rise to errors in the minimum distance decoding receiver of FIG. 11 . In particular, a receiver can decide that message t 3 was transmitted when message t 4 was actually transmitted. These errors in the minimum distance decoding receiver can arise because current models assume that noise in the channel is independent of signal strength.

Accordingly, there is a need for a receiver that accounts for the interrelationship between noise in the channel and the transmitted signal.

Errors in the receiver may be reduced, according to the invention, with a receiver having a processor that generates a set of thresholds and having a comparator. The processor generates a minimum threshold and a maximum threshold representing a variable range for each of a plurality of possible message levels. The comparator identifies the message by comparing the received signal with the generated minimum and maximum thresholds.

Another embodiment of the invention provides for a method of forming a constellation design having a predetermined number of “i” message levels. The constellation design forms part of a receiver that identifies a transmitted message based upon a received signal. The inventive method includes determining a minimum threshold and a maximum threshold that represent a variable range for each of a plurality of possible signal levels, and calculating a distance d(i) between possible signal levels. The calculated distance d(i) is based upon the determined minimum and maximum thresholds.

The invention also provides for a method of identifying a message based upon a received signal. The method includes steps of receiving the signal, generating thresholds, and identifying the message by comparing the received signal with the generated thresholds. The generated thresholds include a minimum threshold and a maximum threshold that represent a variable range for each of a plurality of possible message levels.

The features and advantages of the invention will be apparent from the following description, as illustrated in the accompanying Figures in which like reference characters refer to the same elements throughout the different views:

FIG. 1 is block diagram of a receiver in accordance with the invention;

FIG. 2 is a block diagram of a communication system incorporating the receiver of FIG. 1 ;

FIG. 3 illustrates the distribution function of the received data y(i) of FIG. 2 ;

FIG. 4 shows an exemplary set of probability density functions utilized by the receiver of FIG. 1 ;

FIG. 5 shows another exemplary set of probability density functions utilized by the receiver of FIG. 1 ;

FIG. 6 graphically illustrates the constellation design of the receiver of FIG. 1 ;

FIG. 7 is a flow chart for generating a constellation design according to the invention;

FIG. 8 shows a flow chart for identifying a message based upon a received signal;

FIG. 9 is a block diagram of a known telecommunication system;

FIG. 10 illustrates a known minimum distance criteria;

FIG. 11 shows the constellation design for a known minimum distance criteria receiver; and

FIG. 12 shows a probability density function for a known receiver.

FIG. 1 is a block diagram of a receiver 10 for identifying a transmitted message. FIG. 2 illustrates that the receiver 10 can be part of a communication system 20 , such that the receiver 10 can identify a transmitted message t(i) based upon a received signal Y. As further shown in FIG. 1 , the receiver 10 includes a processor 12 and a comparator 14 . The processor 12 generates a minimum threshold and a maximum threshold that form part of a constellation design. FIG. 6 shows a constellation design formed by the processor 12 of FIG. 1 . The illustrated constellation design includes a minimum threshold Ymin(i) and a maximum threshold Ymax(i). The minimum and maximum thresholds represent a variable range for each of a plurality of possible message levels. The comparator 14 identifies the transmitted message by comparing the received signal Y with the generated minimum and maximum threshold signals from the processor 12 .

With further reference to FIG. 1 , the processor 12 receives signal Y as an input and generates the threshold signals. Further details on generation of the constellation design and the threshold signals are described hereinafter. The threshold signals are received by comparator 14 . Comparator 14 then determines, based upon the threshold signals and the received signal Y, the best estimate for the transmitted signal t(i). For example, comparator 14 identifies where the received signal Y lies along the x-axis of FIG. 6 , relative to the decision regions t 1 –t 4 . Once a decision region is identified, the comparator outputs the signal M based upon the decision region identified. Signal M represents the receiver's best estimate for the transmitted signal.

Processor 12 and comparator 14 can both be formed using electronic circuitry, software instructions executed on a processor, or a combination of circuitry and software. In another aspect of the invention, processor 12 and comparator 14 can be an integral processing block. Particularly, the functions of processor 12 and comparator 14 can be performed by a digital signal processor or micro-processor executing software instructions.

FIG. 2 shows a block diagram of a new communication system 20 incorporating the receiver 10 of FIG. 1 . In comparison, a block diagram of a known communication system is illustrated in FIG. 9 . The prior art communication system assumes that noise is independent from the transmitted signal. However, the inventors have discovered that noise is not independent from signal, rather some noise is interrelated with the signal strength being transmitted. From this it follows that different signal levels have different noise properties. This concept is illustrated in FIG. 2 .

In particular, communication system 20 includes a transmitter 22 , a digital impairment block 24 , a first summer 26 , a coherent noise block 28 , a second summer 30 , an independent noise block 32 , and the receiver 10 . The digital impairment block receives the transmitted signal t(i) from the transmitter 22 . The first summer 26 , then sums the output signal s 1 ( i ) from the digital impairment block with the output from the coherent noise block, to form the signal s(i). The second summer then sums the signal s(i) with the output signal n from the independent noise block 32 , to generate the signal Y. The receiver 10 generates the output signal M in response to the received signal Y.

The inventor's research demonstrated that the digital impairment block 24 is a non-linear re-mapping that is dependent on the transmitted signal level. Coherent noise block 28 is typically Gaussian random noise caused by the CODEC operation or quantization of the transmitted signal t(i). The inventor's research has also shown that the coherent noise block has a variance that is dependent upon the transmitted signal level t(i). Accordingly, the received signal Y is a random Gaussian process that is dependent upon the transmitted signal level. Since the received signal Y is a random process, the received signal is not a deterministic function as conventional channel modeling teaches.

FIG. 3 is an exemplary bar chart showing the distribution function of the received data Y of FIG. 2 . The left side of FIG. 3 shows four different transmitted signals, the right side of FIG. 3 shows four different received signals, and a channel is illustrated between the transmitted and received signals. The figure illustrates that the received signal is not deterministic data. Rather, the received signal Y is random data with a particular distribution function. The distance between signal levels, identified as d 1 , d 2 and d 3 , also varies. Accordingly, a probability function is preferably used to express the event that the received signal equals a particular message level, and a probabilistic function is preferably used to express the distance between message levels. In comparison, as shown in FIG. 10 , conventional channel modeling teaches that the received signal levels and the distance between signal levels are deterministic. Conventional channel modeling does not teach that the received signal level is best represented by a range of values and that the range of values for each particular signal level may vary.

FIG. 4 shows an exemplary probability density function for Y as utilized by the receiver 10 of FIG. 1 . FIG. 4 illustrates that the received signal Y is randomly distributed data. The received signal data is divided into two curves, one labeled f Y [y(k)/t(i)] and another labeled f Y [y(k)/t(i+1)]. The curve labeled f Y [y(k)/t(i)] represents the probability that message y(k) was received given that t(i) was transmitted, and the curve labeled f Y [y(k)/t(i+1)] represents the probability that message y(k) was received given that t(i+1) was transmitted.

The curves of FIG. 4 also illustrate the definitions of the minimum threshold Ymin, the maximum threshold Ymax, Lmse(i), distance d(i), and Lev(i).

In particular for an i th PCM level, Ymin(i) represents the minimum threshold of a range of received values that cause the receiver 10 to estimate that message t(i) was transmitted. Ymax(i) represents the maximum threshold of a range of values that cause the receiver 10 to estimate that message t(i) was transmitted. Together, Ymin(i) and Ymax(i) form a range of values representing that message t(i) was transmitted.

The “i+1” PCM level has a distinct set of minimum and maximum thresholds, Ymin(i+1) and Ymax(i+1). Ymin(i+1) and Ymax(i+1) form a range of values that cause the receiver 10 to estimate that message t(i+1) was transmitted. The range of values formed by Ymin(i) and Ymax(i) may differ from the range of values formed by Ymin(i+1) and Ymax(i+1). For example, the numerical value Ymax(i)−Ymin(i) may differ from the numerical value Ymax(i+1)−Ymin(i+1). As discussed above, because of the interrelationship between noise and signal level, the length of the range of values representing a signal level may differ from the length of the range of values representing another selected signal level.

The level mean square error, Lmse(i), is defined for an i th PCM level as follows:

For a given probability threshold P 0 (typically P 0 =95%),

If P [y(k)=t(i)]>=P 0 for any Y that is an element of the range Ymin(i) to Ymax(i),

Then Lmse(i)=[Ymax(i)−Ymin(i)]/2, for the i th PCM level.

The Lmse(i) represents the acceptable range for each received level. If a received value y(k) is within the Lmse(i) range, then the received value is estimated by the receiver 10 to be the transmitted signal t(i).

Each of the curves associated with an i th PCM level may have different Lmse(i) values. The difference in the Lmse(i) values results from the realization that the noise in the communication system is dependent upon the signal level. In general, the bigger the Lmse(i) value, the stronger the coherent noise.

FIG. 4 also shows a distance d(i) between two PCM levels. The distance d(i) is calculated according to the following equation:

d ( i )= Lev ( i+ 1)− Lev ( i )− Lmse ( i+ 1)− Lmse ( i );

wherein

Lev(i) is the mean value for the curve f Y [y(k)/t(i)], and Lev(i+1) is the mean value for the curve f Y [y(k)/t(i+1)].

Thus, d(i) is counted from edge to edge of the level ranges. The distance d(i) guarantees a safety distance exists between two levels, and that the level dependent noise is not included inside this safety distance. By assuring a safety distance between two levels, the signal to noise ratio of the overall communication system is increased.

FIG. 5 shows another exemplary set of probability density functions utilized by the receiver of FIG. 1 . The graph of FIG. 5 shows four sets of curves, labeled f Y [y(k)/t( 1 )], f Y [y(k)/t( 2 )], f Y [y(k)/t( 3 )], and f Y [y(k)/t( 4 )]. Safety distances separate each of the curves. In particular, safety distance d 1 is located between the curves f Y [y(k)/t( 1 )] and f Y [y(k)/t( 2 )]; safety distance d 2 is located between the curves f Y [y(k)/t( 2 )] and f Y [y(k)/t( 3 )]; and safety distance d 3 is located between the curves f Y [y(k)/t( 3 )] and f Y [y(k)/t( 4 )]. The safety distances d 1 –d 3 are all greater than 0, thereby assuring an effective safety distance between each of the transmitted messages.

FIG. 6 shows a constellation design for the receiver of FIG. 1 . The illustrated constellation design is associated with the curves shown in FIG. 5 . The constellation design of FIG. 6 illustrates the received signal strength Y along the x-axis, and it also illustrates the decisions made by the receiver 10 along the x-axis. FIG. 6 shows a division of the observed space into four disjoint decision regions t 1 , t 2 , t 3 and t 4 . If the received signal Y is an element of t 1 , then the receiver output signal M is set to t 1 , that is the receiver 10 decides that t 1 was transmitted. Analogously, if the received signal Y is an element of t 2 , then the receiver output signal M is set to t 2 , that is the receiver 10 decides that t 2 was transmitted. In particular, the receiver 10 estimates that the transmitted message sent was t(i) if the signal strength lies in the decision region t(i).

Each of the illustrated decision regions t 1 –t 4 is based upon the minimum threshold Ymin(i), the maximum threshold Ymax(i), Lmse(i), and Lev(i) parameters. In particular, each of the decision regions t(i) is centered around the corresponding Lev(i) points shown in FIG. 5 . The range of distinct length for each decision region t(i) is based upon the corresponding Ymin(i) and Ymax(i) parameters shown in FIGS. 5 and 6 . The range of Lmse for each decision region may vary because the noise associated with each received signal can vary.

FIG. 6 also illustrates safety distances d 1 , d 2 and d 3 that separate the ranges t 1 , t 2 , t 3 and t 4 . The safety distances between decision regions vary. As described above, the safety distance depends upon the Lmse and Lev values of the decision regions surrounding the safety regions. The range of the safety region varies because the noise associated with each received signal can vary.

FIG. 7 is a flow chart for generating a constellation design having a selected number of (i) message levels. The generated constellation design is used by the receiver 10 to identify a transmitted message based upon a received signal. The illustrated flow chart includes the steps of: determining the minimum and the maximum thresholds for each possible received signal level y(k) (Step 86 ); and calculating the distance d(i) between received signal levels based upon the determined minimum and maximum thresholds (Step 92 ). The minimum and maximum thresholds represent a variable range for each of a plurality of received signal levels y(k).

The process for generating a constellation design begins at step 80 . At step 82 , a central site modem transmits a training sequence through the communication channel to the receiver 10 located in a client site modem. At step 84 , the transmitted training sequence is used to identify the probability density functions representative of the probability that a signal y(k) is received given that a signal t(i) is transmitted. These conditional probabilities are given the notation: f Y [y(k)/t(i)]. Typically, the training sequence transmitted by the central site modem includes the transmission of L Pulse Code Modulation levels being sent N times, wherein 12 <N<100. The client site modem receives the corresponding data L(1), L(2), . . . L(N); i.e. the client site modem receives the signal L(i).

At step 86 , the minimum and maximum thresholds are determined for each possible received signal level. The thresholds define a range for each possible received signal level wherein the probability of correctly receiving the transmitted message exceeds or equals a selected probability P 0 .

At step 88 , the mean value, Lev(i), is determined for each received signal level, and at step 90 the Lmse(i) is determined for each possible received signal level. The order of steps 88 and 90 can be reversed, that is the Lmse(i) can be calculated before calculating Lev(i).

At step 88 , the mean value, Lev(i), is determined for each PCM level. That is each of the curves representing the conditional probabilities f Y [y(k)/t(i)] is determined. The mean value for each curve is typically calculated using standard mathematical techniques for calculating the mean value of a curve. For instance, Lev(i) can be calculated according to the equation,

;

wherein L(i) is the training data received by the client site modem.

Alternatively, if using level learning, the mean value can be obtained by taking the final convergence data from the level learning output.

At step 90 , the Lmse is determined based upon the probability density functions calculated in step 84 . For each curve representing an i th PCM level, an associated Lmse(i) is calculated. Each Lmse(i) is calculated by estimating, for each curve, the range wherein the probability of correctly receiving a transmitted message exceeds or equals a selected probability P 0 (typically, P 0 =95%).

Alternatively, Lmse can be calculated as follows:

Standard MSE of

L = σ 2 = 1 N ⁢ ∑ i = 1 N ⁢ ⁢ [ L ⁡ ( i ) - Lev ⁡ ( i ) ] 2 ,

and

Lmse=ασ 2 , where α meets the following equation:

P0 = ∫ - ασ 2 ασ 2 ⁢ e - x 2 2 ⁢ σ 2 ⁢ ⁢ ⅆ x ∫ - ∞ ∞ ⁢ e - x 2 2 ⁢ σ 2 ⁢ ⁢ ⅆ x ,

where P 0 is a selected probability.

At step 92 , the safety distance d(i) between each of the PCM levels is determined. The distance d(i) is calculated according to the following equation:

d ( i )= Lev (i+1)− Lev ( i )− Lmse (i+1)− Lmse ( i );

wherein

Lev(i) is the mean value for the curve f Y [y(k)/t(i)], and Lev(i+1) is the mean value for the curve f Y [y(k)/t(i+1)].

At step 94 , it is determined whether all the calculated safety distances d(i)>=d min . If all the safety distances are >=d min , then processing continues to step 96 where the constellation design is completed. If a safety distance d(i)<d min , then processing branches to step 98 .

At step 98 , the constellation design is adjusted to ensure that all safety distances d(i)>=d min . Typically, this is achieved by removing an overlapping signal level in the constellation design that gives rise to the inadequate safety distance. By removing the overlapping signal level in the constellation design, the safety distance is increased. For example, if Lev(1) is accepted as a level in the constellation design and d(1)<d min , then Lev(2) should be skipped such that the level in the constellation design following Lev(1) is Lev(3). As a result, the new safety distance between Lev(1) and Lev(3) is greater than d min . After the safety distance is adjusted, processing returns to step 86 .

FIG. 8 shows a flow chart for identifying a message based upon a received signal. The chart includes the steps of receiving the signal (step 102 ), generating minimum and maximum thresholds (step 86 ), and identifying the message by comparing the received signal with the generated minimum and maximum thresholds (step 104 ). The generated minimum and maximum thresholds represent a variable range for each of a plurality of possible message levels.

The method for identifying a message begins at step 100 . At step 102 the receiver 10 receives the transmitted signal. After step 102 , the method proceeds to steps 82 , 84 , 86 , 88 , 90 , and 92 . In one alternative embodiment of the invention, step 102 can be performed after step 95 and before step 104 . Steps 82 – 92 are fully described under the description of FIG. 7 .

At step 95 , it is determined whether all the calculated safety distances d(i)>=d min . If all the safety distances are >=d min , then processing continues to step 104 where the constellation design is completed. If a safety distance d(i)<d min , then processing branches to step 98 .

At step 98 , the constellation design is adjusted to ensure that all safety distances d(i)>=d min . Typically, this is achieved by removing an overlapping signal level in the constellation design that gives rise to the inadequate safety distance. By removing the overlapping signal level in the constellation design, the safety distance is increased. After the safety distance is adjusted, processing returns to step 86 .

At step 104 , the receiver 10 compares the received signal with the minimum and maximum thresholds. For example, the comparator 14 compares the received signal level with the threshold signals received from the processor (e.g., table) 12 . The threshold signals represent the constellation design similar to that illustrated in FIG. 6 . By comparing the threshold signals to the received signal the comparator can identify which decision region contains the received signal level. Based on this comparison, the comparator then generates the output signal M. After step 104 , the method of identifying the message ends at step 106 .

While the invention has been shown and described having reference to specific preferred embodiments, those skilled in the art will recognize that variation in form and detail may be made without departing from the spirit and scope of the invention. Thus, specific details of the disclosure herein are not intended to be necessary limitations on the scope of the invention other than as required by the prior art.