Peak power to average power ratio reduction in multicarrier communication systems using error-correcting code

[0002] This application claims benefit of Provisional application Ser. No. 60/101,746, filed Sep. 24, 1998.

[0003] 1. Field of the Invention

[0004] This invention pertains to data communication systems that employ a multitude of carriers for conveying information through a transmission medium. In particular, this invention addresses the problem of peak to average power ratio reduction in such systems.

[0005] 2. Description of the Background Art

[0006] A multicarrier transmission system is one that employs Frequency Division Multiplexed (FDM) subcarriers for transmission of data across a communication channel. A comprehensive description of multicarrier systems is given in by John A. C. Bingham in “Multicarrier Modulation for Data Transmission: An idea whose time has come”, IEEE Communication Magazine, Vol. 28, No 5, pp. 5-14, May 1990.

[0007] A typical multicarrier transmission system,is depicted in FIG. 1. It shows serial data in the form of bits input to a serial to parallel converter 100, which may also frame the bits. (A frame is an ordered sequence of bits of a given size). The output of block 100 is fed to a Forward Error Correction (FEC) block 200, which adds redundant bits to facilitate correction of possible errors introduced by the transmission medium 900. The output bit frame from the encoder is mapped to symbols in the mapper 300. The frame of symbols then passes through the modulator 400. The modulation could be carried out, for instance, using Inverse Fast Fourier Transform (IFFT) and the corresponding demodulation carried out using Fast Fourier Transform (FFT). The modulated signal is converted to serial data 700 and transmitted on to the channel 900, where it suffers several impairments in addition to being corrupted by noise. At the receiver, the received data is grouped into frames by a serial to parallel converter 1000 and subsequently passed through the demodulator 1100. The demodulated symbols are converted to bits and passed through FEC decoder 1200. The data bits are obtained by passing the decoded bits through a parallel to serial converter 1300.

[0008] In practice, the data bits input to the transmitter module are independent and the symbols obtained using the bits-to-symbols mapper are also independent. Whenever the number of subcarriers is large, the modulator output magnitude tends to have a Gaussian distribution, which has an infinite peak to average power ratio. A clipper 800, which has a cutoff based on a predesignated clipping probability, is then used to limit the peak signal power that is transmitted on to the channel. The clipping probability needs to be small in order that the error introduced due to clipping is small. If the predesignated clipping probability is reduced, the peak power input to the channel increases, which may cause saturation in the subsequent amplification stages. A higher peak power requires a larger range of amplifier linearity and leads to higher cost. Thus it becomes necessary to limit the peak power transmitted on to the channel by reducing the clipping level while still maintaining a low clipping probability.

[0009] FIG. 1 shows a peak detector 500 at the output of the modulator, which activates a symbol modifier 600 whenever the magnitude of any of the modulator output samples exceeds a predesignated threshold or a set of thresholds. The threshold could be set based on the level of peak power that can be transmitted on to the channel, while the task of the symbol modifier is to modify the symbols being modulated in such a manner that the peak is reduced. Although FIG. 1 shows the symbol modifier correcting the symbols that are being modulated, it is possible to achieve the same effect by correcting the modulated samples.

[0010] The symbol modifier needs to fulfill a number of objectives:

[0011] 1. The clipping probability should remain unaltered when the clipping threshold is lowered.

[0012] 2. The modifications introduced in the symbols should not cause significant increase in the error rate at the receiver.

[0013] 3. The symbol modifier should have a low complexity.

[0014] 4. The Peak to Average power Ratio (PAR) reduction scheme should be transparent to the receiver.

[0015] 5. The modifications made to the data symbols should not cause an increase in the average power.

[0016] 6. The loss in data rate caused due to symbol modification should be minimal.

[0017] Most of the requirements are conflicting and it may not be possible to meet all of them at the same time. The amount of importance given to different requirements by a particular method decides the extent of PAR reduction achievable by that method.

[0018] A scheme using a pre-designated set of subcarriers to reduce the PAR is described by J. Tellado and J. Cioffi in “PAR Reduction in Multicarrier Transmission Systems (97-367)”, T1E1.4/97-367 Dec. 8, 1997. The method uses an iterative procedure that aims at reducing the largest peak every iteration. A similar scheme by the same authors is detailed in “Revisiting DMT's PAR (98-083)”, T1E1.4/98-083, Mar. 3, 1998. Here, an iterative procedure tries to reduce all the peaks present in each iteration. Both the methods employ a precomputed peak reduction kernel. The reduction in PAR is obtained at the expense of data carrying subcarriers. It is required that the receiver be aware of the predesignated subcarriers to be used for peak reduction.

[0019] The modulo-D scheme described in “A new approach to PAR control in DMT Systems”, NF-83, ITU—T, Study Group 15, 11-14 May 1998, uses an expanded constellation in each subcarrier for PAR reduction. The method uses symbols drawn from larger constellations whenever the original modulation produces large peaks. The method results in no data rate loss. The use of larger constellations results in increased average power and higher intermodulation distortion. The receiver needs to perform a reverse operation to the transmitter action to recover the original data symbols.

[0020] A sign inversion method is specified in “An Efficient Implementation of PAR reduction method based on subset inversion”, AB-061r2, ITU—T, Study Group 15, 3-7 August, 1998. The method consists of dividing the set of subcarriers into several subsets and achieving a PAR reduction by inverting the sign of the symbols in some of the subsets. The transmitter uses part of the data carrying bits to indicate to the receiver whether a sign inversion has been applied. This method requires receiver cooperation and results in some data rate loss. An error in a subset inversion indicator bit may result in wrong decoding of many of the data bits associated with that subset.

[0021] The scheme specified in “A. E. Jones, T. A. Wilkinson and S. K. Barton, Block coding scheme for reduction of peak to mean envelope power ratio of multicarrier transmission schemes, Electronic Letters, Vol. 30, No. 25 pp 2098-2099, December 1994” uses a coding scheme with an inherently low PAR. This is achieved at the expense of increase in the redundancy (extra bits added to the data carrying bits.)

[0022] This invention pertains to Peak to Average power Ratio (PAR) reduction in multicarrier communication systems that employ a Forward Error Correction (FEC) coding mechanism. A method and apparatus are provided that computes a subcarrier symbol modification that effects a reduction in PAR of the transmitted data samples. The present invention consists of a peak detection mechanism, a procedure for choosing a subcarrier and a symbol modifier scheme. The peak detector uses a threshold for determining whether the PAR reduction is to be applied. A slightly modified version using a lower sampling rate and a threshold over adjacent samples is also disclosed.

[0023] Several methods are described for choosing a subcarrier for symbol modification depending on the location(s) of the peak and the effectiveness of the symbol modification on reducing the PAR with very little loss of coding gain. Specific methods apply to single peaks, two peaks and multiple peaks. The methods for choosing the subcarriers can be applied to any PAR scheme that uses symbol modifications for reducing PAR. The symbol modifier uses the fact that subcarrier errors, introduced rarely, will have a minor effect on the coding gain of the error-correction mechanism used. A tradeoff between extent of PAR reduction and loss in coding gain can be made by modifying the threshold of the peak detector.

[0024] FIG. 1 is a block diagram of a typical multicarrier system that employs a forward error correction code.

[0025] FIG. 2 is a block diagram of the present invention.

[0026] FIG. 3 explains the effect of sampling rate on peak detection.

[0027] FIG. 4 depicts an iteration of Procedure 1.

[0028] FIG. 5 describes Procedure 2.

[0029] FIG. 6 is a block schematic of Procedure 3.

[0030] FIG. 7 demonstrates usage of different threshold for detection of contiguous peaks.

[0031] In accordance with the present invention, an error correcting mechanism is used to achieve a PAR reduction in multicarrier communication systems. Most multicarrier systems employ an FEC mechanism in order to improve the data rate. For instance, the Asymmetric Digital Subscriber Line (ADSL) communication protocol specified in “ANSI T1E1.413-1995, American National Standard for Telecommunications—Network and Customer Installation Interfaces—Asymmetric Digital Subscriber Line (ADSL) Metallic Interface, August 1995” uses a Reed Solomon coding scheme for error correction. In the scheme presented the encoded data frame is modified in order to achieve a reduction in PAR with little or no loss in the coding gain. It is possible to tradeoff coding gain with the extent of PAR reduction based on the application requirements. The advantage of the present invention is that the receiver need not have the knowledge of the transmitter employing a PAR reduction mechanism. Consequently, the receiver need not perform any extra action that reverses the effect of the transmitter action for achieving PAR reduction. No subcarriers need to be specifically allocated for PAR reduction signals.

[0032] The present invention is applicable to multicarrier data communication systems that use a bit or byte level error correction mechanism. Further, it is applicable for any system where the modulation and demodulation are performed at the frame level. However, the ensuing description considers a multicarrier system employing IFFT and FFT for modulation and demodulation, respectively, and a Reed Solomon byte error correcting mechanism. Details about the Reed Solomon error correction code are given by Man Young Rhee in “Error Correcting Coding Theory,” McGraw-Hill, International Editions, 1989 which is hereby incorporated by reference.

[0033] A block schematic of the proposed method is shown in FIG. 2. A Reed Solomon encoder 2100 adds R redundant check bytes for every block of K input data bytes to produce a frame of N=K+R bytes. The data frame of N bytes is then mapped to symbols in block 2200 and modulated using the IFFT block 2300. Assuming a multicarrier system of m carriers with Bi bits in carrier i, the data frame size (in bytes) N satisfies N*8=B1+B2+ . . . +Bm. In case of bit wise framing schemes, the sum of the bits need not be a multiple of 8. In a more general case, the encoded frame of size N may span more than one block of modulator output. In this case, the size of the input to the mapper is not the same as that of the input to the IFFT block.

[0034] The IFFT samples are passed through a peak detector 2400. The peak detection is carried out on the modulated samples using a predetermined threshold (or set of thresholds). The output of the peak detector activates the symbol modifier block 2500 whose output is added to the modulator output. This is finally passed through the Digital to Analog converter, filters and line drivers (represented in block 2700) and transmitted onto the channel.

[0035] The functions of peak detector and symbol modifier blocks are now explained in detail.

[0036] The inputs to the peak detector are M=2m samples of the IFFT. The peak detector uses a predesignated threshold T. Each IFFT sample is compared with the threshold and the indices of samples whose magnitude exceeds the threshold are stored along with the amount by which they violate the threshold. This data forms the input to the symbol modifier block.

[0037] More generally, the peak detector could also find out if several successive IFFT samples are exceeding another prespecified threshold T1. The motivation behind such an action is as follows: The peak detector works on a sampled response and the sampling instances may not capture the actual largest peak but some neighbouring smaller value. This problem can be avoided by increasing the sampling rate itself, in order to improve the possibility that actual peak values are detected. This problem is schematically depicted in FIG. 3. The sampled response corresponding to the normal sampling rate (fs) corresponds to the points of intersections of the continuous vertical lines with the continuous curve. It is seen that the actual peak value is missed for this case. If the sampling rate is doubled (to 2*fs), new samples would have resulted corresponding to the intersections of the continuous curve with the dotted vertical lines. It can be observed that one of the new points is nearer to the actual peak value.

[0038] In actual practice, it may not be possible to increase the sampling rate since that induces extra computation overheads. A compromise solution in such cases would employ another threshold T1, possibly different from T, and look for cases where 2 or more contiguous samples cross this threshold. FIG. 7 depicts a case where 2 peaks exceed the threshold T1. It is possible to get a better approximation to an actual peak by performing simple interpolation using these points.

[0039] The symbol modifier is conveyed the value and location of the estimated peak(s) for which it needs to compensate.

[0040] This block determines the modification(s) to be made to the input symbols or the modulated samples such that the output of the symbol modifier reduces the overall PAR of the transmit signal. Below several embodiments are described, which have varying degrees of complexity. The clipping level is fixed based on the permissible bit error rate introduced by the transmitter module. In general the clipping probability for a given threshold is small. In such a case, the probability that more than one sample will be clipped in a frame is small compared to the probability of a single sample (peak) getting clipped.

[0041] First, a procedure is described that takes care of one peak in a frame. The procedure determines that subcarrier symbol which has the maximum effect on the peak. The symbol is then given a phase rotation to effect a peak reduction. It is possible that a new peak results by this procedure; the procedure may then be repeated for the new peak after removing the previously chosen subcarrier from the search.

[0042] When there is more than one peak, the procedure is carried out starting from the largest one. The pseudo code for the procedure is given below:

[0043] 1. For the largest peak occurring, say at location L, do steps 2-4.

[0044] 2. Determine the subcarrier, which will result in the maximum effect on the given peak. For ease of understanding, let us consider a case where the subcarrier frequencies are given by 0*B, 1*B, 2*B . . . , m*B. The sampling rate is assumed to be M*B. For each subcarrier, determine effect E of the symbol on the output. For a complex input X_i+jY_iat the ith subcarrier of the modulator, this is computed as follows. The effect of the ith subcarrier is given by

[0045] E_i=X_i*cos((2*π*L*i)/(M))−Y_i*sin((2*π*L*i)/(M))

[0046] 3. Determine the subcarrier that has the maximum value of R_i+E_i,

[0047] Where R_i=sqrt(X_i*X_i+Y_i*Y_i).

[0048] 4. Apply a phase correction P to the chosen subcarrier computed as follows:

[0049] P=−(2*π*L*i)/(M)−atan(Y_i/X_i)

[0050] (X_i+jY_i)←(X_i+jY_i)*exp(j*P)

[0051] Remove the chosen subcarrier that has been modified from the search space.

[0052] 5. Repeat steps 1-4 if necessary.

[0053] 6. Remodulate the changed symbols and transmit the modified samples.

[0054] One iteration of Procedure 1 is depicted in FIG. 4. To begin with, the largest peak is found (block 4000) and the subcarrier with the maximum effect on this peak is found (block 4100). The above described phase correction is applied to this subcarrier (block 4200) and the symbols or samples are modified and transmitted (block 4300).

[0055] In step 2 above, the expression for E corresponds to a conventional QAM modulation scheme in each subcarrier. If the modulation is performed using IFFT, the (M-i) the subcarrier will have the complex conjugate of the ith subcarrier symbol. In this case, the expression for E will have to be scaled by a factor of 2 (with the exceptions of the DC and Nyquist subcarriers).

[0056] Modifications to the procedure are now mentioned.

[0057] In step 3 above, R₁+E_icould be approximated to 2*E_iin order to avoid the square root computation.

[0058] In step 4 above, the phase correction may result in an invalid symbol. In such a case, the nearest valid symbol could be chosen. This is required so that the receiver adaptation during data mode is unaffected.

[0059] A 180 degrees phase correction could be applied instead of the one computed in step 4. This may result in lower bit errors introduced in case of certain kind of bit to symbol mapping schemes. For e.g., in case of a constellation with even number of bits-per-symbol, a 180 degrees phase shift results in a valid symbol and introduces only two bit errors. This could result in a smaller loss in coding gain.

[0060] If the average power constraint can be relaxed, the amplitude of the subcarrier could also be varied to increase the extent of PAR reduction achieved.

[0061] Repeated application of the above procedure on a data frame results in a higher PAR reduction at the cost of coding gain. This allows the transmitter to tradeoff the amount of PAR reduction desired against coding gain.

[0062] Although the above procedure is computationally inexpensive, it may result in too many symbols being modified leading to unacceptable loss of coding gain. Thus, in a further embodiment, this situation is addressed. This procedure is as follows:

[0063] 1. Determine the peaks P1, P2, P3, . . . Pn (n<=M) at locations L1, L2 . . . Ln, respectively.

[0064] 2. Determine the effects E of subcarrier on the largest peak. Calculate the phase correction as specified in 2, 3 and 4 of procedure 1 above. Determine the overall effect of the phase correction on all the other peaks as a sum (weighted or otherwise) of the individual effects. Choose the subcarrier that gives the greatest sum of effects.

[0065] 3. Remove the chosen subcarrier that has been modified from the search space.

[0066] 4. Repeat steps 1-3 if required.

[0067] 5. Remodulate the changed symbols and transmit the modified samples.

[0068] Procedure 2 is depicted in FIG. 5. The largest n peaks are found (block 5000) and the effect of subcarriers on the largest peak determined (block 5100). Out of the subcarriers, few that give the maximum effect are selected (block 5200). The cumulative effect on the n peaks due to each subcarrier in the selected set is computed and the best of them chosen (block 5300). The phase correction is applied to this subcarrier, the modulated data modified and transmitted.

[0069] Here, instead of choosing the subcarrier with the greatest overall effect (effect E as defined in procedure 1), the subcarrier that gives the minimum sum of residual peaks is chosen. Here residual peak is defined as the amount by which a peak exceeds the threshold value.

[0070] Procedure 2 needs a search through all the subcarriers. In practice, the event of occurrence of more than two peaks is very low. The one peak case has already been dealt with. Accordingly, a procedure that can handle two peaks and does not need to search through all the subcarriers is now described. Thus, the above procedure needs to be applied only wherein there are more than two peaks, which occurs very rarely.

[0071] In case of two peaks, the search for the best subcarrier may be restricted to a subset of subcarriers as follows:

[0072] 1. Determine the distance D between the two samples i.e. the peaks occur at L1 and L1+D.

[0073] 2. Compute the phase difference between the two peak locations for each subcarrier. The phase difference is calculated as:

[0074] P=(2*π*D*i)/(M)

[0075] Where,

[0076] i→subcarrier number,

[0077] M→Total samples in the frame.

[0078] 3. If both peaks have the same sign, choose subcarriers that satisfy the following relation:

[0079] −Δ<P<Δ

[0080] Where,

[0081] Δ is a small angle between 0 and π/2. (A typical value of Δ could be π/6.)

[0082] For peaks with opposite signs, choose subcarriers that satisfy the relation:

[0083] π−Δ<p<π+Δ

[0084] 4. Apply either procedure 1 or procedure 2 to the reduced set of subcarriers.

[0085] Procedure 3 is depicted in FIG. 6. The distance between the two large peaks is found (block 6000). The phase difference between the two peaks is computed for each subcarrier (block 6100). The carriers that have small phase difference (as indicated in Procedure 3) are chosen (block 6200) and either of the procedures 1 or 2 applied to this set (block 6300).

[0086] To minimize computation during procedure 3, the set of subcarriers for each value of D may be precomputed and stored.

[0087] The methods for choosing the subcarrier to be modified are generic: it can be applied to any scheme that modifies one or more subcarriers to effect a PAR reduction.

[0088] In all the procedures above, the amount of subcarrier symbols that could be modified will be limited by the error correcting capability of the encoder.

[0089] Apart from IFFT, any alternate means of frame (symbol) based QAM modulation may also be used. This could also include PAM and DPSK modulation.

[0090] The procedure can also be applied to any subset of the 2-dimensional constellation or multi-dimensional constellations.

[0091] The symbol modification can be applied to the phase or the amplitude or both. Also, the modules can be implemented in hardware or software in accordance with the present invention.