DIRTY PAPER PRECODMG WITH KNOWN INTERFERENCE STRUCTURE AT

RECEIVER

CROSS-REFERENCE TO RELATED APPLICATION This application claims the benefit of U.S. Provisional Application

No. 60/724,941, filed October 7, 2005, the disclosure of which is hereby expressly incorporated by reference in its entirety, and priority from the filing date of which is hereby claimed under 35 U.S.C. § 119.

BACKGROUND Broadcast is a communication scenario or modality where a single transmitter sends independent information to multiple non-cooperating receivers. The broadcast channel was introduced by T. Cover in "Broadcast Channels", /EEE Trans. Inform Theory, 1972, where an achievable capacity region of the degraded channel is derived by means of superposition coding. T. Cover, "An Achievable Rate Region for the Broadcast Channel," IEEE Trans. Inform. Theory, 1975, and ε. van der Meulen, "Random Coding Theorems for the General Discrete Memoryless Broadcast Channel," IEEE Trans. Inform. Theory, 1975, disclose an inner bound for degraded discrete memoryless broadcast channels. Marton presented an inner bound of a class of nondegraded broadcast channel in "A Coding Theorem for the Discrete Memoryless Broadcast Channel," IEEE Trans. Inform. Theory, 1979.

Recently the capacity region of multiple-input multiple-output ("MIMO") Gaussian broadcast channel has been studied intensively due to its applicability and benefits in wireless communications applications. The sum capacity of the multi-user MIMO broadcast channel is well studied, see for example, G. Caire and S. Shamai, "On the Achievable Throughput of a Multiantenna Gaussian Broadcast Channel," IEEE Trans. Inform. Theory, vol. 49, no. 7, pp.1691-1706, July 2003; Wei Yu and I. M. Cioffi, "Sum Capacity of Gaussian Vector Broadcast Channels," /EEE Trans. Inform. Theory, vol 50, no. 9, pp. 1875-1892, Sept. 2004; and S. Vishvanath, N. Jindal and A. Goldsmith, "Duality, Achievable Rates, and Sum-Rate Capacity of Gaussian Mimo Broadcast Channels," /EEE Trans. Inform. Theory, vol 49, no. 10, pp 2658-2668, Oct. 2003. Dirty paper coding ("DPC") is a key technology discussed in these papers to derive the sum capacity of the MBVIO Gaussian broadcast channel.

A well-known practical DPC approach, known in the art as Tomlinson-Harashima precoding ("THP"), is described in H. Harashima and H. Miyakawa, "Matched- Transmission Technique for Channels with Intersymbol Interference," /EEE Trans. Commun.,vol. 20, pp. 774-780, Aug. 1972; and, M. Tomlinson, "New Automatic Equaliser Employing Modulo Arithmetic," Electronics Letters, vol. 7, pp. 138-139, March 1971. THP was originally developed for intersymbol interference ("ISI") channels. Its simple structure makes THP a very attractive solution for DPC implementation. U. Erez, S. Shamai(Shitz), and R. Zaniir. "Capacity and Lattice- Strategies for Cancelling Known Interference." In Proceedings of ISITA 2000, Honolulu, Hawaii, pp. 681-684, Nov. 2000. However THP suffers a 1.53dB capacity loss in the scalar case due to shaping, although the capacity gap can be eliminated by using vector lattice coding with much higher complexity.

Since THP is a nonlinear operation, it inevitably causes some quantization noise. The inventors herein have developed a method to reduce the effect of the quantization noise introduced by nonlinear coding. Towards this end, we observe that in some applications, the interference may be of a particular modulation structure that is known to the receiver. This is often the case, for example, in wireless applications where the interference is a known, modulated signal. For example, we disclose a method that reduces the performance loss by taking advantage of the known modulation structure information of the interference signal.

SUMMARY

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This summary is not intended to identify key features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

Although dirty paper coding is a known method for improving the performance of wireless broadcast telecommunications, and is suitable for broadcasting independent signals to multiple receivers, the method is known to incur significant losses, including losses that are attributable to the use of the modulo function in prior art implementations. Disclosed herein is a novel method for implementing DPC that takes advantage of prior knowledge of the interference signal to eliminate or reduce losses associated with DPC.

A method is disclosed for precoding a signal to be transmitted from a transmitter to a receiver in a broadcast system. A source signal representing information to be transmitted from the transmitter to the first receiver is generated. The modulation structure, or aspects of the modulation structure, is determined for a second signal transmitted to a second receiver, the second signal being an interference to the source signal. A first constellation for decoding a signal received by the first receiver is selected based on the interference signal modulation structure, and a mapping rule for mapping the received signal is determined. The source signal is then precoded according to the mapping rule. The source signal and/or the interference signal may be generated, for example, using quadrature amplitude modulation, or with a higher order modulation method.

In a particular embodiment the source signal is a low-resolution multimedia signal, and the interference signal is a high-resolution multimedia signal for the same multimedia content, so that the transmitter can transmit content at various resolutions, to suit different receivers having different capabilities.

The precoding may be demapped onto its constellation without using a modulo operation, such that quantization noise is eliminated.

DESCRIPTION OF THE DRAWINGS

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same become better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIGURE 1 is a diagram generally illustrating the scalar case dirty paper coding scheme scenario; FIGURE 2 is a diagram generally illustrating the dirty paper coding implementation with THP;

FIGURE 3 shows a dirty paper coding implementation in accordance with the present invention, wherein the structure of the interference is known;

FIGURE 4A shows the effective constellation in a typical THP scheme; FIGURE 4B shows an exemplary constellation suitable for use with the present invention, wherein two signals are transmitted using QPSK modulation;

FIGURE 5 is a diagram showing a transceiver structure for applying the present method for higher order constellations;

FIGURE 6 is a constellation diagram similar to FIGURE 4B, and indicating the gridsize parameter.

FIGURE 7 is a diagram illustrating a prior art method for hierarchical multimedia delivery; and FIGURE 8 shows an application of the present method to hierarchical multimedia delivery.

DETAILED DESCRIPTION I. SYSTEM MODEL 1.1 Dirty paper coding

Consider the scalar case dirty paper coding illustrated in FIGURE 1, described in detail in M. Costa, "Writing on Dirty Paper," IEEE Trans. Inform. Theory, vol. IT-29, no. 3, May 1983, and is hereby incorporated by reference. The output of the precoder 100 is given as x = v — as , where v is the input signal, s denotes the known interference, and a is a scalar multiplier. To maximize the mutual information between y andv, given p the signal power, P _x , and noise power P _n , we let a = — and obtain the channel

1 P capacity as C = — log(l + — ) .

2 P _n

1.2 Implementation of Dirty Paper Coding Let λ denote an n-dimensional lattice and let V denote its fundamental Voronoi region. Also let u ~ unif(V) , that is, u is a random variable (dither) uniformly distributed over V . The dirty paper coding scheme may be implemented as follows,

Transmitter: The input alphabet is restricted to V . For any v c F , the precoder sends:

x = (v- as -«)modλ .

Receiver: The receiver computes:

v = (ay + u)m.odA,

where u is the common dither shared by the receiver and the transmitter and is uniformly districutred over (-(λ/2),(λ/2)) . The dithering ensures that the channel input x has a uniform distribution. The quantizer level λ is chosen to meet the power constrains without causing any ambiguity in v. From the expression of v, is clear that quantizatiokn introduces extra noise in demodulation. Hence, the capacity is strictly less than the capacity of the corresponding DPC channel. In U.Erez, S.T. Brin, Approaching the Dirty Paper Limit for Canceling Known Interference,, 41st Ann. Allerton Conf. on Commun., Control, and Computing, Oct. 1-3, 2003, MMSE scaling is introduced to improve the THP performance. In Shamai and Laroia, The Intersymbol Interference Channel: Lower Bounds on Capacity and Channel Precoding Loss, IEEE Trans. Inf. Theory, vol. 42, no. 9, pp. 1388-1404, Sep. 1996, the authors break down the THP losses into a shaping loss, a modulo loss and a power loss. Specifically, the shaping loss is 1.53 dB in the high SNR regime while the modulo loss (up to 3-4 dB) and power loss dominate the low SNR regime. For the scalar case, the problem can be viewed from another angle. Following the

DPC method described above, let a — 1 in high SNR regions. The interference is therefore subtracted directly in precoding. While doing this, a modulo operator 105 is needed to sustain the power constraint in the transmitter side, which means < P .

This is a THP precoding, and is illustrated generally in FIGURE 2. At the receiver side, another modulo process 110 is performed to recover the transmitted data. The quantizer λ is chosen to meet the power constraints without causing any ambiguity in v . From FIGURE 2, it can be shown that:

y = x + s + n = (v - s)modA + s + n where m is an integer. Then we have:

v = ymodλ = (v + τz)modλ .

It is clear that quantization introduces extra noise in demodulation, m the scalar case, the gap to the capacity is known to be 3-4 dB in low SNR regions. Now let us investigate whether it is possible to improve the performance without increasing complexity.

In a broadcast channel scenario for the two-user case {i.e., user A and user B) the transmitted signal for user B is seen as interference to user A. A diagram illustrating the present method implemented for an exemplary transceiver in the two-user broadcast scenario is shown in FIGURE 3, where v is the signal for user A, while the interference, s , is actually the transmitted signal for user B. hi many applications, the modulation schemes of each user are commonly broadcast on a public channel, and therefore each user knows, or can know, the modulation schemes of the other user(s). It will be appreciated that the source signal and the interference signal may be transmitted by the same transmitter, or may be transmitted by different transmitters, that may be in unrelated broadcast systems. We disclose herein an approach that reduces, or even eliminates in some cases, the performance loss (e.g., 3-4 dB in the scalar case) by taking advantage of the known power and/or modulation structure information of the interfering signal, s , in the low SNR regime.

II. PRECODING WITH INTERFERENCE STRUCTURE

KNOWN AT RECEIVER

As discussed above, the conventional THP precoding introduces quantization noise. Of course, it is desirable to reduce or eliminate such noise.

In FIGURE 3, the modulation structure information of the interference, s , is known to the receiver 120. It will be appreciate by persons familiar with the art that a variety of modulation structures that may be implemented, including fore example quadrature amplitude modulation ("QAM"), non-rectangular QAM, phase modulation, amplitude modulation, and the like. For simplicity, we consider a system using quadrature amplitude modulation 112, and wherein the source signal is precoded to account for a known interference modulation structure and the receiver 120 has prior knowledge of the constellation of the received signal, y . Of course, the method described herein may be readily implemented using other modulation structures in a straightforward manner, using the teaching of the present disclosure. As described herein, using the present method we can de-map y onto its constellation without performing the modulo operation required in THP. In the meantime, the soft information can also be extracted, and used as the input to a successive soft channel decoder. The new scheme is explained with a two-user example below.

2.1. Example 1 : Two users with OPSK constellation

Consider, for example, the two-user case. Assume for this example that both users are quadrature phase shift keying modulated ("QPSK"). For the regular THP case shown in FIGURE 2, the decoded signal is v = (v + «)modλ . The constellation of y 200 is shown in FIGURE 4A. The points inside the dashed box 202 are the effective constellation of v .

Of course, the precoding output must meet the transmitter power constraint. In other words, the output x of the precoder 114 (FIGURE 3) must have the same average power as the source v .

In this example, the scheme is carried out in the following steps:

1. Precoding:

x = v-s; |v > s ;

x where |_«J indicates the floor operator.

The precoding rule is applied to both dimensions of the QPSK signal. The power of x is the average power of random signal: ±[2(i-l) ^• |v|-|s|] and ±[2(i+l)|v|-|s|], which are bounded.

2. Decoding: The decoder detects the 2-bit symbol based on the location of the received signal (relative to four decision regions). For |v|>|s|, the decision region is the same as the QPSK. For |v| <= |s|, unlike regular QPSK, the four decision regions are asymmetric as illustrated on the constellation 120 shown in FIGURE 4B. Nevertheless, a direct mapping from the source v to y can be established. By removing the modulo operation, the noise folded into the modulo interval around the origin is eliminated.

It will be appreciated that with the structure information of the interference, s, the receiver shares the knowledge of y ¹ S constellation with the transmitter. In this case, y has 16-QAM like constellation. However, the mapping from v to y has several possible

choices. It is easily verified that the mapping shown in FIGURE 4B yields the best performance in the present example.

2.2 Example 2: Two users with high order constellation Refer now to FIGURE 5, which shows diagrammatically the present method applied utilizing a higher order constellation, still assuming for purposes of illustration, a system using QAM. The disclosed precoding strategy can be readily extended to higher order modulation scenarios. It should be appreciated that the constellation of y may vary with the strength of the interference (or the signal of another user). However if the signal strength of the interferer signal is within a certain range, the constellation of y remains unchanged.

Generally speaking, the design of the new precoding scheme involves two steps:

1. Selecting the constellation of y , subject to the following constraints:

(a) In order to meet the power constraints at the transmitter, the constellation of y must be designed properly according to the modulation structure and/or strength of the interference. A common rule must be in place, so that both receiver and transmitter will expect the same constellation for y .

(b) According to the constellation of y , a proper mapping rule should be set from v to y so that the best performance is achieved.

2. Precoding strategy at transmitter.

Once the constellation of y is chosen, we need to design a precoder according to the mapping rule and the interference, the modulation structure of which is fully known at the transmitter. Also we should keep in mind that the transmitter signal must satisfy the transmitter power constraint.

At the receiver, the source information is demodulated directly from y , without using a modulo function. Note that the above processes at the transmitter and the receiver are independent. 2.3 Example 3: Source OPSK modulated, interference 16-OAM modulated hi this example, the source is QPSK modulated while the interference 16-QAM modulated. Assuming the average signal strength of the interference, s, is 1.5 times the average signal strength of the source, v, that is s = 1.5 v , we select the constellation of

y as indicated in FIGURE 6, which shows the same constellation shown in FIGURE 4B ₅ with the definition for gridsize indicated.

Then at the precoder a precoding strategy is selected for the source, v , to achieve the selected constellation of y . The mapping rule from source v to x is shown in the Table 1, using the definition of gridsize shown in FIGURE 6.

Table 1 mapping rule from source V to X v is (0,0) Ifreal(s)>0, then real(x)~gridsize-real(s) ; else real(x) =-gridsize-real(s) ; Ifimag(s)>0, then imag(x)=gridsize-imag(s); else imag(x) =-gridsize-imag(s) ;

v is (0,1) Ifreal(s)>0, then real(x)=3xgridsize-real(s); else real(x)=-3 xgtidsize-real(s); Ifimag(s)>0, then imag(x)=gridsize-imag(s) ; else imag(x) --gridsize-imag(s) ;

v is (1,0) Ifreal(s)>0 ,then real(x)-gridsize-real(s); else real(x) —-gridsize-real(s); Ifimag(s)>0, then imag(x)=3xgridsi∑e-imag(s); else imag(x)=-3 xgridsize-imag(s) ;

v is (1,1) Ifreal(s)>0, then real(x)=3 ^y -gridsize-real(s) ; else real(x)=3 xgridsize-real(s); Ifimag(s)>0, then imag(x)=3 xgridsize-imag(s) ; else imag(x)=-3 xgridsize-irnag(s) ;

As noted above, the constellation of y may vary with the strength of the interference. It will be readily apparent to persons of skill in the art that the precoding and decoding approach can be easily modified for each possible constellation of y accordingly.

If both the source and the interference constellations are 16-QAM or even higher order, it may not be practical to do such precoding at the transmitter due to complexity

issues. If the complexity is overly burdensome, the regular THP precoding may be conducted at the transmitter, while the modified decoding strategy is still applicable at the receiver.

2.4 Example 4: More than two-user case For the case involving more than two users, things become a little more complicated. The receiver needs to know the structure and strength of the other two (or more) users. However once this information is determined, the receiver still can predict the constellation of y . The precoding and decoding procedures are still the same as the two-user case. 2.5 Example 5: Hierarchical modulation for multi-rate multimedia delivery

In digital TV or other wireless/wireline broadcasting applications, different users usually experience different channel qualities/signal strengths due to their geographical locations. Ideally, users with high signal strength should receive higher qualities programs (e.g., high-definition TV - HDTV) over those with lower signal strength and therefore only the basic program. Such can be achieved through the combination of source coding and hierarchical modulation. A multi-rate source code is a data compression algorithm designed specifically for the multi-user communication system. The simplest example of a multi-rate source code is the multi-resolution code — in which a single transmitter describes the same information to a family of receivers so that all receivers receive the lowest-rate description (the first data stream), and each higher rate is achieved by adding on to the description at the nearest lower rate (the second data stream, etc.).

Hierarchical modulation can be employed to transmit the first and the second or/and more data streams. The most commonly used hierarchical modulation scheme is the hierarchical QAM, where QPSK carrying the first data stream (e.g., lowest-rate description) is combined with higher dimensional QAM (e.g., 16-QAM) carrying the second data stream (e.g., the next level of description) or an additional source. For practical applications, the first modulation enables the basic program with relatively lower data rate, and the higher dimensional QAM enables additional information for higher quality programs or more channels.

While hierarchical QAM is relatively simple to implement, it does suffer from some performance loss relative to regular QAM. Existing techniques such as success

cancellation can be used to recover some of the loss in hierarchical QAM. However the cost burden incurred at the receiving end is often prohibitive in practice.

The present method can be implemented to provide a new hierarchical modulation scheme for multi-rate multimedia delivery based on the DPC technique. The major advantages of the new technique over prior art include:

1. Significantly simplified receiver structure - different data streams can be decoded independently.

2. No additional requirements on data memory - since different data streams are decoded independently, no excess data memory is needed as in the case of joint decoding/success demodulation.

3. Capacity achieving performance - by using DPC at the transmitter, the information theoretic data rate limits can be achieved without receiver complication

The prior approach that achieves hierarchical multimedia delivery is illustrated in FIGURE 7, where the first data stream (source 1) is coded and modulated (e.g., using QPSK). The power of the first modulated data stream is adjusted by 0 ₄ . Similarly the second data stream (source 2) is coded and modulated in a separate branch (e,g,, using QPSK) with power α ₂ . The two modulated signals are then mixed before being transmitted. Clearly, the two modulated signals interfere to each other, leading to lower performance than regular QAM schemes. A typical constellation of the hierarchical QAM signal is depicted in FIGURE 4A.

At the receiver side, a low signal strength user will simply demodulate the basic signal (the first data stream) while users with higher signal strength can demodulate both signals from the constellation.

The present method suggests a different hierarchical modulation approach for broadcasting application using the DPC.

In the present scheme, the first data stream (Source 1) is modulated with regular modem technique such as the QPSK. Instead of generating the second signal independently, the interference from the first data stream is pre-subtracted using the DPC technique as shown in FIGUPvE 8. Because of this operation, the second modulated data stream, when reaching a receiver, will suffer from no interference from source 1, as discussed above.

A number of DPC implementation algorithms can be employed, including the trellis code approach and the structured DPC ("SDPC") method. The SDPC is

computational advantageous due to the exploitation of the structure information embedded in the interfering signal.

El. PERFORMANCE ANALYSIS AND SIMULATION RESULTS In this section, we analyze the symbol error rate of the proposed scheme and compared it with the regular THP precoding.

3.1 Two users with OPSK constellation

Assuming that source and interference are both QPSK signals and the signal strength of interference abides v < ≤ 3 v| . The constellation of y for regular THP and proposed precoding scheme are shown in FIGURE 4A and 4B. In FIGURE 4A, the dots inside the dashed are effective constellation points. The symbol error rate for this case is easy to calculate as:

For the proposed scheme, we map the source into the constellation according to the interference by the following rules:

* = ^« gn(*X(|2v-|v||)-|*D The mapping from source v to y is shown in FIGURE 4B. The symbol error rate for this case is:

1 I F P _S S _D D _P P _C C = 2xPJ e 2 = - ₂ erf Jc( \δ p- _N ≡^) J

In absence of the interference, the symbol error rate for QPSK signal through

AWGN channel is P _AWGN = 2 x P _e 12 = erfc{ \ ^b~λWGN ) . Under the same transmitter

N _n power constraint, it is clear that E _b _ _AWGCN < E _b _ _SDPC < E _b _ _AWGCN . So we get P _AWGCN - Ps _DP c - ^P _THP • ^^ ^s equation is also valid when source and interference are both BPSK (binary phase shift keying) signals.

Simulation studies have been conducted. In our simulation, the source and interference are both QPSK signals. The amplitude of interference signal is chosen to be

1.5 times of that of source signal for the proposed scheme. For the regular THP, α is set to p be optimized value as — . The simulation results match the theoretical results well in

high SNR region.

We also studied the performance of modified THP precoding with channel coding. A rate 1/2 (7, 5) turbo code is used with the log-map decoding algorithm. The results show that the modified scheme outperforms the regular THP and has almost the same performance as the interference-free case. 3.2 Two users with high order constellation

Following the example in last section, we study the case where the source is QPSK and interference is 16-QAM modulated. With the similar analysis as the above, the symbol error rate of regular THP case is:

For the new scheme:

^p ~ ⁼ -**&> -

In absence of the interference, the symbol error rate for QPSK signal through

AWGN channel is P _se% = 2xP _e = erfc(M-) . So we get P _sA = 2P _se2 = 2P _se3 .

We also conducted simulation for this case. In our simulation, α is set to be p optimized value as - — for the regular THP. The simulation results match the

theoretical results well in high SNR region. We also studied the performance of modified THP precoding with channel coding. A rate 1/2 (7, 5) turbo code is used with the log-map decoding algorithm. The results show that the modified scheme outperforms the regular THP and has almost the same performance as the interference-free case.

The present modified precoding approach outperforms the regular THP precoding, especially for BPSK and QPSK signals. The new algorithm achieves comparable performance as the interference-free case. For the high order constellation, the performance improvement is reduced and the system complexity is increased. This precoding method can be extended into multi-user case.

While illustrative embodiments have been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention.