10 Papr Reduction Of Ofdm Signals Using Cross-entropy-based Tone Injection Schemes

IEEE SIGNAL PROCESSING LETTERS, VOL. 17, NO. 8, AUGUST 2010

727

PAPR Reduction of OFDM Signals Using Cross-Entropy-Based Tone Injection Schemes Jung-Chieh Chen, Member, IEEE, and Chao-Kai Wen, Member, IEEE

Abstract—This letter considers the use of the tone injection (TI) scheme to reduce the peak-to-average power ratio (PAPR) of an orthogonal frequency division multiplexing (OFDM) signal. TI is a distortionless technique that can reduce PAPR significantly without data rate loss and does not require the extra side information. However, the optimal TI scheme requires an exhaustive search over all combinations of possible permutations of the expanded constellation, which is a potential problem for practical applications. To reduce the computational complexity while still improving PAPR statistics, this letter first formulates the PAPR reduction with TI scheme as a particular combinatorial optimization problem. Next, it proposes the application of the cross-entropy (CE) method to solve the problem. Computer simulation results show that the proposed CE method obtains the desired PAPR reduction with low computational complexity. Index Terms—Cross-entropy method, orthogonal frequency division multiplexing (OFDM), peak-to-average power ratio (PAPR), tone injection (TI).

method [8], [9]. Even so, the PAPR performance of the greedy method is not reduced sufficiently. In this letter, we formulate the PAPR reduction with TI scheme as a particular combinatorial optimization problem, and then propose the application of the cross-entropy (CE) method, an effective algorithm that solves various combinatorial optimization problems, to solve the problem. Computer simulation results show that the proposed CE method obtains the desired PAPR reduction with the complexity of , where is the number of subcarriers and is the number of samples. II. SYSTEM MODEL AND PROBLEM DEFINITION Consider an OFDM system with subcarriers. The discretetime transmitted OFDM signal is given by (1)

I. INTRODUCTION

O

RTHOGONAL frequency division multiplexing (OFDM) has been widely used in a variety of digital transmissions including digital video/audio broadcasting, digital subscriber lines, and wireless local area networks [1], [2] because of its ability to cope with the frequency selective fading of wideband communication with reasonable complexity. However, a challenging issue for the OFDM system is its high peak-to-average power ratio (PAPR). Numerous approaches have been proposed [1]–[7] to reduce the PAPR of the OFDM system. Among these methods, tone injection (TI) [8], [9] is a distortionless technique that can reduce PAPR significantly without data rate loss. In addition, TI does not require the exchange of side information between transmitter and receiver. However, implementation of the TI approach requires solving a difficult integer programming problem whose complexity grows exponentially with the number of available subcarriers, which is far too much to be practically implemented. Therefore, one has to resort to suboptimal solutions such as the greedy Manuscript received March 15, 2010; revised May 13, 2010; accepted May 14, 2010. Date of current version June 21, 2010. This work was supported in part by the National Science Council, Taiwan, under Grants NSC 98-2221-E017-004 and NSC98-2218-E-110-005-MY2. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Vincent K. N. Lau. J.-C. Chen is with the Department of Optoelectronics and Communication Engineering, National Kaohsiung Normal University, Kaohsiung 802, Taiwan (e-mail: [email protected]). C.-K. Wen is with the Institute of Communications Engineering, National Sun Yat-sen University, Kaohsiung 804, Taiwan (e-mail: [email protected]). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/LSP.2010.2051617

where is a complex input symbol sequence, and stands for a discrete time index. The PAPR of the transmitted signal in (1) is defined as (2) where denotes the expected value operation. The basic idea of the TI scheme is to increase the constellation size to map each of the points in the original constellation into several equivalent points with the same information content in the expanded constellation. Each information unit can be mapped into one of several equivalent constellation points, and thus these extra degrees of freedom can be exploited for PAPR reduction. Assume that -ary square quadrature amplitude modulation (QAM) is used as a modulation scheme, where is the minimum distance between neighboring points. In this can take case, the real and imaginary parts of each symbol , where values in the set denotes the number of levels per dimension. To reduce PAPR, the TI method maps each input symbol into several equivalent points in the expanded constellation. Mathematically, the TI method modifies the input symbol by adding a variable to as follows: (3) where and are any integer values, and is a positive . Thus, real number chosen, such that can be removed at the receiver by performing a modulo- on the real and imaginary part of the frequency bins. The transmitted

1070-9908/$26.00 © 2010 IEEE

728

IEEE SIGNAL PROCESSING LETTERS, VOL. 17, NO. 8, AUGUST 2010

OFDM signal after performing the TI scheme is then replaced by

(4) The objective of the TI method is to determine the integers and that produce the lowest PAPR for . To reduce the peaks of the transmitted signal as much as possible, the optimal TI scheme requires an exhaustive search over all combinations of possible permutations of and . It turns out that the complexity of the full optimization at the transmitter would be [8], [9] (5) where is the number of candidate constellation points and is the number of dimensions needed to be -shifted. This results in high computational complexity, which cannot be implemented for practical situations. Therefore, one has to resort to suboptimal solutions such as greedy algorithms [8], [9]. However, the greedy algorithm is easily trapped into local solutions. As a result, it can only obtain moderate PAPR reductions. Inspired by the success of the CE method in solving various combinatorial optimization problems, the PAPR reduction problem with TI scheme is transformed into a combinatorial optimization problem. Then, application of the CE method is proposed to solve the problem in order to minimize PAPR of the transmitted signal. In this case, the transmitted signal after performing the modified TI scheme can be expressed as (6) where whose entries sponding signal symbol is defined as

is a binary selection sequence determine whether the correis shifted or not, and

Fig. 1. Expanded constellation of the CE approach with 16-QAM.

side the gray box represent the original 16-QAM, while constellations outside the gray box represent the expanded constellation of the corresponding original ones. As shown in Fig. 1, only constellations located on the outer ring could be shifted, and the corresponding equivalent constellations are nearly symmetrical about the origin. In addition, the constellations closer to the original of the original constellation would not be shifted, because shifting them would result in a greater power increase. Furthermore, and most importantly, this TI scheme requires no side information at all for the OFDM system because the equivalent constellations do not overlap with the original positions. Based on the above-described TI scheme, this letter aims to determine which combination of expanded and original constellations contributes to PAPR reduction. Since there is only one equivalent constellation for the symbol to choose to be shifted or not, the resulting combinatorial optimization problem is

(9) (7)

where (10)

indicates the particular mapping relationship beHere tween the original constellation and its corresponding equivalent point, which can be defined as [11]

and is the set of -dimensional binary vectors. It is obvious that finding the optimum solution of (9) is a difficult . Therefore, optimization problem with the complexity of a novel implementation of PAPR reduction problem in (9) using the CE method in the next section is proposed. III. THE CE-BASED TI SCHEME FOR PAPR REDUCTION

(8)

and . Fig. 1 illustrates this where expanded constellation for 16-QAM, in which constellations in-

The CE method is an iterative algorithm for combinatorial optimization [10]. The basic steps for each iteration consist of generating a random sample according to a probability distribution and then updating the parameters of the probability distribution to produce better samples in the next iteration. For a thorough discussion of the CE method and its applications, please refer to

CHEN AND WEN: PAPR REDUCTION OF OFDM SIGNALS

729

[10]. Next, we elaborate the step-by-step procedure of the prothat minimizes posed CE algorithm to search for the optimal the PAPR as follows. and initialize the • Step 1) Set the iteration counter probability vector with for all , where indicates the probability of the th input symbol, which is chosen to be shifted to its expanded constellation, and the superindex of denotes the iteration index. to generate • Step 2) Use the density function random samples , where is the sample size, is modeled as an independent and each element of Bernoulli random variable with the probability distribufor tion . The probability distribution is defined as (11) where the indicator function shows whether the th input symbol is chosen to be shifted to its equivalent constellation or not. • Step 3) Calculate the fitness function according to (10) to and obtain a set of performance values rank them in ascending order so that . Then, set , where denotes the fraction of is the ceiling operathe best samples and the operation tion. to calcu• Step 4) Use the same samples late the parameter according to (12) where by

is an indicated variable defined

(13) • Step 5) Update the parameter

smoothly via (14)

. where is the smoothing parameter, with • Step 6) If the stopping criterion is not reached, then set and go back to Step 2. Here, the stopping criterion is the predefined number of iterations. IV. NUMERICAL RESULTS Simulation experiments are conducted in this section to verify the PAPR performance of the proposed CE-based TI subscheme. We assume OFDM systems with carriers, in which the transmit signal is oversampled by a OFDM blocks are generated randomly factor of 4 and to obtain the complementary cumulative distribution function of the PAPR. For comparison, the conventional selected mapping (SLM) scheme [4] is also tested, where patterns of distinct sign sequences are gen, and the pattern with erated randomly from the set

Fig. 2. PAPR reduction comparison of CE-based TI and SLM methods with and 16-QAM.

N = 256

the lowest PAPR is selected for transmission. SLM is chosen for comparison because it is simple to implement and can achieve significant PAPR reduction with low complexity. In terms of the parameters used in the CE, the smoothing parameter is , and the algorithm is stopped when the iteration 0.81, number exceeds the predetermined value. In this case, the total number of samples for the CE is population size, , times . It should the maximum generation value, ; that is, be noted that the complexity of CE for each sample to find a due to the -point IFFT suboptimal solution is operations, which is of the same order as SLM. Accordingly, the complexity for CE and SLM with samples for finding a , which is much less than suboptimal solution is the complexity required for the optimal TI scheme. Figs. 2 and 3 show the performance of the PAPR reduction using SLM and the proposed CE-based TI schemes when 16-QAM and 64-QAM are employed, respectively. For 16-QAM, with the number of distinct sign sequences , and , the suppressed PAPRs of SLM are 7.26, 7.06, 7.00, and at 6.94 dB, respectively. For 64-QAM, with number of distinct , 640, 960, and 1280, the PAPRs of sign sequences are reduced to 7.08, SLM at 6.93, 6.88, and 6.82 dB, respectively. Next, after performing the proposed CE-based TI scheme, the PAPR of the OFDM is signal with 16-QAM at suppressed by 7.69, 7.22, 6.68, and 6.50 dB when the number , and , respectively, where of samples the population size of the CE is assumed to be 32, and the corresponding maximum numbers of generations are 5, 10, 15, and 20, respectively. On the other hand, the PAPR of CE is suppressed with 64-QAM at by 7.44, 7.06, 6.66, and 6.26 dB when the number of samples , and , respectively, where the population size of the CE in this case is assumed to be 64, and the corresponding maximum numbers of generations are 5,

 = 0:8

1The reasons for choosing are based on the following: the recommendation of [10], which suggests the range for the design of , and our simulation experience for this problem.

0:7 <  < 1

730

Fig. 3. PAPR reduction comparison of CE-based TI and SLM methods with and 64-QAM.

N = 256

IEEE SIGNAL PROCESSING LETTERS, VOL. 17, NO. 8, AUGUST 2010

it reaches the optimal solution. Moreover, the phase rotation of every subcarrier in SLM must be transmitted to allow for the rebits covery of the data block at the receiver side, and thus of side information is required. In this case, the major serious problem in SLM method for PAPR reduction is how to handle the side information about phase rotation information. The probability of erroneous side information detection has a significant influence on the bit error rate performance of the system since the whole data block is lost every time the receiver does not detect the correct side information. However, the proposed CE-based TI scheme does not require extra side information and does not have data rate loss. Most importantly, compared , to the the optimal TI scheme with complexity of order . It the complexity of our proposed algorithm is should be noted that the common drawback of TI scheme is that it requires an increase in the transmission power. To make this increased power to be as low as possible, in the proposed CE-based TI scheme, only constellations located on the outer ring could be shifted and the constellations closer to the original of the original constellation would not be shifted, because shifting them would result in a greater power increase. V. CONCLUSION This letter presented a CE-based TI scheme that was used to reduce computational complexity and improve PAPR performance for OFDM signals. The TI scheme was formulated as a particular combination optimization problem, and then the CE method was applied to solve the problem. Simulation results showed that the performance of the proposed CE-based TI scheme not only achieved significant PAPR reduction but also enjoyed complexity advantages. REFERENCES

Fig. 4. (a) PAPR reduction comparison of CE-based TI and SLM for the same complexity with 16-QAM and (b) PAPR reduction comparison of CE-based TI and SLM for the same complexity with 64-QAM.

10, 15, and 20, respectively. As expected, PAPR performance improves with an increase in the number of samples for both SLM and CE. In addition, after the same number of enumeration (samples), the proposed CE converges close to a global minimum. However, SLM is easily trapped into local solutions. It turns out that the PAPR is not reduced sufficiently even when is large. Finally, regarding the complexity issue of the proposed algorithm, Fig. 4(a) and (b) plot the average PAPR reduction performance versus the same complexity for SLM and the proposed CE with 16-QAM and 64-QAM, respectively. It can be seen that the convergence speed of the proposed CE-based TI scheme is low at the initial stage (i.e., when the total number of samples is small) because there is not enough elite samples to produce better samples in the next iteration. As a result, the proposed CE-based TI performs slightly worse than SLM with a lower value of the total number of samples . However, after this initial stage, the convergence speed improves greatly until

[1] S. H. Han and J. H. Lee, “An overview of peak-to-average power ratio reduction techniques for multicarrier transmission,” IEEE Wireless Commun., vol. 12, no. 2, pp. 56–65, 2005. [2] T. Jiang and Y. Wu, “An overview: Peak-to-average power ratio reduction techniques for OFDM signals,” IEEE Trans. Broadcast., vol. 54, no. 2, pp. 257–268, June 2008. [3] S. H. Müller and J. B. Huber, “OFDM with reduced peak-to-average power ratio by optimum combination of partial transmit sequences,” Electron. Lett., vol. 33, no. 5, pp. 368–369, Feb. 1997. [4] R. W. Bäuml, R. F. H. Fisher, and J. B. Huber, “Reducing the peak-toaverage power ratio of multicarrier modulation by selected mapping,” Electron. Lett., vol. 32, no. 22, pp. 2056–2257, Oct. 1996. [5] T. Jiang, W. Xiang, P. C. Richardson, J. Guo, and G. Zhu, “PAPR reduction of OFDM signals using partial transmit sequences with low computational complexity,” IEEE Trans. Broadcast., vol. 53, no. 3, pp. 719–724, Sept. 2007. [6] J.-C. Chen, “Partial transmit sequences for peak-to-average power ratio reduction of OFDM signals with the cross-entropy method,” IEEE Signal Process. Lett., vol. 16, no. 6, pp. 545–548, Jun. 2009. [7] J.-C. Chen and C.-K. Wen, “A low-complexity scheme to reduce the PAPR of an OFDM signal using sign-selection algorithms,” IEEE Signal Process. Lett., vol. 17, no. 2, pp. 189–192, Feb. 2010. [8] J. Tellado, “Peak to Average Power Reduction for Multicarrier Modulation,” Ph.D. dissertation, Stanford Univ., Stanford, CA, 2000. [9] J. Tellado, Multicarrier Modulation With Low PAR: Applications to DSL and Wireless. Boston, MA: Kluwer , 2000. [10] R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method. Berlin, Germany: Springer, 2004. [11] M. Ohta, Y. Ueda, and K. Yamashita, “PAPR reduction of OFDM signal by neural networks without side information and its FPGA implementation,” Inst. Elect. Eng., J. Trans. Electron. Inf. Syst., vol. 126, no. 11, pp. 1296–1303, 2006.