PEAK TO AVERAGE POWER REDUCTION
`FOR MULTICARRIER MODULATION
`
`SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING
`
`A DISSERTATION
`
`AND THE COMMITTEE ON GRADUATE STUDIES
`
`OF STANFORD UNIVERSITY
`
`IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
`
`FOR THE DEGREE OF
`
`DOCTOR OF PHILOSOPHY
`
`J ose Tellado-Mourelo
`September 1999
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 1 of 168
`
`

`

`© Copyright by Jose Tellado-Mourelo 2000
`All Rights Reserved
`
`11
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 2 of 168
`
`

`

`I certify that I have read this dissertation and that in my opinion it is fully adequate,
`in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
`
`John M. Cioffi
`(Principal adviser)
`
`I certify that I have read this dissertation and that in my opinion it is fully adequate,
`in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
`
`Donald C. Cox
`
`I certify that I have read this dissertation and that in my opinion it is fully adequate,
`in scope and in qua~Lree of Doctor of Philosophy.
`
`Thomas Lee
`
`Approved for the University Committee on Graduate Studies:
`
`lll
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 3 of 168
`
`

`

`Abstract
`
`T HE DATA RATE AND RELIABILITY REQUIRED to support the new information
`
`age has increased the demand for high speed communication systems. Mul(cid:173)
`ticarrier modulation has recently gained great popularity due to its robustness in
`mitigating various impairments in such systems.
`A major drawback of multicarrier signals is their high Peak to Average Power
`Ratio (PAR). Since most practica! transmission systems are peak-power limited, the
`average .transmit power must be reduced for linear operation over the full dynamic
`range, which degrades the received signal power.
`This dissertation formulates the PAR problem for multicarrier modulation and
`proposes three new methods for PAR reduction. The first two structures prevent dis(cid:173)
`tortions by reducing the PAR on the discrete-time signal prior to any nonlinear device
`such as a DAC or a power amplifier. The third structure corrects for transmitter non(cid:173)
`linear distortion at the receiver when the nonlinear function is known. Most methods
`reduce the PAR of the discrete-time signal although the PAR of the continuous-time
`signal is of more interest in practice. We derive new absolute and statistical bounds
`for the continuous-time PAR based on discrete-time samples.
`The first distortionless structure, called Tone Reservation, reserves a small set of
`subcarriers for reducing the PAR. For this method, the exact solution and several low
`complexity suboptimal algorithms are presented.
`The second distortionless structure is called Tone Injection. For this method,
`the constellation size is increased to allow multiple symbol representations for each
`information sequence. PAR reduction is achieved by selecting the appropriate symbol
`mappings. The exact solution to this PAR minimization problem has non-polynomial
`
`lV
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 4 of 168
`
`

`

`complexity. Bounds on maximum PAR reduction are derived and efficient algorithms
`that achieve near optimal performance are proposed. Similar to the Tone Reservation
`method, most of the complexity is introduced at the transmitter. The additional
`complexity at the receiver is a simple modulo operation on the demodulated complex
`vectors.
`The third structure reduces the PAR by applying a saturating nonlinearity at the
`transmitter and correcting for nonlinear distortion at the receiver. This simplifies the
`transmitter at the expense of adding complexity at the receiver .. Mutual Information
`expressions are derived for multicarrier transmission in the presence of nonlinear
`distortion. The optimum maximum likelihood receiver and an efficient demodulator
`based on the maximum likelihood receiver are also described.
`
`V
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 5 of 168
`
`

`

`Acknow ledgment
`
`I HAVE MANY PEOPLE TO THANK for helping to make my Stanford experience
`
`both enriching and rewarding.
`First and foremost, I wish to thank my adviser, Prof. John Cioffi. Throughout my
`.years at Stanford, John has been a constant source of research ideas, encouragement
`and guidance. His confidence in me; his inspiring words in times of need and his unique
`blend of academic and entrepreneurial attitude have ;created an ideal environment for
`this research.
`I also wish to thank my associate adviser, Prof. Donald Cox. His breadth of
`knowledge and perceptiveness have instilled in me great interests in wireless com(cid:173)
`munications. The quality of this dissertation has also improved due to his careful
`review and many good suggestions. I do regret not initiating more interactions with
`Prof. Cox during my graduate years.
`I would also like to thank Prof. Arogyaswami Paulraj for agreeing to be a member
`of my orals committee, and for offering me the opportunity to apply and extend my
`knowledge at Gigabit Wireless Inc. I am grateful to Prof. Jim Plummer for serving
`as chairman of my orals committee and to Prof. Tom Lee for agreeing to serve as my
`third reader.
`I am grateful for the financial support from Apple Computers, Accel Partners and
`Intel. Without their generous donations, this research would not have been realized.
`It was a privilege and a pleasure to be one of Cioffi's "kids". Given the size of the
`group, it's amazing how well we ali get along. I especially enjoyed the many lively
`discussions with Acha Leke and Susan Lin on a wide range of topics ranging from
`consulting to the stock market. Special thanks to Susan Lin for her enthusiasm and
`
`Vl
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 6 of 168
`
`

`

`unflagging willingness to help whenever the need arises. Thanks to Kok-Wui Cheong
`and Carlos Aldana for offering to set up and maintain the computer network for the
`group, and for responding above and beyond the call of duty on severa! occasions.
`Other members of this extended family whose friendship and support I have enjoyed
`include Krista Jacobsen, Rick Wesel, Phil Bednarz, Pete Chow, Minnie Ho, Greg
`Raleigh, Rohit Negi, Atul Salvekar, Nick (Zi-Ning) Wu, Joe Lauer, John Fan, Ardavan
`Maleki, Joonsuk Kim, Won-Joon Choi and Wonjong Rhee. I am grateful to Joice
`DeBolt for her invaluable assistance with all administrative work. I also like to extend
`best wishes to the new members of the group - A vneesh Agrawal, George Ginis,
`Jeannie Lee, Wei Yu and Steve Zeng.
`Outside of John's research group, I have been very fortunate to engage in discus(cid:173)
`sions with a group of very talented people. They are Suhas Diggavi, Bijit Halder,
`Miguel Lobo and Jorge Campello. Their insights have helped my research , but more
`importantly, I cherish t heir friendship. My thanks also go to Josep Añon, Jaime
`Cham, Gabriel Perigault, Ang~l Lozano and Daniel llar who have remained great
`friends since the early days at Stanford.
`As I write this,_ I aro afraid that several important people are being accidentally
`omitted. I apologize if you deserve to be here, but are not . I hope you can forgive
`the oversight.
`Through it all, I owe my greatest debt to my family - my parents, my brother
`Tony and my sister Monica. I am most grateful for their love, encouragement, and
`support throughout my life.
`To Louise, who has given me happiness and unwavering support in my life and
`work, thank you. Your love is the most rewarding experience of my graduate years.
`As I embark on new challenges in life, I know I will always reflect on my time at
`Stanford with great nostalgia.
`
`Jose Tellado-Mourelo
`September 17} 1999
`
`Vil
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 7 of 168
`
`

`

`Contents
`
`Abstract . . . . .
`Acknowledgment
`List of Tables .
`List of Figures
`
`1 Introduction
`1.1 Outline of Dissertation
`1.2 Research Contributions .
`
`2 Multicarrier Modulation
`2.1 Multicarrier Modulation . . . . .
`2.2 Partit ioning for Vector Coding ..
`2.3 Partitioning for DMT and OFDM
`2.4 Loading Principles
`.
`
`3 Peak to Average Ratio
`. .. .
`.
`3.1 Multicarrier Signals . . . . . . . . .
`3.2 Peak to Average Ratio . . . . . . . . .. . .
`3.3 Statistical Properties of Multicarrier Signals
`3.4 Bounds on Continuous-Time PAR using
`Discrete-Time Samples . . . . . . . . . .
`3.5 Descript ion of Memoryless Nonlinearity .
`3.6 Effect of Nonlinearities on System Performance
`3.6.1 PSD Degradation . . . . . . . . . . . . .
`
`viii
`
`lV
`
`Vl
`
`Xl
`xii
`
`1
`2
`3
`
`5
`6
`8
`9
`12
`
`15
`16
`22
`26
`
`29
`41
`44
`45
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 8 of 168
`
`

`

`3.6.2 BER Increase . . . . . . . . . ..
`3. 7 Limits for Distortionless PAR Reduction
`3.8 Techniques for PAR Reduction ....
`3.8.1 PAR Reduction with Distortion .
`3.8.2 Distortionless PAR Reduction ..
`3.9 New PAR Reduction Structures Proposed
`
`4 PAR Reduction by Tone Reservation
`. .. .
`.
`4.1 Problem Formulation .
`. . . . . . . .
`4.2 PAR Reduction Signals for Tone Reservation .
`4.3 Optimal PAR Reduction Signals for
`Tone Reservation . . . . . . . . . . . .
`4.4 Simple Gradient Algorithms with Fast
`Convergence . . . . . . . . . . . . . . .
`Iterative PAR Reduction as a Controlled
`Clipper . . . . . . . . . . . . . .. .. . .
`Tone Reservation Kernel Design . . . . .
`4.6.1 Computing Peak Reduction Kernels .
`4.6.2 Choosing the PRT Set n . ..... .
`4.6.3 Numerical Computation of n and p .
`4.7 Results . . . . . . . . . . . . . . ... ... .
`
`4.6
`
`4.5
`
`5 PAR Reduction by Tone Injection
`5.1 PAR Reduction using Generalized
`Constellations . . . . . . . . . . . .
`5.2 Power Increase
`. .. ... .... .
`5.3 Maximum PAR Reduction per Dimension
`Translation
`. . . . . . . . . . . . . . . . .
`5.4 Simple Algorithms for Computing x[n/ L] .
`5.5 Results . . .
`5.6 Conclusions
`
`. . . . . . . . . . . . . . . . .
`
`lX
`
`46
`53
`56
`58
`59
`63
`
`66
`67
`70
`
`73
`
`79
`
`87
`89
`90
`91
`94
`96
`
`100
`
`101
`106
`
`111
`113
`115
`121
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 9 of 168
`
`

`

`6 Maximum Likelihood D etection of Distorted M ulticarrier Signals 123
`6.1 Effects of a Memoryless Nonlinearity on
`Achievable Rate . . . . . . . . . . . . .
`6.2 Maximum Likelihood (ML) Detection .
`6.3 Numerical Results .
`6.4 Conclusions
`. . . . . . . .
`
`124
`130
`137
`141
`
`7 Summary and Conclusions
`7.1 T hesis Summary
`. . . . .
`
`Bibliography
`
`143
`143
`
`145
`
`X
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 10 of 168
`
`

`

`List of Tables
`
`. . . . . . . . . . . . . . . . . . . . . . .
`4.1 PRT and kernel complexity
`5.1 Maximum PAR reduction (in dB) vs. number of iterations. All tones
`carry 64QAM symbols and N = 64
`. . . . . . . . . . . . . . . . . . . 113
`5.2 Maximum PAR reduction (in dB) vs. number of iterations. All tones
`carry 16QAM symbols and N = 512.
`. . . . . . . . . . . . . . . . . . 114
`
`96
`
`Xl
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 11 of 168
`
`

`

`List of Figures
`
`3.1 DMT/OFDM Transmitter Block Diagram. . . . . . . . . . . . . . . .
`3.2 Different Multicairier Symbols: A) Basic, B) With CP and C) With
`CP and windowed extended CP-CS . . . . . . . . . . . . . . . . . . .
`3.3 Multicarrier Signals from Figure 3.2 . . . . . . . . . . . . . . . . . . .
`3.4 PSD of the discrete-time multicarrier signal in (3.14) for N = 512,
`L = 4 and Raised Cosine windows with different roll-off lengths
`3.5 CCDF of PAR{ xm(n]} for N = 256, 512, 1024, 2048
`. . . . . . . . .
`3.6 CCDF of PAR{xm(n/ L]} for L = 1, 2, 4, 16. . . . . . . . . . . . . .
`3.7 CCDF of PAR{xm(n/L]} for L = 2,4 given PAR{xm[n]} ~ 10 dB.
`3.8 Upper bound on the maximum of x(t) given x(n/ L) . . . . . . . . .
`3.9 PDF of x'(t) (Normalized by n N/Tv'3) . . . . . . . . . . . . . . . .
`3.10 CCDF of PAR{xm[n/ L]} for L = 4, 8 given PAR{xm(n/2]} ~ 10 dB
`. . . . . . .
`3.11 CCDF of PAR{xm[n/8]} given PAR{xm[n/4]} ~ 10 dB
`3.12 Peak CCDF at different points of an ADSL modero for an Ideal Over-
`Sampled PAR reduction method
`. . . . . . . . . . . . . . . . . . . .
`3.13 PSD for x[n/4) with tapered window wr[n] followed by a limiter . . .
`3.14 Analytical and simulated SER for N = 512 and 64QAM for the
`SL(8 dB) nonlinearity. . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.15 Analytical and simulated SER for N = 512 and 1024QAM for the
`SL(ll dB) nonlinearity.
`. . . . . . . . . . . . . . . . . . . .
`3.16 Diagram for pdfs of x, g(x) and x - g(x) . . . . . . . . . .
`3.17 Relative Capacity of Peak-Power-Limited AWGN channel .
`3.18 Additive model for PAR reduction. . . . . . . . . . . . . .
`
`17
`
`19
`20
`
`21
`28
`31
`32
`34
`36
`38
`39
`
`40
`46
`
`50
`
`51
`52
`55
`63
`
`Xll
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 12 of 168
`
`

`

`71
`
`79
`84
`
`86
`
`. . . . . . . . . . . . .
`Illustration of the Tone Reservation structure
`4.1
`4.2 PAR CCDF for a baseband multicarrier symbol of size N = 512 and
`oversampling L = 1 when i = 5% and i = 20% with Randomly-
`. . . . . . . . . .
`. . .
`Optimized set 1?.,*
`. . .
`. . . . . . . . . .
`. . .
`. . . . . . . . . . . . . . .
`Illustration of the SCR gradient algorithm
`4.3
`4.4 Signa! to Clipping Noise Power Ratio (SCR) improvement vs. number
`of iterations for both Optimized PRT with SCR gradient technique
`and Structured (Adjacent or Periodic) tone location. Iteration O cor-
`responds to original SCR . . . . . . . . . . . . . . . . . . . . . . . . .
`4.5 Probability that the PAR of a raudomly generated N = 512 baseband
`DMT / OFDM symbol exceeds P A.Ro for i = 5% for two index choices,
`Contiguous tones, 1?.,1¡2 = {244,245, ... 256} and randomly optimized
`set n· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`4.6 CDF and CCDF of the Kernel's second peak for R = 26 and N = 512.
`4.7 P AR(xm + cm(i)) distribution for i = 1, ... , 10 and ~ = 5%. Contigu-
`ous tone set with n1;2 = {244,245, ... 256} . . . . . . . . . . . . . . .
`4.8 P AR(xm + cm(i)) distribution for i = 1, ... , 10, 40 and i = 5% with
`Randomly Optimized set n• . . . . . . . . . . . . . . . . . . . . . . .
`99
`. . . . . . . . . 102
`5.1 Block Diagram for the Tone Injection PAR reduction
`5.2 Tbe constellation value A is the mínimum energy point of tbe equiva-
`lent set A = A + PkD + jqkD
`. . . . . . . . . . . . . . . . . . . . . . 103
`5.3 Generalized constellation for 16QAM for a given value D, wben IPkl ::; 1
`and Jqkl ::; l. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
`5.4 Tone Injection PAR CCDF for N = 64, 16QAM and p = 1 . . . . . . 116
`5.5 Tone Injection PAR CCDF for N = 256, 16QAM and p = 1.75 for
`iterations i = 1, . . . , 6.
`. . . . . . . . . . . . . . . . . . . . . . . . . . 117
`5.6 Peak CCDF at four different points of an ADSL transmitter: standard
`IFFT output (x[n]), twice oversampled Tone Injection PAR reduction
`output (x[n/2]), twice oversampled FIR HPF output (z[n/2) = x[n/2)*
`hpf[n/2]), and 4x oversampled FIR LPF output (z[n/4] * lpf[n/4])
`118
`. . 119
`5.7 Same as Figure 5.6 with Butterworth HPF and Butterworth LP F
`
`93
`97
`
`98
`
`xiii
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 13 of 168
`
`

`

`5.8 Sarne as Figure 5.6 for the ADSL transrnit filter provided by Pairgain 120
`5.9 Peak CCDF at the 4 x oversarnpled filtered output when the t ransmit
`filters are included in the PAR reduction algorithrn
`. . . . . . . . . . 121
`6.1 Channel nonlinear model for computing mutual information. . . . . . 125
`6.2 Channel capacity and mutual inforrnation for a ClipLevel of 5dB and
`. . . . . . . . . . . . . . 127
`7 dB for the Soft Lirniter (SL) nonlinearity.
`6.3 Relative mutual information for a ClipLevel of 5dB, 7dB and 9dB for
`the Soft Limiter (SL) nonlinearity. . . . . . . . . . . . . . . . . . . . . 128
`6.4 Relative mutual inforrnation for a ClipLevel of 5dB, 7dB and 9dB for
`the Solid-State Power Amplifier (SSPA) nonlinearity.
`. . . . . . . . . 129
`6.5 Channel capacity and practica! data rates for a ClipLevel of 5dB, 7dB
`and 9dB for the Soft Limiter (SL) if distortion term is assumed to be
`AWGN . ........ . .. .. .. .. . . . . . . . . . . . . . . . .. . 134
`Iterative ( quasi-ML) nonlinear distortion canceler. . . . . . . . . . . . 135
`6.6
`6.7 Performance of the iterative-ML algorithm for a SL nonlinearity when
`N = 512, L = 1 and ClipLevel = 9dB.
`. . . . . . . . . . . . . . . . . 138
`6.8 Performance of the iterative-ML algorithm for a SSPA nonlinearity
`when N = 512, L = 1 and ClipLevel = lldB.
`. . . . . . . . . . . . . 139
`6.9 Performance of the iterative-ML algorithm for the Gaussian clip win(cid:173)
`dowing nonlinearity with Gaussian clip windowing when N = 4096,
`L = 2 and ClipLevel = 9dB. . . . . . . . . . . . . . . . . . . . . . . . 140
`· 6.10 Performance of the iterative-ML algorithm for a SL nonlinearity when
`N = 4096, L = 2 and ClipLevel = 8dB.
`. . . . . . . . . . . . . . . . 141
`
`XlV
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 14 of 168
`
`

`

`Chapter 1
`
`Introduction
`
`T HE DEMAND FOR HIGH DATA RATE SERVICES has been increasing very rapid(cid:173)
`
`ly and there is no slowdown in sight. Almost every existing physical medium
`capable of supporting broadband data transmission to our homes, offices and schools,
`has been or will be used in the future. This includes both wired (Digital Subscriber
`Lines, Cable modems, Power Lines) and wireless media. Often, these services require
`very reliable data transmission over very harsh environments. Most of these transmis(cid:173)
`sion systems experience many degradations, such as large attenuation, noise, multi(cid:173)
`path, interference, time variation, nonlinearities, and must meet many constraints,
`such as fi.nite transmit power and most importantly ji,nite cost. One physical-layer
`technique that has recently gained much popularity due to its robustness in dealing
`with these impairments is multicarrier modulation.
`Unfortunately, one particular problem with multicarrier signals, that is often cited
`as the major drawback of multicarrier transmission, is its large envelope fluctuation,
`which is usually quantifi.ed by the parameter called Peak-to-Average Ratio (PAR).
`Since most practica} transmission systems are peak-power límited, designing the sys(cid:173)
`tem to operate in a perfectly linear region often implies operating at power levels
`well below the maximum power available. In practice, to avoid operating the am(cid:173)
`plifi.ers with extremely large back-offs, occasional saturation of the power amplifi.ers
`or clipping in the digital-to-analog-converters must be allowed. This additional non(cid:173)
`linear distortion creates inter-modulation distortion that increases the bit error rate
`
`1
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 15 of 168
`
`

`

`Chapter 1 .. Introduction
`
`2
`
`in standard linear receivers, and also causes spectral widening of the transmit signal
`that increases adjacent channel interference to other users. This dissertation derives a
`number of relevant results regarding PAR analysis and designs a number of efficient,
`low complexity PAR reduction algorithms.
`While most derivations and results are described for multicarrier modulation based
`on the discrete-time or continuous-time Fourier basis, many of t hese results can be
`extended to other multicarrier modulation methods, such as Vector Coding, Discrete
`Wavelet Multitone, etc. Moreover, sorne results can be applied to non-multicarrier
`modulations, such as single carrier modulation or Direct-Sequence Spread Spectrum
`to name a few. For the single-carrier case, the transmit basis is generated from the
`equivalent transmit pulse shaplng function. If this transmit pulse shaping function
`has considerable energy over ·several symbols, the three main PAR reduction ideas
`described in this dissertaüon can be applied, although the algorithms described must
`be modified. Similarly, many of our PAR reduction ideas can be utilized whenever
`multiple Direct-Sequence Spread Spectrum signals or multiple single carrier signals
`are combined.
`
`1.1 Outline of Dissertation
`
`Chapter 2 introduces inulticarrier modulation and more specifically the two most
`commonly used orthogonal multicarrier modulation types, Discrete Multitone (DMT)
`and Orthogonal Frequency Division Multiplexing (OFDM).
`Chapter 3· describes real and complex multicarrier signals using continuous-time
`and discrete-time formulations and formally introduces the concept of PAR. This
`chapter also derives bounds on the PAR of the continuous-time symbols given the
`discrete-time samples. Since the PAR reduction methods described in Chapters 4
`and 5 are simplified when operating on discrete-time symbols, these bounds can be
`used to predict the continuous-time PAR. Also, several common nonlinear models are
`pr~sented and their effect on multicarrier demodulation is evaluated.
`Chapter 4 presents the first new distortionless PAR reduction structure, called
`Tone Reservation. The exact solution to this PAR minimization problem, as well as
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 16 of 168
`
`

`

`Chapter 1. Introduction
`
`3
`
`eflicient suboptimal solutions are described followed by a number of simulation results
`for practica} multicarrier systems.
`Chapter 5 describes a second distortionless PAR reduction structure, called Tone
`Injection. Since the exact solution to this PAR minimization problem has non(cid:173)
`polynomial complexity, limits on maximum PAR reduction are derived. Efficient
`suboptimal solutions that achieve close to optima! performance are proposed.
`Chapter 6 evaluates the performance of multicarrier transmission in the presence of
`nonlinear distortion. Theoretical Mutual Information limits are derived. The optima!
`maximum likelihood receiver and an efficient demodulator based on the maximum
`likelihood receiver are also described.
`
`1.2 Research Contributions
`
`The main contributions of this dissertation are the analysis of PAR for multicarrier
`modulation and the design of severa! new structures for PAR reduction. The details
`of these contributions are listed below by chapter.
`
`• Chapter 3) Derives absolute and statistical bounds on the PAR of continuous(cid:173)
`time multicarrier signals given the discrete-time samples. These bounds are
`very important since all the proposed PAR reduction techniques are described
`in terms of discrete-time symbols. Chapter 3 also introduces a new and more
`accurate expression for evaluating the uncoded Bit Error Rate of nonlinearly
`distorted multicarrier signals.
`
`• Chapter 4) Introduces the first novel PAR reduction method called Tone Reser(cid:173)
`vation. This new structure reduces the PAR by optimizing the values of a small
`subset of tones. Both optima! and suboptimal algorithms are proposed.
`
`• Chapter 5) Introduces a second novel PAR reduction method called Tone Injec(cid:173)
`tion. PAR reduction is achieved based on a reversible constellation expansion.
`Theoretical bounds on PAR reduction and power increases are derived. Low
`complexity algorithms are derived.
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 17 of 168
`
`

`

`Chapter l. Introduction
`
`4
`
`• Chapter 6) Derives new expressions for characterizing the achievable rates in
`the presence of nonlinear distortion. The optimal receiver, under finite symbol
`sízes is derived. Low complexity algorithms, based on maximum likelihood are
`proposed.
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 18 of 168
`
`

`

`Chapter 2
`
`Multicarrier Modulation
`
`A CHIEVING DATA RATES that approach capacity over noisy linear channels with
`
`memory, requires sophisticated transmission schemes that combine coding and
`shaping with modulation and equalization. While it is known that a single-carrier
`system employing a minimum-mean-square error decision-feedback equalizer can be,
`in sorne cases, theoretically optimum [1], the implementation of this structure in
`practice is difficult. In particular, the required lengths of the transmit pulse shaping
`filters and the receiver equalizers can be long and the symbol-rate must be optimized
`for each channel. An alternative scheme that is more suitable for a variety of high(cid:173)
`speed applications on difficult channels, is the use of multicarrier modulation, which is
`also optima! for the infinite-length case. The term multicarrier modulation includes a
`number of t ransmission schemes whose main characteristic is the decomposition of any
`wideband tharÍnel into a set of independent narrowband channels. Within this family,
`the most commonly used schemes are Discrete Multitone (DMT ) and Orthogonal
`Frequency Division Multiplexing (OFDM), which are based on the Discrete Fourier
`Transform, resulting in an implementable, high performance structure.
`The main focus of this chapter is to introduce sorne of the basic ideas of mul(cid:173)
`ticarrier modulation and provide the necessary background for understanding the
`subsequent chapters. More detailed descriptions can be found in listed references.
`
`5
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 19 of 168
`
`

`

`Chapter 2. Multicarrier Modulation
`
`6
`
`2.1 Multicarrier Modulation
`
`All multicarrier modulation techniques are based on the concept of channel partition(cid:173)
`ing. Channel Partitioning methods divide a wideband, spectrally shaped transmis(cid:173)
`sion channel into a set of parallel and ideally independent narrowband subchannels.
`Although channel partitioning is introduced here, the reader is referred to [2, Chap(cid:173)
`ter 10] for a more in-depth tutorial description of channel partitioning for both the
`continuous-time case and the discrete-time case. For the continuous-time·case, the op(cid:173)
`timum channel-partitioning basis functions are the set of orthonormal eigenfunctions
`of the channel autocorrelation function. These eigenfunctions are generally diffi.cult to
`compute for finite symbol periods and are not used in practica! applications. Instead,
`we will focus on discr:ete-time channel partitioning, which partitions a discrete-time
`description of the. channel. For this case, it is, assumed that the combined effect of
`transmit filters, transmission ohannel and received filters can be approximated by a
`finite impulse response (FIR) filter. Such a description is not exact, but can be a
`close description as long as a suffi.cient number of samples for the input and output of
`the channel is included and good timing and frequency estimation is achieved [3, 4].
`Calling h = [ho · · · hv] the baseband complex discrete-time representation of the
`channel impulse response, the block of output samples y = [y0 · · · YN-i] can be ex(cid:173)
`pressed as a function of the input samples x = [x-v · · · x_1 x0 · • · XN-i] and the
`channel noise n = [no ··· nN-i) using the following standard vector representation,
`
`[ y::l ]
`
`. . . hv O o
`ho h1
`o ho h1
`. . . hv o
`
`o
`o
`
`o
`
`o ho h1
`
`·.. hv
`
`XN-1
`
`X¡
`Xo
`
`X_v
`
`+ [ n]:']
`
`(2.1)
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 20 of 168
`
`

`

`Chapter 2. Multicarrier Modulation
`
`This can be written more compactly as
`
`y =Hx+n
`
`7
`
`(2.2)
`
`Equation (2.2) represents the input-output relationship for a single block of samples.
`In a practica} communication system, we may transmit in a continuous manner and
`(2.2) becomes ym = Hxm + n m where the index m represents the m-th block.
`To send information over a finite-length multicarrier system, the data must be
`partitioned into blocks of bits, and each block must be mapped into a vector of
`complex symbols xm = [xr · · · X ~_1]. The modulated waveform xm is
`xm = L mkx-;;- = Mxm
`
`(2.3)
`
`N-1
`
`k=O
`
`where { m k, k = O, ... , N -
`l} denote the set of transmit basis vectors and M is the
`matrix constructed with the transmit basis vectors as its columns. At the receiver,
`t he received vector y m is demodulated by computing
`
`ym =
`
`N-1
`
`f* ym]
`:
`= F*ym
`r;ym
`
`[
`
`(2.4)
`
`where { r;, k = O, ... , N - 1} denote the set of receive basis vectors and F* is t he
`matrix constructed with the receive basis vectors as its rows. The overall input-output
`relationship is given by,
`
`y m = F*HMXm +F*n
`
`(2.5)
`
`Different choices for F and M are possible, leading to a number of possible multicarrier
`structures. For the simple case where the channel is memoryless, h = [ho O··· O],
`choosing M to be an orthogonal matrix i.e. M-1 = M*, and setting F = M result in
`perfect channel partitioning. That is, the output vector components can be expressed
`as a function of only one input component and (2.5) can be simplified to N scalar
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 21 of 168
`
`

`

`Chapter 2. Multicarrier Modulation
`
`8
`
`equations:
`
`ykm = hoXí:' + Ní:, k = O, ... , N - 1
`
`(2.6)
`
`where t he noise samples Nr, are independent identically distributed (i.i.d) Gaussian
`samples. For non-trivial channels, a variety of multicarrier structures have been
`proposed, each with a different choice of basis vectors. Sections 2.2 and 2.3 .describe
`two asymptotically optimal multicarrier structures called Vector Coding [5, 6, 7] and
`DMT/OFDM [8, 9, 10, 11, 12, 13, 14]. Other proposed structures include Discrete
`Hartley Transform (DHT) basis vectors [15] and the M-band wavelet transform in
`Discrete Wavelet Multitone (DWMT) modulation [16].
`
`2.2 Partitioning for Vector Coding
`
`The matrix H of size N x (N + v) in (2.2) has a Singular Value Decomposition (SVD)
`
`H = U[A: ON,v]V*
`
`(2.7)
`
`where U is an N x N unitary matrix, V is an (N + v) x (N + v) unitary matrix,
`and O N,v is an N x v matrix of zeros. A is an N x N diagonal matrix with singular
`values >.k, k =O, ... , N along the diagonal. Vector Coding creates a set of N parallel
`independent channels by choosing as transmit basis vectors mk, the first N rows of
`V , i.e. M = V, andas receive basis vectors fk , the rows of U*, i.e. F = U. With these
`substitutions in (2.5) and letting jcm = [Xm*; 01,v]* ,
`
`ym
`
`U* HVX.m + U*nm
`
`U*U[A:ON,v]V*VX.m + U*nm
`[A:ON,v]xm + U*nm
`- AXm+Nm
`
`(2.8)
`
`(2.9)
`
`(2.10)
`
`(2.11)
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 22 of 168
`
`

`

`Chapter 2. Multicarrier Modulation
`
`9
`
`Since U is unitary, the noise vector Nm is also additive white Gaussian with vari(cid:173)
`ance per dimension identical to n m. Equation (2.11) can also be expressed as N
`independent channels just as for the memoryless case in (2.6)
`
`(2.12)
`
`From this derivation shows that vector coding avoids ISI by appending zeros to xm
`in (2.8) and by using the right and left singular vectors of the Toeplitz channel matrix
`H as transmit and receive vectors. Although it can be shown that Vector Coding has
`the maximum Signal to Noise Ratio (SNR) for any discrete channel partitioning [2],
`it is not used in practica! applications due to the complexity involved in computing
`the SVD.
`
`2.3 Partitioning for DMT and OFDM
`
`Discrete MultiTone (DMT) and Orthogonal Frequency Division Multiplexing (OFDM)
`are the most common channel partitioning methods. By adding a restriction to the
`transmit sequence, the complexity of the transmitter and receiver is much lower than
`the Vector Coding case. Both DMT and OFDM use the same partitioning matri(cid:173)
`ces, they only differ in the computation of the data vector xm. For OFDM all the
`components of the data vector X'f\ k = O, ... , N -
`l, i.e. all the subchannels are
`chosen from the same distribution. DMT modulators optimize the amount of en(cid:173)
`ergy Ek and also the amount of bits bk in each subchannel to maximize the overall
`performance over a given channel. This optimization is called loading and will be
`described in more detail in Section 2.4. OFDM is typically used for broadcast or for
`point-to-point transmission in fast time-varying wireless environments where the re(cid:173)
`ceiver cannot feedback to the transmitter the optimal bits and energies. OFDM is the
`modulation format chosen for Digital Audio Broadcast (DAB) [17] and Digital Video
`Broadcast (DVB) [18, 19] and for second generation Hlgh PErformance Radio Local
`Area Networks (HIPERLAN). DMT is used for point-to-point applications, usually
`on slowly time-varying channels, such as telephone lines [20, 21]. DMT has been
`
`CSCO-1025
`Cisco v. TQ Delta, IPR2016-01021
`Page 23 of 168
`
`

`

`Cbapter 2. Multicarrier Modulation
`
`10
`
`chosen as the modulation format for Asymmetric Digital Subscriber Line (ADSL),
`twisted pair telephone lines standard (ANSI Tl.413 (22] and ITU G.992 (23]) and is
`also a major contender in the ongoing Very high data rate Digital Subscriber Line
`(VDSL) standard.
`To achieve channel partitioning, DMT /OFDM forces the modulated transmit vec(cid:173)
`tor xm to satisfy the constraint
`
`x1!:k = xy.J _k, k = 1, ... ,