Packet Permutation PAPR Reduction for OFDM Systems Based on Luby Transform Codes

Show more

1. Introduction

OFDM is an attractive technique for wireless communications, which can provide higher spectral efficiency, lower computational complexity and greater immunity to multipath fading channels. However, one notorious disadvantage of OFDM systems is the high PAPR. This defect needs the high power amplifier (HPA) to operate in its linear region; otherwise, the nonlinearity of HPA can lead to in-band distortion and out-of-band radiation, thus increasing the bit error rate (BER). Existing PAPR reduction schemes can be classified into three categories, and they are clipping methods [1] [2], coding techniques [3] [4] [5] [6] [7] and probability approaches [8] [9] [10].

Fountain codes are record-breaking sparse-graph codes for channels with erasures, such as multicast systems where files are transmitted in multiple small packets, and each packet is either received without error or not received at all [11]. The packet-based coding property exactly matches the N-dimensional multicarrier structure of OFDM systems, and consequently fountain codes are used to reduce the PAPR [5] [6] [7]. Such a combination can also benefit from cross layer designing, which shows advantages in information sharing among layers and network adaptability.

During the encoding process of fountain codes, different generator matrices [5] and input packet combinations for a chosen degree value [6] can generate various candidates so that we can select the one with the smallest PAPR for transmission. In [7], the scheme deploys fountain codes to control PAPR by introducing a desired level. One similarity of these methods is that an encoded packet is transmitted by an OFDM symbol (i.e., the length of each packet is the same as the OFDM size). This means that the mapping relationship between LT codes and OFDM symbols is not well utilized, so we propose a novel PAPR reduction algorithm based on encoded packet permutation. In the new scheme, we exchange positions of encoded packets to generate different candidates and multiply one OFDM symbol by one phase rotation vector to further improve performance. Simulation results show that satisfactory PAPR reduction performance can be obtained.

This paper is organized as follows. Section 2 presents backgrounds of PAPR and LT Codes. Section 3 illustrates the proposed algorithm and simulation results are shown in Section 4. Finally, Section 5 concludes the paper.

2. PAPR and LT Codes

2.1. PAPR in OFDM Systems

A discrete OFDM symbol ${x}_{n}$ of N subcarriers is expressed as

${x}_{n}=\frac{1}{\sqrt{N}}{\displaystyle \underset{k=0}{\overset{N-1}{\sum}}{X}_{k}{e}^{j\frac{2\pi kn}{N}}},0\le n\le N-1$ (1)

in which $X={[{X}_{0},{X}_{1},\dots ,{X}_{N-1}]}^{T}$ is a data block. The PAPR of ${x}_{n}$ can be defined as

$PAPR=\frac{\underset{0\le n\le N-1}{\mathrm{max}}{\left|{x}_{n}\right|}^{2}}{E\left[{\left|{x}_{n}\right|}^{2}\right]}$ (2)

where $E[\cdot ]$ represents the expectation operator. We often use complementary cumulative distribution function (CCDF) to denote the probability that the PAPR of an OFDM symbol exceeds a given threshold $PAP{R}_{0}$ . In [12], the CCDF is derived as

$\begin{array}{l}\mathrm{Pr}(PAPR>PAP{R}_{0})=1-\mathrm{Pr}(PAPR\le PAP{R}_{0})\\ =1-{(}^{1}\end{array}$ (3)

In general, 4 times oversampling [13] is often performed to precisely capture peak values, so Equation (3) can be modified as

$\mathrm{Pr}(PAPR>PAP{R}_{0})=1-{(1-{e}^{-PAP{R}_{0}})}^{\alpha N}$ (4)

where the empirical value of $\alpha $ is 2.8 [14].

Selected mapping (SLM) [8] is a probability method to reduce PAPR for OFDM systems. The main idea of this technique is that the transmitter generates a set of sufficiently independent candidate data blocks via multiplying a data block by Q independent phase rotation vectors, and the vector length is the same as the number of subcarriers. The transmitted data block will be the one whose PAPR is the smallest among them. In such a case, the probability that an OFDM symbol exceeds a threshold will be

$\mathrm{Pr}(PAPR>PAP{R}_{0})={[1-{(1-{e}^{-PAP{R}_{0}})}^{\alpha N}]}^{Q}$ (5)

Obviously, the probability will dramatically approach 0 as Q increases.

2.2. LT Codes

Digital fountain codes have good performance in erasure channels, which are firstly proposed by M. Luby in 1998. Until 2002, he invented LT codes that can be applied to practice [15]. Assume the input packet vector is $\{{s}_{1},{s}_{2},\dots ,{s}_{k}\}$ and the encoded packet vector is $\{{t}_{1},{t}_{2},\dots ,{t}_{n}\}$ . The encoding process can be described in the following. For each encoded packet, an integer d is first sampled from a probability density function, and then d input packets are uniformly randomly chosen to composite the encoded packet by Exclusive OR (XOR) operation. Finally, the header and footer are added to the encoded packet. The integer d is the degree of the encoded packet, and hence, the probability density function is called degree distribution [16]. The encoding structure of LT codes can also be represented in a bipartite graph, and a toy case where there are five input symbols and six output symbols is depicted in Figure 1.

One remarkable advantage of fountain codes is rateless in the sense that the number of encoded packets generated from the source message is potentially limitless. In a multicast system, any receiver who is interested in receiving the

Figure 1. The bipartite graph is made of input packets (round nodes) and encoded packets (rectangle nodes). The neighbors of a packet in one party are those packets in another party with connecting edges to it. The number of edges connected to an encoded packet is exactly the degree of that packet, which is determined by the degree distribution.

message can reconstruct input packets after collecting a sufficient number of encoded packets. The belief propagation (BP) algorithm is always used in the decoding process. At the beginning, the receiver finds an encoded packet ${t}_{n}$ that is connected to only one input packet ${s}_{k}$ and restores it as the desired input packet. If there is no such an encoded packet, this decoding algorithm halts at this point and fails to recover all input packets. Next, the receiver will reduce the degrees of the other packets with degree two or more by removing the recovered input packet through XOR operation. This process is going to be repeated until the input packets with degree one cannot be found. The decoding performance is closely related to the degree distribution. The Robust Soliton distribution (RSD) is widely used and can be defined as follows

$\rho (d)=\{\begin{array}{l}1/k,d=1\\ 1/d(d-1),d=2,3,\dots ,n\end{array}$ (6)

$\tau (d)=\{\begin{array}{l}s/kd,d=1,2,\dots ,(k/s)-1\\ s\mathrm{log}(s/\delta )/k,d=k/s\\ 0,d>k/s\end{array}$ (7)

$\mu (d)=\frac{\rho (d)+\tau (d)}{Z}$ (8)

where $Z={\displaystyle {\sum}_{d}\rho (d)+\tau (d)}$ is a normalized factor and $s=c\mathrm{ln}(k/\delta )\sqrt{k}$ . The parameter c is a constant of order 1 and $\delta $ is the allowable failure probability.

3. Packet Permutation Algorithm

The nature of some probability approaches is to generate different signal candidates and send the one with the smallest PAPR. Fountain coded PAPR reduction methods follow this idea and also realize the error correction. In [5] and [6], the author generates candidates through combining various input packets after determining a degree value. In addition, the rateless property allows us to produce encoded packets limitlessly, so [7] achieves PAPR control by discarding those packets whose PAPR exceeds the threshold.

One potential candidate generation method is the utilization of the mapping relationship between LT packets and OFDM symbols. Once an LT packet is generated, the simplest and ideal transmission scheme is that this packet is carried by one OFDM symbol; that is to say, this packet occupies all subcarriers and is transmitted over an OFDM symbol. In fact, this mapping method is a typical case that a packet is transmitted over all subcarriers and several OFDM symbols. Above method is labeled as “Scheme I”. A packet occupying a part of subcarriers and transmitting over a few symbols is the Scheme II [17]. Figure 2 illustrates mapping relationships of Scheme I and Scheme II. For a packet in Scheme I, we can split it into two parts and place the second part on another symbol, so the rest of subcarriers can carry another packet with half data. Consequently, we convert Scheme I into Scheme II.

When several packets are mapped into one symbol, exchanging packet positions or occupied subcarrier blocks can generate different packet permutations,

(a)(b)(c)

Figure 2. An illustration of different transmission schemes. (a) The most simplest and ideal implementation of Scheme I: a packet occupies all subcarriers and is transmitted over an OFDM symbol; (b) Scheme I: a packet occupies all subcarriers and is transmitted over several OFDM symbols; (c) Scheme II: a packet occupies a part of subcarriers and is transmitted over several OFDM symbols.

and it is reasonable to regard one permutation as a signal candidate. For simplicity, we assume that the number of packets in a symbol and the OFDM size are both the power of two, and one packet is only transmitted over a symbol. When four packets are sent over one symbol, there will be 4! = 24 permutations, and we use the function Perms to decide which subcarrier block each packet occupies.

For example, if packet 1, packet 2, packet 3 and packet 4 compose an OFDM symbol from subcarrier 0 to N-1 and v = [packet 4, packet 3, packet 2, packet 1], the first outcome returned by Perms(v) is [packet 1, packet 2, packet 3, packet 4] so that Packet 1, Packet 2, Packet 3, and Packet 4 are modulated on subcarrier 0~(N/4 − 1), N/4~(N/2 − 1), (N/2~3N/4 − 1), and 3N/4~(N − 1), respectively. Figure 3 depicts the first four permutations of vector v. Moreover, simulation results in Section 4 will demonstrate that only relying on packet permutation cannot reduce PAPR evidently, so we introduce a phase rotation vector to settle this problem. The proposed approach is presented in Figure 4. Another thing we should notice is that the more packets in a symbol, the more permutations a symbol has. When a symbol is made up of 8 packets, it means an 8! = 40,320 search for the optimal candidate, which is impossible. Therefore, we can freely set a maximal permutation to limit the exhausted search.

For a fountain coded system, the receiver does not care which packet is firstly received. If it receives a sufficient number of encoded packets, it can recover the input packets. Therefore, the position change of packets in a symbol does not

Figure 3. The first four permutations by using the function Perms when [packet 4, packet 3, packet 2, packet 1] occupies 8 subcarriers.

Figure 4. The proposed algorithm.

need side information and has no adverse effect on decoding. Moreover, we also do not change degree values for any packets, so this algorithm does not result in extra decoding overhead.

4. Simulation Results

In order to evaluate the PAPR reduction performance, we consider a N = 1024 subcarriers and 16 Quadrature Amplitude Modulation (QAM) OFDM system, which one packet is transmitted over a symbol and assigned to 256 subcarriers. With regard to the degree distribution in LT codes, we choose RSD and set c = 0.1 and $\delta =0.5$ . The number of input and encoded packets are both 40000 so as to obtain a smooth CCDF curve, and 4 times oversampling is performed.

4.1. Impact of the Number of Permutations

Figure 5 describes the CCDF of different permutations when phase rotation vectors are not used. The function Perms returns a matrix containing all permutations of the elements of vector v in reverse lexicographic order, so k = 2

Figure 5. CCDF of PAPR for OFDM symbols with different number of permutations when phase rotation vectors are not used.

chooses the first two permutations of vector v, and so on. It can be seen that the CCDF improves with the increase of k. However, we can also conclude that the PAPR cannot be reduced evidently through only relying on packet permutation. One reason is that the performance of k = 24 over k = 6 only holds a lead by 0.2 dB at CCDF of 10-1, and the other is that k = 6, k = 8, k = 10, k = 12 and k = 24 almost have the same performance when PAPR0 ≥ 10.2 dB.

4.2. Impact of the Phase Rotation Vector

For further reducing PAPR, we combine packet permutation with phase rotation and simulate two schemes. Algorithm I is the first scheme, and 24 permutations multiplying by 24 independent phase rotation vectors is the second one. Figure 6 plots the performance of these schemes’ CCDFs. Obviously, Figure 6 shows a great improvement in PAPR reduction with the combination of packet permutation and phase rotation. In SLM, the number of phase rotation vectors impacts the PAPR reduction performance. Nevertheless, curves of 1 phase rotation vector and 24 phase rotation vectors almost overlap each other. We can explain that packet permutation can partly act as some phase rotation vectors to produce symbols with different PAPR. With regard to the side information, the first scheme only needs ${\mathrm{log}}_{2}1$ bit compared with ${\mathrm{log}}_{2}24$ in the second scheme. All the above advantages are why we introduce 1 phase rotation vector in the proposed algorithm. We also consider sizes of phase sets from which phase rotation vectors are chosen, because there are more likely to change each subcarrier’s phase with higher sizes. The parameter h in Figure 6 indicates different phase sets, and h = 1, h = 2, h = 3 respectively denote the set of {1, −1}, {1, −1, j, −j}

and $\{0,\frac{\pi}{4},\frac{\pi}{2},\frac{3\pi}{4},\pi ,\frac{5\pi}{4},\frac{3\pi}{2},\frac{7\pi}{4}\}$ . However, the size of the phase set makes no difference.

Figure 6. CCDF of PAPR for OFDM symbols with different number of phase rotation vectors and phase sets.

4.3. Impact of the Permutation Selection Mode

In Section 3, we mentioned that we can freely self-define the maximal number of candidates among all permutations to prevent proceeding an exhausted optimal permutation search, so which group of permutations is used as candidates may have an impact on the PAPR reduction performance, i.e., the impact of the permutation selection mode. In this part, the function Perms (v) is still used to return all permutations in reverse lexicographic order. We choose 12 candidates among 24 permutations in our simulation by using adjacent mode, interleaved mode and pseudo-random mode, respectively. Figure 7 illustrates the comparison of different selection modes. Firstly, it is clearly that the combination of packet permutation and 1 phase rotation vector shows superiority over packet permutation again. Then, adjacent mode and pseudo-random mode slightly outperform interleaved mode, but such a performance lead is so narrow that can be neglected. When phase rotation is not used, three selection modes have the same performance.

5. Conclusion

In this paper, the transmission scheme for an LT coded OFDM system is firstly analyzed. Then we describe a new signal candidate generation method by permutating LT packets in an OFDM symbol and assigning them to different subcarrier blocks, so the symbol with the smallest PAPR among candidates is transmitted to reduce PAPR. The packet permutation also combines with a phase rotation vector to improve the performance. Simulation results demonstrate that the proposed algorithm can evidently reduce PAPR and the permutations of a few packets can play the role of phase rotation vectors. Moreover, the

Figure 7. CCDF of PAPR for OFDM symbols with different permutation selection mode when 12 permutations are used.

new scheme almost does not need side information and has good decoding performance.

References

[1] Anoh, K., Tanriover, C. and Adebisi, B. (2017) On the Optimization of Iterative clipping and Filtering for PAPR Reduction in OFDM Systems. IEEE Access, PP, 1.

[2] Sohn, I. and Kim, S.C. (2015) Neural Network Based Simplified Clipping and Filtering Technique for PAPR Reduction of OFDM Signals. IEEE Communications Letters, 19, 1438-1441. https://doi.org/10.1109/LCOMM.2015.2441065

[3] Jones, A.E., Wilkinson, T.A. and Barton, S.K. (1994) Block Coding Scheme for Reduction of Peak to Mean Envelope Power Ratio of Multicarrier Transmission Schemes. Electronics Letters, 30, 2098-2099. https://doi.org/10.1049/el:19941423

[4] Tsai, Y.C., Deng, S.K., Chen, K.C. and Lin, M.C. (2008) Turbo Coded OFDM for Reducing PAPR and Error Rates. IEEE Transactions on Wireless Communications, 7, 84-89. https://doi.org/10.1109/TWC.2008.060610

[5] Lee, S.-K., Chiu, H.-L., Tsai, Y.-C. and Chen, H.-Y. (2009) LT Codes for OFDM Multicast Systems with PAPR Reduction Capability. Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, ACM, 348-352.
https://doi.org/10.1145/1582379.1582456

[6] Lee, S.K., Liu, Y.C., Chiu, H.L. and Tsai, Y.C. (2011) Fountain Codes with PAPR Constraint for Multicast Communications. IEEE Transactions on Broadcasting, 57, 319-325. https://doi.org/10.1109/TBC.2011.2104690

[7] Jiang, T. and Li, X. (2010) Using Fountain Codes to Control the Peak-To-Average Power Ratio of OFDM Signals. IEEE Transactions on Vehicular Technology, 59, 3779-3785. https://doi.org/10.1109/TVT.2010.2053397

[8] Bauml, R.W., Fischer, R.F.H. and Huber, J.B. (1996) Reducing the Peak-to-Average Power Ratio of Multicarrier Modulation by Selected Mapping. Electronics Letters, 32, 2056-2057. https://doi.org/10.1049/el:19961384

[9] Jeon, H.B., No, J.S. and Shin, D.J. (2011) A Low-Complexity SLM Scheme Using Additive Mapping Sequences for PAPR Reduction of OFDM Signals. IEEE Transactions on Broadcasting, 57, 866-875. https://doi.org/10.1109/TBC.2011.2151570

[10] Cimini, L.J. and Sollenberger, N.R. (2005) Peak-to-Average Power Ratio Reduction of an OFDM Signal Using Partial Transmit Sequences. IEEE Communications Letters, 4, 86-88, March 2000.

[11] Mackay, D.J.C. (2005) Fountain Codes. Communications, IEE Proceedings, 152, 1062-1068. https://doi.org/10.1049/ip-com:20050237

[12] O’Neill, R. and Lopes, L.B. (1995) Envelope Variations and Spectral Splatter in Clipped Multicarrier Signals. Proceedings of 6th International Symposium on Personal, Indoor and Mobile Radio Communications, 1, 71-75.
https://doi.org/10.1109/PIMRC.1995.476406

[13] Tellambura, C. (2001) Computation of the Continuous-Time Par of an OFDM Signal with BPSK Subcarriers. IEEE Communications Letters, 5, 185-187.
https://doi.org/10.1109/4234.922754

[14] Jiang, T. and Wu, Y. (2008) An Overview: Peak-to-Average Power Ratio Reduction Techniques for OFDM Signals. IEEE Transactions on Broadcasting, 54, 257-268.
https://doi.org/10.1109/TBC.2008.915770

[15] Luby, M. (2002) LT Codes. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 271-280. https://doi.org/10.1109/SFCS.2002.1181950

[16] Jeon, S.Y., Ahn, J.H. and Lee, T.J. (2016) Reliable Broadcast Using Limited LT Coding in Wireless Networks. IEEE Commun. Lett., 20, 1187-1190.
https://doi.org/10.1109/LCOMM.2016.2548465

[17] Xiaoying, S. (2009) An Opportunistic Error Correction Layer for OFDM Systems. EURASIP Journal on Wireless Communications and Networking, 2009, 1-10.