Genetic Algorithm Based Nearly Optimal Peak Reduction Tone Set Selection for Adaptive Amplitude Clipping PAPR Reduction

An OFDM signal is the sum of $N$ independent, modulated tones (subcarriers) of equal bandwidth with frequency separation $1/T$, where $T$ is the time duration of the OFDM symbol. For a complex-valued phase-shift keying (PSK) or quadrature amplitude modulation (QAM) input OFDM block $\textbf{X}=[X_{0},X_{1},\ldots,X_{N-1}]^{T}$ of length $N$, the inverse discrete Fourier transform (IDFT) generates the ready-to-transmit OFDM signal. The discrete-time OFDM signal is expressed as

which can also be written in matrix form $\textbf{x}=[x_{0},\dots,x_{N-1}]^{T}=\textbf{Q}\textbf{X}$, where Q is the IDFT matrix with the $(n,k)$-th entry $q_{n,k}=\frac{1}{\sqrt{N}}e^{\frac{j2\pi nk}{N}}$.

The PAPR of x is defined as the ratio of the maximal instantaneous power to the average power; that is

The complementary cumulative distribution function (CCDF) is one of the most frequently used performance measures for PAPR reduction, representing the probability that the PAPR of an OFDM symbol exceeds the given threshold $PAPR_{0}$, which is denoted as

In the TR-based OFDM scheme, peak reduction tones (PRT) are reserved to generate PAPR reduction signals. These reserved tones do not carry any data information, and they are only used for reducing PAPR. Specifically, the peak-canceling signal $\textbf{c}=[c_{0},c_{1},\ldots,c_{N-1}]^{T}$ generated by reserved PRT is added to the original time domain signal $\textbf{x}=[x_{0},x_{1},\ldots,x_{N-1}]^{T}$ to reduce its PAPR. The PAPR reduced signal can be expressed as

where $\textbf{C}=[C_{0},C_{1},\ldots,C_{N-1}]^{T}$ is the peak-canceling signal vector in frequency domain. To avoid signal distortion, the data vector X and the peak reduction vector C lie in disjoint frequency domains, i.e.

where $\mathcal{R}=\{i_{0},i_{1},\ldots,i_{M-1}\}$ is the index set of the reserved tones, $\mathcal{R}^{C}$ is the complementary set of $\mathcal{R}$ in $\mathcal{N}=\{0,1,\ldots,N-1\}$, and $M<N$ is the size of PRT set.

The PAPR of the peak-reduced OFDM signal $\textbf{a}=[a_{0},a_{1},\ldots,a_{N-1}]^{T}$ is then redefined [18] as

Thus c must be chosen to minimize the maximum of the peak-reduced OFDM signal a, i.e.

To obtain the optimum $\textbf{c}^{*}$, (7) can be reformulated as the following optimization problem:

which is a Quadratically Constrained Quadratic Program (QCQP) problem [18] and $e$ is an optimization parameter. Although the optimum of a QCQP exists, the solution requires a high computational cost. To reduce the complexity of the QCQP, a simple gradient algorithm proposed by Tellado in [16, 17, 18] iteratively updates the vector c as follows:

where $\alpha_{i}$ is a scaling factor, $\textbf{p}=[p_{0},p_{1},\ldots,p_{N-1}]^{T}$ is called the time domain kernel, and $\textbf{p}[((k-k_{i}))_{N}]$ denotes a circular shift of p to the right by a value $k_{i}$ calculated by

The time domain kernel p is obtained by the following formula:

where $\textbf{P}=[{P}_{0},{P}_{1},\ldots,{P}_{N-1}]^{T}$ is called the frequency domain kernel whose elements are defined by

After $J$ iterations of this algorithm, the peak-reduced OFDM signal is obtained:

From (9)-(13), it can be found that the PAPR reduction performance of the TR-based OFDM system depends on the selection of the time domain kernel p, which is only a function of PRT set $\mathcal{R}$. When p is a single discrete pulse, the best PAPR reduction performance can be obtained because the maximal peak at location $k_{i}$ can be canceled without distorting other signal sampling. But it is impractical because a single discrete pulse will results in that all tones should be assigned to the PRT set. So we should select the time domain kernel p such that the p not only reduces the peak at location $k_{i}$ but also suppresses the other big values at location $k\neq k_{i}$.

To find the optimal PRT set, in mathematical form, we require to solve the following combinatorial optimization problem:

which requires an exhaustive search of all combination of possible PRT set $\mathcal{R}$, i.e. $|\mathcal{R}|=C^{M}_{N}$ possible combination numbers of PRT set are searched, where $C^{M}_{N}=\frac{N!}{M!(N-M)!}$ denotes the binomial coefficient. It is an NP-hard problem and cannot be solved for the number of tones envisaged in practical systems. In [16, 18], the consecutive PRT set, the equally spaced PRT set and the the random PRT set optimization were proposed as the candidates of PRT set. Although the consecutive PRT set and the equally spaced PRT set are the simplest selections of PRT set, their PAPR reduction performance are inferior to that of the random PRT set optimization. But the random PRT set optimization requires larger PRT set sampling, and the associated complexity limits the application of such a technique. A variance minimization method in [19] is developed to solve the NP-hard problem, and it is just a modified version of the random PRT set optimization, which also has the drawback of high computational cost. In [20], a cross entropy method was proposed to solve the problem. It obtains better results than the existing selection methods, but it requires larger population or sampling sizes. These limitations of the existing methods motivate us to find an efficient method to obtain a nearly optimal PRT set. As mentioned before, we propose a genetic algorithm (GA) based PRT set selection method for the purpose with very low computational complexity.

The GA introduced by Holland [24] is a stochastic search method inspired from the principles of biological evolution observed in nature. GA uses a population of candidate solutions initially distributed over the entire solution space. Based on the principle of Darwinian survival of the fittest, GA produces a better approximation to the optimal solution by evolving this population of candidate solutions over successive iterations or generations. The GA's evolution uses the following genetic operators:

1. 1.

   Selection is a genetic operator that chooses a chromosome from the current generation's population in order to include in the next generation's mating pool. In general, chromosomes with a high fitness (merit) should be selected and at the same time chromosomes with a low fitness should be discarded.

2. 2.

   Cross-over is a genetic operator that exchanges the elements between two different chromosomes (parents) to produce new chromosomes (offsprings). The new population of the next generation consists of these offsprings.

3. 3.

   Mutation is a genetic operator that refers to the alteration of the value of each element in a chromosome with a probability.

GA has been applied to extensive optimization problems, such as pilot location search of OFDM timing synchronization waveforms [27], joint multiuser symbol detection for synchronous CDMA systems [28], the search of low autocorrelated binary sequences [29] and thinned arrays [30]. For a complete understanding of the GA, the reader is referred to [24, 25, 26].

A detailed description of the GA used for searching the nearly optimal PRT set positions is described in what follows.

An initial population of $S$ chromosome (parent) sequences is randomly generated. Each parent sequences is a vector of length $N$, and each element of the vector is a binary zero or one depending on the existence of a PRT at that position (one denotes existence and zero denotes non-existence). The number of the PRT in each binary vector is $M<N$. Denote the $S$ parent sequences as $\{\textbf{A}_{1},\dots,\textbf{A}_{S}\}$. Then each $\textbf{A}_{\ell}$ is a binary vector of length $N$.

For each parent sequence $\textbf{A}_{\ell}$, the PRT set $\cal R_{\ell}$ is the collection of the locations whose elements are one. Then the frequency domain kernel $\textbf{P}_{\ell}$ corresponding to the PRT set $\cal R_{\ell}$ is obtained by (12), and the time domain kernel $\textbf{p}_{\ell}=[p_{0}^{\ell},\dots,p_{N-1}^{\ell}]$ is obtained by (11). The merit (secondary peak) of the sequence $\textbf{A}_{\ell}$ is defined as

The $T$ sequences (called elite sequences) with the lowest merits are maintained for the next population generation. The best merit of the $S$ sequences is defined as

Then all $S$ sequences are crossed-over with a probability denoted by $p_{c}$. For simplicity, one point cross-over is used in this paper. In order to prevent local minima, mutation operator controlled by a probability $p_{m}$ is applied by changing randomly selected elements in a chromosome sequence. Due to the cross-over and mutation operations, the number of PRT in a newly generated sequence (offspring) may be different to $M$ (the size of the PRT set), so that the PRT set is infeasible. Hence one or more zero (zeros) or one (ones) will replace the randomly selected elements in the offspring to guarantee that the PRT set is feasible (the number of the PRT in the offspring is $M$).

An illustration of the cross-over and mutation operations is presented in Fig. 1, where black circles represent PRT positions. Chromosomes from two parents are separated from a randomly selected point and crossed-over to generate new offsprings. Due to crossed-over operation, the size of PRT set of an offspring can be more or less than the required $M$ PRTs. If an offspring has PRTs more than the required $M$, then several randomly selected PRTs will be removed. If an offspring has PRTs less than the required $M$, then several PRTs will be added to the randomly selected positions.

The merits of all offspring sequences are evaluated using (15). Each sequence competes for the next generation pool. The $T$ elite sequences obtained from the previous generation replace the $T$ worst sequences with the highest merits in the current generation. This increases the probability of generating better solution and prevents the loss of the optimal solution because of cross-over and mutation operations. The best merit of the offsprings is evaluated using (16), which will replace the best merit of the previous generation if it is smaller than it.

The cycle is repeated until a predetermined number of times or a solution with a predefined fitness threshold (the merit is less then some predefined threshold) is achieved. Therefore the proposed GA-based PRT position search algorithm can be summarized in Algorithm 1:

The AS-TR method is an iterative clipping and filtered technique. It firstly uses a soft limiter [32] to the input OFDM signal to get the clipping noise $f_{n}^{(i)}$,

where $A$ is the target clipping threshold which is relevant to the clipping ratio $\gamma=\frac{A^{2}}{E{|x_{n}|^{2}}}$, $\theta_{n}^{(i)}$ is the phase of $x_{n}^{(i)}$ and $i$ denotes the iteration number. The filtered clipping noise $\hat{f}_{n}^{(i)}$ is obtained by making $f_{n}^{(i)}$ through a filter whose passbands are only on reserved tones. Let $\textbf{f}^{(i)}=[f_{0}^{(i)},f_{1}^{(i)},\ldots,f_{LN-1}^{(i)}]^{T}$ and $\hat{\textbf{f}}^{(i)}=[\hat{f}_{0}^{(i)},\hat{f}_{1}^{(i)},\ldots,\hat{f}_{LN-1}^{(i)}]^{T}$, where $L$ is an oversampling factor. The peak-reduction signal of the AS-TR method is iteratively updated as follows:

where $\beta$ is a positive step size that determines the convergence rate. The optimal $\beta$ is calculated by the following formula:

where $\Re[x]$ represents the real part of $x$, $\textbf{S}_{p}=\{n:n\in\textbf{S}_{1}$, $|x_{n}^{(i)}|>|x_{n-1}^{(i)}|$ and $|x_{n}^{(i)}|\geq|x_{n+1}^{(i)}|\}$ is the index set of the peak of $f_{n}^{(i)}$, and $\textbf{S}_{1}=\{n:|f_{n}^{(i)}|>0\}$ is the index set of all clipping pulse.

In general, the larger PAPR reduction obtained by a lower target clipping level is expected. But the PAPR reduction performance of the AS-TR method is very sensitive to the target clipping level. In other words, different clipping ratio $\gamma$ results in different PAPR reduction performances, as will be demonstrated in Section V. However, the optimal target clipping level or clipping ratio can not be predetermined at the initial stage. In the next section, an adaptive clipping scheme is proposed to get better PAPR reduction regardless of the initial clipping ratio $\gamma$.

In this section, we propose an adaptive amplitude clipping algorithm for TR-based OFDM systems. The main objective is to control both the target clipping level $A$ and the convergence factor $\beta$ at each iteration. The objective function is denoted as

where $\textbf{S}_{1}=\{n:|f_{n}^{(i)}|>0\}$ is the index of all clipping pulses. The reason that we select (20) as the objective function is based on the following inequality.

By least square method, (20) shows that the optimal convergence factor is

where $\langle\cdot,\cdot\rangle$ represents the real inner-product. This implies that the calculation of $\beta$ involves real domain, rather than complex domain, which is another advantage of our proposed algorithm.

Let $\textbf{S}_{2}=\{n:|f_{n}^{(i+1)}|>0\}$ and $\Omega=\textbf{S}_{1}\bigcup\textbf{S}_{2}$. Suppose that the size of $\Omega$ is $N_{1}$. Then the gradient is updated as follows:

Then the proposed adaptive amplitude clipping (AAC-TR) algorithm is stated in Algorithm 2.

The complexity of the AAC-TR algorithm in oversampling case (oversampling factor $L\geq 4$) for accurate PAPR [10] is measured by using the number of real multiplications. A complex multiplication is counted as four real multiplications. We only consider the runtime complexity. Step 1 and step 2 are not counted because all clipping-based methods must carry out these two steps.

In step 3, $f_{n}^{(i)}$ can be calculated as $f_{n}^{(i)}=x_{n}^{(i)}-x_{n}^{(i)}(A/|x_{n}^{(i)}|)$, where $n\in\textbf{S}_{1}=\{n:|f_{n}^{(i)}|>0\}$, and $N_{\textbf{S}_{1}}$ is the size of $\textbf{S}_{1}$. Although $N_{\textbf{S}_{1}}$ is a random variable, it is roughly a constant in all iterations and its mean can be calculated as follows [21].

So the complexity of computing $f_{n}^{(i)}$ can be estimated as $2\bar{N}_{\textbf{S}_{1}}$ real multiplications, and $\bar{N}_{\textbf{S}_{1}}$ real divisions.

In step 4, the number of real multiplications for computing an $LN$-point DFT with $N_{\textbf{S}_{1}}$ nonzero inputs and $N$ in-band outputs (other outputs are not needed) can be computed as follows [23, 31]:

where $\mathcal{M}_{k}$ represents the number of real multiplications for computing a $k$-point DFT. Based on (26)-(28) and replacing $N_{\textbf{S}_{1}}$ by $\bar{N}_{\textbf{S}_{1}}$, the average complexity $\mathcal{M}_{DFT}$ of the DFT is calculated. Similarly, replacing $N_{\textbf{S}_{1}}$, $N$ and $L$ by $M$, $LN$ and $1$ respectively, the average complexity $\mathcal{M}_{IDFT}$ of the IDFT can be also calculated.

In (22), the calculation of $\beta$ requires $2\bar{N}_{\textbf{S}_{1}}$ real multiplications and $1$ real division. Note that the update of $A$ in (24) and the calculation of $\nabla_{A}$ in (23) only require $1$ real multiplication and $1$ real division, respectively.

The complexity of the AAC-TR algorithm mainly depends on the $LN$-point DFT/IDFT pair and weighting the clipping noise in (18). The latter requires $2LN$ real multiplications. Based on the above analysis, the total complexity of the the AAC-TR algorithm for $K$ iterations is

real multiplications and $K(\bar{N}_{\textbf{S}_{1}}+2)$ real divisions.

If DFT/IDFT used in the AAC-TR algorithm is replaced by FFT/IFFT to compute the peak-reduced signal, the computational complexity of the AAC-TR algorithm is evaluated as $\mathcal{O}(LN\log(LN))$, which is consistent with the AS-TR algorithm. But it is better than the gradient algorithm [16, 18]. The latter is with complexity of order $\mathcal{O}(LN^{2})$ [23]. On the other hand, the AAC-TR algorithm can counteract all large peaks above the clipping level in each iteration, while the gradient algorithm can only mitigate one peak in each iteration.

Compared to the AS-TR algorithm, the complexity of the AAC-TR algorithm slightly increases due to the following factors. The calculation of $\beta$ for the AS-TR algorithm in (19) is operated over $\textbf{S}_{p}$, which requires $5\bar{N}_{\textbf{S}_{p}}$ real multiplications. Nevertheless, the calculation of $\beta$ for the AAC-TR algorithm in (22) is over $\textbf{S}_{1}$, which requires $2\bar{N}_{\textbf{S}_{1}}$ real multiplications. From [21], we have $\bar{N}_{\textbf{S}_{1}}=L\sqrt{\frac{6}{\pi}}\frac{\sigma}{A}\bar{N}_{\textbf{S}_{p}}$. For example, when $L=4$, $N=512$, and $\gamma=5$ dB, we have $\bar{N}_{\textbf{S}_{1}}=86.6902$ and $\bar{N}_{\textbf{S}_{p}}=39.4389$. So $5\bar{N}_{\textbf{S}_{p}}-2\bar{N}_{\textbf{S}_{p}}=23.8139$ real multiplications are reduced in each iteration. Although the adaptive update of clipping level in (24) and (23) will result in the increment of calculation (mainly real additions), the operation reduction of computing $\beta$ can compensate some of such increment so that the complexity of the AAC-TR algorithm slightly increases compared to that of the AS-TR algorithm.

Table I compares the computational complexity and the normalized secondary peak among different methods. For comparison, the differences between the normalized secondary peak of the CE algorithm and those of other methods are also calculated. It can be seen that the secondary peaks achieved by consecutive PRT set and equally spaced PRT set are the worst among all methods. The secondary peak obtained by the CE algorithm excels those of other methods. The secondary peak by random set optimization (RSO) with $10^{5}$ randomly chosen PRT set is $0.0402$ larger than that of CE algorithm with $20400$ searches. So the CE algorithm with lower computational complexity gets better performance than RSO. On the other hand, the computational complexity of CE algorithm is five times greater than that of GA-PRT algorithm. But the difference between the secondary peaks of the two methods is only $0.0191$. In other words, the complexity reduction by GA-PRT algorithm is $(20400-5100)=15300$ operations with payment of only $0.0191$ in the secondary peak. So the proposed GA-based PRT set selection algorithm is more efficient than the CE algorithm for solving the secondary peak. The fact that the PAPR reduction performances of CE and GA are almost the same will be demonstrated in Fig. 2.

In Fig. 2, the comparison of PAPR reduction performance based on Tellado's gradient algorithm (GD-TR) [16, 18] with the above different PRT sets is shown. Here the iteration number of the gradient algorithm is set to $10$. When $P_{r}(PAPR>PAPR_{0})=10^{-4}$, the PAPR of the original OFDM is $12$ dB. The PAPRs of CS-PRT set and ES-PRT set are $10.8$ dB and $10.5$ dB, respectively. Using the random set optimization in [18], when the number of randomly selected PRT sets is $10^{5}$, the PAPR is reduced to $9.2$ dB. The PAPR obtained by the CE-PRT with the search complexity $UK=120*170=20400$ in [20] is $9.1$ dB. The PAPR obtained by the GA-PRT with the search complexity $SK=30*170=5100$ is $9.1$ dB. There is a negligible gap between the PAPRs obtained by CE-PRT and by GA-PRT. But from Table I, we see that the search complexity of the GA-PRT is only $SK/UK=30/120=25\%$ of that by the CE-PRT.

In Fig. 3, 100 experiments are performed to compare the means of the best secondary peak obtained by GA-PRT algorithm and CE-PRT algorithm. According to the original CE algorithm proposed by Rubinstein, the sample size $U$ is very large to get better performance for the CE-PRT algorithm, so we only adopt $U=120$ used in the [20] for comparison. It is can be found that the performance of the GA-PRT algorithm is better than that of the CE-PRT one in approximately 1-90 iterations. As the increase of iterations, the secondary peaks of the CE-PRT algorithm are improved. This displays that the convergence of the CE-PRT algorithm is slower than that of the GA-PRT one, so that the proposed GA-PRT algorithm can get a better suboptimal PRT set. On the other hand, the maximal difference of the secondary peak gained by the GA-PRT algorithm between $S=30$ and $S=120$ is only 0.0134, so $S=30$ is a better choice for the proposed GA-PRT algorithm.

Fig. 4 compares the PAPR reduction performance of the proposed AAC-TR algorithm with the constant scaling (Constant) algorithm, AS-TR method in [21, 22], signal to clipping noise ratio (SCR-TR) algorithm and gradient descent (GD-TR) algorithm [17] for the same GA-PRT set. Here the iteration number of the constant scaling algorithm is $40$. The same maximum iteration number is set to $10$ for AS-TR, AAC-TR, GD-TR and SCR-TR. When $P_{r}(PAPR>PAPR_{0})=10^{-4}$, the PAPR of the original OFDM is $11.9$ dB. Using the constant scaling algorithm to SCR-TR algorithm GD-TR algorithm and AS-TR algorithm, the PAPRs are approximately reduced to $9.33$ dB, $9.67$ dB, $9.22$ dB, $8.56$ dB, respectively. The PAPR is approximately reduced to $7.05$ dB by using the proposed AAC-TR algorithm. Compared to the PAPR of the original OFDM, an approximate $4.85$ dB reduction gain is obtained, which is $1.51$ dB larger than AS-TR algorithm, $2.62$ dB larger than SCR-TR algorithm, $2.17$ dB larger than GD-TR algorithm and $2.28$ dB larger than constant scaling algorithm for the same $10$ iterations.

Fig. 5 compares the average PAPR reduction performance of the AS-TR, AAC-TR and GD-TR with clipping ratio $\gamma=4$ dB for the same iteration numbers. Fig. 4 shows that the average PAPR reduction performance of the AAC-TR algorithm is better than those of AS-TR and GD-TR. When the iteration number equals $11$, the AAC-TR algorithm converges to $6$ dB PAPR. Although the GD-TR algorithm is simple, its convergence speed is the slowest among the three methods. When the iteration number is $20$, its average PAPR is approximately $7.4$ dB, which is $1.4$ dB larger than AAC-TR algorithm in $11$ iterations. The AS-TR algorithm converges to $7.1$ dB PAPR in $7$ iterations, however, which is approximately $0.9$ dB larger than AAC-TR algorithm in the same iterations.

Table II compares the average power increase (API) (in dB), average simulation time (AST) (in millisecond) and PAPR for AS-TR, AAC-TR and GD-TR with clipping ratio $\gamma=5$ dB for $10$ iterations. We observe that the AST of the GD-TR method is least (Note that the GD-TR method must prestore an $LN\times LN$ IFFT matrix, the calculation does not include in simulation time), but its PAPR is $0.66$ dB larger than that of the AS-TR algorithm, and $2.17$ dB larger than that of the AAC-TR algorithm. The APIs of AS-TR and AAC-TR are almost the same. Compared to AS-TR algorithm, the AST of the AAC-TR algorithm increases slightly, but its API is less than that of the AS-TR, and PAPR is $1.51$ dB smaller than that of AS-TR.

Fig. 6 compares the PAPR reduction performance of AS-TR algorithm and AAC-TR method with $10$ iterations for three different target clipping ratios, $\gamma=0$ dB, $2$ dB and $4$ dB. For comparison, the original OFDM signal's PAPR is also given. When $P_{r}(PAPR>PAPR_{0})=10^{-4}$, the AS-TR algorithm for the three different clipping ratios, $\gamma=0$ dB, $2$ dB and $4$ dB can obtain $0.9$ dB, $1.4$ dB and $2.4$ dB PAPR reduction from the original OFDM PAPR of $12$ dB. It demonstrates that the AS-TR algorithm is sensitive to the target clipping ratio. Different target clipping ratios can result in different PAPR reduction performance. Contrary to the AS-TR algorithm, the proposed AAC-TR algorithm obtains an approximately $5$ dB PAPR reduction from the original OFDM PAPR of $12$ dB for all three of the target clipping ratios.

In Fig. 7, we compare the PAPR reduction performance of AAC-TR algorithm for different step size $\rho$. When $\rho=0.1$ and $\rho=0.3$, the PAPRs are $9.3$ dB and $7.8$ dB. For other choices on $\rho$, the differences of the PAPRs are very small. The reasons can be that the smaller $\rho$ can not effectively adjust the clipping level $A$. This corresponds to that $A$ is not updated. So we should select a bigger step size $\rho$ to gain better PAPR performance for the AAC-TR algorithm.