An overview of peak-to-average power ratio reduction schemes for OFDM signals

Orthogonal frequency division multiplexing (OFDM) has been adopted as a standard for various high data rate wireless communication systems due to the spectral bandwidth efficiency, robustness to frequency selective fading channels, etc. However, implementation of the OFDM system entails several difficulties. One of the major drawbacks is the high peak-to-average power ratio (PAPR), which results in intercarrier interference, high out-of-band radiation, and bit error rate performance degradation, mainly due to the nonlinearity of the high power amplifier. This paper reviews the conventional PAPR reduction schemes and their modifications for achieving the low computational complexity required for practical implementation in wireless communication systems.

SECTION I. Introduction

Recently, orthogonal frequency division multiplexing (OFDM) has been regarded as one of the core technologies for various communication systems. Especially, OFDM has been adopted as a standard for various wireless communication systems such as wireless local area networks [1], wireless metropolitan area networks, digital audio broadcasting, and digital video broadcasting. It is widely known that OFDM is an attractive technique for achieving high data transmission rate in wireless communication systems and it is robust to the frequency selective fading channels [2]. However, an OFDM signal can have a high peak-to-average power ratio (PAPR) at the transmitter, which causes signal distortion such as in-band distortion and out-of-band radiation due to the nonlinearity of the high power amplifier (HPA) and a worse bit error rate (BER) [3]. In general, HPA requires a large backoff from the peak power to reduce the distortion caused by the nonlinearity of HPA and this gives rise to a low power efficiency, which is a significant burden, especially in mobile terminals. The large PAPR also results in the increased complexity of analog-to-digital converter (ADC) and digital-to-analog converter (DAC). Thus, PAPR reduction is one of the most important research areas in OFDM systems.

PAPR reduction schemes can be classified according to several criteria. First, the PAPR schemes can be categorized as multiplicative and additive schemes with respect to the computational operation in the frequency domain. Selected mapping (SLM) and partial transmit sequences (PTS) are examples of the multiplicative scheme because the phase sequences are multiplied by the input symbol vectors in the frequency domain [4]. On the other hand, tone reservation (TR) [5], peak canceling, and clipping [6] are additive schemes, because peak reduction vectors are added to the input symbol vector.

Second, the PAPR reduction schemes can be also categorized according to whether they are deterministic or probabilistic. Deterministic schemes, such as clipping and peak canceling, strictly limit the PAPR of the OFDM signals below a given threshold level. Probabilistic schemes, however, statistically improve the characteristics of the PAPR distribution of the OFDM signals avoiding signal distortion. SLM and PTS are examples of the probabilistic scheme because several candidate signals are generated and that which has the minimum PAPR is selected for transmission.

Besides the PAPR reduction schemes, the single carrier frequency division multiple access (SC-FDMA) scheme has been proposed for alleviating the PAPR problem in uplink transmission. The SC-FDMA is a adopted multiple access scheme for uplink transmission in the long term evolution (LTE) of cellular systems by the third generation partnership project (3GPP). It is clear that the PAPR of SC-FDMA is lower than that of OFDMA, because SC-FDMA transmits the input symbols sequentially using a single carrier, while OFDMA transmits the input symbols in parallel.

There have been several papers summarizing the PAPR reduction schemes [7]–​[9]. In these papers, PAPR reduction schemes are compared according to various criteria, which include the PAPR reduction capability, average power increase, BER degradation, data rate loss, computational complexity, and out-of-band radiation. Jiang and Han briefly deal with the issues of PAPR in the multiuser OFDM systems [7], [8]. In [9], it is mentioned that the low complexity PAPR reduction schemes may be applicable to mobile communication systems.

Although numerous schemes have been proposed to solve the PAPR problem, no specific PAPR reduction scheme can be considered as the best solution. Since the criteria involve trade-offs, it is needed to compromise the criteria to meet the system requirements. The aim of this paper is to review the conventional PAPR reduction schemes and the various modifications of the conventional PAPR reduction schemes for achieving a low computational complexity

Fig. 1. OFDM transmitter.

This paper is organized as follows: Section II defines PAPR and analyzes the characteristics of PAPR. Then, we investigate the conventional PAPR reduction schemes in Section III. Modifications of the conventional PAPR reduction schemes with a low computational complexity are presented and the numerical results are discussed in Section IV. Finally, the concluding remarks are given in Section V.

SECTION II. OFDM System Model and PAPR

A. OFDM System Model

Let ${\bf A}=[A_{0}A_{1}\cdots A_{N-1}]^{T}$ denote an input symbol vector in the frequency domain, where $A_{k}$ represents the complex data of the $k$th subcarrier and $N$ is the number of subcarriers. The input symbol vector is also called the input symbol sequence. The OFDM signal is generated by summing all the $N$ modulated subcarriers each of which is separated by $1/Nt_{s}$ in the frequency domain, where $t_{s}$ is the sampling period. Then, a continuous time baseband OFDM signal is defined as $$a_{t}={1\over \sqrt{N}}\sum_{k=0}^{N-1}A_{k}e^{j2\pi{k\over Nt_{S}}t}, 0\leq t < Nt_{s}.$$ The discrete time baseband OFDM signal $a_{n}$ sampled at the Nyquist rate $t=nt_{s}$ can be given as $$\alpha_{n}={1\over \sqrt{N}}\sum_{k=0}^{N-1}A_{k}e^{j2\pi{k\over N}n}, n=0,1, \cdots, N-1.$$

Let a $=[a_{0}a_{1}\cdots a_{N-1}]^{T}$ denote a discrete time OFDM signal vector. Then, a corresponds to the inverse fast Fourier transform (IFFT) of ${\bf A}$, that is, ${\bf a}={\bf QA}$, where ${\bf Q}$ is the IFFT matrix. The block diagram of OFDM transmitter is described in Fig. 1.

Let ${\bf a}_{L}=[\alpha_{0,L}\alpha_{1,L}\ldots a_{LN-1,L}]^{T}$ be an oversampled discrete time OFDM signal vector where $\alpha_{n,L}$ is the oversampled discrete time OFDM signal sampled at $t=nt_{s}/L$ written as $$a_{n,L}={1\over \sqrt{N}}\sum_{k=0}^{LN-1}A_{k}^{\prime}e^{j2\pi{k\over LN}n}, n=0,1, \cdots, {LN}-1$$ where $A_{k}^{\prime}$ is $${\cal A}_{k}^{\prime}=\cases{A_{k}, &$0\leq k\leq N-1,$\cr 0, &$N\leq k\leq LN-1$.}.$$

Continuous time baseband OFDM signals can be approximately represented by $L$ times oversampled discrete time baseband OFDM signals. It is shown in [10] that choosing $L=4$ is sufficient to approximate the peak value of the continuous time OFDM signals.

B. Peak-to-Average Power Ratio

The PAPR of the discrete time baseband OFDM signal is defined as the ratio of the maximum peak power divided by the average power of the OFDM signal [4], that is, $${\rm PAPR}(a_{n})\triangleq{\max\limits_{0\leq n\leq N-1} \vert a_{n}\vert^{2} \over P_{av}(a_{n})} \eqno{\hbox{(1)}}$$ with $$P_{av}(\alpha_{n})={1\over N}\sum_{n=0}^{N-1}{\rm E}\{\vert a_{n}\vert^{2}\} \eqno{\hbox{(2)}}$$ where ${\rm E}\{\cdot\}$ denotes the expected value. For the uncoded OFDM system, we can assume that the input symbols are identically and independently distributed, that is, $${\rm E}\{A_{i}A_{j}^{\ast}\}=\cases{\sigma^{2}, &$i=j,$\cr 0, &$i\neq j.$}$$ From Parseval's theorem, the average power $P_{av}({\bf a})$ in (2) is $\sigma^{2}$.

An alternative measure of the envelope variation of the OFDM signals is the crest factor $\zeta$ which is the ratio of the maximum to the root mean square of the signal envelope, defined as $$\zeta(a_{n})\triangleq{\max\limits_{0\leq n\leq N-1}\vert a_{n}\vert \over \sqrt{P_{av}(a_{n})}}$$

The PAPR of the continuous time baseband OFDM signal $a_{t}$ defined as the ratio of the maximum instantaneous power divided by the average power of the OFDM signal, can be expressed as $${\rm PAPR} (a_{t})\triangleq{\max\limits_{0\leq t < Nt_s}\vert a_{t}\vert^{2} \over P_{av}(a_{t})}$$ where $$P_{av}(a_{t})={1\over Nt_{s}}\int_{0}^{Nt_{s}}{\rm E}\{\vert a_{t}\vert^{2}\}dt.$$

And the PAPR of the continuous time passband OFDM signal $g_{t}$ is also defined as $${\rm PAPR} (g_{t})\triangleq{\max\limits_{0\leq t< Nt_{s}}\vert g_{t}\vert^{2} \over{P_{av}(g_{t})}}.$$

The discrete time baseband OFDM signals, which constitute the output of the IFFT block, are transformed to continuous time baseband OFDM signals by a low-pass filter called DAC, where the peak power can be increased while maintaining a constant average power. Usually, the PAPR of the continuous time baseband OFDM signals is larger than that of the discrete time baseband OFDM signals by $0. 5\sim 1.[$ dB [10], [11].

Mixing the continuous time baseband OFDM signal with the radio frequency generates the continuous time passband OFDM signal. It does not change the peak power but the average power of the passeband OFDM signal is half the average power of the continuous time baseband OFDM signal. Thus, the PAPR of the continuous time passband signal is generally larger than that of the continuous time baseband OFDM signal by 3 dB. Then, the relationship between PAPRs is given as $${\rm PAPR} (a_{n})\leq {\rm PAPR}(\alpha_{t})<{\rm PAPR}(g_{t})$$ .

In some literature on coding schemes, the peak-to-mean envelope power ratio (PMEPR) also denotes the PAPR of the continuous time baseband OFDM signals [12]. For a code $\Omega$ and any codeword ${\bf A} \in\Omega$ with the probability $p({\bf A})$, the mean envelope power of the continuous time baseband OFDM signals is expressed as $$P_{av}(\alpha_{t})\triangleq P_{av}({\bf A})={{\rm E}(\vert\vert {\bf A}\vert\vert^{2}) \over N}={1\over N}\sum_{{\bf A}\in\Omega}\vert\vert {\bf A}\vert\vert^{2}p({\bf A})$$ where $a_{t}$ is the continuous time baseband OFDM signal corresponding to the codeword $\bf A$ and $\vert\vert {\bf A}\vert\vert$ denotes the vector norm of ${\bf A}$. Then, based on the above definition, the PMEPR of the codeword. ${\bf A}$ can be defined as $${\rm PMEPR}({\bf A}) \triangleq{\max\limits_{0 \leq t < Nt_{s}}\vert a_{t}\vert^{2} \over P_{av}({\bf A})}.$$ The PMEPR of a code $\Omega$ is also defined as $${\rm PMEPR}({\Omega}) \triangleq\max_{{\bf A}\in \Omega}{\max\limits_{0 \leq t < Nt_{s}}\vert a_{t}\vert^{2} \over P_{av}({\bf A})}.$$

C. Distribution of PAPR

In this subsection, we explain the distribution of PAPR of discrete time baseband OFDM signals. Here, OFDM signal means a discrete time baseband OFDM signal. For a large number of $N$ subcarriers, an OFDM signal $a_{n}$ can be modeled as a zero-mean asymptotically complex Gaussian distributed random variable, because it is a superposition of a large number of modulated signals. Then, $\vert \alpha_{n}\vert$ has a Rayleigh distribution. If we assume that $\vert a_{n}\vert$ 's are statistically independent, the probability that the PAPR of the Nyquist-rate sampled OFDM signals exceeds a given threshold $\xi_{0}$ can be calculated as $${\Pr}(\xi>\xi_{0})=1-(1-\exp\left(-\xi_{0})\right)^{N} \eqno{\hbox{(3)}}$$ where $\xi=$ PAPR $(a_{n})$. Even though we assume that $a_{n}$ 's are statistically independent, $\vert \alpha_{n}\vert$ 's are not statistically independent. But, the numerical analysis for $N\geq 128$ shows that the approximation of the statistical independence of $\vert a_{t}\vert$ 's is quite accurate.

Based on the level crossing rate analysis [13], Ochiai and Imai derived a simple closed-form approximation for the distribution of PAPR for the band-limited baseband OFDM system, defined as $${\Pr}(\xi>\xi_{0})\approx 1-\exp\left[-\sqrt{{\pi\over 3}}N\xi_{0}\exp(-\xi_{0}^{2})\right]. \eqno{\hbox{(4)}}$$ The distribution obtained from (4) is quite accurate for $N\geq 100$ and for the relatively large value $\xi_{0}$.

D. High Power Amplifier Models

In the complex baseband representation of the modulated signals [14], the input-output relationship of HPA can be expressed in the form of complex envelopes as $$u_{t}={\alpha_{t}g(r)e^{j\Phi(r)} \over r}$$ where $a_{t}$ is a complex baseband OFDM signal and $r=\vert a_{t}\vert$. The AM/ AM and AM/PM conversion functions of the traveling wave tube amplifier (TWTA) model are obtained via an approximation using the amplitude and phase functions given as $$g(r)={\alpha_{g}r \over 1+\beta_{g}r^{2}}$$ and $$\Phi(r)={\alpha_{\Phi}r \over 1+\beta_{\Phi}r^{2}}$$ where $\alpha_{g}, \beta_{g}, \alpha_{\Phi}$, and $\beta_{\Phi}$ determine the characteristics of TWTA.

In general, the solid state power amplifier (SSPA) (which is mostly realized using GaAs-FET's) has a linear region larger than that of TWTA. For large inputs, the AM/ AM conversion function $g(r)$ approaches the saturation (maximum) value produced by current and voltage clipping. The AM/PM conversion of SSPA is assumed to be so small that it can be neglected and the AM/ AM conversion function $g(r)$ of SSPA is expressed as $$g(r)={vr\over \left(1+\left({v \over r_{0}}r\right)^{2p}\right)^{1 \over 2p}}, p>0, r_{0}>0, \,\,{\rm and}\,\, v>0 \eqno{\hbox{(5)}}$$ where $r_{0}$ is the limiting output amplitude, $v$ is the small signal gain, and $p$ determines the smoothness of the transition from the linear region to the limiting region.

The third HPA model can be represented as an idealized amplifier, which could be obtained when a real amplifier is ideally linearized by a predistortion unit [15], [16]. That is, the AM/AM conversion function is ideally linear up to the limiting output amplitude, where it remains constant and the AM/PM conversion function is zero. This AM/AM conversion function is the limiting case of (5) as $p\rightarrow\infty$, that is, $$\lim_{p\rightarrow\infty}g(r)=\cases{vr_{0}, &$r>r_{0}$\cr vr, &$r\leq r_{0}$.}$$

SECTION III. PAPR Reduction Schemes

Numerous schemes have been developed to reduce the PAPR of OFDM signals, which is one of the major drawbacks in multicarrier systems. In this section, we investigate the conventional PAPR reduction schemes using some examples and discuss related optimization problems as well as the advantages and disadvantages in terms of the PAPR reduction capability, computational complexity, BER degradation, power increase, etc.

A. Clipping

Clipping is the simplest way to reduce the peak signal to a desired level [17], [18]. The output signal of a soft limiter can be written as $$\bar{\alpha}_{n}=\cases{a_{n}, &$\vert a_{n}\vert < A_{{\rm th}}$\cr A_{{\rm th}}e^{j\phi(a_{n})}, &$\vert a_{n}\vert \geq A_{{\rm th}}$}\eqno{\hbox{(6)}}$$ where $A_{{\rm th}}$ is the clipping level and $\phi(\alpha_{n})$ represents the phase of $\alpha_{n}$. Although this scheme ensures peak reduction, it has two main drawbacks. First, clipping generates self interference by distorting the signal amplitude which increases BER. It also gives rise to regrowth of the high frequency components and thus the spectral efficiency is reduced.

Several schemes have been developed to overcome these problems in the clipping method. Although filtering can reduce or remove out-of-band radiation, it can also cause peak regrowth. Therefore, iterative clipping and filtering scheme is needed to obtain the desired PAPR reduction, but this requires additional computational complexity [19]–​[21].

Peak windowing is a method to reduce the peak value by multiplying the correcting function by the original OFDM signal [11], [22]. The correcting function is the shaped window that must have a narrow impulse response in the time domain and its frequency spectrum must be close to rectangular in the in-band frequency. Gaussian, Kaiser, and cosine filters are examples of correcting functions. This scheme suppresses out-of-band radiation while reducing the peak signal, but the peak reduction worsens as the number of peak signals that need to be windowed increases.

There are several schemes for reducing these problems at the receiver, which are inherently generated by clipping. In [23], it is shown that signals affected by clipping can be reconstructed by estimation and cancelation of clipping noise at the receiver.

B. Nonlinear Processing

Nonlinear characteristics generated by passing through DAC and HPA can be mitigated by nonlinear processing before OFDM signals are converted to analog signals. The nonlinear companding and decompanding transform is the scheme where the input signal to DAC is nonlinearly scaled by suppressing signals with large amplitudes and expanding signals with small amplitudes [24]. At the receiver, the original signal is recovered from the companded signal via the decompanding process, which is the inverse operation of the companding process after ADC. It has been suggested that non-symmetric decompanding can improve BER performance for band-limited OFDM systems [25].

The predistortion technique estimates nonlinear characteristics of DAC and HPA and inserts its inverse process before DAC. It aims to transform nonlinear output to linear output at HPA. Unlike the companding scheme, it does not need any additional blocks at the receiver. There are several schemes for implementing the predistortion scheme. Look-up-table [15], [26], stochastic gradient [27], [28], and recursive least square based methods [29], [30] are adaptive predistorters which process the time domain signals. But, it is very important to compensate for the time delay from the feedback loop to the analog filter. Thus, it has been suggested that a predistorter in the frequency domain can overcome this drawback [31].

C. Coding

Block coding, which encodes an input data to a codeword with low PAPR, is one of the well-known techniques for reducing PAPR. For example, we can reduce the PAPR of OFDM signals with four subcarriers, simply by mapping three-bit input data to four-bit codeword, where a parity is added to the last bit in the frequency domain.

Another well known example is the Golay complementary sequence. The use of Golay complementary sequences as codewords ensures that the OFDM signals have PAPR of at most 3 dB [32]. Ordinary Golay complementary sequences can be used for OFDM signals with phase shift keying (PSK) modulation. Recently, a method of constructing Golay complementary sequences for OFDM signals with 64-quadrature amplitude modulation (QAM) constellation has been proposed [33]. Although Golay complementary sequences have good error correction as well as relatively small PAPR, they incur a significant rate loss.

D. Partial Transmit Sequences

The main principle of the PTS scheme is that an input symbol vector ${\bf A}$ is partitioned into $V$ disjoint symbol subvectors ${\bf A}_{v}= [A_{v,0}A_{v,1}\cdots A_{v,N-1}]^{T},v=1,2, \cdots, V$ as follows [4] $${\bf A}=\sum_{v=1}^{V}{\bf A}_{v}. \eqno{\hbox{(7)}}$$

Here, ‘disjoint’ implies that for each $k, 0\leq k\leq N-1, A_{v,k}= 0$ except for a single $v$. In other words, the support sets of ${\rm A}_{1}$ 's are disjoint. The signal subvector ${\bf a}_{v}=[a_{v0}\alpha_{v.1}\cdots a_{v.N-1}]^{T}$ is generated by applying IFFT to each symbol subvector ${\bf A}_{v}$, also known as a subblock. Each signal subvector ${\bf a}_{v}$ is then multiplied by a unit magnitude constant $r_{v}^{w}$. chosen from a given alphabet ${\cal Z}$, which is usually ${\cal Z}=\{\pm 1\}$ or ${\cal Z}=\{\pm 1, \pm j\}$. Then, they are summed, which results in a PTS OFDM signal vector ${\bf a}^{w}=[a_{0}^{w}\alpha_{1}^{w}\cdots a_{N-1}^{w}]^{T}$ given as $${\bf a}^{w}=\sum_{v=1}^{V}r_{v}^{w}{\bf a}_{v}$$ where ${\bf r}^{w}=\lceil r_{1}^{w}r_{2}^{w}\cdots r_{V}^{w}], 1\leq w\leq W, W=\vert {\cal Z}\vert^{V-1}$, is called a rotating vector. The PAPR of ${\bf a}^{w}$ is computed for $W$ rotating vectors and compared. That which has the minimum PAPR is selected for transmission. The index $\tilde{w}$ of the corresponding rotating vector ${\bf r}^{\tilde{w}}$ is selected according to $$\tilde{w}=\arg\min_{1\leq w\leq W}\max_{0 \leq n\leq N-1}\left\vert \sum_{v=1}^{V}r_{v}^{w}a_{v,n}\right\vert.$$

The receiver must know the index information to recover the original input symbol vector.

The PAPR reduction performance and the computational complexity of the PTS scheme depend on the method of subblock partitioning. In other words, there is a trade-off between the PAPR reduction performance and the computational complexity in the PTS scheme [35].

The random partitioning method is known to have the best performance among PAPR reduction schemes for PTS. Although the interleaving method can reduce the computational complexity of the PTS scheme using the Cooley-Tukey FFT algorithm, it has the worst performance in terms of the PAPR reduction.

E. Selected Mapping

The SLM scheme statistically reduces PAPR but it has a slight increase in redundancy and completely avoids signal distortion [4], [34]. In this scheme, $U$ alternative input symbol vectors ${\bf A}^{u}=[{\cal A}_{0}^{u}{\cal A}_{1}^{u}\ldots {\cal A}_{N-1}^{u}]^{T}, 1\leq u\leq U$ are generated via componentwise vector multiplication of the input symbol vector ${\bf A}$ and $U$ phase sequences ${\bf P}^{u}=[P_{0}^{u}P_{1}^{u}\cdots P_{N-1}^{u}]^{T}$. We use the notation ${\bf A}^{u}={\bf A} \otimes {\bf P}^{u}$ to represent componentwise multiplication, i.e., $A_{k}^{u}=A_{k}P_{k}^{u}, 0\leq k\leq N-1$.

The phase sequence ${\bf P}^{u}$ is generated by using the unit-magnitude complex number, that is, $P_{k}^{u}=e^{j\phi_{k}^{u}}$, where $\phi_{k}^{u}\in [0,2\pi)$. In general, binary or quaternary elements are used for $P_{k}^{u}$, that is, $\{\pm 1\}$ or $\{\pm 1, \pm j\}$.

IFFT is performed for each of $U$ alternative input symbol vectors to generate $U$ alternative OFDM signal vectors as $${\bf a}^{u}={\bf QA}^{u}={\bf Q}({\bf A}\otimes {\bf P}^{u}),\quad 1\leq u\leq U \eqno{\hbox{(8)}}$$ where Q is the IFFT matrix. Then, the OFDM signal vector ${\bf a}^{\bar{u}}$ with the minimum PAPR among $U$ alternative OFDM signal vectors ${\rm a}^{v}$ is selected and transmitted, where the index $\tilde{u}$ of the transmitted vector is obtained by $$\bar{u} =\arg\min\limits_{1\leq u\leq U}(\max\limits_{0\leq n\leq N-1}\vert a_{u,n}\vert). \eqno{\hbox{(9)}}$$ In order to recover the original input symbol vector in the receiver, the transmitter must send the index information, which is known as side information and this causes a slight increase in redundancy.

Clearly, as $U$ increases, PAPR reduction become large while the computational complexity becomes too high, mainly due to $U$ IFFTs. It should be noted that there is a saturation effect, that is, the additional PAPR reduction gain decreases as $U$ increases.

F. Tone Reservation

The TR scheme is developed for digital subscriber line (DSL) system to reduce the PAPR. In the DSL system, subcarrier is also called as a tone. The TR scheme reserves some tones for generating a PAPR reduction signal instead of data transmission [36]. Let ${\cal R}=\{i_{1}, i_{2}, \cdots, i_{W}\}$ denote the ordered set of the positions of the reserved tones and ${\cal R}^{{\rm c}}$ denote the complement set of ${\cal R}$ in ${\cal N}=\{0,1, \cdots, N-1\}$, where $N$ and $W$ are numbers of subcarriers and reserved tones, respectively. The input symbol $A_{k}$ is expressed as $$A_{k}=X_{k}+C_{k}=\cases{C_{k}, &$k\in {\cal R}$\cr X_{k}, &$k\in {\cal R}^{{\rm c}}$}$$ where $X_{k}$ is the data symbol with 0 in the set ${\cal R}$ and $C_{k}$ is the PAPR reduction symbol with 0 in the set ${\cal R}^{{\rm c}}$. Let $a_{n}, x_{n}$, and $C_{n}$ be the IFFT signals of $A_{k}, X_{k}$, and $C_{k}$, respectively. Since the inverse Fourier transform is a linear operation, the OFDM signal $a_{n}$ corresponds to the summation of the data signal $x_{n}$ and the PAPR reduction signal $c_{n}$, i.e., $a_{n}=x_{n}+c_{n}$. In the TR scheme, PAPR is defined as $${\rm PAPR}({\bf a}) ={\max\limits_{0\leq n\leq N-1} \vert x_{n}+c_{n}\vert^{2}\over {1 \over N}\sum_{n=0}^{N-1}{\rm E}[\vert x_{n}\vert^{2}]}. \eqno{\hbox{(10)}}$$ It should be noted that the denominator is not ${1\over N}\sum_{n=0}^{N-1} E [\vert x_{n} +c_{n}\vert^{2}]$ rather it is ${1\over N}\sum_{n=0}^{N-1}{\rm E}[\vert x_{n}\vert^{2}$. Otherwise, PAPR can be reduced simply by increasing the average power of $c_{n}$.

Next, we consider the method of generation of peak reduction signals. Peak reduction signals are iteratively generated as follows. Let ${\bf p}=[p_{0}p_{1}\cdots p_{N-1}]^{T}$ be the time domain kernel defined by $$p_{n}={1\over \sqrt{N}}\sum_{k\in {\cal R}}P_{k}e^{j2\pi{k\over N}t}$$ where ${\bf P}=[P_{0}P_{1}\cdots P_{N-1}]^{T}$ is called a frequency domain kernel for the PAPR reduction with $P_{k}=0$ for $k\in {\cal R}^{{\rm c}}$. The time domain kernel ${\bf p}$ is used to compute the PAPR reduction signal sequence $c$ iteratively [5]. That is, the PAPR reduction signal sequence ${\bf c}^{l}$ at the $l$th iteration is obtained as $${\bf c}^{l}=\sum_{i=1}^{l}\alpha_{i}{\bf p}_{((\tau_{i}))} \eqno{\hbox{(11)}}$$ where ${\bf p}_{((\tau_{i})}$ denotes a circular shift of ${\bf p}$ by $\tau_{i}$ and $\alpha_{{\rm i}}$ is a complex scaling factor computed according to the threshold level and the maximum peak value at the $i$th iteration. The circular shift $\tau_{i}$ is determined as $$\tau_{i}=\arg\max_{0 \leq n \leq N-1}\vert x_{n}+c_{n}^{i-1}\vert.$$ Then, the OFDM signal in the TR scheme can be represented as $${\bf a}={\bf x}+{\bf c}^{l}. \eqno{\hbox{(12)}}$$ Because of the shift property of the Fourier transform, it is always the case that element of ${\bf Q}^{-1}{\bf p}_{((\tau_{i}))}$ and ${\bf C}^{l}={\bf Q}^{-1}{{\bf C}}^{l}$ are zero in ${\cal R}^{{\rm c}}$, where ${\bf Q}^{-1}$ is the FFT matrix. Thus, the iteratively generated PAPR reduction signal sequence does not affect the data symbols. If the maximum number of iterations is reached or the desired peak power is obtained, iteration stops. For simplicity, we assume that only one maximum peak of the OFDM signal is reduced per iteration in (12).

Fig. 2. Block diagram of the proposed PTS scheme with low computational complexity.

The PAPR reduction performance of the TR scheme depends on the selection of the PRT set $R$. But, this problem is known as NP-hard, because the kernel ${\bf p}$ must be optimized over all possible discrete sets ${\cal R}$. Thus, it cannot be solved for practical values of $N$. In [37], an efficient method is proposed for selecting a near optimal PRT set.

G. Tone Injection and Active Constellation Extension

The tone injection (TI) scheme maps each point of the original constellation into one of several equivalent points in the expanded constellation, which results in extra degrees of freedom and can be exploited for PAPR reduction [36].

The active constellation extension (ACE) method is another technique which changes the constellation to reduce the peak power. TI maps the data onto alternative constellations which are cyclically extended from the original constellation points. On the other hand, the ACE method maps the data located at the outer constellations onto arbitrary positions that do not decrease the minimum distance from the other constellation points. This can reduce PAPR and requires a slight increase of average transmit power, and it does not require changing or adding any blocks at the receiver.

The ACE algorithm is based on two convex problems of the peak level constrained signal set and ACE constrained signal set. It can be solved using two main algorithms. One is the projection onto convex set (POCS) method [38] and the other is the smart gradient project (SGP) method [39]. The POCS algorithm is the optimal solution, but it converges to the desired peak value too slowly. The SGP algorithm is suboptimal, but it efficiently reduces the peak value and has a small number of iterations. The SGP algorithm is based on the gradient project method, clipped signals are multiplied by the gradient step size determined by the approximate balancing of peak values per iteration. This algorithm is more suitable for smaller constellation sizes and larger OFDM block sizes because it has more degrees of freedom for constellation extension in these conditions.

ACE constraints to maintain the minimum distance may cause peak regrowth, which increases the average power and the amount of iterations. Allowing reverse extension can reduce peak regrowth to some extent, but it increases BER [40].

SECTION IV. Modified PAPR Reduction Schemes with Low Complexity

This section investigates the various modifications of the conventional PAPR reduction schemes for achieving low computational complexity.

A. PTS Scheme with Low Computational Complexity

The PAPR reduction performance of PTS schemes is better than that of the SLM schemes for a given computational complexity, but the redundancy of the PTS scheme is larger than that of the SLM scheme. As the number of subcarriers and the order of modulation increase, reducing the computational complexity becomes more important.

The conventional PTS scheme performs as many IFFT operations as the number of subblocks and requires an exhaustive search for the OFDM signal with the minimum PAPR over all combinations of rotating factors. This results in an exponential increase in the computational complexity, which is proportional to the number of subblocks. Many algorithms have been proposed for finding suboptimal rotating vectors [41], [42], which do not have an exponential increase in the complexity that depends on the number of subblocks.

In [43], a new PTS scheme was proposed for reducing the computational complexity of IFFTs. Unlike the conventional PTS scheme, where input symbol vectors are partitioned at the initial stage, the proposed PTS scheme performs block partitioning after the first $l$ stages of IFFT. In this scheme, the $2^{n}$-point IFFT based on the decimation-in-time algorithm is divided into two parts. The first part is the first $l$ stages of IFFT. The second part is the remaining $n-l$ stages. In the first $l$ stages of IFFT, the input symbol vector ${\bf A}$ is partially IFFT-ed to form an intermediate signal vector $\hat{{\bf a}}$, This intermediate signal vector is partitioned into $V$ intermediate signal subvectors and then, the remaining $n-l$ stages of IFFT are applied to each of the intermediate signal subvectors.

Let ${\bf T}_{i}$ be an $N\times N$ symmetric matrix representing the $i$th stage of IFFT and ${\bf Q}_{i}^{j}={{\bf T}}_{i}{\bf T}_{i-1}\cdots {\bf T}_{i+1}{\bf T}_{i},j \geq i$. Then, the $N=2^{n}$ point IFFT matrix ${\bf Q}$ can be expressed as ${\bf Q}={\bf Q}_{0}^{n-1}$.

Compared to the conventional PTS scheme, the computational complexity of the proposed PTS scheme is lower, because there is a common intermediate signal vector $\hat{{\bf a}}={\bf Q}_{0}^{l-1}{\bf A}$ for IFFT of $V$ symbol subvectors. When the number of subcarriers is $N=2^{n}$, the numbers of complex multiplications $n_{{\rm mu}1}$ and complex additions $n_{{\rm ad}{\rm d}}$ of the conventional PTS scheme are given by $n_{mul}=2^{n-1}nV$ and $n_{{\rm add}}=2^{n}nV$, respectively, where $V$ is the number of subblocks. If the intermediate signal is partitioned after the $l$th stage of IFFT, it is clear that the numbers of complex computations of the proposed PTS scheme are given as $n_{\rm mul}1=2^{n-1}n+2^{n-1}(n-l)(V-1)$, and $n_{{\rm add}}=2^{n}n+2^{n}(n-l)(V-1)$. Thus, the computational complexity reduction ratio (CCRR) of the proposed PTS scheme over the conventional PTS scheme is defined as $$\eqalignno{{\rm CCRR} &=(1-{{\rm complexity}\,\,{\rm of}\, \,{\rm new}\,\,{\rm PTS} \over {\rm complexity}\,\,{\rm of}\,\, {\rm conventional}\,\,{\rm PTS}})\times 100\cr &=(1-{1\over V}){l\over n}\times 100\ (\%).}$$

It is shown that the optimal value for $n-l$ does not depend on the number of subcarriers and it is around five when the number of subcarriers is between 256 and 8192. In the case of $N= 2048,V=8$, and $n-l=5$, the proposed PTS scheme reduces the computational complexity by 48% while the proposed PTS scheme has almost the same PAPR reduction performance as that of the conventional one.

B. SLM Scheme with Low Computational Complexity

In this subsection, we investigate three modified SLM schemes with low computational complexity.

1. FFT Partitioning Scheme

A new SLM scheme with low computational complexity is proposed in [44]. This is a method for applying the SLM scheme to the intermediate stage of IFFT rather than the first stage as in the previous subsection. In this scheme, the $N$ point IFFT based on decimation-in-time algorithm is partitioned into two parts, i.e., the first $l$ stages and the remaining $n-l$ stages. To make alternative OFDM signals, we multiply the different $U$ phase sequences, ${\bf P}^{u}, 1\leq u\leq U$, using the signal in the intermediate $l$th stage of IFFT. Based on the proposed SLM scheme, the computational complexity is reduced compared to the conventional SLM scheme, because it uses a common IFFT upto $l$ stages and then the SLM scheme is applied to the intermediate stage IFFTed signals.

Since the proposed SLM scheme is performed using a stage-by-stage IFFT approach, we denote $i$th stage of IFFT as ${\bf T}_{i}$. The computational complexity can be reduced by the common IFFT operation ${\bf Q}_{0}^{l-1}={\bf T}_{l-1}{\bf T}_{l-1}\cdots {\bf T}_{0}$. The output signal corresponding to the phase sequence in the proposed SLM scheme $\tilde{{\bf a}}$ can be expressed as $$\tilde{{\bf a}}={\bf T}_{n}\cdots {\bf T}_{k+1}\tilde{{\bf P}}{\bf T}_{k}\cdots {\bf T}_{1}{\bf A} \eqno{\hbox{(13)}}$$ where $\tilde{{\bf P}}$ is a $2^{n-l}\times 2^{n-l}$ diagonal block matrix, i.e., each $2^{l}\times 2^{l}$ subblock of $\tilde{{\bf P}}$ is either $\pm {\bf I}_{2^{l}}$. Here, ${\bf I}_{2^{l}}$ is the $2^{l}\times 2^{l}$ identity matrix.

When the number of subcarriers is $N=2^{n}$, the numbers of complex multiplications $n_{{\rm mu}1}$ and complex additions $n_{{\rm ad}{\rm d}}$ of the conventional SLM scheme are given by $n_{{\rm mu}1}=2^{n-1}nU$ and $n_{{\rm ad}{\rm d}}=2^{n}nU$, respectively, where $U$ is the total number of phase sequences. If the phase sequences are multiplied after the $l$th stage of IFFT, the numbers of complex computations of the proposed SLM scheme are given by $n_{{\rm mu}1}=2^{n-1}n+2^{n-1}(n- {l}) (U-1)$ and $n_{{\rm add}}=2^{n}n+2^{n}(n-l)(U-1)$.

The proposed SLM scheme has almost the same PAPR reduction performance as that of the conventional SLM scheme for $n-l=5$ and 16-QAM constellation. In the case of $n-l=5$, the proposed SLM OFDM system reduces the computational complexity by $41\sim 51\%$ as $U$ increases from 4 to 16.

2. Alternative OFDM Signal Combining Scheme

In order to achieve a large PAPR reduction in the conventional SLM scheme, we have to generate a sufficiently large number of alternative OFDM signal vectors, which cause a high computational complexity because IFFT must be performed to generate each alternative OFDM signal vector. Therefore, it is desirable to reduce the number of IFFTs and avoid degradation of the PAPR reduction performance [45].

Let ${\bf a}^{i}$ and ${\bf a}^{k}$ be the alternative OFDM signal vectors, generated by the conventional SLM scheme as in (8). Based on linear property of the Fourier transform, the linear combination of these two vectors can be given as $$\eqalignno{{\rm a}^{i,k}&=c_{i}{\bf a}^{i}+c_{k}{\bf a}^{k} \cr &=c_{i}{\bf Q}({\bf A}\otimes {\bf P}^{i})+c_{k}{\bf Q}({\bf A}\otimes {\bf P}^{k})\cr &={\bf Q}({\bf A}\otimes(c_{i}{\bf P}^{{\rm i}}+c_{k}{\bf P}^{k})) &{\hbox{(14)}}}$$ where $c_{i}$ and $c_{k}$ are complex numbers. If each element of the vector $c_{i}{\bf P}^{i}+c_{k}{\bf P}^{k}$ in (14) has a unit magnitude, $c_{{\rm i}}{\bf P}^{i}+c_{k}{\bf P}^{k}$ can be also used as a phase sequence for the SLM scheme and ${\bf a}^{i,k}$ can be considered as the corresponding alternative OFDM signal vector. Therefore, if we have alternative OFDM signal vectors ${\bf a}^{i}$ and ${\bf a}^{k}$, another alternative OFDM signal vector ${\bf a}^{i,k}$ can be obtained, which avoids the need for IFFT. Note that the phase sequence $c_{i}{\bf P}^{i}+c_{k}{\bf P}^{k}$ is not statistically independent of ${\bf P}_{i}$ and ${\bf P}^{k}$. Here, we investigate how to make each element of $c_{i}{\bf P}^{i}+c_{k}{\bf P}^{k}$ a unit magnitude, in the condition that each element of the phase sequences ${\bf P}^{i}$ and ${\bf P}^{k}$ has a unit magnitude. Clearly, the elements of the vector $c_{i}{\rm P}^{i}+c_{k}{\rm P}^{h}$ have a unit magnitude if the following conditions are satisfied:

1. Each element of ${\bf P}^{{i}}$ and ${\bf P}^{k}$ has a value in $\{+1,- 1\}$;

2. $c_{i}=\pm 1/\sqrt{2}$ and $c_{k}=\pm j/\sqrt{2}$.

Since the two alternative OFDM signal vectors generated from the phase sequences $\pm(c_{0}{\rm P}^{i}+{}_{ck}{\rm P}^{k})$ have the same PAPR, we only consider the case of $c_{i}=1/\sqrt{2}$ and $c_{k}=\pm{j}/\sqrt{2}$, Since $\vert c_{i}\vert^{2}=\vert c_{k}\vert^{2}=1/2$, the average power of ${\bf a}^{i,k}$ is equal to half the sum of the average power of ${\bf a}^{i}$ and ${\bf a}^{k}$. Using $U$ binary phase sequences, $2 {U \choose 2}$ additional phase sequences are obtained, where ${U \choose 2}=U(U-1)/2$. Thus, the total $U^{2}$ phase sequences are obtained as $$\eqalignno{&\{{\bf P}^{1}, {\bf P}^{2}, \cdots, {\bf P}^{U}, {1\over \sqrt{2}}({\bf P}^{1}\pm j{\bf P}^{2}),\cr & \qquad \quad {1\over \sqrt{2}}({\bf P}^{1}\pm j{\bf P}^{3}), \cdots, {1\over \sqrt{2}}({\bf P}^{U-1}\pm j{\bf P}^{U})\}.}$$

Fig. 3. Block diagram of the proposed SLM scheme with low computational complexity.

By combining each pair among $U$ alternative OFDM signal vectors ${\bf a}^{u}$ obtained by using $U$ binary phase sequences as above, a set ${\cal S}$ of $U^{2}$ alternative OFDM signal vectors is generated as $$\eqalignno{S &=\{{\bf a}^{u}\vert 1 \leq u \leq U^{2}\}\cr &=\{{\bf a}^{u}\vert 1 \leq u\leq U\}\cr &\cup\left\{{1\over \sqrt{2}}({\bf a}^{i}+j{\bf a}^{k}), {1\over \sqrt{2}}({\bf a}^{i}-j{\bf a}^{k})\vert 1\leq i < k\leq U\right\} {\hbox{(15)}}}$$ where only $U$ IFFTs and the additional summations of $U^{2}-U$ pairs of OFDM signal vectors are needed. However, the computational complexity for the summations of OFDM signal vectors is negligible compared with that of IFFT.

The modified SLM scheme with $U$ binary phase sequences can be compared with the conventional SLM scheme with $U^{2}$ binary phase sequences. These two schemes show a similar PAPR reduction performance for a small $U$. However, as $U$ increases, the PAPR reduction performance of the modified scheme becomes worse than that of the conventional SLM scheme with $U^{2}$ binary phase sequences, because $U^{2}$ phase sequences of the modified scheme are statistically correlated.

3. SLM Scheme with Conversion Matrix

Let $\hat{{\bf P}}^{u}= {\rm diag} (P_{1}^{u}, P_{2}^{u}, \cdots, P_{N-1}^{u})$ be an $N\times N$ diagonal matrix. Then, alternative OFDM signal vectors are written as $${\bf a}^{u}={\bf Q}\hat{{\bf P}}^{u}{\bf A}={\bf Q}\hat{{\bf P}}^{u}{\bf Q}^{-1}{\bf a}={\bf K}^{u}{\bf a} \eqno{\hbox{(16)}}$$ where ${\bf K}^{u}={\bf Q}\hat{{\bf P}}^{u}{\bf Q}^{-1}$ is called a conversion matrix.

In [46], Wang proposed a new SLM scheme which reduces the computational complexity by substituting the conversion matrix for IFFT. The proposed scheme generates the alternative OFDM signal vectors by multiplying the original OFDM signal vector by the conversion matrices where the number of nonzero elements is $4N$ and the nonzero elements belong to the set $\{\pm 1, \pm j\}$. Thus, the conversion with ${\bf K}^{u}$ requires only $3N$ complex additions.

For example for $N=16$ and ${\bf P}^{u}= [1\,j\, 1-j\,1\,j\,1-j\,1\,j\,1 -j1j1-j]^{T}$, the $i$th column vector $\Omega_{i}^{{\rm u}}$ of the conversion matrix ${\bf K}^{u}$ is expressed as $$\Omega_{i}^{u}=[1\,0\,0\,0-1\,0\,0\,0\,1\,0\,0\,0\,1\,0\,0\,0]_{((i))}^{T}, 0\leq i\leq 15$$ where $[\cdot]_{((i))}$ is a circularly down-shifted version of column vector $[\cdot]$ by $i$. Since all the column vectors only have four nonzero elements, the number of nonzero elements of the conversion matrix iS $64 (=4\times 16^{\backslash}$.

It is worth mentioning that the phase sequence must have periodicity in order to maintain $4N$ nonzero elements of the conversion matrix and this leads to the degradation of the PAPR reduction performance.

Figs. 4(a) and 4(b) show examples of the proposed SLM schemes in [46]. The first scheme generates eight alternative OFDM signal vectors from only one IFFT and seven conversions while the second scheme uses two IFFTs and six conversions. In the second scheme, an input symbol vector of the second IFFT is transformed via multiplication by the randomly generated phase sequence ${\bf P}_{z}$.

Based on the simulation result, the first SLM scheme has slightly worse PAPR reduction performance and the second SLM one shows almost the same PAPR reduction performance as the conventional SLM scheme.

C. Multi-Stage TR Scheme

A multi-stage TR scheme was proposed in order to achieve a low PAPR that has a reduced data rate loss [47]. The multi-stage TR scheme adaptively selects one of several PRT sets according to the PAPR of the OFDM signal while the PRT set is fixed for the conventional TR scheme. In fact, the multi-stage TR scheme utilizes the conventional TR schemes in a sequential manner.

Fig. 4. Block diagram of the SLM schemes using the conversion matrix: (a) The first proposed scheme and (b) the second proposed scheme.

Fig. 5 shows a two-stage TR scheme where the first TR block TR₁ is the conventional TR scheme using ${\cal R}_{1}$ and $\gamma_{1}$ as its PRT set and threshold level, respectively, while the second TR block ${\bf TR}_{2}$ uses ${\cal R}_{2}$ and $\gamma_{2}$. In this scheme, the peak of an OFDM signal is initially reduced by TR1 using the threshold level $\gamma_{1}$. After processing by TR₁, the OFDM signal is transmitted, if the PAPR of the processed OFDM signal is lower than the target PAPR threshold level $\gamma_{2}$. Otherwise, the OFDM signal must be processed by TR2 for further reduction of PAPR. For the two-stage TR scheme, additional side information of one-bit must be transmitted to indicate which TR block was used.

The two PRT sets must be designed to satisfy the condition, ${\cal R}_{1}\subset {\cal R}_{2}$. Let $W_{1}$ and $W_{2}$ denote the size of ${\cal R}_{1}$ and ${\cal R}_{2}$, respectively. The frequency domain kernel ${\bf P}_{m}$ is constructed by assigning 1 's to the tones in ${\cal R}_{m}$, where $m=1,2$. Since $W_{2}$ is larger than $W_{1}$, the sidelobes of ${\bf p}_{2}$ are much lower than those of ${\bf p}_{1}$, and thus ${\bf p}_{2}$ can reduce PAPR more effectively.

The average tone reserved ratio (TRR) of the two-stage TR scheme is defined as $$\rho_{av}=\rho_{1}{\Pr}({\rm PAPR}_{{\rm x}_{1}}< \gamma_{2})+\rho_{2}\{1-{\Pr}({\rm PAPR}_{{\rm x}_{1}} < \gamma_{2})\} \eqno{\hbox{(17)}}$$ where $\rho_{1}$ and $\rho_{2}$ are the TRR values of TR₁ and TR₂, respectively, and ${\rm PAPR}_{{\rm x}_{1}}$ is the PAPR of the OFDM signal ${\bf x}_{1}$ after TR₁ is applied.

Fig. 5. A block diagram of two-stage TR scheme.

Fig. 6. PAPR reduction performance of the conventional TR scheme with 5%, 8%, and 10% TRRs and the two-stage TR scheme with (3% 30%), (4% 30%), and (5%, 30%) TRRs when $N=1,024$ and 16-QAM are used.

Since $\rho_{2}>\rho_{1}$, to minimize $\rho_{a\iota}$, it is desirable to select the threshold level $\gamma_{1}$ such that ${\Pr}({\rm PAPR}_{{\rm x}_{1}} <\gamma)$ is quite high $(\geq 0.9)$. Then, the two-stage TR scheme can reduce the PAPR level of OFDM signals below the target threshold level $\gamma_{2}$ while achieving an average TRR close to $\rho_{1}$.

Fig. 6 shows the PAPR reduction performance of the conventional TR scheme with 5%, 8%, and 10% TRR, and the two-stage TR scheme with (3%, 30%), (4%, 30%), and (5%, 30%) TRR, for $N=1,024$ and 16-QAM. It is clear that the PAPR of the OFDM signals in the two-stage TR scheme with (5%, 30%) TRR does not exceed 7.0 dB, with the probability of 10⁻⁵. While, the OFDM signals in the conventional TR schemes with (5%, 8%) TRR can have a PAPR exceeding 7.0 dB with the same probability. While the data transmission efficiency $(1\ -\rho_{av})$ is 0.95 for the conventional TR scheme with 5% TRR and 0.94 for the two-stage TR scheme with (5%, 30%) TRR, the PAPR reduction performance of the two-stage TR scheme with (5%, 30%) TRR is much better than that of the conventional TR scheme with 5% TRR.

SECTION V. Conclusions

The high PAPR is considered to be one of the major drawbacks of OFDM systems, because the large signal fluctuation gives rise to the low power efficiency. In this paper, we provided an overview of the conventional PAPR reduction schemes such as clipping, SLM, PTS, TR, TI, and ACE, and their modifications for achieving a low computational complexity. Although many PAPR reduction schemes have been developed, none of them satisfies commercial requirements or has been adopted as a standard for wireless communication systems. But, the modified PAPR reduction schemes with low computational complexity can be applied to high data rate OFDM systems. Future studies on PAPR reduction may include a combination of different schemes.